Questions pratiques-3/Practice Questions-3

v.1.0

5-20 Solution
min 𝑤6 + 𝑤7
s. t. 𝑤1 + 𝑤2 + 𝑤4 = 18
2𝑤1 − 𝑤3 + 𝑤6 = 2
3𝑤2 + 5𝑤3 − 𝑤5 + 𝑤7 = 15
𝑤1 , … , 𝑤7 ≥ 0

Variables de base / Basic variables = 𝑤4 , 𝑤6 , 𝑤7 .

Setup the model for Phase I. Apply Simplex Algorithm to this Phase I to show that the model is
infeasible.

5-22 Solution

max −𝑦5
s. t. −2𝑦1 + 𝑦2 − 𝑦3 + 𝑦5 = 2
𝑦2 + 𝑦4 = 1
𝑦1 , … , 𝑦5 ≥ 0

1
Initial table
BV y1 y2 y3 y4 y5 RHS
y5 -2 1 -1 0 1 2
y4 0 1 0 1 0 1
w 0 0 0 0 1 0
We need to transform the last row (corresponding to the objective function) to obtain the
following second table:
BV y1 y2 y3 y4 y5 RHS
y5 -2 1 -1 0 1 2
y4 0 1 0 1 0 1
w 2 -1 1 0 0 -2
The pivot is highlighted. Variable 𝑦2 enters the basis and 𝑦4 leaves.
BV y1 y2 y3 y4 y5 RHS
y5 -2 0 -1 -1 1 1
y2 0 1 0 1 0 1
w 2 0 1 1 0 -1
This table is optimal with a solution 𝑦1 , 𝑦3 , 𝑦4 = 0 and 𝑦2 = 𝑦5 = 1. The objective function
value is 𝑤 = −1. Therefore, we could not increase the value of 𝑤 to 0, meaning that the
corresponding solution is not feasible for the original model, and the original model is infeasible.

2
5.28 Solution

(a)

(b)
max 𝑥1 + 𝑥2
s. t. 𝑥1 + 𝑥2 + 𝑥3 = 9
−2𝑥1 + 𝑥2 + 𝑥4 = 0
𝑥1 − 2𝑥2 + 𝑥5 = 0
𝑥1 , … , 𝑥5 ≥ 0

(c)

BV x1 x2 x3 x4 x5 RHS
x3 1 1 1 0 0 9
x4 -2 1 0 1 0 0
x5 1 -2 0 0 1 0
z -1 -1 0 0 0 0
Pivot is highlighted in yellow. Variable x1 enters and x5 leaves.

BV x1 x2 x3 x4 x5 RHS
x3 0 3 1 0 -1 9
x4 0 -3 0 1 2 0
x1 1 -2 0 0 1 0
z 0 -3 0 0 1 0
The first iteration did not help us improve the objective function. Its value is still zero. Next, we
enter x2 and x3 leaves.

3
 BV x1 x2 x3 x4 x5 RHS
x2 0 1 0.333 0 -0.333 3
x4 0 0 1 1 1 9
x1 1 0 0.667 0 0.333 6
z 0 0 1 0 0 9
This tableau is optimal and gives an objective function value of 9 when x1=6 and x2=3, x3=0,
x4=9 and x5=0.

Note that x5 is a nonbasic variable and we can enter it to the basis, because its reduced cost is
zero (highlighted in gray). If the solution is degenerate, this operation will not change the
solution. If there is an alternative optimal solution, we will find it. When we do enter x5 to the
basis, we obtain the following table.

BV x1 x2 x3 x4 x5 RHS
x2 0 1 0.667 0.333 0 6
x5 0 0 1 1 1 9
x1 1 0 0.333 -0.333 0 3
z 0 0 1 0 0 9
The objective function did not improve but we identified an alternative optimal solution at x1=3,
x2 = 6, x3 = 0, x4 = 0 and x5 = 9 with an objective function value of 9.

4
6.1. For each of the following constraint coefficient changes, determine whether the change
would tighten or relax the feasible set. Assume that the model is a linear program, and that all
variables are nonnegative and that the constraint is the only one.

