Badania operacyjne (wykład), Bad.oper.

McDusty

archive

WPROWADZENIE

Badania operacyjne powstały podczas II wojny światowej w Anglii. Podczas II wojny światowej przy dowództwach większych jednostek utworzono pewne grupy specjalistów z różnych dziedzin nauki (matematyki, fizyki, psychologii itp.), które miały za zadanie opracowanie pewnej strategii związanej z obroną czy z atakiem. Ponieważ w wojsku zadanie takie nazywa się operacją dlatego grupy te nazwano grupami operacyjnymi.

Po wojnie okazało się, że opracowane metody przez te grupy można zastosować w gospodarce zarówno w skali makro jak i mikro.

Badania operacyjne wchodziły najpierw w skład ekonometrii.

W badaniach operacyjnych można wyodrębnić cztery następujące etapy:

Budowa modelu

W tym etapie należy określić cel lub cele działania, wyodrębnić czynniki od których zależy osiągnięcie tego celu. Następnie konstruujemy model matematyczny (postać analityczna modelu). Ze struktury modelu decyzyjnego wynika informacja np. o kosztach czy cenach.

Rozwiązanie modelu, czyli wyznaczenie decyzji optymalnej

W zależności od postaci analitycznej modelu stosujemy odpowiednie metody za pomocą których wyznaczamy decyzję optymalną analizowanego zagadnienia.

Weryfikacja modelu i uzyskanego rozwiązania

Analiza rozwiązania powinna odpowiadać na pytanie jak dalece rozwiązanie zmieni się w toku procesu decyzyjnego w zależności od zmiany niektórych czynników.

Wdrażanie rozwiązania

Sprawdzenie czy teoria pokrywa się z praktyką; przećwiczenie modelu na systemie rzeczywistym.

MATEMATYCZNY MODEL DECYZYJNY

PRZYKŁAD:

Przedsiębiorstwo wytwarza dwa wyroby A i B, używając w tym celu różnych środków produkcji, z których trzy są limitowane. Nakłady limitowanych środków na jednostkę produkcji i limity tych środków podaje tablica w jednostkach umownych.

Środki produkcji	Jednostkowe nakłady		Limity
Środki produkcji		A	Limity	B
I	1	4	24
II	3	1	21
III	1	1	9

Zysk osiągany na wyrobie A wynosi 2 jednostki, a na wyrobie B - 5 jednostek.

Ustalić optymalne rozmiary produkcji poszczególnych wyrobów oraz podać łączny zysk zrealizowany przy optymalnym asortymencie produkcji.

x₁ - ilość produkcji wyroby A

x₂ - ilość produkcji wyrobu B

Pierwsza część modelu - funkcja celu (lub kryterium celu)

z = 2x₁ + 5x₂ → zysk max

Druga część modelu - warunki uboczne (lub równania bilansowe) - dotyczy środków produkcji, które limitują ilość wyrobów

x₁ + 4x₂ ≤ 24

3x₁ + x₂ ≤ 21

x₁ + x₂ ≤ 9

Trzecia część modelu - tzw. warunki brzegowe - dotyczą zmiennych decyzyjnych

x₁, x₂ ≥ 0

W modelu programowania liniowego występują dwie grupy wielkości, a mianowicie:

zmienne decyzyjne - x₁, x₂ - tzn. wielkości, które należy ustalić;
parametry.

KLASYFIKACJA MODELI DECYZYJNYCH

Istnieją trzy kryteria klasyfikacji modeli decyzyjnych:

ze względu na zmienne decyzyjne:

modele liniowe

Jeżeli w modelu wszystkie zmienne decyzyjne są w pierwszej potędze to taki model nazywamy modelem liniowym. Zespół wszystkich metod służących do rozwiązywania modeli liniowych nazywa się programowaniem liniowym.

modele nieliniowe

Jeżeli w modelu choć jedna ze zmiennych jest w innej potędze niż pierwszej to taki model nazywamy modelem nieliniowym. Zbiór metod służących do rozwiązywania modeli nieliniowych nazywamy programowaniem nieliniowym.

ze względu na parametry:

modele stochastyczne

Jeżeli w modelu choć jeden parametr jest niestały i niepewny to taki model nazywamy stochastycznym. Wyróżniamy trzy typy modeli stochastycznych:

modele probabilistyczne

Jeżeli w modelu choć jeden parametr jest zmienną losową o znanym rozkładzie prawdopodobieństwa to taki model nazywamy modelem probabilistycznym. W rozwiązaniu stosuje się rachunek prawdopodobieństwa.

modele statystyczne

Jeżeli w modelu choć jeden parametr jest zmienną losową o nieznanym rozkładzie prawdopodobieństwa to taki model nazywamy statystycznym. Do rozwiązania stosujemy statystykę matematyczną.

modele strategiczne

W tego typu modelach o parametrach wiemy tylko to, że przyjmują wartości z pewnego przedziału, inaczej mówiąc znamy obszar zmienności parametrów. Modelami strategicznymi zajmuje się teoria gier.

Modelami probabilistycznymi i statystycznymi zajmują się takie teorie jak:

teoria masowej obsługi (kolejek, ogonków)
teoria odnowy (odnowienia)
programowanie sieciowe
programowanie dynamiczne.

modele deterministyczne

Model, w którym wszystkie parametry są stałe i znane (pewne) nazywamy modelem deterministycznym.

ze względu na czas:

modele statyczne

Jeżeli model dotyczy jednego okresu (nie zawiera zmiennej czasowej t) to jest to model statyczny.

modele dynamiczne

Gdy model dotyczy kilku okresów (zawiera zmienną czasową t) to jest modelem dynamicznym.

Powyższa klasyfikacja modeli jest nierozłączna (zazębia się), tzn. analizowany przez nas model jest modelem liniowym, deterministycznym i statycznym.

GEOMETRYCZNA METODA ROZWIĄZYWANIA PROGRAMÓW LINIOWYCH

