2013.10.

14

Linear programming
The simplex method

Eventually reach optimal vertex

Move to a better vertex

Start at some vertex

1

Optimal production schedule

Production Processing time required Time

process For a table, x For a chair, y available
Cutting 4h 3h 240 h
Assembling 2h 1h 100 h
Net profit / Unit 7 Lt 5 Lt
How many units of tables and Profit: P 7x 5y max
chairs should be produced in
Constraints on resources:
order to maximize profit not
violating the constraints? Cutting time: 4x 3y 240
Assembly 2x y 100
time: x 0; y 0
Natural:

1
 2013.10.14

Geometrical solution
Moving isoprofit line P = 7x + 5y → max

Isoprofit line P = 7x + 5y

The simplex method: tables and chairs

Profit: P 7x 5y max
Tables Chairs Total time
Cutting time: 4 x 3 y 240
What is the economical
Assembly time: 2 x y 100
interpretation of the slack
Natural: x 0; y 0 variables s1, s2?

Step 1. Transform the system of linear inequalities into a

system of linear equations by introducing slack variables
s1, s2, … , sm ≥ 0:
The slack variables have meaning
of remaining resources. E.g., if we
Cutting time: 4x 3y s1 240 produced nothing, x = y = 0, then
Assembly time: 2x y s2 100 all resources were in place:
s1= 240, s2 = 100.
4

2
 2013.10.14

The simplex method

Step 2. Put the objective function P 7 x 5 y into the form:
7 x 5 y 0 s1 0 s2 P 0
• If variable with the negative coefficient is increased, then profit
increases by the value of the coefficient:

7( x 1) 5 y 0 s1 0 s2 P 7 0
7 x 5( y 1) 0 s1 0 s2 P 5 0

• Profit decreases, if variable with the positive coefficient is increased

• For the slack variables (resources!), vice versa holds

The simplex method

Putting all together, we obtain the following system of linear
equations:

Cutting time 4x 3y s1 240;

Assembly time 2x y s2 100;
Profit /unit 7x 5y P 0

Step 3. Write initial simplex tableau:

For the beginning, we
4 3 1 0 0 240 produce nothing: x = y = 0,
2 1 0 1 0 100 thus we have all resources
unused: s1= 240, s2 = 100.
7 5 0 0 1 0
Profit P is 0, also
6

3
 2013.10.14

The simplex method

x y s1 s2 P Total
Cutting time 4 3 1 0 0 240
Assembly time 2 1 0 1 0 100
Profit /unit 7 5 0 0 1 0

Negative values in the profit line indicate possibility to increase

the profit by increasing production by 1 unit. If there were no
negative values, then optimal solution is reached.

We produce nothing so far. Which product, tables or chairs,

should be included into production plan first?

Step 4. In the profit line determine the entry with the largest
absolute value. This column is called the pivot column.
7

The simplex method

Pivot element
x y s1 s2 P Total
Cutting time 4 3 1 0 0 240 240 / 4 = 60
Assembly time 2 1 0 1 0 100 100 / 2 = 50
Profit /unit 7 5 0 0 1 0

We decided to start producing tables. How many tables we

can produce given the resources on hand?

240 / 4 = 60 – cutting time allows us to produce 60 tables.

100 / 2 = 50 – assembly time allows us to produce only 50 tables.

Step 5. Divide free terms by corresponding element of the

pivot column and pick the row with the least ratio. This is the
pivot row. 8

4
 2013.10.14

The simplex method

x y s1 s2 P Total
Cutting time 4 3 1 0 0 240
Assembly time 2 1 0 1 0 100 :2
Profit /unit 7 5 0 0 1 0

We decided to produce 50 tables. This requires certain amount

of resources. Rework the tableau to reflect remaining
resources and profit gained.

Step 6. Produce elementary row operations using the pivot

element, according the Gaussian elimination:

a) Divide the pivot line by the pivot element

b) Make zeros in the pivot column (above and below the pivot
element) 9

The simplex method

x y s1 s2 P Total
Cutting time 4 3 1 0 0 240
Assembly time 1 1 / 2 0 1 / 2 0 50 (–4) 7
Profit /unit 7 5 0 0 1 0
x y s1 s2 P Total
Cutting time 0 1 1 2 0 40 Cutting time left
Number of tables
Assembly time 1 1/ 2 0 1/ 2 0 50 decided to produce
Profit /unit 0 3 / 2 0 7 / 2 1 350 Profit if 50 tables
were produced
Decision to produce
tables
Still not the best
plan!

