Specific usecase of two-phase simplex algorithm

Question

The problem below aims to find to most optimal way to transport the fuel :

A company Er must transport a type of fuel from its two refineries Ra and Rb to its two points of sale PV1 and PV2. The quantities that can be produced on sites A and B can reach a maximum of 100 and 20 units respectively, while the demand for PV1 and PV2 is 40 and 80 units respectively. The unit cost of transport from each factory to each point of sale is indicated in the table below:

        PV1        PV2  
Ra      3          4
Rb      1          3

The company wants to know how to transport the merchant produced while minimizing the total cost of transport.

1. Formulate this problem in the form of a linear program (P).
2. Formulate the combined dual linear program.
3. Give an economic interpretation of the dual and its variables.
4. Solve by the simplex algorithm the LP (P).
5. Solve by LP transport algorithm (P).

---

The linear problem can be found below as :

\begin{align}\min&\quad z=3\cdot X_{11}+4\cdot X_{12}+X_{21}+3\cdot X_{22}\\\text{s.t.}&\quad X_{11}+X_{12}=100\\&\quad X_{21}+X_{22}=20\\&\quad X_{11}+X_{21}=40\\&\quad X_{12}+X_{22}=80.\end{align}

---

The Question Part

I'm doing well with the first three questions but I'm struggling with the 4th question, so far I have to solve the 4th question with the two-phase simplex algorithm due to its canonical form. I have found some resources on how to process with the two-phase simplex algorithm but I can't figure out how to apply it on my given example.

NOTE : Basically, the symbol "=" is either ">=" or "<="; it depends on the demand and the offer, but to be able to work with the two-phase simplex method we make the demand equal to the offer – the teacher said so. This way all our constraints become equal, we can add artificial variables but I don't know how to proceed from here to solve this problem.

The constraints before to make them equal :

Offer constraints : \begin{align}\quad X_{11}+X_{12}<=100\\ X_{21}+X_{22}<=20.\end{align}

Demand constraints : \begin{align}\quad X_{11}+X_{21}>=40\\ X_{12}+X_{22}>=80.\end{align}

Answer 1

The point of the 2-phase simplex is to find a feasible initial solution (a starting point for the "normal" simplex). Indeed finding a set of $X$ values that satisfy the constraints can be hard (manually). This is not a problem when you have constraints of the form $Ax\le b$, as $x=0$ is a trivial possibility.

To do this you introduce one artificial variable per constraint : \begin{align} &X_{11}+X_{12} +a_1=100\\ &X_{21}+X_{22}+a_2=20\\ &X_{11}+X_{21}+a_3=40\\& X_{12}+X_{22}+a_4=80 \end{align}

And you minimise $$\sum_{i=1}^4 a_i$$

Note that it is easy to find an initial solution for this first phase: just set $X=0$, $a_1=100$, $a_2=20$, $a_3=40$, $a_4=80.$ If you find an optimal solution with $a_1=a_2=a_3=a_4=0$, it means that you have found values of $X$ that satisfy your initial constraints.

You can then use these values of $X$ for phase $2$ as a starting point.