Metodę tę stosujemy w przypadku kiedy model decyzyjny składa się z dwóch lub najwyżej trzech zmiennych decyzyjnych. składa się ona z dwóch etapów:

polega na wyznaczeniu obszaru dopuszczalnych rozwiązań

Aby wyznaczyć obszar dopuszczalnych rozwiązań należy:

wykreślić prostą, której punkty spełniają równanie odpowiadające danej nierówności
rozstrzygnąć, po której stronie prostej znajdują się punkty spełniające daną nierówność

Aby wykreślić prostą należy znaleźć punkty (0, x₁), (0, x₂).

X₁

X₂

Ponieważ wszystkie te nierówności muszą być spełnione jednocześnie więc poszukujemy punktów (obszaru), który spełnia cały ten układ.

Obszarem dopuszczalnych rozwiązań jest wielobok w wierzchołkach ABCD0. Obszar dopuszczalny jest obszarem wypukłym. Z wypukłości obszaru dopuszczalnych rozwiązań wynika, że rozwiązania optymalnego należy poszukiwać wśród wierzchołków tego obszaru, czyli w naszym przypadku są to wierzchołki ABCD0.

poszukujemy rozwiązania optymalnego.

Aby wyznaczyć rozwiązanie optymalne należy wyjść z równania funkcji celu.

Dokonujemy przekształcenia

5x₂ = z - 2x₁ /5 z = 0

x₂ = z/5 - 2/5 x₁

x₂ = -2/5 x₁ → Jest to równanie linii izocelowej (izokwanty) dla zerowej

wartości funkcji celu.

Wiadomo, że przesuwając równolegle tą izokwantę nie zmieniają się parametry (zwiększa się funkcja celu). Jeżeli z dąży do maksimum (zysk) to poszukujemy wierzchołka jak najdalej początku układu. Jeżeli z dąży do minimum (koszt) to poszukujemy wierzchołka jak najbliżej początku układu.

x₁ = 4 x₂ = 5

z = 2*4 + 5*5 = 33 (jednostek)

ODPOWIEDŹ: Aby osiągnąć maksymalny zysk przedsiębiorstwo powinno produkować

4 jednostki wyrobu A oraz 5 jednostek wyrobu B.

OGÓLNY MODEL LINIOWY

Model programowania liniowego może występować w dwóch postaciach, a mianowicie:

w postaci kanonicznej

Jeżeli wszystkie warunki uboczne w modelu są równaniami to taki model nazywamy modelem o postaci kanonicznej.

w postaci standardowej

Gdy wszystkie warunki uboczne są nierównościami typu ≥ albo ≤ to taki model nazywamy modelem o postaci standardowej.

Funkcja celu w modelu decyzyjnym może dążyć do maksimum albo do minimum. Wynika to z zasady o racjonalnym działaniu, która przebiega według dwóch zasad:

osiągnąć maksymalny efekt przy danych środkach
osiągnąć dany efekt przy minimalnych środkach.

Model w postaci standardowej

I z = c₁x₁ + c₂x₂ + ... + c_nx_n → max lub min

II a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≤ b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≤ b₂

............

a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤ b_m

III x₁, x₂, ..., x_n ≥ 0

lub

z = ∑ c_j x_j → max lub min

j = 1

∑ a_ij x_j ≥ b_i i = 1, 2, ..., m

j = 1

x_j ≥ 0 j = 1, 2, ..., n

gdzie c_j, b_i, a_ij dla i = 1, 2, ..., m j = 1, 2, ..., n oznaczają parametry modelu

c_j - współczynnik funkcji celu przy j-tej zmiennej decyzyjnej

b_i - wyraz wolny i-tego warunku ograniczającego

a_ij - współczynnik przy j-tej zmiennej decyzyjnej w i-tym warunku ograniczającym

W ogólnej postaci mamy n zmiennych decyzyjnych i m warunków ubocznych.

W badaniach empirycznych uzyskujemy zawsze model o postaci standardowej, natomiast wszystkie metody programowania liniowego są przystosowane do postaci kanonicznej.

MODEL O POSTACI KANONICZNEJ

I z = c₁x₁ + c₂x₂ + ... + c_nx_n z = ∑ c_j x_j

j = 1

II a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n = b₂n

............ ∑ a_ij x_j ≥ b_i

a_m1x₁ + a_m2x₂ + ... + a_mnx_n = b_mj = 1

III x₁, x₂, ..., x_n ≥ 0 x_j ≥ 0

W jaki sposób zamienić model z postaci standardowej w model o postaci kanonicznej?

W tym celu wprowadzamy do każdej nierówności tzw. zmienną swobodną (uzupełniającą). Dla zmiennych swobodnych zakłada się zerowe wartości funkcji celu. Ponadto zmienne swobodne muszą spełniać warunek brzegowy. Jeżeli warunek uboczny jest nierównością o znaku „≤” to zmienną swobodną wprowadzamy ze znakiem „+”. Natomiast, gdy warunek uboczny jest nierównością o znaku „≥” to zmienną swobodną wprowadzamy ze znakiem „─”. Zmienne swobodne mają interpretację ekonomiczną, przy czym inaczej ich wartość interpretuje się gdy są wprowadzone ze znakiem „+”, tzn. że oznaczają zapasy (rezerwy) tego środka produkcji, w którym występują, a inaczej w przypadku gdy są wprowadzone ze znakiem „─”.

POSTAĆ STANDARDOWA POSTAĆ KANONICZNA

z = 2x₁ + 5x₂ → max z = 2x₁ + 5x₂ + 0x₃ + 0x₄ + 0x₅ → max

x₁ + 4x₂ = 24 x₁ + 4x₂ + x₃ = 24

3x₁ + x₂ = 21 3x₁ + x₂ + x₄ = 21

x₁ + x₂ = 9 x₁ + x₂ + x₅ = 9

x₁, x₂ ≥ 0 x₁, x₂, x₃, x₄, x₅ ≥0

