Pierwszy ma 7 stron i porusza zagadnienia takie jak: programowanie liniowe, programowanie matematyczne, ogólna postać, programowanie nieliniowe, programowanie przy ograniczeniach, jakościowe i ilościowe metody zarządzania, kurtyna algebraiczna, szczegółowy model zadania, wykres, uogólniony model zadania, zapis macierzowy, ogólny model zadania programowania liniowego, postać kanoniczna, przykładowe modele programowania liniowego, ograniczenia elastyczne, ograniczenia sztywne, dopuszczalność rozwiązań, ograniczenia częściowo elastyczne.
Drugi plik ma 8 stron i porusza zagadnienia takie jak: modele minimaksowe, minimax, aproksymacja, programowanie liniowe całkowitoliczbowe, relaksacja liniowa zadania PLC, źródła całkowitoliczbowości, niepodzielności, kresy i oszacowania, wyznaczanie oszacowań, zmienne przełączające, prosta alternatywa ograniczeń, wielokrotna alternatywa ograniczeń, implikacja ograniczeń, wyrażenia logiczne, zmienne dyskretne, reprezentacja binarna zmiennych całkowitoliczbowych, zliczanie.
Trzeci plik ma 10 stron i porusza zagadnienia takie jak: podstawowa postać zadania, zbiór rozwiązań, macierz i zmienne bazowe, rozwiązania bazowe, "bazowa" wartosc funkcji celu, warunki optymalności, algorytm simplex, dodatkowe oznaczenia, przejscie do sąsiedniej bazy, szczegółowy algorytm, rozwiązanie początkowe, szczególne przypadki, tablica simplex, tablica simplex po zmianie bazy, efektywnosc algorytmu simplex, zadanie pierwotne, zadanie dualne, twierdzenie o słabej dualności, algorytm dualny simplex, twierdzenie Dantziga?Ordena.
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 — wekt
(…)
… 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)