Step 7. Go to Step 4 until all profit row entries become

non-negative
10

5
 2013.10.14

The simplex method

Step 4 and 5 repeated:

x y s1 s2 P Total
Cutting time 0 1 1 2 0 40 40 / 1 = 40
Assembly time 1 1/ 2 0 1/ 2 0 50 50 / (1/2) = 100
Profit /unit 0 3 / 2 0 7 / 2 1 350

Step 6 repeated:

x y s1 s2 P Total
Cutting time 0 1 1 2 0 40 (–1/2) 3/2
Assembly time 1 1/ 2 0 1/ 2 0 50
Profit /unit 0 3 / 2 0 7 / 2 1 350
11

The simplex method

x y s1 s2 P Total
Cutting time 0 1 1 2 0 40
Assembly time 1 0 1 / 2 3 / 2 0 30
Profit /unit 0 0 3/ 2 1 / 2 1 410

Conclusion. Optimal product mix is achieved:

Number of:
Tables x = 30;
Chairs y = 40;
Maximal profit Pmax(40, 30) = 410.

12

6
 2013.10.14

The simplex method

Shadow prices of the resources
x y s1 s2 P Total
Cutting time 0 1 1 2 0 40
Assembly time 1 0 1 / 2 3 / 2 0 30
Profit /unit 0 0 3/ 2 1 / 2 1 410

The last row corresponds to the equation:

3/2s1 + 1/2s2 = 410.
If resources s1 are increased by 1 unit, then
3/2(s1 + 1) + 1/2s2 = 410 + 3/2.
Buying more resources allows us to produce more and increase our profit.
The last line shows, that one additional hour in cutting increases profit by
3/2 Lt; one additional hour in assembly increases profit by ½ Lt. Thus, these
are the maximal prices that could be paid for additional unit of resources.
They are referred to as the shadow prices of the resources.
13

Setting up the initial simplex tableau

1. Transform the system of linear inequalities
into a system of linear equations by
introducing slack variables s1, s2, … , sm
2. Rewrite the objective function
c1 x1 c2 x2 ... c n x n 0s1 0s 2 ... 0s m P 0
3. Write the corresponding augmented matrix

14

7
 2013.10.14

The simplex method

1. Set up the initial simplex tableau
2. Determine whether the optimal solution has been
reached by examining all entries in the last row to the
left of the column of free terms
1. If all entries are non-negative, the optimal solution has been
reached. Proceed to step 4.
2. If there are one or more negative entries, the optimal
solution has not been reached yet. Proceed to step 3
3. Perform the pivot operation. Return to step 2.
4. Determine the optimal solution(s). The optimal value of
the variable heading each unit column is given in the
column of free terms in the row containing 1. The
variables heading columns not in unit form are assigned
value 0 (corresponding products are suggested not to
produce).
15

Solve by the simplex method

P = 2x + 2y + z max
2x + y + 2z ≤ 14
2x + 4y + z ≤ 26
x + 2y +3z ≤ 28
x ≥ 0, y ≥ 0, z ≥ 0

16

8
 2013.10.14

Standard minimization problem:

• The objective function is to be minimized
• All the variables are nonnegative
• Each linear constraint may be written so that the
expression involving the variables is greater than or
equal to a constant
C 6x 8 y min
• Every standard minimization
40 x 10 y 2400
problem can be converted into
a standard maximization problem. 10 x 15 y 2100
The first one is called primal problem, 5 x 15 y 1500
the other is called a dual problem x 0, y 0

Converting primal to dual

1. The rows in the primal problem become columns in the dual problem;
2. Coefficients of the objective function in the primal problem become
the right-hand side of the constraints in the dual problem;
3. The right-hand side coefficients in the primal problem become the
coefficients of the target function
4. Minimization problem becomes maximization problem, and vice versa
5. The inequality signs become reversed

Primal problem Dual problem

C 6x 8 y min P 2400u 2100v 1500 z max
40 x 10 y 2400 40u 10v 5 z 6
10 x 15 y 2100 10u 15v 15 z 8
5 x 15 y 1500
x 0, y 0 u 0, v 0, z 0

9
 2013.10.14

The Fundamental Theorem of Duality

(by John von Neumann, 1903-1957)

• A primal problem has a solution if and only if

the corresponding dual problem has a
solution. Furthermore, if a solution exists,
– The objective functions of both problems attain
the same optimal value
– The optimal solution to the primal problem
appears under the slack variables in the last row
of the final simplex tableau associated with the
dual problem

Convert the problem to the dual one and solve:

20

10