m = 3 n = 2 m = 3 n = 5 n > m

W postaci kanonicznej liczba zmiennych jest większa od ilości równań.

Jeżeli m = n to układ ma dokładnie jedno rozwiązanie - jest to tzw. układ Kramerowski. Nie istnieje tu problem optymalizacji.

Gdy n > m to układ posiada nieskończenie wiele rozwiązań, a więc w tym to przypadku istnieje możliwość wybrania rozwiązania optymalnego.

PODSTAWOWE OKREŚLENIA METODY PROGRAMOWANIA LINIOWEGO (dotyczą postaci kanonicznej modelu)

Rozwiązaniem dopuszczalnym programowania liniowego jest wektor (uporządkowany ciąg liczb) X = [x₁ x₂ ... x_n] spełniający warunki uboczne i brzegowe modelu.

Rozwiązaniem podstawowym (wierzchołkowym lub bazowym) jest rozwiązanie dopuszczalne posiadające nie więcej niż m dodatnich wartości x_j, gdzie m jest liczbą warunków ubocznych. X = (x₁, x₂, ..., x_m, 0, 0, ...,0)

Niezdegenerowanym rozwiązaniem podstawowym nazywamy takie rozwiązanie, które zawiera dokładnie m dodatnich wartości x_j.

Zdegenerowanym rozwiązaniem podstawowym nazywamy takie rozwiązanie, które posiada mniej niż m dodatnich wartości x_j.

Maksymalna liczba rozwiązań podstawowych równa się ilości kombinacji

gdzie n - liczba zmiennych decyzyjnych

m - liczba warunków brzegowych

TWIERDZENIE:

Jeżeli optymalne rozwiązanie programu liniowego istnieje to przynajmniej jedno rozwiązanie podstawowe jest rozwiązaniem optymalnym.

ALGEBRAICZNA METODA ROZWIĄZYWANIA PROGRAMÓW LINIOWYCH

Polega ona na przebadaniu wszystkich rozwiązań podstawowych.

POSTAĆ STANDARDOWA POSTAĆ KANONICZNA

z = 2x₁ + 5x₂ → max z = 2x₁ + 5x₂ + 0x₃ + 0x₄ + 0x₅ → max

x₁ + 4x₂ ≤ 24 x₁ + 4x₂ + x₃ = 24

3x₁ + x₂ ≤ 21 3x₁ + x₂ + x₄ = 21

x₁ + x₂ ≤ 9 x₁ + x₂ + x₅ = 9

x₁, x₂ ≥ 0 x₁, x₂, x₃, x₄, x₅ ≥0

m = 3 n = 2 m = 3 n = 5 n > m

Należy przebadać 10 rozwiązań podstawowych

Zakładamy, że istnieje rozwiązanie podstawowe w postaci następującej x = (x₁, x₂, x₃, 0, 0)

x₁ + 4x₂ + x₃ = 24

3x₁ + x₂ = 21

x₁ + x₂ = 9

x₁ = 6

x₂ = 3

x₃ = 6

z = 2*6 + 5*3 = 27

x = (6, 3, 6, 0, 0)

Zakładamy następującą postać rozwiązań podstawowych x = (x₁, x₂, 0, x₄, 0)

x₁ + 4x₂ = 24

3x₁ + x₂ + x₄ = 21

x₁ + x₂ = 9

x₁ = 4

x₂ = 5

x₄ = 4

z = 2*4 + 5*5 = 33

x = (4, 5, 0, 4, 0)

Zakładamy następującą postać rozwiązań podstawowych x = (x₁, x₂, 0, 0, x₅)

x₁ + 4x₂ = 24

3x₁ + x₂ + x₄ = 21

x₁ + x₂ + x₅ = 9

x₅ = - 12/11

Ponieważ zmienna x₅ nie spełnia warunku brzegowego, wobec powyższego w takiej postaci nie istnieje rozwiązanie podstawowe.

Zakładamy następującą postać rozwiązań podstawowych x = (x₁, 0, x₃, 0, x₅)

x₁ + x₃ = 24

3x₁ = 21

x₁ + x₅ = 9

x₁ = 7

x₃ = 17

x₅ = 2

z = 2*7 = 14

x = (7, 0, 17, 0, 2)

Zakładamy następującą postać rozwiązań podstawowych x = (x₁, 0, 0, x₄, x₅)

x₁ = 24

3x₁ + x₄ = 21

x₁ + x₅ = 9

x₅ = -15

W takiej postaci rozwiązanie podstawowe nie istnieje.

Zakładamy następującą postać rozwiązań podstawowych x = (0, x₂, x₃, x₄, 0)

4x₂ + x₃ = 24

x₂ + x₄ = 21

x₂ = 9

x₃ = -12

W takiej postaci rozwiązanie podstawowe nie istnieje.

Zakładamy następującą postać rozwiązań podstawowych x = (0, x₂, 0, x₄, x₅)

4x₂ = 24

x₂ + x₄ = 21

x₂ + x₅ = 9

x₂ = 6

x₄ = 15

x₅ = 3

z = 5*6 = 30

x = (0, 6, 0, 15, 3)

Zakładamy następującą postać rozwiązań podstawowych x = (0, 0, x₃, x₄, x₅)

x₃ = 24

x₄ = 21

x₅ = 9

z = 0

x = (0, 0, 24, 21, 9)

Zakładamy następującą postać rozwiązań podstawowych x = (0, x₂, x₃, 0, x₅)

4x₂ + x₃ = 24

x₂ = 21

x₂ + x₅ = 9

x₅ = -12

W takiej postaci nie istnieje rozwiązanie podstawowe.

Zakładamy następującą postać rozwiązań podstawowych x = (x₁, 0, x₃, x₄, 0)

x₁ + x₃ = 24

3x₁ + x₄ = 21

x₁ = 9

x₄ = -6

W tej postaci nie istnieje rozwiązanie podstawowe.

Zestawienie wyników

Numer rozwiązania	zmienne	Wartości zmiennych	wartości funkcji celu
1	1, 2, 3	6, 3, 6	27
2	1, 2, 4	4, 5, 4	33
3	1, 2, 5	_	_
4	1, 3, 5	7, 17, 2	14
5	1, 4, 3	_	_
6	2, 3, 4	_	_
7	2, 4, 5	6, 15, 3	30
8	3, 4, 5	24, 21, 9	0
9	2, 3, 5	_	_
10	1, 3, 4	_	_

z_max = 33

x₁ = 4 x₂ = 5

Zakład powinien produkować 4 jednostki wyrobu A oraz 5 jednostek wyrobu B. Ponadto istnieje rezerwa drugiego środka produkcji wynosząca 4 jednostki.

METODA SIMPLEX

Metoda simplex przebiega według następujących etapów:

Musimy znaleźć rozwiązanie podstawowe (wyjściowe) pierwsze.

Istotę tej metody przedstawimy w oparciu o przykład numeryczny.

Załóżmy, że dany jest model, w którym funkcja celu dąży do maksimum

z = 10x₁ + 20x₂ + 15x₃ → max

2x₁ + 3x₂ + 3x₃ ≤ 480

2x₁ + x₂ + 5x₃ ≤ 240

x₁, x₂, x₃ ≥ 0

Powyższy model zamieniamy na postać kanoniczną

z = 10x₁ + 20x₂ + 15x₃ + 0x₄ + 0x₅ → max

2x₁ + 3x₂ + 3x₃ + x₄ = 480

2x₁ + x₂ + 5x₃ + x₅ = 240

x₁, x₂, x₃, x₄, x₅ ≥ 0

W metodzie simplex wybieramy pierwsze rozwiązanie podstawowe w postaci

x = (x₁, x₂, 0, 0, 0)

2x₁ + 3x₂ = 480

2x₁ + x₂ = 240

x₁ = 60

x₂ = 120

x = (60, 120, 0, 0, 0)

z = 10*60 + 20*120 = 3000

Miejsca niezerowe będziemy oznaczali przez „i” a miejsca zerowe oznaczamy przez „j”.

Metoda ta polega na przebadaniu wszystkich miejsc zerowych. Należy w tym celu policzyć pewne wielkości. W metodzie tej istnieje kryterium optymalności.

Badamy czy wprowadzenie zmiennej na miejsce j=3 ulepszy nam rozwiązanie. W tym celu należy obliczyć

∆_j = ∑c_i z_ij - c_j

i∈x

∆_j - kryterium optymalności dla naszego przykładu

c_i - współczynniki z funkcji celu dla zmiennych i-tych

c_j - współczynniki z funkcji celu dla zmiennej j-tej

∆₃ = c₁ z₁₃ + c₂ z₂₃ - c₃

z_ij są to współczynniki kombinacji liniowej, które wyliczamy według wzoru

A_j = ∑A_i z_ij

i∈x

gdzie A_j - wektor współczynników stojących przy zmiennej j-tej;

A_i - wektory współczynników przy zmiennych i-tych.

A₃ = A₁ z₁₃ + A₂ z₂₃

Korzystając z własności działań na wektorach otrzymujemy następujący układ równań:

3 = 2z₁₃ + 3z₂₃

5 = 2z₁₃ + z₂₃

z₁₃ = 3

z₂₃ = -1

∆₃ = 10*3 + 20*(-1) - 15 = -5

Wobec powyższego, tzn. w przypadku gdy z → max, może wystąpić jeden z następujących przypadków:

jeżeli ∆_j ≥ 0 dla j = m+1, m+2, ..., n

to wartość funkcji celu nie może być zwiększona i plan początkowy jest optymalny;

jeżeli ∆_j < 0 dla pewnego „j” i wszystkie odpowiadające temu indeksowi wielkości z_ij ≤ 0 dla i = 1, 2, ..., m

to zadanie nie posiada rozwiązania;

jeżeli ∆_j < 0 dla pewnego „j” i dla każdego „i” co najmniej jedna z liczb z_ij > 0

to rozwiązanie można ulepszyć.

Obliczanie rozwiązania ulepszonego

W tym celu obliczamy (wyznaczamy) θ = x_i / z_ij z_ij > 0

x_i - wartość zmiennych z rozwiązania podstawowego

Następnie obliczamy zmienne nowego rozwiązania według następującego wzoru:

x_i (θ) = x_i - θz_ij

x_j (θ) = θ

Obliczamy θ:

θ = min x₁ / z₁₃

θ = min 60 / 3 = 20

x₁(θ) = 60 -20*3 = 0

x₂(θ) = 120 - 20*(-1) = 140

x₃(θ) = 20

x₄(θ) = 0

x₅(θ) = 0

x₂= (0, 140, 20, 0, 0)

z = 3100

W nowym rozwiązaniu zawsze wyzerowuje się ta zmienna, dla której θ przyjęła wartość minimalną.

Badamy czy wprowadzenie zmiennej na miejsce j=4 ulepszy nam rozwiązanie.

i = 2, 3 j = 4

∆₄ = c₂ z₂₄ + c₃ z₃₄ - c₄

A₄ = A₂ z₂₄ + A₃ z₃₄

1 = 3z₂₄ + 3z₃₄

0 = z₂₄ + 5z₃₄

z₂₃ = 5/12

z₃₄ = - 1/12

∆₄ = 20 * 5/12 + 15 * (-1/12) = 7 1/12 > 0

Ponieważ ∆_j > 0, a więc wprowadzenie zmiennej na miejsce j=4 nie ulepszy nam rozwiązania.

Badamy miejsce j=5

i = 2, 3 j = 5

∆₅ = c₂ z₂₅ + c₃ z₃₅ - c₅

A₅ = A₂ z₂₅ + A₃ z₃₅

0 = 3z₂₅ + 3z₃₅

1 = z₂₅ + 5z₃₅

z₂₅ = -1/4

z₃₅ = ¼

∆₅ = 20 * (-1/4) + 15 * ¼ = -5/4 < 0

Ponieważ ∆₅ < 0 i istnieje jedno z₃₅ > 0 wobec powyższego wprowadzając zmienną na miejsce j=5 ulepszymy rozwiązanie.

Obliczamy θ

θ = x₃/z₃₅

θ = 20/(1/4) = 80

x₁(θ) = 0

x₂(θ) = 140 - 80*(-1/4) = 160

x₃(θ) = 20 - 80*(1/4) = 0

x₄(θ) = 0

x₅(θ) = 80

z_max = 160*15 = 3200

ROZWIĄZYWANIE PROGRAMÓW LINIOWYCH ZA POMOCĄ TABLIC SIMPLEX (algorytmu simplex)

Zmaksymalizować następujący model:

z = 2x₁ + x₂ → max

x₁ + 2x₂ ≤ 18 x₁ + 2x₂ + x₃ = 18

x₁ + x₂ ≤ 10 x₁ + x₂ + x₄ = 10

5x₁ + x2 ≤ 30 5x₁ + x2 + x₅ = 30

x₁ + x₂ ≥ 0 x₁, x₂, x₃, x₄, x₅ ≥ 0

m = 3 n = 2 m = 3 n = 5

x = (x₁, x₂, x₃, x₄, x₅)

W algorytmie simplex za pierwsze rozwiązanie podstawowe (bazowe) przyjmujemy rozwiązanie postaci następującej:

x = (0, 0, x₃, x₄, x₅)

x₃ = 18

x₄ = 10

x₅ = 30

z = 0

Budowa pierwszej tablicy simplex

c_i	Wektory bazy	c_j	2	1	0	0	0	θ 18 10 6
c_i	Wektory bazy			B	A₁	A₂	A₃		A₄	A₅
0	A₃	18	1	2	1	0	0
0	A₄	10	1	1	0	1	0
0	A₅	30	5	1	0	0	1
	z_j	0	0	0	0	0	0
	∆_j	Х	-2	-1	0	0	0

c_i - wartość funkcji celu dla zmiennych bazowych

c_j - wartości funkcji celu dla wszystkich zmiennych występujących w modelu

B - wektor wyrazów wolnych (wartości zmiennych z bazowego rozwiązania podstawowego)

A₁, A₂, A₃, A₄, A₅ - wektory współczynników stojących przy odpowiednich zmiennych decyzyjnych

wektory bazy - wektory odpowiadające indeksom zmiennych wchodzących w skład rozwiązania bazowego

z_j = ∑c_i z_ij

i∈x

Wektory bazy każdej tablicy simplex muszą tworzyć macierz jednostkową. Oznacza to, że na skrzyżowaniu odpowiednich wektorów występuje 1, a pozostałe składowe to 0. Zależność ta powoduje, że wszystkie pozostałe parametry znajdujące się w tablicy są równe współczynnikom kombinacji liniowej z_ij z metody simplex.

Odczytujemy wartość funkcji celu

∆_j = z_j - c_j

Ponieważ ∆_j < 0 a funkcja celu zmierza do maksimum więc plan można ulepszyć. Należy jeszcze sprawdzić czy istnieje choć jedno z_j > 0.

Aby ulepszyć rozwiązanie należy w tym celu ustalić kolumnę i wiersz kluczowy.

Kolumna kluczowa odpowiada minimalnej wartości ∆_j. Oznacza jaką zmienną należy wprowadzić do bazy aby ulepszyć rozwiązanie.

Wiersz kluczowy jest to najmniejszy iloraz wynikający z podzielenia wektora B przez odpowiednie elementy kolumny kluczowej. Odpowiada to w metodzie simplex wartości θ (wektor A₅).

Wiersz kluczowy oznacza, którą ze zmiennych należy usunąć z bazy aby na jej miejsce wprowadzić zmienną z kolumny kluczowej, czyli na miejsce wektora A₅ wprowadzamy wektor A₁.

Na przecięciu wiersza kluczowego z kolumną kluczową znajduje się element rozwiązujący.

Prawo tworzenia tablic simplex oprócz pierwszej:

Dzielimy każdy element wiersza kluczowego przez element rozwiązujący. Otrzymane ilorazy będą odpowiednimi elementami nowego wiersza następnej tablicy simplex.
Wszystkie pozostałe elementy obliczamy według następującego schematu:

EKK * EWK

NE = WE - ______

NE - nowy element

WE - wybrany element

EKK - element kolumny kluczowej

EWK - element wiersza kluczowego

ER - element rozwiązujący

Druga tablica simplex

C_i	wektory bazy	c_j	2	1	0	0	0	θ 6 2/3 5 30
C_i	wektory bazy			B	A₁	A₂	A₃		A₄	A₅
0	A₃	12	0	9/5	1	0	-1/5
0	A₄	4	0	4/5	0	1	-1/5
2	A₁	6	1	1/5	0	0	1/5
	z_j	12	2	2/5	0	0	2/5
	∆_j	Х	0	-3/5	0	0	2/5

Ponieważ ∆_j < 0 i istnieją z_ij > 0 wobec powyższego rozwiązanie można ulepszyć.

Ustalamy kolumnę i wiersz kluczowy

Element rozwiązujący jest równy 4/5

C_i	wektory bazy	c_j	2	1	0	0	0
C_i	wektory bazy			B	A₁	A₂	A₃	A₄	A₅
0	A₃	3	0	0	1	-9/4	¼
1	A₂	5	0	1	0	5/4	- ¼
2	A₁	5	1	0	0	- ¼	¼
	z_j	15	2	1	0	¾	¼
	∆_j	Х	0	0	0	¾	¼

Ponieważ wszystkie ∆_j ≥ 0 wobec powyższego jest to rozwiązanie optymalne

x = (5, 5, 3, 0, 0)

z_max = 15

METODA SZTUCZNEJ BAZY (metoda M)

Metodę tę stosujemy wówczas kiedy warunki uboczne modelu są nierównościami typu „≥” albo równościami.

Kiedy warunki uboczne są „≥”

z = c₁x₁ + c₂x₂ + ... + c_nx_n → min

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≥ b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≥ b₂

...................

a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≥ b_m

x_j ≥ 0 j = 1, 2, ..., n

Aby powyższy model sprowadzić do postaci kanonicznej należy do każdej nierówności wprowadzić zmienną swobodną ze znakiem „-”.

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n - x_n+1 ≥ b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n - x_n+2 ≥ b₂

...................

a_m1x₁ + a_m2x₂ + ... + a_mnx_n - x_n+m ≥ b_m

x₁, x₂, ..., x_n, x_n+1, x_n+2, ..., x_n+m ≥ 0

W tym przypadku istnieje problem zbudowania rozwiązania podstawowego ponieważ wartości zmiennych nie spełniają warunku brzegowego.

Aby zbudować rozwiązanie podstawowe należy do każdego równania wprowadzić zmienną sztuczną, która spełnia warunki brzegowe.

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n - x_n+1 + u₁ ≥ b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n - x_n+2 + u₂ ≥ b₂

...................

a_m1x₁ + a_m2x₂ + ... + a_mnx_n - x_n+m + u_m ≥ b_m

u₁, u₂, ..., u_m ≥ 0

Ale w tym przypadku zmienia się funkcja celu, ma ona postać następującą:

z = c₁x₁ + c₂x₂ + ... + c_nx_n + M(u₁ + u₂ + ... + u_m) → min

M - bardzo duża liczba dodatnia

Zmienne sztuczne nie mają interpretacji ekonomicznej, wprowadzany je tylko w celu rachunkowym.

Jeżeli warunki uboczne są równościami

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n = b₂

...................

a_m1x₁ + a_m2x₂ + ... + a_mnx_n = b_m

x_j ≥ 0 j = 1, 2, ..., n

W tym przypadku nie możemy zbudować rozwiązania bazowego ponieważ wektory bazy nie tworzą macierzy jednostkowej. Dlatego też należy do każdego równania wprowadzić zmienna sztuczną.

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n - x_n+1 + u₁ = b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n - x_n+2 + u₂ = b₂

...................

a_m1x₁ + a_m2x₂ + ... + a_mnx_n - x_n+m + u_m = b_m

TWIERDZENIA dotyczące metody sztucznej bazy:

Jeżeli rozwiązanie wyjściowe ma chociaż jedno rozwiązanie optymalne to jest ono również rozwiązaniem zadania rozszerzonego. Zastosowanie metody simplex do zadania rozszerzonego zapewnia takie rozwiązanie, w którym każda ze zmiennych sztucznych równa się 0.
Jeżeli zadanie wyjściowe nie ma rozwiązania to rozwiązanie zadania rozszerzonego będzie zawierać przynajmniej jedno u_i dodatnie dla i = 1, 2, ..., m.

FORMUŁOWANIE ZAGADNIENIA TRANSPORTOWEGO

MODEL MATEMATYCZNY

Na określonym terenie istnieje n dostawców i każdy z nich dysponuje odpowiednio a_i > 0 (i = 1, 2, ..., n) jednostkami towaru. Jednocześnie istnieje m odbiorców zgłaszających zapotrzebowanie na ten towar w ilości b_j (j = 1, 2, ..., m). przyjmijmy, że są dane jednostkowe koszty transportu c_ij (i = 1, 2, ..., n oraz j = 1, 2, ..., m). Ponadto będziemy zakładali, że suma dostaw jest równa sumie zapotrzebowania

n m

∑a_i = ∑b_j

i=1 j=1

x_ij (i = 1, 2, ...,n oraz j = 1, 2, ..., m) - zmienne decyzyjne, które interpretujemy jako wielkości przewozu od i-tego nadawcy do j-tego odbiorcy.

Przy tych założeniach model matematyczny zadania transportowego postaci kanonicznej można zapisać w następującej postaci:

n m

k = ∑ ∑ c_j x_ij → min

i=1 j=1

∑ x_ij = a_i i = 1, 2, ..., n

i=1

∑ x_ij = b_j j = 1, 2, ..., m

i-1

x_ij ≥ 0 i = 1, 2, ..., n j = 1, 2, ..., m

W zamkniętym zagadnieniu transportowym mamy m^xn zmiennych decyzyjnych oraz m+n warunków ubocznych.

ZAPIS ZAGADNIENIA W POSTACI TABLICY TRANSPORTOWEJ

Punkty nadania (odprawy)	Punkty odbioru	Limity nadania (odprawy)
Punkty nadania (odprawy)		Limity nadania (odprawy)	1 2 ..... m
1 2 .... n	x₁₁ x₁₂ ..... x_1m x₂₁ x₂₂ ..... x_2m ............ x_n1 x_n2 ..... x_nm	a₁ a₂ ..... a_n
zapotrzebowanie	b₁ b₂ ..... b_m	∑b_j = ∑a_i

Ponadto musimy mieć daną macierz kosztów jednostkowych (bezpośrednich) c_ij

┌ ┐

│c₁₁ c₁₂ ..... c_1m│

│c₂₁ c₂₂ ..... c_2m│

c_ij =│................ │

│................ │

│c_n1 c_n2 ..... c_nm│

└ ┘

ALGORYTM ROZWIĄZYWANIA ZAMKNIĘTEGO ZAGADNIENIA TRANSPORTOWEGO

PRZYKŁAD:

Trzy wytwórnie wód gazowanych zapatrują w swój wyrób pięć hurtowni. Zdolności produkcyjne wytwórni wynoszą kolejno: 50, 100, 150 jednostek, a zapotrzebowanie hurtowni kolejno - 25, 115, 60, 30, 70 jednostek. Macierz kosztów jednostkowych oraz przedstawione powyżej parametry zostały ujęte w następującej tablicy transportowej:

