A Mixed Constraint Problem
A Mixed Constraint Problem
A mixed constraint problem includes a combination of … , =, and Ú constraints.
So far we have discussed maximization problems with all … constraints and minimiza- tion problems with all Ú constraints. However, we have yet to solve a problem with a mix- ture of … , Ú , and = constraints. Furthermore, we have not yet looked at a maximization problem with a Ú constraint. The following is a maximization problem with … , Ú , and = constraints.
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 can- not 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
maximize Z = $400x1 + 200x2 subject to
c o n t r a c t e d i t e m s o f l e a t h e r b r i e f c a s e s x 1 , x 2 Ú 0 x 1 … 2 0 2 x 1 + 8 x 2 Ú 8 0 y d . 2 x 1 + x 2 = 3 0
where x1 = briefcases and x2 = 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 neces- sary form for simplex solution, let us test it at the origin to see if it meets the starting requirements:
x 1 + x 2 = 3 0
+ 0 = 30
An artificial variable is added to an equality (=) constraint for standard form.
Because zero does not equal 30, the constraint is not feasible in this form. Recall that a Ú constraint did not work at the origin either in an earlier problem. Therefore, an artificial vari- able was added. The same thing can be done here:
x1 + x2 + A1 = 30 Now at the origin, where x1 = 0 and x2 = 0,
A 1 = 3 0 0 + 0 + A 1 = 3 0
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 maximiza- tion 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