120 121

120 121



120 Programowanie liniowe całkowito liczbowe

odpowiadające zmiennej bazowej o wartości niecałkowitej. Na podstawie tego ograniczenia konstruujemy dodatkowy warunek ograniczający, nazywany równaniem dęcia. Nazwa bierze się stąd, żc ten dodatkowy warunek odcina ze zbioru rozwiązań dopuszczalnych niecałkowite rozwiązanie optymalne zadania zrelaksowanego (oraz dodatkowo pewne inne rozwiązania tego zadania), jednak wśród tych odrzuconych punktów nie ma żadnego rozwiązania dopuszczalnego wyjściowego zadania programowania całkowitoliczbowego.

Zaproponowany dalej sposób konstrukcji równania cięcia generuje, po dołączeniu tego równania do zbioru pozostałych warunków ograniczających rozpatrywanego zadania, rozwiązanie bazowe optymalne, lecz niedopuszczalne. Chcąc przejść do kolejnego rozwiązania dopuszczalnego (i optymalnego), stosujemy dualną metodę simpleks. Konstruujemy kolejne równania cięcia tak długo, aż otrzymamy rozwiązanie całkowitoliczbowe zadania zrelaksowanego z dołączonymi dodatkowo kolejnymi równaniami cięć. Otrzymane w ten sposób rozwiązanie jest rozwiązaniem optymalnym wyjściowego zadania programowania całkowitoliczbowego.

2.3.1. Konstrukcja równania cięcia

Sposób konstrukcji równania cięcia i wykorzystania go w obliczeniach zilustrujemy za pomocą przykładu.

Przykład 2.4

Pokażemy zastosowanie naszkicowanego powyżej postępowania na przykładzie zadania sformułowanego w przykładzie 2.1. Przypomnijmy to zadanie:

jc, + x2 —» max, ją + 2x2 < 32,

18*1 + 3,r2 ^ 224,

ją, x2 > 0,

ją, x2 — całkowite.

Rozpatrzymy zadanie z pominięciem warunków całkowitoliczbowości. Wprowadzając zmienne bilansujące, sprowadzamy zadanie do postaci standardowej, która jest jednocześnie postacią bazową. Otrzymujemy:

ją + x2 —» max,

ją+2x2+.K:i    = 32,

I 8jc, + 3jc2 +j.'4=224, ją, x2, ją, xA ^ 0.

Zadanie możemy rozwiązać, stosując prymalną metodę simpleks. Ostatnią tablicę simpleksową przedstawiono w postaci tablicy 2.2.

Tablica 2.2

cx —>

max

1

1

0

0

b

Baza

*1

*2

*2

1

0

1

0,5455

-0,0303

10,6667

**l

1

1

0

-0,0909

0,0606

10,6667

cr

-Z/

0

0

-0,4545

-0,0303

21,3333

Uzyskane rozwiązanie zadania liniowego nie daje nam rozwiązania w liczbach całkowitych, przystąpimy więc do konstrukcji równania cięcia, które dołączymy do rozpatrywanego przez nas zadania. Wykorzystamy do tego celu ten wiersz tablicy simpleksowej, w którym odpowiadająca mu zmienna bazowa przyjmuje wartość niecałkowitą i jej część ułamkowa jest największa. W otrzymanym rozwiązaniu mamy *, =*2 = 10,6667, stąd części ułamkowe są takie same i mamy [10,66671 = 10 (przypomnijmy, że symbol [a] oznacza największą liczbę całkowitą nie przekraczającą a). W celu utworzenia równania cięcia wybieramy równanie odpowiadające zmiennej *,. Ma ono postać:

z, - 0,0909*, + 0,0606*, = 10.6667.    (2.1)

Zauważmy, że ponieważ dla współczynników przy zmiennych niebazowych zachodzą związki:

[-0,0909] <-0,0909

oraz

[0,0606] 0,0606, tak więc:

[-0,0909]*,0,0909*, oraz

[0,0606] *4 < 0,0606*4.

Dodając stronami dwie powyższe nierówności, otrzymujemy:

[-0,0909]*, + [0,0606]*4 ^ -0.0909*, + 0,0606*4.

Jeżeli do obu stron ostatniej nierówności dodamy zmienną *,, to otrzymamy:

*, + [- 0,0909]*, +10,0606] *4 <*,-0,0909*, + 0,0606*4 = 10,6667.

Końcowa równość jest powtórzeniem rozpatrywanego przez nas równania. Z powyższego związku wynika, że:

+ [- 0,0909]*, + [0,0606]*4 < 10,6667.


Wyszukiwarka

Podobne podstrony:
SOBOTA, 26.10.2013 9.15 s. 2.17 Programowanie liniowe i całkowitoliczbowe s. 1.13 Pomiar
106 107 2 106 Programowanie liniowe całkowitoliczbowe leks, a także metodę geometryczną, moż.na wyko
108 109 2 108 Programowanie liniowe całkowitoliczbowe Rysunek 2.1 Rozpatrzymy najpierw możliwość pod
110 111 I 10 Programowanie liniowe całkowito!iczbowe jest celowy, gdyż nie jest możliwe wygenerowani
112 113 Programowanie liniowe całkowitoliczbowe Rysunek 2.6    Rysunek 2.7112 Przykła
114 115 I 14 Programowanie liniowe całkowitoliczbowe Otrzymujemy następujące zadania: I 14 Programow
116 117 I 16 Programowanie liniowe całkowitoliczbowe Iteracja 5 Porządkujemy lisię zadań. Na liście
118 119 I 18 Programowanie liniowe całkowitoliczbowe Przykład 2.3 Należy rozwiązać zadanie: /(jc,, j
122 123 122 Programowanie liniowe całkowitoliczbowe Ponieważ zmienne *,, *,, x4 mogą przyjmować jedy
124 125 124 Programowanie liniowe całkowitoliczbowe Interpretację geometryczną metody cięć przedstaw
126 127 126 Programowanie liniowe całkowitoliczbowe decyzyjny małego wydawnictwa przygotowującego pl
128 129 128 Programowanie liniowe całkowitoliczbowe •    warunki określające możliwoś
130 131 130 Programowanie liniowe całkowitoliczbowe W swoich planach wydawnictwo nie zamierza uwzglę
132 133 132 Programowanie liniowe całkowitoliczbowe Interpretacja rozwiązania Maksymalna wielkość sp
134 135 134 Programowanie liniowe calkowitoliczbowe Rozwiązanie optymalne Zadanie rozwiązujemy za po
120 Małgorzata Winter obrazu, stanowiąca odpowiednik wyrażonej w doktrynie anglosaskiej zasady true
120 121 (2) 120 ĆWICZENIA I WYJAŚNIENIA Zazwyczaj w tego typu zadaniach jest kilka rysunków, na któr
066 067 2 66 Programowanie linioweTwierdzenie 1.3 Dla rozwiązań optymalnych9 x, y, odpowiednio, zada
082 083 2 82 Programowanie liniowe Będziemy znajdowali kolejne przedziały, posuwając się po osi licz

więcej podobnych podstron