ZADANIA DO ĆWICZEŃ Z PROGRAMOWANIA LINIOWEGO

1. PODSTAWY PROGRAMOWANIA LINIOWEGO (PL):

- wektory, macierze, rachunek macierzowy,

- elementy teorii przestrzeni liniowych,

- bazowe rozwiązanie układu równań liniowych,

- sformułowanie zadania PL,

- graficzne rozwiązywanie zadania PL.

Przykład nr 1

Sprawdzić, z definicji, czy podane zestawy wektorów tworzą bazę w danej przestrzeni:

� a^T = [2 3], b^T = [4 1], c^T = [0 1]

‚ a^T = [2 3 1], b^T = [4 2 0],

� a^T = [1 3 4], b^T = [6 3 0], c^T = [5 0 -4],

„ a^T = [3 -1 3], b^T = [2 2 2], c^T = [4 1 0].

Wskazówki

Tylko ostatni zestaw wektorów tworzy bazę. Dobrym przypomnieniem algebry może być sprawdzanie liniowej niezależności innymi metodami niż z definicji: wyznaczenie rzędu macierzy, obliczenie wyznacznika itp.

Przykład nr 2

Wyznaczyć dowolne, bazowe rozwiązanie podanego układu równań:

2x₁ + 3x₂ – 6x₃ + x₄ = 24

x₁ – 6x₂ – 12x₃ + x₄ = 12

Wskazówki

Kolejne etapy postępowania: wybór dowolnych dwóch kolumn z macierzy A, sprawdzenie ich liniowej niezależności (dowolnym sposobem), wyznaczenie rozwiązania bazowego odpowiadającego wybranym wektorom bazy (rozwiązanie układu dwóch równań z dwiema niewiadomymi).

Rozwiązanie

Przykładowe rozwiązanie, jeżeli przyjmiemy, że najpierw badamy kolumny pierwszą i czwartą macierzy A. Wektor a¹ i wektor a⁴ są liniowo niezależne (można to łatwo sprawdzić), co pozwala wyznaczyć bazowe rozwiązanie układu równań przyjmując zgodnie z definicją x₂=0 oraz x₃=0:

x₁=12

x₂=0

Należy zauważyć, że to szczególne rozwiązanie jest bazowym rozwiązaniem zdegenerowanym.

Przykład nr 3

Na przykładzie typowego zadania programowania liniowego wyjaśnić podstawowe pojęcia, składowe i strukturę zadania programowania liniowego: zmienne decyzyjne (nieujemność), funkcja kryterium (maksymalizacja albo minimalizacja), warunki ograniczające (bilansowe, strukturalne, brzegowe). Wyjaśnić proces uzyskiwania rozwiązania: rozwiązanie dopuszczalne (wielościenny zbiór wypukły), rozwiązanie optymalne (przeszukiwanie zbioru rozwiązań wierzchołkowych).

Wskazówki

Rozwiązań optymalnych może nie być w ogóle (zbiór pusty rozwiązań dopuszczalnych), może nie być skończonego rozwiązania optymalnego (szczególny przypadek, gdy zbiór rozwiązań dopuszczalnych jest nieograniczony), może być jedno rozwiązanie optymalne (wierzchołek), może być nieskończenie wiele rozwiązań optymalnych (liniowa kombinacja wypukła punktów wierzchołkowych optymalizujących wartość funkcji).

Wykorzystując dowolne przykłady zadań PL zastosować graficzną metodę rozwiązywania zadania PL (oczywiście tylko w R²) do zilustrowania przedstawionych wcześniej pojęć i interpretacji. W szczególności należy pokazać co w R² oznacza graficzne poszukiwanie rozwiązania optymalnego na zbiorze rozwiązań dopuszczalnych oraz na czym polega istnienie wielu rozwiązań optymalnych (rozwiązania optymalne na krawędzi zbioru rozwiązań dopuszczalnych).

2. FORMUŁOWANIE LINIOWYCH PROBLEMÓW DECYZYJNYCH (1):

- typowe zagadnienia bilansowe,

- klasyczny problem "diety",

- klasyczny problem "działalności produkcyjnej".

Przykład nr 1

W zakładzie produkcyjnym powstają dwa wyroby: „z” oraz „y”. Wytwarzane są z czterech rodzajów półproduktów: a, b, c, d. Pojedynczy wyrób „z” powstaje z półproduktów użytych w następujących ilościach: 2a, b, 3c, 2d. Pojedynczy wyrób „y” powstaje z półproduktów użytych w następujących ilościach: 2a, 2b, 2c, 3d. Z kolei jednostka półproduktu „c” składa się z: 2a, b. Natomiast jednostka półproduktu „d” składa się z: 2a, 2b.

Zdolności produkcyjne działów, w których powstają półprodukty i wyroby gotowe są limitowane. W dziale A można wytworzyć co najwyżej 1200 półproduktów „a”, w dziale B co najwyżej 1500 półproduktów „b”, w dziale C co najwyżej 500 półproduktów „c”, w dziale D co najwyżej 600 półproduktów „d”. W dziale montażowym E zdolności produkcyjne wynoszą co najwyżej 200 jednostek wyrobów „z” i „y” razem.

W badanym okresie cena wyrobu „z” wynosi 1 denar, a cena wyrobu „y” odpowiednio 1,5 denara. Określić program produkcji, który pozwoli uzyskać maksymalną wartość produkcji wyrobów „z” i „y”.

Wskazówki

Sugeruje się zrealizowanie kolejno następujących poleceń:

