Optimization (Linear Programming) - Operations Research

Operations Research topic.

1. Water Resources Development and Management

Optimization
(Linear Programming)

CVEN 5393

Mar 7, 2011

2. Acknowledgements
e Dr. Yicheng Wang (Visiting
Researcher, CADSWES during Fall
2009 - early Spring 2010) for
slides from his Optimization
course during Fall 2009
* Introduction to Operations

Research by Hillier and Lieberman,
McGraw Hill

3. Today's Lecture

* Simplex Method
— Recap of algebraic form
- Simplex Method in Tabular form

Simplex Method for other forms
— Equality Constraints

— Minimization Problems

(Big M and Twophase methods)

Sensitivity / Shadow Prices

+ Simplex Method in Matrix form
- Basics of Matrix Algebra
- Revised Simplex

Dual Simplex

+ R-resources / demonstration

4. SIMPLEX METHOD
(MATRIX FORM)
MATRIX ALGEBRA BASICS
REVISED SIMPLEX

5. Matrices and Matrix Operations

A matrix is a rectangular array of numbers. For example

is a 3x2 matrix (matrices are denoted by Boldface Capital Letters)

In more general terms,

aı an ain
qa |e a Gan | _ lay
Amı Am2 Ginn
is an m X n matrix, where aj), .. . , dy represent the numbers that are the elements of this

matrix; | is shorthand notation for identifying the matrix whose element in row i and column j
is aj for every i = 1,2,...,m and j=1,2,...,n.

6. Matrix Operations

Let A = llayl and B = lb. be two matrices having the same number
of rows and the same number of columns.

Matrices A and B are said to be equal (A = B) if and only if all the corresponding

elements are equal (a; = bj for all i and j).

To multiply a matrix by a number (denote this number by k )

kA = |ka;|

For example,

To add two matrices A and B

3
A+B=|a,+ bj For example, F

1 6
0 -9
3 2 0
et]

HE

7. Subtraction of two matrices

A-B=A+(-DB,
so that

A — B = lla;; — bjjl.
For example,

ISERE

Matrix multiplication

mm

Matrix multiplication AB is defined if and only if the number of columns of A equals the num-
ber of rows of B.

Thus, if A is an m X n matrix and B is an n X matrix, then their product is

AB =

n
2 ix Dy
k=1

where this product is an m X s matrix. However, if A is an m X n matrix and B is an r X s
matrix, where n # r, then AB is not defined.

8. To illustrate matrix multiplication,

Al Fa 3 1(3) + 2(2) 1(1)+2(5) zu
0 E sk 4(3) + 0(2) 4(1)+0(5)|=|12 4].
3 2(3)+3(2) 2(1) + 3(5) 2 17

Nh

On the other hand, if one attempts to mutliply these matrices in the reverse order, the resulting

product
3 1 1 2
4 0
E 3 2 3
is not even defined.
Even when both AB and BA are defined,
AB + BA

in general.

Matrix division is not defined

9. Matrix operations satisfy the following laws.
A+B=B+A,
(A+B)+C=A+(B+C),
A(B + C) = AB + AC,
A(BC) = (AB)C,

The relative sizes of these matrices are such that the indicated operations are defined.

Transpose operations

This operation involves nothing more than interchanging the rows and columns of
the matrix.
Thus, for any matrix A = |la;|, its transpose A7 is

AT = [lal

2 Di
A=|1 3], then A7= > de -
A 0 a 3 ©

For example, if

10. Special kinds of matrices

Identity matrix

The identity matrix Tis a square matrix whose elements are Os except for Is along
the main diagonal. ( A square matrix is one in which the number of rows is equal to

the number of columns).

IA = A = AI

where I is assigned the appropriate number of rows and columns in each case for the

multiplication operation to be defined.

11. Null matrix

The null matrix 0 is a matrix of any size whose elements are all Os .

0 0 0
auf 9 +0
0.0 - 0

Therefore, for any matrix A,
A+0=A, A-A=0, and 0A = 0 = AO,
where 0 is the appropriate size in each case for the operations to be defined.

12. Inverse of matrix
(a) If A is nonsingular, there is a unique nonsingular matrix A”, called
the inverse of A, such that AA~' =I =A7'A.

(b) If A is nonsingular and B is a matrix for which either AB = I or
BA =I, then B= A !.

(c) Only nonsingular matrices have inverses.

To illustrate matrix inverses, consider the

13. Vectors

A special kind of matrix that plays an important role in matrix theory is the kind that has either a
single row or a single column. Such matrices are often referred to as vectors. Thus

: == x]
is a row vector, and
x
x (We use boldface lowercase letters
x=|.

to represent vectors)
An

is a column vector.

A null vector 0 is either a row vector or a column vector whose elements are all Os, that is.

O= 10,0) sag]

One reason vectors play an important role in matrix theory is that any m X n matrix can be
partitioned into either m row vectors or n column vectors, and important properties of the matrix
can be analyzed in terms of these vectors.

14. Partitioning of matrices

Up to this point, matrices have been rectangular arrays of elements, each of which is
a number. However, the notation and results are also valid if each element is itself a
matrix.

For example, the matrix

41 Ay 4%
ron |
da Ay la
may be written as

a. a
A=[C, C, G)] where C,= | “| G= | a

Azı 22
dis
and = |
423

R,
ale] where R,= [4 42 43] and Ry = [ax an a]
2,

or as

15. or as

A=[A, Aj]
where
4, Ae 413
A, = and A, =
da Age, 433
or where - E
11 12 13
A, = and A, =
a Az loz

The process of dividing a matrix into smaller matrices, or submatrices, is
called partitioning and is usually denoted by a dotted line. The four
partitions described would be denoted respectively as follows:

ba i : =]
Azı H i Ga

% Ne i | Ge i
de Ag! ¡Az Ga
Matrix operations can then be performed with matrices whose elements

are matrices, provided the rules of operation are valid for the given
matrix and for the resulting submatrices.

16. Example : Calculate AB, given

4 3
6 © 1
A= and B=j0 1
21 ©
1 0
Solution. Partition the two matrices:
4 3
6:0 1 oo B,
A= H =[A, Az] and B=|0 1|=
2110 B,
1 0
where
A 5 A as B [4 3] d B wa
= la = lo = , an =
le a Ho | = org
then
B,
AB =[A, As] [ ] = A,B, + A,B,
B,
and
6 0 po 14 24 18 L ©
AB = [4 31+ = Ca
2 1 01! © 8 6 o 1

17. Matrix Form of Linear Programming

Original Form of the Model Augmented Form of the Model

Maximize Z= 3x, + 5x2 Mini Z=3x+3%,

subject to subject to

a)
=> a

