Logistyka.net.pl

Komputerowe wspomaganie

TRANSCOMP - XIV INTERNATIONAL CONFERENCE
COMPUTER SYSTEMS AIDED SCIENCE, INDUSTRY AND TRANSPORT
Planowanie transportu, Metody optymalizacyjne, Programowanie sieciowe

Danuta OLĘDZKA
Arkadiusz WĘGLARZ 2

KOMPUTEROWE WSPOMAGANIE
PLANOWANIA I ORGANIZACJI TRANSPORTU NA PLACU BUDOWY.
FRAGMENT MATERIAŁÓW DYDAKTYCZNYCH, CZĘŚĆ I
W referacie przedstawiono wybrane zastosowania metod komputerowych: programowania liniowego i programowania sieciowego, w procesie podejmowania decyzji dotyczących planowania i organizacji transportu materiałów na placu budowy. Opracowanie jest częścią materiałów dydaktycznych przedmiotu „Metody komputerowe w inżynierii lądowej”, który autorzy referatu prowadzili w latach
1988 - 2002 dla studentów budownictwa na Politechnice Warszawskiej.

COMPUTER-AIDED CONSTRUCTION SITE PLANNING AND TRANSPORT
ORGANIZATION. EDUCATIONAL MATERIALS, PART I
The papers presents selected applications of computing methods (linear programming and network programming) to decision-making processes regarding construction site materials planning and transport organization. The study is a part of educational materials of academic course "Computing methods in civil engineering", which was held by the authors in years 1988 - 2002 for building department students at Warsaw University of Technology.

1. WSTĘP
Celem przedmiotu „Metody komputerowe w inżynierii lądowej”, który autorzy prowadzili dla studentów specjalności „Technologia i organizacja budowy”, było wprowadzenie do wspomagania komputerowego w decyzjach dotyczących planowania i organizacji w budownictwie. Ramowy program przedmiotu był następujący:
1. Przegląd metod komputerowych stosowanych w inżynierskich zadaniach decyzyjnych. Wprowadzenie do modelowania matematycznego.
2. Programowanie liniowe - zastosowania w planowaniu produkcji, gospodarce materiałowej, planowaniu realizacji przedsięwzięć.
Wydział Inżynierii Lądowej, Politechnika Warszawska, al. Armii Ludowej 16, e-mail: d.oledzka@il.pw.edu.pl
Wydział Inżynierii Lądowej, Politechnika Warszawska, al. Armii Ludowej 16, e-mail: a.weglarz@il.pw.edu.pl

2560

Danuta OLĘDZKA , Arkadiusz WĘGLARZ
Programowanie sieciowe - zastosowania w optymalizacji transportu, zagadnieniach lokalizacji, projektowaniu tras komunikacyjnych, w zagadnieniach kombinatorycznych.
4. Analiza czasowo-kosztowa realizacji przedsięwzięcia. Decyzje finansowe.
5. Programowanie dynamiczne - zastosowania w gospodarce środkami produkcji, planowaniu wielookresowym, planowaniu realizacji przedsięwzięć.
6. Teoria masowej obsługi - zastosowania w planowaniu i organizacji robót budowlanych, organizacji produkcji.
7. Gospodarka zapasami - komputerowa analiza systemu zapasów.
8. Systemy ekspertowe - wprowadzenie do pracy z bazami danych, metody określania efektywności decyzji w sytuacji niepewności i ryzyka.
9. Symulacja cyfrowa - zastosowanie w planowaniu realizacji zadań budowlanych z uwzględnieniem czynników losowych.
Zagadnienia związane z transportem są omawiane w punktach 2, 3, 5, 8, 9. W tym referacie ograniczamy się do programowania sieciowego.
2. WYZNACZANIE TRASY O MINIMALNEJ DŁUGOŚCI
Weźmy pod uwagę sieć , W - n-elementowy zbiór węzłów, L ⊆ W × W - zbiór łuków. W sieci określono długości łuków. W programowaniu sieciowym termin droga oznacza ciąg węzłów i łuków: x, , x, …, (xk-1,xk), xk, gdzie x, .., xk jest ciągiem różnych węzłów, są łukami sieci, i=1, .., k-1. Zadanie polega na wyznaczeniu drogi o minimalnej długości pomiędzy wybranymi węzłami. Bez straty ogólności można przyjąć, że szukaną drogą jest droga prowadząca z jedynego węzła początkowego do jedynego węzła końcowego sieci. Postępowanie to opisują zależności rekurencyjne ([1], [2]):
z := 0 z j := min (z i + d ij ) i< j
gdzie
L z dij
:= j = 2, .., n,
< i, j > ∈ L jest zbiorem łuków sieci o n węzłach, jest liczbą węzłową przypisaną węzłowi początkowemu sieci, jest długością łuku , „staje się”, znak przypisania zmiennej wartości liczbowej wyrażenia.

