INFORMATION COMPUTER LAB 1

TMA945 Applied optimization

Michael Patriksson

11 februari 2002

Preparations

We do recommend that you formulate all problems on standard form before the laboration. In addition there are some dual problems which may be formulated in advance. Remember that the simplex method requires equality constraint and non-negative variables.

Examination

Deadline for turning in the laboration is 18/2, 24.00! What we want is answers to all questions, and a short motivation to all answers except 1 2 and 5. The handing in we be via a plain text file. This file sp Should be named lab1.txt and you should put it under the root in your account (the directory where you are when you log in) We will copy this file at the deadline. In addition to the answers this file should include the number of the group and the names of the participants, prominently displayed at the beginning of the file. Even if you prefer working at home, we want you to place the file at the account at the department. A tip for you who prefers to work at home is to place a .forward file in your lab account containing the mail address of your home account. This will forward all mail sent to the account to your home account. If you have passed the laboration, or if you need to correct the answers, we will send mail saying so to the laboration account. If you need to correct the laboration, a correcltion should be placed at the same place and named lab1_retur1.txt.

The simplex method

In this laboration you will solve some small LP-problems using the simplex method implemented in matlab. The purpose of this laboration is to increase your understanding of linear programming, duality sensitivity analysis and the simplex method.

An extra exercise is to solve the famous diet-problem using an interactive program at Argonne national laboratory.

First we describe the matlab program, after this follows the problems to be solved.

The Matlab program

Before you start make sure that you are located in the directory where your matlab files are. (The Matlab files are retrieved according to instructions given at the course home page

http://www.md.chalmers.se/~mipat/TOkurs.html.)

Unpack the files by giving the command tar -xvf lab1_eng.tar at the prompt. This will create a directory named LP. Descend into this directory by typing cd LP and start matlab by typing

matlab.

Once matlab starts up you may start the program by writing simplex at the prompt.

Entering the problem

The problem to be entered must be on standard form, that is, all constraints should be equality constraints and the right hand side of these constraints should be non-negative. This means that you must add slack variables and/or artificial variables.

Once started, the program will ask for the dimension of the problem, after this the program window will appear and you press Edit to enter the matrix and vectors into the table. All fields which may be altered will be slightly pink. You may switch fields by pressing Tab. After filling in all number you press Edit again to stop the data entry. All fields left empty will be filled with 0.

Solving LP-problems using the simplex method

After entering the problem you need to select a starting basis. This is done by marking which variables should be basic and clicking supply basis

The program will now list the basis matrix, compute its inverse, the value of the basic variables and the value of the objective function. Choose the incoming variable by selecting it and click give incoming . The program will now compute B^{−1}A^{j}. You choose which variable should leave the basis by marking the wanted row to the right of the value of the basic variables and click Change basis . Continue in this fashion until you find an optimal basis.

Solving a problem using both phases of the simplex method If the problem is such that no obvious feasible basis exists, you must use the two phase method. This is done by supplying the phase-I objective function and solve the problem. Make sure that you remember the optimal basis. Now change the objective function th the one given in the problem and remove the artificial variables. Enter the previous feasible basis as your starting basis and continue.

Adding a variable If you need to add an extra variable, this is done by clicking New column This will add an extra column and place the program in editing mode.

Removing a variable Chose which variable should be removed by clicking the buttons above the matrix (the same ones used to choose the basis), and click Remove column

Adding a constraint A new constraint requires a new row in the constraint matrix, and usually a new column for the slack variable. Adding a new row works in the same way as adding a new column, but after adding a row, a new starting basis must be chosen.

Removing a constraint Chose which constraint should be removed by clicking the buttons to the right of the values of the basic variables (the same button used to designate a leaving variable) and click remove row .

Changing a coefficient This is done by pressing Edit and changing the matrix

Summary of commands

The following commands are available:

Supply basis  - Supplies a new basis chosen by pressing the buttons above the columns.
Change basis  - Designates the leaving variable and changes the basis.
New column  - Adds a new column and places the program in editing mode.
Edit  - Toggles editing mode for the program.

Save - Save the problem under the name given in the field Filename. If no name is given the name default is used. The format used is matlabs .mat format.

New row - Creates a new row in the constraint matrix and places the program in editing mode.

Retrieve - Restores the problem in the file given by the field filename. If no name is used, the name default is used.

Remove column - Remove the column/columns indicated by the radio-buttons above the matrix.

Remove row - Removes the rows indicated by radio-buttons to the right of the basic variable values.

Quit  - Terminates the program

Workspace

In Matlabs workspace we have the matrix (A), the cost (c) the right hand side (b), the basis (B), the basis inverse (invB), the reduced cost (rc), the basic variable indices (basindex), b̄ (Bb) and Ā^{j} (col).

Exercises

1. Solve the problem

max z = 2x_{1} + 4x_{2} + 3x_{3}
då x_{1} + 3x_{2} + 2x_{3} ≤ 30
x_{1} + x_{2} + x_{3} ≤ 24
3x_{1} + 5x_{2} + 3x_{3} ≤ 60
x_{1}, x_{2}, x_{3} ≥ 0

2. Solve the problem

min z = x_{1} + 3x_{2} + 2x_{3}
då 2x_{1} + x_{2} + x_{3} ≤ 30
x_{1} + 2x_{2} + x_{3} ≥ 10
−x_{1} + 2x_{2} + 3x_{3} ≤ 40
x_{1}, x_{2}, x_{3} ≥ 0

using both phases of the simplex method.

3. Solve the problem

min z = 4x_{1} + 10x_{2} − 4x_{3}
då −2x_{1} + x_{2} + x_{3} ≤ 2
−3x_{1}  + x_{3} ≥ 1
x_{2} − x_{3} ≥ 1
x_{1}, x_{2}, x_{3} ≥ 0

4. Formulate and solve the dual problem of exercise 3. Check that the answer is consistent with the answer from exercise 3.

5. Solve the problem

max z = 6x_{1} + 4x_{2} + 7x_{3}
då x_{1} + 2x_{2} + 3x_{3} ≤ 8
2x_{1} + x_{2} + 2x_{3} ≤ 5
3x_{1} + 3x_{2} + 4x_{3} ≤ 10
x_{1}, x_{2}, x_{3} ≥ 0

6. Add a new variable to problem 5, having the cost coefficient 2 and the constraint matrix column ( 3 0 1). Supply the new variables reduced cost in the basis optimal for problem 4. reoptimize the problem and give the solution of the augmented problem. Comment on the result.

7. Given the optimal basis in exercise 6, calculate the shadow-price of constraint 2. Using this shadow price, what should be the new optimal value if the right hand side of constraint 2 is changed to 6. Check the result with matlab and comment on the result.

The diet problem (Do not turn this in, mostly for fun).

The diet problem is one of the first known applications of linear-programming. The task is to supply the daily intake of some necessary substances (vitamins, minerals, proteins, fat and so forth) as cheaply as possible given a number of different foods and their nutritional content. The original problem was to feed US soldiers as cheaply as possible.

At the address

http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/diet/

you will find an interactive program which allows you to choose from a number of different foods, and amount these an LP-solver will choose the cheapest diet satisfying all constraints.

In addition you may read about the history of this problem as well as get more information about linear programming. Another excellent site on optimization is the INFORMS (INstitute For Operations Research and the Management Sciences) home page located at

http://www.informs.org/Resources/