(6)
and

x,=0, forj=1,2,3,4,5.

Maximize Z= ex; Maximize Z=cx,

subject to =>

Ax=b and x20,

here e is the row vec = (6) Caving E 5 ee 3
where e is the row vector € = [€1, Ca, ‚Cal, Where I is the m X m identity matrix

x, b, and 0 are the column vectors and A is the matrix

Sine
x bi 0 di An ‘ Am mil
Xn+2

xa ba 0 da da “dan | +2
x=|. |. b=| |, 0=|. À = Xs :

Me bn 0 Ami Amr Ann Xnt+m.

18. Maximize Z=cx, Maximize Z=ex,

subject to =>
‘ x x
Ax =b and x=0, (A, 1] = = b and 4 =0

s

subject to

where e is the row vector € = [c;, C2,...., Cpl,
x, b, and 0 are the column vectors and A is the matrix

where I is the m X m identity matrix

x by 0 an da ay Anti
y 1% — by EM 0 A = a * Gin x= En+2

Xn bn 0 Amı Am2 °°" Amn Xn+m

Maximize 1 0 | 0

subject to c= [3,5], [A 1]=10 2: 0

ay 3 2} 1

19. Solving for a Basic Feasible Solution
For initialization,

= TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem
Maximize Z= cx, Coefficient of:
Basic Right
Bat Iteration — Variable | eq. | z | x x x x x | Side
SURES ne zZ (0) 1 -3 = o o 0 o
a a) o El 6 1 0 o 4
x x o “ @ | o | ol 0 1 o az
pan] ]-» ao | Jee n 18 [0 | HE
x Es
Si z @ | 1 | -3 o. 0 3 o 30
For any iteration, 1 # oo" ce : à | 4
22 (2) o o 1 o 2 0 6
e x eo |» | BL oe 1 le
Maximize Z=cgXg FCyXy
E © |: o o 0 3 1 36
subject to & wlel@ . A ı 1] 2
2
1
x x x apo o 1 0 + o 6
[B,N] =b and "20 x ojo i o. 0 a hi 2
Xy Xy J 3 3
By By ‘** Bim Na Na Nin Xai Xu
. ss N, c x
Bi Ba Ba 0 Bam | y= Na Na on = Xo x= E
Bm Bm2 °** Bmm Nm Nm2 Nin “Bm An

20. Solving for a Basic Feasible Solution

For initialization, Maximize
subject to

[A, I] |

xX
X

s

Z = cx,

=b an |

“o
Xs

For any iteration,

Maximize Z=CgXg Fy Xy
subject to
0505 =b and >| =0
Xy Xy
By, By Bim

%=x=T!b=b
Z=cgl'b=cgb

mn) Z = Cp Xp + CyXy = Cp Xp = Cp BD

Bx, + Nxy =b
Bx, = b - Nxy

Xp =Bb-BINxy "5% Z =cp Bb
Xp = Bb

y

Xp = Bb

Xai <u

Xp An
= X.=|":

XBm vn

21. Example

= TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

contient of
Base right
ei le Fle e a a a | Oe
4 [ololi à 2
EI a had
z Io lıls o »
A » a |o} fm o 4
» |@]o| fof à E
% @ | o | BD ra]
z lolo o Pr
« |wlel a . 5
2
» |a@lolo : é
» lo lol » 2
Iteration 1
5 1 0 0
s=|n|, B=|0 2 Of,
ig 0 2 1
5] fo 04 [4 4
so[|=|0 4 0||12|=|6|.c,=10,5,0) so Z=[0,5,01| 6 |=30.
as} lo -1 dle] [6 6

1 0/1 00
e=13,5], [AM =/]0 2/0 1 0
3 210 © 1
4 X
b=|12 [7] > xa
x
1 Xs
Xp=x=I'b=b Xp =B"b
Z=cgl'b=cgb Z=c¿B"b
Iteration 0
% 100 x3 1 0 0|| 4 4
x=|x|,B4l0 1 0|=B"Iso[x,[=f0 1 Of} 12] =] 12
x, 001 Xs, 0 0 1JL18 18
4
ey =10,0,0), so Z=(0,0,0)] 12] =0
18

eration 2

z

"

sw

"
cor
EEE we
wor

eve,
I
Dan

2
+ En =[0, 5,3}, ¿usa
2

=36.

22. Matrix Form of the Set of Equations in the Simplex Tableau

TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

For the original set of equations, the

