Answer to Question #108156 in Operations Research for Philasande Hlwempu

Question

How to solve the following linear program using simplex algorithm:

Minimizer z=a+b+c
Subject to 1.a-b-c lesser than or equal to 0
2.a+b+c greater than or equal to 4
3.a+b-c=2
4.a,b greater than or equal to 0

Answer 1

Solving the direct linear programming problem by the simplex method using a simplex table.

Define the minimum value of the objective function $z=a+b+c$ under the following conditions, restrictions.

$a-b-c\le0$

$a+b+c\ge4$

$a+b-c=2$

To construct the first supporting plan, we bring the system of inequalities to the system of equations by introducing additional variables (transition to the canonical form).

In the 1st inequality of meaning (≤), we introduce the basis variable $d$ . In the 2nd inequality of meaning (≥), we introduce the basis variable $e$ with a minus sign.

$a-b-c+d=0$

$a+b+c-e=4$

$a+b-c=2$

The expanded matrix of the system of constraints-equalities for this problem:

$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c:c} 1 & -1 & -1 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 0 & -1 & 4 \\ \hline 1 & 1 & -1 & 0 & 0 & 2 \end{array}$

We bring the system to the identity matrix by the Jordan transform method.

1. You can select $d$ as the base variable.

2. You can select $e$ as the base variable.

We get a new matrix:

$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c:c} 1 & -1 & -1 & 1 & 0 & 0 \\ \hline -1 & -1 & -1 & 0 & 1 & -4 \\ \hline 1 & 1 & -1 & 0 & 0 & 2 \end{array}$

3. You can select $c$ as the base variable.

Resolution element RE = -1. The line corresponding to the variable $c$ is obtained by dividing all the elements of the string $c$ by the resolving element RE = -1. In place of the resolving element, we get 1. In the remaining cells of the column c

c, we write zeros.

All other elements are determined by the rule of the rectangle.

Imagine the calculation of each element in the form of a table:

$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c:c} 0 & -2 & 0 & 1 & 0 & -2 \\ \hline -2 & -2 & 0 & 0 & 1 & -6 \\ \hline -1 & -1 & 1 & 0 & 0 & -2 \end{array}$

Since the system has an identity matrix, we take $z=(4,5,3)$ as the basis variable.

We express the base variables through the rest:

$d=2b-2$

$e=2a+2b-6$

$c=a+b-2$

Substitute them in the objective function:

$z=2a+2b-2$

Among the free members, there are negative values; therefore, the obtained basic plan is not basic.

Instead of the variable $e$ , you must enter the variable $a$ .

We perform simplex table transformations using the Jordan-Gauss method.

$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c:c:c} Basis&B&a&b&c&d&e\\ \hline d&-2&0 & -2 & 0 & 1 & 0 \\ \hline a&3&1 & 1 & 0 & 0 & -1/2\\ \hline c& 1 & 0 & 0 & 1 & 0 & -1/2\\ \hline z&-8&0&0&0&0&1 \end{array}$

Among the free members of bi, there are negative values; therefore, the obtained basic plan is not basic.

Instead of the variable $d$ , you must enter the variable $b$ .

We perform simplex table transformations using the Jordan-Gauss method.

$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c:c:c} Basis&B&a&b&c&d&e\\ \hline b&1&0 & 1 & 0 & -1/2 & 0 \\ \hline a&2&1 & 0 & 0 & 1/2 & -1/2\\ \hline c& 1 & 0 & 0 & 1 & 0 & -1/2\\ \hline z&-8&0&0&0&0&1 \end{array}$

We express the base variables through the rest:

$b=1/2*d+1$

$a=-1/2*d+1/2*e+2$

$c=1/2*e+1$

Substitute them in the objective function:

$z=(-1/2*d+1/2*e+2)+(1/2*d+1)+(1/2*e+1)$

Basic variables are variables that are included in only one equation of the constraint system and, moreover, with a unit coefficient.

We solve the system of equations for basis variables: $a,b,c$

Assuming that the free variables are 0, we get the first reference plan:

$z=(2,1,1,0,0)$

A basic solution is called admissible if it is non-negative.

$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c:c:c} Basis&B&a&b&c&d&e\\ \hline b&1&0 & 1 & 0 & -1/2 & 0 \\ \hline a&2&1 & 0 & 0 & 1/2 & -1/2\\ \hline c& 1 & 0 & 0 & 1 & 0 & -1/2\\ \hline z&0&0&0&0&0&1 \end{array}$

We pass to the basic algorithm of the simplex method.

1. Verification of the optimality criterion.

Among the values of the index row there are no positive ones. Therefore, this table determines the optimal plan for the task.

The final version of the simplex table:

$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c:c:c} Basis&B&a&b&c&d&e\\ \hline b&1&0 & 1 & 0 & -1/2 & 0 \\ \hline a&2&1 & 0 & 0 & 1/2 & -1/2\\ \hline c& 1 & 0 & 0 & 1 & 0 & -1/2\\ \hline z&0&0&0&0&0&1 \end{array}$

The optimal plan can be written as follows:

$a=2, b=1, c=1$

$z=1*2+1*1+1*1=4$