Homework 5

Due: Nov. 9, 22:00:00

Linear program and standard form

  1. Transform the following linear program into an equivalent standard form:


    subject to:2x1+x23,3x1x27,x10.

  2. Consider the following optimization problem:


    subject to:Ax=b,x0,

    where A, b, c and d are given. Assume that ci0 for all i.

    As such this is not a linear program since the objective function involves absolute values. Show how this problem can be formulated equivalently as a linear program. Explain why the linear program is equivalent to the original optimization problem.

    Would the transformation work if we were maximizing?

Simplex method

  1. Solve the following linear program by simplex method (note that (x1,x2,x3)=(0,0,0) is feasible):


    subject to:x1+2x2+3x32,3x1+x2+2x32,2x1+3x2+x34,x1,x2,x30.

    Write all intermediate forms.

  2. We would like to use two-phase simplex method to solve the following linear program.


    subject to:x1x21,x1x23,2x1+x24,x1,x20.

    The first step should be to find a feasible solution by simplex method, since (x1,x2)=(0,0) is not feasible. What linear program should we solve at the first step (in order to find a feasible solution)?

    (You only need to write the linear program. No need to solve it.)


  1. Consider the dual of linear programs in standard form.

    • Write the dual to


      subject to:15x1+14x2+45x3+44x4+13x5=2021,xi0,

      and solve it by solving its dual.

    • What is the dual to the general standard linear program?


      subject to:Ax=b,x0.

  2. Consider the linear program


    subject to:Ax=b,x0.

    Assume that this linear program is unbounded. Prove that, if we replace b by any vector b, the resulting linear program is either infeasible or unbounded.