Programowanie liniowe - Linear programming

Obrazowa reprezentacja prostego programu liniowego z dwiema zmiennymi i sześcioma nierównościami. Zbiór możliwych rozwiązań jest przedstawiony na żółto i tworzy wielokąt , dwuwymiarowy politop . Liniowa funkcja kosztu jest reprezentowana przez czerwoną linię i strzałkę: Czerwona linia to zestaw poziomów funkcji kosztu, a strzałka wskazuje kierunek, w którym optymalizujemy.

Zamknięty obszar dopuszczalny problemu z trzema zmiennymi jest wielościanem wypukłym . Powierzchnie dające stałą wartość funkcji celu są płaszczyznami (nie pokazano). Problem programowania liniowego polega na znalezieniu punktu na wielościanie, który znajduje się na płaszczyźnie o największej możliwej wartości.

Programowanie liniowe ( LP , zwane również optymalizacją liniową ) to metoda pozwalająca na osiągnięcie najlepszego wyniku (takiego jak maksymalny zysk lub najniższy koszt) w modelu matematycznym, którego wymagania są reprezentowane przez zależności liniowe . Programowanie liniowe to szczególny przypadek programowania matematycznego (znanego również jako optymalizacja matematyczna ).

Bardziej formalnie, programowanie liniowe jest techniką dla optymalizacji o liniowej funkcji celu , z zastrzeżeniem równości liniowego i liniowych nierówności ograniczeń . Jest możliwe, obszar jest Polytope wypukły , który to zespół definiuje się jako przecięcie skończenie wielu półprzestrzeni , z których każdy jest zdefiniowany przez nierówności liniowej. Jego celem jest funkcją rzeczywistego -valued afiniczne (liniowy) Funkcja określona w tej bryły. Algorytm programowania liniowego znajduje w politopie punkt, w którym ta funkcja ma najmniejszą (lub największą) wartość, jeśli taki punkt istnieje.

Programy liniowe to problemy, które można wyrazić w formie kanonicznej jako:

${\ Displaystyle {\ zacząć {wyrównany} i {\ tekst {Znajdź wektor}} i \ mathbf {x} \ \ & {\ tekst {który maksymalizuje}} i & \ mathbf {c} ^ {T} \ mathbf {x } \\&{\text{z zastrzeżeniem}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{i}}&&\mathbf {x} \geq \mathbf {0} .\ koniec{wyrównany}}}$

Tutaj składowe x są zmiennymi do określenia, c i b są danymi wektorami (ze wskazaniem, że współczynniki c są używane jako macierz jednowierszowa w celu utworzenia iloczynu macierzy), a A jest daną macierzą . Funkcja, której wartość ma zostać zmaksymalizowana lub zminimalizowana ( w tym przypadku) nazywana jest funkcją celu . Nierówności A x  ≤  b i x ≥ 0 są ograniczeniami, które określają wypukły politop, na którym ma być optymalizowana funkcja celu. W tym kontekście dwa wektory są porównywalne, gdy mają te same wymiary. Jeśli każdy wpis w pierwszym jest mniejszy lub równy odpowiadającemu wpisowi w drugim, to można powiedzieć, że pierwszy wektor jest mniejszy lub równy drugiemu wektorowi. ${\ Displaystyle \ mathbf {c} ^ {T}}$${\ Displaystyle \ mathbf {x} \ mapsto \ mathbf {c} ^ {T} \ mathbf {x}}$

Programowanie liniowe może być stosowane na różnych kierunkach studiów. Jest szeroko stosowany w matematyce, w mniejszym stopniu w biznesie, ekonomii i niektórych problemach inżynierskich. Branże wykorzystujące modele programowania liniowego obejmują transport, energetykę, telekomunikację i produkcję. Okazał się przydatny w modelowaniu różnego rodzaju problemów w planowaniu , wyznaczaniu tras , harmonogramowaniu , przydzielaniu i projektowaniu.

Historia

Leonid Kantorowicz

Jana von Neumanna

Problem rozwiązywania układu nierówności liniowych sięga co najmniej od Fouriera , który w 1827 r. opublikował metodę ich rozwiązywania i od którego pochodzi nazwa metody eliminacji Fouriera-Motzkina .

W 1939 r. sformułowanie problemu programowania liniowego, który jest równoważny z ogólnym problemem programowania liniowego, podał sowiecki matematyk i ekonomista Leonid Kantorowicz , który również zaproponował metodę jego rozwiązania. W ten sposób rozwinął w czasie II wojny światowej planowanie wydatków i zwrotów w celu obniżenia kosztów wojska i zwiększenia strat nałożonych na wroga. Dzieło Kantorowicza było początkowo zaniedbane w ZSRR . Mniej więcej w tym samym czasie co Kantorovich, holendersko-amerykański ekonomista TC Koopmans sformułował klasyczne problemy ekonomiczne jako programy liniowe. Kantorovich i Koopmans podzielili później nagrodę Nobla w dziedzinie ekonomii z 1975 roku . W 1941 roku Frank Lauren Hitchcock sformułował również problemy transportowe jako programy liniowe i podał rozwiązanie bardzo podobne do późniejszej metody simplex . Hitchcock zmarł w 1957 roku, a nagroda Nobla nie jest przyznawana pośmiertnie.

W latach 1946-1947 George B. Dantzig niezależnie opracował ogólną formułę programowania liniowego do wykorzystania w problemach planowania w US Air Force. W 1947 r. Dantzig wynalazł również metodę simpleks, która po raz pierwszy skutecznie rozwiązała problem programowania liniowego w większości przypadków. Kiedy Dantzig zaaranżował spotkanie z Johnem von Neumannem, aby omówić jego metodę simpleks, Neumann natychmiast domyślił się teorii dualności , zdając sobie sprawę, że problem, nad którym pracował w teorii gier, jest równoważny. Dantzig dostarczył formalnego dowodu w niepublikowanym raporcie „Twierdzenie o nierównościach liniowych” z 5 stycznia 1948 r. Praca Dantziga została udostępniona opinii publicznej w 1951 r. W latach powojennych wiele branż stosowało je w swoim codziennym planowaniu.

Pierwotnym przykładem Dantziga było znalezienie najlepszego przydziału 70 osób do 70 miejsc pracy. Moc obliczeniowa wymagana do przetestowania wszystkich permutacji w celu wybrania najlepszego przypisania jest ogromna; liczba możliwych konfiguracji przewyższa liczbę cząstek w obserwowalnym wszechświecie . Jednak znalezienie optymalnego rozwiązania zajmuje tylko chwilę, przedstawiając problem jako program liniowy i stosując algorytm simpleks . Teoria stojąca za programowaniem liniowym drastycznie zmniejsza liczbę możliwych rozwiązań, które należy sprawdzić.

Leonid Khachiyan po raz pierwszy wykazał, że problem programowania liniowego można rozwiązać w czasie wielomianowym w 1979 roku, ale większy teoretyczny i praktyczny przełom w tej dziedzinie nastąpił w 1984 roku, kiedy Narendra Karmarkar wprowadził nową metodę punktu wewnętrznego do rozwiązywania problemów programowania liniowego.

Zastosowania

Programowanie liniowe jest szeroko stosowaną dziedziną optymalizacji z kilku powodów. Wiele praktycznych problemów w badaniach operacyjnych można wyrazić jako problemy programowania liniowego. Pewne szczególne przypadki programowania liniowego, takie jak problemy z przepływem sieciowym i problemy z przepływem wielu towarów , są uważane za wystarczająco ważne, aby wygenerować wiele badań nad wyspecjalizowanymi algorytmami ich rozwiązywania. Szereg algorytmów dla innych typów problemów optymalizacyjnych działa poprzez rozwiązywanie problemów LP jako podproblemów. Historycznie, idee programowania liniowego zainspirowały wiele głównych koncepcji teorii optymalizacji, takich jak dualność, dekompozycja oraz znaczenie wypukłości i jej uogólnień. Podobnie programowanie liniowe było intensywnie wykorzystywane we wczesnym tworzeniu mikroekonomii i jest obecnie wykorzystywane w zarządzaniu przedsiębiorstwem, takim jak planowanie, produkcja, transport, technologia i inne zagadnienia. Chociaż kwestie nowoczesnego zarządzania ciągle się zmieniają, większość firm chciałaby maksymalizować zyski i minimalizować koszty przy ograniczonych zasobach. Google używa programowania liniowego do stabilizacji filmów z YouTube. Dlatego wiele zagadnień można scharakteryzować jako problemy programowania liniowego.

Forma standardowa

Postać standardowa jest zwykłą i najbardziej intuicyjną formą opisu problemu programowania liniowego. Składa się z następujących trzech części:

• Funkcja liniowa do maksymalizacji

np ${\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}}$

• Ograniczenia problemowe o następującej postaci

np

