Optimization Technique LAB
ASSIGNMENT 4(Computation of initial simplex table)
Consider the following linear programming, which can be solved by SIMPLEX
method:
Conditions are: All the constraints should be ≤ type. All bi ≥ 0, i = 1, 2, ..., m.
All xj ≥ 0, j = 1, 2, ..., n.The objective function should be maximization type.
(P):
max c1 x1 + c2 x2 + ... + cn xn
subject to
a11 x1 + a12 x2 + . . . a1n xn ≤ b1
a21 x1 + a22 x2 + . . . a2n xn ≤ b2 (1)
...................
....................
am1 x1 + am2 x2 + . . . amn xn ≤ bm , m≤n
All xj ≥ 0.
The standard form is:
max c1 x1 + c2 x2 + ... + cn xn + 0.xn+1 + 0.xn+2 + ... + 0.xn+m
a21 x1 + a22 x2 + . . . a2n xn + xn+2 = b2
...................
....................
am1 x1 + am2 x2 + . . . amn xn + xn+m = bm
All xj ≥ 0, j = 1, 2, ..., xn+m .
Notation:
• Xj = (p1j , p2j , ..., pmj )T is the j th column of this system. For all i =
1, 2, ..., m, pij = aij if j ≤ n, pij = 1 if j > n, j = n + i and pij = 0 if
j > n, j ̸= n + i
• b = (b1 , b2 , ..., bm )T column vector.
• Basis B. This is a row vector of basic variables. In this standard form it
is (xn+1 , xn+2 , ..., xn+m ). The basis will change in every iteration of the
simplex table, which will be used later.
1
• XB = (.....)T is a column vector, whose components are the value of basic
variables, which you will get after substituting nonbasic variables as zero
in every iteration. In the standard form, XB = (b1 , b2 , ..., bm ). This will
change in other iterations later.
• N B is the vector of nonbasic variables. This will change in other iterations.
In the standard form N B = (x1 , x2 , ..., xn ). The value of every nonbasic
variable is zero.
• C = (C1 , C2 , ..., Cn , Cn+1 , Cn+2 , ..., Cn+m ), is a row for coefficients of basic
and non-basic variables in the objective function.
• CB is the column vector, whose components are the value of cj corre-
sponding to basic variable xj , i.e, xj ∈ B and CN B is the vector of the
value of cj corresponding to non-basic variable xj i.e xj ∈ N B.
• ∆j = zj − cj = CB
T
Xj − cj , j = 1, 2, ..., n + m
C1 C2 ... Cn Cn+1 Cn+2 ... Cn+m
XB CB X1 X2 ... Xn Xn+1 Xn+2 ... Xn+m b
xn+1 cn+1 a11 a12 ... a1n 1 0 ... 0 b1
xn+2 cn+2 a21 a22 ... a2n 0 1 ... 0 b2
.. .. .. .. .. .. .. .. .. .. ..
. . . . . . . . . . .
xn+m cn+m am1 am2 ... amn 0 0 ... 1 bn
T
XB CB ∆1 ∆2 ... ∆n ∆n+1 ∆n+2 ... ∆n+m
Table 1: Simplex Table
T
∆j = CB Xj − Cj
Initial SIMPLEX table: ASSIGNMENT:
Q 1. Develop code in C/C++ to write the given LPP, which is suitable for the
simplex method, to standard form and print the initial table, b, B, CB , XB , ∆j
for every j = 1, 2, ..., n + m.
Q2. Consider the following LPP and verify your code for the following output:
(a)b, B, CB , XB , ∆j for every j
(b)Initial Table
M inimize 3x1 + 2x2 − 4x3 − x4
subject to
3x1 − x2 + 2x3 − 5x4 ≤ 10
3x1 + 2x2 − x3 + x4 ≤ 4
3x1 + 2x2 − 3x3 + 5x4 ≤ 5
x1 , x2 , x3 , x4 ≥ 0
Standard form;
M aximize − 3x1 − 2x2 − −4x3 + x4
subject to
3x1 − x2 + 2x3 − 5x4 + x5 = 10
3x1 + 2x2 − x3 + x4 + x6 = 4
3x1 + 2x2 − 3x3 + 5x4 x7 ≤ 5
x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0
b = (10, 4, 5)T
B = (x5 , x6 , x7 )T
XB = (10, 4, 5)T
CB = (0, 0, 0)T
∆1 = 3, ∆2 = 2, ∆3 = −4, ∆4 = −1, ∆5 = 0, ∆6 = 0, ∆7 = 0
2
−3 −2 4 1 0 0 0
XB CB X1 X2 X3 X4 X5 X6 X7 b
x5 0 3 −1 2 −5 1 0 0 10
x6 0 3 2 −1 1 0 1 0 4
x7 0 3 2 −3 5 0 0 1 5
T
XB CB = 0 3 2 −4 −1 0 0 0
Table 2: Simplex Table
