Przykład 1.
Dwie linie komunikacji miejskiej mogą być obsługiwane przez trzy rodzaje środków transportu: trolejbusy, autobusy i tramwaje. Dane o dziennej zdolności przewozowej, dziennych kosztach eksploatacji, okresie eksploatacji środków transportu i przewidywanej wielkość pracy poniżej:
Rodzaj środka transportu |
Dzienna zdolność przewozowa [tys. pasażero-km] na linii
|
Dzienne koszty eksploatacji [tys. zł] na linii |
Okres eksploatacji [doby] |
||
|
1 |
2 |
1 |
2 |
|
Trolejbusy Autobusy Tramwaje
|
10 5 12 |
15 10 10 |
4 3 5 |
8 4 4 |
300 300 300 |
Planowana wielkość pracy Transportowej [tys. pasażero-km] |
3600 |
4800 |
|
Należy opracować plan przydziału środków transportu dla obu linii komunikacji miejskiej, przyjmując jako kryterium optymalizacji, minimum kosztów eksploatacji.
Zmienne decyzyjne: X = [xij], /i=1,2,3; j=1,2/, xij oznacza tę część okresu eksploatacji , w którym środek transportu „i-tego” rodzaju przeznaczony jest do eksploatacji na „j-tej” linii.
Warunki brzegowe: xij ≥ 0 oraz x11 + x12 ≤ 1,
x21 + x22 ≤ 1,
x31 + x32 ≤ 1.
Warunki wewnętrznej zgodności: na linii nr 1: 300 (10x11 + 5x21 + 12x31) = 3600,
na linii nr 2: 300 (15x12 + 10x22 + 10x32) = 4800.
Funkcja celu: K (xij) = 300 (4x11 + 8x12 + 3x21 + 4x22 + 5x31 + 4x32).
Rozwiązanie:
Postać kanoniczna zadania:
+ 1,
+ 1,
+ 1,
+ 12,
+ 16,
, gdzie
Iteracja 0:
|
-x11 |
-x12 |
-x21 |
-x22 |
-x31 |
-x32 |
|
y1 y2 y3 0 0 |
1e.r. 0 0 10 0 |
1 0 0 0 15 |
0 1 0 5 0 |
0 1 0 0 10 |
0 0 1 12 0 |
0 0 1 0 10 |
1 1 1 12 16 |
Z0 |
-4 |
-8 |
-3 |
-4 |
-5 |
-4 |
0 |
By otrzymać pierwsze rozwiązanie bazowe w przypadku gdy niektóre z elementów pierwszej kolumny tablicy simplex są zerami należy stosować zmodyfikowany algorytm pochodzący od Jordana.. Zwraca on szczególną uwagę na wiersze z zerami.
Algorytm wyboru elementu rozwiązującego:
Wybrać dowolny wiersz zawierający zero w pierwszej kolumnie
|
Czy są w tym wierszu elementy dodatnie?
|
nie tak
Zadanie nie ma rozwiązania, układ warunków wewnętrznej zgodności jest sprzeczny.
|
|
W wierszu tym wybrać dowolny element dodatni, kolumna zawierająca ten element jest kolumną rozwiązującą. |
|
|
|
|
|
Oznaczyć w kolumnie rozwiązującej wszystkie dodatnie elementy /oprócz elementu w wierszu funkcji celu/.
|
|
|
|
|
|
Dla każdego oznaczonego elementu obliczyć iloraz: elementu z kolumny wyrazów wolnych znajdujących się w danym wierszu przez oznaczony element znajdujący się w tym wierszu.
|
|
|
|
|
|
Element, dla którego otrzymany iloraz jest najmniejszy, wybrać jako element rozwiązujący.
|
Iteracja 1.
|
-y1 |
-x12 |
-x21 |
-x22 |
-x31 |
-x32 |
|
x11 y2 y3 0 0 |
1 0 0 -10 0 |
1 0 0 -10 15 |
0 1 0 5e.r. 0 |
0 1 0 0 10 |
0 0 1 12 0 |
0 0 1 0 10 |
1 1 1 2 16 |
Z1 |
4 |
-4 |
-3 |
-4 |
-5 |
-4 |
4 |
Iteracja 2.
|
-y1 |
-x12 |
0 |
-x22 |
-x31 |
-x32 |
|
x11
y2
y3
x21
0 |
1
2
0
-2
0 |
1
2
0
-2
15 |
0
0
0
0
0 |
0
1e.r.
0
0
10 |
0
1
0 |
0
0
1
0
0 |
1
1
16 |
Z2 |
-2 |
-10 |
0 |
-4 |
|
-4 |
|
Iteracja 3.
|
-y1 |
-x12 |
0 |
-y2 |
-x31 |
-x32 |
|
x11
x22
y3
x21
0 |
1
2
0
-2
-20 |
1
2
0
-2
-5 |
0
0
0
0
0 |
0
1
0
0
-10 |
0
1
24 |
0
0
1
0
10e.r. |
1
1
10 |
Z3 |
6 |
-2 |
0 |
4 |
|
-4 |
|
Iteracja 4.
|
-y1 |
-x12 |
0 |
-y2 |
-x31 |
0 |
|
x11
x22
y3
x21
x32 |
1
2
2
-2
-2 |
1
2
-2
|
0
0
0
0
0 |
0
1
1
0
-1 |
0
|
0
0
0
0
0 |
1
0
1 |
Z4 |
-2 |
-4 |
0 |
0 |
|
0 |
|
Iteracja 5.
|
-y1 |
-x12 |
0 |
-y2 |
-x21 |
0 |
|
x11
x22
y3
x31
x32 |
|
|
|
|
|
|
1
1
|
Z5 |
|
|
0 |
0 |
|
0 |
|
Łączny koszt eksploatacji na obydwu liniach przy użyciu trolejbusów, autobusów i tramwaji w ciągu 300 dób sięga kwoty 3.370 tys. zł.
Decyzje dyspozytora:
x11 = 1 - trolejbusy przez cały okres należy eksploatować na linii 1,
x12 = 0,
x21 = 0
x22 = 1- autobusy przez cały okres należy eksploatować na linii 2,
x31 =
- tramwaje przez okres
okresu eksploatacji należy skierować do obsługi linii 1,
x32 =
- a przez
okresu tramwaje obsługują linię 2,
y1 = 0
y2 = 0 - trolejbusy i autobusy należy eksploatować przez cały okres tj. 300 dób,
y3 =
- w tej części okresu eksploatacji nie powinno się eksploatować tramwajów na żadnej linii, ta część okresu stanowi rezerwę wynoszącą
dób.