Krdytkyu

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_2le 5\ x_3+x_4le4\ x_1+x_3=3\ x_2+x_4ge4\ x_ige0$$

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

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?

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_2le 5
\ x_3+x_4le 4
\ x_1+x_3=3
\ x_2+x_4=4
\ x_ige 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. 3le x_1+x_2le 5
\ 0le x_1le 3
\ 0le x_2le 4.$

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

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

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: