Derivate the $3$ equations system from a linear model 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?
 A: 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.