wytwórnie	Hurtownie					limity
wytwórnie		1	2	3	4	limity	5
1	10	15	20	20	40	50
2	20	40	15	30	30	100
3	40	35	40	55	25	150
zapotrzebowanie	25	115	60	30	70	300

Ustalić optymalny plan przewozu oraz łączny minimalny koszt transportu.

Aby rozwiązanie podstawowe było niezdegenerowane musi zawierać m+n-1 kratek bazowych

m+n-1 = 7

Algorytm transportowy składa się z trzech etapów:

Polega on na ustaleniu rozwiązania podstawowego.

Znamy dwie metody ustalania planu podstawowego:

metoda lewego górnego rogu (metoda kąta zachodnio-północnego)

Polega na przyporządkowaniu zmiennych wartości liczbowych poczynając od lewego górnego rogu poprzez korektę odpowiednich wartości przesuwamy się po przekątnej do prawego dolnego rogu.

Plan pierwszy ustalony metodą lewego górnego rogu

	1	2	3	4	5
1	25	25				50 25 0
2		90	10			100 10 0
3			50	30	70	150 100 70 0
	25 0	115 90 0	60 50 0	30 0	70 0

k₁ = 10*25 + 15*25 + 40*90 + 15*10 + 40*50 + 55*30 + 25*70

k₁ = 9775 jednostek

metoda minimum macierzy

	1	2	3	4	5
1	²⁵10	²⁵15	20	20	40	50 25 0
2	20	¹⁰40	⁶⁰15	³⁰30	30	100 40 10 0
3	40	⁸⁰35	40	55	⁷⁰25	150 80 0
	25 0	115 90 10 0	60 0	30 0	70 0

Metoda ta polega na znalezieniu macierzy kosztów bezpośrednich najniższego kosztu i wprowadzeniu w tę kratkę odpowiedniego ładunku. Następnie korygujemy odpowiednie wielkości ładunku i wykreślamy wiersz lub kolumnę. Powyższe postępowanie powtarzamy tak długo aż wykreślimy całą macierz kosztów. Ustalony plan pierwszy metodą minimum macierzy jest następujący:

	1	2	3	4	5
1	25	25				50
2		10	60	30		100
3		80			70	150
	25	115	60	30	70

Obliczając całkowite koszty przewozu dokonane według tego planu:

k₁ = 7500 jednostek

Sprawdzamy czy rozwiązanie podstawowe jest optymalne.

W tym celu wychodzimy z jednego z planów ustalonych poprzednimi metodami (dla nas planem wyjściowym będzie plan minimum macierzy). Teraz należy wyznaczyć tablicę kosztów pośrednich, którą oznaczamy przezc_ij.

Istnieją dwie metody wypełniania tablicy kosztów pośrednich:

metoda jednakowych różnic

W kratki bazowe wpisujemy koszty bezpośrednie i bierzemy je w kółkach. Pozostałe miejsca tablicy wypełniamy w sposób następujący:

	1	2	3	4	5
1	10	15	-10	5	5
2	35	40	15	30	30
3	30	35	10	25	25

Uwzględniając koszty w kratkach bazowych ustalamy różnicę między nimi dotyczące kolumn lub wierszy. Ustalona różnica musi być zachowana do końca tablicy.

metoda potencjałów

Polega ona na przyporządkowaniu każdemu punktowi nadania liczby u_i i każdemu punktowi odbioru - v_j. Powyższe oznaczenia muszą spełniać następujący układ równań dla każdej kratki bazowej. Równania te mają postać:

10 = u₁ + v₁

15 = u₁ + v₂

40 = u₂ + v₂

35 = u₃ + v₂

15 = u₂ + v₃

30 = u₂ + v₄

20 = u₃ + v₅

Powyższy układ składa się z siedmiu równań i ośmiu niewiadomych. Można więc nadać jednej ze zmiennych dowolną wartość np. u₁ = 0

u₁ = 0 v₁ = 10

u₂ = 25 v₂ = 15

u₃ = 20 v₃ = -10

v₄ = 5

v₅ = 5

u_i v_j	10	15	-10	5	5
0	10	15	-10	5	5
25	35	40	15	30	30
20	30	35	10	25	25

Następnie obliczamy kryterium optymalności ∆_j =c_ij - c_ij, czyli koszty pośrednie minus koszty bezpośrednie.

	1	2	3	4	5
1	0	0	-30	-15	-35
2	15	0	0	0	0
3	-10	0	-30	-30	0

Jeżeli wszystkie elementy tablicy ∆_j ≤ 0 to kończymy obliczenia przyjmując rozwiązanie podstawowe pierwsze za optymalne.

Jeżeli choć jedna kratka w tablicy ∆_j > 0 (kratka 21 - liczba 15) to rozwiązanie nie jest optymalne. Przechodzimy do etapu trzeciego.

Modyfikacja rozwiązania

W tym etapie korzystamy z metody simplex, która mówi, że do nowego rozwiązania wprowadzamy tę zmienną, dla której ∆_j jest największa. Wprowadzając tę zmienną do bazy musimy inną zmienną z bazy usunąć, a ponadto pociąga to za sobą zmianę wartości innych niektórych zmiennych decyzyjnych. Reguły pozwalające na mechaniczne korygowanie wartości zmiennych są następujące:

W ostatnim planie wytyczamy graf zaczynając od kratki x₂₁ wprowadzając do niej symbol „+” i na zmianę symbol „-”. Przy czym nie wolno jest zmienić kierunku przez pustą kratkę. Ilość ładunku jaką należy przesunąć jest równa najmniejszej liczbie opatrzonej symbolem „-”. W metodzie simplex odpowiada to wartości θ.

Plan drugi:

	1	2	3	4	5
1	15	35				50
2	10		60	30		100
3		80			70	150
	25	115	60	30	70

Przyrost planu obliczamy:

∆_j * θ = 15*10 = 150

k₂ = k₁ - 150 = 7350 jednostek

