5. Linear Programming

5.1. Theory

5.2. Exercises

5.2.1. Finding a basic feasible solution and pivoting

Given the following linear program:

\[\begin{split}\min \quad & 2 x_1 + 3 x_2 \\ \text{subject to} \quad & x_3 = 2 + x_1 - x_2 \\ & x_4 = -3 + 2x_1 + 3x_2 \\ & x_1, x_2, x_3, x_4 \ge 0\end{split}\]

  1. Find a basic feasible solution (BFS) to initialize the simplex algorithm. Is it trivial to find it or do you need to create and solve the auxiliary problem?

  2. Find the optimal solution of the problem.

5.2.2. Standard, slack forms and pivoting

Given the following linear program:

\[\begin{split}\max \quad & x_1 + 3 x_2 \\ \text{subject to} \quad & x_1 - x_2 \le 8 \\ & x_1 + x_2 \ge 3 \\ & -x_1 + 4x_2 = 2 \\ & x_1 \ge 0\end{split}\]

  1. Transform it in standard form (only \(\le\) inequalities and all variables must have a positivity constraint).

  2. Transform the standard form of the problem in slack form (only equalities and all variables must have a positivity constraint).

  3. Find a BFS to initialize the simplex algorithm. Is it trivial to find it or do you need to create and solve the auxiliary problem?

  4. Find the optimal solution of the problem.

Note

If you are training yourself on other linear programs, it is always useful to verify your solution with online solvers like this one which provide all the steps to reach the solution.