运筹学代写-G205
时间:2022-04-04
IEM G205
DETERMINISTIC OPERATIONS RESEARCH
Midterm Exam 2 – Practice with Solutions
Instructor: Dr. Ondemir Student: __________________
Justify briefly your answer, where appropriate, and show all work!
Problem 1 (50 points)
The following linear program P with two resources and three activities represents the
production model of a company.
Maximize Z = 3x1 + x2 + 2x3
subject to
x1 - x2 + 2x3 ≤ 20 (1)
2x1 + x2 - x3 ≤ 10 (2)
and
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
Let x4 and x5 denote the slack variables for the respective functional constraints. After we
apply the simplex method, the final simplex tableau is
Coefficient of:
Basic
Variable Eq. Z x1 x2 x3 x4 x5
Right
Side
Z (0) 1 8 0 0 3 4 100
x3 (1) 0 3 0 1 1 1 30
x2 (2) 0 5 1 0 1 2 40
Answer the following independent questions:
(a) Write the optimal solution of P, i.e. values of all variables (original and slack) and z-
value and the optimal solution of its dual (dual variables, surplus and dual objective
value).
From the column of BV and the RHS column : x1=0, x2=40, x3=30, x4=0, x5=0, Z=100;
From the (0) row: y1=3, y2=4, y3=8, y4=0, y5=0, dual obj value=100
(b) Write the defining equations of the optimal corner point.
x1 = 0, x1 - x2 + 2x3 = 20, 2x1 + x2 - x3 = 10
(c) Are all resources used at the optimal solution? If not, determine the unused amounts
of the resources.
All resources are used because both slacks have zero values.
(d) If the price of resource #2 is 3.5 per unit should the company buy additional units of
that resource, if available, in order to increase profit?
Price(3.5)(e) Use algebraic analysis to find the allowable ranges for resources #1 and #2 (b1 and b2)
so that the current basis remains optimal. Use the ranges obtained and the
information in the final simplex tableau to answer the following questions:
⎥⎥



⎢⎢



Δ+
Δ+=
⎥⎥



⎢⎢



Δ
⎥⎥



⎢⎢



+
⎥⎥



⎢⎢



140
130
0
1
21
11
40
30
b
bb ; 30+ 1bΔ >0; 40+ 1bΔ >0 ⇒ 1bΔ >-30 ⇒ b1>-10.

⎥⎥



⎢⎢



Δ+
Δ+=
⎥⎥



⎢⎢



Δ⎥
⎥⎥


⎢⎢



+
⎥⎥



⎢⎢



2240
230
2
0
21
11
40
30
b
b
b
; 30+ 2bΔ >0; 40+2 2bΔ >0 ⇒ 2bΔ >-20 ⇒ b2>-10.

Another way is to assume simultaneous changes (more general case) and impose
feasibility:
⎥⎥



⎢⎢




⎥⎥



⎢⎢



Δ+Δ+
Δ+Δ+=
⎥⎥



⎢⎢



Δ
Δ
⎥⎥



⎢⎢



+
⎥⎥



⎢⎢



0
0
22140
2130
2
1
21
11
40
30
bb
bb
b
b . Although independent ranges (above)
have been used to answer the following two questions, the last two inequalities can
also be used.

(i) If the company had 60 units of resource #1 (instead of 20) what the optimal
profit would have been?
An increase of b1 by 40 is within range (upper range=∞), therefore shadow price of
resource #1(3) is unchanged and the optimal profit will be 100+(3)*(40)= 220.
(ii) If the company had only 5 units of resource #1 and 5 units of resource #2
available (i.e. 15 and 5 units fewer, respectively), would the current basis remain
optimal?
We have simultaneous decreases of the RHS, so let’s use the 100% rule. 100(15/30
+ 5/20)=75% < 100, therefore the current basis remains optimal.
(f) Perform sensitivity analysis with reoptimization, if necessary, to find the new optimal
solution if the coefficients of activity #1 have been changed to
+
⎥⎥



⎢⎢




⎥⎥



⎢⎢




=
⎥⎥



⎢⎢



Δ
Δ
Δ

⎥⎥



⎢⎢



