You have two item factories, $A$ and $B$, and there are two clients that buy such item.
Each client has a demand - the first one needs $400$, and the second $300$.
Each factory has a storage of items - $A$ has $a$ and $B$ has $b$.
There is a transportation cost per item from one factory to a client. For the first factory, it costs $30$ for the first client, and $25$ for the second. For the second factory, it would be $36$ and $30$.
You want to supply the clients with the minimum transportation cost.
Well then,
Formulate a linear program for this. Assume that the factories are allowed to have leftover supplies.
Ok, for starters, surely $x_1+x_3 = 400$ and $x_2+x_4 = 300$?
$$\begin{cases} x_1+x_3 = 400\\ x_2+x_4 = 300 \end{cases}$$
Next, the factories shouldn't be able to supply more than their storage, so...
$$\begin{cases} x_1+x_3 = 400\\ x_2+x_4 = 300\\ x_1+x_2 \le a\\ x_3+x_4 \le b \end{cases}$$
So the objective function would be like
$$\min z = 30x_1 + 25x_2 + 36x_3 + 30x_4$$
I'm not sure if the above formulation is correct, but it looks fine so let's try to solve the program:
Transform the inequalities...
$$\begin{cases} x_1+x_3 = 400\\ x_2+x_4 = 300\\ x_1+x_2 + x_5 = a\\ x_3+x_4 + x_6 = b \end{cases}$$
The matrix looks like...
$$\begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 400 \\ 0 & 1 & 0 & 1 & 0 & 0 & 300 \\ 1 & 1 & 0 & 0 & 1 & 0 & a \\ 0 & 0 & 1 & 1 & 0 & 1 & b \\ 30 & 25 & 36 & 30 & 0 & 0 & z \end{bmatrix}$$
Wait. There's nothing to do here. The objective row has no negative terms, so the Simplex algorithm ends. This only suggests me that something did not go well - what was it?
I was told to create two artificial variables, so here goes:
The third and fourth column are not canonical, so we will add two artificial variables, $\color{red}{x_7, x_8}$:
$$\begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 0 & \color{red}1 & 0 & 400 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & \color{red}1 & 300 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & a \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & b \\ 30 & 25 & 36 & 30 & 0 & 0 & 0 & 0 & z \end{bmatrix}$$
We have expanded the program, so now we must solve
$$\min w = x_7 + x_8$$
$$\begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 400 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 300 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & a \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & b \\ 30 & 25 & 36 & 30 & 0 & 0 & 0 & 0 & z \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & w \end{bmatrix}$$
We must make the seventh and fourth columns canonical, by getting rid of the $1$s at the last row. This is done with
$$-r_1 + r_6 , -r_2 + r_6$$
$$\begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 400 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 300 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & a \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & b \\ 30 & 25 & 36 & 30 & 0 & 0 & 0 & 0 & z \\ -1 & -1 & -1 & -1 & 0 & 0 & 0 & 0 & w - 700 \end{bmatrix}$$
Now we must solve this expanded program with the Simplex method. However, I can't find the pivot because $a / 1 = a$ and I don't know what $a$ is...
