# 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

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 )

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 : bi : ci (thus, ai/(ai +bi +ci) fraction of the i-th bottle is chemical
A, bi/(ai +bi +ci) fraction of the i-th bottle is chemical B, and ci/(ai +bi +ci) 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.

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of June 22nd you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!

2Checkout.com is an authorized reseller
of goods provided by Sofmath

 "It really helped me with my homework.  I was stuck on some problems and your software walked me step by step through the process..." C. Sievert, KY

 Sofmath 19179 Blanco #105-234San Antonio, TX 78258 Phone: (512) 788-5675Fax: (512) 519-1805