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

• An optimal solution $\left({𝑥}_1^{\ast },{𝑥}_2^{\ast }\right)=\left(2,2\right)$
• The objective is ${𝑧}^{\ast }=10$

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 $\left({𝑥}_1,{𝑥}_2\right)$ to $\left({𝑥}_1,{𝑥}_2,{𝑥}_3\right)$, the solution $\left({𝑥}_1^{\ast },{𝑥}_2^{\ast },0\right)$ is feasible

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

• If no, the current solution $\left({𝑥}_1^{\ast },{𝑥}_2^{\ast },0\right)$ is optimal
• If yes, we increase the nonbasic variable ${𝑥}_3$ 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 (${𝑥}_3$), it simplifies to:

After we solve the original problem, we have ${𝐵}^{\ast }=\left({𝑥}_1,{𝑥}_2\right)$ and ${𝑁}^{\ast }=\left({𝑠}_1,{𝑠}_2\right)$

• The optimal basis is ${𝐵}^{\ast }$

When we add a new decision variable ${𝑥}_3$, it is 0 (nonbasic) at the beginning

Therefore, to solve the new problem, we may start from the basis $𝐵=\left({𝑥}_1,{𝑥}_2\right)$ and the set of nonbasic variables $𝑁=\left({𝑥}_3,{𝑠}_1,{𝑠}_2\right)$

We start with the optimal tableau

The vecots of constraint coefficients for nonbasic variables is:

for column $𝑗$:

Where ${𝐴}_{𝑗}$ is the coefficient column for ${𝑥}_3$:

And the vector if reduced costs for nonbasic variables is

For column $𝑗$, that value is

From this new tableau keep iterating

$\left({𝑥}_1^{\ast \ast },{𝑥}_2^{\ast \ast },{𝑥}_3^{\ast \ast }\right)=\left(0,0,6\right)$ with ${𝑧}^{\ast \ast }=48$

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 $\left({𝑥}_1^{\ast },{𝑥}_2^{\ast }\right)=\left(2,2\right)$ into the new constraint

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

The original optimal tableau

The new constraint ${𝑥}_1\le 1$ introduces a new slack variable (${𝑠}_3$)

Include ${𝑠}_3$ to be a basic variable

Let $𝐵=\left({𝑥}_1,{𝑥}_2,{𝑠}_3\right)$ and $𝑁=\left({𝑠}_1,{𝑠}_2\right)$

We have

We then have

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

• This means $𝐵=\left({𝑥}_1,{𝑥}_2,{𝑠}_3\right)$ 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: