ISBN 978-84-9048-242-1
0214P04
EDITORIAL
UNIVERSITAT POLITÈCNICA DE VALÈNCIA
Ope a ions Resea ch
in business adminis a ion and managemen
Concepción Ma o o Ál a ez
Ja ie Álca az So ia
Concepción Gines a Pei o
Ma ina Segu a Ma o o
The publica ion o his book has been app o ed by he Depa men o Applied S a is ics
and Ope a ions Resea ch and Quali y o he Uni e si a Poli ècnica de València (Spain)
Academic book collec ion
To ci e his publica ion please use he ollowing e e ence: MAROTO ÁLVAREZ, C.,
[e al] (2014) Ope a ions esea ch in business adminis a ion and managemen .
Valencia: Uni e si a Poli ècnica de València
Fi s edi ion, 2014
Au ho s: Concepción Ma o o Ál a ez
Ja ie Álca az So ia
Concepción Gines a Pei o
Ma ina Segu a Ma o o
Co e design by Ca men Llo e
O his edi ion: edUPV / www.lalib e ia.up .es / Re .: 6176_02_01_01
ISBN: 978-84-9048-242-1 (p in e sion)
ISBN: 978-84-9048-241-4 (elec onic e sion)
DOI: h ps://doi.o g/10.4995/REA.2022.617602
h p:// iny.cc/edUPV_ ea
Ope a ions esea ch in business adminis a ion and managemen / edUPV
The euse and edis ibu ion o he con en s is allowed as long as he au ho ship is
acknowledged and he comple e bibliog aphic in o ma ion is ci ed. No comme cial use o
gene a ion o de i a i e wo ks allowed
To ou s uden s: ne e lose he hope o do hings
be e .
Acknowledgmen s
We acknowledge he suppo o he Facul y o Business
Adminis a ion and Managemen o he Uni e si a
Poli ècnica de Valencia in p epa ing his book o
Ope a ions Resea ch eaching.
We also hank S ephen and Dogan o hei in ini e
pa ience wi h he English p oo eading.

5




CONTENTS



CHAPTER 1. THE NATURE AND METHODOLOGY
OF
OPERATIONS
RESEARCH
............................................... 11
1.1. THE ORIGIN AND EVOLUTION
OF
OPERATIONS RESEARCH ........................................................................ 13
1.2. THE NATURE OF OPERATIONS RESEARCH............................... 14

1.3. APPLICATIONS ............................................................................................. 17
1.4. METHODOLOGY OF OPERATIONS RESEARCH ...................... 20
1.4.1. FORMULATION OF THE
PROBLEM
................................................... 20
1.4.2. MODELLING.............................................................................................. 22
1.4.3.
IMPLEMENTATION
................................................................................. 27
1.4.4. DATA............................................................................................................ 30

1.5. SUMMARY ...................................................................................................... 31
1.6. SELECTED REFERENCES ....................................................................... 31


CHAPTER 2. FORMULATING AND SOLVING
LINEAR
PROGRAMMING MODELS:
BASIC
CONCEPTS ............................................................................... 33
2.1. THE PROBLEM: PRODUCTION IN A POWER
PLANT
AND POLLUTION CONTROL ......................................................... 35
2.2. THE MODEL: VARIABLES, OBJECTIVE
FUNCTION
AND CONSTRAINTS ............................................................................. 36
2.2.1.VARIABLES: DIVISIBILITY AND
NONNEGATIVITY
HYPOTHESIS
....................................................... 36
2.2.2.OBJECTIVE FUNCTION AND CONSTRAINTS:
LINEARITY
HYPOTHESIS
.................................................................. 37
2.2.3.GENERAL FORMULATION OF A LINEAR PROGRAMMING
MODEL: CERTAINTY HYPOTHESIS ................................................ 42
2.3. FEASIBLE REGION AND GRAPHICAL SOLUTION ................ 43

2.4. SLACK VARIABLES ............................................................................. 45

2.5. SENSITIVITY ANALYSIS.................................................................... 45
2.5.1. SENSITIVITY ANALYSIS OF THE OBJECTIVE
FUNCTION COEFFICIENTS............................................................
45
2.5.2.SENSITIVITY ANALYSIS OF THE RIGHT-HAND SIDE OF
THE
CONSTRAINTS
.........................................................................
47
6
Ope a ions esea ch in business adminis a ion and managemen








2.6. THE EXTENDED PROBLEM: A NEW VARIABLE ....................... 49
2.7. LINEAR PROGRAMMING MODEL
SOLVING
WITH SPREADSHEET ..........................................................................
50
2.8. LINEAR PROGRAMMING MODEL
SOLVING

WITH OPTIMIZATION SOFTWARE .............................................. 53
2.9. MODELLING: SOME EXAMPLES .................................................. 55
2.9.1. COMMON MISTAKES IN MODELLING .......................................... 55
2.9.2. SOME MODELS OF LINEAR PROGRAMMING ........................... 57
2.10. SUMMARY ............................................................................................. 60
2.11. SELECTED REFERENCES ............................................................... 61
2.12. CASE STUDIES ..................................................................................... 61

CHAPTER 3. GENERAL METHODS OF
LINEAR
PROGRAMMING ..................................................................
69
3.1. BASIC CONCEPTS: CORNER-POINTS AND
BASIC
SOLUTIONS............................................................................................. 71
3.2. THE SIMPLEX METHOD.................................................................... 75
3.2.1. GENERAL CONCEPTS ..................................................................... 75
3.2.2. THE SIMPLEX METHOD BY SIMULTANEOUS
EQUATIONS
....... 75
3.2.3. CRITERIA OF THE SIMPLEX METHOD: ENTERING
A BASIC VARIABLE AND A LEAVING BASIC VARIABLE ...........
78
3.2.4. TABLEAU SIMPLEX......................................................................... 81

3.3. INITIAL BASIC FEASIBLE SOLUTION AND
ARTIFICIAL
VARIABLES. THE TWO-PHASE METHOD ...........................
85
3.4. SIMPLEX ALGORITHM WITH BOUNDED VARIABLES ......... 89
3.4.1. LOWER BOUND
TECHNIQUE
........................................................ 89
3.4.2 UPPER BOUND TECHNIQUE.......................................................... 93

3.5. THE REVISED SIMPLEX METHOD, THE
INTERIOR-POINT
ALGORITHM AND THE OPTIMIZATION SOFTWARE........ 99
3.6. SUMMARY .............................................................................................102

3.7. SELECTED REFERENCES ...............................................................103

3.8. CASE STUDIES .....................................................................................104
7
Con en s




CHAPTER 4. DUALITY AND SENSITIVITY ANALYSIS.................. 111

4.1. THE DUAL PROBLEM AND
PRIMAL-DUAL
RELATIONSHIPS ................................................................................. 113
4.1.1. THE PRIMAL PROBLEM AND THE DUAL
PROBLEM
.................. 113
4.1.2. PRIMAL-DUAL RELATIONSHIPS.................................................... 114
4.2. DUAL SIMPLEX ALGORITHM ........................................................ 116
4.3. SENSITIVITY ANALYSIS OF THE COEFFICIENTS
OF
THE OBJECTIVE FUNCTION ......................................................... 119
4.3.1.
MODIFICATION
OF A CJ
CORRESPONDING
TO A NONBASIC
VARIABLE .......................................................................................... 120
4.3.2. MODIFICATION OF A CJ CORRESPONDING TO A BASIC
VARIABLE ......................................................................................... 121
4.3.3. SIMULTANEOUS
MODIFICATIONS
OF SEVERAL
COEFFICIENTS ................................................................................ 121

4.4. SENSITIVITY ANALYSIS OF THE RIGHT-HAND SIDE
OF
THE
CONSTRAINTS
............................................................................. 123
4.5. PARAMETRIC LINEAR PROGRAMMING ................................... 126

4.6. SUMMARY ............................................................................................... 128

4.7. SELECTED REFERENCES ................................................................. 128

4.8. CASE STUDIES ....................................................................................... 129


CHAPTER 5. INTEGER PROGRAMMING .............................................
137

5.1. INTRODUCTION .................................................................................... 139

5.2. A SIMPLE PROBLEM TO DISTRUST OF ROUNDINGS .......... 140
5.3. SOME APPLICATIONS OF INTEGER PROGRAMMING........... 142
5.3.1. CAPITAL BUDGETING DECISIONS ............................................... 143
5.3.2. SETUP COST
PROBLEM
.................................................................. 144
5.3.3. SITE SELECTION OF INDUSTRIES AND
SERVICES
..................... 146
5.3.4. A DISTRIBUTION PROBLEM WITH NONLINEAR COSTS ............ 147
5.3.5. A PROBLEM OF TRANSPORT ROUTES ......................................... 152
5.3.6. OTHER FORMULATION POSSIBILITIES WITH BINARY
VARIABLES ....................................................................................... 154
8
Ope a ions esea ch in business adminis a ion and managemen






5.4. INTEGER PROGRAMMING
TECHNIQUES:
BRANCH-AND-BOUND ALGORITHMS ........................................ 156
5.4.1.
INTRODUCTION
............................................................................... 156
5.4.2. GRAPHICAL
SOLUTION
.................................................................. 156
5.4.3. SELECTION CRITERIA OF THE
NODE
.......................................... 163

5.5. BRANCH-AND-BOUND TECHNIQUES
AND
OPTIMIZATION SOFTWARE............................................................ 166
5.6. SUMMARY................................................................................................ 168
5.7. SELECTED REFERENCES ................................................................. 168
5.8. CASE STUDIES ....................................................................................... 169

CHAPTER 6. MULTIOBJECTIVE PROGRAMMING
AND
GOAL PROGRAMMING ................................................ 177

6.1. BASIC CONCEPTS: OBJECTIVES, GOALS AND CRITERIA. 179

6.2. MULTIOBJECTIVE
PROGRAMMING
...........................................
180
6.2.1. CONSTRAINTS
METHOD
................................................................. 184
6.2.2. WEIGHT METHOD ........................................................................... 185
6.2.3. OTHER MULTIOBJECTIVE
TECHNIQUES
.................................... 186
6.3. GOAL PROGRAMMING...................................................................... 187
6.3.1. GENERAL STRUCTURE OF A GOAL PROGRAMMING
MODEL
. 187
6.3.2. WEIGHTED GOAL
PROGRAMMING
.............................................. 189
6.3.3. PREEMPTIVE GOAL PROGRAMMING........................................... 191
6.4. SUMMARY ............................................................................................... 195
6.5. SELECTED REFERENCES ................................................................. 195
6.6. CASE STUDIES ....................................................................................... 196

CHAPTER 7. DISCRETE MULTIPLE CRITERIA DECISION
MAKING TECHNIQUES .................................................... 203
7.1. ANALYTIC HIERARCHY METHOD...............................................

205
7.1.1. INTRODUCTION................................................................................ 205
7.1.2. HIERARCHY BUILDING..................................................................... 206
7.1.3. SETTING PRIORITIES........................................................................ 207
Chap e 1. The na u e and me hodology o ope a ions esea ch
15
in ui ions and opinions. I we conside ha echnology is in cha ge o designing sys ems,
physical as well as abs ac , Ope a ions Resea ch is a echnology ha designs abs ac
sys ems ha consis o use ul in o ma ion o he planning, he con ol and he o he
necessa y ac i i ies o manage an o ganiza ion.
Acco ding o Keys, Ope a ions Resea ch is a echnology ha designs abs ac
sys ems, by scien i ic means, o imp o e he e ec i eness o o ganiza ions. The
implica ions o eaching and lea ning Ope a ions Resea ch ake in o conside a ion wo
componen s. On he one hand, o mal means mus be used o each use ul wo king ways,
such as quan i a i e analysis and applica ion o scien i ic me hods. On he o he hand, i
is necessa y o complemen his educa ion wi h he applica ion o he p e ious skills o
eal p oblems. This ex book conside s his app oach as he mos app op ia e in a eas
whe e Ope a ions Resea ch is augh , which a e, Business Adminis a ion and
Managemen s udies.
Robinson (2000) de ines Ope a ions Resea ch as he applica ion o he scien i ic
me hod o imp o e he e ec i eness o ope a ions, decisions and managemen . Robinson
conside s ha one o he easons o he discipline o emain in isible o isible bu no
well unde s ood, is because i has been p ac iced unde di e en names. Besides
Ope a ions Resea ch, o he almos synonymous e ms ha e been used such as
Managemen Science, Decision Technology, Decision Suppo , Policy Science, Sys ems
Analysis (wi h ela i e applica ions o adminis a ion and decisions), Managemen
Technology and Managemen Analy ics. Business Analy ics is ano he ecen name ha
in eg a es desc ip i e and p esc ip i e analy ic me hodologies.
An impo an ea u e o Ope a ions Resea ch is main aining a global pe spec i e on
he p ojec s, analyzing he pa icula p oblems in he con ex in which hey occu . In bo h
he classical and he mos mode n de ini ions o Ope a ions Resea ch he sys em concep
is undamen al. Le us see some examples ha will illus a e his.
Many companies calcula e he uni p oduc ion cos a a machine shop o a p oduc ion
line, aking in o accoun all o he cos s o he esou ces used. The lowe he uni
p oduc ion cos he g ea e he e iciency. This p ocedu e is alid only o p oduc ion
p ocesses ha consis o a single phase and whe e he e is no ouble in selling he p oduc .
When he company has complex p oduc ion p ocesses wi h se e al p oduc s (e.g. ile
companies) and each line p oduces di e en pa s - o en in small ba ches-, which a e
used as inpu s in subsequen phases o he p oduc ion p ocess, his ac s as an incen i e
o he machines o be p oducing all he ime. I he nex p oduc ion line in he
manu ac u ing p ocess does no equi e hese in e media e s ocks immedia ely, he
company will need o s o e hem empo a ily, incu ing a cos o hese in e media e
s ocks ha a e no a ibu ed o he line ha gene a ed hem. The e o e, he p oduc ion
line seems o be e icien , while he company has o deal wi h excessi e cos s caused by
hese in e media e s ocks.

Ope a ions esea ch in business adminis a ion and managemen
16
As we ha e seen in he p e ious example, he ope a ion e iciency o a pa icula
di ision o a company can impai he o e all pe o mance in e ms o objec i es and
goals. The e iciency measu es how well esou ces in a gi en ac i i y a e used. Thus we
can speak o echnical e iciency, which does no need o be he same as economic
e iciency, which maximizes he di e ence be ween e enues and cos s. Howe e , a
company is in e es ed in achie ing i s objec i es, which we can e alua e ia i s
e ec i eness. Tha he se e al pa s o a sys em ope a e e icien ly does no necessa ily
mean ha he whole sys em is e ec i e in achie ing i s objec i es. This is no o say ha
e iciency is con a y o e ec i eness. Real e iciency is measu ed in e ms o he
o e all objec i es o he company. E iciency and e ec i eness a e complemen a y
concep s. In sho , we can say ha e ec i eness deals wi h "doing he igh hing" and
e iciency wi h "doing hings igh " (Daellenbach and McNickle, 2012).
He e is ano he example o illus a e he concep o sys em in Ope a ions Resea ch.
In a company wi h i e depa men s ( aw ma e ials p ocu emen , p oduc ion, ma ke ing,
inance and pe sonnel) ma ke ing p oposes an inc ease in he du a ion o he gua an ee o
one o i s p oduc s o be e compe e. Wha o ms he sys em? Wha o ms he
en i onmen ?
The ma ke ing depa men consis s o dis ibu ion, sales and cus ome se ices. The
company assumes ha ex ending he gua an ee pe iod will inc ease sales. Howe e , hey
also inc ease gua an ee cos s due o added cus ome se ices. The e o e, he sys em o be
s udied could be educed o sales and cus ome se ices (Sys em 1), wi h all o he
ope a ions o he company, cus ome s and compe i o s which o m he en i onmen . The
aim o Sys em 1 is o ind ou he gua an ee pe iod ha maximizes he di e ence be ween
bene i s om sales and gua an ee cos s.
Sys em 1 conside s p oduc quali y as a pa o he en i onmen , bu p oduc quali y
will a ec bo h sales and wa an y cos s. Fo his eason, Sys em 1 could be expanded o
include p oduc ion (Sys em 2). The objec i e o his sys em is o de e mine he op imal
combina ion o p oduc quali y and he gua an ee pe iod o maximize p o i s. Howe e ,
p oduc quali y is also a ec ed by he quali y o he aw ma e ials used, which a e pa o
he sys em 2 en i onmen . Thus Sys em 2 could be expanded u he o include he
p ocu emen o aw ma e ials and o m Sys em 3. Sys em 3 could also be ex ended o
include o he company's p oduc s, i sales o hese p oduc s a e a ec ed by changes in
he gua an ee pe iod o he i s p oduc , leading o Sys em 4.
In Figu e 1.1 we can see how each sys em is included in a la ge one. Wi h his
example we wan o illus a e he ac ha he Ope a ions Resea ch always ies o sol e
he con lic s o in e es wi hin he company, so ha he bes esul o he company in
e ms o i s objec i es is achie ed. This does no mean ha he s udy should always
explici ly conside all aspec s, bu ha he objec i es sough a e ha e o be consis en
wi h hose o he company.
Chap e 1. The na u e and me hodology o ope a ions esea ch
17
Figu e 1.1. Example o ilus a e he sys em concep . Sou ce: Daellenbach e al. 1987.
1.3. APLICATIONS
A e Wo ld Wa II he B i ish as well as he Ame ican a my main ained ac i e
Ope a ions Resea ch eams. As a esul , nowadays he e is a la ge numbe o people called
“mili a y ope a ions esea che s” ha apply he Ope a ions Resea ch app oach o na ional
de ense p oblems. Ope a ions Resea ch is also widely used in o he ypes o o ganiza ion
and in he business wo ld. In ac , almos all la ge and many medium sized en e p ises
wo ldwide ha e es ablished Ope a ions Resea ch eams.
Among he indus ies ha apply Ope a ions Resea ch a e hose dealing wi h a ia ion
and missiles, compu e science, elec ic powe gene a ion, elec onics, ood, me allu gy,
mining, pape , pe oleum, anspo a ion, as well as inancial ins i u ions, go e nmen
agencies and hospi als. The companies which we e inalis s o he F anz Edelman
INFORMS (Ins i u e o Ope a ions Resea ch and he Managemen Science) p ize
p o ide excellen examples o eal applica ions o Ope a ions Resea ch
(h p://www.in o ms.o g).
Among he inalis s in 2012 we e Hewle -Packa d (HP), In el and TNT Exp ess. The
la e won he awa d o i s "Global Op imiza ion", which uses ad anced me hods o
op imize he anspo ne wo k o he company. This p og am sol es p oblems in
wa ehouse loca ion, op imal ou es o ucks, lee managemen and pe sonnel
scheduling.
In 2011 Midwes Independen T ansmission Sys em Ope a o (Midwes ISO), a non-
p o i o ganiza ion ha manages he elec ici y ma ke in 13 U.S. s a es (No h Cen al
egion) and one in Canada (Mani oba), won he awa d. I has ope a ional con ol o mo e
han 1,500 ene gy p oduc ion plan s and 55,000 miles o powe lines. I no i ies he plan s,
e e y 5 minu es, o he amoun o ene gy equi ed o mee he cu en demand. I uses a
linea p og amming model o calcula e p oduc ion le els and es ablish he ma ke p ice
o elec ici y. The model size is up o 3 million con inuous a iables and 4 million
Sys em 4
O
he
P oduc s
Sys em 3
Pu chases
Sys em 2
P oduc ion
Sys em 1
Sales and cus ome se ices
Ope a ions esea ch in business adminis a ion and managemen
18
cons ain s. The solu ion o he model p o ides plan p oduc ion le els and ene gy p ices
(shadow p ices o oppo uni y cos s). I also uses an in ege p og amming model o
de e mine when a plan should be p oducing o no . The indi idual companies e ain
physical con ol o he plan s and ansmission lines. Midwes ISO manages he eal- ime
powe o bid and buy on demand, manages he ma ke and maximizes he bene i o he
company which sells he cheapes elec ici y. In sho , using echniques discussed in his
book, in his example he p ice a which elec ici y is bough and sold is de e mined and,
wha is mo e impo an , he elec ici y is a ailable when and whe e i is needed and
p o ided sa ely.
In 2009 HP and he Ma io ho el chain we e no able en ies wi h wo Ope a ions
Resea ch ools o manage he p oduc po olio and wi h a p ice op imize espec i ely.
Also in 2009 Za a was among he inalis s o applying Ope a ions Resea ch o imp o e
i s dis ibu ion p ocess. Cocacola En e p ises, he wo ld's la ges bo le and dis ibu o
o Coke p oduc s (Coke, Fan a, Sp i e, Minu e Maid, e c) was also ecognized in 2007
o i s applica ion o schedule he daily ou es o 10,000 ucks.
We will discuss he applica ion o Za a in a li le mo e de ail. Za a´s supply chain
consis s o wo main wa ehouses loca ed in Spain, which egula ly ecei e shipmen s o
inished ga men s om supplie s and eplenish all Za a s o es wice a week. The key is
o de e mine he exac numbe o each size (up o 8 di e en sizes) and each i em (up o
3,000 a a ime) o be included in each shipmen o each s o e ( he e a e o e 1,500). Un il
2005 Za a used a p ocedu e ha equi ed a la ge numbe o employees o de e mine
shipmen s o each s o e. The company de eloped a decision making p ocess based on
Ope a ions Resea ch me hods, including me hods o o ecas ing and a e y la ge mixed
in ege p og amming model. The implemen a ion o his new p ocess p esen ed many
echnical di icul ies. One o hem was o include he unce ain y o es ima es and
in en o y policies o he s o es, and he in eg a ion o a complex ma hema ical model
wi h many la ge da abases. They also had o ha e he so wa e and ha dwa e
in as uc u e necessa y o sol e op imiza ion o housands o p oblems in a couple o
hou s each day. Addi ionally, i p esen ed challenges ela ed o human esou ces, because
he Za a co po a e cul u e highly alues in ui ion and pe sonal judgmen in decision-
making. The de elopmen o his new p ocess, suppo ed by Ope a ions Resea ch
echniques, was comple ed in all s o es and a icles and i has been used since 2007.
In gene al, linea p og amming and in ege p og amming ha e been success ully
used in sol ing p oblems ela ed o he alloca ion o he means o p oduc ion, ma e ial
mixing, dis ibu ion, anspo a ion, in es men selec ion and planning o ag icul u e,
among o he s. A e y impo an applica ion o linea p og amming in he ield o
economics is Da a En elopmen Analysis (DEA), de eloped by Cha nes, Coope and
Rhodes (1978). DEA is a linea p og amming based echnique ha allows us o
empi ically measu e he p oduc i e e iciency o decision uni s such as g oups o
companies in he same sec o , inancial ins i u ions, hospi als, educa ional ins i u ions,
e c. and iden i y he companies ha a e on he e icien on ie o p oduc ion. The
e iciency is measu ed by he weigh ed sum o he ou pu s on he inpu s. The weigh ing
s uc u e is calcula ed using linea p og amming. Fu he mo e, he concep s o linea
Chap e 1. The na u e and me hodology o ope a ions esea ch
19
p og amming guide and acili a e he analysis and in e p e a ion o he esul s o he DEA
models. A p esen his is s ill a e y ac i e ield o wo k, bo h in he applica ion and in
he esea ch being conduc ed.
Nonlinea p og amming is also used in ce ain p oblems o esou ce alloca ion,
selec ion o e icien po olios, new p oduc design, p oduc ion p oblems, mix u es in
chemical p ocesses, e c. Mul iobjec i e p og amming and goal p og amming also
ha e many applica ions such as na u al esou ce managemen (Wein aub e al., 2007),
scheduling o ad e ising media, land use managemen , loca ion o u ili ies and planning
o esou ces in hospi als o name jus a ew. O he Ope a ions Resea ch echniques such
as in en o y heo y, game heo y and simula ion ha e been used in a a ie y o con ex s.
Ope a ions Resea ch sha es wi h A i icial In elligence he objec i e o p o iding
me hods and p ocedu es o sol ing p oblems and making decisions. A i icial
In elligence is in e en ial and has expe knowledge and heu is ic me hods. Ope a ions
Resea ch is mainly based on ma hema ical algo i hms. A ca e ul in eg a ion o hese wo
app oaches has a b igh u u e ahead o he pe o mance and accep ance o he sys ems.
Decision Suppo Sys ems o decision making in eg a e Ope a ions Resea ch and
A i icial In elligence echniques in in o ma ion sys ems ha a e e y use ul in he
decision making p ocess. This in eg a ion can make Ope a ions Resea ch echniques
mo e accessible o decision make s and he models can also use A i icial In elligence
echniques. We should also highligh heu is ic sea ch echniques such as gene ic
algo i hms, abu sea ch and simula ed annealing.
Ope a ions Resea ch models a e common in inance, o en g ouped unde he name
o inancial enginee ing. Simila ly ma ke ing enginee ing usually means Ope a ions
Resea ch applied o ma ke ing. In his ield i is applied o s a egic decisions (planning,
po olio, e c.) and a he ac ical le el (p oduc design, ad e ising, e c.). They also play
an impo an ole in he analysis o elec onic ma ke s. O he oppo uni ies will come
om elec onic ade and in es men , om online banking o online insu ance.
Wi h ega d o supply chain managemen , he digi al economy p o ides oppo uni ies
o use Ope a ions Resea ch in esou ce planning in companies. Gi en he in o ma ion ha
is a ailable online, ad anced planning and p oduc ion scheduling, will imp o e
coo dina ion and coope a ion be ween supplie s and cus ome s. The g ow h o mobile
compu ing and communica ion will inc ease he aid ha applica ions gi e o decision-
making in anspo ucks. Thus he e a e companies ha op imize loading and uck
ou es using web applica ions o ob ain da a and dis ibu e solu ions. The In e ne also
acili a es he expansion o supply managemen owa ds in eg a ing p oduc design, sales
and cus ome s.
Finally, we mus emphasize he s eng hs o Ope a ions Resea ch in he digi al
economy e a: i exploi s he as amoun o da a a ailable, which is o e e inc easing
complexi y due o i s analy ical na u e and unce ain y, modeling inc eases ou
unde s anding o business p ocesses and i ual expe imen s can be made wi hou
isk o business and hus p o ides decision making echnology o he au oma ion o
Ope a ions esea ch in business adminis a ion and managemen
20
ecu ing decisions in eal ime, such as o web applica ions. In sho , he Ope a ions
Resea ch o he u u e is Ope a ions Resea ch in eal ime. Cus ome s o en ask when
hei o de will be deli e ed. P o ide s base hei esponse on hei in en o y and he
scheduled p oduc ion in p og ess. Howe e , hey should now be able o espond a e
pe o ming a scheduling algo i hm including he po en ial o de . To achie e he equi ed
pe o mance in eal ime some imes we need o eso o heu is ic algo i hms such as
hose discussed in he las chap e o he book.
1.4. METHODOLOGY OF OPERATIONS RESEARCH
Daellenbach and McNickle (2012) clea ly es ablish h ee majo phases in he
me hodology o Ope a ional Resea ch which a e: p oblem o mula ion, modelling and
implemen a ion, which in u n b eak down in o he sub-phases indica ed in Figu e 1.2.
Figu e 1.2. Me hodology o Ope a ion Resea ch. Sou ce: Daellenbach and McNickle (2012)
1.4.1. FORMULATION OF THE PROBLEM
In he i s place, we should make a syn hesis o he si ua ion, o example h ough
g aphics o cha s which will help us du ing he p oblem de ini ion phase, a e which
we should iden i y he s uc u e, he ans o ma ion p ocesses, he componen s and he
Fo mula ion
o he p oblem
Modelling
Implemen a ion
Sin hesize he
p oblem
si ua ion
Follow up he
solu ion
use
Iden i y he
p oblem
Build a ma hema ical
model
Desc ibe he ele an
sys em
Find he p e e ed
solu ion
Valida ion o he
solu ion
Plan he
implemen a ion
Sensi i i y
analysis
Con ol he
solu ion
Implemen he
solu ion
P ojec p oposal
P ojec epo
Re ising he solu ion

Chap e 1. The na u e and me hodology o ope a ions esea ch
21
inpu s and ou pu s o he ele an sys em. Fo a p oblem o exis he e mus be an
indi idual o g oup o indi iduals, called decision-make s, who a e no sa is ied wi h he
cu en si ua ion o who ha e unsa is ied necessi ies, such as eaching some goals o
objec i es. They also know when he goals o objec i es ha e been sa is ac o ily eached
and hey ha e con ol o e he aspec s o he si ua ion ha a ec he ex en o which he
goals o objec i es a e achie ed. The ou elemen s o a p oblem a e:
x The decision-make /s.
x The decision-make ´s objec i es.
x The measu emen o e iciency in o de o be able o assess he ex en o which
objec i es a e achie ed.
x The ac ion al e na i es o decision a iables o each he objec i es.
The second s ep o he o mula ion o he p oblem is i s iden i ica ion and consis s o
de ining hese ou elemen s. The hi d s ep consis s o de ining he ele an sys em o
he p oblem ha we ha e iden i ied in he p e ious s ep, including i s en i onmen . The
decision-make has an esen ial ole in he p oblem o mula ion phase.
In p ac ice, he de e mina ion o hese ou componen s migh no be so easy o ob ain
by simply asking he decision-make . Some imes he decision-make only has a ague
in ui ion ha hings could go be e . We should explo e and cla i y he si ua ion h ough
se e al people in ol ed in he si ua ion. Some imes, i may happen ha he pe son who
makes he decisions does no ha e access o he in o ma ion needed o make an e ec i e
decision and he one ha has he in o ma ion does no ha e enough au ho i y o make
decisions. In hese cases, he i s hing o do is o change he s uc u e o he o ganiza ion,
e-assigning he oles in he decision making. In mos eal applica ions, p oblem
o mula ion is no achie ed in hese h ee s eps, a he he ini ial o mula ion is de ailed
wi h successi e e o mula ions, as he p oblem is be e unde s ood. In ac , i con inues
un il he p ojec concludes. Howe e , i is in his phase whe e he success o ailu e o
many p ojec s occu .
Once we know he p oblem and he ele an sys em well enough, we can decide
whe he Ope a ions Resea ch may p o ide a solu ion o he p oblem. The e o e we should
ask ou sel es he ollowing ques ions:
Can he p oblem be exp essed in quan i a i e e ms?
A e he equi ed da a a ailable o can hey be ob ained a a easonable cos ? 
Does he cos o he analysis jus i y he possible bene i s ha will be ob ained om
WKHimplemen a ion o he esul s? To wha ex en can he decision-make expec a ions
EH ul illed?
I we answe hese ques ions a i ma i ely, hen he o mula ion phase concludes wi h
a p oposal ha will be he documen which he decision-make will use o decide o
con inue wi h he p ojec o no . The e o e, he p oposal is a key elemen . We should no
p omise mo e han we know ha we can ob ain wi h he a ailable esou ces. Since
Ope a ions Resea ch has much in common wi h he scien i ic esea ch, i should be
guided by he e hics o he scien i ic me hod.
Ope a ions esea ch in business adminis a ion and managemen
22
The ollowing anecdo e om Acko illus a es bo h he di icul y o o mula ing he
p oblem in eal cases, and he ac ha we can no always sol e an unsa is ac o y si ua ion
by making models. I is as impo an o know wha models a e use ul and when we can
imp o e decision making, as i is o know how o ecognize when hey a e no he igh
ool. The adminis a ion o a la ge o ice building ecei ed complain s o yea s abou
excessi e s a ime spen wai ing o he ele a o s in he main lobby. Se e al eams o
Ope a ions Resea ch analyzed his p oblem o excessi e wai ing ime. Di e en solu ions
we e p oposed: o use some ele a o s o lowe loo s and o he s o highe loo s only.
Howe e , i was concluded ha a signi ican educ ion would be possible only by
ins alling new ele a o s wi h a high associa ed cos . A membe o he las eam o s udy
he p oblem asked why s a complained and a e app opia e inqui ies i u ned ou o be
because o bo edom. The Ope a ions Resea ch eam hen p oposed ins alling mi o s.
Some wo ke s used hem o make a inal check o hemsel es o o check ou o he s a
wi hou being oo ob ious. When his solu ion was implemen ed he complain s
disappea ed (Acko , 1987). Nowadays, sc eens wi h in o ma ion o in e es o he s a
can achie e he same e ec as he mi o s did hen.
Ope a ions Resea ch, in many cases, does no in end o ind he op imal solu ion, bu
o ind some deg ee o imp o emen o e he p e ious si ua ion. One o he ounding
a he s o he discipline colloquially explained i as ollows: "Ope a ions Resea ch is he
a o p o iding bad solu ions o p oblems ha o he wise would ha e wo se solu ions."
1.4.2. MODELLING
This phase dis inguishes Ope a ions Resea ch om o he me hods o sol ing
p oblems. Acco ding o Daellenbach and McNickle (2012), Ope a ions Resea ch is o en
seen as a numbe o echniques and ma hema ical ools, which do no a ou he discipline
a all o he de imen o i s po en ial. The modelling phase begins by exp essing he
sys em ela ed o he p oblem in quan i a i e e ms. A ma hema ical model exp esses in
quan i a i e e ms he ela ionships be ween especially impo an componen s o he
sys em ha ha e been de ined in he o mula ion phase. These ela ionships can
some imes be ep esen ed in a sp eadshee and o some o he s i is necessa y o o mula e
he ela ionships in e ms o ma hema ical exp essions, such as equa ions, inequali ies o
unc ions. The e m model is used in a b oad sense, since i can ake he o m o a cha
as well as o ma hema ical exp essions.
We call he ac ion al e na i es o con ollable aspec s o he p oblem decision
a iables. The e m ac ion al e na i es is used when he numbe is disc e e and usually
small. The measu emen o he beha iou o e ec i eness is he aspec ha measu es he
ex en o which he objec i es o he company a e eached. I his measu e o e ec i eness
can be exp essed as a unc ion o he a iables, we call i he objec i e unc ion. Ou goal
is o ind he alues o he decision a iables ha maximize o minimize he objec i e
unc ion. The pa ame e s o coe icien s ep esen he uncon ollable aspec s o he
p oblem. And he cons ain s a e he ma hema ical exp essions ha limi he ange o
alues o he decision a iables. F om he ea ly 50’s, a numbe o ma hema ical models
ha e been de eloped wi h hei own esolu ion p ocedu e, such as linea p og amming
Chap e 1. The na u e and me hodology o ope a ions esea ch
23
and i s nume ous ex ensions, ne wo k models such as he c i ical pa h, e c. They a e wha
we call gene al pu pose models. Any p oblem ha sa is ies he hypo heses o a gene al
model can be app oached and sol ed in his way. Fo hose p oblems ha do no adap o
any speci ic echnique o Ope a ions Resea ch, a model should be de eloped o he
speci ic pu poses, wi h a unique s uc u e o ha pa icula p oblem. Likewise, a solu ion
p ocedu e has o be c ea ed o ha speci ic case. Las ly, when all o he inpu s and
ela ionships a e known, he p oblem is de e minis ic, while i some inpu s o esul s a e
subjec ed o unce ain y, like he p obabilis ic in luences, he model is known as
p obabilis ic o s ochas ic.
A ma hema ical model, o be use ul, should enable be e decisions when you use i
han when you don' and should also be:
x Simple: Simple models a e easie o he decision-make o unde s and. I will be
easie i he decision-make ollows he logic o a sp eadshee han a se o
equa ions. Howe e , when designing complex models i is una oidable ha
app oxima ions app op ia e o he eal si ua ion be made.
x Comple e: The model should include all o he signi ican aspec s o he p oblem
ha a ec he measu emen o i s e ec i eness. I may be necessa y o design wo
models, one wi h ce ain aspec s o compa e and o decide hei ele ance and
ano he one wi hou hem.
x Easy: I should be possible o ob ain esponses om he model, such as he
op imum solu ion, wi h a easonable compu a ional e o . Mo eo e , i should be
easy o p epa e, upda e and change he pa ame e s and ob ain new answe s quickly.
x Adap i e: Usually, easonable changes in he s uc u e o he p oblem do no
in alida e he model. I he changes in alida e he model, i may be possible o adap
he model wi h sligh modi ica ions. An adap i e model is known as a obus
model.
In p ac ice, we may ind hese p ope ies use ul in a model, howe e , use s may only
app ecia e some o hem. Thus, he decision-make and he use o he model migh be
mo e in e es ed in he desi able p ope ies o he modelling p ocess han in hose o he
model i sel . The c edibili y and us o he use a e ela ed mo e o he p ocess and he
in e ac ion wi h he modelle han wi h he model i sel . In his sense, i is impo an o
keep in mind he ollowing aspec s:
The model should be app op ia e o he si ua ion unde s udy: The model
p oduces ou s anding esul s wi h he smalles possible cos and in he ime equi ed by
he decision-make . A “good” Ope a ions Resea ch model does no necessa ily ha e o
show he de ails o o esemble he physical sys em ha i a emp s o op imize. In
addi ion, a good model should allow us o measu e he p og ess eached owa d he
decision-make ’s objec i es.
The model has o p oduce in o ma ion ha is ele an and app op ia e o he
decision-making p ocess. I he model complies wi h hese las wo p ope ies and we
can demons a e hem o bo h he decision-make and he use , hen i is mo e likely ha
Ope a ions esea ch in business adminis a ion and managemen
24
hey will ind he model use ul. Las ly, some o he p ope ies o good models a e in
con lic . A simple model canno ake in o conside a ion all o he ele an aspec s. A
obus model canno be simple. A model ha includes all o he signi ican aspec s may
no be easy o manipula e. The pe son (o eam) ha builds he model should balance
hese aspec s and adop a commi men , which should ake in o conside a ion he unding
and he ime a ailable o he analysis. I should also ake in o conside a ion he possible
bene i s. Thus, he use o simple and quick s a egies ha p o ide 50% o he bene i s can
be economically mo e ad an ageous han using a sophis ica ed and expensi e model ha
achie es 90% o he po en ial bene i s. The cos o de elopmen o he ma hema ical
model, da a collec ion, calcula ion o he bes solu ion, model implemen a ion and
main enance, inc eases mo e han p opo ionally wi h he sophis ica ion o he model,
while he bene i s inc ease less han p opo ionally.
Al hough he p ocess o ma hema ical modelling can be conside ed as a scien i ic
p ocess, he e a e ce ain aspec s ha a e close o an a han o a science. I is
conside ed an a because i is necessa y o de elop simple models ha a e good
app oaches o eal li e. The e is li le ad ice ha can be gi en in his espec , excep ha
he abili y and necessa y skills can be acqui ed wi h p ac ice. Expe s ecommend s a ing
wi h simple models ha become iche e ol ing owa ds elabo a ed models by he
inco po a ion o addi ional aspec s o he p oblem. Ano he ip is o wo k wi h nume ic
examples, as well as g aphics and cha s.
The cons uc ion o models in he p ac ice o business adminis a ion and
managemen is aluable a leas o he ollowing easons (Eppen e al, 1997):
1. The models equi e ha he objec i es be explici y de ined.
2. The models equi e he iden i ica ion and eco ding o he ypes o decisions ha
in luence hese objec i es.
3. The models equi e he iden i ica ion and eco ding o he in e ac ions be ween all
hese decisions and o hei espec i e ad an ages and disad an ages.
4. The models equi e hinking abou he a iables o include and o de ine hem in
quan i a i e e ms.
5. The models equi e us o conside wha da a a e ele an o he quan i ica ion o
hese a iables and o de e mine he in e ac ions be ween hem.
6. The models equi e he ecogni ion o he ele an es ic ions on he alues ha
a iables can ake.
7. The models can communica e ideas and expe ise, acili a ing eamwo k.
A e he cons uc ion o he model, we manipula e he quan i a i e model o explo e
he sys em’s beha iou in esponse o he changes in he inpu s, ha is, we explo e he
solu ion space. The objec i e is o ind he p e e ed solu ion in e ms o he decision-
make ’s objec i es. I he la e is in e es ed in a main objec i e he op imal solu ion has
Chap e 1. The na u e and me hodology o ope a ions esea ch
31
In summa y, he iden i ica ion o he da a sou ces, da a collec ion and e alua ion a e
ac i i ies ha may happen pa allel o any o he ele en s eps o he me hodology
desc ibed, e en in he las s ep o he e ision o he solu ion. In some cases da a may no
be a ailable in he equi ed o m o may e en no exis . In hese cases, ac ions should be
aimed a he collec ion o da a in he equi ed o m.
Las ly, we would also like o emphasize he impo ance o he analys ’s skills
ega ding pe sonal ela ionships and hei abili y o ob ain in o ma ion om in e iews.
Open in e iews a e ecommended o pe o m, showing cu iosi y and in e es in wha
o he s know, a he han gi ing he image o an expe who knows e e y hing.
1.5. SUMMARY
This chap e app oaches he basic na u e and me hodology o Ope a ions Resea ch in
o de o unde s and and assess he ole o Ope a ions Resea ch in he educa ion and
aining o G adua es in Business Adminis a ion and Managemen . Ope a ions Resea ch
is a echnology whose pu pose is he p oduc ion o in o ma ion abou sys ems o imp o e
he e iciency o companies and o he o ganiza ions. The cons uc ion and he sol ing
echniques o ma hema ical models a e only a pa o a eal Ope a ions Resea ch
p ojec . The P oblem o mula ion and solu ion implemen a ion phases a e also key, so
we should no lose sigh o he ole played by he model and he solu ion wi hin he
me hodology o Ope a ional Resea ch.
The aim o he emaining chap e s is o acili a e lea ning o he o mula ion and
sol ing linea p og amming models, in ege , nonlinea and mul iple c i e ia using
Mic oso Excel Sol e and LINGO and o he p o essional so wa e (Expe Choice and
D-Sigh ). We will ocus on he key concep s and he necessa y echniques o he co ec
in e p e a ion o he esul s o he models, in o de o imp o e decision-making and
ul ima ely he e ec i eness o companies. We ecommend ha he s uden ead his
in oduc o y chap e again a he end o he cou se, when hey will be e unde s and some
o he issues discussed.
1.6. SELECTED REFERENCES
1. Acko , R.L. (1987): The A o P oblem Sol ing: accompanied by Acko 's Fables.
John Wiley & Sons.
2. Assad, A.A., Wasil, E.A. and G.L. Lilien (1992): Excellence in Managemen Science
P ac ice. A eadings book. P en ice-Hall In e na ional.
3. Daellenbach, H.G.; Geo ge, J.A. and D.C. McNickle, (1987): In oducción a las
écnicas de In es igación de Ope aciones. CECSA.

Ope a ions esea ch in business adminis a ion and managemen
32
4. Daellenbach, H., McNickle, D. and S. Dye (2012): Managemen Science. Decision-
making h ough sys ems hinking. 2nd Re ised Edi ion. Palg a e Macmillan.
5. Eppen, G.D.; Gould, F.J.; Schmid , C.P.; Moo e, J.H. and L.R. Wea he o d (1997):
In oduc o y Managemen Science: Decision Modeling wi h Sp eadshee s. 5 h edi ion.
Pea son.
6. Hillie , F.S and Hillie , M.S. (2011): In oduc ion o Managemen Science. A
Modelling and Case S udies. App oach wi h Sp eadshee s. Fou h Edi ion. McG aw-
Hill.
7. Hillie , F.S. and Liebe man G.J. (2010): In oduc ion o Ope a ions Resea ch. Nin h
Edi ion. McG aw-Hill.
8. Keys, P. (Ed) (1995): Unde s anding he p ocess o Ope a ional Resea ch. Wiley.
9. Ki by, M.W. (2000): “Ope a ions Resea ch T ajec o ies: The Anglo-Ame ican
Expe ience om he 1940’s o he 1990’s”, Ope a ions Resea ch 48, 661-670.
10. Robinson, R. (2000): “A Business Execu i e´s Guide o Mode n OR”, OR/MS Today
27/3, 22-27.
11. Wein aub, A.; Rome o, C.; Bjo ndal, T. and R. Eps ein (2007) (Edi o s): Handbook
o Ope a ions Resea ch in Na u al Resou ces. Sp inge .
12.Wins on, W. L. and S.C. Alb igh (2012): P ac ical Managemen Science. Fou h
Edi ion. Sou h-Wes e n. USA.
CHAPTER
2
FORMULATING AND SOL
VING
LINEAR PROGRAMMING
MODELS: BASIC CONCEPTS
2.1. THE PROBLEM: PRODUCTION IN A POWER PLANT AND
POLLUTION CONTROL ............................................................................. 35
2.2. THE MODEL: VARIABLES, THE OBJECTIVE FUNCTION AND
CONSTRAINTS ............................................................................................... 36
2.2.1. VARIABLES: DIVISIBILITY AND NONNEGATIVITY HYPOTHESIS ..... 36
2.2.2. OBJECTIVE FUNCTION AND CONSTRAINTS: LINEARITY
HYPOTHESIS ............................................................................................. 37
2.2.3. GENERAL FORMULATION OF A LINEAR PROGRAMMING
MODEL: CERTAINTY HYPOTHESIS ....................................................... 42
2.3. FEASIBLE REGION AND GRAPHICAL SOLUTION ....................... 43
2.4. SLACK VARIABLES .................................................................................... 45
2.5. SENSITIVITY ANALYSIS ........................................................................... 45
2.5.1. SENSITIVITY ANALYSIS OF THE OBJECTIVE FUNCTION
COEFFICIENTS........................................................................................ 45
2.5.2. SENSITIVITY ANALYSIS OF THE RIGHT-HAND SIDE OF THE
CONSTRAINTS
2.6. THE EXTENDED PROBLEM: A NEW VARIABLE ........................... 49
2.7. LINEAR PROGRAMMING MODEL SOLVING WITH A
SPREADSHEET ………………………………………………………. 50
2.8. LINEAR PROGRAMMING MODEL SOLVING WITH
OPTIMIZATION SOFTWAR 53
2.9. MODELLING: SOME EXAMPLES
…………………..........………………
.. 55
2.9.1. COMMON MISTAKES IN MODELLING…………………...……….……….. 55
2.9.2. SOME MODELS OF LINEAR PROGRAMMING………………………...… 57
2.10. SUMMARY .................................................................................................... 60
E
…………………..………………
Ope a ions esea ch in business adminis a ion and managemen
34
2.11. SELECTED REFERENCES ...................................................................... 61
2.12. CASE STUDIES ............................................................................................ 61
Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
35
Linea P og amming is he mos impo an echnique used in Ope a ions Resea ch
and is conside ed o be as one o he mos signi ican scien i ic ad ances o he 20 h
cen u y. I is a s anda d ool o sol ing op imiza ion p oblems ha has had an
ex ao dina y impac since 1950 and cu en ly sa es millions o dolla s o many
companies and businesses. Some o he mos common applica ions include p oblems such
as alloca ing p oduc ion esou ces, ma e ial blending, dis ibu ion, anspo a ion, ood
planning and adia ion he apy design.
In linea p og amming eal p oblems a e ep esen ed by ma hema ical models subjec
o a numbe o condi ions, such as he linea na u e o he unc ions. Simila o wha
happens wi h o he Ope a ions Resea ch echniques, model cons uc ion is an essen ial
s age and i is mainly he ui o expe ience and he co ec applica ion o some basic
p inciples. We begin his chap e by o mula ing a p oblem and hen a linea
p og amming model in o de o sol e i s ep by s ep. In his way all he assump ions o
linea p og amming models will be explained. We will also see ha he meaning o
p og amming in his con ex is a he di e en om he e m "p og amming", as used in
compu e science o e e o so wa e implemen a ion.
Fu he , we will sol e g aphically one p oblem o help he in ui i e unde s anding o
he main basic concep s, such as easible solu ion, easible egion and op imal solu ion.
The concep o slack a iables and he e ec s o changing he pa ame e s o he model
h ough sensi i i y analysis a e also p esen ed.
Nex , we will sol e he p oblem as we would in p ac ice, using sp eadshee s o
op imiza ion so wa e and we will in e p e he esul s. The chap e includes o he
p oblems ha will acili a e lea ning he modelling and subsequen esolu ion and
in e p e a ion o he solu ion o imp o e decision-making in business. Finally, selec ed
e e ences on his opic a e gi en as a guide o p o ide s uden s wi h ex a eading
ma e ial. The chap e includes case s udies; some o which will be used in labo a o y
sessions and sol ed by he s uden s wi h he help o he eache , and o he case s udies
will se e as sel -assessmen exe cises.
2.1.THEPROBLEM:PRODUCTIONINAPOWERPLANTAND
POLLUTION CONTROL
The managemen o a coal- ueled he mal powe plan is analyzing he ope a ional
con igu a ion o he plan o adap o new en i onmen al pollu ion con ol egula ions.
The maximum emission a es o he he mal powe plan a e
x Maximum emission o sulphu oxide: 3000 pa s pe million (PPM)
x Maximum emission o pa icles (smoke): 12 kilog ams/hou (kg/h)
The coal is anspo ed o he plan by ain and is unloaded in o con aine s close o he
plan . A con eyo bel akes i o he pul e ize , in which i is handled and ed di ec ly o
he combus ion chambe a he co ec speed. The hea gene a ed in he combus ion
Ope a ions esea ch in business adminis a ion and managemen
36
chambe is used o p oduce s eam, which, in u n, se es o d i e he u bines.
Two ypes o coal a e used: ype A, a ha d, clean-bu ning coal wi h low sulphu
con en ( a he expensi e); and ype B, a cheap, ela i ely mild coal wi h high sulphu
con en ha causes smoke, as shown in Table 2.1. The he mal alue in e ms o he
s eam gene a ed is g ea e o coal ype A han o ype B, which a e 24000 and 20000
lb pe on espec i ely.
Table 2.1. Emission o pollu ing agen s
Coal Sulphu oxide in uel gases Pa icles (kg emission/ on)
A 1800 PPM 0.5 Kg/ on
B 3800 PPM 1.0 Kg/ on
As coal ype A is ha d, he pul e ize can only handle 16 ons o coal A pe hou ;
howe e , i can handle up o 24 ons o coal B pe hou . The loading sys em o he
con eyo bel has a capaci y o 20 ons pe hou independen o he ype o coal.
One o he many ques ions he plan 's managemen has gi en is he emission limi s o he
pollu ing agen s and he ypes o coal a ailable, wha is he maximum possible amoun o
elec ici y ha can be gene a e in he powe plan ? The answe will allow manage s o
de e mine he sa e y ange in o de o co e peak powe demands.
2.2.THEMODEL:VARIABLES,OBJECTIVEFUNCTIONAND
CONSTRAINTS
2.2.1. VARIABLES: DIVISIBILITY AND NONNEGATIVITY HYPOTHESIS
In he sho e m, he ins alla ions o he powe plan a e ixed. The only aspec o he
p oblem ha can be changed and used o modi y he p oduc ion o he powe plan is he
amoun o each ype o coal o bu n. The e o e, he decision a iables o he p oblem a e
x Amoun o coal A used pe hou , e e ed o as X1 ( on/h)
x Amoun o coal B used pe hou , e e ed o as X2 ( on/h)
Linea p og amming o en e e s o he con ollable aspec s o decision-making
p oblems as ac i i ies. The e o e, X1 and X2 ep esen he bu ning ac i i y le els o coal
A and coal B, espec i ely.
LINEAR PROGRAMMING HYPOTHESIS 1: DIVISIBILITY
All a iables can ake any eal alue

Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
37
Many ac i i ies o he eal wo ld a y in a con inuous way, i.e., hey a e di isible
in ini ely. Fo example, he amoun o coal bu n pe hou can be adjus ed wi hin ce ain
limi s. Howe e , he e a e eal ac i i ies ha can only ake in ege alues, o example,
he numbe o uck ips necessa y o mo e a ce ain load om one place o ano he o
he numbe o compu e s equi ed by a company.
When he eal ac i i y is no di isible in a ini e way, bu he no mal le el o he
ac i i y is a high numbe , hen di isibili y condi ions can be used as a con enien
app oach. This means ha he alue o he solu ion is en o highe . F ac ional alues a e
ounded up o he closes in ege alue. Howe e , i he no mal le el o he ac i i y is less
han 10, in ege p og amming will be necessa y.
LINEAR PROGRAMMING HYPOTHESIS 2: NONNEGATIVITY CONDITIONS
All a iables a e nonnega i e
This hypo hesis e lec s he na u e o mos eal ac i i ies, since nega i e ac i i y le els
ha dly e e occu in economic o enginee ing con ex s. Howe e , his conside a ion does
no in ol e a loss o gene aliza ion. Any numbe (posi i e, ze o o nega i e) can be
exp essed as he algeb aic di e ence be ween wo nonnega i e numbe s. I an ac i i y
can occu in bo h posi i e and nega i e le els ( o example, buying o selling bonds), wo
a iables a e in oduced o his ac i i y, X+ o nonnega i e le els, and X- o nonposi i e
le els. Thei di e ence X = X+- X- ep esen s he eal le el o he ac i i y. Wi h his
me hod, bo h X+ and X- a e subjec o be nonnega i e. Op imiza ion so wa e allows use s
o de ine di ec ly hese a iables as ee a iables wi h a a ia ion ange be ween nega i e
and posi i e in ini y.
2.2.2. OBJECTIVE FUNCTION AND CONSTRAINTS: LINEARITY HYPOTHESIS
The objec i e o he plan 's managemen is o maximize powe gene a ion in he plan .
Since elec ic powe is gene a ed om s eam he e is a di ec ela ionship be ween s eam
and elec ic powe gene a ion, maximizing s eam gene a ion is equi alen o maximizing
elec ic powe gene a ion. The e o e, he managemen objec i e can be es a ed as
" inding he combina ion o uels ha maximizes s eam gene a ion ".
How much s eam is p oduced o any gi en amoun o coal used? A simple and
sys ema ic way o de e mining his is shown in Table 2.2.
Le us exp ess he amoun o s eam gene a ed in housands o pounds. The e o e, coal
A p oduces 24 s eam uni s and coal B 20 s eam uni s pe on o coal. Thus, he amoun o
s eam gene a ed pe hou is
(1) 24 X
1
+ 20 X
2
= Z
Ope a ions esea ch in business adminis a ion and managemen
38
Table 2.2. Building he objec i e unc ion
Coal S eam
(lb/ on)
Coal used
( on/hou )
S eam gene a ed
(lb/hou )
A 24000 X 24000 X1
B 20000 X2 20000 X2
To al amoun o s eam lb/h = 24000 X1 + 20000 X2
The i s e m in (1) is called he objec i e unc ion and Z is he alue o he objec i e
unc ion. The a iable coe icien s a e called objec i e unc ion coe icien s. The p oblem
equi es de e mining alues o X1 and X2 ha maximize Z alue. Figu e 2.1. shows ha
(1) is a amily o pa allel s aigh lines and ha o each alue o Z we ob ain a s aigh
line, whose poin s ep esen he possible combina ions o X1 and X2 ha gene a e he
same amoun o s eam and hus, o ene gy. Fo his eason, hey a e known as
isop oduc ion lines (isop o i o isocos , in he case ha he objec i e unc ion
co esponds o p o i o cos espec i ely). I can also be no ed ha he objec i e unc ion
is linea .
LINEAR PROGRAMMING HYPOTHESIS 3: LINEARITY
All ela ionships be ween a iables a e linea . In linea p og amming his implies:
1. P opo ionali y o he con ibu ions. The indi idual con ibu ion o each
a iable is s ic ly p opo ional o i s alue, and he p opo ionali y ac o is
cons an o he ange o alues ha he a iable may ake.
2. Addi i i y o he con ibu ions. The o al con ibu ion o he a iables is equal
o he sum o he indi idual con ibu ion, ega dless o he alue o he a iables.
A ela ionship such as Z = 5 X1 + 3 X12 + 2 X2 o Z = 24 X1 + 20 X2 o X1  5 and
10 + 22 X1 + 20 X2 o X1 > 5 would iola e he condi ion o p opo ionali y; whe eas Z
= 24 X1 o X2 = 0, 20 X2 o X1 = 0 and 22 X1 + 18 X2 o X1 > 0 and X2 > 0 would
iola e he condi ion o addi i i y.
Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
39
5 1015202530
5
10
15
20
25
30
0
Z = 240
Z = 360
Z = 480
Z=600
X
2
X
1
Figu e 2.1. Objec i e unc ion
Hypo hesis 3 implies cons an scale p o i s and p e en s scale economies. In p ac ice,
his condi ion p obably does no s ic ly hold; in pa icula , o e y low o e y high
ac i i y alues. Howe e , i his condi ion is ul illed in an app oxima e way wi hin he
no mal ange o solu ion alues, a linea p og amming model would be a good app oach.
This conside a ion also excludes he p oblem o ixed cos s when hey a e p esen ed o
posi i e alues o he a iable, bu no o ze o alues.
In addi ion o he nonnega i i y condi ions, he alues o he a iables should ul ill
ce ain cons ain s ha may be o a physical, economic o legal na u e.
Cons ain o pa icle emissions
The maximum amoun o smoke emissions pe hou in powe plan s is limi ed o 12
kg. Acco ding o Table 2.1, one on o coal A p oduces 0.5 kg smoke and one on o coal
B p oduces 1 kg smoke. I he plan bu ns X1 ons o coal A and X2 o B, he o al amoun
o smoke emi ed by bo h ypes o coal is equal o he sum o bo h, which canno exceed
12 kg/h.
Ope a ions esea ch in business adminis a ion and managemen
40
The coe icien s o he a iables in he cons ain s a e called echnical coe icien s and
he second e m o he inequali y o independen e m is known as igh -hand side (RHS)
cons ain pa ame e .
Cons ain o loading ins alla ions
The sys em o he con eyo bel ha anspo s he coal om he con aine s o he
pul e ize has a capaci y o 20 on/h. The e o e, he load cons ain will be:
Cons ain o he pul e ize capaci y
The maximum capaci y o he pul e ize is 16 on/h o coal A o 24 on/h o coal B.
Tha is, i akes 1/16 h o handle one on o coal A and 1/24 h o pul e ize one on o coal
B. I he solu ion demands he combina ion o bo h ypes o coal, he ime equi ed o
pul e ize a mix u e o X1 on o A and X2 o B is (1/16)X1 + (1/24) X2. This cons ain is
exp essed as a combina ion o X1 and X2 o 1 hou . The e o e, he cons ain o he
pul e ize is:
1
24
1
16
1
21 d XX
o
No e how he di icul y a ising om he di e en maximum a es has been sol ed.
The a es ha e been con e ed o equi ed ime pe on and he cons ain is exp essed
e ms o ime a he han capaci y.
Cons ain o sulphu oxide emissions
Maximum sulphu oxide emissions should no exceed 3000 PPM a any ime. Since
bo h ypes o coal a e bu n simul aneously, he combina ion o X1 on o coal A, and X2
ons o coal B pe hou ha eeds he combus ion chambe is conside ed as an
homogeneous mix u e.
X1/(X1 + X2) o he mix u e is coal A wi h a sulphu oxide emission a e o 1800 PPM
and X2/(X1 + X2) o he mix u e is coal B, wi h a sulphu oxide emission a e o 3800
PPM. The emission a e o he mix u e will be he weigh ed mean alue o he indi idual
(2) 0.5 X1 + X2 d 12
(3) X1 + X2 d 20
(4) 1.5 X
1
+
X
2
d 24
Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
47
Objec i e Func ion: C1 X1 + 20 X2
Pul e ize : 1.5 X1 + X2 = 24
20
1
20
5.1
1
C
This gi es C1 = 30. Fo an inc ease in C1 highe han 30, he op imal solu ion will
change om A o B. Fo C1 = 30 he objec i e unc ion 30 X1 + 20 X2 akes i s maximum
alue o 480 a e e y poin o line AB. Simila ly, i C1 dec eases o 10 (all o he
coe icien s emaining cons an ) he objec i e unc ion will be pa allel o he smoke
cons ain . I C1 we e lowe han 10, he op imal solu ion would change om poin A o
poin C (see Figu e 2.4).
In conclusion, we can say ha i he coe icien C1 is such, ha he slope o he line
ha ep esen s i is be ween he slope o he cons ain s o he pul e ize and smoke, he
ini ial op imal solu ion (poin A) is op imum. And we ha e deduced ha i he es a e
cons an , he solu ion X1 = 12 and X2 = 6 will be he op imal solu ion o any alue o he
X1 coe icien o he objec i e unc ion o he in e al 10 d C1 d 30. Can you de e mine
he in e al co esponding o C2 wi hou changes in he ini ial op imal solu ion, i.e. poin
A in Figu e 2.4?
2.5.2. SENSITIVITY ANALYSIS OF THE RIGHT-HAND SIDE OF THE CONSTRAINTS
Le us see wha happens o he op imal solu ion when he igh -hand side o a
cons ain changes. Suppose ha he managemen is conside ing he ins alla ion o a
sys em ha educes he amoun o smoke emissions by 25%. This will allow he plan o
ul ill he legal egula ions while emi ing up o 15 Kg/h o uncon olled smoke om he
combus ion chambe . Wha would be he e ec in e ms o inc easing s eam gene a ion?
Le us i s conside ha he maximum allowed smoke emissions inc ease om 12 o
13 kg/h, all he o he coe icien s emaining cons an . This causes a mo e upwa ds in he
smoke cons ain . Figu e 2.5 shows how he easible egion inc eases. In he new easible
egion Z = 408 is no he op imal alue o he objec i e unc ion, as i s bes alue lies a
poin D. The e o e, he op imal solu ion changes om A o D. This change occu s due o
he ac ha he smoke cons ain is s ic ly ul illed in he op imal solu ion o he o iginal
p oblem. Now, he new ac i i y le els o he a iables a e X1 = 11 and X2 = 7.5. The
dec ease in X1 causes a educ ion o 24 s eam uni s, whe eas he inc ease in X2 inc eases
s eam p oduc ion by 30 uni s. The ne inc ease is 6. Thus he new maximum alue o he
objec i e unc ion will be Z = 408 + 6 = 414.
The imp o emen o he op imal alue o he objec i e unc ion due o he uni
inc ease in he RHS o a cons ain is called oppo uni y cos o dual p ice o he
cons ain . In his case he oppo uni y cos o he smoke cons ain is 6.

Ope a ions esea ch in business adminis a ion and managemen
48
Figu e 2.5. Sensi i i y analysis o he igh -hand side o smoke cons ain
Wha would happen i he maximum smoke emissions we e 14, 15, 16 and
17 kg/h? Figu e 2.5 shows how he a ea o he easible egion inc eases wi h each change
o a maximum o 16. Check ha o each change he objec i e unc ion inc eases by 6.
Fo an inc ease highe han 16, he smoke cons ain becomes edundan . Now he
op imal solu ion will be es ic ed by he pul e ize , sulphu and load cons ain s. Thus,
he oppo uni y cos o his cons ain is ze o o alues highe han 16.
The o iginal ques ion equi ed he de e mina ion o he inc ease in he p oduc ion o
s eam due o he change in he allowable smoke le els om 12 o 15 kg/h. This will be 3
x 6 = 18 s eam uni s/h.
Wha is he oppo uni y cos o a cons ain which is no s ic ly me in he op imal
solu ion? I becomes clea ha i one pa o he esou ce is no used, i.e. he slack a iable
is posi i e, he addi ional amoun s o ha esou ce ha e no alue. They would only
inc ease he amoun o slack. The e o e, he dual p ice o ha cons ain is ze o.
De e mine he dual p ices o he o he cons ain s. Obse e he ela ionship be ween he
5 1015202530
5
10
15
20
25
30
0
LOAD
PULVERIZER
SULPHUR
4035
SMOKE
D
A
X
1
X
2
Op imal solu ion:
X1 = 11
X2 = 7.5
Z = 414
Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
49
oppo uni y cos o a cons ain and he slack a iable associa ed wi h i . When one
esou ce is comple ely used i s oppo uni y cos is gene ally posi i e (nonnega i e o be
mo e exac ) and i s slack a iable is ze o, whe eas when he slack a iable is posi i e he
dual p ice is ze o.
Dual p ices p o ide managemen wi h aluable in o ma ion abou he p o i s ha can
be ob ained by smoo hing he cons ain s. I he bene i s exceed he cos gene a ed by
smoo hing a gi en cons ain , hen he changes a e a ac i e.
2.6. THE EXTENDED PROBLEM: A NEW VARIABLE
The powe plan is o e ed a hi d ype o uel, coal ype C, ha has a sulphu oxide
emission a e o 2000 PPM, a smoke emission a e o 0.8 kg/ on o bu n uel, and equi es
1/20 h pe on o he pul e ize and loading capaci y. I s he mal alue is equi alen o
21000 lb o s eam pe uel on. Is i p o i able o use his uel in he plan ?
Le us e o mula e he p oblem wi h his hi d ype o coal. Le X3 be he numbe o coal
C ons pe hou . Thus
Max 24 X1+ 20 X2 + 21 X3
Subjec o
0.5 X1 + X2 + 0.8 X3 d 12 (smoke)
X1 + X2 + X3 d 20 (load)
1.5 X1 + X2 + 1.2 X3 d 24 (pul e ize )
1200 X1 - 800 X2 + 1000 X3 0 (sulphu )
X1  0, X2  0 and X3 0
The dual p ices o he o iginal p oblem p o ide all he in o ma ion needed o know
i we a e in e es ed in his new coal. I we decide o use one on o coal C, X3 = 1, we
mus ha e he equi ed machine capaci y (loading sys ems and pul e ize ) and ha e he
possibili y o emi smoke and sulphu ha would be gene a ed wi h i . This is equi alen
o educing he igh -hand side o he cons ain s o he o iginal p oblem in he ollowing
way:
0.5 X1 + X2 d (12-0.8) o 11.2 (smoke)
X1 + X2 d (20-1) o 19 (load)
1.5 X1 + X2 d (24-1.2) o 22.8 (pul e ize )
1200 X1 - 800 X2 (0-1000) o –1000 (sulphu )
Ope a ions esea ch in business adminis a ion and managemen
50
The loading sys em allows us o use a on o he new ype o coal, as we ha e spa e
capaci y. We can also emi mo e sulphu , since he la e cons ain also has slack.
The e o e, he oppo uni y cos s o hese wo cons ain s a e ze o.
Howe e , as we can no emi mo e smoke and we do no ha e mo e capaci y in he
pul e ize , we can only bu n a on o new coal C i we do no bu n any coal A and/o B.
In his way we ha e he pul e ize a ailable and he possibili y o emi ing he smoke
needed o bu n a on o coal C.
Speci ically, o bu n one on o coal C we need o educe he use o he pul e ize by
1.2 (dec eases he RHS). As he oppo uni y cos is 14, he esul will cause a dec ease o
1.2 x 14 = 16.8 in he alue o he objec i e unc ion. Simila ly, o bu n a on o coal C,
we ha e o s op emi ing 0.8 kg o smoke om bu ning coal A and B. A educ ion o 0.8
kg o maximun emission o smoke dec eases he alue o he objec i e unc ion by 0.8 x
6 = 4.8. The o al dec ease o he objec i e unc ion alue is equal o hei sum, 21.6 s eam
uni s. Fu he mo e, he addi ional ou pu pe hou ob ained by bu ning one on o coal C
is only 21 uni s. Thus, he ne loss in s eam p oduc ion is 0.6 uni s. The e o e, in hese
condi ions i is no ad an ageous o use coal C and he op imal solu ion emains he same.
2.7. LINEARPROGRAMMINGMODELSOLVINGWITHA
SPREADSHEET
The g aphical solu ion is only possible i he numbe o a iables is no highe han 2
(3?). P oblems wi h mo e a iables will ha e o be sol ed ma hema ically; o example,
by applying he simplex me hod (an e icien algo i hm ha will be explained in chap e
3). As eal p oblems ha e hund eds o housands o a iables and cons ain s, in p ac ice
he p oblem is sol ed using op imiza ion so wa e. Since sp eadshee s a e he mos used
ools in he business en i onmen we will see i s pe o mance o sol ing linea , in ege
and nonlinea p og amming models. Annex 1 explains in de ail he p ocedu e o en e ing
da a o a linea p og amming model and sol ing i in Excel. Table 2.3 p esen s he da a
o he p oblem and he op imal solu ion. The alue o he decision a iables, he objec i e
unc ion and he i s membe o he cons ain s in he op imal solu ion a e p esen ed in
i alics. The emaining da a a e he model coe icien s.
Tables 2.4 and 2.5 a e he epo s gene a ed by he Excel Sol e ool a e sol ing he
model and pick he op imal solu ion and sensi i i y analysis espec i ely. In Table 2.4
you can see he alues o he a iables and he objec i e unc ion a he op imal solu ion,
and he alue o he slack a iables o he cons ain s. The column "S a us" shows
"Binding" o indica e ha in his case he cons ain is checked s ic ly, ie he slack
a iable is ze o and "No Binding" when he slack a iable is posi i e.
Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
51
Table 2.3. Model and Op imal Solu ion o he p oblem o ene gy p oduc ion and pollu ion
con ol
A
B
C
D
E
F
G
H
I
1
ENERGY PRODUCTION AND POLLUTION CONTROL
2
3
Coal A
Coal B
4
S eam p oduc ion in housands o lb/ on
24
20
5
Used
capaci y
LHS
RHS
6
Emission o smoke
kg/h
0.5
1
12

12
7
Loading ins alla ion
1
1
18

20
8
Pul e ize capaci y
1.5
1
24

24
9
Emission o sulphu
1200
-800
9600

0
10
11
Coal A
on/h
Coal B
on/h
To al
S eam
P oduc ion
housand
lb/h
12
12
6
408
Table 2.4. Op imal solu ion o he p oblem o ene gy p oduc ion and pollu ion con ol
Mic oso Excel 14.0 Answe Repo
Objec i e Cell (Max)
Cell
Name
O iginal Value
Final Value
$I$12
To alS eamP oduc ion
0
408
Va iable Cells
Cell
Name
O iginal Value
Final Value
In ege
$E$12
Coal A ( on/h)
0
12
Con in
$F$12
Coal B ( on/h)
0
6
Con in
Cons ain s
Cell
Name
Cell Value
Fo mula
S a us
Slack
$G$6
Emission o smoke kg/h
12
$G$6<=$I$6
Binding
0
$G$7
Loading ins alla ion
18
$G$7<=$I$7
No Binding
2
$G$8
Pul e ize capaci y
24
$G$8<=$I$8
Binding
0
$G$9
Emission o sulphu oxide
9600
$G$9>=$I$9
No Binding
9600
Ope a ions esea ch in business adminis a ion and managemen
52
Table 2.5. Sensi i i y analysis o he p oblem o ene gy p oduc ion and pollu ion con ol
Mic oso Excel 14.0 Sensi i i y Repo
Va iable Cells
Final
Reduced
Objec i e
Allowable
Allowable
Cell
Name
Value
Cos
Coe icien
Inc ease
Dec ease
$E$12
Coal A ( on/h)
12
0
24
6
14
$F$12
Coal B ( on/h)
6
0
20
28
4
Cons ain s
Final
Shadow
Cons ain
Allowable
Allowable
Cell
Name
Value
P ice
R.H. Side
Inc ease
Dec ease
$G$6
Emission o smoke kg/h
12
6
12
4
4
$G$7
Loading ins alla ion
18
0
20
1E+30
2
$G$8
Pul e ize capaci y
24
14
24
4
6
$G$9
Emission o sulphu oxide
9600
0
0
9600
1E+30
Table 2.5 is he sensi i i y analysis. Fi s ly i indica es he ange o e which each
coe icien in he objec i e unc ion can a y wi hou changes o he op imal solu ion. Fo
example, he coe icien o X1, which can inc ease by 6 and dec ease by 14, ie, can be
be ween 10 and 30. I also gi es us he educed cos o a iables, which is an impo an
concep and can be in e p e ed as he amoun ha should imp o e he objec i e unc ion
coe icien o he a iable su icien ly o i o ake a nonze o alue in he op imal
solu ion. In his case, as he a iables ha e a posi i e alue, i s educed cos is ze o. When
he a iable has a posi i e alue, because i has a lowe bound g ea e han ze o, he
in e p e a ion o he educed cos is penal y, in e ms o he objec i e unc ion o in oduce
he a iable in he solu ion.
Secondly he sensi i i y analysis p o ides he ange o a ia ion o he igh -hand side
o he cons ain ha does no change he alue o he oppo uni y cos . Fo example, he
RHS o he es ic ion o smoke wo h 12 kg/hou can be be ween 8 and 16, as i can
inc ease by 4 and dec ease by 4, wi hou changes in he alue o 6 o i s oppo uni y cos .
6 is he inc ease in s eam p oduc ion (objec i e unc ion) o addi ional uni on he RHS,
i.e. pe each kg/hou mo e o smoke ha can be gene a ed. Please ead Annex 1 o
de ailed in o ma ion.
In summa y, o sol e a linea p og amming model wi h Excel, we in oduce he
p oblem da a in da a cells, which co espond o he echnical coe icien s (aij), he
objec i e unc ion coe icien s (Cj) and he igh -hand side o he cons ain s (bi o
RHS). A e a iable cells a e de ined, whe e we ha e he alues o decision a iables,
he linea unc ions a e in oduced ha ep esen he cons ain s and he objec i e
unc ion. The SUMPRODUCT unc ion o he sp eadshee is use ul o in oduce linea
unc ions o he model (objec i e unc ion and cons ain s). The use o ange names in
o mulas is also in e es ing o simpli y he da a en y p ocess and imp o e he
unde s anding o he model (see Annex 1).

Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
53
The ea u es o Excel o sol ing op imiza ion models ha e imp o ed g ea ly in ecen
yea s. In ac , hey ha e inco po a ed la es and ad anced me hods such as gene ic
algo i hms ha we explain in he las chap e o he book. Howe e , i s use is cu en ly
ecommended o sol ing small o medium sized models. Fo models wi h housands o
a iables and cons ain s we conside i mo e app op ia e o use mo e powe ul
op imiza ion so wa e, including essen ial modelling languages o gene a e la ge models.
LINGO and CPLEX a e good choices, hey also ha e he abili y o impo and expo da a
om sp eadshee s and da abases.
2.8.SOLVINGLINEARPROGRAMMINGMODELWITH
OPTIMIZATION SOFTWARE
In his sec ion we highligh he LINDO Sys ems company ha has sold a ma ke ing
op imiza ion so wa e o mo e han wo decades, such as LINGO which inco po a es a
model gene a ion language and op imize s o sol e linea , in ege , nonlinea and
s ochas ic p og amming models. Fu he mo e, LINDO Sys ems has a p og am called
Wha 's Bes which is an add-in o Excel and can sol e linea , in ege , nonlinea and
s ochas ic p og amming models wi h sp eadshee s, use ul o companies ha p e e o use
his so wa e en i onmen . S uden s can download he la es e sion o LINGO and
sol ing examples and case s udies o he book (www.lindo.com). In his websi e manuals
and aining ma e ial such as he book o Linus Sch age a e also a ailable.
The da a inpu o he ene gy p oduc ion and pollu ion con ol p oblem, he solu ion
and sensi i i y analysis ob ained using LINGO a e he ollowing:
MODEL:
!EXAMPLE 1: ENERGY PRODUCTION AND POLLUTION CONTROL;
[OBJ] MAX = 24 * X1 + 20 * X2;
[SMOKE] 0.5 * X1 + X2 <= 12;
[LOAD] X1 + X2 <= 20;
[PULVERIZER] 1.5 * X1 + X2 <= 24;
[SULPHUR] 1200 * X1 - 800 * X2 >= 0;
END
Global op imal solu ion ound a s ep: 5
Objec i e alue: 408.0000
Va iable Value Reduced Cos
X1 12.00000 0.0000000
X2 6.00000 0.0000000
Ope a ions esea ch in business adminis a ion and managemen
54
Row Slack o Su plus Dual P ice
OBJ 408.0000 1.000000
SMOKE 0.0000 6.000000
LOAD 2.0000 0.000000
PULVERIZER 0.0000 14.000000
SULPHUR 9600.0000 0.000000
Ranges in which he basis is unchanged:
Objec i e Coe icien Ranges
Cu en Allowable Allowable
Va iable Coe icien Inc ease Dec ease
X1 24.00000 6.000000 14.00000
X2 20.00000 28.000000 4.00000
Righ hand Side Ranges
Row Cu en Allowable Allowable
RHS Inc ease Dec ease
SMOKE 12.00000 4.000000 4.000000
LOAD 20.00000 INFINITY 2.000000
PULVERIZER 24.00000 4.000000 6.000000
SULPHUR 0.00000 9600.000000 INFINITY
As shown in he inpu da a, we should use he symbol * o mul iplica ion and he
semi colon (;) o indica e he end o a sen ence, which can be a commen , he objec i e
unc ion o a cons ain . Commen s s a wi h exclama ion ma ks (!) and he names o he
objec i e unc ion and cons ain s can be indica ed in b acke s.
As in Excel Sol e we can ge a se ies o epo s a e sol ing he model. Fi s comes
an o e iew o he numbe and ype o a iables, cons ain s and coe icien s.Then he
model p o ides he op imal alue o he objec i e unc ion, which is 408 in his example.
Fo each a iable i indica es he ac i i y le el in he op imal solu ion (X1 =12 and X2= 6)
and he educed cos , which is ze o in his case. The educed cos can be in e p e ed as
he amoun by which he coe icien o he objec i e unc ion o ha a iable should
imp o e o i o ake a alue o he han ze o in he op imal solu ion. Ano he possible
in e p e a ion is o conside he educed cos as he penal y cos o in oducing he a iable
in he solu ion.
Nex , we ob ain he alue o he slack a iables (slack o su plus) o he cons ain s
and hei oppo uni y cos o dual p ice. In his sec ion we can obse e a esul men ioned
ea lie , ha is, he ela ionship be ween hese wo concep s. When he slack a iable o a
cons ain is ze o, i.e., he cons ain is s ic ly me , no mally i s oppo uni y cos will be
o he han ze o. And when he slack is posi i e, he associa ed oppo uni y cos is ze o.
No e ha his is so in all he cons ain s and ha he i s ow is no a cons ain , bu he
objec i e unc ion o he model. Remembe ha he oppo uni y cos is he amoun by
which he objec i e unc ion imp o es pe uni inc ease in he RHS o he cons ain .
Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
55
Thus, o a maximiza ion p oblem when we inc ease he RHS o a cons ain , he new
alue o he objec i e unc ion is gi en by
New op imal alue o Z = Fo me op imal alue + ǻ RHS* (oppo uni y cos o cons ain )
In he case o minimiza ion p oblems, he e m "imp o e" logically in ol es
dec easing, hus he new op imal alue will be
New op imal alue o Z = Fo me op imal alue - ǻ RHS* (oppo uni y cos o cons ain )
The las wo sec ions co espond o he sensi i i y analysis o he objec i e unc ion
coe icien s and RHS o he cons ain s. The i s line indica es ha he anges p o ided
a e hose in which he basis does no change. This concep is explained in chap e 3.
Looking a he i s pa o he able we can say ha he coe icien o X1 in he
objec i e unc ion, which is wo h 24, may inc ease by 6 and dec ease by 14 uni s wi hou
changes in he op imal solu ion. This is wi hou changes in he alue o a iables X1 and
X2. Ob iously i hese alues a e he same and C1, which is wo h 24, inc eases o
dec eases, he alue o he objec i e unc ion ha is C1*X1 + 20*X2 will change
acco dingly.
The lowe pa o he sensi i i y analysis e e s o he a ia ion o he RHS o he
cons ain s. In he i s column we ha e he cons ain name and in he second he alue
in he model (RHS). The hi d column indica es he inc ease o RHS alue and he ou h
column he dec ease, wi hou changing he alue o he oppo uni y cos o he
cons ain . Fo example, he RHS o he pul e ize cons ain is 24 and can inc ease by
ou and dec ease by six. In o he wo ds, i s alue can be be ween 18 and 28 wi hou
changing i s oppo uni y cos which is 14 (dual p ice). In e p e he anges p o ided o
o he cons ain s.
2.9. MODELLING: SOME EXAMPLES
2.9.1. COMMON MISTAKES IN MODELLING
The e a e wo ex eme ways o lea ning o build op imiza ion models, one h ough
knowledge o s anda d examples and o he h ough o mula ing models c ea i ely. The
i s op ion equi es much less analy ical capabili y han he second, bu i is mo e limi ed.
I only se es o sol e eal p oblems ha i s anda d models. Ob iously, in p ac ice he
bes app oach is o in eg a e bo h. The mis akes made in he modelling p ocess can be
classi ied in o h ee ca ego ies:
1. E a a o ypog aphical e o s
2. Making basic o mula ion mis akes
3. App oxima ion e o s
Ope a ions esea ch in business adminis a ion and managemen
56
The i s wo ypes o e o s a e easy o sol e once iden i ied. Typog aphical e o s
a e ha de o ind as he model size inc eases. Howe e , in hese cases ma ix gene a o s
o modelling languages a e commonly used, educing hei incidence. E o ype 2 is a
mo e se ious because i in ol es no ha ing unde s ood he p oblem o he o mula ion
o linea p og amming models.
E o s o ype 3 ha e a mo e sub le cha ac e . In gene al in de eloping a model ha
ep esen s a eal si ua ion we need o do some o m o app oxima ion. Fo example,
ce ain p oduc s a e agg ega ed, he weekdays a e g ouped o cos s ha a e no
p opo ional o he a iable alues a e conside ed linea . To a oid e o s o his ype one
should be able o iden i y hose app oxima ions ha a e accep able.
Op imiza ion so wa e usually has capabili ies o p o iding some da a abou he
model, such as he alues anges o he pa ame e s among o he s. This in o ma ion is
use ul in he iden i ica ion o e o s ype 1. These e o s also end o p o ide solu ions
ha a e ob iously w ong.
Fo mula ion e o s a e much mo e di icul o sys ema ize because he e a e many
ypes. Among he mos common is wha is known as dimensional analysis: he uni s o
all e ms o a es ic ion mus be equal. To a oid his e o i is o en use ul o o mula e
he p oblem in wo ds and hen w i e he associa ed algeb aic o m.
Ano he associa ed e o wi h he measu emen uni s is he use o uni s in such a way
ha e y la ge o e y small numbe s can appea in he same model. This can cause
signi ican ounding e o s. This can be a oided by scaling he model in o de o educe
he di e ence be ween he la ges and he smalles coe icien alue, and make i as small
as possible. Good p o essional op imiza ion so wa e can sol e his p oblem
au oma ically.
Ano he o mula ion e o is called non-simul anei y e o . In linea p og amming all
cons ain s mus be sa is ied simul aneously. We may wan o indica e ha , i a p oduc
is made, i is made o a minimum le el, e.g. 20. And he solu ion indica es i i is made o
no , and i yes, he solu ion will gi e us i s manu ac u e le el. As we shall see, o indica e
hese si ua ions we should no w i e X 20 and X d 0. We need o use an in ege
p og amming model. LINGO can gene a e he equi ed in ege a iables and cons ain s
i you indica e ha his a iable is semicon inuous (See Annex 2).
Finally, we poin ou ha he undamen al cha ac e is ics o a good model o be use ul
in decision-making a e he ollowing: simple, comple e, easy o handle, adap able,
app op ia e o he si ua ion and p oducing ele an in o ma ion o decision-making.
I is ad isable o e- ead he sec ion on Ope a ional Resea ch me hodology explained in
Chap e 1.The nex sec ion p esen s a well-known p oblem o lea n how o o mula e and
sol e models, as well as discussing he esul s ob ained. This lea ning p ocess will
con inue h oughou he book wi h examples and case s udies, many o which s uden s
pe o m wi h he help o he eache in labo a o y sessions.
Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
63
Table 2.9. Technical cha ac e is ics o aw ma e ials and die equi emen s
Cha ac e is ics
Raw ma e ials Needs
Al al a
Ba ley
Wild
Ba ley
Soy
Sun lowe
S aw
C1
C2
Fib e
uni s/kg
0.15
1
0.18
1.05
0.88
0.3
>=6.3
>=8.6
D
iges ible
P o ein
/Kg
0.02
0.06
0.04
0.4
0.28
0.01
>=0.66
>=0.75
D y
M
a e ial
/Kg
0.22
0.85
0.25
0.9
0.93
0.9
8.8
-
11.6
8-
13
COST
(eu os
/Kg)
0.14
0.30
0.08
0.60
0.42
0.12
CASE STUDY 2: A FEED PROBLEM
A mul ina ional company in he ood sec o has se e al eed ac o ies in he coun y.
The eed o mula ions which he company manu ac u es and dis ibu es is calcula ed
e e y mon h in he cen al headqua e s aking in o accoun he p ices and a ailabili y o
aw ma e ials. Table 2.10 shows he da a o sol e a small example o his eal p oblem.
The company needs o calcula e he op imal o mula ion in o de o minimize he
cos o eed o a ce ain ype o animal, whose nu i ional equi emen s a e he ollowing:
The eed mus ha e a p o ein pe cen age be ween a minimum o 12% and a maximum o
15%, while he minimum le els o calcium and phospho us should be 1 and 0.30%
espec i ely.
Table 2.10. Cha ac e is ics o aw ma e ials and eed equi emen s
Cha ac e is ics
Co n
Whea
Ba ley
Al al a
P ice (eu os/ on)
142
134
125
108
P o ein %
8.5
11
11
17
Phospho us %
0.27
0.35
0.37
0.30
Calcium %
0.02
0.04
0.06
1.77

Ope a ions esea ch in business adminis a ion and managemen
64
1. P opose a model o de e mine he op imal o mula ion in o de o minimize he
eed cos
2. Resol e he model using Sol e ool om Excel and LINGO.
3. Indica e he o mula ion and he minimum cos o eed.
4. Wha a e he exac pe cen ages o p o ein, calcium and phospho us o he
ob ained eed?
5. The company needs o buy mo e ba ley, bu he p ice has inc eased by 10
eu os/ on. In his si ua ion, should he eed be manu ac u ed wi h he same aw
ma e ials which he op imal solu ion indica es?
6. The pu chasing manage upda es ma ke p ices and obse es ha p ices o co n
and whea ha e dec eased sligh ly, exac ly 4 eu os/ on in bo h cases. Would his
new si ua ion a ec p oduc ion policy and he e o e also he pu chase o aw
ma e ials?
7. The mul ina ional company has launched an en i onmen al p og am which is a
pa o he co po a e social esponsibili y, in o de o educe pollu ion caused by
mea p oduc ion. They a e commi ed o manu ac u ing he eeds wi h p o ein
quan i ies ha a e close o animals’ equi emen s. The e o e, hey ha e p oposed
educing he maximum pe cen age o p o ein o 14.5%. Would his decision
a ec he o mula ion and cos o eed? Wha happens i he p oposal is 13%? I
possible, indica e he o mula ion and cos o eed in bo h cases om sensi i i y
analysis.
8. Analyse he di e ences i he e a e any, be ween he in o ma ion gi en by Excel
and LINGO.
CASE STUDY 3: PRODUCTION PROBLEM
A company manu ac u es h ee p oduc s A, B and C. The h ee p oduc s sha e ou
machines M1, M2, M3 and M4 in hei p oduc ion p ocess. Fo p oduc A we need h ee
ope a ions on machines M1, M3 and M4, o p oduc B only wo ope a ions on machines
M1 and M3 o on machines M2 and M4 a e needed, and p oduc C can be manu ac u ed
using machines M1 and M3 o machines M2, M3 and M4.
The ime equi ed in minu es pe uni p oduced o each p oduc ion possibili y on each
machine, he a iable cos o p oduc ion pe minu e, he daily capaci y o each machine
and he minimum daily demands o he h ee p oduc s a e p esen ed in he ollowing
Table.
The objec i e consis s o de e mining he p oduc ion scheme ha minimizes he
o e all a iable cos . Sol e his p oblem wi h LINGO and answe he ollowing
ques ions.
Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
65
1. How many uni s o each p oduc a e manu ac u ed in each p ocess and wha is he
o e all cos ?
2. Which machines ha e idle capaci y and wha a e hese capaci y?
3. I i we e possible o add an ex a ime o hal an hou pe day on machine M1, wha
e ec would i ha e on he o e all p oduc ion cos ?
4. I demand o p oduc B we e 40 uni s, wha e ec would i ha e on he o e all
p oduc ion cos ?
5. Wha can you say abou he e ec on he o e all cos in he case o an inc ease in
demand o C om 10 o 12 daily uni s?
6. The company has ecei ed an o de o p oduce 5 uni s pe day o a new p oduc , D.
Each uni o D equi es 2 min on machine M1, 12 min on machine M2 and 6 min on
machine M3. The ne p o i pe uni o D is 25 money uni s. Should his p oduc be
manu ac u ed? Jus i y you answe . In case o an a i ma i e answe , wha would he
new alue o he objec i e unc ion be wi hou sol ing he p oblem again? Please use
he oppo uni y cos concep . Finally, check i he esul indica ed is co ec .
Table 2.11. Technical and economic da a
P oduc
P ocess
Time (min/uni )
Mini
mum
daily demand
M1
M2
M3
M4
A
1
10
6
3
36
B
B1
1
8
10
45
B2
2
6
9
C
C1
1
8
16
10
C2
2
10
3
8
Va iable cos pe min (mu)
40
50
24
30
Daily capaci y in min
480
480
480
480
CASE STUDY 4: PRODUCTION PROBLEM
A company is planning he apple picking and p oduc ion o cide o he nex
season. I manu ac u es se e al cide p oduc s (na u al, ex a, b u , black label, e c.)
ha di e in he mix u e o apple a ie ies, which can be g ouped as swee , sou o
bi e . The p oduc ion p ocess has se e al phases: p essing, mace a ion, slow
e men a ion, cla i ica ion and s abiliza ion, bo ling and labelling. The p ocess yield
is high and p oduces 0.8 li es cide pe kilo o apples.
The company has buil a linea p og amming model o be able o de e mine how
many apples o each a ie y i should buy o p oduce 40,000 li es o na u al cide and
10,000 li es o ex a cide . Table 2 shows he cha ac e is ics o he apple a ie ies
Ope a ions esea ch in business adminis a ion and managemen
66
and o he cide p oduc s. The deg ee o acidi y o he cide mus be wi hin he ange
indica ed in he able, as mus he suga s in he case o he ex a cide . The objec i e
is o minimize he company p oduc ion cos s.
Table 2.12 Cha ac e is ics o he apple a ie ies and ypes o cide
Cha ac e is ics
Apple a ie y
Cide p oduc s
1
2
3
Na u al
Ex a
Deg ees o
alcohol %
8
6
.5
4
.2
7 4.
8
Vola ile acidi y
g
/ li e 1.
3
2
.1
1
.4
1
.2 - 2
0.
7 – 1
.6
To al Acidi y
g / li e
2.
2
4
3
.5
3
– 4
.5
3
.5 - 4
Suga s g / li e
70
45
55
-
50
- 60
P ice eu os/kg.
0.
4
0.
35
0
.3
MODEL:
! Cide p oduc ion;
! VARIABLES: V1j, V2j y V3j Kg. Apples o a ie y 1,2 o 3 needed
o p oduce cide j (N=Na u al y E=Ex a);
[OBJECTIVE_FUNCTION] MIN=0.4*(V1N + V1E) + 0.35*(V2N + V2E) +
0.3 *(V3N + V3E);
! Cons ain s;
[Deg eesA_Na u al] 0.8*(8*V1N + 6.5*V2N + 4.2*V3N) = 7*40000;
[Vola ileA_Min_Na u al] 0.8*(1.3*V1N + 2.1*V2N + 1.4*V3N) >= 1.2*40000;
[Vola ileA_Max_Na u al] 0.8*(1.3*V1N + 2.1*V2N + 1.4*V3N) <= 2*40000;
[To alA_Min_Na u al] 0.8*(2.2*V1N + 4*V2N + 3.5*V3N) >= 3*40000;
[To alA_Max_Na u al] 0.8*(2.2*V1N + 4*V2N + 3.5*V3N) <= 4.5*40000;
[Quan i y_Na u al] 0.8*(V1N + V2N + V3N) = 40000;
[Deg eesA_Ex a] 0.8*(8*V1E + 6.5*V2E + 4.2*V3E) = 4.8*10000;
[Vola ileA_Min_Ex a] 0.8*(1.3*V1E + 2.1*V2E + 1.4*V3E) >= 0.7*10000;
[Vola ileA_Max_Ex a] 0.8*(1.3*V1E + 2.1*V2E + 1.4*V3E) <= 1.6*10000;
[To alA_Min_Ex a] 0.8*(2.2*V1E + 4*V2E + 3.5*V3E) >= 3.5*10000;
[To alA_Max_Ex a] 0.8*(2.2*V1E + 4*V2E + 3.5*V3E) <= 4*10000;
[Suga s_MinEx a] 0.8*(70*V1E + 45*V2E + 55*V3E) >= 50*10000;
[Suga s_MaxEx a] 0.8*(70*V1E + 45*V2E + 55*V3E) <= 60*10000;
[Quan i y_Ex a] 0.8*(V1E + V2E + V3E) = 10000;
END
Chap e 2. Fo mula ing and sol ing linea p og amming models: basic concep s
67
Global op imal solu ion ound.
Objec i e alue: 22246.38
In easibili ies: 0.000000
To al sol e i e a ions: 10
Va iable Value Reduced Cos
V1N 16666.67 0.000000
V1E 0.000000 0.1739130E-01
V2N 33333.33 0.000000
V2E 3260.870 0.000000
V3N 0.000000 0.2666667E-01
V3E 9239.130 0.000000
Row Slack o Su plus Dual P ice
FO 22246.38 -1.000000
Deg eesA_Na u al 0.000000 -0.4166667E-01
Vola ileA_Min_Na u al 25333.33 0.000000
Vola ileA_Max_Na u al 6666.667 0.000000
To alA_Min_ Na u al 16000.00 0.000000
To alA_Max_Na u al 44000.00 0.000000
Quan i y_Na u al 0.000000 -0.1666667
Deg eesA_Ex a 0.000000 -0.2717391E-01
Vola ileA_Min_Ex a 8826.087 0.000000
Vola ileA_Max_Ex a 173.9130 0.000000
To alA_Min_Ex a 1304.348 0.000000
To alA_Max_Ex a 3695.652 0.000000
Suga s_MinEx a 23913.04 0.000000
Suga s_MaxEx a 76086.96 0.000000
Quan i y_Ex a 0.000000 -0.2608696
Ranges in which he basis is unchanged:
Objec i e Coe icien Ranges:
Cu en Allowable Allowable
Va iable Coe icien Inc ease Dec ease
V1N 0.4000000 INFINITY 0.1739130E-01
V1E 0.4000000 INFINITY 0.1739130E-01
V2N 0.3500000 0.1052632E-01 INFINITY
V2E 0.3500000 0.1052632E-01 INFINITY
V3N 0.3000000 INFINITY 0.2666667E-01
V3E 0.3000000 INFINITY 0.2666667E-01
Righ hand Side Ranges:
Cu en Allowable Allowable
Row RHS Inc ease Dec ease
Deg eesA_Na u al 280000.0 13333.33 12500.00
Vola ileA_Min_Na u al 48000.00 25333.33 INFINITY
Vola ileA_Max_Na u al 80000.00 INFINITY 6666.667
To alA_Min_ Na u al 120000.0 16000.00 INFINITY
To alA_Max_Na u al 180000.0 INFINITY 44000.00
Quan i y_Na u al 40000.00 1197.605 1355.932
Deg eesA_Ex a 48000.00 571.4286 6000.000
Vola ileA_Min_Ex a 7000.000 8826.087 INFINITY
Vola ileA_Max_Ex a 16000.00 INFINITY 173.9130
To alA_Min_Ex a 35000.00 1304.348 INFINITY
To alA_Max_Ex a 40000.00 INFINITY 3695.652
Suga s_MinEx a 500000.0 23913.04 INFINITY
Suga s_MaxEx a 600000.0 INFINITY 76086.96
Quan i y_Ex a 10000.00 1038.576 326.4095
Ope a ions esea ch in business adminis a ion and managemen
68
1. Indica e he minimum cos o p oduc ion and he quan i y o apples o each a ie y ha
he company should buy o he nex pe iod.
2. Wha is he alue o alcohol in deg ees, he ola ile and o al acidi y in he na u al cide ,
p oduced acco ding o op imal solu ion o he model?
3. The na u al cide is p oduced using apple a ie ies 1 and 2. Why is a ie y 3 no used
o make na u al cide ? Unde wha condi ions which would i be in e es ing o use a ie y
3 o p oduce na u al cide ?
4. Wha would he op imal solu ion be i he p ice o a ie y 1 was 0.45 eu os/kg? And
wha would happen i he p ice was 0.39 eu os/kg?
5. Will he op imal solu ion change i he alcohol deg ee o na u al cide dec eases o 6.8
%? Wha happens i he alue is 6%? Wha he changes and wha alues emain he same
in bo h cases?
6. Wha would be he e ec on he op imal solu ion i he maximum le el o suga s is
55g /li e in he ex a cide ?

CHAPTER
3
GENERAL METHODS OF
LINEAR PROGRAMMING
3.1. BASIC CONCEPTS: CORNER-POINTS AND BASIC SOLUTIONS 71
3.2. THE SIMPLEX METHOD ........................................................................... 75
3.2.1. GENERAL CONCEPTS ............................................................................. 75
3.2.2. THE SIMPLEX METHOD BY SIMULTANEOUS EQUATIONS ............ 75
3.2.3. CRITERIA OF THE SIMPLEX METHOD: ENTERING A BASIC VARIABLE
AND A LEAVING BASIC VARIABLE ......................................................... 78
3.2.4. SIMPLEX TABLEAU .................................................................................. 81
3.3. INITIAL BASIC FEASIBLE SOLUTION AND ARTIFICIAL
VARIABLES. THE TWO-PHASE METHOD ..................................... 85
3.4. SIMPLEX ALGORITHM WITH BOUNDED VARIABLES ............. 89
3.4.1. LOWER BOUND TECHNIQUE .............................................................. 89
3.4.2. UPPER BOUND TECHNIQUE .............................................................. 93
3.5. THE REVISED SIMPLEX METHOD, THE INTERIOR-POINT
ALGORITHM AND THE OPTIMIZATION SOFTWARE .................. 99
3.6. SUMMARY ...................................................................................................... 102
3.7. SELECTED REFERENCES ........................................................................ 103
3.8. CASE STUDIES .............................................................................................. 104
Chap e 3. Gene al me hods o linea p og amming
71
In he p e ious chap e we g aphically sol ed a linea p og am wi h wo a iables o
in oduce he basic concep s o linea p og amming in he mos comp ehensible and
in ui i e way possible. Howe e , in p ac ice, p oblems usually ha e mo e a iables and
cons ain s and he e o e we need some ma hema ical ools o ind he op imal solu ion.
Fo una ely, we ha e a e y e icien algeb aic echnique: he Simplex Me hod de eloped
by Geo ge Dan zig in 1947. The simplex me hod is an amazing algo i hm which ecei ed
a compe i o in oduced in 1984 (in e io poin algo i hm o Ka ma ka ) ha seemed o
eplace i . Howe e , his compe i o has no so a ul illed he expec a ions ha i had
ini ially aised. Today he simplex me hod emains he basis o so wa e ha sol es linea
p og amming models in he business sec o , bo h la ge and small. Only in he case o e y
la ge models would he in e io poin algo i hm be p e e able and hen in combina ion
wi h he simplex me hod.
This chap e s a s wi h he de ini ions o he basic concep s o gene al linea
p og amming echniques, ha is, con ex se s, co ne -poin s and basic solu ions. We will
hen explain he Simplex me hod and he dual phase me hod as well as echniques wi h
bounded a iables.
We will end he chap e wi h a b ie e e ence o he e ised simplex me hod and he
la es de elopmen s in linea p og amming. P o essional business manage s need o know
he basics o he me hods o sol ing linea p og amming. This knowledge acili a es he
o mula ion o models and he in e p e a ion o he solu ions, imp o ing decision making.
In addi ion, he simplex algo i hm and i s ex ensions a e he basis o sensi i i y analysis,
as well as o he op imiza ion echniques ha we will see in ollowing chap e s such as
in ege p og amming, mul iobjec i e p og amming and nonlinea p og amming.
3.1. BASIC CONCEPTS: CORNER-POINTS AND BASIC SOLUTIONS
We will con inue using he p oduc ion model o a powe plan as desc ibed in he
p e ious chap e . Fo now, we will simply conside wo o he ou o iginal cons ain s.
Speci ically, he p oblem will consis o inding he alues o he decision a iables X1
and X2 ha
(1) Maximize 24 X1+ 20 X2
and e i y he cons ain s
X1

0 and X2

0
0.5 X1 + X2
d
12 (smoke)
1.5 X1 + X2
d
24 (pul e ize )
Ope a ions esea ch in business adminis a ion and managemen
72
Figu e 3.1 shows he nonnega i i y condi ions o he a iables and cons ain s o his
p oblem. As we al eady know, he se o poin s (X1, X2) ha mee all cons ain s o m he
easible egion.
The easible egion o a linea p og amming model is a con ex se .
A se is con ex when, be ween wo gi en poin s, all midpoin s also belong o he se .
This is a cha ac e is ic o he easible egion o any linea p og amming model and i is
he p inciple o he solu ion p ocedu e known as simplex algo i hm. Ano he key concep
is ha o co ne -poin s, which a e he e ices o he polygon ha o ms he easible
egion (in he case o wo a iables).
In he p e ious chap e , we ha e also in ui i ely seen ha i a linea p og amming
model has a ini e op imal solu ion, a leas one co ne -poin o he easible egion will be
op imal. Figu e 3.1 shows ha he co ne -poin s o he p oblem a e A, B, C and D. How
a e hese poin s gene a ed algeb aically? Fi s , we o mula e he linea p og amming
model (1) in he s anda d o m by en e ing he slack a iables X3 and X5 o main ain he
no a ion o he o iginal p oblem.
(2) 0.5 X1 + X2 + X3 = 12 (smoke)
1.5 X1 + X2 + X5 = 24 (pul e ize )
No e ha now each co ne -poin o he easible egion can be ob ained by se ing wo
a iables o ze o and sol ing he esul ing se o equa ions (2). Fo example, poin C,
which co esponds o he op imal solu ion, is ob ained by se ing X3 and X5 o ze o. When
sol ing he esul ing sys em o wo equa ions wi h wo unknown quan i ies we ob ain
X1=12 and X2=6. We can e i y his esul and ob ain he alues o he a iables o
poin s A, B and D.
Howe e , he selec ion o a iables o be se o ze o in o de o ob ain he co ne poin s
is no a bi a y. I we se X1 and X5 o ze o we ob ain he poin E (X2=24 and X3 = -12).
This solu ion is no easible as X3 is nega i e and he e o e no a co ne poin . Howe e ,
any easible solu ion ob ained by his p ocedu e is a co ne poin and ice e sa.
A simple me hod o de e mine he alues o he a iables in he co ne poin s is as
ollows. I we exp ess he i s cons ain (2) in e ms o X1 and he slack a iables, and
he second in e ms o hese la e and X2 we ob ain he ollowing equa ions
(3) X1 - X3 + X5 = 12
X2 + 1.5 X3 - 0.5 X5 = 6
Chap e 3. Gene al me hods o linea p og amming
79
ou housand pounds. This is he case, because when inc easing he alue o X2 by one
uni he objec i e unc ion inc eases by 20, bu X3 and X1 dec ease by 2/3, which causes
a dec ease o he objec i e unc ion o (2/3) C3 + (2/3) C1 = (2/3) 24 = 16. The e o e, 20
- 16 = 4 is he ne e ec due o he changes o le els o ac i i y o he basic a iables
when a uni o he en e ing basic a iable is inc eased.
Rega ding ou p oblem, we can add ha he basic solu ion co esponding o (8)
consis s o bu ning 16 ons o coal A, no hing o B, he ull capaci y o he pul e ize
machine has been eached (i s slack a iable X5 is ze o) and we can s ill inc ease he
emission o smoke by 4 mo e uni s. When conside ing whe he o bu n coal B, we ha e
o educe he quan i y o coal A o ha e he necessa y capaci y in he pul e ize o bu n 1
on o coal B. As we can see in (5), 1 on o coal A only equi es 3/2 uni s o he pul e ize
and 1 on o coal B, 1 uni , he e o e o pul e ize one on o coal B i is necessa y o
dec ease he bu ning o coal A by 2/3.
The p e ious easoning is based on he use o sca ce esou ces, howe e , i can be
gene ally applied o any ype o a iables and cons ain s. The educed coe icien o he
objec i e unc ion (Cj - Zj) always ep esen s he a ia ion o he objec i e unc ion pe
en e ing nonbasic a iable uni . I i is posi i e, i will inc ease he alue o he objec i e
unc ion and i i is nega i e i will dec ease his alue. The educed cos o he basic
a iables is always ze o.
When he e a e se e al nonbasic a iables in a basic solu ion ha inc ease Z (i we
a e maximizing), one app oach is o selec he en e ing basic a iable wi h he bes uni a y
imp o emen . When he e is no posi i e educed coe icien , we will no be able o
imp o e Z and he e o e, we ha e eached he op imal solu ion.
CRITERION TO CHOOSE THE ENTERING BASIC VARIABLE
The en e ing basic a iable is he a iable wi h he highes (Cj-Zj) alue
(Maximiza ion).
OPTIMALITY CRITERION
A easible basic solu ion is op imal i any (Cj-Zj)
d
d
0 o he nonbasic a iables
(Maximiza ion).
P e iously, we ha e seen ha a minimiza ion p oblem, Min Z, can be exp essed as a
maximiza ion Max (-Z) p oblem. Howe e , he simplex c i e ion can also be modi ied
con enien ly. Thus, he en e ing basic a iable would be he one which has he smalles
(Cj-Zj), and he op imali y c i e ia ha (Cj-Zj) 0.
Le us now look a wha happens wi h he le els o ac i i y o he basic a iables when
a nonbasic a iable en e s, o example X2 a he second i e a ion. We ha e jus seen how
a uni a y inc emen o X2 causes a dec ease o 2/3, in X3 as well as in X1 as can be seen
in (8). Simila ly, an inc ease o X2=ș in (8) will cause some p opo ional dec ease o he
basic a iables. Conc e ely

Ope a ions esea ch in business adminis a ion and managemen
80
(13) X3 = 4 - Į1 X2 = 4 - 2/3 X2
X
1 = 16 - Į2 X2 = 16 - 2/3 X2
As X2 is inc eased, X1 o X3 will g adually dec ease un il one o hem is ze o. I we
con inue inc easing X2, one o he o he o bo h would be nega i e, he e o e he solu ion
would become an in easible solu ion and we can ne e le his happen. The e o e, he
highes alue ha X2 can ake, main aining easibili y, is
(14) ș = min (4/ 2/3, 16/ 2/3) = 6
i any o hose Įi had been nega i e o ze o, we would ha e no ca ied ou he
co esponding quo ien , since he basic a iable would inc ease i s alue o would emain
wi h he same le el o ac i i y. In his case, he basic a iable would ne e be ze o and,
he e o e, i could no be eplaced by he en e ing basic a iable.
CRITERION FOR THE LEAVING BASIC VARIABLE
Gi en Įi o he en e ing basic a iable, he lea ing basic a iable is he one ha
sa is ies
(15)
ș is he alue o he new basic a iable Xj in he new solu ion.
I he e a e no posi i e Įi, ș can be inc eased wi hou bound because none o he
a iables in he cu en basis will be ze o. As ș inc eases, he alue o he objec i e
unc ion also inc eases. I he en e ing basic a iable does no ha e an uppe bound, he
objec i e unc ion could inc ease o in ini y. This si ua ion is known as unbounded
solu ion.
CRITERION FOR UNBOUNDED SOLUTIONS
I o some nonbasic a iable wi h (Cj-Zj) >0 all he alues Įi a e no posi i e, he
linea p og amming model does no ha e a ini e op imal solu ion.
CHANGE OF BASIS:
When we pass om a basic solu ion BS0 o an adjacen basic solu ion BS1 he
ollowing o mulas indica e how he le els o ac i i y o he basic a iables and he
alue o he objec i e unc ion change:
( alue o he basic a iable Xi)
Di
ș
=
min
o any Di > 0
Chap e 3. Gene al me hods o linea p og amming
81
(16) Xi1 = Xi0 - Įij șj
X
j1 = șj
'
'
Z = șj (Cj -Zj)
The i s equa ion ells us he alue o Xi1 (basic a iable i in he basic solu ion BS1)
when uni s o he nonbasic a iable j (șj) en e in he basis. The coe icien o he equa ion
Įij is hus dec easing he basic a iable i in he abo e solu ion (Xi0) pe uni inc ease in
he nonbasic a iable j.
The inc ease o he objec i e unc ion
'
Z is he numbe o uni s o he en e ing basic
a iable (șj) by i s educed coe icien (Cj-Zj).
3.2.4. SIMPLEX TABLEAU
The calcula ions o he simplex me hod a e ca ied ou in a mo e app op ia e way by
using a able s uc u e known as simplex ableau. Table 3.1 ep esen s he ini ial simplex
ableau co esponding o he co ne -poin A o Figu e 3.1 and equa ions (5).
In he i s column o Table 3.1 we speci y he name o he basic a iables, hen we
ha e a column o each a iable o he linea p og amming model in he s anda d o m,
ano he o he second membe o he cons ain s and inally, a column o speci y he
quo ien be ween he alue o he basic a iable and he Įij coe icien o he en e ing
basic a iable. No e ha he i s ow o he able, co esponding o X3 as basic a iable,
is he i s equa ion o (5), he second ow ha has X5 as basic a iable is he second
equa ion o (5) and, simila ly, he hi d ow o Cj-Zj is he equa ion o he objec i e
unc ion as exp essed in (5). The e o e, i is as i we le Z as a basic a iable in all he
i e a ions o he algo i hm, bu wi h he sign changed. This is why in he cell o column
bi and he ow (Cj-Zj) o he simplex ableau will appea he alue o he objec i e unc ion
will appea wi h he sign changed. No e also ha he coe icien s o he basic a iables
make up he uni ma ix, he e o e, he alues o hese a iables a e hose shown in
column bi.
Applying he en e ing and lea ing c i e ia o he basic a iables, we selec i s X1 as
en e ing basic a iable, as i p oduces he highes uni a y inc ease in he objec i e
unc ion. As lea ing basic a iable, he basic a iable chosen is he i s o be ze o, ha
is, X5. Thus, he new basis will be o med by X3 and X1. I is impo an o no e ha a his
p ecise s ep he algo i hm o he simplex implici ly conside s he nonnega i i y condi ions
o he a iables.
Ope a ions esea ch in business adminis a ion and managemen
82
Table 3.1. Ini ial simplex ableau
BASIC
VAR.
X1
X2
X3
X5
bi
bi/Įi
X3 0,5
1 1 0 12
24
X5 1,5
1 0 1 24
16
Cj - Zj 24
20
0 0 0
Table 3.2. Second simplex ableau
BASIC VAR.
X1
X2
X3
X5
bi
bi/Įi
X3 0 2/3
1 -
1/3
4 6
X1 1 2/3
0 2/3
16
24
Cj - Zj 0 4 0 -
16
-
384
The ollowing s ep consis s o ans o ming he i s ableau in o he canonical o m
co esponding o he new basis. Pi o ow is he ow o he lea ing basic a iable and
pi o column, he column o he en e ing basic a iable. Pi o is he common elemen o
he pi o column and he pi o ow, while he semipi o s a e he emaining elemen s o
he column o he en e ing basic a iable.
Chap e 3. Gene al me hods o linea p og amming
83
Table 3.3. Thi d simplex ableau: op imal solu ion
BASIC VAR.
X1 X
2 X
3 X
5 b
i
X2 0 1 3/2 -1/2
6
X1 1 0 -1 1 12
Cj - Zj 0 0 -6 -14
-408
To se he co esponding ableau o he ollowing basic solu ion in canonical o m i
is necessa y ha he pi o elemen be 1 and all he o he elemen s o he pi o column,
ze o. This is achie ed by applying he ollowing ules when passing om an BS o an
adjacen BS1:
(17)
In summa y, pi o ow ĮIL,j, is ans o med by di iding i by he pi o . The emaining
lines,
D
1 i j, including (Cj-Zj), a e ans o med by sub ac ing he pi o ow ob ained in he
i s place and mul iplied by he co esponding semipi o numbe . Cha 1 shows an
ou line o he s eps o he simplex algo i hm.
Table 3.3 is he simplex ableau o he op imal solu ion. As we al eady knew and as
we can see in his able, he op imal solu ion consis s o using 12 on/h o coal A and 6
on/h o coal B, ob aining a apo p oduc ion o 408 housand pounds. Fu he mo e, his
able p o ides addi ional in o ma ion such as he oppo uni y cos s o he sca ce
esou ces. Wha is he dual p ice o he cons ain o smoke? Wha is i s p ac ical
meaning?
D
1
ij
=
D
1
IL,j
D
ij - SEMIPIVOT
D
IL,j
D
IL,j
D
IL,JE
PIVOT
D
1
IL,j
=
=
Ope a ions esea ch in business adminis a ion and managemen
84
CHART 3.1. SIMPLEX ALGORITM (MAXIMIZATION)


INITIAL FEASIBLE
SOLUTION
BS0
THE ENTERING BASIC
VARIABLE
JE: MAX (C
j
-Z
j
) all j nonbasic a .
(C
j
-Z
j
)=C
j
-
6D
ij
-C
i
(i basic a .)

(C
j
-Z
j
)>0
D
i

JE

>0
NO
NO
OPTIMAL
SOLUTION
UNBOUNDED
SOLUTION
THE LEAVING BASIC VARIABLE
X
0
IL: Min

D
L
j+
CHANGE OF BASE
X
i
=X
i
0
-
T
j
·
D
ij
X
j
=
T
j
'
Z=
T
j
(C
j
-Z
j
)
NEW BASE IN CANONICAL FORM
BS
1

D


IL, j
=
 D
IL, j
/ PIVOT
D

ij
=
D

ij
- SEMIPIVOT ·
D

Il,j

Chap e 3. Gene al me hods o linea p og amming
85
3.3.INITIALBASICFEASIBLESOLUTIONANDARTIFICIAL
VARIABLES. THE TWO-PHASE METHOD.
In he p e ious example we ob ained he basic ini ial solu ion om he slack a iables,
bu many p oblems do no ha e an ini ial solu ion in canonical o m. I he e a e equali y
cons ain s, highe o equal o second non posi i e membe s (=, o bi d 0), he only
addi ional p oblem ou lined is o iden i y he ini ial basic easible solu ion. In his case,
he e is no gua an ee ha a easible solu ion exis s. The e o e, a sys ema ic and e icien
p ocedu e is equi ed o gene a e his basic ini ial and easible solu ion, i i exis s.
One o he ad an ages o he simplex me hod is ha he me hod i sel is able o
gene a e i s own ini ial basic easible solu ion, p o ided ha one exis s. I i does no
exis , he simplex me hod speci ies ha he p oblem does no ha e a solu ion.
When we ha e equali y cons ain s in a model, he e is no slack a iable o his
cons ain ha allows us o ob ain he ini ial basic easible solu ion. We could conside
subs i u ing he equali y cons ain o o he wo, one wi h d and he o he wi h . This
al e na i e is no e y ad isable because i inc eases he numbe o cons ain s o he
p oblem. The echnique o he a i icial a iable is p e e able. This consis s o adding, o
he le side o he cons ain , a ic i ious a iable ha will be called a i icial a iable
and whose only mission is o be he basic a iable o ha cons ain in he ini ial basic
solu ion.
In he case o cons ain s, he slack a iable en e s o be sub ac ed, and i we
mul iplied he equa ion by (-1), we would ind he second membe nega i e and he e o e
wi h an ini ial in easible solu ion. The e o e, in his case we also add an a i icial a iable.
In summa y, when we ha e p oblems wi h = o
cons ain s, an a i icial a iable
is added o each one o he cons ain s o his ype. This new p oblem is called he
augmen ed p oblem. F om he a i icial a iables we ob ain an ini ial basic solu ion ha
is in easible o he o iginal p oblem because he a i icial a iables do no ha e a
meaning in i . The e o e, he i s hing o do is o ind an ini ial basic easible solu ion
o ou eal p oblem, emo ing all he a i icial a iables om he basis. F om his new
basic solu ion we will con inue sea ching o he op imal solu ion.
We will see how he wo-phase me hod allows us o ind he ini ial basic easible
solu ion. This me hod will be explained wi h he ene gy gene a ion example e o mula ed
as a model o minimiza ion o p oduc ion cos s. The addi ional cons ain o ha ing o
p oduce a minimum o 216 housand pounds o apo is added.
(18) Minimize 24 X1+ 15 X2
X
1
0 and X2

0
0.5 X1 + X2
d
12
1.5 X1 + X2
d
24
24 X1 + 20 X2
216
Ope a ions esea ch in business adminis a ion and managemen
86
In he p ocess ha we ollow o ind he op imal solu ion we can dis inguish wo
phases. The i s co esponds o he i e a ions equi ed un il a easible solu ion is ound,
wi hou he a i icial a iables. The second phase consis s o he addi ional i e a ions
pe o med once a easible basic solu ion has been ound un il he op imal solu ion is
eached.
The Two-phase me hod uses wo di e en objec i e unc ions, one in each phase. The
algo i hm s a s by in oducing he a i icial a iables ha a e equi ed o ob ain an ini ial
basic solu ion.
Phase 1:
The simplex me hod is used o sol e he augmen ed linea p og amming whose
objec i e unc ion is he ollowing
(20) Minimize Z = Sum o all o he a i icial a iables
and he cons ain s a e he o iginal cons ain s o he model plus he a i icial a iables
and nonnega i i y cons ain s o all decision and a i icial a iables. The op imal solu ion
ob ained o his p oblem (Z=0) will be a easible basic solu ion o he o iginal p oblem.
Phase 2:
The a i icial a iables a e emo ed, since hei alue is ze o and he simplex is
applied om he easible basic solu ion ob ained a e phase 1 un il he op imal solu ion
is ound. The objec i e unc ion o his phase is ha o he eal p oblem (minimizing he
p oduc ion cos ).
(21) Minimize Z = Objec i e unc ion o he p oblem = 24 X1+15X2
Table 3.4 ep esen s he ini ial simplex ableau o phase 1 o he example o cos
minimiza ion in ene gy p oduc ion. No e ha ow Cj-Zj should be calcula ed om (12).
Tha is
Reduced cos o nonbasic a iable Xj: Cj - Zj = Cj -
6
6
Įij Ci
whe e Cj is he coe icien o he nonbasic a iable in he objec i e unc ion (20). Ci is he
coe icien o he basic a iable i in he objec i e unc ion (20) and Įij is he coe icien
o a iable Xj in he ow i. Fo example,
C1-Z1= C1 – (Į11 C3 + Į21 C5 + Į31 CA i icial ) = 0 – (0.5*0 +1.5*0 +24*1) = -24
Chap e 3. Gene al me hods o linea p og amming
87
Table 3.4. PHASE 1: Ini ial simplex ableau
BASIC VAR.
X1
X2
X3
X5
X6
Xa
bi b
i/Įi
X3
0.5
1
1
0
0
0
12
24
X5
1.5
1
0
1
0
0
24
16
Xa
24
20
0
0
- 1
1
216
9
Cj - Zj
-24
-20
0
0
1
0
-
216
Table 3.5. PHASE 1: Second simplex ableau
BASIC VAR.
X1
X2
X3
X5
X6
Xa
b
i
X3
0
7/12
1
0
1/48
-
1/48
7.5
X5
0
-1/4
0
1
1/16
-
1/16
10.5
X1
1
5/6
0
0
-
1/24
1/24
9
Cj - Zj
0
0
0
0
0
1
0
F om Table 3.4 he logic o he simplex means ha X1 en e s in he basis because i
has he smalles (Cj-Zj) and we a e minimizing he sum o he a i icial a iables. As he e
is only one, we ha e o se i o ze o. When you en e X1 all basic a iables dec ease in
alue. Fo example, X3 dec eases by 0.5 o each X1 uni ha en e s and Xa dec eases by
24. The i s basic a iable ha eaches ze o exi s he basis, being he lea ing basic
a iable, in his case i is he a i icial a iable. The e o e, in one i e a ion we inish phase
1 whose op imal solu ion is shown in Table 3.5.
No e ha Table 3.6, ini ial cha o phase 2, is no hing mo e han he inal ableau o
phase 1 excep ha we ha e emo ed he column o he a i icial a iable and ecalcula ed
he Cj-Zj ow. I is logical ha i should be his way because he objec i e unc ion is now
di e en . Speci ically he objec i e unc ion o he p oblem, i.e. minimize he cos o
p oduc ion (18). By applying he wo-phase me hod i may no be possible o ind a
easible solu ion o he o iginal p oblem. Howe e , he echnique o he a i icial a iables
indica es ha we ha e a si ua ion o his ype. In his example, Table 3.7 co esponds o
he op imal solu ion because no nonbasic a iable can educe he cos , i.e. dec ease he
alue o he objec i e unc ion. In his case, he op imali y c i e ion is ha educed cos s
a e g ea e han o equal o ze o.
Ope a ions esea ch in business adminis a ion and managemen
88
Table 3.6. PHASE 2: Ini ial simplex ableau
BASIC VAR.
X1
X2
X3
X5
X6
bi
bi/Įi
X3
0
7/12
1
0
1/48
7.5
12.
86
X5
0
-
1/4
0
1
1/16
10.
5
X1
1
5/6
0
0
-
1/24
9
10.
8
Cj - Zj
0
-
5
0
0
1
-
216
Table 3.7. PHASE 2: Second simplex ableau: op imal solu ion
BASIC VAR.
X1
X2
X3
X5
X6
bi
X3 -0
.7
0
1
0
0.
05
1.2
X5 0
.3
0
0
1
0.
05
13.2
X2
6/5
1
0
0
-0
.05
10.8
Cj - Zj
6
0
0
0
0.
75
- 162
I he o iginal p oblem does no ha e easible solu ions, hen any op imal solu ion
ob ained in phase 1 o he Two-phase me hod leads o a inal solu ion ha con ains
a leas one a i icial a iable highe han ze o. O he wise, all o hem a e equal o
ze o.
OPTIMALITY CRITERION
The op imal solu ion o he augmen ed p oblem is also op imal o he o iginal
p oblem i he e a e no a i icial a iables wi h non-ze o alues.
I no all o he a i icial a iables a e elimina ed om he basis, he o iginal p oblem
does no ha e a easible solu ion.
Chap e 3. Gene al me hods o linea p og amming
95
Fo he basic solu ion o able 3.13, he only a iable which inc eases he objec i e
unc ion is X2' and, by inc easing i s alue, Y1 inc eases by 3/2 and X4 dec eases by 2
o each addi ional uni in X2'. Thus X4 can each ze o and Y1 can each i s uppe bound.
The la e is wha happens i s and he able co esponding o he nex easible basic
solu ion is a li le mo e complica ed han in p e ious cases as, in addi ion o applying he
o mulae o change he basis (17), o he conside a ions mus be aken in o accoun .
In able 3.14 he alue o he en e ing basic a iable X2' is 2/3. This alue is no
ob ained by di iding bi by he Įi coe icien . In pa icula , 2/3 is wha has o en e in he
basis o X2' o he basic a iable Y1 o each i s uppe bound o 3. Mo eo e as he basic
a iable Y1 eaches i s uppe bound, i is subs i u ed by Y1´as a nonbasic a iable.
The e o e, he coe icien s o column Y1´a e mul iplied by (-1).
Table 3.11. Ini ial simplex ableau
BASIC VAR.
Y1
X2
X3
X4
bi
bi/Įi
X3 2
3
1
0
7
7/3=2.33
X4 2
1
0
1
7
7/1=7
Cj - Zj 4
5
0
0
- 4
Table 3.12. Simplex ableau: i s i e a ion
BASIC VAR.
Y1
X2
'
X3
X4
bi
bi/Įi
X3 2 - 3
1 0 4
4/2=2
X4 2 - 1
0 1 6
6/2=3
Cj - Zj 4 - 5
0 0 - 9
Table 3.13. Simplex ableau: second i e a ion
BASIC VAR.
Y1
X2
'
X3
X4
bi
bi/Įi
Y1 1 -
3/2
1/2
0
2
1/3/2=2/3
X4 0 2 - 1
1
2
2/2=1
Cj - Zj 0 1 - 2
0
-
17

Ope a ions esea ch in business adminis a ion and managemen
96
Table 3.14. Simplex ableau hi d i e a ion: op imum solu ion
BASIC VAR.
Y1' X2' X3 X
4 bi
X2' 2/3 1 - 1/3
0 2/3
X4 - 4/3
0 - 1/3
1 2/3
Cj - Zj - 2/3
0 - 5/3
0 - 17.
66
F om Table 3.14 and aking in o conside a ion (29) and (30) he op imal solu ion is
X1 = 4
X2 = 0.33
Z = 17.66
In b ie , he uppe bound echnique applies he ollowing c i e ia:
VALUE OF THE INCREASING NONBASIC VARIABLE
(31) Xj = șj = min [ȕ, Uj, įj]
Uj = uppe bound o he en e ing basic a iable
The e o e, he basis change can ake place due o h ee di e en si ua ions:
1. ȕ The en e ing basic a iable subs i u es he lea ing basic a iable which
eaches ze o as in he s anda d simplex algo i hm.
2. Uj The en e ing basic a iable eaches i s uppe bound be o e a basic a iable
eaches ze o o i s uppe bound. In his case, Xj has o be eplaced by Xj´ o ice
e sa. The co esponding column mus be mul iplied by (-1) o ob ain he
ollowing simplex ableau, in addi ion o upg ading he alues o he basic
a iables (bi) and o he objec i e unc ion. The new alues o he a iables a e
X
i
DD
i
EE 
min

D
i > 0
base alue Xi - uppe bound Xi
D
i
G 
MIN
D
i
< 0
Chap e 3. Gene al me hods o linea p og amming
97
(32) Xi1 = Xi - Uj Įi
Xj = Uj

Xj´= 0
3. į When inc easing he en e ing basic a iable, one o he basic a iables eaches
i s uppe bound. Fo his eason, in he ollowing able he complemen a y
a iable Xk´ will appea ins ead o Xk o ice e sa and i s column will be
mul iplied by (-1). The nonbasic a iable which is inc eased, Xj subs i u es he
basic a iable Xk. The new alues o he a iables a e
(33) Xk = Uj

Xk´= 0
X
i1 = Xi - į Į i
X
j = į
In his case, in o de o ob ain he new able o he basic solu ion, i is necessa y
o apply he o mulae o he simplex me hod, excep when calcula ing he new
alue o he en e ing basic a iable (į) and change he a iable, and he e o e he
sign o i s co esponding column.
Cha 3.2 ou lines he s eps o he simplex algo i hm wi h uppe bound cons ain s.
No e ha he only di e ence wi h he simplex me hod is in he ule o selec ing he
lea ing basic a iable. In he simplex me hod we choose he one which i s eaches ze o
as he lea ing basic a iable, o a oid an in easible solu ion due o a nega i e a iable. In
he uppe bound echnique we selec he a iable which i s becomes in easible, due o a
nega i e alue o he basic a iable, exceeding he uppe bound o he en e ing basic
a iable o he lea ing basic a iable.
Ope a ions esea ch in business adminis a ion and managemen
98
CHART 3.2. UPPER BOUND TECHNIQUE (MAXIMIZATION)
NO
CHANGE OF BASE
Xj=UjX'j=0
X'i=Xi-U
j·D
i
'Z=Uj(Cj-Zj)
MULTIPLY
x (-1) COLUMN X'j
SIMPLEX
ALGORITM
CHART 3.1.
OPTIMAL
SOLUTION
Xk=UjX'k=0
X'i=Xi-G·D
i
X
j
=
G

D'
ILj
=
D
ILj
/
PIVOT (excep b
IL
)
D'ij=Dij-
SEMIPIVOT·
D'
ILj
MULTIPLY
x (-1) COLUMN X'k
T
j=
G
T
j=U
j
T
j=
E
THE LEAVING BASIC
VARIABLE
IL: TjMin (E,U
j,G)

(Cj-Zj)>0
THE ENTERING BASIC
VARIABLE
JE: MAX (Cj-Zj) all j nonbasic a .
(Cj-Zj)=Cj-6Dij-Ci(i basic a .)
INITIAL FEASIBLE
SOLUTION
BS0
Chap e 3. Gene al me hods o linea p og amming
99
3.5.THEREVISEDSIMPLEXMETHOD,THEINTERIORPOINT
ALGORITM AND THE OPTIMIZATION SOFTWARE
I he simplex algo i hm in i s o m o comple e ableau is analyzed in de ail, as we
ha e desc ibed in sec ions 3.2 onwa ds, we will ealize ha in p oblems wi h many mo e
a iables han cons ain s, we a e upg ading da a a each i e a ion ha a e in ac useless.
Conc e ely he only nonbasic a iable o in e es a each s ep is he en e ing basic a iable.
The e ised simplex me hod main ains he same undamen al logic as he desc ibed
simplex me hod and is no hing o he han a simpli ied e sion ha only calcula es and
s o es he equi ed da a a each momen . I is he e o e a mo e e icien implemen a ion
and he one which is in ac used by op imiza ion so wa e.
The e ised simplex me hod has also ano he impo an aspec in addi ion o he
ad an ages o equi ing less s o age and o en less calcula ion. The compu e can ha e
signi ican ounding p oblems a e pe o ming many i e a ions. This a ec s he alues
Cj-Zj and he a io o he lea ing basic a iable. We could, he e o e, pick a w ong
a iable o en e o lea e he basis. We educe hese ounding e o s o wi hin easonable
limi s by de e mining he in e se o he ma ix o ming he basis ec o s in any i e a ion.
P o essional so wa e ypically in e s his ma ix e e y ew i e a ions and when he
op imali y es is me . Special p ocedu es a e used o s o e and upda e he ma ix o med
by he coe icien s o he basic a iables o i s in e se, which ake in o accoun he
dispe sion o he ma ices helping o co ec e o s, s eamline in e sions and educe
s o age equi emen s.
The impo ance o linea p og amming a he momen is due o he exis ence o an
ex ao dina ily e icien algo i hm: he simplex algo i hm, de eloped by Geo ge Dan zig,
and he a ailabili y o compu e s ha can ca y ou he la ge amoun o necessa y
calcula ions. The heo e ical p ope ies o he algo i hms can be e alua ed h ough he
compu a ional complexi y and coun e examples ha e been c ea ed o demons a e ha he
simplex algo i hm is no polynomial, bu a he i is an exponen ial algo i hm. Al hough
in p ac ice he simplex pe o ms e y well, esea che s ha e con inued o look o
polynomial algo i hms o sol e linea p og amming models.
Na end a Ka ma ka , om he ATT Company, published an a icle in 1984 in which
he announced a new algo i hm o sol e la ge linea p og amming models ha had he
p ope y o being polynomial. Fi s ly, he claimed ha he algo i hm could sol e la ge
models up o 50 imes as e han he simplex me hod. As no de ails o he algo i hm we e
gi en, o copy igh easons, i could no be e i ied i his claim was ue. La e on, some
de ails we e made public and, meanwhile, o he esea che s ha e de eloped applica ions
o he algo i hm ha , so a , ha e p oduced con adic o y esul s.
A he momen , i is no clea which o he wo algo i hms is mo e e icien , al hough
i seems ha in he u u e bo h will be complemen a y in linea p og amming. The bigges
ad an age o he in e io -poin algo i hm is ha he inc ease in he equi ed compu a ional
ime becomes g ea e a a smalle a e han he simplex when he size o he p oblem
Ope a ions esea ch in business adminis a ion and managemen
100
inc eases. On he o he hand, he high p epa a ion ime o Ka ma ka ’s me hod p e en s
i om becoming a s ong compe i o when dealing wi h ela i ely small models (dozens
o hund eds o unc ional cons ain s).
In addi ion, as we will see in he ollowing chap e , he simplex me hod is excellen
o ca ying ou he pos op imali y analysis, while he in e io -poin algo i hm does no
enable one o ca y ou his analysis e icien ly, al hough i ob ains dual p ices. In
summa y, in he u u e i is o eseen ha he simplex will con inue o be used as a s anda d
linea p og amming me hod and Ka ma ka ’s o one o i s e sions o e y la ge
p oblems. As he in e io -poin algo i hm con e ges on he bes solu ion, i is possible
ha a easible solu ion close o he op imal becomes an ini ial solu ion o he simplex
algo i hm, which would allow us o ind he op imal solu ion and ca y ou he sensi i i y
analysis.
Nex we will demons a e wi h an example he app oach o he in e io -poin
algo i hm. The main concep s o he algo i hm a e he ollowing.
Concep 1: To ob ain a easible solu ion ha leads o he op imal solu ion om he
in e io o he easible egion.
Concep 2: To mo e in he di ec ion ha imp o es he alue o he objec i e unc ion
as as as possible.
Concep 3: To ans o m he easible egion in o de o place he cu en ial solu ion
nea he cen e hus allowing a la ge imp o emen when concep 2 is
ca ied ou .
We will see he p e ious ideas wi h he ollowing linea p og amming model and i s
g aphical ep esen a ion:
Max Z = X1 + 2 X2
X1 + X2 d 8
X1 0 X2 0
The algo i hm s a s wi h an ini ial ial solu ion ha should be in he in e io o he
easible egion as in all o he ollowing. Thus, he ini ial solu ion should no be in any o
he h ee s aigh lines ha o m he bounda y o he easible egion (X1 + X2 = 8, X1 = 0,
X2 = 0). (X1, X 2) = (2, 2) a e andomly chosen as an ini ial ial solu ion. Nex , we ha e
o mo e in he di ec ion ha imp o es he alue o he objec i e unc ion as as as
possible. This di ec ion is ha o he g adien o he objec i e unc ion and i is gi en by
he ec o o pa ial de i a i es, ha is (1, 2). No e ha he componen s o his ec o a e
he coe icien s o he objec i e unc ion, as his is a linea unc ion.

Chap e 3. Gene al me hods o linea p og amming
101
The algo i hm begins wi h he linea p og amming model in he s anda d o m
Max Z = X1 + 2 X2
X1 + X2 + X3 = 8
X1 0 X2 0 X3 0
and he ma ix
Max Z = CT X
A X = b
X 0
Figu e 3.2 shows he easible egion o he p oblem, as well as he pa h ha he ial
solu ions ollow un il inding he op imal solu ion (Hillie and Liebe man, 2010).
In his example we ha e seen ha he in e io -poin algo i hm equi es mo e i e a ions
and mo e calcula ions han hose pe o med by he simplex algo i hm and in he end i
only ob ains an app oxima ion o he op imal solu ion. Howe e , we should ake in o
conside a ion ha his algo i hm is designed o la ge p oblems wi h many housands o
unc ional cons ain s. In his case he simplex would ca y ou housands o i e a ions,
while Ka ma ka ’s algo i hm would need a lo less, al hough wi h mo e wo k pe
i e a ion. Cu en ly, he op imiza ion so wa e LINGO inco po a es his me hod (Ba ie
Sol e ), in addi ion o he simplex algo i hm.
In his sec ion we ha e seen ha he linea p og amming so wa e does no use he
ull ableau simplex me hod. The e ised simplex me hod is used because o he lowe
s o age and compu a ion e o . Fu he mo e, he e ised simplex me hod also allows he
pe iodic a oidance o ounding e o s accumula ed o e many i e a ions. The accu acy
o he inal solu ion depends on he ole ances o he p og am o is speci ied by he use .
E o s a e possible due o he way in which he compu e manipula es and s o es decimal
numbe s. Thus, small di e ences om ze o, o example 10 -6, a e conside ed equal o
ze o. These limi s a e called ole ances. The choice is no easy, as he small ole ances
a e di icul o mee and can p omo e e o s. The la ge ole ances can ea many non-ze o
da a as i hey we e ze o.
The accu acy o he solu ion can be imp o ed by app op ia ely scaled inpu da a.
Whene e possible, e y la ge and e y small da a in he same model should be a oided,
because ha inc eases he isk o accumula ion o e o s. The so wa e may ha e op ions
o scale he da a o he p oblem and elimina e in e nal scaling be o e p esen ing he
esul s.
Ope a ions esea ch in business adminis a ion and managemen
102
Figu e 3.2. Pa h o he in e io -poin algo i hm
3.6. SUMMARY
In his chap e we ha e s udied gene al me hods o sol ing any model ha adap s o
he s uc u e o linea p og amming as de ined in chap e 2. Fi s , we ha e de ined he
basic concep s o he solu ion algo i hm pa excellence o Ope a ions
Resea ch/Managemen Science, he simplex me hod. The easible egion o a linea
p og amming model is a con ex se and i i has a ini e op imal solu ion, a leas one
op imal solu ion is a co ne -poin ( easible basic solu ion).
The simplex me hod s a s om a easible basic solu ion and i mo es o ano he
adjacen easible basic solu ion and imp o es he alue o he objec i e unc ion. When
i canno ind a be e adjacen basic solu ion, i means ha i has ound he op imal
solu ion. The c i e ia used by he simplex me hod a e choosing he mos e icien o he
en e ing basic a iable and he i s basic a iable ha eaches ze o o he lea ing basic
a iable.
2864
8
6
4
2
(2.08,4.92)
(2.5,3.5)
(2,2)
0X1
X2
(0,8) óp ima
Chap e 3. Gene al me hods o linea p og amming
103
When all o he cons ain s o he model ha e a smalle han o equal o sign (), he
i s easible basic solu ion is ound om he slack a iables. I his is no he case, we
can apply he a i icial a iable echnique o ob ain an ini ial solu ion and la e use he
wo-phase me hod o ind he op imal solu ion.
In many models he a iables a e uppe and lowe bounded. By applying he simplex
echniques wi h bounded a iables we a oid ha ing o inc ease he numbe o
unc ional cons ain s o he p oblem. In he case o lowe bounds, i is only equi ed o
make a change in he a iable, while o a iables wi h uppe bounds i is also necessa y
modi y he selec ion o he a iable ha lea es he basis a each i e a ion. The inc ease in
e iciency is so conside able ha he op imiza ion so wa e ecommends iden i ying he
bound cons ain s as his special ype o as many a iables as possible.
We ha e also commen ed on he mos e icien way o implemen ing he simplex, he
e ised simplex, which is no hing o he han a e sion o he simplex in which only he
necessa y da a a e calcula ed and s o ed a each i e a ion. In addi ion, his me hod allows
he educ ion o ounding e o s. Las ly, he basic concep s o he la es de elopmen s
ega ding linea p og amming sol ing echniques ha e been desc ibed, in pa icula he
in e io -poin algo i hm. This s a s om a poin in he in e io o he easible egion
and i shi s in he di ec ion in which he objec i e unc ion is imp o ed he quickes way,
while main aining easibili y. This p ocess con e ges o he op imal solu ion. I is
p edic ed ha i will be used in combina ion wi h he simplex o la ge models wi h many
housands o unc ional cons ain s. Cu en ly, he op imiza ion so wa e LINGO
inco po a es i (Ba ie Sol e ).
3.7. SELECTED REFERENCES
1. Daellenbach, H.G.; Geo ge, J.A. and McNickle, D.C. (1987): In oducción a las
écnicas de In es igación de Ope aciones. CECSA.
2. Hillie , F.S. and Liebe man G.J. (2010): In oduc ion o Ope a ions Resea ch. Nin h
Edi ion. McG aw-Hill.
3. Hillie , F.S and Hillie , M.S. (2011): In oduc ion o Managemen Science. A
Modelling and Case S udies App oach wi h Sp eadshee s. Fou h Edi ion. McG aw-
Hill.
4. LINDO Sys ems (2011): LINGO. The modeling language and op imize .
5. Wins on, W. L. and S.C. Alb igh (2012): P ac ical Managemen Science. Fou h
Edi ion. Sou h-Wes e n. USA.
Ope a ions esea ch in business adminis a ion and managemen
104
3.8. CASE STUDIES
CASE STUDY 1
Sol e he p oduc ion planning model o sec ion 3.4.1 wi hou conside ing he cons ain s
o minimum demand, and applying he simplex algo i hm. Then answe he ollowing
ques ions om he inal simplex ableau.
1. Indica e he op imal solu ion.
2. A e all esou ces comple ely used? I he e a e idle esou ces, indica e which ones
and in wha quan i y.
3. The company is conside ing edis ibu ing he esou ces be ween di e en
depa men s. Analyze he con enience o he ollowing al e na i es and i you
conside ha he e is a be e one, indica e i . Explain you easoning.
a) T ans e 25 h/week om depa men 4 and 5 h/week om depa men 5 o
depa men 3.
b) T ans e 25 h/week om depa men 4 and 5 h/week om depa men 5 o
depa men 1.
c) Reduce he hou s in depa men s 2 and 5.
4. Indica e he educed cos s o he a iables and dual p ice o he cons ain s, and
analyze he ela ionship o hese wi h he slack a iables.
CASE STUDY 2
Gi en he ollowing linea p og amming model
Max Z = 24 X1 + 20 X2
0.5 X1 + X2 d 12
1.5 X1 + X2 d 24
0 d X1 d 15
0 d X2 d 10
1. Ob ain he op imal solu ion by means o he g aphic me hod.
2. Ob ain he op imal solu ion by means o he simplex algo i hm.
3. Find he op imal solu ion by applying he uppe bound echnique.
CHAPTER
4
DUALITY AND SENSITIVITY
ANALYSIS
4.1. THE DUAL PROBLEM AND PRIMAL-DUAL RELATIONSHIPS. 113
4.1.1. THE PRIMAL PROBLEM AND THE DUAL PROBLEM ......................... 113
4.1.2. PRIMAL-DUAL RELATIONSHIPS .......................................................... 114
4.2. DUAL SIMPLEX ALGORITHM ............................................................... 116
4.3.SENSITIVITYANALYSISOFTHECOEFFICIENTS
2)7+(OBJECTIVE FUNCTION ........................................................... 119
4.3.1. MODIFICATION OF A CJ CORRESPONDING TO A NONBASIC
VARIABLE .................................................................................................. 120
4.3.2. MODIFICATION OF A CJ CORRESPONDING TO A BASIC
VARIABLE ................................................................................................. 121
4.3.3. SIMULTANEOUS MODIFICATIONS OF SEVERAL COEFFICIENTS... 121
4.4. SENSITIVITY ANALYSIS OF THE RIGHT-HAND SIDE OF THE
CONSTRAINTS ............................................................................................... 123
4.5. PARAMETRIC LINEAR PROGRAMMING .......................................... 126
4.6. SUMMARY ...................................................................................................... 128
4.7. SELECTED REFERENCES ........................................................................ 128
4.8. CASE STUDIES .............................................................................................. 129

Chap e 4. Duali y and sensi i i y analysis
113
One hypo hesis in linea p og amming is he ce ain y wi h espec o model pa ame e s.
In p ac ice, model pa ame e s a e usually es ima es. The e o e, when we ha e ound he
op imal solu ion o a p oblem, we ha e o analyze he e ec s o modi ying he
coe icien s on he p oblem solu ion. Fo example, p ices change wi h ime and we may
ha e used a e age p ices in he model. In such a case, i would be necessa y o e alua e
whe he he op imal solu ion would change i he p ice changed wi hin he es ima ed
limi s. Fo una ely, in linea p og amming i is e y easy o ca y ou his s udy om
op imal simplex ableaux.
This chap e ocuses on how o ca y ou and in e p e a sensi i i y analysis. Howe e ,
be o e s udying sensi i i y analysis we will in oduce he concep o duali y and he dual
algo i hm, which ha e impo an applica ions in economics. Finally, we will s udy
pa ame ic linea p og amming, since on many occasions he chosen alues o some
coe icien s a e only managing decisions. In his case, i is con enien o analyze he
esponse o he p oblem solu ion o hese decisions.
4.1. THE DUAL PROBLEM AND PRIMAL-DUAL RELATIONSHIPS
The p oblem o de e mining he oppo uni y cos o esou ces is also a linea
p og amming model, which is ac ually he dual p oblem o he o iginal p oblem. Duali y
is no only an in e es ing heo e ical ela ionship. Le 's desc ibe i , as i is he basis o he
concep o oppo uni y cos , o he dual simplex algo i hm and o sensi i i y analysis.
E e y linea p og amming p oblem has ano he linea p og amming p oblem
associa ed wi h i , and be ween hem he e a e e y special ela ionships. Each is he dual
o he o he . We shall illus a e i using he p oblem o p oduc ion planning p esen ed in
sec ion 3.4.1 o chap e 3, wi hou ega ding he demand cons ain s, i.e. he lowe bound
cons ain s o he a iables.
4.1.1. THE PRIMAL PROBLEM AND THE DUAL PROBLEM
x Each p oblem cons ain is associa ed wi h one a iable o he o he p oblem and
ice e sa.
x The echnical coe icien s o each p oblem cons ain a e he same as he echnical
coe icien s o he co esponding a iable in he o he p oblem.
x The cons ain 's igh -hand sides a e he objec i e unc ion coe icien s o he
co esponding a iables in he o he p oblem and ice e sa.
x I we minimize in one p oblem wi h cons ain s and nonnega i e a iables, hen
in he o he p oblem we maximize wi h cons ain s  and nonnega i e a iables.
Ope a ions esea ch in business adminis a ion and managemen
114
The dual p oblem associa ed wi h he p oduc ion planning p oblem is shown in Table
4.1. In his Table we see ha he o iginal p oblem is e e ed o as he p imal p oblem.
No e ha he dual p oblem has 5 a iables, one o each cons ain o he p imal p oblem.
I also has 3 cons ain s, one o each a iable o he o iginal p oblem, howe e , he
objec i e unc ion o he p imal is o maximize and he co esponding objec i e unc ion
o he dual is o minimize. No e ha he signs o he cons ain s a e di e en in bo h
p oblems and ha he echnical coe icien s aij o a cons ain in one p oblem a e he
associa ed a iable in he o he .
Table 4.1. The p imal p oblem and he dual p oblem
ORIGINAL PROBLEM
Resou ce alloca ion
P imal P oblem
NEW PROBLEM
Resou ce p ice alloca ion
Dual P oblem
A, B, C
0
Max 20 A + 18 B + 21 C
0.20 A + 0.10 B + 0.30 C d
160
0.50 A + 0.07 C d
80
0.10 A + 0.30 B + 0.10 C d
80
0.02 A + 0.02 B + 0.02 C d
40
0.05 A + 0.06 B + 0.05 C d
40
W1, W2, W3, W4 ,W5
0
Min 160 W1 + 80 W2 + 80 W3 + 40 W4 + 40 W5
0.20 W1 + 0.50 W2 + 0.10 W3 + 0.02 W4 + 0.05 W5 20
0.10 W1 +0.30 W3 + 0.02 W4 + 0.06 W5 18
0.30 W1 + 0.07 W2 + 0.10 W3 + 0.02 W4 + 0.05 W5
21
4.1.2. PRIMAL-DUAL RELATIONSHIPS
The gene al ela ionships be ween he s uc u es o he p imal and dual p oblems a e
summa ized in Table 4.2. The e a e also ela ionships be ween he solu ions o bo h
p oblems, as indica ed below.
x I bo h he p imal and dual p oblems ha e easible solu ions, hen bo h ha e ini e
op imal solu ions and he op imal Z alues a e equal.
x Complemen a y slackness heo em: I one cons ain o ei he o he wo
p oblems has slack in any op imal solu ion o ha p oblem, hen in he o he p oblem
he a iable associa ed wi h ha cons ain is ze o o any op imal solu ion. I one
a iable o ei he o he wo p oblems is no ze o, hen in he o he p oblem he
associa ed cons ain is s ic ly ul illed. This heo em indica es ha a esou ce
which is no used comple ely has a dual p ice o ze o and a esou ce wi h a dual
p ice di e en om ze o is sca ce.
Chap e 4. Duali y and sensi i i y analysis
115
Table 4.2. Rela ionships be ween p imal and dual p oblems
PRIMAL PROBLEM DUAL PROBLEM
ܯܽݔ݅݉݅ݖ݁ܼൌ෍ܿ
௝
ݔ
௝
௡
௝ୀଵ
ܯ݅݊݅݉݅ݖ݁ܼൌ෍ܾ
௜
ݓ
௜
௠
௜ୀଵ
Coe icien s o Objec i e Func ion RHS Coe icien s
Coe icien s Row i Coe icien s Colum j
Cons ain 
σܽଵ௝ݔ௝
௡
௝ୀଵ ൑ܾଵ
Nonnega i e Va iable
w1 0
Cons ain 
σܽଶ௝ݔ௝
௡
௝ୀଵ ൒ܾଶ
No posi i e Va iable
w2  0
Cons ain =
σܽଷ௝ݔ௝
௡
௝ୀଵ ൌܾଷ
F ee Va iable
-  w3  
F ee Va iable
-  x1  
Cons ain =
σܽ௜ଵݓ௜
௠
௜ୀଵ ൌܿଵ
No posi i e Va iable
x2  0
Cons ain 
σܽ௜ଶݓ௜
௠
௜ୀଵ ൑ܿଶ
Nonnega i e Va iable
x3 0
Cons ain 
σܽ௜ଷݓ௜
௠
௜ୀଵ ൒ܿଷ
Ope a ions esea ch in business adminis a ion and managemen
116
4.2. DUAL SIMPLEX ALGORITHM
The simplex algo i hm s a s om a basic easible solu ion in which e e y Xj 0. I
app oxima es he op imal solu ion main aining easibili y a each i e a ion. When all (Cj-
Zj) d 0 an op imal solu ion o maximizing is ound ((Cj-Zj) 0 o minimizing).
Some imes we ha e ini ial solu ions ha a e in easible in he p imal and easible in
he dual. Tha is, we ha e some Xj d 0, bu all (Cj-Zj) d 0 o maximizing ((Cj-Zj) 0 o
minimizing). The dual simplex algo i hm leads o p imal easibili y, main aining dual
easibili y ((Cj-Zj) d 0).
I is impo an o emphasize he ac ha he dual simplex algo i hm is a me hod used
o sol e any kind o p oblem, ega dless o whe he i is p imal o dual, al hough we ha e
explained he algo i hm using he dual p oblem o he p oduc ion planning model. The
only equi emen is o ha e a in easible p imal and a easible dual solu ion.
Le 's conside he dual p oblem o he p oduc ion planning model, which is he
ollowing:
Min 160 w1 + 80 w2 + 80 w3 + 40 w4 + 40 w5
0.20 w1 + 0.50 w2 +0.10 w3 + 0.02 w4 + 0.05 w5
20
0.10 w1 + 0.30 w3 + 0.02 w4 + 0.06 w5
18
0.30 w1 + 0.07 w2 +0.10 w3 + 0.02 w4 + 0.05 w5

21
w1, w2, w3, w4, w5

0
We denomina e w6, w7 and w8 o he slack a iables o he h ee cons ain s. Table 4.3,
co esponding o he i s simplex ableau, shows ha he slack a iables do no o m he
uni y ma ix. By mul iplying he h ee cons ain s by (-1) we ob ain ha ma ix, bu he
ini ial solu ion is in easible, because on se ing o ze o, w1=w2=w3=w4=w5=0, he slack
a iables ake nega i e alues. We know ha in his ype o si ua ion we can apply he
a i icial a iable echnique. Howe e , in his case we a e going o apply he dual simplex
algo i hm, which esul s om applying he c i e ia o he p imal algo i hm o he
dual p oblem.
CRITERION OF THE SIMPLEX DUAL ALGORITHM 1: LEAVING BASIC
VARIABLE
The lea ing basic a iable Xi is he basic a iable wi h he mos nega i e alue
OPTIMALITY CRITERION
The solu ion associa ed wi h a basic a iable is op imal i e e y Xi
0

Chap e 4. Duali y and sensi i i y analysis
117
CRITERION OF DUAL SIMPLEX ALGORITHM 2: ENTERING BASIC
VARIABLE
The en e ing basic a iable is he a iable wi h he lowes quo ien (Cj-Zj)/ -Į-j i
we minimize and he highes quo ien i we maximize.
Minimiza ion: Min (Cj-Zj)/ -Į-j
Maximiza ion: Max (Cj-Zj)/ -Į-j
As opposed o he simplex algo i hm, i s we ha e o selec he lea ing basic a iable
( he mos nega i e) and hen he en e ing basic a iable, i.e. he a iable capable o
inc easing he alue o he basic a iable in he mos e icien way. In he illus a ing
example, w8 lea es and w1 en e s because w1 is he a iable ha in ol es he lowes
inc ease in he objec i e unc ion pe uni inc ease in w8. When compa ing Table 4.3 wi h
he i s simplex ableau o he p imal p oblem (case s udy 1 in chap e 3), we can see ha
he column o he en e ing basic a iable co esponds o he ow o he lea ing basic
a iable. In he same way, he ow o he lea ing basic a iable in he i s i e a ion o he
p imal p oblem solu ion now co esponds o he column o he en e ing basic a iable.
The pi o elemen is he same, wi h i s sign changed. Table 4.4 and ollowing a e ob ained
applying he same basic change p ocedu es as in he simplex algo i hm, gi en by
equa ions (17) in chap e 3.
Table 4.3. Dual algo i hm: ini ial simplex ableau
BASIC
V.
W1
W2
W3
W4
W5
W6
W7
W8
bi
W6 -0.2
0
-0.5
0
-0.1
0
-
0.02
-
0.05
1
0
0
-20
W7 -0.1
0
0
,00
-0.3
0
-
0.02
-
0.06
0
1
0
-18
W8 -0.3
0
-
0.07
-0.1
0
-
0.02
-
0.05
0
0
1
-21
Cj-Zj 160
80
80
40
40
0
0
0
0
Cj-Zj/-Į-ij
160/0.30
=
533.33
80/0.07
=
1142.8
80/0.1
=
800
40/0.02
=
2000
40/0.05
=
800
Table 4.4. Dual algo i hm: second simplex ableau
BASIC
V.
W1
W2
W3
W4
W5
W6
W7
W8
bi
W6
0
-
0.45
-
0.034
-
0.01
-
0.02
1
0
-
0.66
-
6.14
W7
0
0.02
-
0.27
-
0.01
-
0.04
0
1
-
0.33
-
11.07
W1
1
0.23
0.33
0.07
0.17
0
0
-
3.33
69.93
Cj-Zj
0
42.66
26.67
29.33
13.33
0
0
533.33
-11200
Cj-Zj/- Į-ij
26.
67
/0.27
=
98.77
29.3/0.01
=
2933
13.3/0.04
= 333.25
533.3/0.3
=
1616.5
Ope a ions esea ch in business adminis a ion and managemen
118
Table 4.5. Dual algo i hm: hi d simplex ableau
BASIC
V.
W1
W2
W3
W4
W5
W6
W7
W8
bi
W6
0
-
0.45
0
-
0.01
-
0.02
1
-
0.12
-
0.62
-
4.81
W3
0
-
0.07
1
0.04
0.15
0
-
3.70
1.22
40.96
W1
1
0.25
0
0.06
0.12
0
1.22
-
3.73
56.42
Cj-Zj
0
44.63
0
28.34
9.38
0
98.77
500.73
-12293.38
Cj-Zj/- Į-
ij
99.17
2834
469
823.08
807.63
Table 4.6. Dual algo i hm: op imal simplex ableau
BASIC
V.
W1
W2
W3
W4
W5
W6
W7
W8
bi
W2
0
1
0
0.02
0.04
-
2.22
0.27
1.37
10.58
W3
0
0
1
0.04
0.15
-
0.15
-
3.68
1.3
41.68
W1
1
0
0
0.05
0.11
0.55
1.15
-
3.94
53.77
Cj-Zj
0
0
0
27.42
7.39
99.17
86.80
439.14
-12770
.38
I he ables ob ained a e compa ed wi h he ables ha esul om applying he p imal
simplex algo i hm o he o iginal p oblem, i can be no ed ha he dual algo i hm comes
om applying he simplex c i e ia o he dual p oblem. Howe e , we mus ake in o
accoun ha he dual algo i hm se es o sol e ei he o he wo p oblems, as long as he
ini ial solu ion is in easible p imal and easible dual. We know ha we can also use he
wo-phase me hod o in easible ini ial solu ions, bu in his case i is no necessa y o i
o be easible dual.
I we analyze he ables o he op imal solu ion, bo h o he p imal p oblem and he
dual p oblem, we e i y ha he oppo uni y cos s o he esou ces in he p oduc ion
planning p oblem a e gi en by he dual a iables. We can also see ha only he
comple ely consumed esou ces, i.e. he sca ce esou ces ha e a non-ze o oppo uni y
cos in he op imal solu ion.
When analyzing he s uc u e o bo h linea p og amming models, we can see ha in
he p imal p oblem we de e mine he u iliza ion o esou ces o know wha and how much
o p oduce in o de o maximize he company's bene i s. Tha is, we can app oach he
p oblem om he poin o iew o business p oduc ion o e u ns. On he o he hand, he
dual p oblem conside s he dis ibu ion o sha ing o ha income. The e o e, he dual
Chap e 4. Duali y and sensi i i y analysis
119
objec i e unc ion consis s o minimizing he alue o he esou ces used by he company.
The cons ain s make he alue o he esou ces employed in manu ac u ing one p oduc
uni exceed o equal he p oduc uni ma gin. Does his mean ha he e alua ion o he
esou ces ob ained by he dual p og am o ces he company's bene i o be ze o o
nega i e? No, no a all. The complemen a y slackness heo em allows us o know ha i
one o he cons ain s akes a alue highe han he second membe , hen he associa ed
p oduc would no occu . The e o e, i i cos s mo e o a company o manu ac u e a
p oduc han he bene i s ob ained om i , he company will no be in e es ed in
manu ac u ing ha p oduc .
Dual a iables can be in e p e ed as a mechanism ha allows us o assign he g oss
ma gins o he p oduc s in he di e en esou ces. Ve i y ha he uni a y bene i o A can
be a ibu ed as 54 % o depa men 1, 25.6 % o depa men 2 and 20.4 % o depa men
3. In nonlinea p og amming, a simila esul is ob ained wi h he economic in e p e a ion
o Kuhn-Tucke condi ions.
Finally, we ha e o ake in o accoun ha dual a iables do no always p esen a simple
in e p e a ion. Thei in e p e a ion will depend on he p oblem unde analysis.
4.3.SENSITIVITYANALYSISOFTHECOEFFICIENTSOFTHE
OBJECTIVE FUNCTION
The sensi i i y analysis o he coe icien s o he objec i e unc ion consis s o
analyzing he e ec s o he changes in pa ame e s Cj on he op imal solu ion. In chap e
2 we s udied his e ec g aphically wi h he p oblem o ene gy gene a ion in a he mal
powe plan . Remembe ha changes in one o hese coe icien s causes changes in he
isop oduc ion slope. I he modi ica ion is la ge enough, he op imal solu ion may be
ano he co ne poin o he easible egion (Figu e 2.4). The e o e, changes in he Cj
pa ame e s may a ec he op imali y o he p esen solu ion, ye no a ec i s easibili y.
How will a change in a Cj pa ame e a ec he op imal simplex ableau? Only (Cj-Zj) will
change.
Chap e 2 p esen s he op imal solu ion and sensi i i y analysis o he ene gy
p oduc ion model. The esul s indica e he ange o alues wi hin which a coe icien o
he objec i e unc ion can be changed wi hou changing he basis. The analysis is made
by changing one coe icien each ime, and main aining all o he coe icien s cons an .
Le 's see how hese anges a e de e mined wi h he simpli ied example o ene gy
p oduc ion, i.e. using only he smoke and pul e ize cons ain s, as we did in chap e 3 o
explain he simplex algo i hm. Figu e 4.1 ep esen s he easible egion and he op imal
solu ion o his p oblem. I is necessa y o emphasize ha he op imal solu ion is he same,
bu he easible egion is now he polygon OABC. This easible egion is di e en om
ha o he o iginal p oblem because wo cons ain s ha e been elimina ed.
Ope a ions esea ch in business adminis a ion and managemen
120
As we ha e al eady men ioned, when changing a Cj he only elemen s ha a e a ec ed
in he op imal simplex ableau a e he alues o he Cj-Zj. In o de o de e mine he in e al
o Cj we ha e o ake in o accoun whe he he pa ame e co esponds o a basic o non-
basic a iable.
Figu e 4.1. Feasible egion and op imal solu ion o he simpli ied p oblem o ene gy
p oduc ion
4.3.1. MODIFICATION OF A Cj CORRESPONDING TO A NONBASIC VARIABLE
Le 's see wha happens i we modi y C3 in Table 3.3. No Zj would change, since his
a iable is non basic. The only elemen a ec ed will be i s own Cj-Zj, i.e. C3-Z3, due o
he modi ica ion o C3. The e o e, C3 can be modi ied wi hou changes in he op imal
solu ion, as long as C3-Z3 d 0. As Z3=6, hen C3 d 6. Thus, he ange equi ed is - d C3
d 6.
X2
5 1015202530
5
10
15
20
25
30
X1
0
PULVERIZER
SMOKE
A
B
C
D
OPTIMAL SOLUTION: B
X1=12
X2=6
Z=408
Chap e 4. Duali y and sensi i i y analysis
127
Figu e 4.2. Pa ame ic P og amming o b1: change in he objec i e unc ion and
ac i i y le els o he a iables
8
480
384
30
24
2010
Z
b1
8
24
16
30
24
2010
Z
b1
X2
X1
X1, X2

Ope a ions esea ch in business adminis a ion and managemen
128
The esul s o he pa ame e iza ion a e shown in Figu e 4.2. Bo h g aphs display he
h ee segmen s o he independen e m o he smoke cons ain . The only elemen which
emains cons an in each o hem is he oppo uni y cos , as he objec i e unc ion
changes linea ly, as does he ac i i y le el o he a iables. Obse e ca e ully he
e olu ion o he objec i e unc ion. This linea o m by segmen s and conca e is
cha ac e is ic o pa ame ic p og amming and highligh s he law o dec easing ma ginal
p o i s o he esou ces.
4.6. SUMMARY
We ha e seen ha duali y is he heo e ical basis o he oppo uni y cos and o o he
impo an echniques in Ope a ions Resea ch, such as he dual simplex algo i hm and
sensi i i y analysis. I allows us o e alua e which modi ica ions he pa ame e s o he
model can expe ience wi hou a ec ing he op imal solu ion.
The op imal simplex ableau allows us o calcula e, wi h li le compu a ional cos , he
ange o alues o he coe icien s o he objec i e unc ion ha can be changed
indi idually wi hou changing he op imal ac i i y le els o he a iables. We ha e only
o ake in o accoun ha he Cj-Zj mus emain nega i e (maximiza ion). Simila ly, he
anges o he second membe s o he cons ain s a e de e mined subjec o he condi ion
ha he a iables be nonnega i e. When he changes cause non easibili y, he dual
algo i hm allows us o de e mine he op imal solu ion in an e icien manne .
Finally, we ha e seen ha pa ame ic analysis is jus a gene aliza ion o sensi i i y
analysis ha de e mines how he op imal solu ion e ol es when he pa ame e s o he
model a y o e a wide ange. The dual simplex algo i hm is a basic ool o his kind o
analysis.
4.7. SELECTED REFERENCES
1. Daellenbach, H.G.; Geo ge,J.A. and McNickle,D.C. (1987): In oducción a las
écnicas de In es igación de Ope aciones. CECSA.
2. Hillie , F.S. and Liebe man G.J. (2010): In oduc ion o Ope a ions Resea ch. Nin h
Edi ion. McG aw-Hill.
3. Hillie , F.S and Hillie , M.S. (2011): In oduc ion o Managemen Science. A
Modelling and Case S udies App oach wi h Sp eadshee s. Fou h Edi ion. McG aw-
Hill.
4. Wins on, W. L. and S.C. Alb igh (2012): P ac ical Managemen Science. Fou h
Edi ion. Sou h-Wes e n. USA.
Chap e 4. Duali y and sensi i i y analysis
129
4.8. CASE STUDIES
CASE STUDY 1: DUAL PROGRAM AND DUAL ALGORITHM
1. De elop he dual p og am associa ed wi h he ollowing p imal p og am.
Max 3 X1 + 4 X2 + X3
X1 + 3 X2 + 2 X3
10
6 X1 + 2 X2 + X3
d
30
X1 + X2 + X3 = 5
X1, X2, X3
0
2. Sol e he p imal p oblem o he p e ious sec ion h ough he dual simplex
algo i hm.
3. Ob ain he op imal solu ion o he dual p og am om he esul s ob ained in poin
2.
CASE STUDY 2: SENSIBILITY ANALYSIS
1. De e mine he a ia ion in e al o coe icien s C2 and C5 in he ene gy
gene a ion p oblem p esen ed in chap e 2.
2. In he p oduc ion planning p oblem sol ed in case s udy 1 in chap e 3 he bene i s
pe uni o he h ee p oduc s ha e been e ised. The new alues a e CA = 40, CB
= 30 and CC =12. Is he cu en solu ion s ill op imal? I no , de e mine he new
op imal solu ion om he op imal simplex ableau.
3. De e mine he anges o e which b1 and b3 can change indi idually in he ene gy
gene a ion p oblem p esen ed in chap e 2. Compa e he esul ob ained o b1 wi h
he esul ob ained in sec ion 4.4 and explain why hey a e di e en .
4. De e mine he anges o e which he bi o he ollowing linea p og am can change
indi idually (chap e 3-case s udy 2):
Min Z = 0.4 X1 + 0.5 X2
X1, X2
0
0.3 X1 + 0.1 X2 d 2.7
0.5 X1 + 0.5 X2 = 6
0.6 X1 + 0.4 X2 6
Ope a ions esea ch in business adminis a ion and managemen
130
CASE STUDY 3: SENSIBILITY ANALYSIS
F om he co esponding simplex able o he op imal solu ion o he model esul s o
he case s udy 5 o Chap e 3, answe he ollowing ques ions.
1. Indica e he op imal solu ion, he oppo uni y cos o esou ces and he a iables
educed cos and hei meaning.
2. By how much can he uni a y p o i o X2 a y wi hou changing he op imal
solu ion? Does he o al p o i a y? Wha does he sensi i i y analysis o he objec i e
unc ion coe icien s ell us?
3. By how much can he second membe o he R1 cons ain a y wi hou changing
he base? Wha changes and wha emains cons an while a ying b1? Why is he
sensi i i y analysis o he seconda y membe s o he cons ain s impo an when
making decisions on p oduc ion p oblems?
CASE STUDY 4: FEED MANUFACTURING AND DISTRIBUTION
A mul ina ional eed manu ac u ing and dis ibu ion company has 9 ac o ies in he
coun y. The ac o y loca ed in Valencia p oduces183 o mulas o 8 di e en species o
animals. E e y day, 43 ucks lea e he ac o y o dis ibu e 783,000 Kg. o eed. The e
a e wo ypes o eed: eed lou and eed g anule. Feed is also sold in wo di e en ways:
in bulk o in sacks. The dis ibu ion o he di e en ypes o eed is shown in Table 4.13.
O he quan i y p oduced, wo o he mos impo an o mulas ep esen a hi d o he
o al and he i s six imply 55% o he o al p oduc ion. On he ac o y’s p emises an
a e age o 30 T o eed in sacks and all o he eed in bulk is sold di ec ly o clien s. The
ac o y has 647 clien s and i ecei es an a e age o 80 o de s pe day, o which 6 a e
illed di ec ly on si e and 74 a e sen by uck.
A he momen , he nea es a m o which eed is dis ibu ed is loca ed 15 Km om
he ac o y and he mos dis an is 340 Km. 35% o he ucks deli e ing in bulk se e
only one clien , while his pe cen age is 7% o he ucks ha deli e eed in sacks. The
a e age numbe o deli e ies o ucks which dis ibu e o mo e han one clien is 2-3.
Fo he ucks ha dis ibu e sacks, he a e age is 4-5.
The a e age deli e y ime o o de s is 1.25 days, measu ed as he di e ence be ween
he da e on which he o de is ecei ed and he eal da e o deli e y. The pe son in cha ge
o logis ics akes 6 hou s each day o p epa e he ou es o he ollowing day, including
checking s ocks, a ailabili y o ucks, e c.
Chap e 4. Duali y and sensi i i y analysis
131
Table 4.13. Type o p oduc s and quan i ies sen om he ac o y
TYPE
NUMBER OF
PRODUCTS IN
he
CATALOG
AMOUNT SENT
DAILY
(Kg)
N
UMBER OF
DAILY TRUCKS
Bulk Flou eed 1 2,000
Bulk G anule eed 98 600,000 32
Flou in sacks 6 1,000
G anule in sacks 78 180,000 11
Cu en ly, p oduc ion is scheduled acco ding o an es ablished p oduc ion plan, aking
pending o de s in o accoun . 60% o he daily p oduc ion is immedia ely loaded on o he
ucks.
The e a e h ee wo king shi s in he ac o y: om 6-14, om 14-22 and om 22-6.
P oduc ion capaci y is 37,000 Kg/hou and packaging 375 sacks/hou . The ac o y has 12
o 36,000Kg capaci y con aine s and 17 o 17,000Kg capaci y con aine s o bulk s o age.
The s o age capaci y o sacks is 4 cells o 32,000 Kg capaci y. The eal amoun o s ock
a ailable is checked wice a day.
Tables 4.14 and 4.15 show he in o ma ion ela ed o he echnical cha ac e is ics o
he aw ma e ials, cos , as well as he nu i ion needs o each ype o eed acco ding o
he species and he age o he animal.
Ou line a linea p og amming model ha allows o de e mine he o mula ion and cos o
100 T o eed o lambs P1 and 100 T o eed o lambs P3.
1. Do you conside ha he op imal o mula ion ha you can ob ain wi h op imiza ion
so wa e could be composed o 20 aw ma e ials? Explain you answe .
2. Sol e he p e ious p oblem and indica e he op imal composi ion and he cos o
eeds P1 and P3.
3. Ba ley is no pa o any o he wo p e ious o mula ions. Do you belie e ha i
would be pa o one o hem i i s p ice we e 25 m.u./Kg? And i i s p ice we e
22.5? Wha would happen i he p ices o ba ley and whea dec eased by 1 m.u./Kg?
Fi s , answe wi hou sol ing he model again and hen check i you answe is
co ec .
4. Analyze he sensi i i y o he op imal o he p ices o he emaining aw ma e ials
and he u ili y o his in o ma ion o he company.
Ope a ions esea ch in business adminis a ion and managemen
132
5. I he p ice o co n we e inc eased by 0.2 m.u./Kg. and ha o soy dec eased by 0.5
m.u./Kg., would he op imal o mula ion and he cos o eed P1 change? Wha
abou i soy we e dec eased by 1 m.u./Kg? Why? Check wha changes and how
di e en i is om he ini ial solu ion.
6. Wha would be he e ec i eed P1 had a minimum le el o g oss p o ein o 18.5
and o 1.10 o calcium? Answe applying he 100% ule.
7. Calcula e he op imal o mula ion o minimum cos ha akes in o conside a ion
ha eed P3 canno ha e mo e han 40% co n, 10% glu en and 5% sun lowe .
8. This ype o company usually has o ace limi ed s ocks o aw ma e ials. De e mine
he cos and he o mula ions o P1 and P3 om he p e ious sec ion in he ollowing
cases:
8.1. The e is only a s ock o co n o 50 T.
8.2. The p ice o he 50 T o co n in s ock is 26.2 m.u./Kg and he company can buy
in he ma ke as much co n as hey wish a 27 m.u./Kg.
8.3. The company has 50 ons o co n in s ock ha i has o consume. The company
can also acqui e all he co n hey wan a 24 m.u. /Kg.
E alua e in each sec ion he consequences he e could be o he company o sol e he
p oblem by means o simple o mula ion ins ead o using a mul i o mula ion model,
supposing ha hal o he p oduc ion we e P1 and he o he hal P3.
9. Ob ain he o mula ion and he cos o P1 and P3 in such a way ha i apioca, glu en
and molasses a e pa o any o he eed hey ha e a minimum le el o 10%. Use
he semi- a iable op ion o LINGO. How would you sol e i wi h Sol e Excel
sp eadshee ? In ege a iables a e needed o inco po a e such a si ua ion o a model.

Chap e 4. Duali y and sensi i i y analysis
133
Table 4.14. Nu i ional limi s o eed o lambs
CHARACTERISTICS
P
1
P
2
P
3
P
4
P
5
P
6
P
7
P8
U.F.V/Kg Min
1.07
1.02
1.00
1.02
1.02
1.04
0.78
0.98
GROSS
PROT. % Min
18.0
17.6
17.2
17.6
17.6
18.0
14.0
16.5
GROSS
PROT. % Max
19.0
18.6
18.2
18.6
18.6
19.0
15.0
17.5
GROSS
FIBR. % Min
-
-
-
-
-
14.0
-
GROSS
FIBR. % Max
4.40
4.30
4.40
4.4
4.5
15.0
-
FAT MAT
% Min
-
-
-
-
-
-
-
-
FAT MAT
% Max
5.30
4.40
4.30
4.40
4.4
4.50
-
-
STARCH
% Min
-
35.0
35.0
35.0
35.0
35.0
-
30.0
CALCI
UM % Min
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
CALCI
UM % Max
1.30
1.10
1.10
1.10
1.10
1.10
1.10
1.10
PHOSPHORUS T.% Min
0.3
0.3
0.3
0.3
0.3
0.3
0.3
0.3
PHOSPHORUS
T.% Max
0.44
0.35
0.35
0.35
0.35
0.35
0.35
0.35
M.N.D. % Min
-
-
-
-
-
-
-
-
P.D.I.E
. % Min
13.0
12.1
11.9
12.1
12.1
12.3
-
11.2
P.D.I.N. % Min
13.0
12.1
11.9
12.1
12.1
12.3
-
11.2
-
10
Ope a ions esea ch in business adminis a ion and managemen

5BCMF$IBSBDUFSJTUJDTPGUIFSBXNBUFSJBMTDPTUBOEOVUSJFOUT
Chap e 4. Duali y and sensi i i y analysis
1
5BCMF$IBSBDUFSJTUJDTPGUIFSBXNBUFSJBMTDPTUBOEOVUSJFOUTDPOUJOVBUJPO
Chap e 5. In ege p og amming
143
5.3.1. CAPITAL BUDGETING DECISIONS
An au omobile manu ac u ing company wan s o calcula e he op imal dis ibu ion o
i s capi al budge o he nex yea s. The u u e in es men s ha i is conside ing a e he
ollowing:
a) Reno a ing i s cu en ac o y in o de o inc ease i s p oduc ion capaci y by 10,000
uni s pe yea .
b) Cons uc ing a new ac o y, wi h a p oduc ion capaci y o 15,000 uni s pe yea .
c) Pu ing in o p ac ice he esul s ha ha e been ob ained om a su ey on wo ke s'
mo i a ion a wo k, which will inc ease he p oduc ion by 5,000 uni s pe yea .
d) Pu chasing mo e p oduc i e and echnologically mo e ad anced equipmen , wi h
which an inc ease o p oduc ion o 2,000 uni s pe yea will be achie ed.
In es men s a and b a e mu ually exclusi e, and in es men d is condi ional on he
ealiza ion o in es men a. The company seeks o inc ease i s ins alled p oduc i e
capaci y, bu conside s ha , due o he maximum sales o ecas s, i should no exceed an
inc ease o 16,000 uni s pe yea .
The Ne P esen Value (NPV) o he in es men s, as well as he expendi u e and he
inancial a ailabili y a e hose shown in able 5.2.
Table 5.2. In es men da a
In e
s men
NPV
Cash- low
Yea 1
Yea 2
I1 50 60 70
I2 80 100 70
I3 40 30 40
I4 30 20 50
The p oblem consis s o inding ou which in es men s should be ca ied ou in o de
o op imize hei ne p esen alue, knowing ha he inancial a ailabili ies o he i s
and second pe iod a e 150 and 120 m.u. espec i ely.
The in ege p og amming model o sol e his p oblem is he ollowing:
Va iables
We de ine ou bina y a iables Xj = (0, 1) o j = 1, 2, 3, 4 ha will ake he alue 1
when he in es men j is ca ied ou and 0 o he wise.

