A Mixed Constraint Problem Page 1 of 4
[Page A-21]
A Mixed Constraint Problem
So far we have discussed maximization problems with all constraints and minimization
problems with all constraints. However, we have yet to solve a problem with a mixture 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 mixed constraint problem includes a combination of , =, 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 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 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 necessary form for
simplex solution, let us test it at the origin to see if it meets the starting requirements.
x1 + x2 = 30
0+0 = 30
0 30
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 variable
was added. The same thing can be done here.
mk:@MSITStor[Link]\Users\MSFuser\Desktop\private%20document\[Link]... 2/26/2025
A Mixed Constraint Problem Page 2 of 4
x1 + x2 + A1 = 30
Now at the origin, where x1 = 0 and x2 = 0,
0 + 0 + A1 = 30
A1 = 30
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.
[Page A-22]
The constraint for leather is a inequality. It is converted to equation form by subtracting a
surplus variable and adding an artificial variable:
2x1 + 8x2 s1 + A2 = 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 inequality and is transformed by adding a slack variable:
x1 + s2 = 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 . Therefore, this row would never
mk:@MSITStor[Link]\Users\MSFuser\Desktop\private%20document\[Link]... 2/26/2025
A Mixed Constraint Problem Page 3 of 4
be considered as a candidate for the pivot row. The second, third, and optimal tableaus for this
problem are shown in Tables A-22, A-23, and A-24.
Table A-21. The Initial Simplex Tableau
400 200 0 0 M M
Basic
cj Variables Quantity x1 x2 s1 s2 A1 A2
M A1 30 1 1 0 0 1 0
M A2 80 2 8 1 0 0 1
0 s2 20 1 0 0 1 0 0
zj 110M 3M 9M M 0 M M
c j zj 400 + 200 + M 0 0 0
3M 9M
Table A-22. The Second Simplex Tableau
400 200 0 0 M
Basic
cj Variables Quantity x1 x2 s1 s2 A1
M A1 20 3/4 0 1/8 0 1
200 x2 10 1/4 1 1/8 0 0
0 s2 20 1 0 0 1 0
zj 2,000 20M 50 3M/4 200 25 M/8 0 M
c j zj 350 + 3M/4 0 25 + M/8 0 0
[Page A-23]
Table A-23. The Third Simplex Tableau
400 200 0 0 M
Basic
cj Variables Quantity x1 x2 s1 s2 A1
M A1 5 0 0 1/8 3/4 1
200 x2 5 0 1 1/8 1/4 0
400 x1 20 1 0 0 1 0
zj 9,000 5M 400 200 25 M/8 350 + 3M/4 M
c j zj 0 0 25 + M/8 350 3M/4 0
mk:@MSITStor[Link]\Users\MSFuser\Desktop\private%20document\[Link]... 2/26/2025
A Mixed Constraint Problem Page 4 of 4
Table A-24. The Optimal Simplex Tableau
400 500 0 0
Basic
cj Variables Quantity x1 x2 s1 s2
0 s1 40 0 0 1 6
200 x2 10 0 1 0 1
400 x1 20 1 0 0 1
zj 10,000 400 200 0 200
c j zj 0 0 0 200
The solution for the leather shop problem is (see Table A-24):
x1 = 20 briefcases
x2 = 10 pieces of luggage
s1 = 40 extra yd2 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.
Objective Function
Coefficient
Constraint Adjustment MAXIMIZATION MINIMIZATION
Add a slack variable 0 0
= Add an artificial variable M M
Subtract a surplus variable 0 0
and add an artificial M M
variable
mk:@MSITStor[Link]\Users\MSFuser\Desktop\private%20document\[Link]... 2/26/2025