1. Naszkicować schemat blokowy procesu produkcyjnego uwzględniający wszystkie działy produkcyjne od A do E.

2. Zbudować macierz bezpośrednich nakładów jednostkowych półproduktów na wytworzenie wyrobów „z” oraz „y”.

3. Zbudować macierz nakładów jednostkowych półproduktów „a” i „b” na wytworzenie półproduktów „c” i „d”, a następnie wynikającą z niej macierz nakładów jednostkowych półproduktów „a” i „b” na wytworzenie wyrobów „z” oraz „y”.

4. Wyznaczyć macierz zagregowanych nakładów jednostkowych „a” i „b” na wytworzenie wyrobów „z” i „y” (działania na macierzach).

5. Określić zmienne decyzyjne zadania.

6. Zbudować zadanie PL z maksymalizacją wartości produkcji (funkcja kryterium oraz warunki ograniczające).

7. Naszkicować graficznie dopuszczalne rozwiązanie zadania, określić rozwiązanie optymalne i zinterpretować je zgodnie z podaną treścią.

Warto zauważyć, że ten przykład czytelnie wyjaśnia na czym polega problem wąskich gardeł w złożonym procesie produkcyjnym („niedopasowanie” zdolności produkcyjnych działów).

Rozwiązanie

x₁ – produkcja wyrobu „z” (sztuk)

x₂ – produkcja wyrobu „y” (sztuk)

funkcja kryterium:

max [ f(x) = x₁ + 1,5x₂ ]

warunki ograniczające:

12x₁ + 12 x₂ £ 1200

8x₁ + 10 x₂ £ 1500

3x₁ + 2x₂ £ 500

2x₁ + 3x₂ £ 600

x₁ + x₂ £ 200

x₁ ³ 0

x₂ ³ 0

rozwiązanie optymalne:

x₁^* = 0

x₂^* = 100

f_max = 150

Przykład nr 2

W pewnym zakładzie (elektrownia, gazownia lub pogotowie ratunkowe) z powodów technologicznych konieczna jest stała obecność pracowników. Ze względu na zmienne natężenie realizowanego procesu liczba niezbędnych pracowników ulega zmianie. Można ją określić dla czterogodzinnych przedziałów czasu w czasie całej doby: godziny 0-4 – co najmniej 4 osoby, godziny 4-8 – co najmniej 18 osób, 8-12 – co najmniej 7, 12-16 – co najmniej 15, 16-20 – co najmniej 18, w przedziale 20-24 – co najmniej 6 osób.

Pracownicy przychodzą do pracy tylko o określonych godzinach (0, 4, 8, 12, 16 lub 20), a po przyjściu pozostają w pracy przez całą zmianę, która trwa równe 8 godzin.

Należy zbudować zadanie PL w celu uzyskania odpowiedzi na pytanie: jaka jest minimalna liczba pracowników niezbędnych do obsługi procesu produkcyjnego w ciągu doby?

Wskazówki

Problem ten, ze względu na strukturę (minimalizowana funkcja kryterium,

zwroty nierówności w warunkach ograniczających), odtwarza schemat klasycznego problemu „diety”.

Po sformułowaniu zadania PL, przedmiotem analizy może być dalsze modyfikowanie zadania w zależności od wydłużania się lub skracania trwania jednej zmiany.

Rozwiązanie

Zdefiniowanie zmiennej decyzyjnej:

x₁ – liczba pracowników rozpoczynających pracę o godzinie 0,

x₂ – liczba pracowników rozpoczynających pracę o godzinie 4,

x₃ – liczba pracowników rozpoczynających pracę o godzinie 8,

x₄ – liczba pracowników rozpoczynających pracę o godzinie 12,

x₅ – liczba pracowników rozpoczynających pracę o godzinie 16,

x₆ – liczba pracowników rozpoczynających pracę o godzinie 20.

Funkcja kryterium:

min [ f(x) = x₁ + x₂ + x₃ + x₄ + x₅ + x₆ ]

warunki ograniczające:

x₁ + x₂ ³ 18

x₂ + x₃ ³ 7

x₃ + x₄ ³ 15

x₄ + x₅ ³ 18

x₅ + x₆ ³ 6

x₆ + x₁ ³ 4

x_j ³ 0; j=1, 2, ..., 6

Rozwiązanie optymalne:

x₁^* = 14

x₂^* = 4

x₃^* = 3

x₄^* = 12

x₅^* = 6

x₆^* = 0

f_min = 39

Przykład nr 3

Samodzielnie zbudować i charakteryzować strukturę typowego zadania działalności produkcyjnej: maksymalizacja funkcji kryterium (dochód, zysk, lub wartość produkcji), ograniczenia (zasobowe limity wyrażone w warunkach ograniczających w postaci nierówności „nie więcej niż”). Przykład powinien być w przyszłości rozwiązany w pracowni komputerowej za pomocą dostępnego pakietu „Decision” lub programu „Excel”.

W tradycyjnym modelu „działalności produkcyjnej” zakłada się, że struktura wytwarzania produktów jest szeregowa (logiczne „i”), co oznacza, że niezerowa zmienna decyzyjna musi sprawić, że zużywane mogą być (w różnych proporcjach) wszystkie wymienione w zadaniu zasoby produkcyjne (czas pracy maszyn lub urządzeń, siła robocza, inne). Nie dzieje się tak, kiedy struktura wytwarzania ma układ równoległy. Przy okazji omawiania modelu „działalności produkcyjnej” wyjaśnić równoległe struktury produkcyjne (logiczne „lub”), które zmuszają do stosowania większej liczby zmiennych decyzyjnych, ewentualnie do wprowadzania podwójnego ich indeksowania. Zwrócić również uwagę na zapis warunków strukturalnych, które wprowadzają relacje proporcjonalności między zmiennymi lub ich kombinacjami.

3. FORMUŁOWANIE LINIOWYCH PROBLEMÓW DECYZYJNYCH (2):

- zadanie typu "rozkroju",

- klasyczne zagadnienie "transportowe",

- wybrane problemy sieciowe.

Przykład nr 1

Proces technologiczny wymaga, żeby do wytworzenia pewnego produktu gotowego wytwarzać trzy rodzaje elementów. Mogą to być elementy drewniane, papierowe ewentualnie metalowe – w każdym razie są wycinane z jednorodnego arkusza danego materiału o ustalonych wymiarach: 5 metrów na 10 metrów. Element pierwszy e1 jest trapezem prostokątnym: podstawa dolna 5 m, podstawa górna 3 m, wysokość 4 m. Drugi element e2 jest prostokątem o wymiarach: 3m x 4m. Trzeci element e3 jest również prostokątem o wymiarach: 2m x 5m. Wiadomo, że należy wytworzyć co najmniej 12000 elementów e1, co najmniej 6000 elementów e2, co najmniej 8000 elementów e3.

Należy zbudować zadanie PL w celu udzielenia odpowiedzi na pytanie: jak rozcinać standardowe arkusze, aby zminimalizować liczbę zużytych arkuszy i wytworzyć wymaganą liczbę wymienionych, trzech elementów?

Wskazówki

Ilość dostępnych arkuszy nie jest istotna dla sformułowania zadania. Problem decyzyjny polega na ustaleniu ile arkuszy rozcinać według każdego ze sprawnych wariantów. Dlatego też, przed sformułowaniem zadania konieczne jest określenie wszystkich, sprawnych (!) wariantów rozcinania pojedynczego arkusza. W tym celu należy rozważyć różne warianty rozmieszczenia na powierzchni arkusza różnych kombinacji różnych ilości elementów e1, e2 oraz e3.

Zmienna decyzyjna może być określona w jednostkach fizycznych (jak podano poniżej), albo jako zmienna o charakterze intensywnościowym – jako krotność, częstość lub ilość powtórzeń danego rodzaju rozkroju. W zadaniu nie ma wymagania minimalizacji ilości odpadów, co może być dodatkowym urozmaiceniem tego przykładu.

Rozwiązanie

Zdefiniowanie zmiennych decyzyjnych:

x_j – liczba standardowych arkuszy rozcinanych zgodnie z wariantem j, przy czym jÎJ, gdzie J to zbiór wszystkich, wyznaczonych uprzednio, wariantów sprawnych;

w tym zadaniu J={1, 2, 3, 4, 5, 6, 7, 8}

funkcja kryterium:

min [ f(x) = x₁ + x₂ + x₃ + x₄ + x₅ + x₆ + x₇ + x₈ ]

warunki ograniczające (uwaga: kolejność numerowania wariantów może być inna, ale kolumn macierzy A, czyli sprawnych wariantów, powinno być w sumie 8 i powinny one występować w kolumnach macierzy A z tymi samymi współczynnikami!):

2x₁ + x₂ + x₃ + x₄ ³ 12000

2x₂ + x₃ + 3x₅ + 2x₆ + x₇ ³ 6000

x₁ + x₃ + 3x₄ + 2x₆ + 3x₇ + 5x₈ ³ 8000

x_j ³ 0, jÎJ

Ten przykład ma alternatywne rozwiązania optymalne. Rozwiązania zadania podano poniżej:

rozwiązanie optymalne nr 1:

x₁^* = 4500

x₂^* = 3000

x₃^* = 0

x₄^* = 0

x₅^* = 0

x₆^* = 0

x₇^* = 0

x₈^* = 700

f_min = 8200

Mając do dyspozycji ostatnia tablicę sympleksową rozwiązanego zadania, można zidentyfikować i wyznaczyć rozwiązania alternatywne:

rozwiązanie optymalne nr 2:

x₁^* = 3800

x₂^* = 3000

x₃^* = 0

x₄^* = 1400

x₅^* = 0

x₆^* = 0

x₇^* = 0

x₈^* = 0

f_min = 8200

rozwiązanie optymalne nr 3:

x₁^* = 5200

x₂^* = 1600

x₃^* = 0

x₄^* = 0

x₅^* = 0

x₆^* = 1400

x₇^* = 0

x₈^* = 0

f_min = 8200

Przykład nr 2

Zbudować i omówić typowe zadanie „diety”. Struktura zadania: minimalizacja funkcji kryterium (koszt całkowity), ograniczenia (zapewnienie minimalnej ilości niezbędnych składników odżywczych, nierówności postaci „co najmniej”). Przykład powinien być w przyszłości rozwiązany w pracowni komputerowej za pomocą dostępnego pakietu „Decision” lub programu „Excel”.

Przykład nr 3

W pewnej sieci komunikacyjnej (pociągi, bity informacji lub przesyłki pocztowe) chcemy przesłać w pewnej jednostce czasu jak najwięcej jednorodnego towaru z punktu 1 do punktu przeznaczenia o numerze 6. Jest w sumie 6 węzłowych punktów tej sieci. Sieć komunikacyjna składa się z następujących połączeń: (1®2), (1®3), (2®3), (2®4), (3®4), (3®5), (4®5), (4®6), (5®6). Strzałki oznaczają jedyny możliwy kierunek przepływu towaru. Zbiór połączeń oznaczamy L.

