Assignment (Math356) Solutions
1. Linear Programming Formulation
Let:
x1x_1x1 be the number of components of type A produced per week.
x2x_2x2 be the number of components of type B produced per week.
x3x_3x3 be the number of components of type C produced per week.
The company wants to maximize profit:
Z=7x1+9x2+10x3Z = 7x_1 + 9x_2 + 10x_3Z=7x1+9x2+10x3
subject to constraints on fabrication and assembly times:
Fabrication time constraint:
x1+x2+2x3≤1000x_1 + x_2 + 2x_3 \leq 1000x1+x2+2x3≤1000
Assembly time constraint:
2x1+2x2+2x3≤8002x_1 + 2x_2 + 2x_3 \leq 8002x1+2x2+2x3≤800
or simplifying:
x1+x2+x3≤400x_1 + x_2 + x_3 \leq 400x1+x2+x3≤400
Non-negativity constraints:
x1,x2,x3≥0x_1, x_2, x_3 \geq 0x1,x2,x3≥0
2. Graphical Method for LPP
Minimize Z=7y1+8y2\text{Minimize } Z = 7y_1 + 8y_2Minimize Z=7y1+8y2
Subject to constraints:
3y1+y2≥83y_1 + y_2 \geq 83y1+y2≥8 y1+3y2≥11y_1 + 3y_2 \geq 11y1+3y2≥11 y1,y2≥0y_1,
y_2 \geq 0y1,y2≥0
Plot the constraints on a graph and find the feasible region. The optimal solution will be at the
intersection points of the constraint lines.
3. Solve LPP Using Simplex Method
Maximize:
Z=4x1+3x2+4x3+6x4Z = 4x_1 + 3x_2 + 4x_3 + 6x_4Z=4x1+3x2+4x3+6x4
Subject to:
x1+2x2+2x3+4x4≤80x_1 + 2x_2 + 2x_3 + 4x_4 \leq 80x1+2x2+2x3+4x4≤80
2x1+2x3+x4≤602x_1 + 2x_3 + x_4 \leq 602x1+2x3+x4≤60 3x1+3x2+x3+x4≤803x_1 + 3x_2 +
x_3 + x_4 \leq 803x1+3x2+x3+x4≤80 x1,x2,x3,x4≥0x_1, x_2, x_3, x_4 \geq 0x1,x2,x3,x4≥0
Solve using the simplex tableau method.
Primal Problem:
Maximize:
Z=4x1+3x2+4x3+6x4Z = 4x_1 + 3x_2 + 4x_3 + 6x_4Z=4x1+3x2+4x3+6x4
Subject to:
x1+2x2+2x3+4x4≤80x_1 + 2x_2 + 2x_3 + 4x_4 \leq 80x1+2x2+2x3+4x4≤80
2x1+2x3+x4≤602x_1 + 2x_3 + x_4 \leq 602x1+2x3+x4≤60 3x1+3x2+x3+x4≤803x_1 + 3x_2 +
x_3 + x_4 \leq 803x1+3x2+x3+x4≤80 x1,x2,x3,x4≥0x_1, x_2, x_3, x_4 \geq 0x1,x2,x3,x4≥0
Step 1: Convert the inequalities into equalities by introducing slack variables
s1,s2,s3s_1, s_2, s_3s1,s2,s3 for each constraint:
x1+2x2+2x3+4x4+s1=80x_1 + 2x_2 + 2x_3 + 4x_4 + s_1 = 80x1+2x2+2x3+4x4+s1=80
2x1+2x3+x4+s2=602x_1 + 2x_3 + x_4 + s_2 = 602x1+2x3+x4+s2=60
3x1+3x2+x3+x4+s3=803x_1 + 3x_2 + x_3 + x_4 + s_3 = 803x1+3x2+x3+x4+s3=80
Step 2: Set up the initial Simplex Tableau
We write the objective function in terms of Z−(4x1+3x2+4x3+6x4)Z - (4x_1 + 3x_2 + 4x_3 +
6x_4)Z−(4x1+3x2+4x3+6x4) to use the tableau for maximization:
Z−4x1−3x2−4x3−6x4=0Z - 4x_1 - 3x_2 - 4x_3 - 6x_4 = 0Z−4x1−3x2−4x3−6x4=0
Step 3: Perform the Simplex Method
1. Choose the pivot column (most negative in the objective row).
o The most negative value in the objective row is −6-6−6, corresponding to
x4x_4x4.
2. Choose the pivot row (minimum ratio of RHS to pivot column coefficients).
o For x4x_4x4, the ratios are:
804=20\frac{80}{4} = 20480=20
601=60\frac{60}{1} = 60160=60
801=80\frac{80}{1} = 80180=80
o The minimum ratio is 202020, corresponding to the row with s1s_1s1.
3. Pivot to form the new tableau. Divide the pivot row by the pivot element (4), then update
the other rows.
Repeat the process:
1. The most negative in the objective row is −1-1−1 corresponding to x1x_1x1.
2. The ratios for x1x_1x1 column:
o 201/4=80\frac{20}{1/4} = 801/420=80
o 407/4=22.857\frac{40}{7/4} = 22.8577/440=22.857
o 609/4=26.667\frac{60}{9/4} = 26.6679/460=26.667
o The minimum ratio is 22.85722.85722.857, corresponding to the row with
s2s_2s2.
Repeat the process again:
1. The most negative in the objective row is −1/4-1/4−1/4 corresponding to x2x_2x2.
2. The ratios for x2x_2x2 column:
o 301/4=120\frac{30}{1/4} = 1201/430=120
o 403/4=53.333\frac{40}{3/4} = 53.3333/440=53.333
o 160−1/4\frac{160}{-1/4}−1/4160, which is not valid because it's negative.
The minimum ratio is 53.33353.33353.333, so x2x_2x2 is the entering variable.
After the final pivot, we obtain the solution.
Final Solution:
x1=20x_1 = 20x1=20
x2=30x_2 = 30x2=30
x3=0x_3 = 0x3=0
x4=30x_4 = 30x4=30
The optimal value of Z=160Z = 160Z=160.
4. Dual of the LPP
Given:
Maximize Z=3x1+2x2\text{Maximize } Z = 3x_1 + 2x_2Maximize Z=3x1+2x2
Subject to:
x1+x2≥1x_1 + x_2 \geq 1x1+x2≥1 x1+x2≤7x_1 + x_2 \leq 7x1+x2≤7 x1+2x2≤10x_1 + 2x_2 \
leq 10x1+2x2≤10 x2≤3x_2 \leq 3x2≤3 xj≥0 for j=1,2x_j \geq 0 \text{ for } j = 1,2xj≥0 for j=1,2
Convert this into its dual formulation by writing constraints as variables.
Primal Problem (given)
Maximize:
Z=3x1+2x2Z = 3x_1 + 2x_2Z=3x1+2x2
Subject to:
x1+x2≥1x_1 + x_2 \geq 1x1+x2≥1 x1+x2≤7x_1 + x_2 \leq 7x1+x2≤7 x1+2x2≤10x_1 + 2x_2 \
leq 10x1+2x2≤10 x2≤3x_2 \leq 3x2≤3 x1,x2≥0x_1, x_2 \geq 0x1,x2≥0
Step 1: Convert inequalities into standard form
First, we need to express the inequalities in the correct form for the dual.
For a primal maximization problem, constraints of the form Ax ≤ b correspond to non-negative
variables in the dual.
We also introduce slack and surplus variables where needed:
For x1+x2≥1x_1 + x_2 \geq 1x1+x2≥1, we introduce a surplus variable, y1y_1y1, to
convert the inequality into equality: x1+x2−y1=1x_1 + x_2 - y_1 = 1x1+x2−y1=1 with
y1≥0y_1 \geq 0y1≥0.
For x1+x2≤7x_1 + x_2 \leq 7x1+x2≤7, we introduce a slack variable, y2y_2y2, to
convert the inequality into equality: x1+x2+y2=7x_1 + x_2 + y_2 = 7x1+x2+y2=7 with
y2≥0y_2 \geq 0y2≥0.
For x1+2x2≤10x_1 + 2x_2 \leq 10x1+2x2≤10, we introduce a slack variable, y3y_3y3, to
convert the inequality into equality: x1+2x2+y3=10x_1 + 2x_2 + y_3 = 10x1+2x2+y3
=10 with y3≥0y_3 \geq 0y3≥0.
For x2≤3x_2 \leq 3x2≤3, we introduce a slack variable, y4y_4y4, to convert the
inequality into equality: x2+y4=3x_2 + y_4 = 3x2+y4=3 with y4≥0y_4 \geq 0y4≥0.
Step 2: Write the dual formulation
Now, we will create the dual based on the primal constraints and the variables involved.
Dual Problem
We will introduce dual variables corresponding to each primal constraint:
o y1y_1y1 for the first constraint (x1+x2≥1x_1 + x_2 \geq 1x1+x2≥1),
o y2y_2y2 for the second constraint (x1+x2≤7x_1 + x_2 \leq 7x1+x2≤7),
o y3y_3y3 for the third constraint (x1+2x2≤10x_1 + 2x_2 \leq 10x1+2x2≤10),
o y4y_4y4 for the fourth constraint (x2≤3x_2 \leq 3x2≤3).
Minimize:
W=1y1+7y2+10y3+3y4W = 1y_1 + 7y_2 + 10y_3 + 3y_4W=1y1+7y2+10y3+3y4
Subject to:
y1+y2+y3≥3(for x1 coefficient)y_1 + y_2 + y_3 \geq 3 \quad \text{(for } x_1 \
text{ coefficient)}y1+y2+y3≥3(for x1 coefficient) y1+y2+2y3+y4≥2(for x2 coefficient)y_1 +
y_2 + 2y_3 + y_4 \geq 2 \quad \text{(for } x_2 \text{ coefficient)}y1+y2+2y3+y4
≥2(for x2 coefficient)
Dual Variables:
y1≥0,y2≥0,y3≥0,y4≥0y_1 \geq 0, \quad y_2 \geq 0, \quad y_3 \geq 0, \quad y_4 \geq 0y1≥0,y2
≥0,y3≥0,y4≥0
Final Dual Formulation
Minimize:
W=y1+7y2+10y3+3y4W = y_1 + 7y_2 + 10y_3 + 3y_4W=y1+7y2+10y3+3y4
Subject to:
y1+y2+y3≥3y_1 + y_2 + y_3 \geq 3y1+y2+y3≥3 y1+y2+2y3+y4≥2y_1 + y_2 + 2y_3 + y_4 \geq
2y1+y2+2y3+y4≥2
With:
y1,y2,y3,y4≥0y_1, y_2, y_3, y_4 \geq 0y1,y2,y3,y4≥0
5. Steps for Converting LPP into Standard Form
Convert maximization to minimization (if needed).
Express all constraints as ≤\leq≤ or === inequalities.
Convert unrestricted variables into non-negative variables.
Introduce slack, surplus, and artificial variables as necessary.
Construct the initial simplex tableau.
6. Game Theory - Optimal Strategies
Solve the given payoff matrices using the minimax and maximin principles. Use linear
programming or dominance methods if applicable.
Payoff Matrix (a)
Player A Player B[172627516]\text{Player A \ Player B} \quad \begin{bmatrix} 1 & 7 & 2 \\ 6
& 2 & 7 \\ 5 & 1 & 6 \end{bmatrix}Player A Player B165721276
Step 1: Maximin for Player A
Maximin strategy for Player A involves selecting the strategy that maximizes the minimum
payoff (the worst-case scenario).
Row 1: Minimum value = min(1, 7, 2) = 1
Row 2: Minimum value = min(6, 2, 7) = 2
Row 3: Minimum value = min(5, 1, 6) = 1
Player A's maximin strategy is to choose Row 2, which gives the highest minimum payoff of 2.
Step 2: Minimax for Player B
Minimax strategy for Player B involves selecting the strategy that minimizes the maximum
payoff (the worst-case scenario).
Column 1: Maximum value = max(1, 6, 5) = 6
Column 2: Maximum value = max(7, 2, 1) = 7
Column 3: Maximum value = max(2, 7, 6) = 7
Player B's minimax strategy is to choose Column 1, which gives the lowest maximum payoff of
6.
Step 3: Checking for Saddle Point
A saddle point exists if the maximin strategy of Player A equals the minimax strategy of Player
B.
From the analysis:
Player A’s maximin strategy gives 2 (from Row 2).
Player B’s minimax strategy gives 6 (from Column 1).
Since these values are not equal, there is no pure strategy Nash equilibrium (no saddle point)
in matrix (a).
Payoff Matrix (b)
Player A Player B[2541]\text{Player A \ Player B} \quad \begin{bmatrix} 2 & 5 \\ 4 & 1 \
end{bmatrix}Player A Player B[2451]
Step 1: Maximin for Player A
Row 1: Minimum value = min(2, 5) = 2
Row 2: Minimum value = min(4, 1) = 1
Player A's maximin strategy is to choose Row 1, which gives the highest minimum payoff of 2.
Step 2: Minimax for Player B
Column 1: Maximum value = max(2, 4) = 4
Column 2: Maximum value = max(5, 1) = 5
Player B's minimax strategy is to choose Column 1, which gives the lowest maximum payoff of
4.
Step 3: Checking for Saddle Point
A saddle point exists if the maximin strategy of Player A equals the minimax strategy of Player
B.
From the analysis:
Player A’s maximin strategy gives 2 (from Row 1).
Player B’s minimax strategy gives 4 (from Column 1).
Since these values are not equal, there is no pure strategy Nash equilibrium (no saddle point)
in matrix (b) either.