Basle ren rio matrix form is
Gate: eel. | 1: (er = |
z o |] lo ol
P ¿ 1 SiR 3
2 18 E
2 BE |B) FEAF | i ee) Gol
z (0) 1 o 3 0 30
, » lolo E [a
= [els o + ole
% @ |o e] Tia
z Jolilo oo 3 ı|»s er
» [foje[o e 1 + | 2 For any iteration ee
Sime AAA y » |[Z=c,Btb
a |ole|ı eo + 3 = u
Tee ee O |. f cab
T confent of 0 B' ilo A I], 0 B
Iteration | Variable | tq, [2] Orginal Variables | Stack Variables | ‘Ste x
. Alien x 1 B 1 cB"!
0 B!

|

1 cB"!
0 B!

lee

BA

IH
JE 2

0| [1 esBTlA=e eB!
1} o Bo

23. Example 1 o 0 4
1 TABLE 4.8 Complete set ol simplex tableaux for the Wyndor Glass Co. problem 144) eH 7O 210 I Y mel
Coefficient of: 3 0 1 18
Base mon
ss le (Te e = = =] For Iteration 2
z [ol o
o 2 181° 2) : 0
x [815 3 = 5
z (o) 1 30 2
: » [ol 4
» \ols
s |oæle
z lol: : à
» |a@|o
2
: [ol
» [ol ul
L 0
0.0 1 4 —3f|4 2 2
esB-'A —c = [0,5,3]]0 1)-13,5]=[[0,0] B'b=|0 3 Of} 12] =] 6], eB'b=/0,5,3] 6
LI 0 0-4 3JL18 2 2
Z
x
[egB-'A =e] [e¿B7"] zZ E
1 [Ba = el [c¿B7] *2| _|[4
x|= x
0 [a =
x x

24. Summary of the Revised Simplex Method

2 TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem 1, Initialization (Iteration 0)

Basic See Right
A | ZI m a me oe | Se ¡1.0.0
z Jolils 50 o os <= [3,5], [A, ¡O 10
a 5 @ of a mı o ola |
za a o | [o 2 © 1 o 12] ¡O 0 1
= [6 |. ¡CIA EG :
z |olıls o. o 5 o|» 4
$ # mom oo : o o 4 b=|12|, x=
» |@ lol lo] 1 o + of « :
» |@|e| Bo 573 18
z lo 1] o o o 3 1] 3
a lolala à à & 4: 2 :
2 ne Xp =|x4|,B=I=]0 =B!
» |eo jojo 1 © 3 of s
1 1 Xs 0
ns lolelı o o + ¿[2
x] [10
m TABLE 5.8 Initial and later simplex tableaux in matrix form Xg=|x4]=]0 1
Conilidana ot Xs, 00
asc mon L
eration | vane | tg. | Z| original variables | Stuck Varias | ‘Side
o Zz o 1 e o o 4
2 [Um] x : B
«=[0,0,0, so Z=10.0,0112)=0
18
m | 2 To ae alar
Or mo] Er CIS
1 0 ojfio
+ B «GB 'A-c= 2 |. añ
Optimality test: ‘* Eu Ñ $ : 2 B,51=[-3,-5]

25. = TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

2. Iteration 1

Coefficient of: e 5 A ;
eration Vene | eg zT mom =» us| “get Step 1: Determine the entering basic variable
¿gli ge 8 el: Lg ot
o 4 - |
= 1810 | SH eB A e=[0,0,0]0 1 0,0 2 |-[3,5]=[-3,-5]
z olıls 0. o 8 of » 0 0 1113 2
» olelm o : o o | « Lies, BE
' > |elo|bl «io + cols le a a
= Se el So x, is chosen to be the entering variable.
z lolilo oo 3 1]
11 a 5 . ;
2 Po ye ye e's 3 |? Step2: Determine the leaving basic variable
» |alolo 1 o 3 of 6
Loa 1 0 oj[f—0] [-o
» ololı o o [a al dolls Le
oo 1][—2] [-2
3 ug nnd gt a =0 an =2 ap =2
Base = mon
Aeration | Variable | £a. | Z| Original Variables | Sock Variables | sie ‘
: | = ie 7 - | à Ts balas) = balaz =
m [Gam |e x : :
So the number of the pivot row r =2
Any BA CR los : A A
[Uam lo] eta IO Thus, x, is chosen to be the entering variable.

26. Step 3: Determine the new BF solution

X3
The new set of basic variables is Xp = |%
*s,
_ 2
aa 0 1 0 0
To obtain the new B!, y = ls = E=|0 3 0
an 2
ma] | 0 -1 1
Brew = EBoids =
So the new B" is
1 0 Oo}; 1 0 0 1 0 0
Bo? =|6 3 00 1 0; = ]0 3 0
o —1 110 0 1 0: =] 1
a 1 0 olf 4] fa ALE 5 oe at pls te atom
xw=lxl=l0 4 off12}=|o MEA remuer
Xs 0 —1 1]L18 6 © LA [Puelo] À t

my z |o 1] ew tame <a!
m [02 mo BA 8

27. Optimality test:

The nonbasic variables are x, and x,.

1 0 O||1
GBA — e = [0, 5, 0]] 0 3 0110
O =1 1115
arene
cB”! = [0, 5, 0] + —|=
= “I. =

3. Iteration 2

Step 1: Determine the entering basic variable

x, is chosen to be the entering variable.

—|=B, 15 a)

TABLE 5.8 Initial and later simplex tableaux in matrix form

to
o

02m

Right
Side

©

W2...m

os
eb

28. Step 2: Determine the leaving basic variable

1 0 oft — 1 — X3 4
o 4 offo =|o —|. xo =|x,|=|6
o -1 alla — 3 — E 6

The ratio 4/1 > 6/3 indicate that x5 is the leaving basic variable

BUA=

Step 3: Determine the new BF solution

The new set of basic variables is al
et 1
x i E 1 0-4
a
xs = | Xe with y=|-2|= ol. E=|0 1 0
as,
Mi 1 A 0 0 3
— 3

ay
Therefore, the new B" is

1 oO -$]/1 0 0 1 #-4 X3 1 4 -3| 4 2
B'=/0 1 ollo 4 0|/=|0 & Of, x=|x|=10 4 o||12]|=|6
o o jo -1 1 0-4 3 x 0-4 4/18 2

Optimality test:

The nonbasic variables are x, and x.

29. Relationship between the initial and final simplex tableaux

= TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

Coefficient of