Każda z tras ma w danym okresie określoną przepustowość, co oznacza, że w analizowanym okresie może nią zostać przesłana ilość towaru nie większa, niż ustalona i podana. Przepustowości „p” dla kolejnych odcinków sieci przedstawiają się następująco: p(1®2)=7, p(1®3)=10, p(2®3)=6, p(2®4)=8, p(3®4)=2, p(3®5)=3, p(4®5)=7, p(4®6)=8, p(5®6)=9.

Należy zbudować zadanie PL, które umożliwi wyznaczenie rozwiązania, które określi: jakie mają być przepływy towarowe na poszczególnych odcinkach sieci, aby zmaksymalizowana została suma towarów przesłanych z punktu początkowego do punktu końcowego?

Wskazówki

Przed przystąpieniem do formułowania zadania PL wykonać graficzną interpretację zadania. W oparciu o graf łatwiej jest określić warunki ograniczające zadania. W ujęciu zagadnienia zgodnym z konwencją maksymalnego przepływu w sieci (maximal flow method) wyklucza się, że towar mógłby zaginąć na trasie lub w węzłach pośrednich sieci. Szuka się odpowiedzi na pytanie: jaki może być największy przepływ towarów, który opuści punkt początkowy i, pomimo ograniczonych przepustowości kolejnych odcinków sieci, dotrze w całości do punktu końcowego?

Rozwiązanie

Zdefiniowanie zmiennej decyzyjnej:

x_ij – ilość towarów przepływających od węzła i-tego do węzła j-tego sieci;

przy czym (i, j) Î L = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6)}

funkcja kryterium:

max [ f(x) = x₁₂ + x₁₃ ]

alternatywnie można również przyjąć:

max [ f(x) = x₄₆ + x₅₆ ]

warunki ograniczające:

x₁₂ £ 7

x₁₃ £ 10

x₂₃ £ 6

x₂₄ £ 8

x₃₄ £ 2

x₃₅ £ 3

x₄₅ £ 7

x₄₆ £ 8

x₅₆ £ 9

x₁₂ – x₂₃ – x₂₄ = 0

x₁₃ + x₂₃ – x₃₄ – x₃₅ = 0

x₂₄ + x₃₄ – x₄₅ – x₄₆ = 0

x₃₅ + x₄₅ – x₅₆ = 0

x_ij ³ 0, (i, j) Î L

Rozwiązanie optymalne:

x₁₂^* = 7

x₁₃^* = 5

x₂₃^* = 0

x₂₄^* = 7

x₃₄^* = 2

x₃₅^* = 3

x₄₅^* = 1

x₄₆^* = 8

x₅₆^* = 4

f_max = 12

4. ZADANIE TRANSPORTOWE:

- pierwsze rozwiązanie dopuszczalne,

- interpretacja wskaźników optymalności rozwiązania bazowego,

- poprawianie uzyskanego rozwiązania,

- schemat blokowy algorytmu,

- niezbilansowane zadanie transportowe,

- zdegenerowane rozwiązanie bazowe,

- problem tras niedopuszczalnych.

Przykład nr 1

Zbudować własne zadanie transportowe (o wymiarze 3x4): macierz nieujemnych, dwuindeksowych zmiennych decyzyjnych, minimalizacja funkcji kryterium (całkowity koszt dostarczenia towarów), macierz współczynników jednostkowego kosztu przewiezienia towaru dla wszystkich tras, dwie grupy warunków ograniczających (nierówności „£” dla „dostawców”, nierówności „³” dla „odbiorców”).

Pokazać, że z powodu liniowej zależności między warunkami ograniczającymi liczba dodatnich wartości zmiennych w rozwiązaniu bazowym (niezdegenerowanym) powinna być równa: n + m – 1, gdzie „n” oznacza liczbę warunków ograniczających opisujących „dostawców”, a „m” liczbę warunków ograniczających opisujących odbiorców. Ponieważ jest to bilans zamknięty, zawsze jeden z warunków daje się przedstawić jako liniowa kombinacja pozostałych.

Przykład nr 2

Cztery magazyny zaopatrują cztery sklepy w jednorodny towar. Każdy z magazynów (M1, M2, M3, M4) ma do rozesłania jednakową liczbę 20 jednostek towaru. Odbiorcy, czyli sklepy, zgłosili zróżnicowane zapotrzebowanie na towar: S1=15, S2=17, S3=21, S4=27.

Macierz C jednostkowych kosztów (c_ij) przewozu towarów podana jest poniżej:

14	16	12	4
13	12	10	5
12	18	10	7
14	15	14	9

Wskazówki

Rozwiązanie tego przykładu jest proste, ponieważ zadanie jest zbilansowane i w trakcie rozwiązywania nie występuje degeneracja rozwiązania bazowego. Pierwsze rozwiązanie dopuszczalne należy wyznaczyć konsekwentnie wybierając najpierw trasy o najniższym koszcie jednostkowym (metoda minimalnego elementu w tablicy kosztów jednostkowych).

Należy zwrócić uwagę na „oryginalny” cykl, który trzeba zbudować w celu uruchomienia przepływu na jedynej (!) trasie wyróżnionej „nieoptymalnym”, ujemnym wskaźnikiem (proponuje się przyjąć w algorytmie, że „–” przy wskaźniku oznacza możliwość znalezienia następnego rozwiązania bazowego zmniejszającego wartość funkcji). Pokazać, że przejście od jednego rozwiązania bazowego do drugiego, dzięki konstrukcji algorytmu, gwarantuje dopuszczalność i „bazowość” następnego rozwiązania.

