EST
10D
DIPLOMATURA D'ESTADÍSTICA
INVESTIGA CIÓ
OPERATIVA
DETERMINISTA
P ac iques de p og amació
no lineal
amb el paque GINO
Es e e Codina Sancho
,- - . ·-- . --
' UNIVERSITAT POLIT�CN/CA DE CATALUNYA .
1111111111111
1400295316
FACULTAT DE MATEMÁTIQUES I ESTADÍSTICA
INVESTIGA CIÓ
OPERATIVA
DETERMINISTA
P ac iques de p og amació
no lineal
amb el paque GINO
Es e e Codina Sancho
Tí ol: In es igació ope a i a de e minis a.
P ac iques de p og amació no lineal amb
el paque GINO
Au o : Es e e Codina Sancho
Legal: B-37.593-1997
, es pe : ÁHLENS
So Eulalia d' Anzizu, s/n
08034 Ba celona
In es igació Ope a i a De e minis a
(Diploma u a d'Es adís ica)
P ac iques de p og amació no lineal
amb el paque G INO
Es e e Codina Sancho
Depa amen d' Es adís ica i ln es igació Ope a i a
Facul a de Ma e na. iques i Es adís ica
Uni e si a Poli ecnica de Ca alunya
Cu s 97-98

O In oducció.
Els exc cicis de laho aLo i consisLeixen en un conjunL de p ac iques a ealiLza sob e models assignaLs
a cada ¡¡ up ,le p acdques o be desc j s en aquesL ¡¡uió. Cada exe c.ici consLa el 'un A b eu desc ipc.ió i
d'un apa lal d'excmples que l'alumnc han a de essc¡¡ui amb alenció i ep odu'i amb el paquel GINO
p e iamc11L ,1 l'elabo nció d'nn in o me on es conLesla n a un conjuhl de qües ions o muladcs al inal de
la clesc ipció de l'cxe cici. Es sob e aquesL in o me sob e el que s'eíec ua a la alo ació de IB p ac ica.
Aques s exe cicis són:
Exe cici l. Resolució, magal.zemamen i can is de o mulació.
2. Exc cici 2 línim local d'1111a unció eal scnse es . iccions.
3 Exe cici 3 , jusi pe mí11ims quad al s,
4 Exc cici 4 línim lo nl d'una unció eal amh esL iccions.
5 Exe cici 5 MoJcls simples de luxes en xa xes.
6. Exe cicis addicionals. P oblemes d'op imi zació amb esL iccions op a ius.
El p og ama Gl. 'O es L oba insLal.la a la xa xa de PC's de la Facul a de Ma e na. iques i Es adís ica
i de la Fa nlLa d'lnío ma ica de la UPC. Pe in oca -loés su icien si ua -se al di ec o i de eball i dona
la coma ia GINO / q11<:SL guió de p �c i,p1<'s p cLen se 11111.osu icienL i con é unn desc ipció del paq11e que
¡ie mcl, c ecl un les I nsques �sscuci1lls ele inl o lucdó, mílg;,.Lzc namen , modi iCll ió i csolució d 'un model
,le la ío1h1n més scnzílla possihlc. El pa<111el GINO chsposa ele L es comanes d'a_iu inle a Li es: HELP,
COM)! ¡ CAT le,: ,¡,inls ¡,odcu c,;11l1;i 'al11oses 1l11 anL In 1calil.zació deis cxe cicis. Pels es .11d.ian1.s habiLuals
en el 1is del l""I"º' 1,11'' DO la n nnip11lació clel pac¡uel GJ NO p esen .a a 11n esío � c¡unsi 11111 jaque ambdos
pa ¡11el.s compa eixcn molles comanes i una iloso ia ele L eball iden ica.
A cliíe enc.ia iel aque.L LINDO, GJNO no disposa d'un edilo p op! amh el c¡ue mani nla l!D model i,
Lal i com passa amb el paque LINDO la o ma més p ác ica de L eball consisleix en e ús d'un edi o , an
pe c ea pe p ime cop el model com pe e can is i manipulacions d'un model ja c eal. Des-de GINO
pod eu Leni acilmenL accés a qualse,·ol edi o que es igui lns al.la en el PC amb el que es eu L eballan .
Pe an , es11lln molL con enien , sino imp escindible, que coneixeu algún e< üo deis anomenaLs "de
p opi>sil gene nl'' i1cs. .al ln en l'cn o -n en el qne ns mo cu (pc excmple, el No on edi o ).
2
1 Exe cici l. Resolució, maga zemamen i can is de o mu•
lació.
J':11 11111cs p inlc cxe cic, c11s linllln on, n u iliLzn 1111 conjun d coma11c" bi .�11¡ues nmb les que
pode cl,nlln cíldc11Ln1en amh el GJNO l'ol-sc p é iamcn a q11alse ol desc ipcoó cal que s'in o,¡11i al
pn1p1c G I NO De�p cs cl'in o a -lo apa eixc a u 1n ca a ula anuncian! el pac¡11el i innlmeu , el p omp
': ', demn11n111-nos que in od11im unn comn11n i inicianl aixi una sessió. En aques es con licions podcm
cxecuLn la comano COMIIANDS. Apa elxc a en la panlalla el conjunl de comanes de GINO a¡¡ upacles
pe uncionnli als comunes, Podem demana in o mació sob e una omana de e minada miLjan�an la
comnna HELP 'cnmana', la qnal ens dona unn í nse explica i a de la inali al de la comana en qiieslíó:
: HELP GO
GO COHHAND
SOLVES THE CURRENT IIODEL. THE HODEL REMAINS INTACT THROUGH THE SOLUTION
PROCESS.
Ahans ele conlinna cal di que pe so li ele GJNO ulilil.za em comunmenl la coma na QUIT.
Dona cm a a una desc ipció de les se¡¡üen .s comanes: SAVE, RETRIEVE, TAKE, LOOK, DIVERT, RVRT,
SOLU, GO, OS, ALTER, EXT, KOOEL.
1.1 Ca ega i comp o ació d'un modeL
S11poscm el se¡¡iie.11L p oblema cl'opl.imilzació:
S.íl
: :� -: :¡ 2'. (1
(OP) : :1 + 2:1:2 - 2 � O
(l)
La o ma en c¡ue es poL magalzema en el clise du del osL e PC un model GINO consisL .ix en ilxe s
c¡11e .0111.cncn una cle�c ipció del modcl mi ja.n�anl com11nes p oples del GlNO, Aq11e.sLS iLx.e s poden
es.se ccli als íln b ecll o s de p oposil gene al del DOS. Suposem que disposcm en el clise du d '1111 iLxe
HODEL.DAT q11c ,li:,�c i1, el p oblema (OP) mi jan�.an comnnes del GJNO, Si des-de el DOS " eu un ype
KODEL. DAT" , ques apa eix . ia com:
KODEL
KIN = 3 •(x-2)·2 + 4•(y-1)·2
x·2 -y< O;
X+ 2• y -2 < 0 ;
END
l,n sinl axl ¡11e ha eu ele segui pe de ini un modcl és mol!, simple: la pa auln cla11 KODEL indica inici
le clccla a ió d� moclcl i In pa- aulo END linnl ele decln ació En e les ducs pa aulcs hi igme.n 11n conjunL
de il s cl'cxp1csíons mnlc1ni1Li<¡11cs. Ln scpa nció en e ila i ila s'indica pe '; ', En e les diíe enles iles
pol e.�PH la co csponcu a la <lc inició de In 1111ció objccLiu, Aques a e indicada pe IIIN = (p oblema
de 1111 11111i1zac1ó) o pc KAX = (p oblcm;i de mnximiLzació). Els ope ndo s a il.mc ics elemenLals són: +,
-, •, / i l'expo11e.ncia .ió / . SIN(), COSO , EXP(), LOG() cles.•i¡¡ncn ni sinus, cosin11s, 11nció exponencial
i lo¡¡mi me nnlu al espccli c enl,, (> , < Le11c11 iile111ic sii,:ni icaL i u11cions que nl LINDO), En cas de
q11e cspoui,:ueu IIODEL com esposl.a al':• in .c ncli cmc11L, GI 10 cspo111l a nonl,, i c�p� n i1 l'cn ad11
d'11nn elep essió maLemñlica inaliLzncla amh '; ', Pe inalil.z� l'en . nd,� d'un modd .al onlel=l,a END al
p omp ?
3
La comana RETRIEVE HOOEL.DAT ca ega el model des-de el i xe MODEL.DAT, men e que la 
mana TAKE HODEL.OAT execu a les comanes GINO que con ingui el i xe MODEL.DAT (en e elles les
que de ineixcu el model).
Pe comp o a que el model s'ha ca ega co ec amen u ili .za em la comana LOOK_ La comana LOOK
pe mc eu e o el model o an sois una pa d 'ell:
LOOK ALL mos a pe pan alla o el model.
:LOOK ALL
HODEL:
1) HIN= 3 + ( X - 2) - 2 + 4 • ( Y - 1 ) - 2
2) X - 2 Y< o
3) X+ 2 + Y - 2 <O;
END
LOOK ' ila), ila2' Mos a només les iles especi icades dins del ang ' ila], ila2'. Pe exemple:
:LOOK 1,2
1) HIN= 3 • ( X - 2) - 2 + 4 • ( Y - 1) - 2
2) X - 2 - Y< O;
1.2 Modi icacions d'un model.
En cas de que o a nccessa i e ec ua modi/kadons cl'un model pocl iem u .ili za les e.amanes ALTER,
DEL i EXT o bé modi ica la de inició del model mi jan�an . un ecli .o del DOS. En cas de que . ehallem
amb models de pe .i amany és ecomanablc aques a 1íl ima opció
Pe accecli a un i xe en el disc du c¡uan es .cm l. ehallanl. amh el GINO no és necessa i abandona la
sessió ("so i " ,lel paquel). La comana OS ens pe mel d'execula qualse ol comana del sis ema ope a iu
en el que ens l obem (el DOS). Si pe exemple olem consul a quins i .xe s amb l'ex .ensio .DAT enim al
di eclo i en el que es em, senzillamen a iem OS OIR • .DAT i apa eixe ia pe pan alla el llis a de i xe s
p opo cional pel DOS. Analogamenl pod iem in oca un edi o pe modi ica el i xe l 1ODEL.DAT.
Suposanl que inguessim el No on edi o al nos e PC i que aques s'in oques mí ji n an la comana
'NE' pod iem c ida -lo des-de el G!NO pc mo li ic.a el i xe MODEL.DAT:
OS NE HODEL.DAT
Al so .i ne l'eclíLo l,o nMicm a es a eu cliilleg nmh el GINO {,,pn cixc il : ). TomR iem a c..-i e¡;a
miLjan nn In co111a11n TAKE o RETRIEVE el 11011 model c.011I lngu a MODEL.DAT. En cas lc ,¡11n ol¡;uessim
c ea un i .xe en el ,! sc du ;imb la dcsc- ipc1ó del nosl e moclel 11Lili za iem la .onia11n SAVE 'nom de
il.xe '.
Pe modi ica di eclamenl des-de el GJNO un model, és a dl sense edi a un i xe c¡11e con ingui la
se a de inició, uLiliLza em les comancs ALTER, EXT, DEL. La comana DEL se eix pe elimina unn l 1;1 de
la cle inció del modcl. Pe exemplc, DEL 2, esbo a ía la p ime a cs icció del model (OP). La co nl na
EXT se cix pe e egi una ila al nos e moclcl. Desp és de clona la coma.na EXT GJNO ens demana la
de lnció de l: no a ila (110 ? apa eix en pan alla). Pe exemplc, si en el mocleJ ¡,el p ohlem11 (OP) olem
a cgi la es . icció x + y 2:: 1/2 clona iem la comann EXT
:EXT
? X+ Y> .S;
4
la qua! se ia a egida com ila núme o 4 al model. (Reco deu- os d'acaba la línia amb '; ' pe indica
inaliLzació de l'exp essió).
:LOOK ALL
HODEL:
1) HIN= 3 • ( X - 2). 2 + 4 • ( Y - 1 ) . 2
2) X· 2 Y> O
3) X+ 2 • Y - 2 <O;
4) X+ Y> .5 ;
END
La comann ALTER ' ang de iles' 'sl ingl 'sl ing2' snsl.ilueix a les iles dins del nng de iles especi ical
el co ijnnl. ele cn ilc .e s 'sL ingl' pe] conjnnl del ca acLe s 'sL ing2'. Pe exemple, si olem can ia el e me
de la d cl.11 de la esl ic .ió <¡lle exp esa la ila 4), 0.5, pe 1.1 dona iem la comnna: ALTER 4 '.5'1.1'
:ALTER 4 '.5'1.1'
:LOOK ALL
HODEL:
1) HIN= 3 • ( X - 2) - 2 + 4 • ( Y - 1) • 2
2) X· 2 Y> o
3) X+ 2 • Y - 2 <O;
4) X+ Y> 1.1 ;
END
1.3 Resolució d'un model.
Quan n 'esLem segn s de que el model s'ha ca eb'ñl co ccLamenL podem inleuLa esold e'l. lnde
pendcnLmenL del Lipu� de modcl, GINO inida la esol11ció del model amb la comana GO. Al inaliLza
l'execució GlNO p opo ciona la solució q11e ha L obal l dona un missa ge in o ma iu ele les condic.ions
pc les que s'ha p ochií !'a u ada. Una egacla hem esolL un modcl semp e podcm e ¡ue ens o ni a
clona pe pnnl,nlln la solucíó uLiliLzanL la comana SOLU sense in oca el p oceclimenl, al¡;o ismie q11e l'ha
obl ing111 .. Pc csol,l c el moclel (OP):
:LOOK ALL
KODEL:
1) HIN= 3 • ( X - 2). 2 + 4 • ( Y - 1) . 2
:GO
2) X - 2 Y< O
3) X+ 2 • Y - 2 <O;
END
(con!. pág. segiicnl,)
5
2.2 Con ingu de la P ac ica
Pe complimenla la p ac ica cald a que espongueu a les segiienls qiieslions adjunlanl els llislals de
so lida p opo cionals pe GINO i les de inicions deis models emp als. Conside eu les uncions:
(8)
1. Dele mineu miljan�anl l'aju del GINO dos mínims locals de la unció Ji.
2. Comp o eu que els dos punls p opo cioun .s pe GINO e i iquen les c.o11dicio11s necessil iP.s de p ime
i segón o d e.
3. lnlenleu dele mina mi jan�anl el GINO un mínim local de la unció h- Quina solució ob .eniu ?
4. Esc iu les condicions de p ime i segón o d e co esponenls al p oblema de la minimil.zació de la
unció h- Poden l oba alg in punl que les e i ü111i ?. Jus i iqueu la esposli.
12

3 Exe cici 3. Ajus pe mínims quad a s.
En mol cs ocasions se sap q11e un modcl malema ic cspon a una exp cssió del Lip11s
y = J(: :,, ... , : :m, 01, •• , u¡), on : :,, ... , :Z:m són a iables que deLe minen el alo de la magniLucl y i
a,, ... , a són pa amN es <¡lle cal de e mina . Si es cone1x un conjunl d'obse acions :z:U = (:z: ;, ... , !!:),
i de 'alo s de la magniL11cl yU, j = l, ... 1:., co esponenls a 11q11es es obse acions, lla o s poL in -en a -se
de e mina el alo deis pa ameL es a,, ... , a, de o ma que es e i iquln les k igualLals:
En gene al, deguL a que les k obse acions y(j de la magni ud y enen a eclades d'e o s de mesu a
les an e io s equacions no es compli an sino de o ma ap oximada pe un alo de les " , ... , a,.
Pc de e mina un alo ele les a1, .. , 01 podem p ocedi pe ajus . mínim qua l ii ic, és adi , in en a
clele mi11a uns alo s pe a1, .•. , "' de o ma que la suma deis (Jlli !l al.s deis k e o s:
p esenli el mínim alo possible. Es a di , in en a iem oba el mínim de la unció:
3.1 Exemple
El l.emps de CPU que dedica un compulado en l'exe .ució d'un dele mi11al p og ama depen del
olum n de clades d'cn ada al p og ama i se sap que el Lemps cl'execució ha le VP.ni donaL pe una
exp essió del ipus:
(n) = a+ b- n (9)
essen a,b cons an s que es ol ajus a mi jan�an el c i e i de mínims quad a s al disposa -se de les
següen s obse acions:
n; 10 20 35 50 60 75
; 134.12 135.23 137.96 140.10 141.67 143.56
PlanLeja iem el segiienL p oblema d'op imil.zació:
Mín.,1 ,,.,(a,b) = ¿�=1(a+b•n;- ;)2
que desc iu iem al GINO de la següen o ma:
13
!)5 l 10
146.50 149 00 (10)
(11)
KODEL:
1) HIN= Yl . 2 + Y2 . 2 + Y3 . 2 + Y4 . 2 + YS . 2 + Y6 . 2 + Y7 . 2 +
YB . 2
2) Y! A + B • 10 -134. 12
3) Y2 A + B • 20 -136,23
4) Y3 A + B • 36 -137.96
5)
Y4 A + B • so - 140.10
6)
YS = A + B • 60 -141. 67
7)
Y6 = A + B • 76 -143.66
8) Y7 A + B • 96 -146.50
9) YB = A + B • 110 -149.00;
END
Al esol el e'] ob .ind iem el alo de les a iables Yl, ... YB que 1'micamenl p opo cionen la diíe encia
en e el alo obse a i ]'ajus a i els alo s esli nals pe les cons .anls a, b qnc e11e11 clonals pe les
a iables A, B.
: GO
SOLUTION STATUS: DPTIHAL TO TOLERANCES. DUAL CONOITIONS: SATISFIED.
OBJECTIVE FUNCTIOR VALUE
1) .246766
VARIABLE VALUE REDUCE□ COST
Y1 -.061568 .000000
Y2 .313019 .000000
Y3 -.190112 .000000
Y4 -. 103231 .000000
Y5 -.188636 .000000
Y6 .148245 .000000
Y7 .177417 .000000
YB -.096702 .000000
A 132.573840 -.000074
B . 148459 .000005
ROW SLACK OR SURPLUS PRICE
2) .000000 .123136
3) ·ºººººº -.626037
4) .000000 .380224
S) .000000 .206461
6) .000000 .377271
7)
.000000 -.296491
8) .000000 -.354834
9) .000000 ,191405
14
Fixem-nos en que una o ma al e na i a de desc iu e el model se ia:
HODEL:
HIN= ( A + B • 10 -134 .12 2 + A + B • 20 -13S.23 - 2
+ ( A + B • 3S -137.96 -2 + A + B • so - 140 .10 - 2
+ ( A + B • 60 -141.67 -2 + A + B • 7S -143.S6 - 2
+ ( A + B • 9S -146.SO -2 + A + B • 110 -149.00) - 2
END
Així dones el model ajusla ind a dona pe (n) = 132.5738 + 0.148459 · n.
15
3.2 Con ingu de la P ac ica
Pe complimen a la p ac ica cald a que esolgueu els segiienls p oblemes mi jan�an l'aju del GINO,
aclj1111 anL un llis .a amb els esul .a s p opo cionals pe! paq11e .
l. Un .ecnic ol oh eni una exp essió pe la dis ancia <le enada cl'un el1icle en unció de la eloci a
a la que s'inicia el enal .. Se sap que la dis ancia de enada en unció de la elocila ha de eni donada
pe una exp essió del ipus: d( ) = o0 · + a1 • !, i es disposa de les següenls obse acions:
¡ 20 30 35 40 50 60 65 75 85 100 11 O
d, 2.7 5.3 7.1 8.9 13.3 18.2 20.8 26.4 33.4 44.7 52.!J (12)
• Planlejeu una unció objec iu ,p(o0, o1, /31) que exp esi la suma deis quad a s de les di e encies en e
els alo s obse als d; i d( ;) = o0 • + o1 · ( ;)11'.
• Del.c mine11 amb l'ajn ele! GINO nn alo pels coe icienls o0, o1, /31 de mane a que es minimi zi
l'anl.e io nnció p(u·o,01,/31)
2. La quanLi a de camions ele anspo que en en i su l.en del po d'11na ciu .n . clepe.n di ec amen
del olum de me cade ies que a iba o su emba ca del po . Les me cacle ies esl an composades pe :
a) con enido s, b) me cade ía pesada i e) me cade ia a clojo lleuge a. Els ecnics del po es imen c¡ue la
elació en e el olum de camions de anspo i els di e en s ipus de me cade ies espón a una exp essió
del ipus:
on (c,¡,, d) es la q11an i a de camions ele anspo , e és la quan i a de con .aine s, p és la quan i a
de mc cacle ia pesada en ones i ,/ és la q11an i a de me cacle ia a dojo lleuge a ambé en ones i ª" ª •
lld són pa ilmel es a de e mina .
Es disposa del següenl conjun cl'obse acions:
e, 210 810 205 300 350 160 704
45
45 170
p, 500 305 300 1080 300 105 58'5 81 75 340
d, 220 110 40 50 280 10 1080 30
35
365 (13)
, 15320 21307 10945 27810 13620 6510 25517 3735 3913 11502
Mi .jan�anL aj11s mínim q11ad a .ic dele mine11, a pa li de les ohse acions. el alo deis pa ame es
11,, "¡;, Cid del mouel.
16
4 Exe cici 4. Mínim local d 'una undó eal amb es iccions.
Ac¡u,:sL exe cici e com objecLiu l'analisi de les condiciona de p ime o d e d'un p oblema de p og a
mació no lineal (PNL) amb esL iccions i la idenLi icació deis mulLiplicado s de Lag ange de les esL iccions
del p oblem;i Lal i com els p opo ciona GINO al p esen a una saludó d'aquesL.
Es ecomana Leni p esenLs cls conccp es ex)'>osaLs a classe de Leo ia. Pe La! de aciliLa -ho p esenlem
al inal de la p ac ica un b eu esum de Leo ia pc les condicions de 1" o d e d'un p oblema amb
esL iccions i desp es p esenLcm un exemple nume ic pc il.lusL a la o ma en que GJNO p esenLa una
solució i com in e p e a aques a.
4.1 Un exemple. Signi ica de les columnes PRICE i REDUCED COST
Mi jan�anl aques exemplc es mos a a com GINO p esen a els mul iplicado s de les es iccions de
desigualLaL d'un p oblema de p og ama.ció no lineal. Les condicions de Kuhn-Tucke esLablc.ixen que els
mu!Liplicodo s de les esL iccions de dcsignalLaL han de se no nega ius menl e que, pels mul iplicado s
de les es iccions d'lgualLaL no hi ha es di . No obs anL po sembla que GJNO no espec a aquesLes
condicions. Amb el següenL exemple acla i em aques aspecLe:
S.a Z2 -Z � 0
Z¡ + 2:i:2 - 2 $ 0
(µ1, µ2 mulLiplicado s de Lag ange)
(14)
Obsé. eu que no hi ha-n esL iccions d'igua!LaL p esenLs. P e iamenLa aplica de o ma sisLema ica les
condicions de Kuhn-Tucke cald á exp esa Loles les es iccions de d.esigual aL del p oblema en la o ma
g(: ) � O. Fixem-nos que la p ime a esl icció esla e.xp esada de la o ma: z2- :i:1 � O. Si mullipliquem
pe -1 ambdos cosLa.Ls de la desiguallaL calcl a can ia ? pe $ i la esL icció s'exp esa a ll11 o s segons
:i:? - :i:2 � O, amb lo c¡ual lo es les csL iccions del nos . e p oblema son del Lipus 9(:z:) � O. El lag angia
d'a ¡uesL p oblema se ia dones:
Les condicions de Kuhn-1 1cke pel p oblema són:
6(:i:1 -2) + 2:i:¡µ¡ + µ2
8(:i:2 -1) -µ¡ + 2µ2
µ¡ ? o, µ2 ? 0
z2 -z
:i:¡ + 2:i:2 -2
µ¡(:i:2 -z?) + µ2(z1 + 2z2 - 2)
= o
= o
(signes deis mul ipl.)
� O (/ ac ibili a )
$ o ( " )
= O (com¡,lcmcn n ie n )
(16)
Pe La] de esold e el model amb el paqneL GINO p epa a iem un ilxe (pe exemple, el HODEL. DAT)
amb la de inicio del p oblema PNL:
HODEL
HIN= 3 •(x-2)"2 + 4•(y-1)"2
:i:·2 - y< O;
: + 2• y -2 <O;
END
Cal di que no es necessa i .on e Li Loles les esL icdons de desig11all.a.L a la o ma � O pe c ea
el iLxe de de inició del model ( ilxe HODEL. DAT). No obsLanL es molL con cnienL e -he ¡>e p oce li
17

de o ma o denada, si cal plan eja les condiciona de Kuhn-Tucke i calcula ama els mul iplicado s de
Lag ange. Ca ega iem el i xe MOOEL.DAT al paque GINO miLjan�an la comana TAKE MODEL.DAT.
Desp és de comp o a que s'ha ca ega co ec amen mi jan�an la comana LOOK ALL el esold iem
(comana GO):
:LODK ALL
HDDEL:
1) KIN= 3 • ( X - 2). 2 + 4 • ( Y - 1) - 2
:GD
2) X - 2 Y< O
3) X+ 2 • Y - 2 <O;
END
SOLUTIDN STATUS: OPTIKAL TO TDLERANCES. DUAL CONOITIDNS: SATISFIED.
OBJECTIVE FUNCTION VALUE
1) 5.069133
VARIABLE VALUE REDUCED COST
X .780776 ·ºººººº
y .609612 .000000
ROi/ SLACK DR SURPLUS PRICE
2) .000001 2.790982
3) .000000 2.957023
Sa en que la solució p opo cionada pe GINO és la (xj, 1:;) ::::: (0.760776, 0.600612) calculeu a mil
els alo s deis mul iplicado s (µj, µ2) i comp o eu que són ap oximadamenL (2.7!)0982, 2.957023)
Ca egueu a a el maLeix model pe o exp esan la p ime a es icció en la o ma: 1:2 - : .¡ 2'. O i
esoleu-lo. Oblind eu la següen espos a de GINO:
:LODK ALL
KDDEL:
1) KIN= 3 • ( X - 2) - 2 + 4 • ( Y - 1 ) - 2
:GD
2) Y X - 2 > O
3) X+ 2 • Y - 2 <O;
END
SOLUTIOR STATUS: OPTIMAL TO TOLERARCES. DUAL CORDITIORS: SATISFIED.
OBJECTIVE FUICTIOI VALUE
1) 5.069133
(con . pag. segiienl)
18
VARIABLE VALUE REDUCED COST
X .780776 ·ºººººº
y .609612 .000000
ROII SLACK OR SURPLUS PRICE
2) .000001 -2.790982
3) .000000 2.957023
Obse 11 11 n a com la en ada de la columna PRICE co sponenl a la es icció p ime a apa ei can
iadn de signe. GINO o ma en aqnes cas el ll g angia de la següen . o ma.:
mosl anl-nos a la columna PRICE els 111, 112 que gua den la. segiien ela.ció a.mb els µ1, µ2:
(18)
Pe an podem eu e que GINO p esen a a la columna PRICE:
•Sí la es íccíó s'exp esa de la o ma g¡(x) :S O lla o s a la columna
PRICE apa eíx el mul iplicado de Lag ange: µ¡.
•Sí la es iccíó s'exp esa de la o ma g¡(
x) � O lla o s a la columna
PRICE apa eix el mul iplicado de Lag ange can ia de signe: -µ;.
Columna REDUCED COST. Al cos al de la columna VALUE , on es dona el alo de cada a iable a
la solució del p oblema, apa eix la columna REDUCED COST. Cada elemen d'aquesla columna es co espon
amb un deis elemenls de 'il .C(: 1, 2,µ1,µ2). Pe) nosl e p oblema d'exemple apa eixen:
a.e a¡ a(xi -:i:¡) a(: 1 + 2: 2 -2)
ax1 = ax1 +111• éJ: 1 + 112' ax1
a.e a¡ a(z1 -:i:?) éJ(: 1 + 2:i:2 -2) (19)
axi = ax2 +111 • 8:i:, + 112• ax,
Eslan a. aluades les de i a.des pa. cials * , ... e c. de o ma ap oximada. O sigui que la columna
REDUCED COST ens p opo ciona una ap oxima.ció al g adien del lag angia espec e de : del p oblema (el
qua) és eo icamenL ze o en un punL que e i iqui les condicions de Knhn-Tucke ). Pe aques a causa
si a la columna REDUCED COST no apa eixen elemen s nnls o quasi n11ls ("" 10-6) s'acos uma a dona el
missalge DUAL CONDITIONS UNSATISFIED. (Veu e p ac ica 1)
19
.2 Resum de eo ia.
Donem a con inuació un b eu esum de les condicions de p ime o d e d'un p oblema PNL. Suposem-
10s en on a s a oba un pun : " E I ' pel que una unción /(: ) : R" ...... R p esen í un alo mínim
Jins d'un conjun de pun s de R" que enen exp esa s pe un conjun de igualLa s en núme o ini del
;ipus h;(: ) = O, i = 1, ... mi/o un conjun de desigual a s, ambé en núme o ini , del ipus 9i(x) S O,
i = 1, ... L:
Mín /(: )
S.11 /,(x) = 0
g(x) S O
De inim el Lag angia del p oblema (PNL) com:
(PNL)
Lla o s o óp im local del p oblema PNL e i ica a les condicions de Kuhn-Tucke :
(20)
(21)
Condicions de Kuhn-Tucke (Kuhn i Tucke (l!l51)) Di ·em que x·, >.•, ¡1" e i iq11en les condicions
de lí lin-T ck< si es compl<ixcn les es cnndicions seg,icnls:
l. g(: ") S O, /1(: ") = O. ( ac ibililal}
2. µ· T g(x") = O,µ· ,:: O. (complemen a ie .a )
3. ' l(x",>.",µ") = O
( ' l(x" ,>.", µ") = ' (x") + ' /1(: ") T )." + 'g(x") T¡,• ) (22)
Cal ema ca que o el que s'ha di an e io men és alid en els casos en que no hi es iguin p esen s
es iccions d'ignal a .
20
Za
z
g
- - - - ------ ------ -
Mín,;
s.a
Es demana:
� ( ,2 + �Zi�I •� z.)1 ) ½
i=D
... a *1
Z¡ � O - /J • Z¡,
(zo = Za, ZN = ZT, 6 = ( TÑ ,))
X
i=l, ... ,N-1
l. Resold e el p oblema pe "'ª = O, Za = 7, "'T = 1, ZT = 4.8, o = 61 /3 = 5.04, N = 15.
(31)
2. De e mina una ap oximació deis ex ems de l'in e al de pun s de con ac e de z(z) ambla ec a
z = 6 - 5.04 · "'·
3. Compa a la solució ob inguda amb la del p oblema sense es iccions (30)
27