Aby sprawdzić czy plan drugi jest planem optymalnym należy powtórzyć etap drugi (obliczamy koszty pośrednie).

	1	2	3	4	5
1	10	15	5	20	5
2	20	25	15	30	15
3	30	35	25	40	25

∆_j =c_ij - c_ij

	1	2	3	4	5
1	0	0	-15	0	-35
2	0	-10	0	0	-15
3	-10	0	-15	-15	0

Wobec powyższego plan drugi jest planem optymalnym.

DUALIZM W PROGRAMOWANIU LINIOWYM

Dla każdego zadania decyzyjnego nazwanego zadaniem pierwotnym istnieje pewne inne zadanie decyzyjne nazwane zadaniem dualnym.

Dualizm można rozpatrywać w aspekcie matematycznym i ekonomicznym.

ASPEKT MATEMATYCZNY DUALIZMU

Dany model pierwotny

z = c₁x₁ + c₂x₂ + ... + c_nx_n → max

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≤ b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≤ b₂

..................

a_m1x₁ + a_m2x₂ + ...+ a_mnx_n ≤ b_m

x₁, x₂, ..., x_n ≥ 0

Model dualny

k = b₁y₁ + b₂y₂ + ... + b_my_m → min

a₁₁y₁ + a₂₁y₂ + ... + a_m1y_m ≥ c₁

a₁₂y₁ + a₂₂y₂ + ... + a_m2y_m ≥ c₂

.............

a_1ny₁ + a_2ny₂ + ... + a_mny_m ≥ c_n

y₁, y₂, ..., y_m ≥ 0

Własności modelu dualnego:

Jeżeli w zadaniu pierwotnym chodzi o maksymalizację wartości funkcji celu to w zadaniu dualnym funkcję celu należy minimalizować i odwrotnie.
Liczba zmiennych w zadaniu dualnym jest równa liczbie równań w zadaniu pierwotnym.
Wagi (c_j) funkcji celu zadania pierwotnego są wyrazami wolnymi zadania dualnego.
Wyrazy wolne zadania pierwotnego są wagami funkcji celu zadania dualnego.
Macierz współczynników przy zmiennych decyzyjnych w programie dualnym jest macierzą transponowaną macierzy z programu pierwotnego.
Kierunek nierówności w warunkach ubocznych programu dualnego jest przeciwny.

Pomiędzy tymi programami zachodzą związki matematyczne, które mają istotne znaczenie przy rozwiązywaniu tych programów. Związki matematyczne między programem pierwotnym i dualnym:

Przy dowolnych rozwiązaniach dopuszczalnych programu pierwotnego i dualnego wartość funkcji celu programu pierwotnego nie przewyższa wartości funkcji celu programu dualnego, co można zapisać:

n m

∑ c_jx_j ≤ ∑ b_iy_i

j=1 i=1

Oba programy pierwotny i dualny mają rozwiązania optymalne, są to takie i tylko takie rozwiązania, przy których wartości funkcji celu programów są sobie równe.

Oznaczając przez x_j i y_i rozwiązania optymalne tych programów. Powyższą własność można zapisać następująco:

n m

∑ c_jx_j = ∑ b_iy_i

j=1 i=1

Na to aby wektory x i y były odpowiednio optymalnymi rozwiązaniami swoich programów potrzeba i wystarczy aby spełnione były następujące warunki:

Jeżeli i-ty warunek programu pierwotnego jest w optymalnym rozwiązaniu tego programu spełniony z nierównością to i-ta zmienna w optymalnym rozwiązaniu programu dualnego przyjmuje wartość 0, co można zapisać:

a_i1x₁ + a_i2x₂ + ... + a_inx_n < b_i to y_i = 0

Jeżeli j-ty warunek programu dualnego jest w optymalnym rozwiązaniu tego programu spełniony z nierównością to j-ta zmienna w optymalnym rozwiązaniu programu pierwotnego przyjmuje wartość 0, co można zapisać:

a_1jy₁ + a_2jy₂ + ... + a_mjy_m < c_j to x_j = 0

Jest to tzw. twierdzenie o równowadze.

INTERPRETACJA EKONOMICZNA ZADANIA DUALNEGO

Przyjmijmy, że model pierwotny dotyczy ustalenia programu produkcyjnego maksymalizującego dochód osiągany z produkcji „n” wyrobów. Niech wagi c_j oznaczają cenę j-tego wyrobu, w współczynnik a_ij wielkość zużycia i-tego środka na produkcję jednostki j-tego wyrobu. Wyrazy wolne b_i - zasoby i-tego środka produkcji, a zmienna x_j - wielkość produkcji j-tego wyrobu. Przy tych oznaczeniach zmienne dualne y_i oznaczają cenę i-tego środka produkcji. Wielkość ceny dualnej każdego z zasobów wskazuje o ile wzrośnie maksymalna wartość funkcji celu, gdy wielkość danego zasobu powiększy się o jednostkę. Ceny dualne umożliwiają ujawnienie „wąskich gardeł” wstrzymujących wzrost efektywności produkcji. Ceny te wskazują, które zasoby są bardziej deficytowe (o najwyższych cenach), które są mniej deficytowe i które są niedeficytowe.

Na rynku, w którym panuje konkurencja program dualny powinien rozwiązywać konkurent, który chciałby odkupić środki produkcji od właściciela tych środków. Właściciel tych środków powinien rozwiązywać program pierwotny.

PRZYKŁAD:

Mając dany model pierwotny zbudować program dualny.

z = 2x₁ + 5x₂ → max

x₁ + 4x₂ ≤ 24

3x₁ + x₂ ≤ 21

x₁ + x₂ ≤ 9

x₁, x₂ ≥ 0

Program dualny

k = 24y₁ + 21y₂ + 9y₃ → min

y₁ + 3y₂ + y₃ ≥ 2

4y₁ + y₂ + y₃ ≥ 5

y₁, y₂, y₃ ≥ 0