music mio Initial Tableau
teration vase | em | 2] » m | he
z lots m: 3: 9|e Row 0: t=[-3, -510,0,010]=[-ei0i0].
3 18 || A 1 0{1 0 0! 4
z lolils o © 3 o | » Other rows: T=|0 2/0 1 0/12] =(AiTiB).
1 ololm oo 1 000 L3 210 0 1118
@|o} fo} 1 o 4 o ;
oo] Bet En fi -e/ 0} o)
z lolıle o © 3 ı|= Tlajirio
, oleo er 303]. ern
A mojo 1 © 4 of «
“ lol o. © + gla Row 0: © = 0,010, 3,11 36)=[2"—ely* iz).
= oo
1 TABLE 5.8 Initial and later simplex tableaux in matrix form omer: neo: 1 jo Asa
Coefficient of: ji o10 -
Basle Right
iteration | variable | Eu [2 | Original Variables | Slack Variables | Side a tLe
0 z lo 1 -e o o ‘Gombinied: Tr -[ a
% (1,2,...,m) | 0 A 1 b
Z=c BA Zt=cBb
* — "rl
m | z lo 1] «sue a [en B's b*=B"'b
xy (012...,m|0 BIA e B'b

(1) = t+ y*T = [y*A — ci y* |
(9) T* = ST = [S*A | S*

y*b]=[cB"A-c ¿0887 ¿487 1b]
¿S*b]=[8 "aj 8" 8]

30. = TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

ne peer er Initial Tableau
eration Verte | Em | Z | m mm mm | Se RowO: t=[-3, -510,0,010]=[-ci0i0).
z Ilelıla a= © sole
° 2 18 || Ben 01,00%
» 10 o 3 LT © y T 18 Other rows: T=|0 2j0 1 0j12[|=[Ailib].
z or o fo 3 of] » 3 210 0 1118
» [o lomo fp]. x,
2 als: ‘combines: [E [0 2
» lolo Boee te ot 7 Prier
z lol: o 0e à | |
» lololo o 1 4 +}: Foriterationl
2
» [ea jojo 1 09. + ol. 1 0 0 5
% olelı o o + 3|2 Sk=Bl=|0 4 0 y*=[0, 5,
0 -1 1
1041-0014
pk =t + y*T = 1-3, -510 0, 0f0)+{0, 3 0jo 240-4 0¡12|=[=3, 0, 50
3 210 0 1:18
10 Of: 01 6 014 1 o f1 0 4
T*=S*T=|0 4 ollo 2:0 1 o:2|=|o 1 lo 4 6
o-1 alla 230 0 1 18 3 0 lo -1 6

30]

31. = TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

Initial Tableau

Covfficiont of:
Basic
teration Variable | en | 7
z [ol
s | mo
$ x a o
E CHR)
z lol:
N » [| mo
» [ajo
» |o|o
z lol:
» [mo
2
x [ojo
= [oo

t* =t + y*T=[-3. -510, 0, 010]+[0,

1 4 -4]1 of 1
T*=S*T=f0 3 ojo 21:0
0) 48 2:30

Row 0: t=[-3, -510,0,010]=[-c1010].
10/11 0 0! 4
Other rows: T=|0 2j0 1 0 3
3 210 0 1118
Combined: [+] = [E | : | ed |
For iteration 2:
1 4-3
S*=Bl=|0 4 0 y*=[0, % 1]
04 4
1 0:100:4
lo 2:0 1 oın]=[0 0, [0, 3, 1} 36)
32:00 1118
oul 4 o o lr 4 -4| 2
0! 12/=/0 1 jo 30 6
1708 1 0 [0-4 43 2

32. DUAL SIMPLEX

33. HUGHES-MCMAKEE-
NOTES\CHAPTER-05.PDF

34. Duality Theory and Sensitivity Analysis

Duality Theory

Primal Problem

Maximize Z= > Gi
subject to
and
20, for f= hereon

Dual Problem

Minimize
subject to
for j= 1,2,
and
y20 fori=1,2..

Primal Problem

Dual Problem

Maximize
subject to
Ax=b

and

2=&

Minimize Yo = yb,
subject to
yA=c
and
y=0

2 TABLE 5.8 Initial and later simplex tableaux in matrix form

Coefficient of:

Basic Right

Iteration | Variable | Eq. | Z | Original Variables | Slack Variables | Side
o 2 [0 1 -e o o

» [@2...,m|o A 1 b

Any 2 (0 1 cB Ane CA «bb

x (02..m|o BIA [2 Bb

35. TABLE 6.1 Primal and dual problems for the Wyndor Glass Co. example

Primal Problem
in Algebraic Form

Maximize Z = 3x; + 5%,
subject to

my <4

3x + 2% < 18

and x20, x2>0.

Primal Problem
in Matrix Form

Dual Problem
Dual Problem

in Algebraic Form

Minimize W= 4y, + 12y, + 18ys,
i subject to
n +3p=3

Dp + 2ys25

Dual Problem
in Matrix Form

Maximize z= (3, 51[ "|
subject to

BIHHE

MEE!

;
same wenn]

18,
subject to

10
Dr ya ya [o 2|=13, 5)
32

and

Li ver ys] = [0, O, 0].

TABLE 6.2 Primal-dual table for linear programming, illustrated by the Wyndor
Glass Co. example

==
Br:
za
7 En o om | sn [E 258
gora a am | <% |ÉSÉSE
| Ele a om | <a [3 828
i Hi E
‘Objective Function

(b) Wyndor Glass Co. Example

x Xz
n 1 0 < 4
Ya 0 2 <12
Y 3 2 < 18
vl vl
3 5

36. Initial Tableau

Row 0: t=[-3, -510,0,010]=[-e1 010).
10/1 0 0! 4
Other rows: 0 2/0 1 o!12|-{ai
3 210 01118
, Y_fejojo
contas: []-[[219.
Final Tableau
Row 0: # = (0,010, 3, 1136) =[z*—ely*! zZ").
Ooj1 3352
Other rows: T=lo 1jo 3 Eb =[A* | S* ib".
1 uta + 412
E ale]
Combined: tial at is pl:

» TABLE 5.8 Initial and later simplex tableaux in matrix form.

Coefficient of:
Basic Right
Iteration | Variable | Eq. | Z | Original Variables | Slack Variables | Side
o z |o 1 e o o
x |(02%.. mo A 1 b
Any £ (0) 1 «BAC CR Bb
x |02%.m|o| “ETA rT |8%

Lu
for J = Lies

Dual Problem

= Soy,

Minimize

subject to

DE

and

for j= 1,2,...,

‚m.

2; 7 €; isthe
surplus variable for
the functional
constraints in the
dual problem.

37. TABLE 6.4 Notation for entries in row 0 of a simplex tableau

Coefficient of:

Basic Right
Iteration | Variable | Eq.| Z| x: x Ky Kern rez Xn+m | Side
Any zZ (0) A-G 2 yı Ya Ym

TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

Basic

Coefficient of:

Right

TABLE 6.5 Row 0 and corresponding dual solution for each iteration
for the Wyndor Glass Co. example

eration _varible | ee [Zz] mm | Side
z oros 0 o ol» A la TT
o s 10) o 1 o 1 9 2 4 Primal Problem Dual Problem
x @ | o | poe Y o | 32]
= 241117 y » 2 1 | 78 iteration Row 0 In Ya Ys | n-G 2-0 |W
z lolıla © © 5 o|»
5 % wolf o 1 0 of «
» |@fo| fl 1 o + of «
Pi a |» | BA 23
z lolıle o o E
2 » mpofjo on 3 à | 2 Ifasolution for the primal problem and its
a mlolo ve 3 o | * corresponding solution for the dual problem
1 4 ñ mbes
# [es] À 4. € 3 3 | * are both feasible, the value of the objective

function is optimal.

If a solution for the primal problem is feasible and the value of the objective function is not optimal
(for this example, not maximum), the corresponding dual solution is infeasible.

38. Summary of Primal-Dual Relationships

Weak duality property: If x is a feasible solution for the primal problem and y
is a feasible solution for the dual problem, then

cx = yb.

Strong duality property: If x* is an optimal solution for the primal problem
and y* is an optimal solution for the dual problem, then

ex* = y*b.

Complementary-solutions property: At each iteration, the simplex method
simultaneously identifies a CPF solution x for the primal problem and a comple-
mentary solution y for the dual problem (found in row 0, the coefficients of the
slack variables), where

ex = yb.
If x is not optimal for the primal problem, then y is not feasible for the dual
problem.

39. Summary of Primal-Dual Relationships
Complementary optimal solutions property: At the final iteration, the sim-
plex method simultaneously identifies an optimal solution x* for the primal prob:
lem and a complementary optimal solution y* for the dual problem (found in
row 0, the coefficients of the slack variables). where

ex* = y*b.
The y; are the shadow prices for the primal problem.

Symmetry property: For any primal problem and its dual problem, all relation
ships between them must be symmetric because the dual of this dual problem i:
this primal problem.

Duality theorem: The following are the only possible relationships between the
primal and dual problems.

1. If one problem has feasible solutions and a bounded objective function (anc
so has an optimal solution), then so does the other problem, so both the weak
and strong duality properties are applicable.

2. If one problem has feasible solutions and an unbounded objective functior
(and so no optimal solution), then the other problem has no feasible solutions

3. If one problem has no feasible solutions, then the other problem has either nc
feasible solutions or an unbounded objective function.

40. Complementary basic solutions property: Each basic solution in the primal
problem has a complementary basic solution in the dual problem, where their
respective objective function values (Z and yo) are equal. Given row 0 of the
simplex tableau for the primal basic solution, the complementary dual basic

© TABLE 6.4 Notation for entries in row 0 of a simplex tableau

Coefficient of:
Basic Right
Iteration | Variable | Eq. | Z | x x2 ... Xn Xn+t Xn+2 ** Xnim | Side
Any Z (0) |1|29 4 2-0 an Yi Ya we Ym w

41. Complementary slackness property: Given the association between variables
in Table 6.7, the variables in the primal basic solution and the complementary
dual basic solution satisfy the complementary slackness relationship shown in
Table 6.8. Furthermore, this relationship is a symmetric one, so that these two
basic solutions are complementary to each other.

= TABLE 6.7 Association between variables in primal and dual problems

Primal Variable Associated Dual Variable
(Decision variable) x, 2)~ 6 (surplus variable) j= ‚n
Any problem (Slack variable) xa yı (decision variable) i= im
Decision variables: xy 2, — & (Surplus variables)
X2 2-@
Wyndor problem Slack variables: x yı (decision variables)
x Ya
xs Y

TABLE 6.8 Complementary slackness
relationship for complementary
basic solutions

Primal Associated
Variable Dual Variable
Basic Nonbasic (m variables)

Nonbasic Basic (n variables)

42. Maximize Z = 3x, + Sx,

subject to Oh nig Mainz = an + Su
Dos 0.9 Dr
Primal Problem | ¿, 2x Sn + 20 = 18 MEL
420 #20

(6) 3x, + 2m

and 0.6)

%=0, forj=1,2,3,4,5

Minimize W=4y, + 12y2 + 18ys,

subject to

Dual Problem ara
2ÿ2 + 2522 02 =0

0.0)

and
Ni =O, y2=0, ys =O, 2:-C1>0, 22 — C2=0

Table 6.9 Complementary Basic Solutions for the Wyndor Glass Co. Example

Primal Problem Dual Problem

No Basic Solution Feasible? Feasible? Basic Solution

(4,6, 0,0, -6) S (3. 3, 0, 0,0)
(0,9, 4, —6, 0) N (0, 0, 3, 8, 0)

AT (0, 0,4, 12, 18) s (0.0,0, =3, =5)
E a (4,0, 0, 12,6) s (3.0,0.0,-5)
E 3 (6,0, —2, 12,0) N (0,0, 1,0, 3)
m7 (4,3,0,6, 0) (3, 0,3,0, 0)
Ba (0, 6,4, 0, 6) (0.3. 0, =3, 0)
E 6 (2,6,2,0,0) s (0,3, 1,0, 0)
7
nS

43. (Complementary optimal basic solutions property: Each optimal basic solu-
fion in the primal problem has a complementary optimal basic solution in the
dual problem, where their respective objective function values (Z and yo) are
Equal. Given row 0 of the simplex tableau for the optimal primal solution, the
Komplementary optimal dual solution (y*,z*— e) is found as shown in
Mable 6.4.

TABLE 6.4 Notation for entries in row 0 of a simplex tableau

Coefficient of:

Right

Iteration | Variable | Eq.

44. Con Te Me Compare, e Persan aired reproduction ely
TABLE 6.10 Classification of basic solutions

Satisfies Condition

for Optimality?
Yes No
Optimal Suboptimal
Feasible? : 5 ar
No uperoptimal Neither feasible nor superoptimal a à
Neither feasible nor Neither oe nor
superoptimal superoptimal

Table 6.9 Complementary Basic Solutions for the Wyndor Glass Co. Example

Primal Problem
Basic Solution Feasible?

Dual Problem

No: Feasible? Basic Solution

1 (0, 0, 4, 12, 18) Yes 0 (0,0, 0, —3, -5)
2 (4,0, 0, 12, 6) € (3,0, 0,0, —5)

Suboptimal 3 (6,0, —2, 12, 0) (0.0.1.0, 3) | Superptimal
4 (4,3, 0,6, 0)
5 (0. 6, 4, 0, 6) No (05030

Optimal 6 Q 0,0) (0,3, 1,0, 0) Optimal
T 1% 5, 0,0, —6) (3, 3,0, 0, 0)

| 8 (0,9, 4, -6, 0) (0, 0, 3, 8, 0) L

Superoptimal Suboptimal

45. TABLE 6.11 Relationships between complementary basic solutions

Both Basic Solutions

Primal Basic Complementary

Solution Dual Basic Solution Primal Feasible? Dual Feasible?
Suboptimal Superoptimal Yes No
Optimal Optimal Yes Yes
Superoptimal Suboptimal No Yes
Neither feasible Neither feasible No No

Nor superoptimal nor superoptimal

Primal problem uel problem

Bagua | ve E

Superoptimal Suboptimal

(optimal) 2* We (optimal)

Suboptimal Soperoptimal

46. Adapting to Other Primal Forms

Primal Problem Dual Problem

Maximize Z= Minimize yo

subject to subject to

fon S aye

and
20, forj=4,2...,0

y>0, fori=1,2,....m

TABLE 6.12 Conversions to standard form for linear programming models

Nonstandard Form Equivalent Standard Form

Minimize Z Maximize (-Z)

n
=$ ax < -b;
A

x; unconstrained in sign

47. TABLE 6.13 Constructing the dual of the
dual problem

Dual Problem

Converted to Standard Form

Minimize W = yb,

subject to
yA=c
and
y=0.

Maximize (-W) = -yb,
subject to

=yA = -c
and

y=0.

Converted to
Standard Form

|

Its Dual Problem

Maximize Z=cx,

subject to
Ax=b
and
x=0.

Minimize (-Z) = -cx,
subject to

Ax = -b
and

x=0.

48. TABLE 6.14 Corresponding primal-dual forms

Primal Problem
(or Dual Problem)

Dual Problem
(or Primal Problem)

Maximize Z (or W) Minimize W (or Z)
Constraint i: Variable y; (or xj):

= form € > y=0

= form € > Unconstrained

= form € > y <0
Variable x; (or yj): Constraint j:

x=0 € > = form
Unconstrained & > = form

x =0 € > = form

Primal Problem

Maximize Z= cx,
subject 0

sb fori=1,2,

forj=1,B...,

m

Dual Problem

Minimize

subject to

Fameac forj=1,2....n

49. 7
max 2 = > 05%;

i=

subject to

DD aux; = bj, i= 1, 2,000, m

Fo

M 20, j—1,2,...,n

y; : dual variables corresponding to (1)

Y : dual variables corresponding to (2)

m

minw = Si by; + > (5,37)
i=1 ima

subject to

> ay + > Cas) 2 ci, 7= 1,2, n

rer i=1

Yo y 20, 1=1,2,0-..m

7
maxz = > CA

subject to
D ait bis i—ls2s,m (1)
Veja < —b, i=1,2,--.,m (2)

La =
ser

420, j—1,2,-..,n

m

MAC)

¿=1

min w =

m

Day) Soi, FH 1,2;

y;: unconstrained in sign

ren]

=
Dam Sei, FAA, 2 +850

ini

50. = ”
max 2 — D cm; max z= >) ct;
: j=í j=1
subject to subject to

Y Gx; bi, i=1,2,..,m 5 a ir
i=1 i=)

x20, 7=1,2, #20, ¿=1,2,-*

1? : dual variables corresponding to (2 ,
yi p g to (2) 7, SS yl!

2
m

mine = > (by?) min 1 = > by;

fet
i=1

subject to

se ay) Cin Im 1,2)+-,8 ¥ <0 ,71=1,2,
d=1

2) ay; > 65 J 15 23°,

yi 0, i= 1, 250+) m

51. Primal Problem
(or Dual Problem)

TABLE 6.14 Corresponding primal-dual forms

Dual Problem
(or Primal Problem)

Maximize Z (or W)

Minimize W (or Z)

Constraint i:

Variable y; (or xj):

= form <

> y=0

form <

> Unconstrained

= form €

> y <0

Variable x; (or yj):

Constraint j:
> = form

x=0 €
Unconstrained &

> = form

x <0<

Primat Problem

Maximize

subject 10

ys sb, tori=1,2....m

and

for j= 1,2,

y=0,

> = form

Dual Problem

subject to

Dame ferj=l,d....n

and

52. TABLE 6.15 One primal-dual form for the radiation therapy example

Primal Problem

Dual Problem

Maximize —Z= —0.4x, — 0.5x2,

subject to

Minimize W= 2.7yı + 6y2 + 6y3,

0.3x + 0.1x2 = 2.7

0.5x + 0.5x;

0.6x + 0.4x2 = 6 <

and

subject to

>y=0 (8)
> yz unconstrained in sign (0)
> y=0 (8)
and

x=0 €

> 0.3y, + 0.59 + 0.613 > -0.4 (S)
> 0.1y, + 0,5% + 0.413 => —0.5 (5)

x=0 €

TABLE 6.16 The other primal-dual form for the radiation therapy example

Primal Problem

Dual Problem

Minimize Z=0.4x, + 0.5%,

subject to

Maximize W-=2.7yi + 6y3 + 6ys,
subject to

> yi =O

0.3x) + 0.1x2 = 2.7

0.5x + 0.5x2=6 €

> y3 unconstrained in sign

0.6x + 0.4x2=6 €

and

> y=0
and
> 0.3y{ + 0.593 + 0.6y, = 0.4

> O.1yj + 0.57; + 0.4y3 = 0.6

53. TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

Dual Simplex Method conan of som
eration variable | ea | 2 | x xs | Side
= o|lıla = © o o | o
$ E @ | o | 4 fo 4 o ol
Can eH Campa PORE rc 3B Pi @ | 2 | cp 1 ofa]
TABLE 6.10 Classification of basic solutions ‘
2 olıla © © 8 o | »
Satisfies Condition 7 » olelm o +1 o o | 4
for Optimality? m alo|ll ı o 4 o | «
% @ |o | E 1 a]
u) No z lo || o o o 2 1 | x
Yes | Optimal Suboptimal % mofo o + } 1 | 2
Feasible? 2 A
No | Superoptimal Neither feasible nor superoptimal ” ojojo 1 © 2 opos
„ |elelı 0° o + +4|2

Table 6.9 Complementary Basic Solutions for the Wyndor Glass Co. Example

Primal Problem
Basic Solution Feasible?

No.
1 (0,0,4, 12, 18) 0 (0, 0, 0, —3, —5
2 (4,0,0, 12, 6) 3,0, 0,0, 5)
Suboptimal 3 (6,0, —2, 12,0) (0,0,1,0,-3) Superptimal
T 4 (4,3,0,6,0) (4, 0,4, 0, 0) 1
5 (0, 6, 4, 0, 6) (03.0 —3 0)
Optimal 6 (2. 6, 2, 0. 0) (0. #, 1, 0, 0) Optimal
7 (4, 6,0, 0, —6) (3.3,0,0, 0)
J 8 (0,9, 4, 6, 0) L
Superoptimal Suboptimal

54. Simplex Method : Keep the solution in any iteration suboptimal

( not satisfying the condition for optimality, but the condition for
feasibility).

Dual Simplex Method : Keep the solution in any iteration

superoptimal ( not satisfying the condition for feasibility, but the
condition for optimality).

If a solution satisfies the condition for optimality, the coefficients
in row (0) of the simplex tableau must nonnegative.

If a solution does not satisfy the condition for feasibility, one or
more of the values of b in the right-side of simplex tableau must
be negative.

55. 1. Initialization: After converting any functional constraints in > form to =
form (by multiplying through both sides by —1), introduce slack variables as
needed to construct a set of equations describing the problem. Find a basic
solution such that the coefficients in Eg. (0) are zero for basic variables and

subject to nonnegative for nonbasic variables (so the solution is optimal if it is feasible).

Yi + 3y3 Go to the feasibility test.

Summary of Dual Simplex Method

Maximize Z=-4y,-1

riables are nonnega-
tive. If they are, then this solution is feasible, and therefore optimal, so stop.
Otherwise. go to an iteration.

3, Iteration:

nk Coefficient of: hight Step 1 Determine the leaving basic variable: Select the negative basic

Iteration Variable [Eq. | Z| y ym yo ys | Side Variable that has the largest absolute value.

Step 2 Determine the entering basic variable: Select the nonbasic vari-

2y3 + 2yz 2. Feasibility test: Check to see whether all the basic
h20, 220,

z olılı m 18 o of o E a ;
0 7 "Y ola lo 3 1 0 | -3 able whose coefficient in Eq. (0) reaches zero first as an increasing multiple of
» ¡polo fe 2 914 “5 the equation containing the leaving basic variable is added to Eq. (0). This selec-

z lol: 4 o B 0 6 |-30 tion is made by checking the nonbasic variables with negative coefficients in that

1 y» [po f[-1 0 13 1 | -3 equation (the one containing the leaving basic variable) and selecting the one

» |@}o} o 1 Ly 0 + 3 with the smallest absolute value of the ratio of the Eq. (0) coefficient to the
coefficient in that equation

E mM. 5 a ? bs | Step 3 Determine the new basic solution: Starting from the current set of

2 wey) Oy gy 9 Tomy opt equations, solve for the basic variables in terms of the nonbasic variables by

n [ajo 4 1 0 3 4 3 Gaussian elimination. When we set the nonbasic variables equal to zero, each

AAA basic variable (and Z) equals the new right-hand side of the one equation in
Which it appears (with a coefficient of +1), Return to the feasibility test.

56. Sensitivity Analysis

Maximize Z=cx,

Maximize Z= I ga, %
a subject to

Ax=b

subject to

The simplex method already has been used to obtain an optimal solution to a linear
programming model with specified values for the b;, c;, and a,; parameters. To initiate
sensitivity analysis, one or more of the parameters is changed. After the changes are
made, let b;, ©, and a;; denote the values of the various parameters. Thus, in matrix
notation,

b—b, e> 6 A — A,
for the revised model.

57. Initial Tableau

Row 0: t=[-3,-510,0,010]=[-ei0i0].
1 0}1 0 0! 4

Other rows: T=|0 2/0 1 0/12] =[Ailib).
3 210 0 1118

si <;o
comes: — [J- [919
Final Tableau
Row 0: t= (0,010, 3,11 36)=[2"-ciyt 12]

0.011 3352
Other rows: T=jo 1jo 3 je = [A* ES" bt).
1 010 3 312

Combined: E qe + at 151 |.

(1) ti =t + y*T = [y*A — ce! y* io y*b]=[c8'A-c ¿087 ¿c87b]
(2) T* = SET = [S*A | S* | Ss

S* = Bo!

58. Original Model

Revised Model

Maximize Z=[3,5] [;

subject to

Maximize Z=[4,5] ha!
da

subject to

1 0 4 10 | 4
eel) | | EE
AE, 22 pl as
and at

x=0 x=:

1 0 4

c= [4,5] 0 2 b=|24

2 2 18

59. © TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

Coefficient of:

ast Right
Merstion Variable | Eq | 2 [mm | Side
z @ fils s 0 o of o
W a m | o | ft oe | 4
x Q) o i} 2 o 1 o 12]
5 @ |o | te + LI LL
z olıla o o 5 o | x
5 » o|lolm oo 4 o o | 4
o mol fl 1 o 3 o
” @ |o | Br. [el
3
z olılo oo 3 1 |
1 1
, mojo o 4 + Ela
» |@le|o +1 © + of «
1 1
o fol 1 o o + plz
Basic Seaton Right
Variable | Eq | ZI on mm. x | Side
z o]lıl# = o o 0
_ % || ea E 4
E ojo o 2 0 1 of 2%
ES ao] 2 2 Q ‘à 18
zZ (0) 1
Revised final] 43 oo | 0
tableau % @ | 0
x 16) 0

un

oo

toe toe tae

epB7! = [0.5.4 ]| O

we Oe

8
BIA —

[0,5,4]|0

12
3

1 0 4

0 2|, b=|2

22 18
1

Ro

1) — [4.5] = [0,0]

_ 7
&B"'b= [0.5.4] | 12
-3

48

60. Case 1 : Changes in b;

Suppose that the only changes in the current model are that one or more of the b;

, m) has been changed. In this case, the only resulting changes

in the final simplex tableau are in the right side column. '

» TABLE 5.8 Initial and later simplex tableaux in matrix form

Final Tableau

e Coefficient of: pen Row 0: t* =[0, 010, 3, 11 36) =[2"—ely* iz).
Iteration | Variable Eq. Z | Original Variables | Slack Variables | Side 2
5 2 To ; = ri 5 Other rows: 0 | 6| =[ati sti bs).
x |(02...m|o A 1 b 2
Combined:
Any Zz (0) 1 3 "Ae CA cB ib
xs |(02...,m|o BIA B B'b se = B ! y* = GB"!
4 4 7
b= | 12 b=|24| Right side of final row 0: Ze = yeh
Right side of final rows 1,2,...,m: b* = S*b
18 18] “*

61. = TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

Coefficient of: umo
Baste ight ”
AA E EN ie
z o|lıla 5 o o o [o a
6 lo i ft $ 1%
x Q) o i} 2 o 1 o 12]
& | 0 SA
2 olıla o. o 5 o |
4 oloım o 1 0 of «4
æ lolo 1 o + of «
@ | o | BIS Ss |
2 olılo o 36
> w joto o 2
2
joto 1 A
o jols o 2

b=|12| —> b=] 24 Z* = y*b = [0,8 1]| 24] = 54
18 18 18

62. Incremental analysis

Equivalently, because the only change in the original model is Ab, = 24 — 12 =
12, incremental analysis can be used to calculate these same values more quickly.

j= TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

_ fan 0 mm a Eu

= y* = y* | =y* Meration Variable | eq | 2 | om mes | Side

ve y Ab 2 Aba y 12 zZ (0) 1 3 5 o o o o

A ES SS

Ab, 0 z olıls o o 5 o | x

Ab* = S* Ab = S*| Ab, | = S*| 12 ' ES AI à Fle

Ab; 0 x 18) o EJ o o a E) 6]

z olılo © © 3 1 | 3

1-4 , » Jolelo o 1 4 42

y*=[0,8,1] st=|0 4 0 » laleloe 1 © 4 of.

vd 5 wo oo + 3] 2

AZ* = 3(12) = 18, so Z* = 36 + 18 = 54

Abi =412)=4 $6 be Hora G Therefore, the current (previously optimal)

ay je basic solution has become
Ab} = 3(12) = 6, so by =6+6= 12

Abt = -\(12) = —4, so bf =2-4=-2 (X, Xo, X3, Xy, X5) = (72, 12, 6, 0, 0)

63. The dual simplex method now can be applied to find the new
optimal solution.

= TABLE 4.8 Complete set of simplex tableaux for the Wyndor Glass Co. problem

Baste Loetitont of fight TABLE 6.21 Data for Variation 2 of the Wyndor Glass Co. model
iseration variable | ea |Z] = m x | ‘side
zZ ollo + o B o Final Simplex Tableau after Reoptimization
Pr = 34 H
Z 3 Ls 59 sl Coefficient of: Ts
z olıls + © 2 of » Variable || 2] 2 11 xxs | Side
; » ofo|m o : eo ol“
:
= en fo [| ee 2 LS Model Parameter z lolıl$3o oo ¿4
a @ | | Gu 8]
2 olılo oo 3 ‘i 423, @=5 (= » [ofol 10 1 0 0! 4
= E dl on=1, 02=0 3 1
* a lo o & 2 1 3 Aen Eee » [Q|o[73 10 0 3/9
? ES a o o 1 o 3 o 6 =}, a2=2, b=18 x @10!-3 0 0 1 = 6
A æ lol sr o o + +]
2 olıloe o o 3 1 | 36
» m lol o 4 + +le
x æ@ lol eo ı o } o | 2
= aloelı oo y 4 |-2
#
be = 2 +4 Ab,
ES # ie
Ab} = 3(12) = 4, so bj =2+4=6 i"
a 1
: : ==) di = 6 + AD,
Ab3 = 3(12) = 6, so bj =6+6=12 = =
a # Fe
* =2-
Abk = —4(12)=—4, sbi=2-4=-2 b3 =2—gAb,