Ope a ions esea ch in business adminis a ion and managemen
144
Objec i e unc ion
The objec i e is o maximize he Ne P esen Value o all in es men s.
Max 50 X1 + 80 X2 + 40 X3 + 30 X4
Cons ain s
The expendi u e du ing he i s and second yea canno exceed he a ailabili y:
60 X1 + 100 X2 + 30 X3 + 20 X4
d
150
70 X1 + 70 X2 + 40 X3 + 50 X4
d
120
In es men s a and b a e mu ually exclusi e al e na i es:
X1 + X2
d
1
In es men d is condi ional on he ealiza ion o in es men a, ha is, d can only be
ca ied ou i a has been done. These a iables a e known as con ingen decisions,
which a e decisions ha depend upon p e ious decisions.
X4
d
X1
The inc ease o he p oduc i e capaci y should no exceed he maximum sales
o ecas :
10000 X1 + 15000 X2 + 5000 X3 + 2000 X4
d
16000
5.3.2. SETUP COST PROBLEM
A company can manu ac u e ou p oduc s on a p oduc ion line ha goes h ough
h ee di e en depa men s. Table 5.3 shows he manpowe /hou needed in each
depa men s pe one housand p oduc uni s, as well as he a ailabili y o hou s pe mon h,
he g oss p o i (sale p ice - a iable cos ) and he ixed cos o condi ioning he
p oduc ion line o each p oduc , i.e. se up cos s. The company wan s o p og am he
p oduc ion o maximize he bene i s.
The linea p og amming app oach does no wo k when we ha e se up cos s. In linea
p og amming all cos s a e conside ed o be a iable cos s, ha is, p opo ional o he alue
o he a iable, while in his case he e is a ixed cos only when he a iable alue is
posi i e, bu ze o when he a iable alue is also ze o. I should be emphasized ha he
se up cos p oblem only a ises when he ixed cos is cha ged i he e is p oduc ion and is
no cha ged i he p oduc ion le el is ze o. When he ixed cos is always cha ged, he
con inuous linea p og amming is alid. Why?
Chap e 5. In ege p og amming
145
Table 5.3. Technical and economical da a
P oduc
Manpowe -hou
needed pe one
housand uni s o p oduc
G oss p o i
€/uni
Se up
Cos
€
Dep 1
Dep 2
Dep 3
P1 160
120
50
80 200,000
P2 150
200
50
85 200,000
P3 100
180
50
98 90,000
P4 200
175
50
100 150,000
A ailabili y o
manpowe -hou
s/
mon h
4,
000
4,
800
1,
600
Le ´s see he o mula ion o an app op ia e mixed in ege p og amming model o sol e
he p e ious p oblem. We de ine he a iables P1, P2, P3 and P4 o be he size o each
p oduc ion ba ch in housands o uni s.
Pj
0 o j = 1, 2, 3, 4
The p o i o p oducing P1 is
B1 = 80,000 P1 - 200,000 o P1 > 0 and
B1 =0 o P1 = 0
The p o i s o he o he h ee p oduc s p esen a simila s uc u e. To ep esen his by
means o a linea unc ion we de ine some bina y a iables Yj which ha e a alue o 1
when Pj > 0 and ze o when Pj = 0.
The objec i e unc ion is as ollows:
MAX 80,000 P1 + 85,000 P2 + 98,000 P3 + 100,000 P4
- 200,000 Y1 - 200,000 Y2 - 90,000 Y3 - 150,000 Y4
The cons ain s will e e o a ailabili y o man-hou s in he h ee depa men s and
hey will ha e o gua an ee ha he se up cos is cha ged when he e is p oduc ion.
Dep1: 160 P1 + 150 P2 + 100 P3 + 200 P4
d
4,000
Dep2: 120 P1 + 200 P2 + 180 P3 + 175 P4
d
4,800
Dep3: 50 P1 + 50 P2 + 50 P3 + 50 P4
d
1,600
Ope a ions esea ch in business adminis a ion and managemen
146
P1
d
100 Y1
P2
d
100 Y2
P3
d
100 Y3
P4
d
100 Y4
The las ou cons ain s ensu e ha he se up cos is conside ed whene e he
co esponding le el o p oduc ion is posi i e. The coe icien o he bina y a iables has
o be a numbe la ge enough no o limi he le el o ac i i y o he Pj, in his case 100 is
big enough o no limi he p oduc ion alues.
5.3.3. SITE SELECTION OF INDUSTRIES AND SERVICES
Ano he impo an applica ion o mixed in ege p og amming is ound in p oblems
whe e he objec i e is o de e mine he loca ion and op imal size o a se ies o ac o ies
ha p oduce high consump ion goods. The demand and hei clien s' loca ion a e known.
The model o a p oduc and one pe iod could be he ollowing:
Coe icien s
b1, b2..., bn: known demands o n clien s (j=1, 2 …n)
a1, a2..., am: p oduc ion capaci ies o ins all in m ac o ies (i=1, 2 …m)
1, 2..., m: cons uc ion cos o he ac o ies (i=1, 2 …m)
Cij: anspo cos o a uni o goods om he i- h ac o y o he j- h clien
Va iables
Xij: Numbe o anspo ed uni s om ac o y i o clien j
yi: Bina y a iables, 1 indica es ha he ac o y i is buil and 0 o he wise o i
= 1,2,...,m
Objec i e Func ion
The objec i e consis s o minimizing he o al cos ( ixed cos o cons uc ion o he
ac o ies plus he dis ibu ion a iable cos s) sa is ying he demand.

ij
n
j
iji
m
i
i
XCy MIN
¦¦

11
Chap e 5. In ege p og amming
147
Cons ain s
Clien s demand
j
m
i
ij
bX
¦
1
j=1, 2… n
P oduc ion capaci y o he ac o ies
ii
n
j
ij
yaX d
¦
1
i=1, 2…m
This ype o model has been applied o p oblems such as loca ion o milk
pas eu iza ion cen e s, slaugh e houses, eed wa ehouses, was e ea men plan s, e c...
5.3.4. A DISTRIBUTION PROBLEM WITH NONLINEAR COSTS
In his sec ion we p esen a eal p oblem o decision-making and mixed in ege
p og amming model ha educes he dis ibu ion cos s o he company (Ma o o, C.;
Aliaga, S. and A. To es, 2000).
The ope a ion p ocess o he company is ep esen ed in Figu e 5.3. The company
manages he b oile p oduc ion p ocess p o iding a me s wi h one-day-old chickens,
eed and o he esou ces such as echnical and sani a y assis ance. I is also esponsible
o collec ing and ma ke ing he a ened chicken. B oile a me s p o ide he labo and
equipped wa ehouses, and hey a e paid on he basis o a e age cos s o b eeding and
p oduc ion esul s. Gi en he economic impo ance o eed cos s, he company is hinking
o educing anspo cos s om he ac o y o he a ms. The dis ibu ion o shipmen s
was ca ied ou wi h subjec i e c i e ia and manually. The e o e, he company was also
in e es ed in planning shipmen s o eed by objec i e c i e ia, minimizing cos s.
The company is esponsible o es ima ing he eed equi ed by each a m and placing
o de s o he eed ac o y. This o e s p ices wi h a cos s uc u e shown in Table 5.4. As
shown in he able, anspo p ices depend bo h on he weigh o he o de and he
dis ance om he ac o y o he a m. Thus, he company is acing a nonlinea
anspo a ion cos s uc u e. The p e ious me hod used by he company was o assess
he needs o each ype o eed on each a m and place as many la ge o de s as possible
and he di e ence wi h ano he o de . The company is awa e ha hese emaining o de s
inc ease he o al cos .
Ope a ions esea ch in business adminis a ion and managemen
148
Figu e 5.3. Ope a ion p ocess o he company
Table 5.4. Feed anspo cos s s uc u e
Dis ance
Km
20-24
Tons
€/Tons
16
-19.9
Tons
€/Tons
12-15.9
Tons
€/Tons
8-11.9
Tons
€/Tons
4-7.9
Tons
€/Tons
0-10
1.94 1.95 1.99 2.36 3.25
10.1-
15
2.20 2.28 2.36 2.74 3.67
…
100.1-
105
6.94 8.17 9.02 9.30 11.06
…
340.1-
345
19.57 23.87 26.80 27.07 30.68
345.1-
350
18.83 24.19 27.17 27.44 31.10
To sol e his p oblem we p oposed he ollowing in ege p og amming model. The e a e
many models, a leas one o each a m and each ba ch o b oile s. All models ha e he
same s uc u e. Fi s ly we de ine he pa ame e s which will ha e a speci ic alue in each
model.
COMPANY
One-day-old
b oile s
Technical and
sani a y assis ance
B oile s
B oile
a me s
Feed ac o y
Sales and
dis ibu ion

Chap e 5. In ege p og amming
149
Pa ame e s
The eed o de s depend on h ee ac o s: he capaci y o he silos ins alled on he
a ms, he access oad o hem and he eed in ake. The la e is based on he numbe o
chickens, mo ali y, age, sex, season and ype o wa ehouse. La ge o de s o 24 ons,
which a e he ones wi h lowe cos , canno always be conside ed i he size o he silo o
he a m is smalle o i he accesses p e en he passage o ucks o ha size.
The p oblem a ises because anspo cos s a e nonlinea , hey depend on he
dis ance om he a m o he ac o y, and on he shipping amoun . Thus, o a gi en
a m he mos economical a e is ha co esponding o 20-24 on shipmen s (T1 € / on).
The second mos economical a e is he shipping ee om 16 o 19.99 ons (T2), he hi d
om 12 o 15.99 ons (T3), he ou h om 8 o 11.99 ons (T4) and he i h, and mos
expensi e, is he ee o he smalles shipping, om 4 o 7.99 ons (T5). We can s a e ha
he cos is nonlinea , bu is cons an wi hin each o he i e in e als.
Th ee ypes o eed mus be p o ided h oughou he animals’ g ow h p ocess and
he o al amoun in b eeding (P1, P2 and P3) depends on he numbe and sex o he chicks,
as well as o he ac o s such as ace, season and ype acili ies. When he company
planned he deli e ies manually hey made all possible shipmen s o a la ge size,
gene ally lea ing a small esidue o shipping in ons, bu wi h a e y high uni cos . The
model should minimize he cos o anspo a ion o P1, P2 and P3 ons o eed o a
pa icula a m.
Ano he pa ame e a ec ing he o de quan i y is wha we ha e called CSi o i = 1,
2, 3, which is he o al capaci y o he silo excep he sa e y ma gin o he eed Pi.
Finally, Ac is he maximum uck load in e ms o he access oads o he a m.
1. Va iables
We de ined wo ypes o a iables, con inuous a iables Xijk ep esen ing ons o eed
i (i = 1, 2, 3) a he a e j (1, 2 ... 5) in he shipping k (1, 2 ... K) necessa y o b oile
p oduc ion on a gi en a m. K is es ima ed as he maximum numbe o shipping o each
ype o eed needed o supply he la ge a m, du ing each pe iod o consump ion. The
o he ype o a iables is bina y Yijk, which will ake alue 1 i he a e j is used in shipping
k o eed ype i and 0 o he wise. These bina y a iables a e necessa y due o he nonlinea
s uc u e o anspo cos s and pe mi us o o mula e his p oblem using linea unc ions.
Xijk ons o eed i=1, 2, 3 a a e j=1,2,…5 in he shipping k = 1,2…K
Yijk (0, 1) bina y, 1 indica es ha he a e j is used in he shipping k o he ype o
eed i and 0 o he wise.
Ope a ions esea ch in business adminis a ion and managemen
150
2. Objec i e Func ion
The objec i e unc ion consis s o minimizing he anspo cos o he eed needed
o aising chickens on a speci ic a m and is gi en by he cos o all shipmen s o he
a m. All 20-24 ons o de s will be cha ged a p ice T1, 16 o 19.9 ons a p ice T2, 12 o
15.9 ons a p ice T3, 8 o 11.9 a p ice T4 and he o de s be ween 4 and 7.9 ons a p ice
T5 which is he mos expensi e. The Tj a e ixed o each a m and a y om one o
ano he depending on he dis ance o he ac o y.
¦¦¦¦¦¦¦¦¦¦

3
11
55
3
11
44
3
11
33
3
11
22
3
11
11
i
K
k
ki
i
K
k
ki
i
K
k
ki
i
K
k
ki
i
K
k
ki
XTXTXTXTXTMinZ
3. Cons ain s
Demand o each ype o eed: we ha e a es ic ion o each ype o eed ha
indica es ha he sum o all he sen amoun s mus be equal o he o al equi ed.
¦¦
K
k
jk
j
PX
1
11
5
1
¦¦
K
k
jk
j
PX
1
22
5
1
¦¦
K
k
jk
j
PX
1
33
5
1
Silo capaci y: no o de may exceed he capaci y o he silo on he a m minus he
es ima ed sa e y ma gin (CSi). The sa e y ma gin a ies depending on he numbe o
b oile s and hei pe iod o g ow h.
Xijk
d
CSi o i=1,2,3; j=1,…5; K=1,…K
T uck access: he size o he o de s is limi ed by he onnage o he ucks ha can
access he a m.
Xijk
d
Ac o i=1,2,3; j=1,…5; K=1,…K
P ice lis (nonlinea cos s): he ollowing es ic ions ep esen he s uc u e o
anspo cos s ha he company has o pay o he eed ac o y. Thus, he i s cons ain
indica es ha all o de s o eed i wi h he cheapes a e T1 will ha e be ween 20 and 24
ons. The e will be as many cons ain g oups o his ype as he e a e ypes o eed and
possible deli e ies.
Chap e 5. In ege p og amming
151
20 Yi1k
d
Xi1k
d
24 Yi1k
16 Yi2k
d
Xi2k
d
19.9 Yi2k
12 Yi3k
d
Xi3k
d
15.9 Yi3k
8 Yi4k
d
Xi4k
d
11.9 Yi4k
4 Yi5k
d
Xi5k
d
7.9 Yi5k
All he cons ain s o he p ice a i o i = 1, 2, 3 and k = 1, 2,…K
The solu ion o his model gi es he numbe o o de s ha we should place o he eed
ac o y and he measu ed quan i y in ons o each ba ch o chickens and a m, minimizing
he cos , which is he la ges p oduc ion cos o he company and imp o ing i s decision-
making. This model no only educes he cos s o hei ac i i ies, bu i also eac s
app op ia ely o any un o eseen needs such as educ ion o necessi ies due o animal dea h
on ho days, elec ici y ailu es, diseases, e c. by simply e- unning he model wi h he
upda ed da a.
Le us conside a simple example o a simila p oblem. A company needs 85 ons o
p oduc 1 and 90 ons o p oduc 2 o nex mon h. The p o ide has a p ice ha depends
on he size o he o de . De e mine he numbe o o de s o be placed in o de o minimize
he cos o he p oduc .
Table 5.5. T anspo cos ´s s uc u e
Amoun o o de in ons
Cos o T anspo Eu os/ on
16-20 8
12-15.9 12
5-11.9 16
The a iables a e Xijk = ons o p oduc i a p ice j in shipmen k;
The objec i e unc ion
MINIMIZE 8*(X111 + X112 + X113 + X114 + X115 + X211 + X212 + X213 + X214 + X215) +
12*(X121 + X122 + X123 + X124 + X221 + X222 + X223 + X224) +
16*(X131 + X132 + X133 + X134 + X231 + X232 + X233 + X234);
Ope a ions esea ch in business adminis a ion and managemen
152
Cons ain s:
Demand o p oduc P1
X111 + X112 + X113 + X114 + X115 + X121 + X122 + X123 + X124 + X131 + X132 + X133 + X134= 85;
Demand o p oduc P2
X211 + X212 + X213 + X214 + X215 + X221 + X222 + X223 + X224 + X231 + X232 + X233 + X234= 90;
Cu en ly we can sol e his nonlinea cos p oblem by subs i u ing equa ions linking he
amoun o he p oduc wi h he co esponding bina y a iable using a ype o a iable
known in LINGO as semi-con inuous. Fo example, o indica e ha i he a iable X111
has a nonze o alue in he op imal solu ion hen his is be ween 16 and 20, we add o he
model he ollowing
@SEMIC (16, X111, 20)
In his case LINGO gene a es he necessa y bina y a iables and cons ain s o ake his
si ua ion in o accoun . Howe e , in Excel his is no possible and you ha e o en e all he
es ic ions, de ine he bina y a iables and ake in o accoun ha in Excel we ha e o pu
all a iables on he le -hand-side and in he igh -hand-side o he cons ain s only he
independen e m.
5.3.5. A PROBLEM OF TRANSPORT ROUTES
Case s udy 3 o chap e 4 is a p oblem o eed manu ac u ing and dis ibu ion o a
mul ina ional company in he ood indus y which has one o i s ac o ies in Valencia. In
he a o emen ioned case a linea p og amming model was o mula ed o minimize
manu ac u ing cos s. In his sec ion we will explain an in ege p og amming model o
sol e he eed dis ibu ion p oblem o cus ome s, which di e s om he heo e ical ou e
models p esen ed in Ope a ions Resea ch books.
In sho , he company manu ac u es abou 150 animal eed p oduc s and dis ibu es
800,000 kg pe day o an a e age o 70 clien s. The company has a po olio o 700 clien s,
whose dis ance om he ac o y a ies om 15 o 450 km. The company has hi ed a lee
o ucks wi h capaci ies o be ween 12 and 24 ons, wi h compa men s o 4 ons.
The e o e, each deli e y ou e can isi a mos six cus ome s. The pe son esponsible o
calcula ing he ou es dedica es six hou s pe day o his ac i i y. In addi ion, be ween 5-
30 ush o de s a e ecei ed e e y day, which means ha he ou es canno be ecalcula ed
o include hese o de s. The cos o he ou es is a complex unc ion dependen on he
dis ance o he las cus ome se ed and he uck loading, which has a minimum cos
e en i he e is no anspo o goods. Fo example, i a 24- on uck ca ies 20 ons, he
company pays as i 23 ons we e anspo ed.
Chap e 8. Nonlinea p og amming
25
Figu e 8.9. Da a: Re u ns and be a coe icien s o Sha pe
Figu e 8.10. E icien po olio model o Sha pe

Ope a ions esea ch in business adminis a ion and managemen
25
In bo h Ma kowi z and Sha pe models, i is common o add cons ain s in o de o
limi he alue o he decision a iables so ha nei he o hem ep esen s a e y la ge
po olio ac ion. Finally, we can say ha he e a e many o he possible models and you
can ind inance ea ises abou hem.
8.5. SUMMARY
The mos impo an ea u e o nonlinea p og amming is ha no one me hod is " he
bes " o sol e any nonlinea model. The op imal solu ion is no a co ne poin o he
easible egion and i can e en be an in e io poin . When unc ion objec i e and/o
cons ain s a e nonlinea , he p ocedu e o ind he op imal solu ion is mo e complica ed
han in he linea case. Howe e , he e a e me hods ha sol e ce ain ypes o p oblems
e icien ly and many applica ions in business adminis a ion and managemen ha need
hese me hods o imp o e decision-making. An especially impo an one is he e icien
po olios o secu i ies in es men . Ma kowi z and Sha pe models a e he basis o he
mode n po olio heo y in inance.
8.6. SELECTED REFERENCES
1. Daellenbach, H.G.; Geo ge, J.A.y D.C.McNickle (1987): In oducción a las écnicas
de in es igación de ope aciones. CECSA.
2. Hillie , F.S. and Liebe man G.J. (2010): In oduc ion o Ope a ions Resea ch. Nin h
Edi ion. McG aw-Hill.
3. Hillie , F.S and Hillie , M.S. (2011): In oduc ion o Managemen Science. A
Modelling and Case S udies App oach wi h Sp eadshee s. Fou h Edi ion. McG aw-
Hill.
4. LINDO Sys ems (2011): LINGO. The modeling language and op imize .
5. LINDO Sys ems (2006): Op imiza ion in Sp eadshee s wi h Wha ´ s Bes !
h p://www.lindo.com.
6. Luenbe ge , D.G. (1998): In es men Science. Ox o d Uni e si y P ess. Chap e s 6
and 7.
7. Wins on, W. L. and S.C. Alb igh (2012): P ac ical Managemen Science. Fou h
Edi ion. Sou h-Wes e n. USA.
Chap e 8. Nonlinea p og amming
25
8.7. CASE STUDIES
CASE STUDY 1
Sol e he ollowing model which ep esen s a p oblem o in es men po olio
g aphically. Analyse he di e ences be ween his case and g aphical solu ion o a linea
p og amming model.
Min 0.09 X12 + 0.04 X1 X2 + 0.06 X22
Cons ain s:
X1 + X2 = 1
0.06 X1 + 0.02 X2  0.03
X1  0.75
X2  0.9
X1  0
X2  0
CASE STUDY 2
Suppose ha able 8.2 includes he his o ical e u ns o i e ypes o asse s and he
IBEX-35.
Table 8.2. Annual e u ns
YEAR
ASSET 1
ASSET 2
ASSET 3
ASSET 4
ASSET 5
IBEX
1999
12,5
19,9
4,1
12,1
5,6
12,0
2000
9,4
9,2
2,6
8,3
6,2
8,3
2001
13,9
19,9
-4,2
10,2
4,5
9,4
2002
7,7
14,3
7,9
8,4
11,2
10,5
2003
8,7
19,2
9,9
8,6
0,9
9,8
2004
11,0
15,8
10,1
6,9
8,6
11,2
2005
8,8
18,2
6,3
6,5
8,5
8,5
2006
10,5
18,6
10,0
7,3
11,6
10,9
2007
12,5
14,5
2,2
8,4
12,9
10,1
2008
14,0
18,2
6,8
7,2
8,7
12,0
2009
6,8
13,6
8,5
10,3
8,8
8,9
2010
14,2
17,1
6,1
12,8
8,4
14,3
2011
10,9
10,0
6,0
11,3
4,3
8,4
2012
9,5
8,5
6,0
7,9
7,3
9,3
Ob ain he composi ion o e icien po olios o h ee ypes o in es o s, high,
medium and low e u n by using Ma kowi z and Sha pe models. This p oblem can be
sol ed wi h Excel Sol e and LINGO.
CHAPTER
9
METAHEURISTIC
TECHNIQUES:
GENETIC
ALGORITHMS
9.1. GENETIC ALGORITHMS .......................................................................... 263
9.1.1. SOLUTION ENCODING ......................................................................... 266
9.1.2. FITNESS FUNCTION .............................................................................. 266
9.1.3. SELECTION ............................................................................................. 267
9.1.4. CROSSOVER ........................................................................................... 269
9.1.5. MUTATION .............................................................................................. 275
9.1.6. APPLICATIONS: THE TRAVELING SALESMAN PROBLEM ............... 275
9.2. TABU SEARCH .............................................................................................. 284
9.3. SIMULATED ANNEALING ........................................................................ 287
9.4. SUMMARY ...................................................................................................... 289
9.5. SELECTED REFERENCES ........................................................................ 290
9.6. CASE STUDIES .............................................................................................. 290

Chap e 9.Me aheu is ic echniques: gene ic algo i hms
26
In ecen decades a new g oup o algo i hms has appea ed, called me aheu is ics, and
hey ha e been success ully applied o a a ie y o di icul sea ch and combina o ial
op imiza ion p oblems. They a e he la es gene a ion o heu is ic algo i hms, widely used
o sol ing op imiza ion p oblems o all kinds when exac me hods a e no applicable. A
me aheu is ic algo i hm can be de ined as an i e a i e p ocess ha guides and/o modi ies
he ope a ions and/o solu ions o one o mo e subo dina e heu is ic algo i hms o p oduce
highe quali y solu ions in a easonable ime (Voss e al., 1999). They manipula e a single
solu ion o a combina ion o hese in each i e a ion, and as he p ocess p oceeds he
solu ion o solu ions imp o e.
Among he me aheu is ics ha ha e appea ed we may include hose ha mimic he
beha io o na u al sys ems, bo h biological and physical, such as he na u al e olu ion
o he species, he modynamics, coope a i e wo k in an an colony o he beha io o
neu ons in he b ain. F om he wide a ie y o exis ing me aheu is ics, we can highligh ,
due o hei excellen esul s and he di e si y o p oblems o which hey a e being applied;
gene ic algo i hms, abu-sea ch and simula ed annealing, o which we will de o e his
chap e . We can ind a de ailed desc ip ion o hese and o he me aheu is ics in Raywa d-
Smi h e al. (1996). Among hei applica ions we can ci e ou ing p oblems, schedule
managemen , p oduc ion scheduling, p ojec scheduling wi h limi ed esou ces and many
o he s. Gene ic algo i hms a e explained in de ail in he nex sec ion, and in he las wo
poin s o his chap e abu-sea ch and simula ed annealing a e ou lined.
9.1. GENETIC ALGORITHMS
In he '60s he apid p oli e a ion o compu e s led o hei use as simula ion ools by
he scien i ic communi y. In he ea ly '70s, a g oup o esea che s om he Uni e si y o
Michigan, led by P o esso John Holland (1975), p oposed gene ic algo i hms as
compu e p og ams ha mimicked he na u al e olu iona y p ocess and beha ed obus ly
in a a iable and unce ain en i onmen . The main heme o he esea ch ocused on he
obus ness o such sys ems, i.e. how o ind he igh balance be ween e iciency and
e ec i eness o sui di e en en i onmen s. The obus ness o he sys ems, bo h so wa e
and ha dwa e, was a c ucial aspec o hei design, as he cos o ehabili a ion and
edesign could be d as ically educed o e en elimina ed.
The esolu ion o a pa icula complex p oblem can be iewed as sea ch in a space o
possible solu ions and, since we gene ally look o he bes solu ion, i can be u he
unde s ood as an op imiza ion p oblem. Gene ic algo i hms a e algo i hms whose sea ch
mechanisms imi a e a na u al phenomenon: he e olu ion o species h ough gene ic
inhe i ance. In na u e, he p oblem ha each species aces is seeking imp o emen s o
i s own adap a ion o he en i onmen . The main idea o gene ic algo i hms is o do wha
na u e does.
In na u e, he membe s o a popula ion compe e wi h each o he o esou ces such as
ood, wa e o shel e . A he same ime, males compe e amongs hemsel es o a ac
emales. Indi iduals who a e be e p epa ed o su i al and who a ac emales will be
hose ha ge mo e o sp ing. The less success ul indi iduals will ha e ewe o sp ing
Ope a ions esea ch in business adminis a ion and managemen
26
o e en none. This means ha he genes o he i es will be inhe i ed by a g owing
numbe o indi iduals in successi e gene a ions. The combina ion o he good ea u es o
pas gene a ions usually p oduces indi iduals ha a e be e adap ed han hei
p edecesso s. In his sense he species e ol es in o a kind ha is be e and be e adap ed
o hei en i onmen .
Le us ake a popula ion o abbi s as an example (Michalewicz, 1996). In his
popula ion some abbi s a e as e and cle e e han he es . The oxes ha eed on hese
abbi s will ind i mo e di icul o ca ch as and cle e abbi s, so hose will su ely
su i e and do wha abbi s do bes : make mo e abbi s. O cou se, some o he slow and
clumsy abbi s su i e due o good luck and may possibly ha e o sp ing. The o sp ing
popula ion becomes a good mix o gene ic ma e ial: as abbi s ha e c ossed wi h slowe
abbi s, some as e abbi s wi h o he e y as ones, slow abbi s wi h cle e ones,
clumsy wi h as , e c. Addi ionally, mu a ions in he gene ic ma e ial o some indi iduals
in he popula ion can be p oduced, which may in oduce di e en cha ac e is ics om
hose inhe i ed om p e ious gene a ions, i.e. in oduces g ea e a iabili y in he
popula ion. As a consequence, he esul ing abbi popula ion will be, on a e age, as e
and mo e “in elligen " han he o iginal popula ion, because mos o he pa en s which
su i ed he oxes we e quick and cle e . I is in e es ing o hink ha he ox popula ion
also su e s a simila e olu ion, since o he wise, he abbi s would become oo as and
in elligen o be caugh by hem.
Gene ic algo i hms ollow na u e p ocedu e in he p e ious example s ep by s ep.
They wo k on a popula ion o indi iduals, each o which ep esen s a possible solu ion o
he p oblem hey a e applied o. Each indi idual is assigned a i ness alue ep esen ing
he quali y o he solu ion. The indi iduals in he popula ion c oss wi h each o he o
p oduce new solu ions, so ha indi iduals wi h a be e i ness alue a e mo e likely o
be selec ed o c osso e . When wo indi iduals o solu ions a e selec ed o c osso e ,
hey p oduce one o mo e solu ions (child en) who inhe i some o he cha ac e is ics o
each o he pa en s. The leas quali ied indi iduals, i.e. he solu ions wi h wo se i ness
alue a e less likely, bu hey also ha e some possibili y o c oss wi h o he solu ions and
pass hei ea u es on o he nex gene a ion.
Figu e 9.1 shows, in pseudo code, he gene al p ocedu e o a gene ic algo i hm. The
i s s ep consis s o gene a ing he ini ial popula ion o solu ions. One o he main
di e ences be ween he gene ic algo i hms and o he sequen ial algo i hms, such as abu
sea ch o simula ed annealing, is ha he i s one manages a se o solu ions in e e y
i e a ion and no only one solu ion as i is he case o he las wo. Once we ha e he ini ial
popula ion ha may ha e been ob ained in a andom way, each indi idual is e alua ed,
ha is, a i ness alue is assigned o e e y indi idual.
Chap e 9.Me aheu is ic echniques: gene ic algo i hms
26
Figu e 9.1. Gene ic Algo i hm: gene al p ocedu e
A e all o he membe s o he ini ial popula ion ha e been e alua ed, he ollowing
s eps a e epea ed un il he s opping condi ion is sa is ied. Fi s ly, he selec ion o he
popula ion is ca ied ou . In his p ocess each o he indi iduals in he popula ion is copied
a numbe o imes, so ha he bes indi iduals gene ally ha e a highe numbe o copies
han he less skilled indi iduals. In his way we ob ain a new popula ion ha eplaces he
p e ious one.
A e ha , he c osso e p ocess is ca ied ou . The indi iduals in he popula ion a e
pai ed a andom and e e y couple unde goes c osso e wi h a gi en p obabili y. I he
ope a ion is ca ied ou by he couple (pa en s), wo new solu ions (child en) ha eplace
he p e ious ones a e c ea ed. I no , he pa en s emain unal e ed. Thus, in he esul ing
popula ion indi iduals om di e en gene a ions can li e oge he . The e ec o he
selec ion p ocess which is ca ied ou be o e he c osso e ope a ion is ha he bes
indi iduals in he popula ion pa icipa e mo e ac i ely in such p ocesses.
Finally, some indi iduals in he popula ion can mu a e, i.e. some solu ions can be
pa ially al e ed, allowing he popula ion o in oduce new ea u es o ma e ial which ha e
been los h ough e olu ion.
The esul ing popula ion hen is e-e alua ed and he e mina ion condi ion is checked.
This condi ion gene ally e e s o he elapsed compu a ion ime, he numbe o
gene a ions o i e a ions pe o med, he numbe o indi iduals who ha e been e alua ed,
he imp o emen p oduced in he las i e a ions, he a iabili y o he popula ion, e c.
Ob iously, we need o design an encoding o he solu ions be o e we can s a
applying a gene ic algo i hm, his being one o he undamen al aspec s o he design and
he e o e he subsequen e iciency o he gene ic algo i hm. Tha is, we need o de ine
how o ep esen each o he possible solu ions in an app op ia e way.
Gene ic Algo i hm P ocedu e
C ea e_ini ial_popula ion
E alua e_popula ion
While no ( e mina ion_condi ion)
Selec _popula ion
C oss_popula ion
Mu a e_popula ion
E alua e_popula ion
Ope a ions esea ch in business adminis a ion and managemen
26
9.1.1. SOLUTIONS ENCODING
The gene ic algo i hm ope a es on an encoded ep esen a ion o he solu ions,
equi alen o he gene ic ma e ial o he indi iduals, a he han di ec ly on he gi en
solu ions. A solu ion o he p oblem can be ep esen ed as a se o pa ame e s. These
pa ame e s, known as genes, can be placed one a e he o he , o ming a chain o alues,
which a e e e ed o as a ch omosome. In gene ic e ms, he pa ame e se ep esen ed
by a ch omosome is called a geno ype. I con ains he in o ma ion necessa y o cons uc
an o ganism, known as a pheno ype.
In he gene ic algo i hm p oposed by Holland each o he solu ions is ep esen ed by
a chain on a bina y alphabe , i.e. a chain consis ing o only ze os and ones. Al hough he
simple gene ic algo i hm (p oposed by Holland) used a bina y encoding, o he ypes o
encodings ha e been de eloped, such as s ings o in ege s o eal numbe s and e en
chains in which genes do no con ain numbe s. Tha means ha he s ings can be de ined
using any alphabe .
Some imes he ch omosome does no di ec ly ep esen a solu ion o he p oblem, bu
he in o ma ion needed by a pa icula algo i hm o sol e he speci ic p oblem, such as
o example, a heu is ic algo i hm which is able o ind good solu ions o he p oblem. In
his case, we should apply such a p ocedu e using he in o ma ion ep esen ed in he
ch omosome in o de o ob ain a solu ion. Rega dless o whe he hey di ec ly ep esen
a solu ion o he p oblem o no , indi iduals om he popula ion a e gene ally e e ed o
as solu ions. An app op ia e encoding o he solu ions is c ucial o he success o he
gene ic algo i hm, and he es o he p ocedu es o be designed ha will manipula e and
ac on he solu ions will depend on his encoding.
Once we ha e de ined he encoding, he nex s ep is o c ea e he ini ial popula ion o
solu ions o a ce ain size. The e a e gene ally wo ways o gene a e he indi iduals o
ha popula ion: a andom o using some heu is ic algo i hm. The ad an ages o he i s
mechanism a e he equi ed ime and he di e si y o he gene a ed solu ions, bu i may
ha e he disad an age o c ea ing a medioc e popula ion which may need a lo o ime o
con e ge o good solu ions. The second me hod does no ha e he abo e men ioned
d awback, since he solu ions a e usually o a be e quali y, so i can con e ge as e .
Howe e , we should a oid gene a ing a popula ion wi h li le di e si y, because his
lack o di e si y could lead o a p ema u e con e gence, by being apped in a local
op imum. We mus also ake in o accoun he ime needed o c ea e he popula ion by
his me hod because, i i is oo high, a andom popula ion may be ad isable.
9.1.2. FITNESS FUNCTION
The i ness unc ion o e alua ion unc ion is he one ha assigns, o each o he
indi iduals in he popula ion, a i ness alue which indica es he sui abili y o ha
indi idual wi h espec o o he indi iduals who a e pa o he popula ion.
Chap e 9.Me aheu is ic echniques: gene ic algo i hms
27
Ľ Ľ Ľ
3
2
5
7
1
9
4
6
8
Fa he Son
"
"
"
"
1
9
4
"
"
Figu e 9.5(a). PMX c osso e example: 1s s ep
The de ined in e changes ha e been ma ked wi h a ows in he p e ious igu e. These
a e:
2
ļ
1
5
ļ
9
8
ļ
4
The nex s ep is o inhe i hose genes ma ked by ", om he o he pa en and do no
p oduce con lic wi h each o he , i.e. hey do no appea epea edly. I means ha he
daugh e now inhe i s genes om he a he and he son om he mo he .
1
3
4
6
2
5
8
7
9
Mo he Daugh e
3
"
"
7
2
5
8
6
"
3
2
5
7
1
9
4
6
8
Fa he Son
"
3
"
6
1
9
4
7
"
Figu e 9.5 (b). PMX c osso e example: 2nd s ep
Finally, he exchanges de ined abo e se e o inhe i he es o he genes, which a e
hose ha could no be inhe i ed in he p e ious s ep by p oducing con lic s:
1
3
4
6
2
5
8
7
9
Mo he Daugh e
3
1
9
7
2
5
8
6
4
3
2
5
7
1
9
4
6
8
Fa he Son
2
3
8
6
1
9
4
7
5
Figu e 9.5 (c). PMX c osso e example: 3 d s ep
In he p e ious s ep, he daugh e should ha e inhe i ed a "2" in he second posi ion
om he a he , bu his would ha e caused a con lic since he "2" appea ed in he
daugh e in he 5 h posi ion. The e o e, we used he p e iously de ined se o exchanges
whe eby he "2" has been exchanged o a "1", which is inally displayed on he second
posi ion o he daugh e . The same applies o he hi d and inal posi ions o he daugh e .
This ac is also gi en in he i s , hi d and las posi ions o he son.

Ope a ions esea ch in business adminis a ion and managemen
27
Ano he c osso e which has been de ined o his ype o p oblems is he o de
c osso e p oposed by Da is (1985). As in he p e ious c osso e , he i s s ep consis s
o andomly gene a ing wo c osso e poin s k1 and k2 so ha 1 d k1 d k2 d l. In he same
way as in he PMX, each o he descendan s inhe i s he genes con ained be ween
posi ions k1 and k2 om one pa en . The di e ence om he p e ious c osso e is he
ollowing: he emaining genes a e now inhe i ed by he o sp ing in he ela i e o de in
which hey appea in he o he pa en . Le us see he applica ion in he nex example.
Suppose again ha k1=4 and k2=7:
1
3
4
6
2
5
8
7
9
Mo he Daugh e
"
"
"
"
2
5
8
"
"
3
2
5
7
1
9
4
6
8
Fa he Son
"
"
"
"
1
9
4
"
"
Figu e 9.6(a). O de c osso e example: 1s s ep
Now he daugh e will inhe i he genes ma ked as ?, in he ela i e o de in which
hey appea in he a he . Tha is, he daugh e has only inhe i ed he genes "2", "5" and
"8", so she mus inhe i he es . These will be inhe i ed one by one keeping he ela i e
o de in which hey appea in he a he . The ela i e o de o hese genes in he a he is
3 - 7 - 1 - 9 - 4 - 6:
1
3
4
6
2
5
8
7
9
Mo he Daugh e
3
7
1
9
2
5
8
4
6
3
2
5
7
1
9
4
6
8
Fa he Son
"
"
"
"
1
9
4
"
"
Figu e 9.6 (a). O de c osso e example: 2nd s ep
The main di e ence be ween he i s h ee c osso e echniques exposed (one-poin
c osso e , wo-poin c osso e and mul i-poin c osso e ) wi h espec o he men ioned
la e (PMX and o de c osso e ) is ha he la e ones inco po a e p oblem-speci ic
knowledge, while in he o me , no e e ence has been made a all o he ype o p oblem
hey sol e. One o he ad an ages o inco po a ing p oblem-speci ic knowledge is ha
non easible solu ions which a e some imes di icul o manage can be a oided (as could
ha e happened in he a eling salesman p oblem i we had used any o he i s h ee
echniques).
Chap e 9.Me aheu is ic echniques: gene ic algo i hms
27
9.1.5. MUTATION
Once he c osso e p ocess has inished he mu a ion p ocedu e is applied. The
pu pose o his p ocess is o in oduce some a iabili y in o he popula ion, in oducing
some new ea u es o cha ac e is ics in indi iduals, which we e in he popula ion in he
pas , bu we e los du ing he p ocess o e olu ion. Tha is, he mu a ion, unlike he
p ocess o c osso e , is a kind o blind sea ch ha seeks o ensu e ha in he solu ion
space he e is no poin wi h a ze o p obabili y o being examined.
Mu a ion a ec s each o he genes o each o he indi iduals in he popula ion wi h a
ce ain p obabili y, he mu a ion p obabili y, Pm, which is usually qui e small (much
smalle han he c osso e p obabili y). Tha is, each and e e y one o he genes has equal
p obabili y o being a ec ed by he mu a ion. Mu a ing a gene consis s o al e ing i s
alue.
The simple mu a ion consis s o explo ing each indi idual, and o each o i s genes,
gene a e a andom numbe be ween 0 and 1, so ha i he numbe is less han o equal o
Pm, hen he alue o ha gene is chosen andomly among he emaining symbols o he
alphabe . As wi h he c osso e ope a o , mu a ion may also inco po a e p oblem-speci ic
knowledge.
9.1.6. APPLICATIONS: THE TRAVELLING SALESMAN PROBLEM
Since he me aheu is ic echniques in gene al and he gene ic algo i hms in pa icula
a e sui able o be used in combina o ial op imiza ion p oblems, hey ha e many
applica ions in he ield o decision making in adminis a ion and business managemen .
Below he e a e some examples o gene ic algo i hms ha ha e been success ully
designed and applied o sol e business and managemen p oblems such us: s ock
exchange index p edic ion, collec ion ou es o eigh ehicles, esou ce alloca ion in
p ojec scheduling, alloca ion o human esou ces o cons uc ion, shi s, in en o y
managemen , economic p edic ions, e c.
The a elling salesman p oblem is one o he classic p oblems in Ope a ional
Resea ch in which a salesman mus isi a numbe o ci ies and he wan s o ind he
op imal pa h ha minimizes he o al dis ance o a el. Take he ollowing simple
example.
A a elling salesman o he ADESA company has o plan isi s o be made o some
o his cus ome s o e he ollowing week. The e a e en cus ome s o isi and hey a e
loca ed in Alican e, Valencia, Se illa, Cádiz, La Co uña, San ande , Mad id, Ba celona,
Ciudad Real and Zamo a. Figu e 9.7 shows he dis ance be ween each pai o ci ies on
he usual ou e used by he a eling salesman ( oad, highway, eeway, e c.).
We hen seek a cyclic ou e o him o isi e e y ci y once and inish in he same ci y
whe e he s a ed. Thus, he same ou e would be alid o any o he s a ing ci ies. Fo
example, i he op imal ou e was
ALÆ VLCÆBCNÆCRÆSANÆCORÆSEVÆCADÆZAMÆMAD
Ope a ions esea ch in business adminis a ion and managemen
27
we could choose any o he ci ies as he s a ing ci y. I we s a om Alican e, he i s
ci y o isi will be Valencia and hen Ba celona, Ciudad Real, San ande , Có doba,
Se illa, Cádiz, Zamo a, Mad id and back o Alican e. I we s a om Có doba ins ead,
we will go in he i s place o Se illa and hen o Cádiz, Zamo a, Mad id, Alican e,
Valencia, Ba celona, Ciudad Real, San ande and back o Có doba. Ob iously, he o al
dis ance a elled in bo h ou es is exac ly he same.
Figu e 9.7. Dis ances be ween ci ies
The abo e p oblem has many o he applica ions such as he collec ion o money in
ci y phone boxes, he es ablishmen o a ib e op ic line be ween a g oup o use s o he
deli e y o pizzas o a pa icula deale .
The e a e se e al al e na i es o sol e he abo e p oblem. The i s is o p esen a
bina y linea p og amming model. The e a e di e en possibili ies o i s o mula ion. In
one o hem, he esul ing model would ha e a o al o 100 bina y a iables and 101
cons ain s. In gene al e ms, wi h his o mula ion, he ma hema ical model would ha e
a o al o n2 a iables and n2 +1 cons ain s, whe e n is he numbe o ci ies. In many
cases, hese models a e no sol able in p ac ice, making i necessa y o employ heu is ics
o me aheu is ics. Le us see how o design a gene ic algo i hm o sol e he abo e
men ioned p oblem.
Chap e 9.Me aheu is ic echniques: gene ic algo i hms
27
Solu ions encoding
To design an app op ia e encoding o he solu ions o he p oblem, we ha e o hink
abou how o exp ess a solu ion o i . In his p oblem, a solu ion can be ep esen ed by he
o de in which he ci ies should be isi ed, o example:
MADÆVALÆALÆCADÆSEVÆCORÆCRÆZAMÆSANÆBCN
would be a way o exp essing a solu ion, conside ing ha om Ba celona we would
inally e u n o Mad id.
Thus, any pe mu a ion o he ci ies, ep esen s a easible solu ion o he p oblem. One
way o ep esen he solu ions would be o encode hem using o de ed lis s in which each
gene is one o he ci ies o isi . The abo e solu ion can be exp essed as:
MAD
VLC
AL
CAD
SEV
COR
CR
ZAM
SAN
BCN
To simpli y he no a ion, om now on we will ep esen each ci y by hei o de in he
lis o names in alphabe ical o de , so ha he abo e solu ion would be ep esen ed as:
6
9
1
3
8
5
4
10
7
2
Wi h he abo e encoding, any lis ha consis s o a pe mu a ion o ci ies ep esen s a
easible solu ion o he p oblem. We wan o ob ain he bes , ie he op imal solu ion among
all he easible solu ions. The e a e n! di e en pe mu a ions o a p oblem wi h n ci ies.
In his case we would ha e a o al o 10!=3,628,800 possible o de ings.
Ini ial Popula ion
Since any pe mu a ion o he ci ies ep esen s a solu ion o he p oblem, a simple and
low compu a ional e o me hod o c ea e he ini ial popula ion would consis o
gene a ing andom solu ions. An al e na i e could be o apply heu is ic algo i hms ha
ga e us solu ions o he p oblem and use hese as ini ial popula ion. Bo h me hods could
also be combined o gene a e he ini ial popula ion.
An impo an pa ame e o conside in he algo i hm is he size o he popula ion ha
we a e going o manage. I is common o use a s anda d size o 50 o 100 indi iduals,
al hough o he sizes may be ad isable. The size is o en de e mined a e some
p elimina y es s.
Ope a ions esea ch in business adminis a ion and managemen
27
E alua ion
I is necessa y o de ine a unc ion ha assigns a i ness alue o each solu ion, which
indica es he alue o he solu ion in ela ion o he objec i e. In ou case, he objec i e is
o minimize he o al dis ance a elled along he ou e, so ha he bes solu ion would be
he one whose o al dis ance is minimal.
6
9
1
3
8
5
4
10
7
2
Solu ion ep esen s a ou e in which he o al dis ance is 3743 kilome es. The o al
dis ance a elled could be he di ec i ness alue, so ha he bes indi iduals would be
hose who ha e a lowe i ness alue. Howe e , many s anda d mechanisms (mainly
selec ion ones) used in gene ic algo i hms a e designed o maximize he i ness alues.
The e o e, we could ans o m he i ness alues o he indi iduals so ha he bes
indi iduals ha e he highes i ness alues and no he lowes . Tha is, he op imal solu ion
o his p oblem should ha e he highes possible i ness alue. One way o doing i ,
amongs many o he s, would be o es ablish an uppe bound on he o al dis ance a elled
and o sub ac he alue o his dis ance bound o each indi idual in he popula ion. One
way o es ablish an uppe bound on he dis ance a elled would be o choose he g ea es
dis ance om each o he columns o he able and add hem. Thus, his uppe bound
would be gi en by:
OF_Uppe _bound = 815+1284+1284+811+908+663 +1056 +1046 +808 +988=9663
Now, he i ness alue o each indi idual would be ob ained by sub ac ing, om he
p e ious bound, he dis ance o he ou e ha i ep esen s. Thus, we would ge an
adequacy alue o 9663-3743=5920 o he solu ion shown abo e, which ep esen ed a
ou e o 3743 kilome es. The solu ion
2
4
6
8
10
1
3
5
7
9
ep esen ing a ou e o 5511 kilome es, would ha e a i ness alue o 4151 lowe han
he p e ious one. The op imal solu ion would ha e he highes i ness alue and he wo s
solu ion would ha e he lowes i ness alue among all possible.
Selec ion
Any selec ion mechanism ou lined in he p e ious sec ion could be used in his
example.

Chap e 9.Me aheu is ic echniques: gene ic algo i hms
27
C osso e
Fo his p oblem and wi h he solu ions encoded in his way, we could apply any ype
o p e iously de ined c osso e mechanism ha wo ks o pe mu a ions, o example
PMX c osso e o o de c osso e bo h p esen ed in sec ion 9.1.4 o his chap e . We
could also de ine a speci ic ype o c osso e o his p oblem, aking in o accoun hei
special condi ions and inco po a ing hem o gene a e he o sp ing in an e icien way.
We should also se he c osso e p obabili y. Values a ound 80-90% a e o en used,
bu , as wi h he popula ion size, i is usually se a e pe o ming some es s.
Mu a ion
The mu a ion in ol es making andom changes o a solu ion mimicking he mu a ions
ha occu on he gene ic ma e ial o li ing c ea u es in na u e. Such mu a ions could make
desi able o undesi able a ibu es appea in indi iduals. I mo es h ough he solu ion
and each gene is mu a ed wi h a ce ain p obabili y o mu a ion, which is usually low, a
a ound 1%, al hough i can a y depending on he p oblem. Fo his p oblem, mu a ing a
single gene could consis o inse ing i a any posi ion o he ch omosome, o exchanging
i di ec ly o he on o ea ones.
A simple gene ic algo i hm such as he one desc ibed in he p eceding pa ag aphs, is
able o sol e sizable ins ances o his p oblem in e y easonable compu a ion imes
ob aining e y good solu ions which makes hese echniques he bes al e na i e o
sol ing some eal p oblems.
To sol e his p oblem wi h Sol e , we ha e wo op ions. The i s is o build a linea
p og amming model and use he me hod "Simplex LP" o sol e i . I should be bo ne in
mind ha he esul ing linea model can be la ge and he ime equi ed o sol ing i can
be ex emely long. Due o i s size i may be unsol able e en on high-end wo ks a ions.
Fu he mo e, we ha e o ake in o accoun he limi a ion in he numbe o a iables and
numbe o cons ain s o he Sol e e sion employed. In pa icula , he de aul e sion
in Excel sol es linea models wi h up o 200 a iables, wi h no limi on he numbe o
cons ain s. We could no sol e p oblems wi h 15 ci ies o mo e by o mula ing he bina y
p og amming model discussed abo e wi h Sol e .
The second op ion would consis o employing he "E olu iona y" me hod, ha uses
gene ic algo i hms and is especially designed o unsmoo hed ype p oblems. Le us see
how o easily de ine he p oblem and hen ind ou now o use he "E olu iona y" me hod
suppo ed by Excel Sol e o sol e i .
Fi s we de ine he dis ance ma ix, as shown in Figu e 9.7. This ma ix is symme ic
and ze os always appea in i s diagonal. Then we should p epa e he cells in which he
solu ion o he p oblem will be displayed once sol ed and how o calcula e, based on he
solu ion, he alue o he objec i e unc ion, ie, he o al dis ance in kilome es.
Ope a ions esea ch in business adminis a ion and managemen
2
We will use wo columns, ORDER and DISTANCE. The i s column is le blank,
because cells B16: B25 a e used o ep esen he solu ion once he p oblem has been
sol ed. Tha is, he alue in cell B17 indica es he numbe o he ci y o isi a e ha ing
isi ed he one whose numbe appea s in cell B16 and so on. The second column will
se e o calcula e he o al dis ance a elled by he salesman i you ollow he o de gi en
in he solu ion indica ed by he column ORDER. To ob ain his o de , we will use he
INDEX unc ion.
The syn ax o his unc ion is:
= INDEX (a ay, ow_num, column_num)
and i e u ns he alue o an i em in a able o ma ix selec ed by he ow and column
indices gi en. Thus, in cell C17 we wan o calcula e he dis ance om he ci y whose
numbe appea s in cell B16 o he ci y whose numbe appea s in cell B17, o which we
w i e =INDEX ($C$2:$L$11; B16; B17) in ha cell and d ag he o mula o cells C18 o
C25.
In cell B16 we w i e =INDEX (C2:L11; B25; B16). I Column B has been le blank,
# VALUE! will appea in hese cells when w i ing he o mulas, since we a e using
nume ical alues ha do no exis in hese o mulas. This is no a mis ake. I we ill in
cells B16: B25 wi h a lis o alues be ween 1 and 10 (a easible solu ion o he p oblem)
we see ha in column C he co esponding dis ance be ween each pai o ci ies on he
ou e is displayed.
Finally, in cell C26 we calcula e he sum o he dis ances a elled by yping =SUM
(C16: C25). The alue displayed in he cell is he o al dis ance a elled, which we wan
o minimize.
We can now p ess he bu on o open he Sol e dialog box and de ine he model o
be sol ed, based on he shee se , as shown in Figu e 9.8.
Se Objec i e: in his case, he o al dis ance a elled is displayed in cell C26.
To: Ou goal is o minimize he o al dis ance.
By Changing Va iable Cells: On he shee we ha e ese ed space o he a iables in
cells B16 o B25
Subjec o he Cons ain s: Clicking he Add bu on, Sol e displays he dialog box o
add cons ain s:
Cell Re e ence: selec he ange o cells ha ep esen he a iables, ie he ange B16:
B25
Chap e 9.Me aheu is ic echniques: gene ic algo i hms
2
In he cen e o his dialog box, which is no mally used o indica e he sign o inequali y
o he cha ac e o he a iables, we selec di , which indica es ha in hese cells Sol e
mus calcula e a pe mu a ion o he in ege alues ha a e consecu i e and s a a 1, ha
is, a pe mu a ion o he in ege s be ween 1 and 10 in ou case.
Figu e 9.8. Sol e Pa ame e s
Selec a sol ing me hod: we selec "E olu iona y" o apply he mechanism based on
gene ic algo i hms. Mo eo e , he way in which we ha e de ined he p oblem makes i
impossible o use he LP Simplex me hod. Then, be o e sol ing he p oblem, we can
con igu e his me hod, o which we mus p ess he Op ions bu on and go o he ab
"E olu iona y", which displays he dialog box shown in Figu e 9.9.
Nex we se he alues shown in Figu e 9.9 o he di e en pa ame e s (as an exe cise,
he s uden could y o change he alues o he di e en pa ame e s and obse e he
e ec hey ha e on he solu ion and he ime i akes o ind i ).
Once we click Sol e, Excel s a s he sea ch o he bes solu ion. Du ing he sea ch
p ocess, in he bo om ba o he sc een, he me hod displays in o ma ion abou he
p ocess, such as he o al numbe o solu ions e alua ed and he objec i e alue o he
bes solu ion ound so a . We can in e up he sea ch p ocess by p essing he Esc key a
any ime. In his case, Sol e displays he bes solu ion ound so a . The bes solu ion
ound by "E olu iona y" Sol e o his example is shown in Figu e 9.10, ep esen ing a
o al dis ance o 3142 kilome es. So, i he a elle s a ed, o example, om Valencia
Ope a ions esea ch in business adminis a ion and managemen
28
(Ci y 9) he ou e o ollow would consis o isi ing Ba celona i s , and hen going o
San ande , Zamo a, Mad id, Ciudad Real, Có doba, Se illa, Cádiz, Alican e and
e u ning o Valencia. The e e se ou e would be equi alen , wi h he same dis ance
a elled. As he solu ion is gi en by a me aheu is ic echnique, we canno gene ally know
whe he i is he op imal solu ion o he p oblem o no . In his case we can ensu e ha i
is, because we ha e op imali y sol ed he p oblem by o he me hods and he op imal
solu ion is al eady known.
I Sol e inishes i s execu ion wi hou being in e up ed, i pe mi s he use o
gene a e wo di e en epo s, called Answe and Popula ion, which a e p esen ed in
Figu es 9.11 and 9.12.
In he Answe epo , he so wa e shows he op ions used by he esolu ion me hod,
he o al ime and he numbe o solu ions e alua ed. I also indica es he alue o he
a ge cell and he bes alue o he a iables.
Figu e 9.9. Op ions o E olu iona y Sol e
Chap e 9.Me aheu is ic echniques: gene ic algo i hms
28
The choice o he pa ame e has a signi ican in luence on he beha iou o he
algo i hm. I s ini ial alue and he manne in which his alue dec eases along he p ocess
mus be se , his is called cooling p og am. I cooling is oo as , he echnique ends o
beha e as a simple local sea ch mechanism and can be apped in a local op imum o a
low quali y solu ion. Mo eo e , i he cooling is oo slow, he unning ime o he
algo i hm can become p ohibi i e.
Apa om he empe a u e pa ame e de ini ion, he p obabili y o accep ance o a
new solu ion s’ V(s) mus also be se , whe e s is he cu en solu ion. As discussed
abo e, his p obabili y depends on he objec i e alue o he new solu ion (o i s
di e ence om he alue o he cu en solu ion) and he cu en empe a u e, . I we
deno e by
'
he di e ence be ween he objec i e alues o he cu en solu ion s and he
new solu ion s', de ined as
'
= (s’)- (s), and assuming ha we minimize he objec i e
unc ion alue, he p obabili y o accep ing s' migh be de ined by:
°
¯
°
®

'
'
o
'
0
01
)'(
/
i e
i
ssP
The abo e o mula would be a possible de ini ion o he p obabili y o accep ance.
The e a e many o he al e na i es and he esea che should be he one esponsible o
choosing i p ope ly, as was he case o he empe a u e pa ame e . Figu e 9.14 shows he
basic ope a ion o he echnique in pseudocode.
The i s s ep consis s o gene a ing he s a ing solu ion ei he andomly o by some
heu is ic p ocedu e. The empe a u e pa ame e , , mus also be ini ialized wi h a ce ain
alue. Then, hese s eps a e epea ed un il he e mina ion c i e ion is sa is ied. The se o
solu ions accessible om he cu en one is gene a ed, and a solu ion is chosen om his
se . In i s simples o m, such a solu ion is chosen andomly, al hough ano he mechanism
could be used. I his solu ion is be e han he one we had, i is accep ed as cu en
solu ion, i no i is accep ed wi h a ce ain p obabili y o accep ance. Finally he
empe a u e is dec eased.
Once he e mina ion condi ion has been sa is ied, he cu en solu ion is p oposed by
his echnique as he solu ion o he p oblem. Some o he comple ion c i e ion ha can
be se a e:
xThe se V(s) is emp y.
xA numbe o i e a ions ha e been comple ed.
xThe empe a u e eaches he minimum alue (usually 0)
xAn accep able solu ion has been ound.

Ope a ions esea ch in business adminis a ion and managemen
2
Finally, he mos ema kable di e ence be ween simula ed annealing and abu sea ch
is he use o he memo y by he la e . Recen ly, some a ia ions o he echnique, known
as hyb id echniques, ha e appea ed. They inco po a e he use o he memo y o imp o e
he e iciency o he echnique in an e ec i e way, among o he new ea u es.
Simula ed Annealing P ocedu e
Gene a e_ini ial_solu ion(s)
=ini _ emp
while no ( e mina ion_c i e ion)
Gene a e V(s)
s’ =choose solu ion om V(s)
i s’ is be e han s
s=s’
else
P=calcula e P(s-->s’, )
s=s’ wi h p obabili y P
upda e
Figu e 9.14. Simula ed Annealing: gene al p ocedu e
9.4. SUMMARY
This chap e has been dedica ed o me aheu is ic echniques in gene al and gene ic
algo i hms in pa icula . Me aheu is ic echniques a e being success ully applied o a wide
a ie y o combina o ial op imiza ion p oblems, di icul p oblems, o which exac
echniques do no allow us o ind he solu ion in many cases due o he eno mous
compu a ional e o equi ed. Fo many o hese p oblems, heu is ic echniques ha
p o ide good esul s ha e been de eloped. Howe e , me aheu is ics imp o e hese esul s
since hey make a deep sea ch o he solu ion space wi h accep able compu a ional e o .
Gene ic algo i hms a e based on he mechanisms o na u al e olu ion, guided by he
p inciple o su i al o he i es . S a ing wi h an ini ial popula ion o solu ions,
mechanisms ha mimic na u al p ocesses a ec ing he species a e applied o i , hus
e ol ing popula ions o a be e quali y. The main di e ence be ween gene ic algo i hms
and o he me aheu is ics such as abu sea ch o simula ed annealing, is ha he o me
handles a se o popula ion o solu ions a each i e a ion and he la e ones a single
solu ion pe i e a ion. These h ee echniques a e he mos used me aheu is ics, bu he e
is no one ha can always o e he bes esul s o any p oblem.
Chap e 9.Me aheu is ic echniques: gene ic algo i hms
2
9.5. SELECTED REFERENCES
1. Alca az, J. (2001), Gene ic Algo i hms o Resou ce-Cons ained P ojec Scheduling,
P oQues In o ma ion and Lea ning.
2. Alca az, J. and Ma o o, C. (2006), A hyb id gene ic algo i hm based on in elligen
encoding o p ojec scheduling, en: Pe spec i es in mode n p ojec scheduling,
Sp inge .
3. Goldbe g, D.E. (1989), Gene ic Algo i hms in Sea ch, Op imiza ion, and Machine
Lea ning, Addison Wesley.
4. Glo e , F. y Laguna, M. (1997), Tabu Sea ch, Kluwe Academic Publishe s.
5. Holland, H.J. (1975), Adap a ion in na u al and a i icial sys ems, Uni e si y o
Michigan P ess.
6. Raywa d-Smi h, V.J., Osman, I.H., Ree es, C.R. and Smi h, G.D. (Edi o s) (1996),
Mode n Heu is ic Sea ch Me hods, John Wiley and Sons.
7. VoE, S., Ma ello, S., Osman, I.H. y Roucai ol, C. (Edi o es) (1999), Me a-heu is ics.
Ad ances and T ends in Local Sea ch Pa adigms o Op imiza ion, Kluwe Academic
Publishe s.
8. Wins on (2011), Mic oso Excel 2010: Da a Analysis and Business Modeling,
Mic oso P ess.
9.6. CASE STUDIES
CASE STUDY 1
Sol e he a elling salesman model om sec ion 9.1.6 elimina ing he ci ies o Zamo a
and Cádiz and including he ci y o Badajoz.
1. Wha is he minimum o al dis ance a elled?
2. How long did Sol e ake o sol e he p oblem?
3. Does he solu ion p o ided by Sol e change i we limi he maximum numbe o
subp oblems sol ed o 200?
4. Wha is he ou e o ollow i we wan o s a and inish in Mad id? And wha i
he pa h should s a and end in Zamo a?
Ope a ions esea ch in business adminis a ion and managemen
29
CASE STUDY 2: SCHEDULING JOBS WITH DUE DATES WITH EXCEL
EVOLUTIONARY SOLVER
Among he combina o ial op imiza ion p oblems in which me aheu is ic echniques
a e he only al e na i es in p ac ice, we can men ion he job scheduling o sequencing
ope a ions. In gene al, we ha e o decide he o de in which a se ies o asks o ope a ions
a e pe o med in o de o op imize a ce ain c i e ion. The ollowing case p esen s a
simple example o be sol ed wi h E olu iona y Sol e .
We ha e a se o 16 jobs ha need o be pe o med sequen ially and we know he
p ocessing ime in days, and he deli e y da e in days om he da e on which he
execu ion o he i s job s a s o each o hem. These deli e y o due da es a e
app oxima e in he sense ha hey can be exceeded, bu we mus also y o ensu e ha
he amoun o ime by which a job exceeds he deli e y da e is no oo long.
In sho , he p oblem consis s o de e mining he o de in which jobs a e o be execu ed
so as o minimize he o al numbe o days ha a delay is incu ed in e ms o due da es.
Figu e 9.15 shows an Excel sp eadshee wi h he p oblem da a. The jobs ha e been
numbe ed om 1 o 16. The execu ion imes and due da es, in days, a e p esen ed in
columns B and C.
In he p e ious shee we ha e included h ee addi ional columns. The column O de
is ese ed o e lec he solu ion p o ided by Sol e , ie, i mus con ain a pe mu a ion o
jobs. In column Finish, he numbe o days un il he end o he execu ion o a job, i
execu ed in he o de shown in column D, mus be calcula ed. So, i , as is now shown in
ha column, he i s scheduled job we e job 16, wi h a du a ion o 5 days, and he second
we e job 1, wi h a du a ion o nine days, his wo k would inish a e 14 days. In he las
column we calcula e he delay o each job, wi h espec o he due da e, i execu ed in
he speci ied o de . I job 1 inishes in 14 days, he delay is 0. Finally, in cell F18 we
calcula e he sum o days o e due, which would be 303 in his case.
Sol e he abo e p oblem wi h E olu iona y Sol e and answe he ollowing
ques ions:
1. In wha o de should he jobs be sequenced?
2. When does job 12 inish? Wha day should he execu ion o job numbe 4 s a ?
3. How many days will job numbe 8 be delayed wi h espec o i s due da e?
4. Wha is he sum o he days delayed?
5. Which is he job wi h he longes delay?
Chap e 9.Me aheu is ic echniques: gene ic algo i hms
29
Figu e 9.15. De ining he job scheduling p oblem wi h Excel

