Assignment - 1

Question 1 - At the beginning of the fall semester, the director of the computer facility of a certain university is confronted with the problem of assigning different working hours to her operators. Because all the operators are currently enrolled in the university, they are available to work only a limited number of hours each day.

There are six operators (four men and two women). They all have different wage rates because of differences in their experience with computers and in their programming ability. The following table shows their wage rates, along with the maximum number of hours that each can work each day.

Each operator is guaranteed a certain minimum number of hours per week that will maintain an adequate knowledge of the operation. This level is set arbitrarily at 8 hours per week for the male operators and 7 hours per week for the female operators (K.S. and N.K.)

The computer facility is to be open from 8 A.M. to 10 P.M. Monday through Friday with exactly one operator on duty during these hours. On Saturdays and Sundays, the computer is to be operated by other staff.

Because of a tight budget, the director has to minimize cost. She wishes to determine the number of hours she should assign to each operator on each day. Formulate a linear programming model for this problem (DO NOT SOLVE IT).

Question 2 - Suppose that the following canonical tableau is associated with a maximization problem

The entries c₁, c₂, c₃, a₁, a₂ and β in the above tableau are parameters. The question below are independent and they all refer to the above tableau. State the most general conditions on the parameters c₁, c₂, c₃, a₁, a₂ and β 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 degenerate. (Observation: A basic solution is called degenerate if the value of one of its basic variables is equal to zero.)

(b) The current basic solution is feasible but the LP is unbounded.

(c) The current basic solution is feasible, x₆ is a candidate to enter the basis and x₃ leaves the basis when x₆ enters the basis.

(d) The current basic solution is feasible, x₇ is a candidate to enter the basis, but when x₇ enters the basis, both the solution and the objective value remain unchanged.

(e) The current basic solution is feasible, x₇ is a candidate to enter the basis, and when x₇ enters the basis, x₁ remains basic and the value of x₁ at the new BFS (after the pivot) is equal to 7. What will be the values of x₃ and x₇ in the new BFS?

Question 3 - Consider the following LP problem:

maximize 2x₁ + 2x₂

s.t. x₁ + x₂ ≤ 2,

4x₁ + x₂ ≥ 4,

x₁ ≥ 0, x₂ ≥ 0.

(a) Use graphical method to find all extreme points and all optimal solutions of LP (??).

(b) Convert LP (??) into an equivalent one in standard form. Find all basic feasible solutions (BFS) of the standard form LP. (Remark: You do not have to solve the standard form LP.) Describe the correspondence between these BFS's and the extreme points obtained in part (a).

Assignment - 2

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 a₁ in the big M method for a maximization LP, the penalty term added to the objective function should be Ma₁.

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

The entries a₁, a₂, b, c₁, c₂, c₃ and c₄ 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 a₁, a₂, b, c₁, c₂, c₃ and c₄ 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, x₅ is a candidate to enter the basis; and when x₅ enters, x₃ 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, x₆ is a candidate to enter the basis. Moreover, when x₆ enters the basis, x₃ leaves the basis, and the value of x₆ at the new BFS is equal to 3.

Question 4 - Consider the following LP problem in minimization form:

minimize w = 6y₁ + 4y₂ + 3y₃ + 6y₄

subject to 3y₁ + 2y₂ + y₃ + 2y₄ ≥ 4

y₁ + y₂ + y₃ - y₄ ≥ 1

y₁ ≤ 0, y₂ ≤ 0, y₃ urs, y₄ ≥ 0.

(a) Find the dual of this problem;

(b) Graphically solve the dual problem.