método SIMPLEx

Capítulo III:
ALGORITMO SIMPLEX
1
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
352&(',0(172'20e72'26,03/(;
3DVVDUGHVROXomR%È6,&$)$&7Ë9(/DXPD
RXWUDWHQWDQGRPHOKRUDUD)81d­22%-(7,92
(VFROKHUXPDYDULiYHOQmREiVLFDTXHPHOKRUHDIXQomRREMHWLYR
F,π$ ,!
HFRORFiODQDEDVH
(VFROKHUXPDYDULiYHOEiVLFDSDUDVDLUGDEDVHGHPRGRD
PDQWHUIDFWLELOLGDGH
2
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
(;(03/2
[[
]0$;
[[[
[[[
[[ [L!
6HMDDEDVH+ ^`
6ROXomR [ [ EiVLFD
IDFWtYHO [ [ [ 23/MiHVWiQD)250$35(3$5$'$UHODWLYDjEDVH
+ ^`⇒[H[VmRFDQGLGDWDVDHQWUDUQDEDVHSRLVVHXV
FRHILFLHQWHVVmRSRVLWLYRVHDXPHQWDP]
(VFROKR[SDUDDXPHQWDUHQWUDUQDEDVHHFRQVHUYR[DQtYHO]HURIRUDGDEDVH
3$5$0$17(5$)$&7,%,/,'$'(
[
[
[
[
[
[
[ [
[
/,1+$
%/248(,2
3
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
&21&/86­2
[HQWUDQDEDVHDVVXPHYDORUSRVLWLYR
[VDLGDEDVHDVVXPHYDORU]HUR
+ ^`⇒+ ^`
&RORFDUR3/QDIRUPD35(3$5$'$UHODWLYDjEDVH+
⇒%DVWDSLYRWHDUHPWRUQRGH$
[[[[[
]
[[[[[
]
129$62/8d­2
%È6,&$)$&7Ë9(/
4
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
$JRUDVy[ID]FUHVFHU]3RUWDQWRIDoR[FUHVFHUHQWUDUQDEDVH
HPDQWHQKR[DQtYHO]HURIRUDGDEDVH
3$5$0$17(5)$&7,%,/,'$'(
&21&/86­2
[ [
[
[ [
[
[ [LUUHVWULWR
/,1+$
%/248(,2
[HQWUDQDEDVH
[VDLGDEDVH
+ ^`⇒+ ^`
3LYRWHDUHPWRUQRGD$TXDGURDQWHULRU
)LFD
[[[[[
]
129$62/8d­2
%È6,&$)$&7Ë9(/
5
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
[DLQGDID]]FUHVFHU
[HQWUDQDEDVH
⇒
[EORTXHLDRFUHVFLPHQWRGH[[VDLGDEDVH
+ ^`⇒+
^`
[[[[[
]
62/8d­2
%È6,&$Ï7,0$
7RGRVRVFRHILFLHQWHVGDIXQomRREMHWLYRVmRQmRSRVLWLYRV
⇒]QmRSRGHPDLVDXPHQWDU
2%6(59$d®(6
VROXomRLOLPLWDGD
VROXomRP~OWLSOD
,17(535(7$d­2*(20e75,&$'26,03/(;
&DPLQKDGHSRQWRH[WUHPRHPSRQWRH[WUHPRDGMDFHQWHDWUDYpVGDDUHVWDTXHRV
OLJDQRVHQWLGRFHFUHVFHU]
6
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
$/*25,7026,03/(;5(680,'2
6XSRQGRFRQVLVWrQFLDQmRUHGXQGkQFLDHFRQKHFLGDXPDEDVHIDFWtYHOLQLFLDO
9HULILFDUVHDEDVHIDFWtYHODWXDOpyWLPD6HIRUWHUPLQRX6HQmRYiSDUD
'HWHUPLQDUDYDULiYHOQmREiVLFDDHQWUDUQDEDVH
'HWHUPLQDUDYDULiYHOEiVLFDDVDLUGDEDVH
$FKDUDQRYDVROXomREiVLFDIDFWtYHOSRUSLYRWHDPHQWRHYROWDUD
7
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
$/*25,7026,03/(;
6XSRQGRFRQVLVWrQFLDDXVrQFLDGHUHGXQGkQFLDVHFRQKHFLGDXPDEDVH
IDFWtYHOLQLFLDO+
FRORTXHRSUREOHPDQDIRUPDFDQ{QLFDUHODWLYDjEDVH+
∧
∧
GHWHUPLQH FV 0D[FL
L∉+
∧
VHFVWHUPLQRX$VROXomREiVLFD
FRUUHVSRQGHjEDVH+pyWLPD
∧
VHFV!YiSDUD
∧
H[DPLQHRYHWRU$V
∧
VH$VLHWRGRVVHXVFRPSRQHQWHVVmRQmRSRVLWLYRV
WHUPLQRX23/WHPVROXomRLQILQLWD
∧V
VH^L$L!`≠φ
DGHWHUPLQHU
∧V
∧
EU
∧V
$U
0tQLPR
∧V
^L!`
$U
∧
EL
{$ }
∧V
L
$U
ELGHQWLILTXHFRPRHOHPHQWRSLY{'HILQD
DQRYDEDVH+¶WURFDQGRVSRUU
∧V
FSLYRWHLHHPWRUQRGHHYROWHD
$U
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
8
&219(5*Ç1&,$'20e72'26,03/(;
1XPDLQWHUDomRGR6,03/(;TXDQGRVHSDVVDGHXPDVROXomREiVLFDIDFWtYHOj
RXWUDDIXQomRREMHWLYRFUHVFHGH∆]
∧
∧
FVE
∧V
U$ U
FROXQDV
∧
FV
OLQKDU
∧V
$U
]]
∧
EU
&RPRSRUKLSyWHVH
∧
FV!
∧
EU!
∧V
$U!
∧
VHFV⇒VROXomRyWLPD
QmRGHJHQHUHVFrQFLD
∧V
∧ V
VHF !H$ U ⇒VROXomRLOLPLWDGD
&RQFOXLVH
∆]!
9
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP
6HDIXQomRREMHWLYRFUHVFHHVWULWDPHQWHDFDGDLWHUDomRHRQ~PHURGHVROXo}HV
EiVLFDVIDFWËYHLVpILQLWRHQWmRRPpWRGR6,03/(;FRQYHUJHSDUDXPDVROXomR
yWLPDILQLWDRXSDUDXPDVROXomRyWLPDLOLPLWDGDQXPQ~PHURILQLWRGHSDVVRV
6,78$d®(6(63(&,$,6120e72'26,03/(;
3UREOHPDVGHPLQLPL]DomR
0LQI[ 0D[I[
(PSDWHQRFULWpULRGHHQWUDGDGDYDULiYHOQDEDVH
GHVHPSDWDVHDUELWUDULDPHQWH
(PSDWHQRFULWpULRGHVDtGDGDYDULiYHOQDEDVH
GHVHPSDWDVHDUELWUDULDPHQWHVROXomRGHJHQHUDGD
&LFODJHP
6HXP3/WHPVROXo}HVEiVLFDVIDFWtYHLVGHJHQHUDGDV
RPpWRGR6,03/(;SRGHILFDULQGHILQLGDPHQWHVHPRYHQGR
VREUHHODVFLFODQGR
pPXLWRUDUR
KiUHJUDVTXHHYLWDPFLFODJHP
10
Departamento de Engenharia de Sistemas - (DENSIS) FEEC/UNICAMP