Podać interpretację wskaźników optymalności. Wyjaśnić, że badane w algorytmie znaki wskaźników pokazują, czy rozwiązanie jest optymalne, natomiast wartość pojedynczego wskaźnika jest jednostkową (przypadającą na jednostkę towaru) miarą zmiany wartości funkcji.

Rozwiązanie

rozwiązanie optymalne, czyli macierz X*:

0	0	0	20
0	12	1	7
0	0	20	0
15	5	0	0

f_min = 754

Przykład nr 3

Podać interpretację i metodę postępowania w następujących przypadkach i zagadnieniach rozszerzających typowe zadanie transportowe:

· zadanie niezbilansowane (dodatkowe wiersze lub kolumny tablicy transportowej),

· degeneracja rozwiązania bazowego (wyjaśnienie i postępowanie w procesie rozwiązywania zadania),

· alternatywne rozwiązanie optymalne,

· skumulowany koszt jednostkowy (uwzględnianie nie tylko kosztu jednostkowego transportu, ale również innych jednostkowych parametrów kosztowych wynikających z charakterystyki dostawców lub odbiorców),

· problem tras niedopuszczalnych (postępowanie w formułowaniu zadania i jego dalszym rozwiązywaniu),

· wieloetapowe zadanie transportowe (na przykład: producent-magazyny-odbiorcy).

5. METODA SYMPLEKS:

- schemat blokowy algorytmu,

- interpretacja uzyskiwanych wyników,

- zmienne sztuczne,

- degeneracja rozwiązania bazowego.

Przykład nr 1

Rozwiązać prosty przykład ograniczony do przestrzeni dwuwymiarowej:

funkcja kryterium:

max [ f(x) = 5x₁ + 25x₂ ]

warunki ograniczające:

2x₁ + x₂ £ 12

2x₁ + 2x₂ £ 20

x₁ ³ 0

x₂ ³ 0

Wskazówki

Omówić przejście od zadania początkowego do zadania rozszerzonego ze zmiennymi pomocniczymi, w tym przypadku dopełniającymi lewą stronę obu nierówności. W algorytmie należy zwrócić uwagę na operacje zmierzające do wymiany w bazie jednego wektora: identyfikacja wektora usuwanego z bazy i wyznaczenie wektora wprowadzanego do bazy.

Należy wyjaśnić w jakiej sytuacji w metodzie sympleks uzyskuje się rozwiązanie optymalne, w jakiej rozwiązanie nieograniczone, a kiedy zadanie nie ma rozwiązania.

Przedstawić graficznie zadanie i pokazać na rysunku na czym polega schemat metody sympleks – badanie optymalności rozwiązania wierzchołkowego i w razie możliwości poprawy rozwiązanie przechodzenie do sąsiedniego wierzchołka zapewniającego większą poprawę wartości funkcji.

Rozwiązanie

rozwiązanie optymalne:

x₁^* = 0

x₂^* = 10

x₃^* = 2

x₄^* = 0

f_max = 250

Przykład nr 2

Rozwiązać dowolny przykład zadania PL ilustrującego problem „działalności produkcyjnej”, a następnie przeanalizować i zinterpretować uzyskany wynik.

Wskazówki

Poniżej podane jest przykładowe zadanie. Ekonomiczny opis problemu sprowadza się do wytwarzania dwóch rodzajów wyrobów (inwencja prowadzącego), które mają określoną cenę zbytu. Są wytwarzane z dwóch rodzajów zasobów (inwencja prowadzącego), których ilość jest ograniczona. Dodatkowo limitowana jest wielkość produkcji obu wyrobów.

max [ f(x) = 3x₁ + 5x₂ ]

3 x₁ + x₂ £ 30

x₁ + 2x₂ £ 20

x₁ + x₂ £ 13

x₁ ³ 0

x₂ ³ 0

rozwiązanie optymalne:

x₁^* = 6

x₂^* = 7

x₃^* = 5

x₄^* = 0

f_max = 53

Rozwiązanie

Interpretujemy uzyskane rozwiązanie:

· maksymalnie możemy uzyskać produkcję o wartości 53 jednostek pieniężnych,

· należy wtedy wytworzyć 6 jednostek wyrobu pierwszego,

· należy wytworzyć również 7 jednostek wyrobu drugiego,

· zasób pierwszy nie zostanie wykorzystany w całości (pozostanie 5 jednostek),

· zasób drugi zostanie wykorzystany w całości (pozostanie 0 jednostek).

Należy przeanalizować na rysunku jaką rolę odegrało ograniczenie wielkości produkcji (trzeci warunek ograniczający)? Jak wyglądałoby rozwiązanie optymalne, gdyby było uzależnione wyłącznie od ograniczeń zasobowych?

Uprzedzając analizę po-optymalną zastanowić się na tym samym rysunku nad wrażliwością rozwiązania optymalnego. Jakie są następstwa dla rozwiązania wynikające ze zmiany cen (pierwszego albo drugiego wyrobu) lub ze zmiany ograniczenia zasobowego (pierwszego albo drugiego zasobu)?

Przykład nr 3

Określić problemy związane z tworzeniem pierwszego, dopuszczalnego rozwiązania bazowego (kiedy nie wystarczają zmienne pomocnicze) oraz interpretację degeneracji rozwiązania bazowego. Przypomnieć na czym polega alternatywne rozwiązanie (zerowe wskaźniki optymalności dla „niebazowych” kolumn/zmiennych w tablicy sympleksowej).

