1. Sympleks

- ograniczenie mniejszościowe ≤ to
, dać je jako bazowe

- ograniczenie większościowe ≥ to
, wyznaczyć inne (np.
oraz
) i dać jako bazowe

- wyrazy wolne (kolumna
) są zawsze dodatnie

- jeżeli brak ograniczenia na
(pisze tylko
) to
, w funkcji celi 1 współczynnik ujemny

a) „Podać i uzasadnić warunek zakończenia obliczeń w algorytmie programowania liniowego”:

Dokonują obrotu kanonicznego, stosuje się kryterium wejścia, określające która zmienna wejdzie do bazy - należy wybrać tą, której wskaźnik optymalności
jest ujemny i najmniejszy. Warunkiem zakończenia obliczeń jest spełnienie kryterium stopu, według którego wszystkie wskaźniki optymalności muszą być nieujemne (
). W takiej sytuacji (gdy spełnione jest to kryterium) nie można znaleźć wierzchołka, który zmniejszyłyby wartość funkcji celu, czyli osiągnięto już jej minimum.

b) „na podstawie tabeli współczynników
uzasadnić wybór elementu głównego
w metodzie programowania liniowego”;

Wykonując obrót kanoniczny dzielimy wiersz z tabeli współczynników
przez wartość elementu głównego
, dlatego:

-
nie może być równe 0, bo nie można dzielić przez 0

-
nie może być ujemne, bo kolumna wyrazów wolnych
też jest zawsze dodatnia (mówi o tym II warunek sympleksowy). Dzieląc dodatnie przez ujemne otrzymałoby się ujemne, a nowo powstały element kolumny
byłby więc ujemny, co jest sprzeczne z II warunkiem sympleksowym.

- ponadto stosunek elementu z kolumny wyrazów wolnych
do elementu głównego
musi być jak najmniejszy (jest to kryterium wyjścia)

Zatem
(jest to I warunek sympleksowy).

Jeżeli zdarzy się tak, że żaden element z kolumny (z tabeli współczynników
) wybranej do bazy nie spełnia warunku
, to funkcja celu maleje nieograniczenie.

2. Warunki Kuhna-Tuckera

Znajduje MIN, więc żeby znaleźć MAX należy zmienić znaki w funkcji celu

a) 1 ograniczenie, Ω wypukłe

- równanie Lagrange'a
gdzie
to ograniczenie, np. jakaś prosta

- warunki K-T:

oraz

- rozpatrzeć 2 przypadki:
(ograniczenia nieaktywne)

(ograniczenia aktywne)

- jeżeli wszystkie warunki są spełnione, to
i
które wyjdą tworzą punkt stacjonarny

- na koniec wstawić wszystkie punkty stacjonarne do funkcji celu
i wybrać MAX

b) kilka ograniczeń, Ω wypukłe

- zmodyfikowane równanie Lagrange'a
, pomijające ograniczenia typu

- warunki K-T:

Oraz

- rozpatrzeć 3 przypadki:
i

- jeżeli wszystkie warunki są spełnione, to
i
które wyjdą tworzą punkt stacjonarny

- na koniec wstawić wszystkie punkty stacjonarne do funkcji celu
i wybrać MAX

c) kilka ograniczeń, Ω niewypukłe

- sprawdzić czy gradienty ograniczeń są zależne liniowo: wypisać ograniczenia
mniejszościowe, obok ich gradienty
czyli macierze 2x1

- jeśli są zależne liniowo, rozwiązanie znajduje się w punkcie nieregularnym

d) ograniczenia różnych typów naraz

- mniejszościowe: są ok

- większościowe: pomnożyć razy -1 aby stały się mniejszościowe

- równościowe: dodatkowa zmienna
, warunek K-T jak dla
i

3. Dualność

Problem pierwotny: Problem dualny:

a) „wykaż dualność”:

- zmodyfikowane równanie Lagrange'a

- warunki K-T:

b) „uzasadnij celowość rozwiązywania problemu dualnego”:

Współzależność rozwiązań zadania pierwotnego i dualnego pozwala na oszczędność czasu obliczeń. Jest to uzasadnione szczególnie wtedy, gdy liczba nierówności ograniczających (np. 5 prostych ograniczających) znacznie różni się od liczby zmiennych decyzyjnych przed dokonaniem bilansowania (2 zmienne,
i
).

c) „korzystając z rozwiązania problemu dualnego wskaż które ograniczenia są aktywne / rozwiąż problem pierwotny”:

- w pierwotnym wyznaczyć macierze
z ograniczeń i funkcji celu

- powstawiać je do dualnego i otrzymać nową funkcje celu
oraz 2 nowe ograniczenia

- sprowadzić do postaci standardowej i policzyć sympleksem, tylko ze w wierszu wskaźników zmieniać znak!

- w otrzymanym rozwiązaniu
też zmienić znak

- wybrać ograniczenia aktywne (ograniczenia pierwotne o tych numerach, jakie mają niezerowe
) i wyznaczyć z nich
.

4. Wolf

„Sprowadź zadanie programowania kwadratowego do zadania programowania liniowego”:

- sprowadź do postaci standardowej, dodając zmienne bilansujące i usuwając nierówności

- macierz
zawiera kwadraty z funkcji celu, np.
. Ma wymiary NxN

- macierz
zawiera elementy liniowe z funkcji celu, np.
. Ma wymiary 1xN

- macierz
zawiera wyrazy wolne ograniczeń. Ma wymiary 1xL

- macierz
zawiera współczynniki ograniczeń. Ma wymiary NxL

- macierz
to transponowana
. Ma wymiary LxN

- macierz
zawiera kwadraty zmiennych bazowych, np.
. Ma wymiary 2xN

- macierz
zawiera zmienne bazowe. Ma wymiary 1x2

- macierz
to macierz jednostkowa razy -1. Ma wymiary NxN

- macierz
zawiera na przekątnej
, czyli 1 lub -1, a gdzie indziej same 0. Wymiary NxN

Jeżeli
to

Jeżeli
to

(
po N,
po 2)