Problem 1:    (18 points)

1.  Given A e Rm ×n  and b e Rm , show that the following mathematical program

min    |Ax · b|1                                                              (1)

北eRn

can be cast as a linear program, where |y|1  := |y1 | + . . . + |ym |. Write it in standard form.

2.  Consider the following linear program

max            3x1 + x2

北1 ,北2 ,北3 ,北4 ≥0

(  5x1      +     x2                              +    x4      =    15

Is x = (2.75, 1.25, 10.75, 0)T a solution? What about x = (0, 4, 8, 11)T ?

Problem 2:    (18 points)   Consider the following linear program:

min            x1 · x2 + x3

北1 ,北2 ,北3 eR

subject to    ．   x1      +    x2       ·   x3      车   10

1. Write the linear program in standard form.

2. Write the linear program corresponding to the first phase simplex.

3.  Apply one iteration of the first phase simplex algorithm in tableau form.

Problem 3:    (16 points)    The company Arcelor manufactures two types of steel at three different steel mills.  During a given month, each steel mill

has 300 hours of blast furnace time available.  Because of differences in the

furnaces at each mill, the time and cost to produce a ton of steel differs for each mill.  The time and cost for each mill are shown in Figure 1.  Each month, Arcelor must manufacture at least 1200 tons of steel 1 and 1100 tons of steel 2. Formulate a linear program to minimize the cost of manufacturing the desired steel. Solve it using python (take a screenshot of your code and report the solution found by software).

Figure 1: Steel production

Problem  4:    (16 points)     Solvay produces two chemicals:  barium and calcium.   These chemicals are produced via two manufacturing processes. Process 1 requires 2 hours of labor and 1kg of raw material to produce 200g of barium and  100g of calcium.   Process 2 requires 3 hours of labor and 2kg of raw material to produce 300g of barium and 200g of calcium.  Sixty hours of labor and 40kg of raw material are available.  Demand for barium is unlimited, but only 2kg of calcium can be sold.  Barium sells for $1.6/g, and calcium sells for $1.4/g.  Any calcium that is unsold must be disposed of at a cost of $0.3/g.  Formulate an LP to maximize Solvay’s revenue less disposal costs.  Solve it using python (take a screenshot of your code and report the solution found by software).

Problem 5:    (12 points)    A farmer grows wheat and corn on his 45-acre farm.  He can sell at most 140 bushels of wheat and 120 bushels of corn. Each acre planted with wheat yields 5 bushels, and each acre planted with corn yields 4 bushels.   Wheat sells for $30 per bushel, and corn sells for $50 per bushel.  To harvest an acre of wheat requires 6 hours of labor; 10 hours are needed to harvest an acre of corn.  Up to 350 hours of labor can be purchased at $10 per hour.   Let A1  denote acres planted with wheat; A2  denote acres planted with corn; and L denote hours of labor that are purchased. To maximize profits, the farmer should solve the following linear program:

,．            A1 + A2  车 45

   6A1 + 10A2 · L 车 0

max  150A1 + 200A2 · 10L   s.t.     ．．                  5A1(L) 车(车) 

                   4A2  车 120

．(           A1 , A2 , L > 0.

Use the output in Figure 2 to answer the following questions:

1. If only 40 acres of land were available, what would the farmer’s profit be?

2. If the price of wheat dropped to $26, what would be the new optimal solution to farmer’s problem?

3.  Use the SLACK portion of the output to determine the allowable in- crease and allowable decrease for the amount of wheat that can be sold. If only 130 bushels of wheat could be sold, then would the answer to the problem change?

Figure 2: Farm production

Problem  6:    (12 points)     Given A  e Rm ×n , b  e Rm , C  e Rp×n, and d e Rp , consider the polyhedra

P := (x e Rn  | Ax > b} and the notations

/a1(T)、

A =  ．        ．

(am(T)．

and

and

Q := (x e Rn  | Cx > d}

/c1(T)、

C =  ．       ．

(cp(T)．

(5)

(6)