64. The allowable range of b; to stay feasible
bi =2+4Ab,=0 = 3Ab,>-2= Ab,= -6,
bf =6+4Ab)=0 = ¿Ab,>-6 = Ab, = —12,

bf =2-4Ab,=0 = 2=4Ab Ab< 6.

The solution remains feasible only if

-—6=Ab,=6

bs =12+Ab> mm) 6<b,<18

For any b;, its allowable range to stay feasible is the range of values over which the
optimal BF solution (with adjusted values for the basic variables) remains feasible.
(It is assumed that the change in this one b; value is the only change in the model.)
The adjusted values for the basic variables are obtained from the formula b* = S*b,
The calculation of the allowable range to stay feasible then is based on finding the

range of values of b; such that b* = 0.

65. Case 2a : Changes in the coefficients of a nonbasic variable

Consider a particular variable x; (fixed j) that is a nonbaic variable in the
optimal solution shown by the final simplex tableau.

A; is the vector of column j in the matrix A.
We have c; — ¢, A, —> A; for the revised model.

== —— 01 dd TABLE 6.21 Data for Variation 2 of the Wyndor Glass Co. model
Model Parameters

1 1
= — A = a=3, @=5 (n=2)
| 0 al a, =1, @2=0, b= 4
3 2 d1=0, a22=2, b,=24
au=3, as2=2, b=18

