# Statistics Questionnaire

2Problem 1: LP Models [16 Points]

(a) [10 Points] The company OptimizaSUN makes two types of products: Sunscreen Lotion and Sunscreen 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:

Resources

Selling Price per bottle ($)

Product

Gross Chemical (g) Grease (g)

Sunscreen Lotion

30

40

15

Sunscreen Spray

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). 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.

(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:

Plant

1

2

3

4

Variable Cost ($)

Taurus Lincoln Escort

12000

16000

9000

15000

18000 11000

17000

19000 12000

19000

22000 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.

3

(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

Fixed Cost ($)

1

2

3

4

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 0

2

@

0

subject to

1

4

2

1

(7, 7, 7,1

7)x

0 1

5 3

3

A

@

2 1 x =

4A

3 4

1

x

0

0 1

0 1

4

4

B0 C

C is optimal. (You may find the vector y = @ 15 A useful in

Prove that the feasible solution x̄ = B

@1 A

1

2

your argument.)

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

(P ) max cT x

subject to Ax = b

x 0.

(Q) min bT y

subject to AT y

0.

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

Problem 4: Bases & Basic Solutions [16 Points]

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

max

s.t.

(3, 2, 1, 0, 1)x

✓

x

◆

✓ ◆

1 0 1 2 1

3

x=

2 1 1 1 0

1

(P)

0

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).

4

(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

✓

◆

✓ ◆

1 1 1 0

300

subject to

x =

1 1 0 1

200

x

0

(a) [12 Points] Solve (P) using the Simplex method, starting with B = {3, 4}. Choose the entering variable (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:

✓

◆ 1

✓

◆

1

a b

d

b

=

.

c d

c

a

ad bc

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

(b) [4 Points] If (P ) has an optimal solution, then write down an optimal basic feasible solution, and

write down a certificate of optimality (briefly explain the validity of your certificate).

Otherwise, if (P ) is unbounded, then write down a certificate of unboundedness (briefly explain the

validity of your certificate).

Problem 6: Theory [20 Points]

For each of the following statements, answer whether it is true or false. If true, give a complete explanation, 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.

(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, 8j = 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.

5

(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 2 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

(IP)

ce xe

e2E

s.t.

X

xe

e2 (U )

xe 2 {0, 1}

1

(U ✓ V, s 2 U, t 62 U )

(e 2 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 y T A

cT .

Then, every feasible solution of (P) has objective value y T b. (That is, y T b

feasible solution x⇤ of (P).)

cT x⇤ holds for every

1

Basic Solutions – 10=(3+3+4) marks

=

ko

KOIR

2

Consider the feasible data A, 6 below for an LP with constraints Ax b, x > 0.

(i) Ensure that the problem is in SEF with A full row rank and b > 0.

(Use GE if needed. You can use MATLAB or some other code or calculation tool. Details

of the calculations do not need to be included. But, please explain the process. Hint: You do

not need to lose the nice integer structure.)

(ii) What is the largest number of possible basic solutions that exist? State clearly why.

(Hint:

There is no need to do any intensive calculations to find this upper bound.)

.

(iii) Find two basic solutions with at least one being feasible, i.e., at least one should be a

BFS. Show the calculations that verify feasibility.

ㅋ 1212

-4 -4 1 1 0 0 2 0 -3 -4 -1

-1 0 0 0 -1 0 1 1

1 -1 0 0 0 0 1 2

-1 -1 1 1 0 0 -1 0 1 0

-2 -1 0 0 -1 0 -1 0 0 0 2

W =

No11

HOTT-

Nodon

-106

39

28

-14

-26

koy

2

Modelling with LP – 10=(6+4) marks

Professor Brett must estimate how much money to spend on food in order to get all the:

energy (2,000 kcal), protein (558), and calcium (800 mg) per day. (The rest of the nutrients

will be covered by pills.) There are six foods chosen along with the data (nutrient value per

serving) as given in the table.

Food

Serving size Energy Protein Calcium Price per serving

(kcal) (g) (mg) (cents)

110

4

2

9

205 32

12

68

160 13

54

36

160 8

285

20

420 4

22

50

260 14

80

50

Oatmeal

Chicken

Eggs

While milk

Cherry pie

Pork with beans

28 g

100 g

2 large

237 cc

170 g

260 g

Us

u

។

Taking taste into account, we add the maximum number of servings per day for each food

to be: u= (4, 3, 2, 8, 2, 2), respectively. .

(i) Model the problem of minimizing the cost of the diet as an LP disregarding any integer

constraints.

(i) Add a constraint that ensures that the amount spent on meat (chicken and pork together)

does not exceed the amount spent on the other foods.

a

–

3 Simplex Method – 15=(3+6+3+3) marks

Consider the LP problem max cł x s.t. Ax 0, with data:

ka

5

_9

-1 -1

2 -2

-2 -1 0

–(87)-(1-0

1

-2

2

=

US

7

-3

-2

1. Introduce slack variables X5, X6, X7 > 0 and transform the given problem to an LP

problem in standard equality form.

NUL

som

2. Using the simplex method solve the LP problem you obtained in the Item above. There

is an obvious feasible basis B (for which AB = I) to start the algorithm; use this basis.

=

3. Is the optimal solution that you have obtained in the Item above the unique optimal

solution to the problem? Prove your claim or provide a counterexample.

4. Suppose that you have a general LP in SEF with a nonunique optimal solution. Show

that there have to exist two distinct optimal basic feasible solutions, or provide an

example where this does not hold.

4 4 Feasibility and Bundedness – 10 marks

т

Let A E RMXn, b ERM, and ceR” be given. Consider the LP problem:

>

T

(P) maxc x s.t. : Ax 0.

Ko

ka

Prove the following statement:

“if (P) has a feasible solution ī and there exists d e R™ such that Ad < 0, d > 0 and

cd > 0, then (P) is unbounded”

Tu

04

on at pinas (cal Ansó, azo)

may , )

at D be it and LP.

(D)

D

min 1891 Ay zc, 920)

fessible sol for p

y feasible sol for D.

A in

Then ch=64

Here IP has feasible id non & 3

dER st Adso, do

ols

A Ad so

S. the Dual has

by Duality Theory

(P)

unbounded

no solution