0
$\begingroup$

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,

enter image description here

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – davidlowryduda May 19 '14 at 8:55
2
$\begingroup$

What are your basic variables? You need to solve for them in the tableau to get a BFS.

$\endgroup$
3
  • $\begingroup$ Oooh, I see - so I need to add two artificial variables, since I already have other two, right? $\endgroup$ – Zol Tun Kul May 16 '14 at 23:39
  • $\begingroup$ Yes, you need to do some kind of phase I procedure to get a BFS. $\endgroup$ – Brian Borchers May 16 '14 at 23:41
  • $\begingroup$ 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? $\endgroup$ – Zol Tun Kul May 17 '14 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.