Wskazówki

Rozwiązywanie zadania ze zmiennymi sztucznymi. Należy wskazać sytuacje, w których muszą pojawić się zmienne sztuczne (w konwencji prymalnej metody sympleks) i wyjaśnić jak wpływa to na proces obliczeniowy.

Pokazać, że każde rozwiązanie z niezerową wartością zmiennej sztucznej w bazie jest rozwiązaniem niedopuszczalnym. Dopiero wyeliminowanie zmiennych sztucznych oznacza, że badane rozwiązanie jest już rozwiązaniem wierzchołkowym zbioru rozwiązań dopuszczalnych.

Poniżej pomocniczy przykład:

funkcja kryterium:

min [ f(x) = x₁ + x₂ ]

warunki ograniczające:

2x₁ + x₂ ³ 8

x₁ + 3x₂ ³ 9

x₁ ³ 0

x₂ ³ 0

rozwiązanie optymalne (gdzie zmienne x₅ i x₆ są zmiennymi sztucznymi):

x₁^* = 3

x₂^* = 2

x₃^* = 0

x₄^* = 0

x₅^* = 0

x₆^* = 0

f_min = 5

Wyjaśnić kiedy powstaje degeneracja, jak ją identyfikujemy w tablicy sympleksowej i jakie stwarza problemy dla procesu obliczeniowego?

Szczególnie interesujące, w kontekście przyszłej interpretacji zmiennych dualnych, jest pokazanie, co na rysunku (w przestrzeni dwuwymiarowej) oznacza wystąpienie degeneracji dopuszczalnego rozwiązania bazowego. Poniżej proponowany przykład:

funkcja kryterium:

max [ f(x) = 10x₁ + 4x₂ ]

warunki ograniczające:

x₁ + x₂ £ 8

2x₁ + 4x₂ £ 16

x₁ ³ 0

x₂ ³ 0

rozwiązanie optymalne (w którym mamy mniej niż dwie dodatnie wartości zmiennych):

x₁^* = 8

x₂^* = 0

x₃^* = 0

x₄^* = 0

f_max = 80

6. DUALNOŚĆ I ZMIENNE DUALNE:

- symetryczne i niesymetryczne pary zadań dualnych,

- informacyjna zawartość tablicy sympleksowej,

- interpretacja zmiennych dualnych.

Przykład nr 1

Należy na bardzo różnych przykładach pokazać pary zadań dualnych i ich własności, szczególnie w odniesieniu do zależności występującej między funkcjami kryterium obu zadań. W odniesieniu do pary zadań „symetrycznych” zaleca się zbudowanie tablicy ułatwiającej zapamiętanie, w jaki sposób określić zadanie dualne do podanego (współczynniki funkcji kryterium i prawych stron zamieniają się miejscami, macierz A ulega transpozycji).

Podać analityczne sposoby dostosowywania zadań złożonych do schematu zadań symetrycznych (przekształcenia kierunku optymalizacji, nierówności lub równań występujących w zadaniu pierwotnym). Zapisać ogólną tablicę przejścia od dowolnego zadania pierwotnego do jego postaci dualnej.

Przykład nr 2

Odczytać zawartość tablicy sympleksowej w części związanej z zadaniem dualnym. Może to zrobić korzystając ze znanego przykładu rozwiązanego wcześniej metodą sympleks:

funkcja kryterium:

max [ f(x) = 5x₁ + 25x₂ ]

warunki ograniczające:

2x₁ + x₂ £ 12

2x₁ + 2x₂ £ 20

x₁ ³ 0

x₂ ³ 0

Wskazówki

Zadanie dualne (symetryczne) przedstawia się oczywiście następująco:

funkcja kryterium:

min [ g(y) = 12y₁ + 20y₂ ]

warunki ograniczające:

2y₁ + 2y₂ ³ 5

y₁ + 2y₂ ³ 25

y₁ ³ 0

y₂ ³ 0

Wiersz wskaźników optymalności w ostatniej tablicy sympleksowej (dającej optymalne rozwiązanie zadania pierwotnego) składa się z następujących elementów: a₀₁ = 20, a₀₂ = 0, a₀₃ = 0, a₀₄ = 25/2. Są to zarazem wartości zmiennych dualnych dla rozwiązania optymalnego minimalizującego g(y).

Wartości zmiennych decyzyjnych dla rozwiązania optymalnego zadania dualnego odnajdujemy w kolejnych kolumnach odpowiadających pomocniczym zmiennym zadania pierwotnego, a w kolejnych kolumnach odpowiadających zmiennym decyzyjnym zadania pierwotnego znajdują się w wierszu wskaźnikowym wartości zmiennych pomocniczych zadania dualnego.

Rozwiązanie

Rozwiązanie optymalne zadania dualnego:

y₁^* = 0

y₂^* = 25/2

y₃^* = 20

y₄^* = 0

g_min = 250

Przykład nr 3

W celu podania interpretacji zmiennych dualnych skorzystać z dwóch metod. Po pierwsze, zinterpretować znaczenia zmiennych, które jest w pełni czytelne dla zadania „działalności produkcyjnej” (korzystamy ze sformułowanego i rozwiązanego już zadania – na przykład nr 2 powyżej). Po drugie, wyprowadzić wnioski z definicyjnej zależności f_max = g_min.

Wskazówki

