University of WaterlooCO250 â Introduction to OptimizationMidterm Exam2014Problem 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 LotionSunscreen Spray 30 40 1550 10 20OptimizaSUN 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 Escort1234 12000150001700019000 16000180001900022000 9000110001200014000Ford 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 4Fixed Cost ($) 7 billion 6 billion 4 billion 2 billionHere 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 ? ? 12your 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 xsubject 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 xsubject to1 1 1 0?1 1 0 1300 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?11 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 Msuch 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. Xe??(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).

The price is based on these factors:

Academic level

Number of pages

Urgency

Basic features

- Free title page and bibliography
- Unlimited revisions
- Plagiarism-free guarantee
- Money-back guarantee
- 24/7 support

On-demand options

- Writer’s samples
- Part-by-part delivery
- Overnight delivery
- Copies of used sources
- Expert Proofreading

Paper format

- 275 words per page
- 12 pt Arial/Times New Roman
- Double line spacing
- Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Delivering a high-quality product at a reasonable price is not enough anymore.

That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read moreEach paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read moreThanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read moreYour email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read moreBy sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more