rozwiazania, FiR, Finanse międzynarodowe

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:

0x01 graphic

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
).