MO Moduł 3: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 13: | Linia 13: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|width="500px" valign="top"|[[Grafika:MO_M3_Slajd3.png|thumb|500px]] | |width="500px" valign="top"|[[Grafika:MO_M3_Slajd3.png|thumb|500px]] | ||
|valign="top"| | |valign="top"|Funkcja oceny jest tu liniowa, bo jest oczywiste, że dodanie do niej dowolnej liczby nie zmienia rozważań (zmienia wartość funkcji wyboru w punkcie minimalizującym, która jest oczywiście od tej liczby zależna, ale rozwiązaniem zadania jest punkt minimalizujący, który jest taki sam !). | ||
|} | |} | ||
---- | ---- | ||
| Linia 19: | Linia 19: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|width="500px" valign="top"|[[Grafika:MO_M3_Slajd4.png|thumb|500px]] | |width="500px" valign="top"|[[Grafika:MO_M3_Slajd4.png|thumb|500px]] | ||
|valign="top"| | |valign="top"|Zamiast „przy ograniczeniach” będziemy pisali p.o. | ||
|} | |} | ||
---- | ---- | ||
| Linia 25: | Linia 25: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|width="500px" valign="top"|[[Grafika:MO_M3_Slajd5.png|thumb|500px]] | |width="500px" valign="top"|[[Grafika:MO_M3_Slajd5.png|thumb|500px]] | ||
|valign="top"| | |valign="top"|Z rysunku wynika, że ograniczenie (c) nie jest potrzebne, oraz że zbiór dopuszczalny jest wielokątem. Linie poziomicowe funkcji liniowej to proste, zatem rozwiązanie leży w wierzchołku wielokąta (albo rozwiązań jest wiele i leżą na brzegu wielokąta, gdy poziomice są równoległe do stosownego ograniczenia). | ||
|} | |} | ||
---- | ---- | ||
| Linia 31: | Linia 31: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|width="500px" valign="top"|[[Grafika:MO_M3_Slajd6.png|thumb|500px]] | |width="500px" valign="top"|[[Grafika:MO_M3_Slajd6.png|thumb|500px]] | ||
|valign="top"| | |valign="top"|W przestrzeni zmiennych zadania liniowego optymalizacji | ||
*zbiór dopuszczalny to (hiper)wielościan, | |||
*miejscem geometrycznym stałej wartości funkcji celu jest (hiper)-płaszczyzna, a | |||
*rozwiązanie zadania (o ile istnieje) leży w jego wierzchołku albo rozwiązań jest wiele i leżą na brzegu wielościanu albo na jego ścianie | |||
|} | |} | ||
---- | ---- | ||
| Linia 37: | Linia 42: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|width="500px" valign="top"|[[Grafika:MO_M3_Slajd7.png|thumb|500px]] | |width="500px" valign="top"|[[Grafika:MO_M3_Slajd7.png|thumb|500px]] | ||
|valign="top"| | |valign="top"|Na płaszczyźnie taki algorytm będzie działać, bo każdy wierzchołek ma tylko dwu sąsiadów, ale przy większej liczbie wymiarów będzie to bardzo powolne i nie wiadomo, czy algorytm się nie zapętli. | ||
|} | |} | ||
---- | ---- | ||
| Linia 43: | Linia 48: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|width="500px" valign="top"|[[Grafika:MO_M3_Slajd8.png|thumb|500px]] | |width="500px" valign="top"|[[Grafika:MO_M3_Slajd8.png|thumb|500px]] | ||
|valign="top"| | |valign="top"|W Polsce, nie bardzo wiadomo dlaczego, algorytm Dantziga nazywa się metodą sympleks, simpleksową, a nawet metodą sympleksów. | ||
Używane w matematyce pojęcie sympleksu nie ma nic wspólnego z metodą Simplex. | |||
|} | |} | ||
---- | ---- | ||
| Linia 85: | Linia 92: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|width="500px" valign="top"|[[Grafika:MO_M3_Slajd15.png|thumb|500px]] | |width="500px" valign="top"|[[Grafika:MO_M3_Slajd15.png|thumb|500px]] | ||
|valign="top"| | |valign="top"|Dla równania | ||
<math>Ax = b,</math> | |||
gdzie x jest wektorem n wymiarowym, a b wektorem p wymiarowym, macierzą bazową nazywa się każdą kwadratową nieosobliwą macierz B, którą da się utworzyć z p kolumn macierzy A. | |||
|} | |} | ||
---- | ---- | ||
| Linia 145: | Linia 158: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|width="500px" valign="top"|[[Grafika:MO_M3_Slajd25.png|thumb|500px]] | |width="500px" valign="top"|[[Grafika:MO_M3_Slajd25.png|thumb|500px]] | ||
|valign="top"| | |valign="top"|Główne problemy implementacyjne związane są z szybkością i dokładnością tego algorytmu. Najwięcej kłopotów jest w nim z odwracaniem kolejnych macierzy bazowych. Przypominamy, że numerycznie macierz odwraca się drogą faktoryzacji. | ||
|} | |} | ||
---- | ---- | ||
| Linia 151: | Linia 164: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|width="500px" valign="top"|[[Grafika:MO_M3_Slajd26.png|thumb|500px]] | |width="500px" valign="top"|[[Grafika:MO_M3_Slajd26.png|thumb|500px]] | ||
|valign="top"| | |valign="top"|Uznane pakiety komercyjne zawierające algorytm Simplex to np. CPLEX, MINOS, NAG, AMPL, MATLAB i Mathematica | ||
|} | |} | ||
---- | ---- | ||
Wersja z 11:07, 28 wrz 2006
 |
 |
 |
