1. Sympleks
- ograniczenie mniejszościowe Ł� to +� x3 , dać je jako bazowe
- ograniczenie większościowe ł� to -� x3 , wyznaczyć inne (np. x1 oraz x2 ) i dać jako bazowe
- wyrazy wolne (kolumna b ) są zawsze dodatnie
ó� ó�ó�
- jeżeli brak ograniczenia na x1 (pisze tylko x2 ł� 0 ) to x1 =� x1 -� x1 , 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 wskaz
nik optymalności c jest ujemny i najmniejszy. Warunkiem zakończenia obliczeń
j
jest spełnienie kryterium stopu, według którego wszystkie wskaz
niki optymalności muszą być nieujemne
( c ł� 0 ). W takiej sytuacji (gdy spełnione jest to kryterium) nie można znalez
ć wierzchołka, który
j
zmniejszyłyby wartość funkcji celu, czyli osiągnięto już jej minimum.
b)  na podstawie tabeli współczynników Bz =� a uzasadnić wybór elementu głównego bpq w
metodzie programowania liniowego ;
Wykonując obrót kanoniczny dzielimy wiersz z tabeli współczynników Bz =� a przez wartość elementu
głównego bpq , dlatego:
- bpq nie może być równe 0, bo nie można dzielić przez 0
- bpq nie może być ujemne, bo kolumna wyrazów wolnych a 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
a byłby więc ujemny, co jest sprzeczne z II warunkiem sympleksowym.
- ponadto stosunek elementu z kolumny wyrazów wolnych a do elementu głównego bpq musi być jak
najmniejszy (jest to kryterium wyjścia)
Zatem bpq >� 0 (jest to I warunek sympleksowy).
Jeżeli zdarzy się tak, że żaden element z kolumny (z tabeli współczynników Bz =� a ) wybranej do bazy nie
spełnia warunku bpq >� 0 , to funkcja celu maleje nieograniczenie.
2. Warunki Kuhna-Tuckera
Znajduje MIN, więc żeby znalez
ć MAX należy zmienić znaki w funkcji celu f (�x)�
a) 1 ograniczenie, W� wypukłe
- równanie Lagrange a L(�x, m�)� =� f (�x)�+� m�(�g(�x)�)� gdzie g(�x)�to ograniczenie, np. jakaś prosta
ś�L
- warunki K-T: =� 0
ś�x1
ś�L
=� 0
ś�x2
ś�L ś�L
Ł� 0 m� =� 0
ś�m� ś�m�
oraz m� ł� 0
- rozpatrzeć 2 przypadki: m� =� 0(ograniczenia nieaktywne)
m� >� 0 (ograniczenia aktywne)
- jeżeli wszystkie warunki są spełnione, to x1 i x2 które wyjdą tworzą punkt stacjonarny x0
- na koniec wstawić wszystkie punkty stacjonarne do funkcji celu f (�x0 )� i wybrać MAX
b) kilka ograniczeń, W� wypukłe
- zmodyfikowane równanie Lagrange a L*(�x, m�)� =� f (�x)�+� m�(�g(�x)�)�, pomijające ograniczenia typu x1 ł� 0
ś�L ś�L
- warunki K-T: ł� 0 x1 =� 0
ś�x1 ś�x1
ś�L ś�L
ł� 0 x2 =� 0
ś�x2 ś�x2
ś�L ś�L
Ł� 0 m� =� 0
ś�m� ś�m�
Oraz x1, x2, m� ł� 0
- rozpatrzeć 3 przypadki: x1 =� 0 i x2 =� 0
x1 =� 0
x2 =� 0
- jeżeli wszystkie warunki są spełnione, to x1 i x2 które wyjdą tworzą punkt stacjonarny x0
- na koniec wstawić wszystkie punkty stacjonarne do funkcji celu f (�x0 )� i wybrać MAX
c) kilka ograniczeń, W� niewypukłe
- sprawdzić czy gradienty ograniczeń są zależne liniowo: wypisać ograniczenia g(�x)� mniejszościowe, obok ich
gradienty �x g(�x)� 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 l� , warunek K-T jak dla x1 i x2
3. Dualność
Problem pierwotny: Problem dualny:
Max Ź� f (�x)� =� cT x Min Ź� f (�x)� =� bT m�
Ax Ł� b AT m� ł� c
x ł� 0 m� ł� 0
a)  wykaż dualność :
- zmodyfikowane równanie Lagrange a
L*(�x, m�)� =� -�cT x +� m�T (�Ax -� b)� L*(�m�, x)� =� bT m� +� xT (�c -� AT m�)�
- warunki K-T:
T
ś�L ć� ś�L ��
ł� 0 �� �� ł� 0
�� ��
ś�x ś�m�
Ł� ł�
T
ś�L ć� ś�L ��
xT =� 0 m�T �� �� =� 0
�� ��
ś�x ś�m�
Ł� ł�
T
ś�L ś�L
ć� ��
Ł� 0 Ł� 0
�� ��
ś�m� ś�x
Ł� ł�
T
ś�L ś�L
m�T =� 0 xT ć� �� =� 0
�� ��
ś�m� ś�x
Ł� ł�
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, x1 i x2 ).
c)  korzystając z rozwiązania problemu dualnego wskaż które ograniczenia są aktywne / rozwiąż problem
pierwotny :
- w pierwotnym wyznaczyć macierze A,b,c z ograniczeń i funkcji celu f (�x)�
- powstawiać je do dualnego i otrzymać nową funkcje celu f (�m�)� oraz 2 nowe ograniczenia
- sprowadzić do postaci standardowej i policzyć sympleksem, tylko ze w wierszu wskaz
ników zmieniać znak!
- w otrzymanym rozwiązaniu f (�m�0 )� =� f (�x0 )� też zmienić znak
- wybrać ograniczenia aktywne (ograniczenia pierwotne o tych numerach, jakie mają niezerowe m� ) i
wyznaczyć z nich x0 .
4. Wolf
 Sprowadz
zadanie programowania kwadratowego do zadania programowania liniowego :
- sprowadz
do postaci standardowej, dodając zmienne bilansujące i usuwając nierówności
- macierz D zawiera kwadraty z funkcji celu, np. x12 . Ma wymiary NxN
- macierz C zawiera elementy liniowe z funkcji celu, np. x1 . Ma wymiary 1xN
- macierz b zawiera wyrazy wolne ograniczeń. Ma wymiary 1xL
- macierz A zawiera współczynniki ograniczeń. Ma wymiary NxL
- macierz AT to transponowana A . Ma wymiary LxN
- macierz DB zawiera kwadraty zmiennych bazowych, np. x3 2 . Ma wymiary 2xN
- macierz xB zawiera zmienne bazowe. Ma wymiary 1x2
- macierz -�1 to macierz jednostkowa razy -1. Ma wymiary NxN
- macierz D� zawiera na przekątnej D�1,D�2,D�3,...,D�n , czyli 1 lub -1, a gdzie indziej same 0. Wymiary NxN
Jeżeli -� c1 -� 2dB1xB >� 0 to D�1 =� 1
Jeżeli -� c2 -� 2dB2xB <� 0 to D�2 =� -�1
x
�� ł�
A 0 0 0 b
�� ł�ę� ś� �� ł�
ę�2D AT -�1 D�ś�ę�l�ś� =� ę�
�� ��ę�m�ś� ��-� cś�
��
ę�
yś�
�� ��
( x, m�, y po N, l� po 2)