=
⎥⎥



⎢⎢



5
3
8
2
0
1
0
1
4
21
11
1
21
11
1
a
a
c
a
a
c
⎥⎥



⎢⎢


⎡−
=
⎥⎥



⎢⎢




⎥⎥



⎢⎢



−⎥
⎥⎥


⎢⎢



1
1
11
2
0
21
11
43


Revised tableau:
Coefficient of:
Basic
Variable

Eq.

Z

x1

x2

x3

x4

x5
Right
Side
Z (0) 1 -1 0 0 3 4 100
x3 (1) 0 1 0 1 1 1 30
x2 (2) 0 1 1 0 1 2 40

x1 enters the basis and x3 leaves the basis.

Coefficient of:
Basic
Variable

Eq.

Z

x1

x2

x3

x4

x5
Right
Side
Z (0) 1 0 0 1 4 5 130
x1 (1) 0 1 0 1 1 1 30
x2 (2) 0 0 1 -1 0 1 10

The new optimal solution is
x1=30, x2=10, x3=0, x4=0, x5=0, Z=130;



Problem 2 (15 points)

For the following linear programming problem, construct its dual.

Minimize Z = 3 x1 + 2 x2
subject to
2 x1 + x2 ≥ 10
-3 x1 + 2 x2 ≤ 6
x1 + x2 = 6
and
x1 ≥ 0, x2 unconstrained in sign


The dual is
Maximize 10y1 + 6y2 + 6y3,
subject to
2y1 - 3y2 + y3 ≤ 3
y1 +2y2 + y3 = 2
and
y1 ≥ 0, y2 ≤ 0, y3 unconstrained in sign













Problem 3 (35 points)

Consider the following linear program P:

Maximize Z = 3x1 + 4x2 + 8x3
subject to
2x1 + 3x2 + 5x3 ≤ 9
x1 + 2x2 + 3x3 ≤ 5
and
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

Let x4 and x5 denote the slack variables of the respective functional constraints.
The Dual of P is D as follows:
Minimize y0 = 9 y1 + 5 y2
subject to
2 y1 + y2 ≥ 3
3 y1 + 2 y2 ≥ 4
5 y1 + 3 y2 ≥ 8
and
y1 ≥ 0, y2 ≥ 0

(a) Using D show that Z*< 18.
It suffices to find a feasible dual solution whose y0 value is 18. Such a feasible solution is
y1=2 and y2=0. The solution satisfies all constraints.
(b) The graphically obtained optimal solution of D is y1*=1 and y2*=1. Without
solving Problem P by simplex, answer the following questions:

(i) Using the optimal solution of D find the value of Z*.
At the optimal solution the two objective values are equal:
Z*= y0* = 9 (1) + 5 (1)=14.

(ii) Using the optimal solution of D and a formula from Fundamental
Insight determine the reduced costs of the decision variables of P.
-c + y*A = -[3 4 8] + [1 1] ⎥⎦
⎤⎢⎣

321
532
=[0 1 0] are the reduced costs of variables x1, x2, and
x3, respectively.

(iii) Use complementary slackness to find the optimal solution of P.

Given two complementary basic solutions (optimal ones in this case) in each pair of
associated variables one is basic and the other is nonbasic. The values of y3, y4, and y5
were found in the previous question (reduced costs) or equivalently can be found from
the dual constraints after they are converted to equations and the values of y1 and y2 are
plugged in.


( y1 = 1, y2 = 1 || y3 = 0, y4 = 1, y5 = 0 ) ⇒ x4 = 0, x5 = 0, x2 = 0
( x4 = 0, x5 = 0 || x1 = ?, x2 = 0, x3 = ? )
The values of the remaining variables are found by solving a system of linear equations
from P after the values of nonbasic variables are set to zero.
2x1 + 5x3 = 9
x1 + 3x3 = 5
whose solution is x1 = 2 and x3 = 1.

x1 = 2 x2 = 0 x3 = 1 x4 = 0 x5 = 0

(iv) Using the optimal solution of P, construct the optimal basis (matrix) B.

The columns of the basic variables are

B = ⎥⎦
⎤⎢⎣

31
52

essay、essay代写