${\ Displaystyle {\ zacząć {macierz} a_ {11} x_ {1} + a_ {12} x_ {2} i \ Leq b_ {1} \ \ a_ {21} x_ {1} + a_ {22} x_ { 2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{macierz}}}$

• Zmienne nieujemne

np

${\ Displaystyle {\ zacząć {macierz} x_ {1} \ geq 0 \ \ x {2} \ geq 0 \ koniec {macierz}}}$

Problem jest zwykle wyrażany w postaci macierzowej , a następnie staje się:

${\ Displaystyle \ max \ {\ \ mathbf {c} ^ {\ operatorname {T}} \ mathbf {x} \ mid \ mathbf {x} \ w \ mathbb {R} ^ {n} \ ziemia A \ mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}}$

Inne formy, takie jak problemy minimalizacji, problemy z ograniczeniami dotyczącymi form alternatywnych, a także problemy dotyczące zmiennych ujemnych, zawsze można przepisać na równoważny problem w postaci standardowej.

Przykład

Załóżmy, że rolnik posiada kawałek ziemi rolniczych, powiedzmy l km ² , które mają być obsadzone zarówno pszenicy lub jęczmienia lub jakiejś kombinacji obu. Rolnik ma ograniczoną ilość nawozu, kilogramów F i pestycydów, kilogramów P. Każdy kilometr kwadratowy pszenicy wymaga kilogramów F ₁ nawozu i kilogramów pestycydów P ₁ , podczas gdy każdy kilometr kwadratowy jęczmienia wymaga kilogramów F ₂ nawozu i kilogramów pestycydu P ₂ . Niech S ₁ będzie ceną sprzedaży pszenicy na kilometr kwadratowy, a S ₂ będzie ceną sprzedaży jęczmienia. Jeżeli powierzchnię ziemi obsadzonej pszenicą i jęczmieniem oznaczymy odpowiednio przez x ₁ i x ₂ , to zysk można maksymalizować wybierając optymalne wartości dla x ₁ i x ₂ . Problem ten można wyrazić następującym problemem programowania liniowego w postaci standardowej:

Wyolbrzymiać: ${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(maksymalizacja przychodów – przychody to „funkcja celu”)
Z zastrzeżeniem:	${\displaystyle x_{1}+x_{2}\leq L}$	(limit całkowitej powierzchni)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}$	(limit nawozu)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}$	(limit pestycydów)
	${\displaystyle x_{1}\geq 0,x_{2}\geq 0}$	(nie można zasadzić obszaru ujemnego).

W formie macierzowej staje się to:

Wyolbrzymiać ${\displaystyle {\rozpocznij{bmatrix}S_{1}&S_{2}\koniec{bmatrix}}{\rozpocznij {bmatrix}x_{1}\\x_{2}\koniec {bmatrix}}}$

