December 1999 Exam

[ 10 ]  1.  Use Phase I of the 2-phase simplex method to determine an initial legitimate feasible tableau for the linear program:

$$\halign{ ...$$

Solution

2.  The optimal tableau to a particular linear program in standard form is given below. [I've changed this slightly to conform to our notation]

[ 10 ]  a).  The entries on the right hand side of the constraints are 1, 55, and 3. Perform right hand side ranging.

[ 10 ]  b).  The objective function is z = 4 x₁ + x₂ + 5 x₃ + 3 x₄. Perform objective function ranging.

[ 10 ]  c).  The objective function is changed from z = 4 x₁ + x₂ + 5 x₃ + 3 x₄ to z = 7 x₁ + x₂ + 8 x₃ + 3 x₄. Determine the new optimal solution and the new optimal value.

[ 10 ]  d).  The constraint $x_4 \le 3$ is added to the original problem. Determine the new optimal solution and the new optimal value.

Solution

[ 10 ]  3.  A linear program in standard form has

$$A = \left[\matrix{-1 & 3 & 1 & -1\cr 1 & 8 & 5 & 3\cr 2 & ... ...r}\right] \qquad c = \left[\matrix{1\cr 2\cr 3\cr 8\cr}\right]$$

Assume that the revised simplex method is being used to find the optimal solution and that the current basis is (x₁, x₂, s₂). The current inverse basis matrix is

$$B^{-1} = \left[\matrix{ 5 & 0 & 3\cr 2 & 0 & 1\cr -21 & 1 & -11\cr}\right]$$

a).  Determine the next basis.

b).  Give an eta matrix E such that the new inverse basis matrix is E B^-1.

Solution

[ 10 ]  4.  Consider the linear program

$$\halign{ ...$$

a).  Find the dual of this problem.

b).  Use complementary slackness to determine if x=(0,4,-3) is an optimal solution. Justify your answer.

Solution

[ 10 ]  5.  Consider the quadratic program

$$\halign{ ...$$

a).  State explicitly the Karush-Kuhn-Tucker conditions for this problem.

b).  Explain where the restricted entry rule is used, what it is, and why it is needed.

Solution

[ 10 ]  6.  A manufacturer of plastics is planning to blend a new product from four chemical compounds. These compounds are mainly composed of three elements A, B and C. The composition and unit cost of these chemicals are shown below.

$$\matrix{\hbox{Chemical Compound} & C1 & C2 & C3 & C4\cr \hb... ... & 25 & 30\cr \hbox{Cost per kilogram} & 20 & 30 & 20 & 15\cr}$$

The new product consists of 25 to 30% element A, at least 30% element B, and at least 25% element C. Owing to side effects, the new material cannot consist of more than 30% of compound 1 or more than 40% of compound 4. Formulate a linear program for determining the least costly way of blending the compounds to make 100 kilograms of the new product. Your answer should be in a format acceptable to either Lindo or Lingo.

Solution

[ 10 ]  7.  An investor has $1000 which she wishes to invest in a combination of two stocks, S1 and S2, and a mutual fund MF. The investor currently has $300 invested in each of the stocks and $400 invested in the mutual fund. There is a 1% transaction fee for selling or buying either of the stocks and there is a 0.5% transaction fee for changes to the mutual fund. The expected rates of return for S1, S2 and MF are 15%, 20% and 8% respectively. The covariance matrix for these investments (in this order) is

$$V = \left[\matrix{.025 & .01 & .003\cr .01 & .06 & .002\cr .003 & .002 & .005\cr}\right]$$

Formulate a quadratic program for minimizing the investor's risk given that the investor requires an expected rate of return of at least 12%. Use x₁, x₂ and x₃ for the amounts of the three investments respectively, and put your answer in a form which is acceptable to either Lindo or Lingo.

Solution