System Analysis Simplex Method.General LP problem is to find the values

  General LP problem is to find the values of X₁,X₂,…..X_n which maximizes (or minimizes) the objective function

  Max (or Min) Z= C₁X₁+C₂X₂+………C_nX_n

  While satisfying the constraints

  a₁₁X₁+…….a_1nX_n             ≤b₁  or  ≥ b₁

  a₂₁X₁+…….a_2nX_n               ≤b₂  or  ≥ b₂

  ……..

  a_m1X₁+…….a_mnX_n ≤b_m or  ≥ b_m

  and    X1, ….Xn     ≥0 

_{……………………………………………………………………………………………………..}

  This problem can be put in the canonical form as follows.

  Inequalities can be converted to equalities.

  a₁₁X₁+…….a_1nX_n  ±S₁   =b₁

  a₂₁X₁+…….a_2nX_n      ±S₂ =b₂

  ……..

  a_m1X₁+…….a_mnX_n      ±S_m = b_m

  ( by adding  a slack or a surplus variable)

……………………………………………………………………………………………..

Minimization or maximization

  Max (min) Z= C₁X₁+C₂X₂+………C_nX_n

 can be converted to a

min (max) Z’=-{ C₁X₁+C₂X₂+………C_nX_n}

 by multiplying the objective function by -1.

…………………………………………………………………………………..

DEFINITIONS

                       Slack variables:

 are defined, when there are  ≤ inequalities.

In the example discussed , the available  capacities of the  three machines M1,M2 and M3 are 40,40 and 40 respectively..

Unused  amounts of the three machines are denoted by X3,X4 and X5.  (They are ≥0.)

Some books denote them by Sj .

……………………………………………………………….

  Surplus variables: 

  re defined when there are ≥ inequalities.

  In the diet planning  problem of the dog,

  The aminimum protein requirements are specified on the r.h.s.. If you feed more,  the dog gets more than what is required.

The excess amount of protein is denoted by X_j or S_j  .(they are ≥ 0) The amount overfed is the surplus variable.

By subtracting that amount we get the equality.

……………………………………………………….

  Non basic variables:

  The variables which have the value zero are called non basic variables.

  Basic variables:

  Variables which  are positive  are called basic variables. However some times the basic variables can have zero values and then the solution is said to be  degenerate .

……………………………………………………………..

  Handling of in-equality Constraints

  Case 1: Slack Variable:

x₁+2x₂+3 x₃ +4x₄£25 

l  Modified to

         x₁+2x₂+3x₃+4x₄+ x₅=25 

         x5³0 is a slack variable.

  Case 2: Surplus Variable:

2 x₁+ x₂-3 x₃³12

l  Modified to

      2 x₁+ x₂-3 x₃- x₄=12

      x₄³0 is a surplus variable

Table 1
Basic={5 6 7};Nonbasic={1 2 3 4}

		6	10	9	20	0	0	0
CB	Basis	x1	x2	x3	x4	x5	x6	x7	constraints
0	x5	4	9	7	10	1	0	0	600 (600/10=60)
0	x6	1	1	3	8	0	1	0	420(420/8=52.5)
0	x7	30	40	20	10	0	0	1	800(800/10=80)
DZ		6	10	9	20	-	-	-	Z=0

Table 2
Basic={5 4 7};Nonbasic={1 2 3 6}

		6	10	9	20	0	0	0
CB	Basis	x1	x2	x3	x4	x5	x6	x7	constraints
0	x5	2.75	7.75	3.25	0	1	-1.25	0	75(75/7.75=9.6774)
20	x4	0.125	0.125	0.375	1	0	0.125	0	52.5(52.5/0.125=420)
0	x7	28.75	38.75	16.25	0	0	-1.25	1	275(275/38.5=7.0798)
DZ		3.5	7.5	1.5	-	-	-2.5	-	Z=1050

Table 3
Basic={5 4 2};Nonbasic={1 7 3 6}

		6	10	9	20	0	0	0
CB	Basis	x1	x2	x3	x4	x5	x6	x7	constraints
0	x5	-3	0	0	0	1	-1	-0.2	20
20	x4	0.0323	0	0.3226	1	0	0.129	-0.0032	51.6129
10	x2	0.7419	1	0.4194	0	0	-0.0323	0.0258	7.0968
DZ		-2.0645	-	-0.1935	-	-	-1.6452	-2.2581	Z=1103.226

Ø 5x1+10x2<=60

Ø 4x1+4x2<=40

X1, X2 >=0

Z=6x1+8x2

Ø 5x1+10x2 + S1 = 60

Ø 4x1+4x2 + S2 = 40

X1, X2, S1, S2 >=0

PIVOT COLUMN

operation	basis	X1	X2	S1	S2	value	ratio
Cbi	Cj	6	8	0	0
0	S1	5	10	1	0	60	60/10=6
0	S2	4	4	0	1	40	40/4=10
	Zj	0	0	0	0	0
	Cj-Zj	6	8	0	0

PIVOT COLUMN

operation	basis	X1	X2	S1	S2	value	ratio
Cbi	Cj	6	8	0	0
8	X2	1/2	1	1/10	0	6	6(1/2)=6
0	S2	2	0	-2/5	1	16	16/2=8
	Zj	4	8	4/5	0	48
	Cj-Zj	2	0	-4/5	0

PIVOT COLUMN

operation	basis	X1	X2	S1	S2	value	ratio
Cbi	Cj	6	8	0	0
8	X2	0	1	1/5	-1/4	2
6	X1	1	0	-1/5	1/2	8
	Zj	6	8	2/5	1	64
	Cj-Zj	0	0	-2/5	-1