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

Calculate your order
Pages (275 words)
Standard price: $0.00
Client Reviews
4.9
Sitejabber
4.6
Trustpilot
4.8
Our Guarantees
100% Confidentiality
Information about customers is confidential and never disclosed to third parties.
Original Writing
We complete all papers from scratch. You can get a plagiarism report.
Timely Delivery
No missed deadlines – 97% of assignments are completed in time.
Money Back
If you're confident that a writer didn't follow your order details, ask for a refund.

Calculate the price of your order

You will get a personal manager and a discount.
We'll send you the first draft for approval by at
Total price:
$0.00
Power up Your Academic Success with the
Team of Professionals. We’ve Got Your Back.
Power up Your Study Success with Experts We’ve Got Your Back.
WeCreativez WhatsApp Support
Our customer support team is here to answer your questions. Ask us anything!
👋 Hi, how can I help?