Transportation problem into initial simplex tableau

544 Views Asked by At

enter image description here

I did (b) .

For (a), I got this

$$\min 3x_1+2.7x_2+2.9x_3+2.8x_4\\ s.t. x_1+x_2\le 5\\ x_3+x_4\le4\\ x_1+x_3=3\\ x_2+x_4\ge4\\ x_i\ge0$$

The standard form is

$$\min 3x_1+2.7x_2+2.9x_3+2.8x_4\\ s.t. x_1+x_2+x_5= 5\\ x_3+x_4+x_6=4\\ x_1+x_3=3\\ x_2+x_4-x_7=4\\ x_i\ge0$$

When writting the initial simplex tableau I found a problem because there are only 3 basic variables and 4 constraints, what do I do to solve the problem?

2

There are 2 best solutions below

4
On BEST ANSWER

I did a part of (a) and (c).

(a) I almost agree with your answer.

Introduce the following variables.

$x_1$ - the number of pints bought from Dick today,

$x_2$ - the number of pints bought from Dick tomorrow,

$x_3$ - the number of pints bought from Harry today,

$x_4$ - the number of pints bought from Harry tomorrow.

Remark that even if Tom can keep brew bought today for tomorrow, this is wrong, because he can buy it cheaper tomorrow. So without loss of generality we can assume that Tom buys $3$ pints of brew today and $4$ pints of brew and tomorrow. Then we have the following linear programming (LP) problem.

$\min 3x_1+2.7x_2+2.9x_3+2.8x_4\\ s.t. x_1+x_2\le 5 \\ x_3+x_4\le 4 \\ x_1+x_3=3 \\ x_2+x_4=4 \\ x_i\ge 0.$

(c) Replacing $x_3$ by $3-x_1$ and $x_4$ by $4-x_2$ we obtain the following LP problem

$\min f(x_1,x_2)=0.1x_1-0.1x_2+19.9\\ s.t. 3\le x_1+x_2\le 5 \\ 0\le x_1\le 3 \\ 0\le x_2\le 4.$

This LP problem has only two variables and can be solved graphically.

enter image description here

The domain of $(x_1,x_2)$ lies between the black segments.

The lines with $f(x_1, x_2) =\operatorname{const}$ are parallel to the straight line $x_1=x_2$, thus the minimum of $f$ on the domain of $(x_1,x_2)$ is achieved when $x_1=0$ and $x_2=4$.

Thus the final answer is $x_1=0$, $x_2=4$, $x_3=3$, $x_4=0$. In this case $f=19.5$.

7
On

Your initial linear programming problem is equivalent to

$$\min 3x_1 + 2.7 x_2 + 2.9x_3 + 2.8 x_4 + Mx_7 + Mx_8$$ subject to $$x_1+x_2 + x_5 = 5$$ $$x_3+x_4+x_6=4$$ $$x_1+x_3+x_7 =3$$ $$x_2+x_4+x_8 = 4$$ $$x \ge 0$$

The big $M$ is going to force $x_7$ and $x_8$ to be $0$ at optimal value and you can begin the simplex at $x = (0,0,0,0,5,4,3,4)$.

To formulate this as a transportation problem, one possible way is to imagine that on the third day, all the remaining beers are going to be donated for free. Hence the total demand is equal to the total supply and the objective function is preserved. The parameter table can be listed as follows. The last column represents the supply amount and the last row represents the demand amount. The other indicates the corresponding cost.

\begin{array}{|c|c|c|c|c|}\hline & D_1 & D_2 & D_3 & \text{Supply} \\ \hline S_1 & 3 & 2.7 & 0 & 5 \\ \hline S_2 & 2.9 & 2.8 & 0 & 4 \\ \hline \text{Demand} & 3 & 4 & 2 & \\ \hline \end{array}

To solve the problem, you can reduce it to a $2$ dimensional problem and solve it.

Or just for fun, you can do the following:

In each of the boxes below, I use the convention of $(c_{ij}, y_{ij})$ where $y_{ij}=x_{ij}$ if it is basic and $y_{ij}=c_{ij}-u_i-v_j$ otherwise. I will use purple to indicate the first case.

\begin{array}{|c|c|c|c|c|}\hline & D_1 & D_2 & D_3 & \text{Supply} \\ \hline S_1 & (3, \color{purple}3) & (2.7,\color{purple}2) & (0,0.1) & 5 \\ \hline S_2 & (2.9, - 0.2) & (2.8,\color{purple}2) & (0,\color{purple}2) & 4 \\ \hline \text{Demand} & 3 & 4 & 2 & \\ \hline \end{array}

It is not optimal as we can see a negative reduce cost. That will be the entering variable.

\begin{array}{|c|c|c|c|c|}\hline & D_1 & D_2 & D_3 & \text{Supply} \\ \hline S_1 & (3, \color{purple}1) & (2.7,\color{purple}4) & (0,-0.1) & 5 \\ \hline S_2 & (2.9, \color{purple}2) & (2.8,0.2) & (0,\color{purple}2) & 4 \\ \hline \text{Demand} & 3 & 4 & 2 & \\ \hline \end{array}

\begin{array}{|c|c|c|c|c|}\hline & D_1 & D_2 & D_3 & \text{Supply} \\ \hline S_1 & (3, 0.1) & (2.7,\color{purple}4) & (0,\color{purple}1) & 5 \\ \hline S_2 & (2.9, \color{purple}3) & (2.8,0.1) & (0,\color{purple}1) & 4 \\ \hline \text{Demand} & 3 & 4 & 2 & \\ \hline \end{array}

Now, all the reduce cost are nonnegative. The solution suggest that on the first day, we should get $3$ pints at $2.9$ and on the second day, we should get $4$ pints at $2.7$.

Edit:

Let me avoid using big $M$ method since you are not familiar with it.

To implement the simplex algorithm, we need to find our basis matrix.

These are our linearity constraints. $$x_1+x_2+x_5=5$$ $$x_3+x_4+x_6=4$$ $$x_1+x_3 =3$$ $$x_2+x_4 = 4$$ $$x \ge 0$$

We want to pick $4$ non-basic variables. For example, let's pick $x_1=3, x_2=4$, let $x_3=0$ and $x_4=0$. Now, we can let $x_5=2$ and $x_6=4$.

That is we pick $x_1, x_2, x_5, x_6$ to be non-basic. Then our $$B = \begin{bmatrix}1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \end{bmatrix}.$$

From there we can easily compute $-c_B'B^{-1}A, c'-C_B'B^{-1}A, B^{-1}b, B^{-1}A$. That is we can construct our simplex tableu and start from there.

Remark: