64Kb - DComp

Capítulo V:
O MÉTODO SIMPLEX REVISADO
1
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
0e72'26,03/(;5(9,6$'2
F1RUPDOPHQWHQ!!PLVWRpQ~PHURGHYDULiYHLVPXLWRPDLRUTXHRQ~PHURGH
UHVWULo}HV
$
F$SUiWLFDUHYHODTXHR6,03/(;UHVROYHXP3/FRPPDPSLYRWHDPHQWRV
F&RQFOXHVHTXHKiFROXQDVTXHQXQFDVmRXVDGDVQmRGLVWDQWHDFDGD
LQWHUDomRHIHWXDPVHFiOFXORVVREUHVHXVHOHPHQWRV
F2FRUUHDVVLPGHVSHUGtFLRGHWHPSRHPHPyULD
F$LGpLDHQWmRpQmRJXDUGDUQDPHPyULDUiSLGD³FRUH´GRFRPSXWDGRUR
TXDGURFRPSOHWRSLYRWHDGR
∧
F
∧
$
∧
E
F'LVSRQGRVHGH$+SRGHVHHIHWXDUXPDSURJUDPDomR6,03/(;GDtQDVFHR
0e72'26,03/(;5(9,6$'2
321726
%È6,&26
6(FRQRPLDGHPHPyULDUiSLGD
6*XDUGDVH$EFQDPHPyULDOHQWDGLVFRILWD
6$WXDOL]DomRGH$+
2
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
$78$/,=$d­2'$,19(56$'$0$75,='(%$6(
0DWUL]GHSLYRWHDPHQWR3UV
([HPSOR
∧
0DWUL]$ QD
LWHUDomRN
∧
0DWUL]$ QD
LWHUDomRN
∧
$ ∧
$ ∧
$ ∧ ∧
$ $ ∧
$ ∧ ∧
$ $ ∧
eIiFLOYHUTXHDRSHUDomRGHDWXDOL]DomRGH$FRQVLVWHQDPXOWLSOLFDomR
SHODPDWUL]3
∧ ∧
$ $ ∧
∧
∧
$ $N $N
∧ ∧
$ $ 30$75,='(3,927($0(172
3
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
6,03/(;5(9,6$'2
',$*5$0$'(%/2&26
1$0(0Ï5,$5È3,'$',63®(66(
+ tQGLFHGDVYDULiYHLVEiVLFDV
∧
E YDORUGDVROXomREiVLFD
F+ FXVWRGDVYDULiYHLVEiVLFDV
$+ PDWUL]LQYHUVDGDEDVH
&$/&8/$9(725
08/7,3/,&$'25
π F+$+
&$/&8/$
FM F+π$,
∧
∧
(VFROKDXPFV!
FROXQDYDULiYHOV
DHQWUDUQDEDVH
∧
$V
7RGRVRV
∧
F,
62/8d­2Ï7,0$
),1,7$
&DOFXOD
$+$V
&DOFXODOLQKDUGHEORTXHLR
YDULiYHODVDLUGDEDVH
'HWHUPLQD3UVHID]DWXDOL]Do}HV
+ +UV→+¶
∧
∧
3UVE→E¶
F+→F+
3UV$+→$+
62/8d­2,1),1,7$
QmRKiEORTXHLR
3('('$'26$0(0Ï5,$/(17$
4
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
(;(03/26,03/(;5(9,6$'2
[[[[
[[[[
[[[[
[[[
[L!L 0D[] VD
3
[[[[
[[[[[ [[[[[ [[[[ [L!L 0D[] )250$
3$'5­2
VD
,1,&,$/,=$d­2
+ ^`
∧
E
F+ $+
5
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
,7(5$d­2
π
●
∧
F ●
F+$+
Fπ$
!
&ROXQDDHQWUDUQDEDVHV ●
∧
$ ●
$+$
/LQKDGHEORTXHLR
●
[
[
[
;⇒U Ι 6
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
3UV 3 ●
$78$/,=$d®(6
●
++ ^`→+¶ ^`
3UVE ∧
→ E ∧
F+ 3UVE ∧
7
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
,7(5$d­2
π
●
∧
F ●
F+$+
Fπ$
!
&ROXQDDHQWUDUQDEDVHV ●
∧
$ ●
$+$
/LQKDGHEORTXHLR
●
[
[
[
;⇒U Ι 8
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
3UV 3 ●
$78$/,=$d®(6
●
+ + ^`→+¶¶ ^`
3UVE ∧
F+ 3UV$+ 9
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
,7(5$d­2
F+
π
●
$+
π ∧
F Fπ$
∧
F Fπ$
∧
F Fπ$
∧
Fπ$
●
F ∧
72'26 FK⇒
62/8d­2Ï7,0$
),1,7$
10
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
[[[[[[[
6,03/(;&2080
[[[[[[[
11
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
[[[[[[[
12
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
6,03/(;
&/È66,&2
,'e,$
%È6,&$
$LQWHUDomR.VH
DSRLDWRWDOPHQWHHP
GDGRVSURYHQLHQWHV
GDLQWHUDomR.
5$=­2→
6,03/(;
5(9,6$'2
$LQWHUDomR.VH
DSRLDHPGDGRVGD
LQWHUDomR=(52
(&2120,$'(0(0Ï5,$
(
(&2120,$'(&È/&8/2
13
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
eDIRUPDSUHSDUDGD
GDLQWHUDomR.
(6758785$
'(
'$'26
∧
F,
∧,
$
([LJHRFRQKHFLPHQWRDWXDOL]DGR
∧
GH$++F+EH]
$OpPGLVWRGHQWURGHFDGDLWHUDomR
∧
pQHFHVViULRRFiOFXORGH πH$V
∧
E
$LQIRUPDomRGHYHVHU
DWXDOL]DGDDFDGD
LQWHUDomR
3,927($0(172
14
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
(;3/,&$d­2'26,03/(;5(9,6$'2
&202&$5$&7(5,=$5$62/8d­2%È6,&$
[+ $+E
] F+$+E
7(67('(27,0$/,'$'(
∧
F, F, π $,
&20
π
F+ $+
6$%(02648(6(
∧
F,→Ï7,02
&DVRFRQWUiULRHVFROKHVHXPDYDULiYHO
∧
[VSDUDHQWUDUQDEDVHFV!
15
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
&È/&8/2'2%/248(,2
∧ ∧V
[+ E$ [V!
6HQGR[VRPDLRUSRVVtYHO
&20
∧ $+E
E
∧V
+ V
$
$ $
$78$/,=$5(6758785$'('$'26
$+1292 3UV$+$17,*$
+$17,*2 ++U+U+P
+1292 ++UV+P
∧
∧
∧
E1292 E
$17,*2$V[V
∧ ]1292 ]$17,*2FV[V
16
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
&RPRYLPRVSURFHVVDVHWRGDLWHUDomRN
VHPQHFHVVLGDGHGHXPDHVWUXWXUDGHGDGRV
FRPSOHWDGDLWHUDomRN
20e72'26,03/(;&/È66,&2
,7(5$d­2
,7(5$d­2
,7(5$d­2
,7(5$d­2
,7(5$d­2
,7(5$d­2
20e72'26,03/(;5(9,6$'2
,7(5$d­2
,7(5$d­2
17
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP