optimization

Assignment 2 Problem 1. An auto company manufactures cars and trucks. Each vehicle must be processed in the paint shop and in the body assembly shop. If the paint shop were painting only trucks, then 40 trucks per day could be painted. If the paint shop were painting only cars, then 60 cars per day could be painted. If the body shop were only producing trucks, then it could process 50 per day. If the body shop were only producing cars, then it could process 50 per day. Each truck contributes $300 to profit, and each car contributes $200 to profit. (a) Formulate an LPP whose solution will determine a daily production schedule that maximizes the company profit. (b) Solve the LPP (find all optimal solutions of the LPP) obtained in (a) by using an appropriate part of the EPT (Extreme Point Theorem). Explain. (c) If in addition, the market demand requires at least 30 cars to be produced daily, what must be the daily production schedule to maximize the company profit (goal programming).

Problem 2. Given the 3-variable LPP:

max z = 5x1 + 3x2 − 3x3 s.t.

2x1 + 3x3 ≤ 6 x2 ≤ 5 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 .

(a) Show that the FR of the given LPP is bounded. (b) Sketch the FR of the LPP and determine all extreme (corner) points of the FR. (c) Find an optimal solution of the LPP by using the EPT. Point out which part of the EPT you have applied. (d) How many optimal solutions does the given LPP have? Explain.

Problem 3. Solve the LPP:

max z = 3x1 + 2x2 s.t.

3x1 + x2 ≤ 12 x1 + 3x2 ≤ 12 2x2 ≤ 7 x1 ≥ 0, x2 urs .

Hint: In the given LPP, x2 urs means that x2 is unrestricted by sign, i.e., x2 can take positive and negative values; no sign restriction on x2.

1

Problem 4. Which of the Cases 1-4 (Unique Solution; Alternative Solutions; Infea- sible LPP, Unbounded LPP) apply to each of the following LPP:

(a) max z = x1 + x2 (b) max z = 4x1 + x2 s.t. s.t.

x1 + x2 ≤ 4 8x1 + 2x2 ≤ 16 x1 − x2 ≥ 5 5x1 + 2x2 ≤ 12 x1 ≥ 0, x2 ≥ 0 x1 ≥ 0, x2 ≥ 0

(c) max z = −x1 + 3x2 (d) max z = 3x1 + x2 s.t. s.t.

x1 − x2 ≤ 4 2x1 + x2 ≤ 6 x1 + 2x2 ≥ 4 x1 + 3x2 ≤ 9 x1 ≥ 0, x2 ≥ 0 x1 ≥ 0, x2 ≥ 0

Problem 5. Consider the following optimization problem:

max z = 40x1 + 10x2 s.t. x1 + 2x2 ≤ 5 |x1 − x2| ≤ 2 x1 ≥ 0, x2 ≥ 0,.

(a) By restating the absolute value constraint as a combination of two linear con- straints, show that the given optimization problem is in fact a Linear Programming Problem. (b) Solve graphically the given LPP either by using iso-cost lines or by using the EPT (Extreme Point Theorem), Part 1, if applicable.

2