podlega ${\ Displaystyle {\ zacząć {bmatrix} 1 i 1 \ \ F_ {1} i F_ {2} \ \ P_ {1} i P_ {2} \ koniec {bmatrix}} {\ zacząć {bmatrix} x_ {1} \ \ x_ { 2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end {bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.}$

Forma rozszerzona (forma luźna)

Problemy programowania liniowego mogą być przekształcone do postaci rozszerzonej w celu zastosowania wspólnej postaci algorytmu simpleks . Ta forma wprowadza nieujemne zmienne typu luz w celu zastąpienia nierówności równościami w ograniczeniach. Problemy można następnie zapisać w następującej postaci macierzy blokowej :

Maksymalizuj :${\displaystyle z}$

${\ Displaystyle {\ zacząć {bmatrix} 1 i - \ mathbf {c} ^ {T} i 0 \ \ 0 i \ mathbf {A} i \ mathbf {ja} \ koniec {bmatrix}} {\ zacząć {bmatrix} z ​​\\ \mathbf {x} \\\mathbf {s} \end{bmacierz}}={\begin{bmacierz}0\\\mathbf {b} \end{bmacierz}}}$

${\ Displaystyle \ mathbf {x} \ geq 0 \ mathbf {s} \ geq 0}$

gdzie są nowo wprowadzone zmienne luzu, są zmiennymi decyzyjnymi i jest zmienną do maksymalizacji. ${\displaystyle \mathbf {s}}$${\displaystyle \mathbf {x}}$${\displaystyle z}$

Przykład

Powyższy przykład został przekształcony w następującą postać rozszerzoną:

Wyolbrzymiać: ${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(funkcja celu)
z zastrzeżeniem:	${\displaystyle x_{1}+x_{2}+x_{3}=L}$	(rozszerzone ograniczenie)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F}$	(rozszerzone ograniczenie)
	${\ Displaystyle P_ {1} \ cdot x_ {1} + P_ {2} \ cdot x_ {2} + x_ {5} = P}$	(rozszerzone ograniczenie)
	${\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.}$

gdzie są (nieujemne) zmienne luzu, reprezentujące w tym przykładzie niewykorzystany obszar, ilość niewykorzystanego nawozu i ilość niewykorzystanego pestycydu. ${\displaystyle x_{3},x_{4},x_{5}}$

W formie macierzowej staje się to:

Maksymalizuj :${\displaystyle z}$

${\displaystyle {\zaczynać{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&1&0&0\\0&F_{1}&F_ {2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\ end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={ \begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{ 4}\\x_{5}\end{bmatrix}}\geq 0.}$

Dwoistość

Każdy problem programowania liniowego, określany jako problem pierwotny , może zostać przekształcony w problem dualny , który zapewnia górną granicę optymalnej wartości problemu pierwotnego. W postaci macierzowej możemy wyrazić problem pierwotny jako:

Maksymalizuj c ^T x z zastrzeżeniem A x ≤ b , x ≥ 0;

z odpowiednim symetrycznym problemem dualnym,

Zminimalizuj b ^T y z zastrzeżeniem A ^T y ≥ c , y ≥ 0.

Alternatywną formułą pierwotną jest:

Maksymalizuj c ^T x z zastrzeżeniem A x ≤ b ;

z odpowiednim asymetrycznym problemem dualnym,

Zminimalizuj b ^T y z zastrzeżeniem A ^T y = c , y ≥ 0.

Istnieją dwie idee fundamentalne dla teorii dualności. Jednym z nich jest fakt, że (dla symetrycznego duala) dualem dualnego programu liniowego jest pierwotny pierwotny program liniowy. Dodatkowo każde możliwe rozwiązanie dla programu liniowego wyznacza granicę optymalnej wartości funkcji celu jego dualności. Twierdzenie o słabej dwoistości mówi, że wartość funkcji celu liczby dualnej w dowolnym możliwym rozwiązaniu jest zawsze większa lub równa wartości funkcji celu liczby pierwotnej w dowolnym możliwym rozwiązaniu. Twierdzenie o silnej dualności mówi, że jeśli liczba podstawowa ma optymalne rozwiązanie, x ^* , to układ dualny również ma optymalne rozwiązanie, y ^* , i c ^T x ^* = b ^T y ^* .

Program liniowy może być również nieograniczony lub niewykonalny. Teoria dualności mówi nam, że jeśli liczba podstawowa jest nieograniczona, to dualność jest niewykonalna przez twierdzenie o słabej dualności. Podobnie, jeśli liczba dualna jest nieograniczona, to element pierwotny musi być niewykonalny. Jednak możliwe jest, aby zarówno dualność, jak i pierwotna były niewykonalne. Zobacz podwójny program liniowy, aby uzyskać szczegółowe informacje i kilka innych przykładów.

Wariacje

Dwoistości krycia/pakowania

Obejmujące PR jest liniowy program w postaci:

Zminimalizuj: b ^T y ,

z zastrzeżeniem: A ^T y ≥ c , y ≥ 0 ,

tak, że macierz A i wektory b i c są nieujemne.

Dualem pokrywającego LP jest pakujący LP , liniowy program postaci:

Maksymalizacja: C ^T x ,

z zastrzeżeniem: A x ≤ b , x ≥ 0 ,

tak, że macierz A i wektory b i c są nieujemne.

Przykłady

Pokrywanie i pakowanie LPs zwykle powstają jako rozluźnienie programowania liniowego problemu kombinatorycznego i są ważne w badaniu algorytmów aproksymacyjnych . Na przykład, złagodzenie LP o zadanej problemu pakowania , z niezależnym problemu zadanej , a problemu z dopasowaniem pakują LPS. Na złagodzenie LP z problemem zestaw pokrywy , z problemem tytułowej wierzchołek oraz ustawionej wyróżniającym się problemem są również pokrycie LPS.

Znalezienie ułamkową zabarwienie o wykresie jest kolejnym przykładem przykrywającej LP. W tym przypadku istnieje jedno ograniczenie dla każdego wierzchołka wykresu i jedna zmienna dla każdego niezależnego zestawu wykresu.

luz uzupełniający

Możliwe jest uzyskanie optymalnego rozwiązania liczby podwójnej, gdy znane jest tylko optymalne rozwiązanie liczby pierwotnej przy użyciu komplementarnego twierdzenia o luzie. Twierdzenie mówi:

Załóżmy, że x  = ( x ₁ ,  x ₂ , ... ,  x _n ) jest pierwotnie wykonalne i że y  = ( y ₁ ,  y ₂ , ... ,  y _m ) jest podwójnie wykonalne. Niech ( w ₁ ,  w ₂ , ...,  w _m ) oznaczają odpowiednie zmienne pierwotne luzu, a ( z ₁ ,  z ₂ , ... ,  z _n ) oznaczają odpowiadające im zmienne o podwójnym luzie. Wtedy x i y są optymalne dla ich odpowiednich problemów wtedy i tylko wtedy, gdy

• x _j z _j  = 0, dla j  = 1, 2, ... ,  n , i
• w _i y _i  = 0, dla i  = 1, 2, ... ,  m .

Więc jeśli i -ta zmienna luzu liczby podstawowej nie jest równa zeru, to i -ta zmienna liczby dualnej jest równa zeru. Podobnie, jeśli j -ta zmienna luzu liczby dualnej nie jest równa zeru, to j -ta zmienna liczby podstawowej jest równa zeru.

Ten konieczny warunek optymalności wyraża dość prostą zasadę ekonomiczną. W standardowej formie (przy maksymalizacji), jeśli w ograniczonym zasobie pierwotnym jest luz (tj. są „resztki”), dodatkowe ilości tego zasobu nie mogą mieć żadnej wartości. Podobnie, jeśli występuje luka w wymogach ograniczenia nieujemności ceny podwójnej (ukrytej), tj. cena nie jest równa zeru, wówczas musi być ograniczona podaż (brak „resztek”).

Teoria

Istnienie optymalnych rozwiązań

Geometrycznie ograniczenia liniowe definiują obszar dopuszczalny , który jest wielościanem wypukłym . Funkcja liniowa jest funkcją wypukłą , co oznacza, że ​​każde minimum lokalne jest minimum globalnym ; podobnie funkcja liniowa jest funkcją wklęsłą , co oznacza, że ​​każde maksimum lokalne jest maksimum globalnym .

Optymalne rozwiązanie nie musi istnieć z dwóch powodów. Po pierwsze, jeśli ograniczenia są niespójne, to nie istnieje rozwiązanie możliwe do zrealizowania: Na przykład ograniczenia x  ≥ 2 i x  ≤ 1 nie mogą być spełnione łącznie; w tym przypadku mówimy, że LP jest niewykonalne . Po drugie, gdy politop jest nieograniczony w kierunku gradientu funkcji celu (gdzie gradient funkcji celu jest wektorem współczynników funkcji celu), wówczas nie zostanie osiągnięta optymalna wartość, ponieważ zawsze jest to możliwe lepsze niż jakakolwiek skończona wartość funkcji celu.

Optymalne wierzchołki (i promienie) wielościanów

W przeciwnym razie, jeśli istnieje rozwiązanie dopuszczalne i jeśli zbiór więzów jest ograniczony, to na granicy zbioru więzów zawsze osiągana jest wartość optymalna przez zasadę maksimum dla funkcji wypukłych (alternatywnie przez zasadę minimum dla funkcji wklęsłych ), ponieważ liniowa funkcje są zarówno wypukłe, jak i wklęsłe. Jednak niektóre problemy mają odrębne optymalne rozwiązania; na przykład problem ze znalezieniem możliwego rozwiązania układu nierówności liniowych jest problemem programowania liniowego, w którym funkcją celu jest funkcja zerowa (to znaczy stała funkcja przyjmująca wszędzie wartość zero). W przypadku tego problemu wykonalności z funkcją zerową dla funkcji celu, jeśli istnieją dwa różne rozwiązania, to każda wypukła kombinacja rozwiązań jest rozwiązaniem.

Wierzchołki politopu nazywane są również podstawowymi możliwymi rozwiązaniami . Powód takiego wyboru nazwy jest następujący. Niech d oznacza liczbę zmiennych. Wtedy podstawowe twierdzenie o nierównościach liniowych implikuje (dla możliwych problemów), że dla każdego wierzchołka x ^* możliwego obszaru LP istnieje zestaw ograniczeń nierówności d (lub mniej) z LP, tak że gdy traktujemy te ograniczenia d jako równości, unikalnym rozwiązaniem jest x ^* . W ten sposób możemy badać te wierzchołki, patrząc na pewne podzbiory zbioru wszystkich ograniczeń (zbiór dyskretny), a nie na kontinuum rozwiązań LP. Ta zasada leży u podstaw algorytmu simpleks rozwiązywania programów liniowych.

Algorytmy

W problemie programowania liniowego, seria ograniczeń liniowych tworzy wypukły, dopuszczalny obszar możliwych wartości dla tych zmiennych. W przypadku dwóch zmiennych obszar ten ma kształt wypukłego wielokąta prostego .

Algorytmy wymiany baz

Algorytm simpleksowy Dantzig

Simplex algorytm , opracowany przez George Gdańska 1947 rozwiązuje LP problemy konstruowania rozwiązanie dopuszczalne w wierzchołku Polytope a następnie idzie wzdłuż ścieżki na krawędziach Polytope na wierzchołki bez zmniejszania wartości funkcji celu dopóki na pewno osiągnięto optymalne. W wielu praktycznych problemach pojawia się „ przeciąganie ”: wykonuje się wiele punktów obrotu bez zwiększania funkcji celu. W rzadkich praktycznych problemach zwykłe wersje algorytmu simpleks mogą faktycznie „cyklować”. Aby uniknąć cykli, naukowcy opracowali nowe zasady obrotu.

W praktyce algorytm simpleks jest dość wydajny i można zagwarantować, że znajdzie globalne optimum, jeśli zostaną podjęte pewne środki ostrożności zapobiegające jeździe rowerem . Udowodniono, że algorytm simpleks skutecznie rozwiązuje problemy „losowe”, tj. w sześciennej liczbie kroków, co jest podobne do jego zachowania w przypadku problemów praktycznych.

Jednak algorytm simpleks ma słabe zachowanie w najgorszym przypadku: Klee i Minty skonstruowali rodzinę problemów programowania liniowego, dla których metoda simpleks wykonuje szereg kroków wykładniczych w rozmiarze problemu. W rzeczywistości przez pewien czas nie było wiadomo, czy problem programowania liniowego jest rozwiązywalny w czasie wielomianowym , czyli w klasie złożoności P .

Algorytm krzyżowy

Podobnie jak algorytm simpleks Dantziga, algorytm krzyżowy jest algorytmem wymiany baz, który obraca się między bazami. Algorytm krzyżowy nie musi jednak zachowywać wykonalności, ale może raczej zmieniać się od wykonalnej podstawy do niewykonalnej podstawy. Algorytm krzyżowy nie ma wielomianowej złożoności czasowej dla programowania liniowego. Oba algorytmy odwiedzić wszystkie 2 ^D narożniki (zaburzony) kostki w wymiarze  D , na kostce Klee-Minty , w najgorszym przypadku .

Punkt wewnętrzny

W przeciwieństwie do algorytmu simpleks, który znajduje optymalne rozwiązanie poprzez przechodzenie krawędzi między wierzchołkami na zbiorze wielościennym, metody punktów wewnętrznych poruszają się po wnętrzu obszaru dopuszczalnego.

Algorytm elipsoidalny, zgodnie z Khachiyan

Jest to pierwszy najgorszy przypadek algorytmu czasu wielomianowego , jaki kiedykolwiek znaleziono dla programowania liniowego. Aby rozwiązać problem, który ma n zmiennych i może być zakodowany w L bitach wejściowych, ten algorytm działa w czasie. Leonid Khachiyan rozwiązał ten długotrwały problem złożoności w 1979 roku, wprowadzając metodę elipsoidy . Analiza zbieżności ma poprzedników (w liczbach rzeczywistych), w szczególności metody iteracyjne opracowane przez Nauma Z. Shora oraz algorytmy aproksymacyjne Arkadi Nemirovskiego i D. Yudina. ${\ Displaystyle O (n ^ {6} L)}$

Algorytm projekcyjny Karmarkara

Algorytm Chaczijana miał przełomowe znaczenie dla ustalenia możliwości rozwiązywania programów liniowych w czasie wielomianowym. Algorytm nie stanowił przełomu obliczeniowego, ponieważ metoda simpleks jest bardziej wydajna dla wszystkich poza specjalnie skonstruowanymi rodzinami programów liniowych.

Jednak algorytm Khachiyan zainspirował nowe kierunki badań w programowaniu liniowym. W 1984 roku N. Karmarkar zaproponował metodę projekcyjną programowania liniowego. Algorytm Karmarkara poprawił się na najgorszym przypadku wiązania wielomianowego Chaczijana (dawanie ). Karmarkar twierdził, że jego algorytm był znacznie szybszy w praktycznym LP niż metoda simplex, co wywołało duże zainteresowanie metodami punktów wewnętrznych. Od czasu odkrycia Karmarkara zaproponowano i przeanalizowano wiele metod punktu wewnętrznego. ${\ Displaystyle O (n ^ {3,5} L)}$

87 algorytm Vaidyi

W 1987 roku Vaidya zaproponował algorytm działający w czasie. ${\ Displaystyle O (n ^ {3})}$

Algorytm Vaidyi 89

W 1989 Vaidya opracował algorytm działający w czasie. Formalnie rzecz biorąc, algorytm wykonuje operacje arytmetyczne w najgorszym przypadku, gdzie to liczba ograniczeń, to liczba zmiennych, a to liczba bitów. ${\ Displaystyle O (n ^ {2,5})}$${\ Displaystyle O ((n + d) ^ {1,5} nL)}$${\displaystyle d}$${\ Displaystyle n}$${\ Displaystyle L}$

Wprowadź algorytmy czasu rzadkości

W 2015 roku Lee i Sidford pokazali, że można go rozwiązać w czasie, gdzie reprezentuje liczbę elementów niezerowych, a w najgorszym przypadku nadal przyjmuje . ${\ Displaystyle {\ tylda {O}} ((nnz (A) + d ^ {2}) {\ sqrt {d}} L)}$${\displaystyle nnz(A)}$${\ Displaystyle O (n ^ {2,5} L)}$

Aktualny algorytm mnożenia macierzy

W 2019 r. Cohen, Lee i Song poprawiali od czasu do czasu czas działania, jest wykładnikiem mnożenia macierzy i jest podwójnym wykładnikiem mnożenia macierzy . jest (z grubsza) definiowana jako największa liczba, taka, że ​​można pomnożyć macierz przez macierz w czasie. W dalszej pracy Lee, Song i Zhang odwzorowują ten sam wynik inną metodą. Te dwa algorytmy pozostają, gdy i . Wynik dzięki Jiangowi, Songowi, Weinsteinowi i Zhangowi poprawił się do . ${\ Displaystyle {\ tylda {O}} ((n ^ {\ omega} + n ^ {2,5-\ alfa/2} + n ^ {2 + 1/6}) L)}$${\ Displaystyle \ omega}$${\ Displaystyle \ alfa}$${\ Displaystyle \ alfa}$${\displaystyle n\razy n}$${\ Displaystyle n \ razy n ^ {\ alfa}}$${\ Displaystyle O (n ^ {2})}$${\ Displaystyle {\ tylda {O}} (n ^ {2 + 1/6} L)}$${\ Displaystyle \ omega = 2}$${\ Displaystyle \ alfa =1}$${\ Displaystyle {\ tylda {O}} (n ^ {2 + 1/6} L)}$${\ Displaystyle {\ tylda {O}} (n ^ {2 + 1/18} L)}$

Porównanie metod punktów wewnętrznych i algorytmów simpleks

Obecna opinia jest taka, że ​​wydajność dobrych implementacji metod opartych na simpleksie i metod punktów wewnętrznych jest podobna w przypadku rutynowych zastosowań programowania liniowego. Jednak w przypadku określonych typów problemów LP może się zdarzyć, że jeden typ solwera jest lepszy od drugiego (czasem znacznie lepszy), a struktura rozwiązań generowanych przez metody punktów wewnętrznych w porównaniu z metodami opartymi na simpleksie znacznie różni się przy wsparciu zestaw aktywnych zmiennych jest zazwyczaj mniejszy dla tej ostatniej.

Otwarte problemy i ostatnie prace

W teorii programowania liniowego istnieje kilka otwartych problemów, których rozwiązanie oznaczałoby fundamentalny przełom w matematyce i potencjalnie duży postęp w naszej zdolności do rozwiązywania wielkoskalowych programów liniowych.

• Czy LP dopuszcza algorytm silnie wielomianowy ?
• Czy LP dopuszcza algorytm silnie wielomianowy do znalezienia rozwiązania ściśle komplementarnego?
• Czy LP dopuszcza algorytm wielomianowy w modelu obliczeń liczb rzeczywistych (koszt jednostkowy)?

Ten ściśle powiązany zestaw problemów został wymieniony przez Stephena Smale jako jeden z 18 największych nierozwiązanych problemów XXI wieku. Mówiąc słowami Smale, trzecia wersja problemu „jest głównym nierozwiązanym problemem teorii programowania liniowego”. Chociaż istnieją algorytmy do rozwiązywania programowania liniowego w słabo wielomianowym czasie, takie jak metody elipsoidalne i techniki punktu wewnętrznego , nie znaleziono jeszcze algorytmów, które umożliwiłyby działanie silnie wielomianowe w liczbie ograniczeń i liczbie zmiennych. Rozwój takich algorytmów byłby bardzo interesujący teoretycznie i być może umożliwiłby także praktyczne korzyści w rozwiązywaniu dużych LP.

Chociaż hipoteza Hirscha została niedawno odrzucona dla wyższych wymiarów, nadal pozostawia otwarte następujące pytania.

• Czy istnieją reguły przestawne, które prowadzą do wariantów simpleks w czasie wielomianowym?
• Czy wszystkie grafy politopowe mają średnicę ograniczoną wielomianem?

Pytania te dotyczą analizy wydajności i rozwoju metod simpleksowych. Ogromna wydajność algorytmu simpleks w praktyce, pomimo jego teoretycznej wydajności w czasie wykładniczym, wskazuje, że mogą istnieć odmiany simpleksu działające w czasie wielomianowym lub nawet silnie wielomianowym. Wiedza o istnieniu takich wariantów miałaby ogromne znaczenie praktyczne i teoretyczne, szczególnie jako podejście do decydowania, czy LP można rozwiązać w czasie silnie wielomianowym.

Algorytm simpleks i jego warianty należą do rodziny algorytmów podążania za krawędzią, nazwanych tak, ponieważ rozwiązują problemy programowania liniowego, przechodząc od wierzchołka do wierzchołka wzdłuż krawędzi wielotopu. Oznacza to, że ich teoretyczna wydajność jest ograniczona przez maksymalną liczbę krawędzi między dowolnymi dwoma wierzchołkami politopu LP. W rezultacie interesuje nas poznanie maksymalnej teoretycznej średnicy grafów grafów politopalnych . Udowodniono, że wszystkie politopy mają średnicę podwykładniczą. Niedawne obalenie hipotezy Hirscha jest pierwszym krokiem do udowodnienia, czy jakikolwiek wielotop ma średnicę superwielomianów. Jeśli takie politopy istnieją, żaden wariant podążający za krawędzią nie może działać w czasie wielomianowym. Pytania dotyczące średnicy politopu są przedmiotem niezależnego zainteresowania matematycznego.

Metody obrotu simplex zachowują pierwotną (lub podwójną) wykonalność. Z drugiej strony, metody przechyłu krzyżowego nie zachowują (pierwotnej lub podwójnej) wykonalności – mogą odwiedzać podstawy pierwotne wykonalne, podwójne wykonalne lub pierwotne i podwójne niewykonalne w dowolnej kolejności. Tego typu metody obrotowe badane są od lat 70. XX wieku. Zasadniczo metody te mają na celu znalezienie najkrótszej ścieżki obrotu na politopie ułożenia w ramach problemu programowania liniowego. Wiadomo, że w przeciwieństwie do grafów politopalnych, grafy ułożenia politopów mają małą średnicę, co pozwala na zastosowanie silnie wielomianowego algorytmu przestawnego krzyżowego bez rozwiązywania pytań o średnicę ogólnych politopów.

Niewiadome całkowite

Jeśli wszystkie nieznane zmienne muszą być liczbami całkowitymi, problem nazywa się programowaniem całkowitoliczbowym (IP) lub programowaniem liniowym całkowitoliczbowym (ILP). W przeciwieństwie do programowania liniowego, które można skutecznie rozwiązać w najgorszym przypadku, problemy programowania całkowitoliczbowego są w wielu praktycznych sytuacjach (tych ze zmiennymi ograniczonymi) NP-trudne . Programowanie liczb całkowitych 0–1 lub programowanie liczb całkowitych binarnych (BIP) to szczególny przypadek programowania liczb całkowitych, w którym zmienne muszą mieć wartość 0 lub 1 (zamiast arbitralnych liczb całkowitych). Problem ten jest również klasyfikowany jako NP-trudny, aw rzeczywistości wersja decyzyjna była jednym z 21 problemów NP-zupełnych Karpa .

Jeśli tylko niektóre z nieznanych zmiennych muszą być liczbami całkowitymi, to problem nazywa się problemem programowania mieszanych liczb całkowitych (MIP). Są one na ogół również NP-trudne, ponieważ są jeszcze bardziej ogólne niż programy ILP.

Istnieje jednak kilka ważnych podklas problemów IP i MIP, które można skutecznie rozwiązać, w szczególności problemy, w których macierz ograniczeń jest całkowicie jednomodułowa, a prawe strony ograniczeń są liczbami całkowitymi lub – ogólniej – gdy system ma całkowitą podwójną integralność (TDI).

Zaawansowane algorytmy rozwiązywania programów liniowych całkowitoliczbowych obejmują:

• metoda płaszczyzny tnącej
• Oddział i związany
• Oddział i cięcie
• Oddział i cena
• jeśli problem ma dodatkową strukturę, możliwe jest zastosowanie opóźnionego generowania kolumn .

Takie algorytmy programowania całkowitoliczbowego omawiają Padberg i Beasley.

Całkowe programy liniowe

O programie liniowym w zmiennych rzeczywistych mówimy, że jest całkowy, jeśli ma co najmniej jedno optymalne rozwiązanie, które jest całkowe. Podobnie mówi się , że wielościan jest całkowy, jeśli dla wszystkich ograniczonych wykonalnych funkcji celu c , program liniowy ma optimum ze współrzędnymi całkowitymi. Jak zaobserwowali Edmonds i Giles w 1977, można równoważnie powiedzieć, że wielościan jest całkowy, jeśli dla każdej ograniczonej możliwej do wykonania całkowej funkcji celu c optymalna wartość programu liniowego jest liczbą całkowitą. ${\ Displaystyle P = \ {x \ mid Axe \ geq 0 \}}$${\ Displaystyle \ {\ max cx \ mid x \ w P \}}$${\ Displaystyle x ^ {*}}$${\displaystyle P}$${\ Displaystyle \ {\ max cx \ mid x \ w P \}}$

Całkowe programy liniowe mają kluczowe znaczenie w wielościennym aspekcie optymalizacji kombinatorycznej, ponieważ zapewniają alternatywną charakterystykę problemu. W szczególności, dla każdego problemu, wypukły kadłub rozwiązań jest integralnym wielościanem; jeśli ten wielościan ma ładny/zwarty opis, to możemy efektywnie znaleźć optymalne, możliwe do zrealizowania rozwiązanie dla dowolnego celu liniowego. I odwrotnie, jeśli możemy udowodnić, że relaksacja programowania liniowego jest całkowa, to jest to pożądany opis wypukłej powłoki możliwych (całkowych) rozwiązań.

Terminologia nie jest spójna w całej literaturze, dlatego należy uważać na rozróżnienie następujących dwóch pojęć:

• w programie całkowitoliczbowym liniowym, opisanym w poprzedniej sekcji, zmienne są siłą ograniczone do liczb całkowitych, a problem ten jest ogólnie NP-trudny,
• w całkowym programie liniowym, opisanym w tej sekcji, zmienne nie są ograniczone do liczb całkowitych, ale raczej udowodniono w jakiś sposób, że problem ciągły zawsze ma całkowitą wartość optymalną (zakładając, że c jest całką), a tę optymalną wartość można znaleźć efektywnie, ponieważ wszystkie programy liniowe o rozmiarze wielomianowym można rozwiązać w czasie wielomianowym.

Jednym z powszechnych sposobów udowodnienia, że ​​wielościan jest integralny, jest pokazanie, że jest on całkowicie jednomodułowy . Istnieją inne ogólne metody, w tym własność dekompozycji liczb całkowitych i całkowita podwójna integralność . Inne dobrze znane integralne LP obejmują pasujący polytope, sieciowy polyhedra, submodular flow polyhedra i przecięcie dwóch uogólnionych polymatroids/ g- polimatroids – np. patrz Schrijver 2003.

Solvery i języki skryptowe (programowania)

Licencje zezwalające :

Licencje typu copyleft (wzajemne) :

MINTO (Mixed Integer Optimizer, solwer programowania liczb całkowitych, który wykorzystuje algorytm branch and bound) ma publicznie dostępny kod źródłowy, ale nie jest oprogramowaniem typu open source.

Licencje własne :

Zobacz też

Uwagi

Bibliografia

Dalsza lektura

Zewnętrzne linki

• Wskazówki dotyczące formułowania problemów związanych z LP
• Słownik programowania matematycznego
• Często zadawane pytania dotyczące programowania liniowego
• Benchmarki dla oprogramowania do optymalizacji