Consider using LP2D and double check your responses.

Solution 6.1.
(a) tighten
(b) tighten
(c) relax
(d) tighten
(e) relax
(f) tighten
(g) tighten
(h) tighten

5
Question. Professor Proof is trying to arrange for the implementation in a computer program of
his latest operations research algorithm. He can contract with any mix of three sources for help:
unlimited hours from undergraduates at $4 per hour, up to 500 hours of graduate students at $10
per hour, or unlimited hours of professional programmers at $25 per hour. The full project would
take a professional at least 1000 hours, but grad students are only 0.3 as productive, and
undergraduates, 0.2. Proof has only 164 hours of his own time to devote to the effort, and he knows
from experience that undergraduate programmers require more supervision than graduates, and
graduates more than professionals. In particular, he estimates that he will have to invest 0.2 hour
of his own time per hour of undergraduate programming, 0.1 hour of his time per hour of graduate
programming, and 0.05 hour of his time per hour of professional programming. The corresponding
mathematical model is as follows:

Solve it in Excel, create the Sensitivity Report, and answer the following questions:

(a) What is the marginal cost per professional-equivalent hour of programming associated with the
optimal solution?
(b) How much would cost increase if 1050 professional-equivalent hours of programming are
required? How about 1100?
(c) Does Professor Proof’s availability limit the optimal solution? How much would cost change
if Professor Proof could devote only 150 hours to supervision? How about 100 hours?
(d) How much would the hourly rate of graduate student programmers have to be reduced before
Professor Proof might optimally hire some?
(e) How much would project cost increase if professional programmers cost $30 per hour? If they
cost $35?
(f) Suppose that Professor Proof decides to require at least 500 programmer hours to go to students.
Could this requirement change the optimal solution?
(g) Suppose that Professor Proof decides to allow unlimited hours of graduate student
programming. Could this revision change the optimal solution?
(h) One of Professor Proof’s colleagues has expressed interest in doing some of the programming
to earn outside income. At what price per hour should Proof be interested if he estimates that the
colleague would be 80% as efficient as a professional and require 0.10 hour of supervision per
hour of work?

6
Solution:

Report:
Variable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value Cost Coefficient Increase Decrease
$C$8 Hours (var) Undergrad 600 0 4 1 1E+30
$D$8 Hours (var) Grad 0 2.947368421 10 1E+30 2.947368421
$E$8 Hours (var) Professional 880 0 25 14 5

Constraints
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$F$10 Required Hours 1000 25.26315789 1000 2280 836
$F$11 Availability 164 -5.263157895 164 836 114
$F$12 Grad.Hr.Limit 0 0 500 1E+30 500

(a) 25.263 $
(b) 50 x 25.263 = 1263.16 $ and 100 x 25.263 = 2526.316 $ (both values are within the allowable
range).
(c) Yes. |-5.263| x (164-150) = 73.684 $ increase. In the second case, |-5.263| x (164-100) = -
336.842 $ increase (both values are within the allowable range).
(d) 2.947 $.
(e) The optimal solution wouldn’t change because 5$ increase is within the allowable range.
Therefore, the optimal obj.fn.value would increase by 5 x 880 = 4400 $ (when increased to 30 $)
and by 10 x 880 = 8800 $ (when increased to 35 $).
(f) No, because the current optimal solution already allocates more than 500 hours to the students.
(g) No, because no grad student hours are used in the optimal solution.
(h) We will answer this question in the 4th next week. Here is the answer:
Let 𝑐 be the hourly payment to Professor Proof’s colleague and consider the corresponding
variable. The reduced cost of this new variable will be equal to 𝑐 − 25.26315789 x 0.8 + -
5.263157895 x 0.1 + 0 x 0 = 𝑐 − 19.684. We then need 𝑐 − 19.684 ≤ 0 for this option to be
profitable. In other words, in order to assign a nonzero value to this variable, the objective function
coefficient of the new variable should not exceed 19.684 $ per hour.