Wartość zj jest długością optymalnej drogi prowadzącej z węzła 1 do węzła j, j=2, .., n.; stąd wartość zn - jest długością drogi z węzła początkowego 1 do węzła końcowego n.
W II etapie obliczeń, wędrując od węzła końcowego, znajduje się łuki wchodzące w skład optymalnej drogi.

KOMPUTEROWE WSPOMAGANIE PLANOWANIA I ORGANIZACJI
Przykład 1. Wyznaczenie trasy o minimalnej długości.
Rysunek 1 przedstawia schemat układu tras komunikacyjnych. Liczby znajdujące się nad łukami, oznaczającymi możliwość transportu zgodnie ze strzałką, mogą oznaczać, przykładowo, odległość lub czas przejazdu. W pierwszym przypadku decydentowi zależy na wyznaczeniu najkrótszej trasy, w drugim - najszybszej. W obu przypadkach algorytm obliczeń komputerowych jest ten sam.
Etap 1 z1:=0 z2:=13 z3:=min(6,13+9)=6 z4:=min(13+5,6+2)=8 z5:=min(13+7,8+4)=12

Rys. 1 Sieć opisująca układ tras komunikacyjnych w przykładzie 1

Etap 2
Droga o minimalnej długości: x, , x, , x, , x

3 WYZNACZANIE TRASY O MAKSYMALNEJ PRZEPUSTOWOŚCI
W sieci S= następuje przepływ, rozumiany jako transport umownych jednostek po łukach sieci. Przyjmijmy, że dla wszystkich łuków określono ich górną przepustowość gij maksymalną liczbę jednostek, jaka może być transportowana (płynąć) łukiem. Zadanie polega na wyznaczeniu maksymalnej liczby jednostek, które mogą wypłynąć z węzła początkowego i dopłynąć do węzła końcowego ([1]).
Model matematyczny: wyznaczyć max v przy ograniczeniach
dla i = 1
v
 x i j − ∑ x ji =  0 dla i = 2, ..., n − 1
∑ j∈A i j∈Bi
 − v dla i = n

0 ≤ x i j ≤ g i j dla < i, j >∈ L gdzie: v
Ai ={j ∈ W: ∈ L}
szukana liczba jednostek, wartość przepływu, zbiór węzłów, do których prowadzą łuki wychodzące z i-tego węzła, dla i = 1, .., n, Bi ={j ∈ W: ∈ Ł} zbiór węzłów, z których prowadzą łuki wchodzące do i-tego węzła, dla i = 1, .., n.
Zmienne decyzyjne zadania stanowią:

2562