Nadając pełną ekonomiczną interpretację zadaniu pierwotnemu, takiemu jak w powyższym przykładzie nr 2, pokazać, że zadanie dualne polega na minimalizacji kosztu zakupu obu rodzajów zasobów, a warunki ograniczające maja zapewnić minimalny poziom opłacalności produkcji obu rodzaju wyrobów. W takim kontekście i-ta zmienna decyzyjna zadania dualnego jest „ceną” jednostki i-tego zasobu występującego w zadaniu pierwotnym.

Natomiast z zależności f(x)_max = g(y)_min tworzymy następujące rozwinięcie (w tym przypadku dla zadania o dwóch zmiennych decyzyjnych):

f(x)_max = c₁x₁^* + c₂x₂^* = b₁y₁^* + b₂y₂^* = g(y)_min.

Obliczając pochodne cząstkowe, najpierw po b₁, a następnie po b₂ otrzymujemy:

¶f(x)_max /¶b₁ = y₁^* oraz ¶f(x)_max /¶b₂ = y₂^*.

Interpretujemy to w ten sposób, że i-ta zmienna dualna (rozwiązania optymalnego) jest miarą krańcowej produktywności i-tego ograniczenia w zadaniu pierwotnym. Dokładniej: wskazuje jaki będzie marginalny przyrost optymalnej wartości funkcji zadania pierwotnego, jeżeli nastąpi marginalne powiększenie i-tego zasobu o jednostkę.

Zmienne decyzyjne w zadaniu dualnym nazywane są cenami dualnymi, cenami cieniami, cenami umownymi cenami przeliczeniowymi lub wewnętrznymi cenami rozrachunkowymi (funkcjonuje bardzo wiele nazw), ale tak czy inaczej dotyczą ceny jednostki danego zasobu. Umowność tej specyficznej ceny polega na tym, że jest to miarą wewnętrznej (u danego producenta) opłacalności zakupu dodatkowej jednostki zasobu (w naszym przykładzie). Kluczowe jest stwierdzenie, czy „dokupienie” dodatkowej jednostki danego zasobu pozwoli uzyskać przyrost wartości funkcji w zadaniu pierwotnym, który ten zakup zrekompensuje.

Uogólniając powiemy, że i-ta cena dualna wskazuje na wrażliwość wartości funkcji kryterium zadania pierwotnego w reakcji na relaksację i-tego warunku ograniczającego: ¶f(x)_max /¶b_i = y_i^*. Nie zawsze możliwe jest podanie oczywistej i czytelnej interpretacji ekonomicznej zmiennych dualnych, jeżeli zadanie pierwotne nie składa się z uporządkowanych i jednorodnych warunków ograniczających, a zmienne decyzyjne są zdefiniowane w skomplikowany sposób.

7. DUALNOŚĆ I DUALNA METODA SYMPLEKS:

- schemat blokowy metody dualnej,

- interpretacja uzyskiwanych wyników,

- wyznaczanie rozwiązań z warunków Dantziga‑Ordena.

Przykład nr 1

Wyjaśnić na czym polega dualna metoda sympleks i porównać ją z prymalną metodą sympleks zwracając uwagę nie na aspekt obliczeniowy, ale na odmienną logikę procesu poprawiania uzyskiwanych rozwiązań.

Wskazówki

O ile metoda prymalna rozpoczynała się od pierwszego, dopuszczalnego rozwiązania bazowego, to metoda dualna rozpoczyna się od pierwszego niedopuszczalnego rozwiązania bazowego z nieujemnymi wskaźnikami optymalności. Prymalna metoda metodycznie badała sąsiednie wierzchołki zbioru rozwiązań dopuszczalnych, aby zatrzymać się w tym z nich, który daje optymalną wartość funkcji. Metoda dualna „porusza się” po pseudo-wierzchołkach, które leża poza obszarem dopuszczalnym, ale „optymalizują” (nieujemność) wskaźniki optymalności. Algorytm dualny kończy się, gdy nieujemność wskaźników zostaje zachowana, a dane rozwiązanie okazuje się również być rozwiązaniem dopuszczalnym.

Zadania rozwiązywane prymalną metodą ze zmiennymi sztucznymi z reguły można rozwiązać metodą dualną bez wprowadzania zmiennych sztucznych. Metoda dualna jest pomocna przy analizie post-optymalnej zadania PL w odniesieniu do zmian współczynników prawych stron .

Przykład nr 2

Rozwiązać przykładowe zadanie stosując dualna metodę sympleks:

min [ f(x) = x₁ + x₂ ]

2x₁ + x₂ ³ 8

2x₁ + 3x₂ ³ 12

x₁ ³ 0

x₂ ³ 0

Wskazówki

Zamiast stosować metodę prymalną (ze zmiennymi sztucznymi) przekształcamy zadanie mnożąc oba bilansowe warunki ograniczające przez „-1”. Można wówczas określić pierwsze rozwiązanie, które będzie niedopuszczalne (ujemna wartość zmiennych), ale wszystkie wskaźniki optymalności będą dla tego rozwiązania nieujemne. Od niego rozpoczyna się działanie algorytmu.

Rozwiązanie

Rozwiązanie optymalne

x₁^* = 3

x₂^* = 2

x₃^* = 0

x₄^* = 0

f_min = 5

Przykład nr 3

Zastosować podane na wykładzie warunki Dantziga-Ordena i wykorzystać je do wyznaczenia rozwiązania optymalnego zadania dualnego. Porównać je z warunkami komplementarności klasycznych warunków Kuhna-Tuckera zadania programowania nieliniowego.