ANNEX 1
THE SOLVER OF THE
EXCEL
SPREADSHEET
Annex 1.The Sol e o he Excel sp eadshee
295
A1.1. FORMULATING AN OPTIMIZATION MODEL
Sp eadshee s a e da a analysis ools mos commonly used in he business
en i onmen . Among i s bene i s o imp o ing decisions i is he possibili y o sol ing
op imiza ion models -linea , in ege and nonlinea p og amming models- wi h Sol e
ool. To access Sol e i is necessa y o ins all i i s . Fo Excel Sp eadshee 2010 and
2013 you should go o O ice bu on, choose Excel Op ions, and in he Add-Ins dialogue
box, check whe he Sol e is ins alled o no . I i has no been ins alled, selec Excel Add-
Ins in he Manage window and click he Go bu on. This b ings up a window wi h he
add-ins ha inco po a e by de aul Excel and he ones you wan o ins all can be selec ed.
To ins all Sol e we ma k i and click he OK bu on. Once ins alled, you can access he
Sol e on he Da a ab.
The Sol e ool a ailable in Excel 2010 and 1013 in oduces h ee me hods o sol ing
op imiza ion models, Simplex LP, GRG Nonlinea and E olu iona y. We will use he
example o ene gy p oduc ion and pollu ion con ol desc ibed in Chap e 2 o explain he
inpu o a linea p og amming model in he sp eadshee and i s esolu ion by Simplex LP
me hod. Chap e 9 desc ibes how o use he E olu iona y me hod o sol e he T a eling
Salesman P oblem (TSP).
We always s a en e ing he p oblem da a on a shee . The da a o he p oblem we
wan o sol e ha e been in oduced as we can see in Figu e A1.1. The da a cells a e
shaded in ligh yellow. To acili a e he building and in e p e a ion o he model i is
con enien o use ange names. So in his case we used S eamP oduc ion as a ange
names o cells E4:F4, RHS o I6:I9 and TechnicalCoe icien s is he name o he cell
ange E6:F9. To en e a ange name we jus ha e o selec he cells and go o
Fo mulas/De ine name. Range names can no con ain spaces. So i you ha e mo e han
one wo d, i is use ul o begin each wo d wi h a capi al le e and elimina e spaces o
acili a e unde s anding.
As we ha e al eady seen, in Chap e s 1 and 2, o co ec ly o mula e an op imiza ion
model in gene al and a linea p og amming model in pa icula , we need o know:
1. The decisions o make.
2. The cons ain s we ha e.
3. How o measu e he pe o mance o ou decisions.
In his case he decisions a e ons o each ype o coal ha we will use o p oduce
s eam, which is ans o med in o ene gy, i.e. he model a iables. Cons ain s ha limi
he alues ha can ake hese decision a iables a e he i m's echnological capaci y
(capaci y o he loading sys em and he pul e ize ) and en i onmen al egula o y
es ic ions limi ing he elease o pollu an s (smoke and sul u oxide). The mo e ene gy
he company can p oduce wi h a ailable esou ces and mee ing en i onmen al egula ions
he be e ou decisions. The e o e, he objec i e is o maximize he o al s eam
p oduc ion.
Ope a ions esea ch in business adminis a ion and managemen
296
Table A.1.1. Da a o he ene gy p oduc ion and pollu ion con ol p oblem
(Chap e 2)
A
B
C
D
E
F
G
I
1
ENERGY PRODUCTION AND POLLUTION CONTROL
2
3
Coal A
Coal B
4
S eam p oduc ion in housands o
lb/ on
24
20
5
RHS
6
Emission o smoke
kg/h
0,5
1
12
7
Loading ins alla ion
1
1
20
8
Pul e ize capaci y
1,5
1
24
9
Emission o sulphu
1200
-800
0
10
The decision a iables will appea in cells E12:F12 o which we assigned he ange
name UsedCoal. The cells whe e Sol e mus s o e he alue o he a iables o he sol ed
model should be ese ed o ha pu pose. They a e he a iable cells, which may ini ially
be assigned a ze o alue and a e sol ing he model we will ha e he op imal a iable
alues. The cons ain alues a e in oduced in Capaci yU iliza ion ange in he cells
G6:G9. These cells collec he i s membe o he cons ain s o he p oblem (Chap e 2,
sec ion 2.2.3). As shown in Figu e A.1.2 i is calcula ed:
G6= =SUMPRODUCT(E6:F6;UsedCoal)
G7=SUMPRODUCT(E7:F7;UsedCoal)
G8=SUMPRODUCT(E8:F8;UsedCoal)
G9=SUMPRODUCT(E9:F9;UsedCoal)
Fo his small example, we could ha e di ec ly used he p oduc and he sum.
Howe e , wi h he SUMPRODUCT unc ion o he sp eadshee we illus a e how o
in oduce cons ain s o linea models. These cells ep esen he alue o he le hand side
(LHS) o he cons ain s in he op imal solu ion. The e o e, hey a e esul cells which
con ain he alues o he le hand o he cons ain s, i.e. hey depend on he alue ha he
decision a iables ha e aken.
In cells H6:H9 we inpu he signs o he cons ain s o acili a e unde s anding he da a
in he sp eadshee . To sol e he model hese condi ions o lowe , highe o equal ope a o s
mus be speci ied in a dialogue box as we will see in sec ion A1.2.
Annex 1.The Sol e o he Excel sp eadshee
303
Table A.1.4. Sol e Answe epo o he ene gy p oduc ion and pollu ion con ol p oblem
(Chap e 2)
Mic oso Excel 14.0 Answe Repo
Wo kshee : [S eamP oduc ion.xls]Da a1
Repo C ea ed:
Resul : Sol e ound a solu ion. All Cons ain s and op imali y condi ions a e sa is ied.
Sol e Engine
Engine: Simplex LP
Solu ion Time: 0,016 Seconds.
I e a ions: 3 Subp oblems: 0
Sol e Op ions
Max Time Unlimi ed, I e a ions Unlimi ed, P ecision 0,000001
Max Subp oblems Unlimi ed, Max In ege Sols Unlimi ed, In ege Tole ance 1%, Assume NonNega i e
Objec i e Cell (Max)
Cell
Name
O iginal Value
Final Value
$I$12
To alS eamP oduc ion
0
408
Va iable Cells
Cell
Name
O iginal Value
Final Value
In ege
$E$12
Coal A ( on/h)
0
12
Con in
$F$12
Coal B ( on/h)
0
6
Con in
Cons ain s
Cell
Name
Cell Value
Fo mula
S a us
Slack
$G$6
Emission o smoke kg/h
12
$G$6<=$I$6
Binding
0
$G$7
Loading ins alla ion
18
$G$7<=$I$7
No Binding
2
$G$8
Pul e ize capaci y
24
$G$8<=$I$8
Binding
0
$G$9
Emission o sulphu oxide
9600
$G$9>=$I$9
No Binding
9600
Table A.1.4 p esen s he Answe epo , which has h ee sec ions, which e e o he
objec i e unc ion, a iables and cons ain s. The i s sec ion shows he alue o he
objec i e unc ion, which in ou p oblem is 408, which means ha he maximum s eam
p oduc ion is a 408,000 pounds o s eam pe hou . The second sec ion displays he
op imal solu ion, namely he op imum alue o each o he a iables, and he na u e o
hese (con inuous in his case).
Finally, o each o he cons ain s o he model i i s indica es he alue aken by
he le hand side o he cons ain . The s a us indica es whe he he cons ain is s ic ly
sa is ied (binding) o no (non-binding). The las column indica es he slack o ha
cons ain .

Ope a ions esea ch in business adminis a ion and managemen
304
Sensi i i y epo (Table A.1.5) p esen s in o ma ion ela ing o sensi i i y analysis.
Fo each a iable he epo indica es he alue aken in he op imal solu ion, he educed
cos ( he quan i y ha should imp o e he coe icien o he a iable, i i s alue is ze o,
so i could ake a nonze o alue in he op imal solu ion) and he possible inc ease and
dec ease o he coe icien o he a iable wi hou changing he op imal solu ion.
Rega ding he cons ain s Shadow P ice gi es i s oppo uni y cos and he in e al in
which i s igh hand side may di e om he ini ial alue so ha he oppo uni y cos
emains cons an .
Table A.1.5. Sol e Sensi i i y epo o he ene gy p oduc ion and pollu ion con ol p oblem
(Chap e 2)
Mic oso Excel 14.0 Sensi i i y Repo
Wo kshee : [S eamP oduc ion.xls]Da a1
Va iable Cells
Final
Reduced
Objec i e
Allowable
Allowable
Cell
Name
Value
Cos
Coe icien
Inc ease
Dec ease
$E$12
Coal A ( on/h)
12
0
24
6
14
$F$12
Coal B ( on/h)
6
0
20
28
4
Cons ain s
Final
Shadow
Cons ain
Allowable
Allowable
Cell
Name
Value
P ice
R.H. Side
Inc ease
Dec ease
$G$6
Emission o smoke kg/h
12
6
12
4
4
$G$7
Loading ins alla ion
18
0
20
1E+30
2
$G$8
Pul e ize capaci y
24
14
24
4
6
$G$9
Emission o sulphu oxide
9600
0
0
9600
1E+30
A1.3. SOLVING OTHER TYPES OF MODELS
As al eady discussed abo e Sol e also inco po a es, apa om Simplex LP, ha
sol es any linea p og amming model (con inuous o in ege ), wo o he echniques, GRG
Nonlinea and E olu iona y ha allow us o sol e nonlinea models, whe he smoo h o
non-smoo h.
Nonlinea models a e hose in which he objec i e unc ions and/o any o he
cons ain s con ains e e ences o o mulas ha do no ollow he pa e n a iables
mul iplied by cons an s. I , o example, x and y a e a iables o he model, any
appea ance o e e ences o he same o mulas as below would make he model nonlinea :
x x2
x xy
x sin x
x xy
Annex 1.The Sol e o he Excel sp eadshee
305
I he model only includes unc ions wi h o dina y ma hema ical ope a o s as abo e,
we can use he GRG Nonlinea me hod o sol e i . Tha p ocedu e uses he gene alized
educed g adien me hod, based on inding poin s whe e he slope is ze o, he condi ion
me by he maxima and minima. In gene al, me hods o sol ing nonlinea models s a
sea ching a a gi en s a ing poin and hey app oach he solu ion in successi e i e a ions,
so ha he solu ion ound may depend on he chosen s a ing poin , pa icula ly in
unc ions ha may ha e di e en local maxima o minima. To a oid his incon enience,
GRG Nonlinea ea u es a Mul iple S a op ion, which allows us o speci y he numbe
o s a ing poin s. The p ocess sol es he p oblem s a ing om each o hese poin s and
e en ually e u ns he bes solu ion ound. This op ion wo ks bes i a iables a e imposed
easonable uppe and lowe bounds.
The GRG Nonlinea me hod is no sui able when in he model e e ences including
non-smoo h unc ions appea , such as MAX, MIN, ABS, IF, SUMIF, SUMIFS,
COUNTIF, COUNTIFS. In his case, we ecommend using E olu iona y me hod, based
on gene ic algo i hms, desc ibed in Chap e 9. The op ions o his me hod allows us o,
among o he hings, speci y he size o he popula ion o be used, se he mu a ion a e o
limi he ime ha can elapse wi hou imp o ing he alue o he objec i e unc ion o
comple e he sea ch p ocess. In Chap e 9 i is desc ibed how o use his me hod o sol e
wo op imiza ion p oblems; he a eling salesman p oblem and a p oblem o sequencing
jobs.
A1.4. BUILDING GOOD SPREADSHEET MODELS
The e a e many ways o ep esen ing a model in a sp eadshee and one o he
ad an ages is p ecisely he lexibili y i o e s. Al hough Excel has many ea u es such as
ange names, shadows, bo de s... ha c ea e "good" models ha a e easy o unde s and,
debug and modi y, i is also easy o c ea e bad models. He e a e some ips ha will
acili a e he cons uc ion o good models.
1. En e , o ganize and clea ly iden i y he da a
The ull model is buil on he da a s uc u e. We mus ca e ully in oduce and p esen
all da a be o e he es o he model. The s uc u e o he model should i he da a as
much as possible.
We should g oup he da a con enien ly and pu labels ha clea ly iden i y hem. In
he da a p esen ed in a able we should pu heade s wi h an o e iew and each column
and each ow should ha e he name ha iden i ies he inpu da a. We mus also iden i y
da a uni s. En e da a o ien ed in he same way is no only clea e , bu also allows us o
use he SUMPRODUCT unc ion. This unc ion assumes ha he wo anges ha e exac ly
he same numbe o ows and columns.
Ope a ions esea ch in business adminis a ion and managemen
306
2. En e each da a only in a single cell, do no epea da a in di e en cells
I da a is needed in mo e han one o mula, always e e o he o iginal da a cell ins ead
o epea ing he da a in di e en si es. This model could be modi ied mo e easily. I he
da a change, we would only need o modi y hem once. We would no need o sea ch in
he whole model how many imes he da a ha ha e changed appea .
3. Sepa a e da a om o mulas. The o mulas should e e o he da a cells
A oid using da a di ec ly in o mulas. You ha e o en e he numbe s in he da a cells
and e e o hem whe e necessa y. Sepa a ing da a om he o mulas has a double
ad an age. Fi s ly, all da a a e isible in he sp eadshee ins ead o being hidden in he
o mulas. To iew he da a makes he model easie o in e p e . Secondly, he model is
easie o modi y because changing da a only equi es modi ying he co esponding da a
cell. We do no need o modi y o mulas. This is impo an in he sensi i i y analysis.
4. Keep he model simple and as easy o in e p e as possible
A oid using complica ed unc ions o Excel when he e a e a ailable unc ions ha
a e simple and easie o in e p e . Use whene e possible SUMPRODUCT o SUM. This
makes he model easie o in e p e and helps o ensu e ha he model is linea (linea
models a e much easie o sol e han nonlinea ).
5. Use ange names
One way o e e o a g oup o cells o a cell in a o mula in he sp eadshee is o
iden i y i wi h a le e and numbe . A be e al e na i e is o use desc ip i e ange names.
To do his, selec he cells and pu he ange name. The ange names a e especially
impo an when w i ing a o mula o a cell esul . W i ing he o mula in e ms o ange
names makes i easie o in e p e . Range names also make ha he desc ip ion in he
Sol e model is easie o unde s and. In gene al, i is ad isable o name a ange o each
g oup o da a cells, a iable cells, objec i e cell and he wo sides o he cons ain s, LHS
and RHS.
As no spaces a e allowed in ange names, we should s a each wo d wi h a capi al
le e o enhance unde s anding. When we modi y a model using ange names we ha e o
ensu e ha he ange names s ill e e o he co ec cells. When ows o columns a e
inse ed, i mus be done in he middle o he ange, and no a he end.
6. Using absolu e and ela i e e e ences o copy o mulas easily
When we need o use a o mula se e al imes, we can in oduce i once and hen use
Excel commands o eplica e. Using absolu e and ela i e e e ences in he o mula no
only helps building models, bu also makes hem easie o change.
Annex 1.The Sol e o he Excel sp eadshee
307
7. Use bo de s, shading and colou s o di e en ypes o da a
I is e y impo an o dis inguish he da a cells, a iable cells, he esul cells and he
objec i e cell in he sp eadshee . The use o shadows, bo de s and colou s help us
isualize he model quickly.
8. View he en i e model in he sp eadshee
The Sol e uses a combina ion o sp eadshee and he Sol e dialogue box o speci y
he model o be sol ed. Fo example, we can speci y he inequali ies in he Sol e dialogue
box wi hou pu ing hem in o he sp eadshee . Howe e , i is ecommended ha each
model elemen appea s on he sc een. This is use ul o la e upda es. In pa icula , all he
elemen s o a cons ain mus appea on he sc een. A good es is no using he Sol e
dialogue box in o de o unde s and any model elemen . We mus be able o iden i y he
a iable cells, he objec i e cell and cons ain s only by looking a he sp eadshee .

ANNEX 2
THE MODELLING LANGUA
GE
AND OPTIMIZER:
LINGO
Annex 2. The modelling language and op imize : LINGO
311
A modelling language and an op imize a e necessa y ools o sol e eal decision
making p oblems in p ac ice. Thus hey a e also essen ial in eaching and lea ning he
echniques ha allow us o o mula e, model and sol e eal decision making p oblems.
Among so wa e packages a ailable in he ma ke we ha e chosen LINGO o se e al
easons. Fi s , i is an op imiza ion so wa e ha inco po a es a modelling language which
allows gene a ing big op imiza ion models easily. I also pe mi s impo ing and expo ing
da a om and o Excel and da abases. Fu he mo e i is a ailable o Linux pla o m and
a wide a ie y o ha dwa e sys ems (compa ible PC, Macin osh and wo king s a ions). As
well as his o di e en sizes o models, om s uden 's e sions ha may sol e p oblems
wi h 200 a iables and 100 cons ain s, o mo e powe ul e sions ha allow sol ing
models wi h an unlimi ed numbe o a iables and cons ain s. E alua ion e sions can
be downloaded om he LINDO Sys ems websi e (www.lindo.com).
A2.1. FEATURES OF LINGO
LINGO is an op imize ha allows us:
1. To sol e di ec models consis ing o equa ions wi h independen a iables and
simul aneous equa ion sys ems.
2. To sol e op imiza ion models in which an objec i e unc ion has o be
maximized o minimized and whose a iables mus ul il a numbe o cons ain s.
I sol es linea , in ege , nonlinea and s ochas ic p og amming models. A Global
op imize is also included o ind a global op imum in nonlinea p og amming. In
addi ion a new ea u e is Chance-Cons ained P og amming. In his case one o
mo e se s o cons ain s a e allowed o be iola ed wi h a speci ied p obabili y.
This ool is use ul when ce ain esou ces o demands a e andom.
3. To gene a e models h ough a modelling language, pa icula ly use ul o la ge
models wi h many equa ions o simila s uc u e. Fu he mo e, i allows he
c ea ion o he s uc u e o he model and keeping i apa om he model's da a.
Da a can be loaded om a ile o sp eadshee .
When using he modelling language, he sys em con e s he exp essions o he
equi ed o m o be sol ed wi h he app op ia e algo i hm. Fo linea p og amming
models he sys em uses he e ised simplex me hod. I also has he in e io poin
algo i hm (Ba ie Sol e ), use ul o sol ing linea and quad a ic models wi h a e y big
numbe o a iables and cons ain s. I he sys em de ec s in ege a iables, i inds he
solu ion wi h he b anch and bound algo i hm, adding cu s o limi he non-in ege
easible egion. Fo nonlinea models, i uses he gene alized educed g adien algo i hm
and he sequen ial linea p og amming algo i hm. A Global op imize is also included o
ind a global op imum in nonlinea p og amming. Finally, LINGO also inco po a es a
lib a y wi h s a is ical, inancial and ma hema ical o mulae.
Ope a ions esea ch in business adminis a ion and managemen
312
A2.2. ENTERING AND SOLVING MODELS
The models can be inpu in he con en ional way yping he unc ions o using he
modelling language. In bo h cases he model is be ween wo commands which a e
MODEL: and END.
Fo example, he model
Max 24 X1+ 20 X2
0.5 X1 + X2
d
1
X1 + X2
d
20
1.5 X1 + X2
d
24
1200 X1 - 800 X2
0
X1
0 X2
0
is indica ed in he ollowing way:
MODEL:
!EXAMPLE 1: ENERGY PRODUCTION AND POLLUTION CONTROL;
[OBJ] MAX = 24 * X1 + 20 * X2;
[SMOKE] 0.5 * X1 + X2 <= 12;
[LOAD] X1 + X2 <= 20;
[PULVERIZER] 1.5 * X1 + X2 <= 24;
[SULPHUR] 1200 * X1 800 * X2 >= 0;
END
No e ha in he inpu da a we ha e o ype he symbol * o mul iplica ion and
semicolon (;) o he end o a sen ence, which may be a commen , he objec i e unc ion
o cons ain s. The commen s s a wi h he exclama ion ma k (!) and he names o he
objec i e unc ion and he cons ain s in b acke s. We can also w i e a iables in he
Righ -Hand-Side (RHS) o cons ain s.
In LINGO menu, he op ion Sol e displays he op imal solu ion, and he op ion
Range he sensi i i y analysis, as shown below o he p e ious example. To ob ain he
sensi i i y analysis, i is necessa y o selec P ices & Ranges and he model has o be
sol ed p e iously. To do so go o LINGO menu / Op ions…/ Gene al Sol e / Dual
compu a ions/ P ices & Ranges.
Annex 2. The modelling language and op imize : LINGO
319
A2.4. VARIABLE DOMAIN FUNCTIONS: BOUND, FREE, INTEGER,
BINARY
AND SEMICONTINUOUS
By de aul LINGO es ic s a iables o nonnega i e alues i Va iables assumed
non-nega i es box is checked in LINGO Menu/ Op ions/ Gene al Sol e . Tha is, he
a iables can assume any eal alue om ze o o posi i e in ini y.
@BND (lowe _bound, a iable_name, uppe _bound) assigns lowe and uppe bounds
o he a iables. I is impo an o emembe ha a mo e e icien algo i hm is used o
sol e he model i he bounds a e indica ed in his way. In addi ion, bounds do no coun
as cons ain s and la ge models can be sol ed.
@FREE( a iable_name) allows he a iable o ake nega i e alues, i.e., be ween
nega i e in ini y and posi i e in ini y.
@GIN ( a iable_name) makes he a iable only ake in ege alues.
@BIN( a iable_name) makes he a iable be bina y, i.e., ake only 0/1 alues.
@SEMIC(lowe _bound, a iable_name, uppe _bound) indica es a semicon inuous
a iable which is ze o o lies wi hin nonnega i e ange. LINGO gene a es he necessa y
bina y a iables and cons ain s ha coun o he size o models.
LINGO suppo s SOS (Special O de ed Se s) and he ollowing ypes o @SOS unc ions:
@SOS1 A mos , only one a iable belonging o an SOS1 se will be g ea e han ze o.
@SOS2 A mos , only wo a iables in a SOS2 se can be di e en om ze o. I wo
a iables a e nonze o, hen he a iables will be adjacen o one ano he .
@SOS3 In he SOS3 se one a iable will be equal o 1 exac ly and all emaining a iables
will be equal o ze o.
Any a iable in SOS se s coun as in ege a iables agains he limi o in ege
a iable imposed in some e sions o LINGO.
@CARD
This unc ion is ela ed o ca dinali y se s o a iables. I allows speci ying a se o
a iables wi h a mos N a iables allowed o be nonze o. This unc ion can imp o e he
e iciency o b anch & bound algo i hm and educe he numbe o a iables and
cons ain s o he model.

Ope a ions esea ch in business adminis a ion and managemen
320
A2.5. MENUS: FILE, EDIT, LINGO, WINDOW AND HELP
LINGO o Windows has i e menus: File, Edi , LINGO, Windows and Help. We
will desc ibe some op ions b ie ly.
FILE Menu:
New (F2) c ea es a model.
Open (C l+O) opens an exis ing ex ile.
Sa e (C l+S) sa es he ac i e window as ex . I may sa e models, epo s o commands.
Sa e as (F5) sa es he ac i e window wi h he name gi en by he use in he dialog box. I can sa e
models, epo s o commands.
Close (F6) closes he ac i e window. I i is a model wi h no name o he ile has been modi ied, he
p og am asks i you wan o sa e he changes.
P in (F7) sends he in o ma ion o he ac i e window o a p in e .
P in Se up (F8) o selec a p in e .
P in P e iew (Shi +F8) o iew he documen .
Log Ou pu (F9) sends all he ollowing sc eens o a ex ile. You can selec , o e w i e on he
exis ing ile o add he ollowing ou pu .
Take Commands (F11) Use his op ion o ead ba ch iles wi h models and commands o execu e
au oma ic ope a ions.
Expo File (IMPORT and EXPORT). I se es o impo and expo iles in MPS o ma . This
o ma de eloped by IBM is use ul o ans e models o o he so wa e o pla o ms.
Da abase Use Imp. Fo en e ing use ID and passwo d in o ma ion o access da a base wi h
@ODBC unc ion.
License shows in o ma ion o so wa e license.
Exi (F10) o exi LINGO.
EDIT Menu:
Undo (C l+Z) undoes he las ac ion.
Redo (C l+Y) undoes he las command undo.
Cu (C l+X) cu s he selec ed ex and sends i o he clipboa d.
Copy (C l+C) copies he selec ed ex o he clipboa d.
Pas e (C l+V) inse s he selec ed ex a he place indica ed by he cu so .
Pas e Special opens a dialog o pas ing objec s.
Selec All (C l+A) selec s all he con en s o he edi ion window.
Find… (C l+F) sea ches o a s ing o ex in he ac i e window.
Annex 2. The modelling language and op imize : LINGO
321
Find Nex (C l+N) inds he nex ins ance o he ex mos ecen ly sea ched.
Replace (C l+H) pe mi s us o ind and eplace ex ; his op ion is use ul, o example, o change
he names o he a iables.
Go o line (C l+T) o in oduce he line numbe o he ac i e window in which we wan o place
he cu so .
Ma ch pa en hesis (C l+P) o ind he closing pa en hesis o ha selec ed. I is use ul in embedded
sen ences. I no pa en hesis has been selec ed, LINGO chooses he one closes o he posi ion o he
cu so .
Pas e unc ion o inse unc ions a he cu en cu so posi ion. Choose i s he ca ego y and hen
he unc ion om he menu.
Selec Fon ... (C l+J) o selec he le e on o he ac i e window o p in e . Some imes i is easie
o display he documen wi h cou ie on .
Inse New Objec Le s you inse OLE objec s in he ac i e window, such as ables, equa ions,
cha s…
Links This op ion allows modi ying he p ope ies o he links o he ex e nal objec s o a LINGO
documen .
Objec P ope ies (ALT+En e ) I we selec his op ion a e selec ing an ex e nal objec , LINGO
allows us o change he objec 's op ions.
LINGO Menu:
Sol e (C l+U) sol es he model s o ed in he memo y. I he e is mo e han one, LINGO sol es he
model o he ac i e window.
Solu ion (C l+W) gene a es a solu ion epo ( ex o g aphical o ma ) o he ac i e window. We
may wan o see only he a iables wi h nonze o alues and/o only he cons ain s ha a e binding.
Range (C l+R) gene a es he epo o sensi i i y analysis, gi ing he ange o alues in which i
can:
1. Change one coe icien o he objec i e unc ion wi hou modi ying he op imal alues o he
decision a iables.
2. Change one coe icien o he RHS wi hou modi ying he op imal alues o he oppo uni y
cos s and he educed cos s.
To enable ange compu a ions, selec he Gene al Sol e Tab unde LINGO/Op ions and in he
Dual Compu a ions lis box, choose he P ices & Ranges op ion.
Op ions (C l+I) allows us o change some pa ame e s o he LINGO in e ace, as well as LINGO
sol e he model.
In e ace shows a dialog box o con ol he appea ance o LINGO, he ou pu and he de aul
ile o ma .
Gene al Sol e allows us, among many o he possibili ies, o ckeck he box Va iables assumed
non-nega i es o place a lowe bound o ze o on all a iables. Dual compu a ions box pe mi s
us o selec P ices & Ranges o ob ain sensi i i y analysis epo . In Gene al Sol e ab we can
indica e ime and numbe o i e a ions used o sol e he model by Run ime Limi s.
Ope a ions esea ch in business adminis a ion and managemen
322
Linea Sol e p o ides op ions ha allow con igu ing he way LINGO sol es linea models.
Among o he possibili ies we can choose p imal simplex, dual simplex o in e io poin algo i hm
(Me hod/P imal simplex/Dual Simplex o Ba ie ). You can check a box o scale a model. The
box Ini ial Linea Feasibili y.Tol allows changing he ole ance alue o he ini ial linea
easibili y and by de aul i is 0.0000003. I is used a he ini ial s age o linea model sol ing in
o de o see whe he a cons ain is sa is ied. Viola ions smalle han ole ance a e igno ed.
The box Final Linea Feasibili y.Tol con ols he ole ance alue o he inal solu ion easibili y
and by de aul i is 0.00000001. I is used a he inal s ages o model sol ing o see i he
cons ain s a e sa is ied. Viola ions smalle han ole ance a e igno ed.
Nonlinea Sol e con ols op ions ha a ec he algo i hms o sol e nonlinea models. Inicial
Nonl Feasibili y Tol. box indica es he ole ance o he ini ial nonlinea easibili y. By de aul , i
is 0.001. Simila ly, he box Final Nonl Feasibili y.Tol p o ides he ole ance o he inal
nonlinea easibili y. By de aul , i is 0.000001. The wo p e ious ole ances a e used in a simila
way o hose used in linea models.
In ege P e-Sol e has op ions o e o mula e he model in o de o sol e i as as as possible
wi h b anch and bound algo i hm. The in ege p e-sol e ope a es only wi h linea in ege
models.
In ege Sol e ab p o ides op ions ha allow us o con igu e he way in which LINGO sol es
in ege p og amming models.
The B anching box has wo op ions o con olling he b anching s a egy used in b anch and
bound algo i hm. The Di ec ion ield con ols how LINGO makes b anching decisions (up, down
o bo h).
P io i y ield pe mi s us o decide i bina y a iables ha e p io i y in b anching p ocess.
Due o a ound-o e o on digi al compu e s, i is no always possible o ind in ege alues o
in ege a iables. We can manage se e al op ions in In eg ali y box, such as Absolu e In eg ali y
and Rela i e In eg ali y. The o me ole ance is used as a es o in eg ali y in in ege
p og amming models. This ole ance measu es he di e ence be ween he a iable alue and an
in ege alue. The la e ole ance is a simila concep measu ed in ela i e e ms.
LP Sol e box allows us o selec he algo i hm o use in b anch and bound p ocess (p imal
simplex, dual simplex and ba ie sol e ).
Op imali y box is used o con ol h ee ole ances. The Absolu e Op imali y ole ance is a
posi i e alue , indica ing o he b anch and bound sol e ha i should only sea ch o in ege
solu ions wi h objec i e alues a leas uni s be e han he bes in ege solu ions ound so a .
The Rela i e Op imali y ole ance is a simila concep o he p e ious ole ance. In his case is
anging om 0 o 1, indica ing ha b anch and bound should only sea ch o in ege solu ions
wi h he objec i es alues a leas 100* % be e han he bes in ege solu ion ound so a .
The Time o Rela i e ole ance is he numbe o seconds be o e he b anch and bound sol e
begins using he Rela i e Op imali y ole ance.
Finally he Tole ances box includes some ole ances o con olling he b anching s a egy:
Hu dle, node selec ion and s ong b anch. Hu dle allows en e ing a known alue o objec i e
unc ion. Then LINGO will only sea ch o in ege solu ion in which he objec i e is be e han
he hu dle alue. The Node Selec ion op ion pe mi s con olling he o de in which he algo i hm
selec s b anch nodes in he ee (Dep h Fi s , Wo s Bound and Bes Bound).
Global Sol e is an addi ional op ion o LINGO. I con e s non-con ex models in o smalle
con ex models. I uses echniques such as linea p og amming and cons ain p opaga ion wi hin
a b anch and bound amewo k o ind global solu ion o non-con ex models.
Annex 2. The modelling language and op imize : LINGO
323
Gene a e gene a es he cu en model epo , use ul o model e i ica ion.
Pic u e ep esen s he model in ma ix o m. This allows iden i ying epe i i e s uc u es in he
model, and inding possible mis akes.
Debug is a command use ul in he sea ch o p oblems in bo h in easible and unbounded linea
models.
Model S a is ics This op ion gene a es model s a is ics, such as numbe o a iables, numbe o
cons ain s, e c...
Look (C l+L) gene a es a epo con aining he model o mula ion. You can see all o selec ed
ows.
WINDOW Menu:
Command Window (C l+1) opens an access window o he command line. In gene al, Windows
use s do no equi e his window.
S a us Window (C l+2) p o ides in o ma ion abou :
To al numbe o a iables in he model, g ouped as linea and nonlinea .
S a us o he algo i hm wi h he cu en s a us o he solu ion, he numbe o i e a ions pe o med,
cu en sum o non- easibili ies, cu en alue o he objec i e unc ion, he bes in ege solu ion and
he bound o he in ege solu ion.
The numbe o cons ain s o he model, di ided in o linea and nonlinea .
The numbe o coe icien s di e en om ze o, di ided in o linea and nonlinea .
Cu en memo y used o s o e da a.
Time un o ob ain he solu ion.
Fu he mo e, his window has an op ion o s op he sol ing p ocess. In his case, i p o ides he bes
solu ion ound up o ha momen including he message ha i may no be op imal o easible. The e
is an op ion o close he window.
Finally, he e is an op ion o indica e how o en (in seconds) we wan he window o be upda ed
(upda e in e al). In in ege p og amming he window upda es whene e a be e in ege solu ion
is ound, ega dless o he alue in oduced. On he o he hand, upda ing oo o en may inc ease
solu ion imes.
Send o back (C l+B)
To send he ac i e window o he back. Fo example, o mo e om he model window o he solu ion
window.
Finally LINGO also has o he common op ions in Windows, applica ions, such as Close All, Tile,
Cascade and A ange Icons.
Help menu allows us o access LINGO help.
Ope a ions esea ch in business adminis a ion and managemen
324
A2.6. LINGO FUNCTIONS
LINGO has se e al ypes o unc ions as ollows:
S anda d ope a o s, which a e he a i hme ic ope a o s, he logical ope a o s and he
equali y and inequali y ela ionships.
A i hme ic ope a o s: Powe ^, mul iplica ion*, di ision /, addi ion+ and sub ac ion-.
Logical ope a o s: #NOT#, #EQ#, #NE#, #GT#, #GE#, #LT#, #LE#, #AND# and #OR#.
Equali y and inequali y ela ions: =,  and . I also accep s < and > o less o equal and
highe o equal, espec i ely. These ela ionships should no be con used wi h he logical
ope a o s #EQ#, #LE# and #GE#.
Va iable domain unc ions: @BIN, @BND, @FREE, @GIN, @SEMIC, @SOS1,
@SOS2, @SOS3, @CARD.
File Impo : @IMPORT and @FILE. The la e is used when he da a a e s o ed in a ile
di e en om he model.
Financial unc ions: @FPA (I, N). @FPL (I,N).
Ma hema ical unc ions: @ABS, @COS, @EXP…
Se -Looping unc ions: @FOR, @MAX, @MIN, @SUM.
P obabili y unc ions: @PBN, @PCX…

ANNEX 3
MULTIPLE
CRITERIA
SOFTWARE FOR
COLL
ABORATIVE DECISION
MAKING: EXPERT CHOICE
COMPARION SUITE
Annex 3. Mul iple c i e ia so wa e o collabo a i e decision making
327
A3.1. MODELLING: DESIGN OF DECISION HIERARCHY
Expe Choice Compa ion Sui e is a web applica ion designed o mul iple c i e ia
decision making bo h o a decision make and o a wo king g oup. I uses he Analy ic
Hie a chy P ocess (AHP) and o he me hods o e alua e al e na i es o a decision
p oblem om he conside ed objec i es (Ra ing Scale, U ili y Cu es o S ep Func ion).
Compa ion acili a es acking he p e e ences o all pa icipan s, hei da a and
commen s.
The pa icipan s o g oup membe s can be: P ojec owne , he only one ha can c ea e
a p ojec in he web applica ion (i is enough o indica e a name), P ojec manage , who
can c ea e and modi y he s uc u e and op ions o he p ojec o decision p oblem and
he P ojec e alua o ha may only issue he eques ed alue judgmen s. The p ojec
di ec o o he manage can collec quali a i e and quan i a i e in o ma ion om all
e alua o s.
C ea e a p ojec
Only he P ojec owne will be able o c ea e a p ojec . To log in in o Compa ion
Co eTM as p ojec owne o p ojec manage , use he e-mail add ess and he passwo d
and ins uc ions ecei ed om Expe Choice. To in oduce he da a o a new p oblem,
click on he New P ojec bu on on he main menu. En e he name and he desc ip ion o
he p ojec and click OK.
Decision hie a chy
S uc u ing he decision p oblem includes de ining c i e ia and objec i es,
iden i ying al e na i es, mapping al e na i es o objec i es and de ining measu emen
me hods.
Click on S uc u e in he main menu and Objec i es on he seconda y menu on he
le o he sc een. Selec he goal o he p ojec (decision p oblem). To en e he goal,
igh click on Goal and en e he goal desc ip ion. Al e na i ely, you can click he le
mouse bu on and en e he goal name. Addi ionally, you can in oduce in o ma ion abou
he p ojec in he igh -handwindow (Edi In o ma ion Documen ).
To add objec i es, igh click on goal and selec “Add (le el below)” in “Objec i es”
which is in he hand co ne o he window. A window will pop up. En e you objec i es
in he pop up window. Click OK o add he objec i es. Add he desc ip ion o o he
necesa y in o ma ion. You can also c ea e sub-objec i es by selec ing he desi ed
objec i e and clicking on Add (le el below).
Ope a ions esea ch in business adminis a ion and managemen
328
Figu e A.3.1 S uc u e o he mul iple c i e ia decision making p oblem
To add al e na i es, igh click on he wo d Al e na i es on he main menu S uc u e
and selec Add o en e he al e na i es one by one o selec Pas e om clipboa d. Use
his command o copy al e na i es om ano he sou ce (Figu e A.3.1).
Al e na i e o objec i e mapping is use ul i you ha e a s uc u e whe e ce ain
al e na i es canno be measu ed agains some objec i es. Full mapping is he de aul
mapping, ha is, all objec i es a e ela ed o all al e na i es. In o he wo ds, all o he
al e na i es con ibu e o eaching all o he objec i es. To de ine he ela ion, click on
Con ibu ions on he le side o he window and uncheck (click he check ma k) he box
nex o he al e na i es ha you do no wan o e alua e agains he highligh ed objec i e.
A3.2. MULTIPLE CRITERIA METHODS
A e in oducing he objec i es and he al e na i es we ha e o de ine he e alua ion
mul iple c i e ia me hods. This can be done om he main menu, unde Measu e. The
measu emen me hod de e mines how each o he e alua ion s eps a e p esen ed o he
e alua o o e alua o s in he case o collabo a i e decision making.
The weigh o he objec i es can be ob ained by pai wise compa ison o di ec
assignmen . Me hods o e alua ing he al e na i es agains he objec i es o he lowes
le el o he hie a chy a e as ollows:
1. Ra ing Scale
2. Pai wise Compa ison
3. U ili y Cu es (Simple o Ad anced)
4. S ep Func ion
5. Di ec Inpu