Całość zapisana w 3 dokumentach w formacie pdf. Notatka porusza zagadnienia takie jak: programowanie Matematyczne, jakościowe i ilosciowe metody zarządzania, wprowadzenie do Programowania Liniowego, postać kanoniczna i przekształcenia zadania, modele minimaksowe, aproksymacja, zadania Całkowitoliczbowe, źródła całkowitoliczbowości, kresy i oszacowania, wyrażenia logiczne, podstawowa postać zadania, zbiór rozwiązań, przejście od zadania pierwotnego do dualnego PL, rozwiązanie zadania dualnego, algorytm dualny simplex.
6Rozwiązywanie zadań PL6.1Podstawowa postać zadania
Bez utraty ogólności możemy sformułować zadanie LP jako:
n
max
z =
cjxj
(6.1a)
j=1
n
p. o.
aijxj = bi,
i = 1, . . . , m
(6.1b)
j=1
xj
0,
j ∈ 1, . . . , n
(6.1c)
• Zbiór w przestrzeni Rn zadany układem nierówności (6.1b) i (6.1c), nazywamy zbio-rem rozwiązań dopuszczalnych,
• jest wielościanem wypukłym w Rn, zwanym również simpleksem.
• Dalej będzie on nazywany wielościanem ograniczeń.
Bez straty ogólności można przyjąć, że:
• m
n,
• wiersze ai macierzy Am×n są liniowo niezależne, tzn.:
m
αiai = 0
i=1
tylko i wyłącznie wtedy gdy αi = 0 dla każdego i = 1, . . . , m
Gdyby m > n to m − n wierszy byłoby liniowo zależnych, i można byłoby je usunąć zzadania.Liniowo zależne ograniczenia można w siebie przekształcać mnożąc przez stałą, wy-starczy więc pozostawić tylko jedno z nich w zadaniu.6.2Zbiór rozwiązań
Niech F oznacza zbiór rozwiązań dopuszczalnych.Są trzy wzajemnie się wykluczające możliwości
1. ograniczenia są sprzeczne, tzn. zadanie PL nie ma rozwiązań dopuszczalnych,
2. zadanie jest nieograniczone, tzn. istnieją takie wektory x, y ∈ F, że cy > 0 oraz
wektor x + αy ∈ F dla dowolnego α
0, czyli funkcja celu może osiągnąć dowolnie
dużą wartość,
3. istnieje x∗ ∈ F takie, że ∞ > cx∗
cx dla dowolnego x ∈ F. x∗ — rozwiązanieoptymalne.
166.3Macierz i zmienne bazowe
Załóżmy, że kolumny macierzy A zostały uporządkowane w taki sposób, że m pierwszychkolumn jest liniowo niezależnych.
Niech:
A = (B, N)
x = (xB, xN)
gdzie
B
– macierz bazowa, baza zadania PL,
B jest macierzą nieosobliwą o wymiarach m × m,tzn. |B| = 0 oraz istnieje B−1,
xB – zmienne bazowe, odpowiadające kolumnom w B,xN – zmienne niebazowe, odpowiadające kolumnom w N.
n
n!Liczba baz jest skończona
=
m
m!(n − m)!6.4Rozwiązania bazowe
Warunek Ax = b można teraz zapisać BxB + NxN = b stąd
xB = B−1b − B−1NxN
(6.2)
jest to równanie wypukłego stożka, gdzie:
B−1b — wierzchołek stożka,
kolumny B−1N — wektory kierunkowe tworzących stożka.
Jednym z jego rozwiązań jest tzw. rozwiązanie bazowe:
xB = B−1b,
xN = 0
(6.3)
Jeżeli xB
0, to jest to tzw. rozwiązanie bazowe dopuszczalne — punkt ekstremalny
(∼wierzchołek) wielościanu ograniczeń.
Punkt x jest punktem ekstremalnym zbioru F jeżeli nie istnieją x , x ∈ F i α ∈ (0, 1),takie, że x = αx + (1 − α)x
176.5“Bazowa” wartość funkcji celu
Niech c = (cB, cN) stąd:
z = cBxB + cNxN
Wykorzystując (6.2) eliminujemy xB:
z = cBB−1b − cBB−1N − cN xN
(6.4)
z = cBB−1b — wartość funkcji celu z dla rozw. bazowego
(…)
… minimalne, łączne odchylenie to można
zastosować poniższy model:
min
(ui + vi )
(3.10a)
i=1,...,n
p. o. aXi + b + ui − vi = Yi ,
ui , vi 0,
i = 1, . . . , n
i = 1, . . . , n
(3.10b)
(3.10c)
Preferowana w statystyce metoda najmniejszych kwadratów prowadzi do zdania nieliniową
funkcją celu:
min
(u2 + v2 )
(3.11)
i
i
i=1,...,n
Gdyby ktoś chciał zminimalizować maksymalne odchylenie to musiałby zastosować…
… Część I
Programowanie liniowe
1
Programowanie Matematyczne, PM
Ogólna postać zadań PM
maksymalizuj
f(x)
przy ograniczeniach gi (x)
0 i = 1, . . . , m
(1.1a)
(1.1b)
• (1.1a) to funkcja celu, którą chcemy maksymalizować,
• (1.1b) to ograniczenia, czyli warunki jakie musi spełniać rozwiązanie zadania x.
Znaczenie PM
• PM to lingua franca zaawansowanego planowania.
• PM pozwala rozdzielić opis…
…, LP,
Prog. Binarne — wszystkie zmienne przyjmują wartości 0 lub 1, ang. Binary
Prog.,
Prog. Całkowitoliczbowe — wszystkie zmienne przyjmują wartości całkowite,
ang. (General) Integer Programming, IP, Combinatorial Programming,
Prog. Całkowitoliczbowe Mieszane — zmienne całkowite i ciągłe (niecałkowite), ang. Mixed Integer Programming, MIP,
• uniwersalne języki programowania i metody rozwiązywania…
... zobacz całą notatkę
Komentarze użytkowników (0)