Danuta OLĘDZKA , Arkadiusz WĘGLARZ
xij - przepływ po łuku, liczba jednostek płynących łukiem v - przepływ w sieci, liczba jednostek płynąca z węzła początkowego do końcowego.
Zależności (4) stanowią warunki zachowania przepływu: oznacza to, że w każdym węźle pośrednim liczba jednostek wpływających musi być równa liczbie jednostek wypływających, a wszystkie v jednostek wywiezionych z węzła początkowego bez strat dochodzi do węzła końcowego.
Zadanie (3) - (5) jest zadaniem programowania liniowego, lecz ze względu na szczególną postać macierzy ograniczeń istnieje algorytm bardziej efektywny od algorytmu sympleks.
Idea algorytmu:
Jest to metoda iteracyjna. Przyjmijmy, że łuki mają jednakową orientację oraz, że istnieje dokładnie jeden węzeł początkowy i dokładnie jeden węzeł końcowy.
Obliczenia rozpoczyna się od dowolnego przepływu dopuszczalnego, przykładowo xij = 0, dla wszystkich ∈ L. W kolejnym kroku wyznacza się drogi prowadzące z węzła początkowego do węzła końcowego, po których może popłynąć więcej jednostek niż dotychczas; są to drogi powiększalne ze względu na obecny przepływ. Aktualny przepływ zwiększa się o jak największą wartość, dopuszczalną ze względu na ograniczoną przepustowość łuków. Postępowanie to powtarza się tak długo, aż nie będzie drogi o podanej własności, wówczas aktualny przepływ jest optymalny.
W obliczeniach komputerowych w każdym kroku iteracyjnym przypisuje się węzłom wartości Ej, o jakie można maksymalnie zwiększyć przepływ od węzła początkowego do danego i-tego węzła.
Z węzła początkowego próbujemy wypuścić maksymalną liczbę jednostek E1:

E =

∑x
j∈A
1j

Do j-tego węzła możemy dowieźć tyle jednostek, ile zostało dowiezionych do węzła i, poprzedzającego oraz na ile pozwala przepustowość łuku :

E j = max ( min (E i , g i j − x i j ))
dla j = 2, ..., n
Przepływ zwiększa się o wartość ∆v = En.
Przykład 2 Wyznaczenie trasy o maksymalnej przepustowości.
Przedsiębiorstwo robót drogowych wykonuje podsypkę kamienną.
Rysunek 2 przedstawia schemat sieci komunikacyjnej wraz z przepustowościami
[tony/h] poszczególnych odcinków dróg łączących kamieniołom 1 z budową 5.
Celem jest wyznaczenie trasy, którą można przewieźć maksymalną ilość kamienia.
Rys. 2. Schemat sieci w przykładzie 2

KOMPUTEROWE WSPOMAGANIE PLANOWANIA I ORGANIZACJI
Wyniki obliczeń komputerowych kolejnych iteracji są w tablicy 1.

Numer iteracji
Liczby węzłowe
∆v =E

Tablica 1. Wyniki obliczeń przykładu 2
Aktualny przepływ po łuku x x x x x
x

4. WYZNACZENIE TRASY TRANSPORTU O MINIMALNYCH KOSZTACH.
Zadanie wyznaczenia trasy transportu danej liczby jednostek materiału, w terminach programowania sieciowego jest następujące. W danej sieci zorientowanej, w której dla każdego łuku określono górną przepustowość przepływu gij oraz koszt przepływu jednostki cij należy wśród przepływów ustalonej wartości v, dopuszczalnych ze względu na przepustowości łuków, wyznaczyć przepływ o minimalnym koszcie ([2]).
W modelu matematycznym:
min
wyznaczyć

∑c

∈ L
ij
xi j przy ograniczeniach (4) - (5).
Algorytm, z którego będziemy korzystać, w literaturze ma nazwę „out of kilter”. Algorytm ten jest efektywną numerycznie metodą rozwiązania wielu zadań decyzyjnych.
Mianowicie:
- dla wszystkich łuków sieci wprowadza się dolną przepustowość d ij :
d i j ≤ x i j ≤ g i j dla < i, j >∈ L zamiast przepływu wprowadza się pojęcie opływu przez dołączenie do sieci łuku powrotnego , dla którego przyjmuje się:
c n = 0, d n 1 = g n = v
Wówczas warunki (4) zachowania przepływu są następujące:

∑ x −∑ x
j∈A i
ij
j∈B i
ji

