Introduction to Management Science (10th Edition)
| So far we have discussed maximization problems with all
A mixed constraint problem includes a combination of
A leather shop makes custom-designed , hand-tooled briefcases and luggage. The shop makes a $400 profit from each briefcase and a $200 profit from each piece of luggage. (The profit for briefcases is higher because briefcases require more hand tooling.) The shop has a contract to provide a store with exactly 30 items per month. A tannery supplies the shop with at least 80 square yards of leather per month. The shop must use at least this amount but can order more. Each briefcase requires 2 square yards of leather; each piece of luggage requires 8 square yards of leather. From past performance, the shop owners know they cannot make more than 20 briefcases per month. They want to know the number of briefcases and pieces of luggage to produce in order to maximize profit. This problem is formulated as where x 1 = briefcases and x 2 = pieces of luggage. The first step in the simplex method is to transform the inequalities into equations. The first constraint for the contracted items is already an equation; therefore, it is not necessary to add a slack variable. There can be no slack in the contract with the store because exactly 30 items must be delivered. Even though this equation already appears to be in the necessary form for simplex solution, let us test it at the origin to see if it meets the starting requirements.
Because zero does not equal 30, the constraint is not feasible in this form. Recall that a x 1 + x 2 + A 1 = 30 Now at the origin, where x 1 = 0 and x 2 = 0,
An artificial variable is added to an equality (=) constraint for standard form.
Any time a constraint is initially an equation, an artificial variable is added. However, the artificial variable cannot be assigned a value of M in the objective function of a maximization problem. Because the objective is to maximize profit, a positive M value would represent a large positive profit that would definitely end up in the final solution. Because an artificial variable has no real meaning and is inserted into the model merely to create an initial solution at the origin, its existence in the final solution would render the solution meaningless. To prevent this from happening, we must give the artificial variable a large cost contribution, or M . The constraint for leather is a 2 x 1 + 8x 2 s 1 + A 2 = 80
An artificial variable in a maximization problem is given a large cost contribution to drive it out of the problem.
As in the equality constraint, the artificial variable in this constraint must be assigned an objective function coefficient of M . The final constraint is a x 1 + s 2 = 20 The completely transformed linear programming problem is as follows : The initial simplex tableau for this model is shown in Table A-21. Notice that the basic solution variables are a mix of artificial and slack variables . Note also that the third-row quotient for determining the pivot row (20 ·0) is an undefined value, or Table A-21. The Initial Simplex Tableau
Table A-22. The Second Simplex Tableau
Table A-23. The Third Simplex Tableau
Table A-24. The Optimal Simplex Tableau
The solution for the leather shop problem is (see Table A-24): x 1 = 20 briefcases x 2 = 10 pieces of luggage s 1 = 40 extra yd 2 of leather Z = $10,000 profit per month It is now possible to summarize a set of rules for transforming all three types of model constraints.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||