Maximize 100X1 + 160X2 Subject to: 6X1 + 14X2 ≤ 42 7X1 + 7X2 ≤ 35 X1, X2 are non-negative integers. For this small example, one may find all 14 feasible solutions directly from the feasible region, i.e., Figure 6.1 in the above reference. Using the objective function iso-value lines, the optimal solution is at point (X1 = 4, X2 = 1), with the optimal value of 560. This solution is superior to (X1 = 5, X2 = 0) with objective function value of 500 given therein. Notice that the optimal solution in on the boundary line 7X1 + 7X2 = 35, but not a vertex as is found in the above reference. Whenever there is integrality condition on some decision variable, then the optimal solution (if exists) might be located anywhere on the feasible region. It might be one of the vertices, could be on the boundary or even inside the feasible region.
See Full PDF See Full PDFJournal of Applied Mathematics and Decision Sciences
In a fast changing global market, a manager is concerned with cost uncertainties of the cost matrix in transportation problems (TP) and assignment problems (AP).A time lag between the development and application of the model could cause cost parameters to assume different values when an optimal assignment is implemented. The manager might wish to determine the responsiveness of the current optimal solution to such uncertainties. A desirable tool is to construct a perturbation set (PS) of cost coeffcients which ensures the stability of an optimal solution under such uncertainties. The widely-used methods of solving the TP and AP are the stepping-stone (SS) method and the Hungarian method, respectively. Both methods fail to provide direct information to construct the needed PS. An added difficulty is that these problems might be highly pivotal degenerate. Therefore, the sensitivity results obtained via the available linear programming (LP) software might be misleading. We propose a unified pivotal solution algorithm for both TP and AP. The algorithm is free of pivotal degeneracy, which may cause cycling, and does not require any extra variables such as slack, surplus, or artificial variables used in dual and primal simplex. The algorithm permits higher-order assignment problems and side-constraints. Computational results comparing the proposed algorithm to the closely-related pivotal solution algorithm, the simplex, via the widely-used pack-age Lindo, are provided. The proposed algorithm has the advantage of being computationally practical, being easy to understand, and providing useful information for managers. The results empower the manager to assess and monitor various types of cost uncertainties encountered in real-life situations. Some illustrative numerical examples are also presented."
Download Free PDF View PDF
