Answer to Question #107859 in Operations Research for Mamabolo Letsatsi

Question

Solve the following linear program using simplex algorithm
Minimize z= a+b+c
Subject to: 1. a - b -c<=0
2. a + b + c>=4
3. a +b-c=2

Answer 1

problem formulating as,

$Minimize\quad z=a+b+c\\ subject\ to,\\ a-b-c\le 0\\ a+b+c\ge4\\ a+b-c=2\\$

After converting the simplex method(big M) form,

$Minimize\quad z=a+b+c+0s_1+0s_2+MA_1+MA_2\\ subject\ to,\\ a-b-c+s_1= 0\\ a+b+c-s_2+A_1=4\\ a+b-c+A_2=2\\$

Steps of every table is described after all the tables..

Table 01:

$S_1$ has gone out from the basis and a has come in to basis.

Table 02:

Row operations:

Row#1=Row#1

Row#2=Row#2-Row#1

Row#2=Row#2-Row#1

$A_1$ has gone out from the basis and b has come in to basis.

Table 03:

Row operations:

Row#3=Row#3/2

Row#1=Row#1+Row#3

Row#2=Row#2-Row#3*2

$A_2$ has gone out from the basis and c has come in to basis.

Table 04:

Row operations:

Row#2=Row#2/2

Row#1=Row#1+Row#2

Row#3=Row#3

since all the $Z-C_j\le0$ , optimal answer is occurred.

Answer to the minimization problem is,

$$\red{a=2\\b=1\\c=1\\Z_{min}=4\\}$$

In all the tables,

• blue numbers $(C_j)$ =corresponding coefficients in minimization function
• $Z-C_j$ = basis variable coefficients multiply by each column and add them -corresponding coefficient in minimization function(blue numbers)
• Then find largest $Z-C_j$(green column),that variable in that column is incoming variable to basis.
• Then b column is divide by that green column and find the smallest positive number. The variable is corresponding row(yellow row) is ​gone out from the basis.
• Then next table is find by making row operations to make the corresponding basis variable matrix to identity matrix.
• These steps are continue until all $Z-C_j \le0.$