=0
dla i = 1, ..., n
Strategia algorytmu jest następująca.
Teoretycznie wyprowadzono warunki, jakie musi spełniać x ij przepływ po konkretnym łuku , aby ów przepływ był optymalny w sensie zadania (8), (4), (5); łuk w takim stanie nosi nazwę uregulowanego (termin amerykański: „in kilter”).

2564

Danuta OLĘDZKA , Arkadiusz WĘGLARZ

Zadanie sprowadza się do uregulowania wszystkich łuków. Metoda jest iteracyjna. Jako opływ początkowy przyjmuje się dowolny opływ, dopuszczalny lub nie, ale spełniający warunki (12), przykładowo opływ zerowy. Krok iteracyjny polega na uregulowaniu kolejnych łuków, z tym że łuki już uregulowane nie tracą swej własności. Sprowadza się to do wyznaczania nowych dróg powiększalnych ze względu na aktualny opływ i wyznaczania nowego opływu o wartości bliższej v, zawsze o minimalnych kosztach.
Przykład 3. Wyznaczanie trasy transportu o minimalnych kosztach.
W sieci, której schemat przedstawia rysunek 3, należy przewieźć 3 jednostki materiału z węzła początkowego do końcowego. Nad łukami napisano trójki liczb: (d ij , g ij , c ij ).

Rys. 3 Schemat sieci dla przykładu 3
Aby wymusić przepływ wartości 3 z węzła 1 do węzła 4, wprowadza się łuk powrotny
<4, 1> i przypisuje mu się wartości: (d, g, c41) = (3, 3, 0).
Wyniki obliczeń komputerowych programem opracowanym dla potrzeb dydaktyki przedstawia rysunek 4.

Rys. 4. Wyniki obliczeń komputerowych przykładu 3

5. ROZWIĄZANIE KLASYCZNEGO ZADANIA TRANSPORTOWEGO
Problem decyzyjny dotyczy zaplanowania przewozu jednorodnego materiału od m dostawców do n odbiorców tak, aby zminimalizować nakłady ponoszone na transport: koszt lub liczbę ton⋅km. W pierwszym przypadku zakłada się, że koszt transportu jest proporcjonalny do liczby przewożonych jednostek ([2]), [3]).

KOMPUTEROWE WSPOMAGANIE PLANOWANIA I ORGANIZACJI
Zmienne decyzyjne: xij - liczba jednostek przewożonych od i-tego dostawcy do j-tego odbiorcy.
Parametry zadania: ai - liczba jednostek materiału dostępnego u i-tego dostawcy, bj - liczba jednostek materiału potrzebna j-temu odbiorcy, cij - odległość pomiędzy i-tym dostawcą a j-tym odbiorcą lub koszt przewozu jednostki materiału na tej trasie
Oznaczmy:
A - suma materiału u dostawców
B - suma zapotrzebowań odbiorców m
n

B =∑ b j

A = ∑ ai i =1
j =1

Jeżeli A ≥ B, to zadanie ma rozwiązanie optymalne, w przeciwnym przypadku rozwiązanie optymalne nie istnieje, gdyż zbiór rozwiązań dopuszczalnych jest pusty.
Model matematyczny zadania, zakładając A ≥ B, jest następujący. m
wyznaczyć
n

∑∑ c
min
i =1 j=1
ij
xi j przy następujących ograniczeniach:
Liczba jednostek wywiezionych od i-tego dostawcy nie może przekraczać liczby jednostek materiału, którym dysponuje: m

∑x j=1
ij

≤ ai
i = 1, ..., m
Zapotrzebowania wszystkich odbiorców zostaną zaspokojone. n

∑x i =1
ij

= bj
j = 1, ..., n
Liczby jednostek przewożonego materiału są nieujemne
x i j ≥ 0 i = 1, ..., m, j = 1, ..., n
Zadanie optymalizacyjne (12) - (15) można efektywnie komputerowo rozwiązać algorytmem „out of kilter” zastosowanym do sieci o m+n+1 węzłach oraz m+mn+n+1 łukach.
Przykład 4. Rozwiązanie zadania transportowego.
Cztery budowy są zaopatrywane w cement z dwóch cementowni. Dostawy cementu odbywają się raz na tydzień. W tablicy 2 podano tygodniową podaż cementowni, zapotrzebowania budów [tys. ton] oraz odległości [km] między cementowniami a

