# What's wrong with this linear program formulation?

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...

• You've asked for this question to be deleted, but that would shortchange the effort of Brian. We prefer not to delete upvoted content. What I would recommend is that you edit your question with your realization (or write another answer, doesn't really matter), and accept Brian's answer (or your answer - whatever actually fits more). By the way, it's a very nicely written question, even if it doesn't actually make sense. – davidlowryduda May 19 '14 at 8:55

• I have added the variables and progressed on the problem. Now I have to solve an expanded program, but I can't find the pivot because $a$ is on the righthand side and I don't know the value of $a$. Does that mean I should have moved $a$ to the lefthand from the beginning? – Zol Tun Kul May 17 '14 at 0:00