Funkcja oceny jest tu liniowa, bo jest oczywiste, że dodanie do niej dowolnej liczby nie zmienia rozważań (zmienia wartość funkcji wyboru w punkcie minimalizującym, która jest oczywiście od tej liczby zależna, ale rozwiązaniem zadania jest punkt minimalizujący, który jest taki sam !). |
 |
Zamiast „przy ograniczeniach” będziemy pisali p.o. |
 |
Z rysunku wynika, że ograniczenie (c) nie jest potrzebne, oraz że zbiór dopuszczalny jest wielokątem. Linie poziomicowe funkcji liniowej to proste, zatem rozwiązanie leży w wierzchołku wielokąta (albo rozwiązań jest wiele i leżą na brzegu wielokąta, gdy poziomice są równoległe do stosownego ograniczenia). |
 |
W przestrzeni zmiennych zadania liniowego optymalizacji
|
 |
Na płaszczyźnie taki algorytm będzie działać, bo każdy wierzchołek ma tylko dwu sąsiadów, ale przy większej liczbie wymiarów będzie to bardzo powolne i nie wiadomo, czy algorytm się nie zapętli. |
 |
W Polsce, nie bardzo wiadomo dlaczego, algorytm Dantziga nazywa się metodą sympleks, simpleksową, a nawet metodą sympleksów.
Używane w matematyce pojęcie sympleksu nie ma nic wspólnego z metodą Simplex. |
 |
 |
 |
 |
 |
 |
 |
Dla równania
gdzie x jest wektorem n wymiarowym, a b wektorem p wymiarowym, macierzą bazową nazywa się każdą kwadratową nieosobliwą macierz B, którą da się utworzyć z p kolumn macierzy A. |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Główne problemy implementacyjne związane są z szybkością i dokładnością tego algorytmu. Najwięcej kłopotów jest w nim z odwracaniem kolejnych macierzy bazowych. Przypominamy, że numerycznie macierz odwraca się drogą faktoryzacji. |
 |
Uznane pakiety komercyjne zawierające algorytm Simplex to np. CPLEX, MINOS, NAG, AMPL, MATLAB i Mathematica |
 |
 |
 |
 |
 |
 |
 |