2566

Danuta OLĘDZKA , Arkadiusz WĘGLARZ
budowami. Celem jest wyznaczenie planu transportu o minimalnym nakładzie mierzonym iloczynem ton × km.

Cementownia 1
Cementownia 2
Zapotrzebowanie

Budowa 1

Budowa 2

Tablica 2. Dane liczbowe dla przykładu 3
Budowa 3 Budowa 4
Podaż

Model matematyczny zadania w terminach programowania sieciowego: wyznaczyć opływ wartości v = 180 w sieci przedstawionej na rysunku 5, gdzie węzły 2, 3 oznaczają cementownie, węzły 4, 5, 6 - budowy.
Dane liczbowe, wprowadzone do programu komputerowego, przedstawia rysunek 6.

Rys. 5 Schemat sieci przykładu 3

Rys. 6. Dane liczbowe przykładu 3

Rozwiązanie optymalne otrzymane autorskim programem komputerowym: x24* = 60 x26* = 20 x35* = 40 x36* = 15 x37* = 65

KOMPUTEROWE WSPOMAGANIE PLANOWANIA I ORGANIZACJI f* = f(x*) = 3140
6. ROZWIĄZANIE WIELOETAPOWEGO ZADANIA TRANSPORTOWEGO
Algorytm „out of kilter” umożliwia rozwiązanie wielu zadań transportowych, transportowych tym wieloetapowych. Możliwe jest uwzględnienie ograniczonych przepustowości węzłów.
Przykład 5. Rozwiązanie nietypowego zadania transportowego.
Przedsiębiorstwo budowlane ma dwa kamieniołomy: K, K. Materiał dostarczany z kamieniołomów jest kruszony w jednym z dwóch punktów: Z, Z, a następnie przewożony do trzech betonowni: B, B, B. W tablicach 3 i 4 podano odpowiednie odległości [km], dzienną zdolność wytwórczą kamieniołomów (podaż)
[liczba wywrotek] i dzienne zapotrzebowanie budów [liczba wywrotek]. Każdy z punktów kruszenia może przyjąć co najwyżej 20 wywrotek dziennie.
Tablica 3. Dane dla przykładu 5
Z
Z
Podaż
K
K
Tablica 4. Dane dla przykładu 5
B
B

B

Z
Z
Zapotrzebowanie
Rysunek 7 przedstawia dane wprowadzone do programu komputerowego.
Rysunek 8 przedstawia sieć opisującą zadanie; gdzie węzły 2, 3 odpowiadają kamieniołom K, K, węzły 4, 6 odpowiadają zakładowi Z, węzły 5, 7 odpowiadają zakładowi Z, węzły 8, 9, 10 - betonowniom.

Rys.7. Dane liczbowe przykładu 3

2568

Danuta OLĘDZKA , Arkadiusz WĘGLARZ

Rys. 8. Schemat sieci przykładu 4
Rozwiązanie optymalne otrzymane autorskim programem komputerowym: x24* = 20 x35* = 20 x68* = 20 x79* = 10 x710* = 10 f* = f(x*) = 600

5. PODSUMOWANIE
W referacie umieszczono skrótowo wybrane fragmenty materiałów z wykładów i ćwiczeń prowadzonych dla studentów budownictwa dotyczące planowania transportu w warunkach deterministycznych.
6. BIBLIOGRAFIA
[1] Sysło M., Algorytmy optymalizacji dyskretnej, Warszawa, PWN 1995.
[2] Szapiro T., Decyzje menedżerskie z Excelem, Warszawa, PWE 2000.
[3] Lenkiewicz W., Podstawy organizacji i zarządzania w budownictwie, Warszawa, ARKADY 1985.