Derivate the $3$ equations system from a linear model

Question

I am asked to "derivate" (or find) the 3 equations system associated with the unique (and optimal) solution of a linear programming model.

This is the model:

$\min z = -5a - 3b - 4c$

Subject to

$2a+b+c +d = 20$

$3a+b+2c + e = 30$

$a,b,c,d,e \ge 0$

The only information that is given to me is that $b>0$ and $c>0$ at the optimum solution.

What this means :

• $b$ and $c$ are dependent variable at the optimum
• $a=d=e=0$ at the optimum (2 constraints mean only 2 dependent variables)

So I tried to replace the appropriate value in the equations to obtain

• $b+c = 20$
• $b+2c = 30$
• $-3b-4c=z$

However, the teacher said that since $a,b$ and $c$ appear in the objective, we want a system of 3 equations to get their values at the optimum (since we know that $d = e = 0$).

That means that we shouldn't suppose that $a=0$. He also hinted that $z$ is not an equation.

So we tried to put the 2 equations equal to the other to make a new equation

$2a+b+c-20 = 3a+b+2c-30$

Which gives us

$10 = a+c$

However, the 2 other equations cancel each other in the matrix and we get infinite solutions depending on the value of $a$ and $c$.

We also tried to represent $b$ and $c$ in function of $a,d$ and $e$ but since we are missing one equation, we don't know how to get the last one.

Q: So how do we "create" this third equation?

Answer 1

This is equivalent to $$\max z = 5a + 3b + 4c$$ under the same conditions and constraints.

Since the matrix calculations are tedious, it can be done on Octave Online. In the code below,

• c stands for the objective function;
• A stands for the coefficient matrix;
• b stands for the RHS in $Ax = b$;
• basis is an ordered collection of indexes representing the current basic varaibles ($a$ is 1, ..., $e$ is 5);
• B selects the columns of $A$ according to basis
• cB selects the entries of $c$ according to basis
• T stands for a simplex tableau.
  • the right bottom corner is the current objective value $z$
  • the rest at the bottom line helps determine the variable which is going enter the basis.
  • the rest on the right-hand side shows the current BFS.

Initially, $d$ and $e$ are chosen as basic variables, with $d=20,e=30$ and $z=0$.

octave:1> format rat;
octave:2> c = [5 3 4 0 0]'; b = [20 30]';
A = [2 1 1 1 0; 3 1 2 0 1];
octave:4> basis = [4 5];
octave:5> B = A(:,basis); cB = c(basis);
T = [B\A B\b; cB'*(B\A)-c' cB'*(B\b)]
T =

          2          1          1          1          0         20
          3          1          2          0          1         30
         -5         -3         -4          0          0          0

We start with the least number -5 at the bottom. Since -5 is in the 1st column, $a$ is going to enter the basis. We choose a pivoting element in the column above -5. As the ratio $20/2=30/3$ is the same, for simplicity, we choose 2 as the pivoting element. Since 2 is on the row representing $d$, we replace $d$ by $a$ in the basis. We try following what your teacher says: $a > 0$.

octave:7> basis = [1 5];
octave:8> B = A(:,basis); cB = c(basis);
T = [B\A B\b; cB'*(B\A)-c' cB'*(B\b)]
T =

          1        1/2        1/2        1/2          0         10
          0       -1/2        1/2       -3/2          1          0
          0       -1/2       -3/2        5/2          0         50

The number -3/2 is the least at the bottom row 3rd column, so $c$ is going to enter the basis, and $e$ is going to leave it.

octave:10> basis = [1 3];
octave:11> B = A(:,basis); cB = c(basis);
T = [B\A B\b; cB'*(B\A)-c' cB'*(B\b)]
T =

          1          1          0          2         -1         10
          0         -1          1         -3          2          0
          0         -2          0         -2          3         50

Here, we have two -2, but since the coefficient of $d$ is zero in the objective function, we let $b$ enter, and $a$ leave the basis.

octave:13> basis = [2 3];
octave:14> B = A(:,basis); cB = c(basis);
T = [B\A B\b; cB'*(B\A)-c' cB'*(B\b)]
T =

          1          1          0          2         -1         10
          1          0          1         -1          1         10
          2          0          0          2          1         70

Finally all entries at the bottom is non-negative, so we are done with $b = c = 10$, $z = 70$ and all other variables vanish. Therefore, according to your model, $a$ should be zero.