Powrót - ekonometria

BADANIA OPERACYJNE

1. Programowanie liniowe.

2. Zagadnienia transportowe.

3. Zarządzanie projektami (modele sieciowe).

1. Programowanie liniowe.

Zadanie I - Programowanie produkcji.

Przedsiębiorstwo produkuje dwa wyroby W1 i W2. Należy zaplanować produkcję przedsiębiorstwa w pewnym tygodniu w taki sposób, aby osiągnięty zysk był maksymalny, jeśli wiadomo, że produkcja wyrobów W1 i W2 jest limitowana ograniczonymi zasobami 3 środków produkcji: S1, S2, S3. Zasoby tych środków wynoszą odpowiednio: 18, 20, 24 jednostki. Nakład środka S1 potrzebny do wyprodukowania jednostki wyrobu W1 wynosi 3 jednostki, a na wytworzenie jednostki produktu W2 wynosi jednostkę. Nakłady środka S2 wynoszą odpowiednio: 1 i 2 jednostki, natomiast środka S3: 3 i 2 jednostki.

Zysk uzyskany z produkcji jednostki wyrobu W1wynosi 2 jednostki pieniężne, a z wytworzenia jednostki wyrobu W2 wynosi 3 jednostki pieniężne.

Budujemy model matematyczny zadania.

Środki produkcji	Nakłady jednostkowe		Zasoby środków produkcji
	W1	W2
S1	3	1	18
S2	1	2	20
S3	3	2	24
Zyski jednostkowe	2	3

Zmienne decyzyjne:

x₁, x₂

x₁ – wielkość produkcji W1

x₂ – wielkość produkcji W2

Funkcja celu:

f(x₁, x₂) = 2x₁ + 3x_{2 →} max

Ograniczenia:

Warunki brzegowe:

Rozwiązanie zadania metodą graficzną:

Rysujemy prostą odpowiadającą pierwszemu ograniczeniu.

1.

P1 (6; 0)

P2 (0; 18)

ZADANIE TRANSPORTOWE

Jest to problem opracowania planu przewozu pewnego jednorodnego produktu od m dostawców do n odbiorców.

Kryterium optymalizacji może w tym zadaniu uwzględniać:

a) minimalizację łącznych kosztów transportu,

b) minimalizację odległości,

c) minimalizację czasu trwania transportu.

Zadanie to rozwiązuje się algorytmem transportowym, w którym w pierwszym kroku wyznacza się pierwsze rozwiązanie dopuszczalne, które następne poprawia się w kolejnych iteracjach.

Zajmiemy się wyznaczeniem rozwiązania dopuszczalnego z zadania transportowego:

a) metodą kąta północno-zachodniego,

b) metodą minimalnego elementu macierzy kosztów.

OZNACZENIA:

Danych jest m dostawców i n odbiorców.

Liczby a₁,a₂,…,a_m – są to podaże dostawców.

Liczby b₁,b₂,…,b_n – są to zapotrzebowania odbiorców.

Na początku rozpatrujemy zadanie transportowe zamknięte (zbilansowane).

Musi być spełniony warunek: - suma podaży = suma zapotrzebowania.

Niech x_ij oznacza wielkość produktu przewożoną od i-tego dostawcy do j-tego odbiorcy (jest to zmienna decyzyjna w tym zadaniu).

- macierz wielkości produktu.

c_ij – jednostkowy koszt przewozu produktu od i-tego dostawcy do j-tego odbiorcy.

- macierz kosztów jednostkowych.

Model matematyczny zadania wyznaczenia takiego planu przewozów, aby łączny koszt transportu był najmniejszy:

Funkcja celu -

Ograniczenia:

Typ 1. Suma , i=1,2,…,n (Suma przewozów od i-tego dostawcy do wszystkich odbiorców równa się podaży tego dostawcy).