Wskazówki

Warunki Dantziga-Ordena są specjalnym przypadkiem warunków optymalności, które zostaną podane w ramach wykładu programowania nieliniowego (w zapisie macierzowym). Zapisane dalej warunki są spełnione dla wektorów rozwiązań optymalnych x^* oraz y^*:

y^*T(b – Ax^*) = 0

(y^*TA – c^T)x^* = 0.

W celu ułatwienia wyznaczania rozwiązania zadania dualnego proponuje się wykorzystywać poprzednio rozwiązane zadania. W trakcie zapisywania warunków i ich rozwiązywania należy podkreślać zależność, która łączy i-tą zmienną zadania prymalnego z i-tym warunkiem zadania dualnego oraz j-ty warunek zadania prymalnego z j-tą zmienna zadania dulanego.

Rozwiązanie

Wykorzystać znany przykład:

funkcja kryterium:

max [ f(x) = 5x₁ + 25x₂ ]

warunki ograniczające:

2x₁ + x₂ £ 12

2x₁ + 2x₂ £ 20

x₁ ³ 0

x₂ ³ 0

otrzymujemy następujące warunki D-O:

y₁^*(12 – 2x₁^* – x₂^*) = 0

y₂^*(20 – 2x₁^* – 2x₂^*) = 0

(2y₁^* + 2y₂^* – 5)x₁^* = 0

(y₁^* + 2y₂^* – 25)x₂^* = 0

po podstawieniu x^* i poprawnym wnioskowaniu na temat komplementarnych warunków D-O wyznaczamy ostatecznie rozwiązanie optymalne zadania dualnego:

y₁^* = 0

y₂^* = 25/2

g_min = 250

8. ANALIZA POST-OPTYMALNA:

- zmiana współczynników funkcji kryterium,

- zastosowanie metody sympleks,

- zmiana prawych stron warunków ograniczających,

- zastosowanie dualnej metody sympleks.

Przykład nr 1

Stosując prosty i rozwiązany już metodą sympleks przykład określić konsekwencje zmian współczynników funkcji kryterium i współczynników prawych stron tworzących zadanie PL.

Wskazówki

Zmiana współczynników funkcji kryterium nie wymaga ponownego rozwiązania przykładu, ponieważ wprowadzenie zmiany w ostatniej tablicy sympleksowej pozwala sprawdzić czy zachowana została optymalność uzyskanego wcześniej rozwiązania (nieujemność wskaźników optymalności). Gdyby optymalność została utracona, to należy zastosować metodę sympleks do uzyskania nowego rozwiązania optymalnego.

Zmiana współczynników prawych stron również nie wymaga rozwiązywania przykładu od początku, ale pociąga za sobą konieczność wyznaczenia macierzy przejścia (znajduje się ona w tych kolumnach macierzy A, które w pierwszej tablicy tworzyły macierz jednostkową). Dzięki macierzy przejścia obliczamy nowy, przekształcony wektor prawych stron, a więc mamy możność ustalić, czy została zachowana dopuszczalność uzyskanego wcześniej rozwiązania optymalnego. Gdyby dopuszczalność został utracona, to należy zastosować dualna metodę sympleks w celu uzyskania nowego rozwiązania optymalnego.

Przykład nr 2

Na prostym przykładzie zadania PL należy przeprowadzić analizę post-optymalną wyznaczając przedziały zmienności współczynników funkcji kryterium, a następnie współczynników prawych stron.

Wskazówki

Dla współczynników funkcji kryterium rozwiązuje się odpowiednie nierówności wynikające z warunku nieujemności wskaźników optymalności. Nierówności buduje się tyle, ile jest wskaźników optymalności z uwikłanym, badanym współczynnikiem funkcji kryterium.

Dla współczynników prawych stron buduje się nierówności, które mają zapewnić nieujemność elementów przekształconego w tablicy sympleksowej nowego wektora prawych stron. Przekształcenia wektora identyfikujemy odtwarzając operacje elementarne dokonywane w celu uzyskania rozwiązania optymalnego. Nierówności do zbadania będzie tyle, ile z nich zawiera badany współczynnik prawej strony.

Uwaga: na tym elementarnym poziomie analizy możemy tylko badać skutki zmiany jednego współczynnika, a więc przy założeniu, że pozostałe nie ulegają tymczasem zmianie. Analiza zmiany współczynników macierzy A nie jest zalecana z powodu ograniczonych możliwości przejrzystego przedstawienia tego problemu.

Przykład nr 3

Wyjaśnić zasady konstrukcji, sposobu postępowania i wykorzystania wyników w sytuacji, gdy do zadania PL wprowadzamy parametr o dającym się z góry przewidzieć przedziale zmienności.

Wskazówki

Zadanie z parametrem można rozwiązywać metodą sympleks z rozbudowana tablicą sympleksową, a efektem końcowym jest określenie jakim wartościom parametru odpowiada szczególne rozwiązanie optymalne (wektor zmiennych decyzyjnych i optymalna wartość funkcji).

9. PAKIET KOMPUTEROWY „DECISION”

(zajęcia nr 1 w pracowni komputerowej):

- algorytm transportowy,

- problem przydziału,

- algorytm sympleks,

- analiza postoptymalna.

10. PAKIET KOMPUTEROWY „DECISION”

(zajęcia nr 2 w pracowni komputerowej):

- programowanie całkowitoliczbowe,

- programowanie wielokryterialne,

- wybrane problemy sieciowe.