0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ use the two-phase simplex method $\endgroup$ – LinAlg Nov 30 '18 at 0:16
  • $\begingroup$ @LinAlg How? ${}$ $\endgroup$ – user441848 Nov 30 '18 at 5:04
  • $\begingroup$ @LinAlg Do you know where can I find the matrix table representation of two-phase simplex method? In my book (Hillier) there is only the matrix table representation of the simplex. $\endgroup$ – user441848 Nov 30 '18 at 5:04
  • $\begingroup$ @Alt. Why is the last constraint an inequality? $\endgroup$ – callculus Nov 30 '18 at 15:23
  • $\begingroup$ @callculus Do you mean the $x_i\ge0$? $\endgroup$ – user441848 Nov 30 '18 at 19:25
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for your answer Alex, I agree that it should be $x_2+x_4=4$ in the LP problem. $\endgroup$ – user441848 Dec 4 '18 at 20:55
  • $\begingroup$ How would you construct the initial simplex tableau of the LP in (c) ? $\endgroup$ – user441848 Dec 4 '18 at 20:56
  • $\begingroup$ @Alt First I would look in Chaps. 3 and 4 for its definition. The same concerns part (b). This should be an easy exercise, and, maybe, the book suggests obtain (c) from (b). I guess the solution of this exersise should show your knowledge of mentioned methods (which may be needed at the exam). Unfortunately, this stuff is covered by a gap in my education, so my answer is partial. $\endgroup$ – Alex Ravsky Dec 4 '18 at 23:54
  • $\begingroup$ Right I should reread chaps. 3 and 4. As mentioned before I've solved (b). Btw thank you again:) $\endgroup$ – user441848 Dec 6 '18 at 2:12
1
+50
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ Thank you for your answer Siong Thye Goh. $\endgroup$ – user441848 Dec 5 '18 at 19:38
  • $\begingroup$ Why did you add $x_7$ and $x_8$ in the constraints of the linear program? $\endgroup$ – user441848 Dec 7 '18 at 18:51
  • $\begingroup$ so that if i want to start my simplex algorithm, there is an obvious starting point, $x_5$ to $x_8$ can be my basic variables and we set the rest to be zero. However, at the optimal value, $x_7$ and $x_8$ will be forced to be zero as the coefficient is $M$ in the objective value. $\endgroup$ – Siong Thye Goh Dec 7 '18 at 19:18
  • $\begingroup$ I don't see how your comment answer my question in the comment $\endgroup$ – user441848 Dec 8 '18 at 18:30
  • 1
    $\begingroup$ I believe the question is asked to test whether you are able to use big M method but of course, you don't have to use it. As long as you can pick your non-basic columns/ variables, you can do the simplex algorithm. I have edited to show how to do so. (remark: Depending on how simplex is taught to you, i am not sure if what i say makes sense to you, if it doesn't, you might want to tell me more about what you really know and what you do not know). $\endgroup$ – Siong Thye Goh Dec 9 '18 at 7:34

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.