Typ 2. Suma , j=1,2,…,n (Ilość produktu przewieziona do j-tego odbiorcy od wszystkich dostawców równa się zapotrzebowaniu tego odbiorcy.

Przykład:

Opracować plan przewozu cukru z dwóch hurtowni spożywczych do czterech sklepów zlokalizowanych w różnych miejscowościach. Jednostkowe koszty transportu, wielkości dostaw, zapotrzebowania sklepów podane są w tablicy:

sklepy	S1	S2	S3	S4	ai
hurtownie
H1	5	2	2	6	80
H2	1	5	8	7	80
bj	10	30	50	70	160
					160

(Elementy c_ij znajdują się wewnątrz tabeli).

Sprawdzamy czy zadanie jest zbilansowane.

Model matematyczny:

Ograniczenia typu 1:

x₁₁+ x₁₂+ x₁₃+ x₁₄=80

x₂₁+ x₂₂+ x₂₃+ x₂₄=80

Ograniczenia typu 2:

x₁₁+ x₂₁=10

x₁₂+ x₂₂=30

x₁₃+ x₂₃=50

x₁₄+ x₂₄=70

x_ij≥0.

Algorytm transportowy

Zakładamy, że zadanie transportowe jest zbilansowane, tz.

Krok 1. Wyznaczenie pierwszego rozwiązania dopuszczalnego.

a) Metoda kąta północno-zachodniego.

Przykład:

Należy przewieść pewien produkt o 3 dostawców do 3 odbiorców.

Dane do tego zadania, a więc koszty jednostkowe, podaże dostawców, zapotrzebowania odbiorców podane są w tablicy:

odbiorcy	O1	O2	O3	ai
dostawcy
D1	17	5	6	16
D2	4	14	9	11
D3	3	9	11	23
bj	10	15	25	50

macierz kosztów

Metoda kąta północno-zachodniego polega na wypełnieniu macierzy przewozów rozpoczynając od węzła w lewym górnym rogu tablicy przewozów. Wpisujemy tam wartość minimum a₁b₁ – min(a₁b₁).

Następnie przesuwamy się w prawo lub w dół (w prawo jeśli i-temu dostawcy został produkt, w dół jeśli całą podaż i-tego dostawcy rozdzielono odbiorcom).

odbiorcy	O1	O2	O3	ai
dostawcy
D1	10*	6*		16
D2		9*	2*	11
D3			23*	23
bj	10	15	25	50

Wygenerowaliśmy w ten sposób rozwiązanie dopuszczalne, które składa się z pięciu węzłów bazowych.

W ogólnym przypadku węzłów bazowych powinno być: m+n-1, gdzie

m - liczba dostawców,

n - liczba odbiorców.

W szczególnym przypadku zdarza się, że mamy do czynienia z rozwiązaniem bazowym zdegenerowanym. Zachodzi to wtedy, gdy równocześnie w trakcie wypełniania węzłów przewozami wyzeruje się podaż i zapotrzebowanie. Wtedy należy przyjąć przewóz w węźle bazowym z wartością zero (dowolnie dla dostawcy lub odbiorcy).

b) Metoda minimalnego elementu macierzy kosztów.

Jako węzeł bazowy wybieramy węzeł, w którym macierz kosztów ma najmniejszą wartość.

W przypadku niejednoznaczności wybieramy dowolny taki węzeł. Następnie określamy wielkość przewozu dla znalezionego węzła biorąc pod uwagę minimalną wartość podaży i popytu dla wyznaczonego przez ten węzeł dostawcy i odbiorcy.

Jednocześnie określamy, czy z dalszych rozważań ma być wyeliminowany dostawca, czy odbiorca i określamy przewozy na wyznaczonej linii na poziomie zero. Postępujemy tak aż do wyczerpania wszystkich możliwości.

(Dla jasności przedstawię tok postępowania krok po kroku.)

odbiorcy	O1	O2	O3	ai
dostawcy
D1	17	5	6	16
D2	4	14	9	11
D3	3	9	11	23	najmniejsza wartość w tym węźle
bj	10	15	25	50

Wybieramy minimum (a₃,b₁): 10 i wpisujemy do węzła.

odbiorcy	O1	O2	O3	ai
dostawcy
D1				16
D2				11
D3	10			23
bj	10	15	25	50

Z dalszych rozważań eliminujemy odbiorcę O₁, ponieważ wyczerpaliśmy jego całe zapotrzebowanie.

odbiorcy	O1	O2	O3	ai
dostawcy
D1	17	5	6	16	najmniejsza wartość w tym węźle
D2	4	14	9	11
D3	3	9	11	23
bj	10	15	25	50

Wybieramy minimum (a₁,b₂): 15 i wpisujemy do węzła.

odbiorcy

O1