University of Waterloo

CO250 — Introduction to Optimization

Midterm Exam

2014

Problem 1: LP Models [16 Points]

(a) [10 Points] The company OptimizaSUN makes two types of products: Sunscreen Lotion and Sun- screen Spray. Each bottle of Sunscreen Lotion is made from 30 grams (g) of Gross Chemical and 40g of Grease, while each bottle of Sunscreen Spray is made from 50g of Gross Chemical and 10g of Grease. Sunscreen Lotion sells for $15 a bottle, while Sunscreen Spray is priced at $20 per bottle. These data are summarized in the following table:

Product Resources Selling Price per bottle ($)

Gross Chemical (g) Grease (g)

Sunscreen Lotion

Sunscreen Spray 30 40 15

50 10 20

OptimizaSUN has a daily supply of 1000g of Gross Chemical (already paid for). It can purchase as much Grease as it wants at $0.01 per gram from a nearby restaurant.

Given the data above, give a linear program formulation that finds the daily production plan that maximizes OptimizaSUN’s profit (i.e. total value of bottles produced minus production costs). De- fine your decision variables clearly, and briefly describe your objective function and each of your constraints. Solutions without adequate explanations will not receive full credit.

(Note: Ignore any perceived integrality requirements.)

(b) [6 Points] Suppose, in addition to the data in (a), OptimizaSUN now wants to make sure that the number of bottles of Sunscreen Lotion and Sunscreen Spray produced per day are within 10 of each other. Also, it can now sell unused Gross Chemical for $0.05 per gram.

Modify your linear program in (a) to find the most profitable daily production plan for OptimizaSUN that takes these new conditions into account. Briefly explain each of your modifications. Solutions without adequate explanations will not receive full credit.

Problem 2: IP Models [18 Points]

Ford has four automobile plants. Each is capable of producing the Taurus, Lincoln, or Escort, but it can only produce one of these cars. The variable cost of producing a car of each type at each plant is given in the following table:

Variable Cost ($) Plant Taurus Lincoln Escort

1

2

3

4 12000

15000

17000

19000 16000

18000

19000

22000 9000

11000

12000

14000

Ford faces the following restrictions:

(i) Each plant can produce only one type of car.

(ii) The total production of each type of car must be at a single plant; that is, for example, if any Tauruses are made at plant 1, then all Tauruses must be made there. Each year, Ford must produce 500000 of each type of car.

(a) [11 Points] Formulate an integer program whose solution will tell Ford how to minimize the annual (variable) cost of producing cars. Define your decision variables clearly, and briefly describe your objective function and each of your constraints. Solutions without adequate explanations will not receive full credit.

(b) [7 Points] Ford faces the following requirements in addition to (i) and (ii) above.

(iii) If plant 2 is used, then Tauruses need to be manufactured at this plant. (iv) If both plants 3 and 4 are used, then plant 1 must also be used.

Also, in addition to the variable cost incurred by the production of a car, Ford also incurs a one-time, fixed opening cost for producing cars at each plant. These fixed costs are given in the following table.

Plant 1 2 3 4

Fixed Cost ($) 7 billion 6 billion 4 billion 2 billion

Here is an example for the sake of illustration. Suppose that Plant 1 is used to produce Escorts, Plant 2 is used to produce Tauruses, and Plant 3 is used to produce Lincolns. This production plan would incur a fixed cost of (7 × 109 + 6 × 109 + 4 × 109 ) = 17 × 109 , plus a variable cost of (9 × 103 × 5 × 105) + (15 × 103 × 5 × 105) + (19 × 103 × 5 × 105) = 21.5 × 109, resulting in a total cost of $ 38.5 billion.

How would your IP from (a) change in order to incorporate the new requirements (iii) and (iv), and in order to minimize the sum of fixed and variable costs? Briefly explain each of your modifications. Solutions without adequate explanations will not receive full credit.

Problem 3: Certificates [14 Points]

(a) [8 Points] Consider the following LP.

(P ) max (7, 7, 7, 7)x

??2 4 5 3?

?3?

subject to

? 0 2 2 1? x =

?1 ?1 ?3 4

?4?

1

?4?

x ? 0

? 4?

Prove that the feasible solution x¯ = ?0? is optimal. (You may find the vector y =

1

?

? 15 ?

useful in

? ? 1

2

your argument.)

(b) [6 Points] Let A be an m×n matrix, b ? Rm and c ? Rn . Consider the following two linear programs:

(P ) max cT x

subject to Ax = b

(Q) min bT y

x ? 0.

Suppose (Q) is unbounded. Prove that (P) is infeasible.

subject to AT y ? 0.

Problem 4: Bases & Basic Solutions [16 Points]

(a) [9 Points] Consider the following linear program:

For each of the following vectors, indicate if it is a basic solution for (P) or not. Give justification. If it is a basic solution for a basis B, state such a basis B. Indicate if it is a basic feasible solution.

(i) (1, ?1, ?1, 1, 1).

(ii) (0, 0, 0, 1, 1).

(iii) (0, ?2, 3, 0, 0).

(b) [7 Points] Suppose that in an LP problem we replace the unrestricted (free) variable x1 by u1 ? v1, where u1 and v1 are nonnegative variables, to create a new LP problem in SEF. Prove that if the point (u1 , v1, x2, x3, . . . , xn ) is a basic feasible solution of the new LP problem, then we cannot have both u1 > 0 and v1 > 0.

Problem 5: Solving Linear Programs [16 Points]

Consider the following linear programming problem (P ) in SEF. Note that (P) is in canonical form for the feasible basis B = {3, 4}.

max 5, 8, 0, 0 x

subject to

1 1 1 0

?1 1 0 1

300

x = 200

x ? 0

(a) [12 Points] Solve (P) using the Simplex method, starting with B = {3, 4}. Choose the entering vari- able (respectively, leaving variable) using the smallest subscript rule, that is, pick the variable with the smallest index if there is a choice. Stop after 3 iterations, even if your solution is incomplete. You may use the following formula for the inverse of a 2 × 2 matrix:

a b

?1

1 d ?b

=

c d ad ? bc

.

?c

Show all of your work. (You may use either canonical form LPs (Chapter 2.5), or tableaus (Chap- ter 2.7).)

Problem 6: Theory [20 Points]

For each of the following statements, answer whether it is true or false. If true, give a complete explana- tion, and if false, give one counter-example or a complete explanation. If you use results from the course, then you should include a proof for full credit.

Marking scheme: Each part 5 marks. For each part:

zero for wrong T/F answer (no matter what is written in the explanation).

2 marks for correct T/F answer, and 1-3 marks for explanation and/or counter-example (in general, an explanation that is incorrect in details and shows lack of understanding of the theory should get zero marks).

(a) [5 Points] Let (P ) be a linear program that has an optimal solution. Then the feasible region of (P ) is bounded.

(Note: the feasible region of an LP is said to be bounded if there exists a (large) positive number M

such that for every feasible solution x¯ = (x¯1, . . . , x¯n )T we have |x¯j | ? M, ?j = 1, . . . , n.)

(b) [5 Points] Let (P) be the following LP (linear program):

max{cT x subject to Ax = 0, x ? 0}

Note that (P) is in SEF, and the right-hand-side vector is the zero vector.

Suppose that (P) has a feasible solution x? such that cT x? > 0 (thus, x? is a feasible solution of positive value). Then (P) is unbounded.

(c) [5 Points] The following integer program (IP) correctly formulates the minimum st-cut problem; in this problem, we have a graph G = (V, E) with nonnegative edge costs ce for each edge e ? E, and there are two designated vertices s and t; the problem is to find an st-cut such that the sum of the cost of the edges in the cut is minimum.

min X ce xe (IP)

e?E

s.t. X

e??(U )

xe ? 1 (U ? V, s ? U, t 6? U )

xe ? {0, 1} (e ? E)

(d) [5 Points] Let (P) be the following LP (linear program):

max{cT x subject to Ax = b}

(Note that x is free, i.e., the entries of x could be negative, zero, or positive.) Suppose that y is a vector (of appropriate dimension) such that yT A ? cT .

Then, every feasible solution of (P) has objective value ? yT b. (That is, yT b ? cT x? holds for every feasible solution x? of (P).