A company is selling 2 products

• Producing 1 unit of product 1 requires 1 unit of resource 1 and 1 unit of resource 2, which can be sold for $2
• Producing 1 unit of product 2 requires 1 unit of resource 1 and 2 unit of resource 2, which can be sold for $3
• Total amount of resources 1 is 4 units
• Total amount of resources 2 is 6 units

−2	−3	0	0	0
1	1	1	0	4
1	2	0	1	6

0	−1	2	0	8
1	1	1	0	4
0	1	−1	1	2

0	0	1	1	10
1	0	2	−1	2
0	1	−1	1	2

• An optimal solution
• The objective is

Additional activity

The company now produces a 3rd product.

• 1 unit of product 3 requires 1 unit of resource 2 and is sold for $8

We don’t need to solve a new linear program

The decision variable set changes from to , the solution is feasible

All we need to do is to check whether we should produce some product 3

• If no, the current solution is optimal
• If yes, we increase the nonbasic variable until one basic variable becomes 0

All we need is the (vector of) reduced costs:

Where:

• : basis matrix
• : non-basis matrix
• : vector of objective coefficients corresponding to the basic variables
• : vector of objective coefficients corresponding to the non-basic variables

For a single nonbasic variable (), it simplifies to:

After we solve the original problem, we have and

• The optimal basis is

When we add a new decision variable , it is 0 (nonbasic) at the beginning

Therefore, to solve the new problem, we may start from the basis and the set of nonbasic variables

We start with the optimal tableau

0	0	1	1	10
1	0	2	−1	2
0	1	−1	1	2

0	0	?	1	1	10
1	0	?	2	−1	2
0	1	?	−1	1	2

The vecots of constraint coefficients for nonbasic variables is:

for column :

Where is the coefficient column for :

And the vector if reduced costs for nonbasic variables is

For column , that value is

0	0	−7	1	1	10
1	0	−1	2	−1	2
0	1	1	−1	1	2

From this new tableau keep iterating

0	0	−7	1	1	10
1	0	−1	2	−1	2
0	1	1	−1	1	2

0	7	0	−6	8	24
1	1	0	1	0	4
0	1	1	−1	1	2

6	13	0	0	8	28
1	1	0	1	0	4
1	2	1	0	1	6

with

Allows asking what if questions:

• What if it is $5 instead of $8
• What if it takes 2 of resource on instead of 1?
• What if it takes 1 of resource 2 instead of 0?

Additional Constraints

Primal

We add a new constraint:

Dual

We may plug in in the original optimal solution into the new constraint

• If it is feasible, it is optimal for the new problem
• In our example, it is not feasible because

The original optimal tableau

0	0	1	1	10
1	0	2	−1	2
0	1	−1	1	2

The new constraint introduces a new slack variable ()

Include to be a basic variable

Let and

We have

We then have

0	0	1	1	0	10
1	0	2	−1	0	2
0	1	−1	1	0	2
0	0	−2	1	1	−1

This is an invalid simplex tableau (RHS column column contains a negative value)

• This means is infeasible (as we already know)

Linear Programming Duality

We know a primal constraint is a dual variable

If a primal LP has one new constraint, it’s dual LP will have one new variable

We add a new constraint: