Duaalne simpleksmeetod (0)

Duaalne   simpleksmeetod
 
 
Lineaarse planeerimise ülesanne
Lineaarse planeerimise ülesanne:
n
maksimiseerida
c x
j
j
j1
n
kitsendustel
 a x  b (i  ,
1 ,
2 ,m)
ij
j
i
j 1

x  0 ( j  ,
1 ,
2 n).
j
 
 
LP ülesanne maatrikskujul.
Kasutades maatrikssümboolikat ja tähistades
a
a
 a
11
12
1n
x
b
c
1
1
1
a
a
 a
21
22
2n
x
b
c
A 
2
x 
2
b 
2
c 







a
a
 a
1
m
m2
mn
x
b
c
n
m
n
võime lineaarse planeerimise ülesande kirjutada maatrikskujul
maxcT  x :
x
A  ,
b
x  
0 .
Lubatavate  lahendite  hulk on kirjapandav kujul
R   x :
x
A  b, x  
0 .
 
 
Duaalne simpleksmeetod.
Kui aga simplekstabel ei ole lubatav, kuid on duaalselt lubatav, siis 
tuleb optimaalse lahendi leidmiseks kasutada duaalset 
simpleksmeetodit. 
Erinevalt harilikust simpleksmeetodist tuleb duaalse simpleksmeetodi 
korral valida simplekstabelist  esmalt  välja juhtrida, ja seejärel juhtveerg 
ning viia siis läbi tabeli ridade  teisendus .
Kui simplekstabel ei ole lubatav, siis peab vähemalt üks  bk  0.
Juhtrida uuele simplekstabelile üleminekuks valitakse selliste ridade 
seast, kus bk  .
0
 
 
Duaalse simpleksmeetodi samm.
Kui selliseid ridu on rohkem kui üks, siis kasutatakse üht kahest reeglist:
1) juhtreaks valitakse alati esimene rida, kus bk  ;
0
2) juhtreaks valitakse alati rida, kus               ni
b
| b |
k  0
ng selajuures on  k
     suurim  sellistest  vabaliikmetest (kui sellisid on rohkem kui üks,
     siis nende seast esimene).
Kui juhtreaks on valtud k. rida, siis toimub juhtelemendi         va
akl
limine  
sellest  reast  järgmise reegli kohaselt:
c
c
l
 min j
| a |
a
0
kj  | a
kl
kj
 
 
Duaalse simpleksmeetodi samm (2).
Seega tuleb juhtveeruks valida juhtreas negatiivsete elementidega 
veergude hulgast see, mille puhul tabeli esimese rea elemendi jagatis 
juhtrea samas  veerus  paikneva elemendiga on absoluutväärtuselt vähim.  
Duaalse simpleksmeetodi  kasutamisel  säilib pärast iga sammu tabeli 
duaalne lubatavus, negatiivne element            a
bk
ga asendub elemendiga 
bk  0.
Sihifunktsiooni  väärtus küll kahaneb igal  sammul  monotoonselt, kuid see 
on loomulik, sest lähenemine optimaalsele lahendile toimub väljapoolt 
lubatavat hulka, ja nimelt sealt, kus sihifunktsiooni väärtus on suurem 
tema väärtusest lubatavate lahendite hulgas.
 
 
Näide
Leida muutujate  x , x , x
1
2
3
mittenegatiivsed väärtused, mis rahuldavad 
võrratuste süsteemi 
 2x  x  ,
2
1
2
2x  x  x  ,
1
1
2
3
x  x  2x   ,
3
1
2
3
ja mis muudavad maksimaalseks funktsiooni
z  x  3x .
2
3
 
 
Näide (2)
Lahendus
Korrutades teise võrratuse kitsenduste süsteemist arvuga –1, saame
 2x  x  ,
2
1
2
 2x  x  x   ,
1
1
2
3
x  x  2x   ,
3
1
2
3
Defineerides mittenegatiivsed abimuutujad  x  ,
0 x  ,
0 x  ,
0
4
5
6
saame kirjutada võrratuste süsteemi võrrandisüsteemina:
 2x  x  x  ,
2
1
2
4
 2x  x  x  x   ,
1
1
2
3
5
x  x  2x  x   .
3
1
2
3
6
 
 
Näide (3)
Et sihivõrrandis
x  3x  z  0
2
3
on kõik kordajad mittenegatiivsed, siis saame duaalselt  lubatava  
simplekstabeli:
1
x
x
x
x
x
x
1
2
3
4
5
6
0
0
1
3
0
0
0
c j
1
min

2
 2 1
0
1
0
0
a j 0
3,
| a | |
j
1|
3,
1  2 1 1 0
1
0
Juhtrida
 3 1
1  2 0
0
1
Juhtelement
Juhtveerg
 
 
Näide (4)
1
x
x
x
x
x
x
1
2
3
4
5
6
 3 1
0
1
0
0
1
c j
1
min

1 1 0  2 1
0
1
a j 0
1
| a | | 2
j
 |
1
2
 3 0
1
0
1
1
3
1 1
2
0
0
1
1
x
x
x
x
x
x
1
2
3
4
5
6
 7 / 2 1/ 2
0
0
1/ 2
0
3/ 2
1/ 2
1/ 2
0
1
1/ 2 0 1/ 2
3/ 2
 7 / 2 0
0
1/ 2
1
1/ 2
2
 2
1
0
1
0
0
Viimane simplekstabel on lubatav kui ka duaalselt lubatav, seetõttu 
vastab ta optimaalsele lahendile. Optimaalne  lahend on:
  *
x  ( ,
0 ,
2 1/ ,
2 ,
0 3/ ,
2 0).  
Duaalse ja  primaarse  simpleksmeetodi 
järjestikune rakendamine
Kui simplekstabel ei ole lubatav ega ka duaalselt lubatav, siis ei ole 
täidetud eeldused ei primaarse ega ka duaalse simpleksmeetodi 
rakendamise  jaoks.
Sel korral rakendatakse algul üht neist  meetoditest  lihtsustatud kujul, 
teisel etapil aga teist meetodit  eespool  kirjeldatud kujul.
Kui näiteks rakendada algul duaalset simpleksmeetodit, siis võib pärast 
juhtrea valimist valida juhtelemendiks esimese negatiivse elemendi 
juhtreast.
Kui aga rakendada algul  primaarset  simpleksmeetodit, siis võib pärast 
juhtveeru valimist valida juhtelemendiks selle rea esimese positiivse 
elemendi.
 
 
Näide
Leida muutujate  x , x , x
1
2
3
mittenegatiivsed väärtused, mis rahuldavad 
võrratusesüsteemi x  x  x  ,1
1
2
3
x  3x  x  ,
2
1
2
3
x  2x  4x  2
1
2
3
mis muudavad maksimaalseks funktsiooni
z  x  3x  4x .
1
2
3
 
 
Näide (2)
Lahendus
Korrutame teise ja kolmanda võrratuse arvuga –1:
x  x  x  ,
1
1
2
3
 x  3x  x   ,
2
1
2
3
 x  2x  4x  2
1
2
3
ja võtame kasutusele mittenegatiivsed abimuutujad x  ,
0 x  ,
0 x  0 :
4
5
6
x  x  x  x  ,
1
1
2
3
4
 x  3x  x  x   ,
2
1
2
3
5
 x  2x  4x  x   .
2
1
2
3
6
 
 
Näide (3)
Viimasest süsteemist  näeme, et ülesande simplekstabel tuleb 
mittelubatav. Et sihivõrrandis  
z  x  3x  4x  0
1
2
3
on negatiivseid kordajaid, siis simplekstabel ei ole ka duaalselt lubatav.  
Lahendamiseks kasutame algul duaalset simpleksmeetodit lihtsustatud 
juhtelemendi valikuga, seejärel primaarset simpleksmeetodit.  
 
 
Näide (4)
1
x
x
x
x
x
x
1
2
3
4
5
6
0
1  3  4 0
0
0
1
1
1
1
1
0
0
Duaalne 
simpleksmeetod 
 2 1  3 1 0
1
0
lihtsustatud 
 2 1  2  4 0
0
1
juhtelemendi 
2
0
0
 3 0 1 0
valikuga
1 0  2 0 1 1 0
2
1
3
1
0 1 0
0
0
1
 3 0 1 1
2
0 0  3
0
1
0
1/ 2
0 1
0
1/ 2 1/ 2 0
1/ 2
1 0
1
3/ 2
1/ 2
0
 
1/ 2 0 0  3 1/  2 1/ 2 1
Näide (5)
5/ 2 0 0 0 1/ 2 1/ 2
1
Primaarne 
1/ 2 0 1 0 1/ 2 1/ 2
0
simpleksmeetod
1/ 3 1 0 0
5/ 3
1/ 3
1/ 3
1/ 6 0 0 1 1/ 6
1/ 6
1/ 3
7 / 2 3 0 0
9 / 2
1/ 2
0
1/ 2 0 1 0 1/ 2 1/ 2 0
1
3 0 0
5
1
1
1/ 2 1 0 1
3/ 2
1/ 2
0
Optimaalne lahend:
x  ( ,
0 1/ ,
2 1/ ,
2 ,
0 ,
0 ).
1
 
 
Näide (6)
1
x
x
x
x
x
x
1
2
3
4
5
6
Nüüd rakendame  
0
esmalt primaarset, 
1  3  4 0
0
0
seejärel duaalset 
1
1
1
1
1
0
0
simpleksmeetodit
 2 1  3 1 0
1
0
Primaarne s.-meetod
 2 1  2  4 0
0
1
4
3
1
0 4 0 0
1
1
1
1 1 0 0
Duaalne s.-meetod
1 0  2 0 1 1 0
2
3
2
0 4 0 1
7 / 2 3 0 0
9 / 2
1/ 2
0
Opt. lahend:
1/ 2 1 0 1
3/ 2
1/ 2
0
1/ 2 0 1 0 1/ 2 1/ 2 0
x  ( ,
0 1/ ,
2 1/ ,
2 ,
0 ,
0 ).
1
 
1
3 0 0   5
1
1

Document Outline

• Duaalne simpleksmeetod
• Lineaarse planeerimise ülesanne
• LP ülesanne maatrikskujul.
• Duaalne simpleksmeetod.
• Duaalse simpleksmeetodi samm.
• Duaalse simpleksmeetodi samm (2).
• Näide
• Näide (2)
• Näide (3)
• Näide (4)
• Duaalse ja primaarse simpleksmeetodi järjestikune rakendamine
• Slide 12
• Slide 13
• Slide 14
• Slide 15
• Näide (5)
• Näide (6)