Remark.  Problems  1-10  are  regular  problems  with  total  100pts  and  Problem  11  &  12  are  the  “bonus” problems.  The points gained from the bonus problems can be added to the total points.  The maximum points will not exceed 100pts.

Regular Problems

Problem  1  (10  pts)    An  alloy  factory  produces  two  kinds of products  (A  and  B).  Each  Product  A requires 2kg of iron, 5kg of aluminum, and $100 worth of labor; each Product B requires 0.5kg of iron, 6kg of aluminum, and $150 worth of labor.  There are 150kg of iron and 300kg of aluminum available at the factory every day. Each Product A and B can sell for $500 and $800, respectively.

(a).  Formulate a linear optimization that maximizes the expected daily profit of selling all the products.

(b). Write the standard form of the LP you formulated in part (a).

(c).  Consider the following modification to the original problem:  Suppose that up to 50kg of iron can be purchased from other places everyday at a cost of $2 per kg.  Can it be easily incorporated into the linear optimization formulation and how?

Problem 2 (10 pts)   Reformulate the problem:

min        2x2 + |x1  − x3 |

s.t.    −|x1 + 2| + |x2 | ≤ 5,

x3(2)  ≤ 1,

as a linear optimization problem. Also, write down its standard form.

Problem 3  (10pts)    Consider a city with I producers, J storehouses, and P types of products that can be stored in storehouses. Each storehouse j ∈ {1, ..., J} has a capacity of Cjp  for product p ∈ {1, ..., P}.  For each producer i∈ {1, ..., I}, the number of unstored product p is Sip.  Finally, the distance of storehouse j from producer i is dij . Formulate a linear optimization problem whose objective is to assign all products to the storehouses, while minimizing the total distance in transportation.

Problem 4 (10pts)    Company A is considering a new work schedule. Every employee will work four days continuously and then get a three-day break.  The company should choose a starting day for every employee so that they can keep running on this seven-day schedule.  The minimum numbers of employees to make Company A run are listed in Table 1.

Write down a linear optimization to find out the best schedule for the company (i.e.  how many employees start working on a certain day), and minimize the total number of employees.

Table 1: Minimum number of employees for each day

Problem  5  (10pts)    Consider  an  LP in its standard form and the corresponding constraint set  P  = {x ∈ Rn |Ax = b, x ≥ 0}.  Suppose that the matrix A has dimensions m × n and that its rows are linearly independent and b ∈ Rm .  For each of the following statements, state whether it is true or false.  Please explain your answers (if not true, please show a counterexample).

(a).  The set of all optimal solutions (assuming existence) must be bounded;

(b).  At every optimal solution, no more than m variables can be positive;

(c). If there is more than one optimal solution, then there are uncountably many optimal solutions.

Problem  6  (10pts)    Solve the following 2-dimensional linear optimization problem using the graphical method as in the lecture.

max         x1 + x2

s.t.     −x1 + x2  ≤ 2,

x1 + 2x2  ≤ 6,

0 ≤ x1  ≤ 4,

0 ≤ x2  ≤ 3.

Which constraints are active at optimal solution? Also list all the corner points of the feasible region.

Problem 7 (10pts)    Consider the following LP:

max         2x1 + 3x2

s.t.   2x1 + 2x2  ≤ 12,

x1 + 2x2  ≤ 8,

4x1  ≤ 16,

4x2  ≤ 12,

x1 , x2  ≥ 0.

Use the Simplex method to solve it.  For each step, clearly mark what is the current basis, the current basic solution, and the corresponding objective value.  Please indicate the number of optimal solution(s) and find an optimal solution along with the optimal value of the objective function.

Problem 8 (10pts)    Consider the following LP:

min          5x1 − 6x2 − 7x3

s.t.     x1 + 5x2 − 3x3  ≥ 15,

5x1 − 6x2 + 10x3  ≤ 20,

x1 + x2 + x3  = 5,

x1 , x2 , x3  ≥ 0.

Use the Big-M method to solve the problem.

Problem 9  (10pts)   In a board game, there are three cards A, B and C. In each round, Card A takes 5 card quotas, and it generates 10 points and 5 Chakra; Card B takes 3 card quotas, and it generates -5 points and -1 Chakra.  Card C takes  1 card quota, and it generates  1 point and 10 Chakra.  Every player has 10 card quotas and 15 Chakra at each round, which will not remain at the end of every round.  Find the optimal combination of cards that one should hold in hand to get the highest points every round.

(a).  Formulate this problem as a linear programming problem (denote x1  as the number of Card A, x2  the number of Card B, and x3  the number of Card C).

(b).  Find the final tableau from Simplex method and give the optimal solution.

Problem 10 (10pts)   Three sellers offer three foods, which contain three different nutrients. We are given Table 2 with the nutritional content of a unit of each food, the minimum requirement of each nutrient, and the selling price for a unit of each food.

Table 2: Food

Design a diet so as to satisfy the minimum requirement of nutrients and minimize the total price to purchase the foods in the diet.

(a).  Formulate the diet problem as a linear programming model.

(b).  Solve the LP by Excel and obtain the sensitivity analysis report.

(c).  The seller of fried rice would like to increase his revenue by increasing the price of fried rice quoted to us.  Is it possible for him to do so?  If it is possible, how much more revenue can he obtain?  If not, what should the seller do to increase his revenue?

(d).  How about the seller of burger?  Can he increase his revenue by increasing the price of burger? Why ? If no, what should the seller do to increase his revenue?

(e).  Can we save any money if the minimum requirement of protein is decreased to 18?  If yes, what is the amount of the savings?

(f).  Does our optimal cost increase or decrease if the minimum requirement of fat is decreased to 5?

(g). If one hot dog provides 2 units of carbohydrates, 3 units of fat and 3 units of protein, and it is sold at a price of 3.2. Do we want to include it in the diet?

(h). If the amount of protein contained in burger is increased to 5.5, but its fat is decreased to 2.  Do we want to have it in the diet? What are the optimal value and optimal solutions.

Bonus Problems

•  Please study the “duality theory” reading material: Hillier, F.S. and G.J. Lieberman, Introduction to Operations Research, 9th edition, McGraw-Hill Science/Engineering/Math (Chapter 6).

Problem  11  (bonus,  10pts)    Consider Table 3 of food and its nutritional values.  The ideal nutrition intake for Alex is at least 20 grams of protein, at most 30 grams of carbohydrates, and at most 50 grams of fat per day. The problem is to find the least costly way to achieve those amounts of nutrition by using the three types of food shown in the table.

(a).  Formulate this problem as a linear programming problem.

(b).  Formulate the dual problem.

Table 3: Food

Problem 12 (bonus, 10pts)    Suppose M is a square matrix such that M = −MT , for example,

M =  1

(  −2

4  )

0   ) .