Pytania otagowane jako linear-programming

Matematyczna i obliczeniowa metoda znalezienia najlepszego wyniku w danym modelu matematycznym, w którym lista wymagań jest reprezentowana jako relacje liniowe.

1
Stabilność numeryczna metody Simplex
Algorytm simpleksowy jest często traktowany albo w ramach rzeczywistej arytmetyki, albo w świecie dyskretnym z dokładnymi obliczeniami. Wydaje się jednak, że jest najczęściej wdrażany za pomocą arytmetyki zmiennoprzecinkowej. Prowadzi to do pytania, czy algorytm simpleks należy traktować jako algorytm numeryczny, w szczególności w jaki sposób błędy zaokrąglenia wpływają na obliczenia. …
2
Programowanie liczb całkowitych ze stałą liczbą zmiennych
Słynny artykuł H. Lenstry Integer Programowanie z ustaloną liczbą zmiennych z 1983 r. Stwierdza, że ​​programy liczb całkowitych o ustalonej liczbie zmiennych można rozwiązać wielomianem czasowym długości danych. Interpretuję to w następujący sposób. Programowanie liczb całkowitych ogólnie jest nadal NP-kompletne, ale jeśli mój typowy rozmiar problemu (powiedzmy około 10.000 zmiennych, …
2
Minimalne maksymalne rozwiązania LP
Programowanie liniowe jest oczywiście obecnie bardzo dobrze rozumiane. Mamy dużo pracy, która charakteryzuje strukturę wykonalnych rozwiązań i strukturę rozwiązań optymalnych. Mamy silną dualność, algorytmy wielogodzinne itp. Ale co wiadomo na temat minimalnych maksymalnych rozwiązań LP? Lub równoważnie maksymalne minimalne rozwiązania? (To nie jest tak naprawdę pytanie badawcze, ale może możemy …
1
Znalezienie płaszczyzny cięcia, która równomiernie dzieli wielościan
Powiedzmy, że mamy wielościan w standardowej formie: A x = bx ≥ 0ZAx=bx≥0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} Czy są znane metody znalezienia hiperpłaszczyzny która dzieli wielościan w taki sposób, że liczba wierzchołków po każdej stronie hiperpłaszczyzny jest w przybliżeniu taka sama? (tj. algorytm minimalizujący …
1
Relaks
Mam pytanie wykonalności, które można sformułować w następujący sposób. Ja dany punkt w -wymiarowej przestrzeni wektorowej i chcę, aby znaleźć najbliższy punkt do że spełnia zestaw „ ograniczeń” formularzadpppreddp ℓ 0qqqpppℓ0ℓ0\ell_0 Biorąc pod uwagę zestaw , co najwyżej jeden z może być niezerowy.S.∈ [ 1 … d]S∈[1…d]S \in [1\ldots d]{ …
1
Dlaczego komplementarność jest ważna?
Komplementarny luz (CS) jest powszechnie nauczany, gdy mówi się o dualności. Ustanawia ładny związek między pierwotnym a podwójnym ograniczeniem / zmiennymi z matematycznego punktu widzenia. Dwa główne powody stosowania CS (zgodnie z nauczaniem na kursach dla absolwentów i podręcznikach): Aby sprawdzić optymalność LP Aby pomóc rozwiązać problem podwójny Biorąc pod …
2
Co można rozwiązać za pomocą programowania półfinałowego, czego nie można rozwiązać za pomocą programowania liniowego?
Znam programy liniowe, ponieważ mogą one rozwiązywać problemy z liniowymi funkcjami celu i ograniczeniami liniowymi. Ale co programowanie półfinalne może rozwiązać, czego programowanie liniowe nie jest w stanie? Wiem już, że programy półfinałowe są uogólnieniem programów liniowych. Jak rozpoznać problem, który można rozwiązać za pomocą programowania półfinałowego? Jakiego typowego problemu …
2
Jak / dlaczego systemy liniowe są tak ważne dla informatyki?
Zainteresowałem się optymalizacją matematyczną całkiem niedawno i bardzo mi się podoba. Wydaje się, że wiele problemów związanych z optymalizacją można łatwo wyrazić i rozwiązać jako programy liniowe (np. Przepływy sieciowe, pokrycie krawędzi / wierzchołków, podróżujący sprzedawca itp.) Wiem, że niektóre z nich są trudne do NP, ale chodzi o to, …
1
Skutecznie rozwiązać system ścisłych nierówności liniowych ze wszystkimi współczynnikami równymi 1 bez użycia ogólnego solwera LP?
Według tytułu, oprócz korzystania z solwera LP ogólnego przeznaczenia, istnieje podejście do rozwiązywania układów nierówności względem zmiennych xja, ... ,xkxi,…,xkx_i, \ldots, x_k gdzie nierówności mają formę ∑ja ∈ jaxja&lt;∑j ∈ Jxjot∑i∈Ixi&lt;∑j∈Jxj\sum_{i \in I} x_i < \sum_{j \in J} x_j? Co ze szczególnym przypadkiem nierówności, które tworzą całkowity porządek nad sumami …
2
Rozwiązania punktu środkowego dla programów liniowych
Istnieje program liniowy, dla którego chcę nie tylko rozwiązania, ale rozwiązania, które jest tak centralne, jak to możliwe na powierzchni polytopa, który przyjmuje minimalną wartość. Z góry oczekujemy, że minimalizująca powierzchnia powinna być wielowymiarowa z różnych powodów, w tym, że minimalizowana funkcja celu jest maksimum z wielu ograniczeń: Zminimalizować ϵϵ\epsilon …
3
Rozwiązanie programowania liniowego w jednym przejściu z uporządkowanymi zmiennymi
Mam rodzinę problemów z programowaniem liniowym: maksymalizuj c′xdo′xc' x z zastrzeżeniem Ax≤bZAx≤bA x\le b, x≥0x≥0x\ge0. ElementyAZAA, bbb, i cdoc są liczbami całkowitymi nieujemnymi, cdocściśle pozytywne. (xxx powinien być również integralny, ale będę się tym martwić później). W mojej aplikacji często zdarza się, że współczynniki AAA i ccc są takie, że …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.