Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Rozdział2
Opisalgorytmu
sympleksowego
2.1
Wprowadzenie
Wniniejszymrozdzialeprzedstawionyzostaniealgorytmsympleksowy,służący
rozwiązywaniuproblemówprogramowanialiniowego.Będziemysystematycznie
zwiększaćstopieńtrudnościprzykładów,bywpodrozdziale2.3podaćszczegó-
łowyopisalgorytmu.Podanazostanietakżemetodawyznaczeniapierwszego
rozwiązaniadopuszczalnegoorazmetodaunikaniazjawiskacykliczności.
Przykład2.1.1
RozważmyPPL:
x1+2x2+3x3
≤5
2x1+3x2+5x3
3x1+
x2+3x3
xi≥0(ź=1j...j3)
≤8
≤4
z
=2x1+
x2+3x3
→
max
(2.1)
Pierwszymkrokiemalgorytmusympleksjestwprowadzeniezmiennychuzu-
pełniających:x4jx5jx6,którezdefiniujemynastępująco:
(
x4=5−
x1−2x2−3x3
4
x5=8−2x1−3x2−5x3
l
x6=4−3x1−
x2−3x3
Rozważmyterazponiższyproblem:
x4=
5
8
4
0
−
−2x1−3x2
−3x1−
x1−2x2
x2
−
−
−
3x3
5x3
3x3
(ź=1j...j6)
x5=
x6=
xi≥
z
=2x1+
x2+3x3→max
15
(2.2)
(2.3)
