Assignment -
This Assignment is composed of four questions.
Question 1 - Answer whether each one of following statements is true or false. If you believe a statement is false, give an example, picture or justification illustrating why it is false. If you believe a statement is true, there is no need to give a justification.
a) Any optimal solution of an LP has to be a basic feasible solution (BFS).
b) For an LP to be unbounded, it's feasible region must be unbounded.
c) Every LP with an unbounded feasible region has an unbounded objective value.
d) When an LP has more than one optimal solution, then it will always have infinitely many optimal solutions.
e) The simplex method always moves from one BFS to another.
f) Every iteration of the simplex method always (strictly) improves the value of the LP objective function.
g) Suppose we introduce an artificial variable a1 in the big M method for a maximization LP, the penalty term added to the objective function should be Ma1.
|
Table 1: Information about the fragrance oil
|
|
fragrance oil
|
price (dollar per ounce)
|
sophistication number
|
flower content
|
|
1
|
8
|
60
|
6
|
|
2
|
12
|
90
|
3
|
|
3
|
10
|
80
|
5
|
|
4
|
15
|
90
|
1
|
Question 2 - GladaCo manufactures two types (j = 1, 2) of scented candles: Regular (j = 1) and Luxury (j = 2). Each type of candle is produced by blending four different types (i = 1, . . . , 4) of fragrance oils. The sales price per ounce of Regular candle is 10 dollars and that of Luxury candle is 60 dollars.
The two types of candle differ in two attributes: sophistication number and flower content. Regular candle must have a sophistication number of at least 60 and a flower content of at most 15%. Luxury candle must have a sophistication number of at least 85 and a flower content of at most 5%. The purchase price per ounce of fragrance oil i, the sophistication number, and flower content of fragrance oil i are listed in the Table 1. The daily demand for Regular candle is 1500 ounces and the daily demand for Luxury candle is 500 ounces.
Assume that
1) the number of ounces of candles is equal to the total number of ounces of fragrance oil used for blending;
2) sophistication number and flower content blend linearly;
3) every candle produced that is not used to meet demand is discarded (and hence, cannot be used to meet next day's demand).
Answer the following questions.
a) Assuming that daily demand for each type of candle must be met, formulate an LP that will enable GladaCo to maximize daily profits;
b) Assume now GaldaCo has the option of loosing customer satisfaction by not satisfying the whole demand and that backlog is not carried over to the future. In such a case, GladaCo looses 5 and 30 dollars, respectively, for each ounce of unsatisfied demand for Regular (j = 1) and Luxury candle (j = 2). Formulate an LP that will enable GladaCo to maximize daily profits.
Question 3 - Suppose that the following canonical tableau is associated with a minimization problem
|
BV
|
z
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
rhs
|
|
z
|
1
|
0
|
0
|
0
|
c1
|
c2
|
c3
|
c4
|
10
|
|
x1
|
0
|
1
|
0
|
0
|
0
|
-8
|
2
|
0
|
b
|
|
x2
|
0
|
0
|
1
|
0
|
-5
|
a2
|
-1
|
-4
|
1
|
|
x3
|
0
|
0
|
0
|
1
|
a1
|
6
|
a3
|
-1
|
9
|
The entries a1, a2, b, c1, c2, c3 and c4 in the above tableau are unknown constants. The questions below are independent and they all refer to the above tableau. State the most general conditions on the parameters a1, a2, b, c1, c2, c3 and c4 that make the statements of each question below true. If you do not state any condition with respect to a specific parameter, I will assume that the parameter can take on any value from -∞ to ∞.
(a) The current basic solution is optimal and nondegenerate. (Observation: A basic solution is called nondegenerate if the value of all its basic variables is nonzero.)
(b) The current basic solution is feasible but the LP is unbounded.
(c) The current basic solution is feasible, x5 is a candidate to enter the basis; and when x5 enters, x3 is the unique candidate to leave the basis and we get a new BFS solution with objective function equal to 5.
d) The current basic solution is feasible, x6 is a candidate to enter the basis. Moreover, when x6 enters the basis, x3 leaves the basis, and the value of x6 at the new BFS is equal to 3.
Question 4 - Consider the following LP problem in minimization form:
minimize w = 6y1 + 4y2 + 3y3 + 6y4
subject to 3y1 + 2y2 + y3 + 2y4 ≥ 4
y1 + y2 + y3 - y4 ≥ 1
y1 ≤ 0, y2 ≤ 0, y3 urs, y4 ≥ 0.
(a) Find the dual of this problem;
(b) Graphically solve the dual problem.
Textbook - Operations Research APPLICATIONS AND ALGORITHMS, FOURTH EDITION by Wayne L. Winston.