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
Trolejbusy
Autobusy
Tramwaje
10
5
12
15
4
3
8
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,
+ 12,
+ 16,
, gdzie
Iteracja 0:
-x11
-x12
-x21
-x22
-x31
-x32
y1
y2
y3
0
1e.r.
16
Z0
-4
-8
-3
-5
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/.
...
figiela