491


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:

0x01 graphic
+ 1,

0x01 graphic
0x01 graphic
+ 1,

0x01 graphic
0x01 graphic
+ 1,

0x01 graphic
0x01 graphic
0x01 graphic
0x01 graphic
+ 12,

0x01 graphic
0x01 graphic
0x01 graphic
0x01 graphic
+ 16,

0x01 graphic
, gdzie 0x01 graphic
0x01 graphic

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?

0x08 graphic
nie tak

0x08 graphic
0x08 graphic
0x08 graphic

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

0x01 graphic

1

0x01 graphic

0

0

0

1

0

0

1

0x01 graphic

1

0x01 graphic

16

Z2

-2

-10

0

-4

0x01 graphic

-4

0x01 graphic

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

0x01 graphic

1

0x01 graphic

24

0

0

1

0

10e.r.

1

0x01 graphic

1

0x01 graphic

10

Z3

6

-2

0

4

0x01 graphic

-4

0x01 graphic

Iteracja 4.

-y1

-x12

0

-y2

-x31

0

x11

x22

y3

x21

x32

1

2

2

-2

-2

1

2

0x01 graphic

-2

0x01 graphic

0

0

0

0

0

0

1

1

0

-1

0

0x01 graphic

0x01 graphic

0x01 graphic
e.r.

0x01 graphic

0

0

0

0

0

1

0x01 graphic

0

0x01 graphic

1

Z4

-2

-4

0

0

0x01 graphic

0

0x01 graphic

Iteracja 5.

-y1

-x12

0

-y2

-x21

0

x11

x22

y3

x31

x32

1

1

0x01 graphic

0x01 graphic

0x01 graphic

Z5

0x01 graphic

0x01 graphic

0

0

0x01 graphic

0

0x01 graphic

Łą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 = 0x01 graphic
- tramwaje przez okres 0x01 graphic
okresu eksploatacji należy skierować do obsługi linii 1,

x32 = 0x01 graphic
- a przez 0x01 graphic
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 = 0x01 graphic
- w tej części okresu eksploatacji nie powinno się eksploatować tramwajów na żadnej linii, ta część okresu stanowi rezerwę wynoszącą 0x01 graphic
dób.



Wyszukiwarka