Friday, July 10, 2015

Simplex Method - Maximization Case

Simplex Method - Maximization Case

Consider the general linear programming problem

Maximize z = c1x1 + c2x2 + c3x3 + .........+ cnxn
subject to
a11x1 + a12x2 + a13x3 + .........+ a1nxn ≤ b1
a21x1 + a22x2 + a23x3 + .........+ a2nxn ≤ b2
.........................................................................
am1x1 + am2x2 + am3x3 + .........+ amnxn ≤ bm
x1, x2,....., xn≥ 0
Where:
cj (j = 1, 2, ...., n) in the objective function are called the cost or profit coefficients.
bi (i = 1, 2, ...., m) are called resources.
aij (i = 1, 2, ...., m; j = 1, 2, ...., n) are called technological coefficients or input-output coefficients.

Converting inequalities to equalities

Introducing slack variables to convert inequalities to equalities
a11x1 + a12x2 + a13x3 + .........+ a1nxn + s1 = b1
a21x1 + a22x2 + a23x3 + .........+ a2nxn + s2 = b2
..............................................................................
am1x1 + am2x2 + am3x3 + .........+ amnxn + sm = bm
x1, x2,....., xn≥ 0
s1, s2,....., sm ≥ 0
An initial basic feasible solution is obtained by setting x1 = x2 =........ = xn = 0
s1 = b1
s2 = b2
..............
sm = bm

The initial simplex table is formed by writing out the coefficients and constraints of a LPP in a systematic tabular form. The following table shows the structure of a simplex table.

Structure of a simplex table


  
cj
c1
c2
c3
---
cn
Right Hand Side  
cB
Basic variables
B
x1
x2
x3
---
Sn
Solution values
b (=XB)
cB1
x1
a11
a12
a13
---
a1n
b1
cB2
x2
a21
a22
a23
---
a2n
b2
cB3
x3
a31
a32
a33
---
a3n
b3
---
-----
----
----
-----
---
----
-----
cBm
xn
am1
am2
am3
---
amn
bm
Z
z1
Z2
Z3
---
Zn

cj- zj
  
c1-z1
C2-z2
C3-z3
---
Cn-zn
  

Where:
Cj = coefficients of the variables in the objective function.
cB = coefficients of the current basic variables in the objective function.
B = basic variables in the basis.
XB = solution values of the basic variables(Right Hand Side.
cj- zj = index row.

Source Link : Simplex Method - Maximization Case

Simplex Method

Simplex Method Introduction

Simplex Method is an algorithm for solving the classical linear programming problem; developed by George B.Dantzig in 1947. The simplex method is an iterative procedure, solving asystem of linear equations in each of its steps, andstopping when either the optimum is reached, or thesolution proves infeasible. The basic method remainedpretty much the same over the years, though therewere many refinements targeted at improvingperformance (eg. using sparse matrix techniques),numerical accuracy and stability, as well as solvingspecial classes of problems, such as mixed-integerprogramming.
Basic Terminology - Simplex Method

Slack variable

It is a variable that is added to the left-hand side of a less than or equal type of constraint to convert the constraint into an equality. In economic terms, slack variables represent left-over or unused capacity.

Specifically:
ai1x1 + ai2x2 + ai3x3 + .........+ ainxn ≤ bi can be written as
ai1x1 + ai2x2 + ai3x3 + .........+ ainxn + si = bi
Where i = 1, 2, ..., m

Surplus variable

It is a variable subtracted from the left-hand side of a greater than or equal to type constraint to convert the constraint into an equality. It is also known as negative slack variable. In economic terms, surplus variables represent overfulfillment of the requirement.
Specifically:
ai1x1 + ai2x2 + ai3x3 + .........+ ainxn ≥ bi can be written as
ai1x1 + ai2x2 + ai3x3 + .........+ ainxn - si = bi
Where i = 1, 2, ..., m

Artificial variable


It is a non negative variable introduced to facilitate the computation of an initial basic feasible solution. In other words, a variable added to the left-hand side of a greater than or equal to type constraint to convert the constraint into an equality is called an artificial variable. 

From: Operation Research Simplified