Linear programming

1 Schedule

Problem sessions:

The homework is due Nov 18, 2008.
The QUIZ will be on Tuesday, Nov. 25.

2 List of algorithms covered in the class

(B-basic, I-intermediate, A-advanced):
I: Gaussian elimination (p. 219, DSV).
I: Computing the dual of a linear program (p. 206, DSV).
A: The simplex algorithm (p. 213, DSV).
B: Zero- sum games using linear programming (p. 208, DSV).
A: Max-flow using linear programming (p. 198, DSV).

3 Basic material

Important concepts, problems, theorems, and algorithms:
• system of linear equations, rank of a matrix,
• linear program , dual linear program,
• basic matrix notation.

Testing method :
• Solve a small linear program (2-3 variables).
• Solve a system of equations using Gaussian elimination (up to 4 variables).
• Given a system of equations , write it in a matrix form.
• Compute rank of a matrix.
• Solve a zero -sum game.

Example problems:
5.1 (due Nov 18, 2008) Solve the following linear program:

5.2 (due Nov 18, 2008) Solve the following system of equations using Gaussian elimination:

5.3 (due Nov 18, 2008) Write the following system of equations in the matrix form Ax = b:

5.4 (due Nov 18, 2008) Compute the rank of the following two matrices

Does the system 2x + 4y + 9z = 3, x − 3y + 5z = −1, 10y − z = 5 have a solution?

5.5 ( removed )

4 Additional homework

5.6 (due Nov 18, 2008) Solve the following linear program:

Use a linear programming solver to obtain the solution (for example you can use freeware lpsolve or function
Maximize in Mathematica (installed in most labs)).

5.7 (due Nov 18, 2008) There are n bottles which contain different mixtures of three chemicals called A,B,C.
The i-th bottle contains the chemicals in ratio a _i : b_i : c_i (thus, a_i/(a_i +b_i +c_i) fraction of the i-th bottle is chemical
A, b_i/(a_i +b_i +c_i) fraction of the i-th bottle is chemical B, and c_i/(a_i +b_i +c_i) fraction of the i-th bottle is chemical
C). We want to know whether it is possible to obtain a mixture containing the chemicals A,B,C in ratio a : b : c by
mixing various amounts from the bottles. Give an efficient algorithm for this problem.

For example, if the input is n = 2, the ratios in the bottles are 1 : 1 : 2 and 3 : 3 : 1, and we want to obtain
mixture with ratio 1 : 1 : 1 then the answer is YES (we can take 2 parts from the first bottle and 1 part from the
second bottle).

5.8 (due Nov 18, 2008) Construct the linear program dual to the following linear program:

Find the optimal solution of the primal and the dual problem. Use a linear programming solver to obtain the
solutions.

5 Additional problems from the book (do not turn in)

Try to solve the following problems. A few of them will be on the quiz. We will go over the ones that you choose in
the problem sessions.
• 7.1, 7.2, 7.3, 7.4, 7.7, 7.8, 7.11, 7.12, 7.13, 7.15, 7.19, 7.27.