We can observe that the changes

lead to a single revised constraint Final Simplex Tableau after Reoptimization
for the dual problem. Basic Sense Right
y +31 >3 ee Variable | Eq. Z| x x m x Xs | Side
3ÿ3 = 3 — 2y3 =
= => 7 9 5
* & —E z |olıl$3o 0 o ¿|
yı 0, yo = 0, a 3: x |mlolıo 1 0 of 4
3 1
9(8) > 4 x ajo 1 0 o 3| 9
0+2@)24 x @)}O}-3 0 0 1 -1| 6

66. The allowable range of the coefficient c; of a nonbasic variable

For any c;, its allowable range to stay optimal is the range of values over which the
current optimal solution (as obtained by the simplex method for the current model
before c, is changed) remains optimal. (It is assumed that the change in this one c; is
the only change in the current model.) When x; is a nonbasic variable for this solu-
tion, the solution remains optimal as long as z; — c; = 0, where z; = y*A; is a con-
stant unaffected by any change in the value of c;. Therefore, the allowable range to
stay optimal for c; can be calculated as c; = y*Aj.

TABLE 6.21 Data for Variation 2 of the Wyndor Glass Co. model
Model Parameters

(n= 2)
b= 4
b2 = 24
a2=2 b=18

@=5

c¡ =y*A, =[0, 0, 3

Final Simplex Tableau after Reoptimization

oa coutiem of |
c, = is the allowable range to stay optimal. variabie | ea. | 2] x m m | se
z Joli]? 4s
x a) o 1 o 1 o o 4
x @lol 1 0 o $] 9
Ka @G) | 0] -3 o o 1 -1 6