Pytania otagowane jako linear-programming

Optymalizacja z liniową funkcją celu, podlegająca ograniczeniom równości liniowej i nierówności liniowej.

3
Ekspresowe operacje logiczne typu boolowskiego w programowaniu liniowym całkowitym zero-jeden (ILP)
Mam całkowity program liniowy (ILP) z niektórymi zmiennymi które mają reprezentować wartości boolowskie. Wartości muszą być liczbami całkowitymi i zawierać 0 lub 1 ( ).xixix_ixixix_i0≤xi≤10≤xi≤10 \le x_i \le 1 Chcę wyrazić operacje boolowskie na tych zmiennych o wartości 0/1, używając ograniczeń liniowych. Jak mogę to zrobić? Mówiąc dokładniej, chcę ustawić …
1
Sortowanie jako program liniowy
Zaskakująca liczba problemów ma dość naturalne ograniczenia w programowaniu liniowym (LP). Przykłady, takie jak przepływy sieciowe, dopasowanie dwustronne, gry o sumie zerowej, najkrótsze ścieżki, forma regresji liniowej, a nawet ocena obwodu, patrz rozdział 7 w [1]! Ponieważ ocena obwodu ogranicza się do programowania liniowego, każdy problem w musi mieć sformułowanie …
2
Czy każdy problem NP ma wielocząsteczkowy preparat ILP?
Ponieważ całkowite programowanie liniowe jest zakończone NP, występuje zmniejszenie Karp z dowolnego problemu w NP. Pomyślałem, że to sugeruje, że zawsze istnieje wielomianowa formuła ILP dla dowolnego problemu w NP. Ale widziałem artykuły na temat konkretnych problemów związanych z NP, w których ludzie piszą takie rzeczy, jak: „to jest pierwszy …
2
Zminimalizuj maksymalny składnik sumy wektorów
Chciałbym dowiedzieć się czegoś o tym problemie optymalizacji: dla podanych nieujemnych liczb całkowitych znajdź funkcję minimalizującą wyrażenie fzaja , j , kai,j,ka_{i,j,k}faff maxk∑jazaja , f( i ) , kmaxk∑iai,f(i),k\max_k \sum_i a_{i,f(i),k} Przykład użycia innej formuły może być jaśniejszy: Otrzymałeś zestaw zestawów wektorów takich jak { {(3, 0, 0, 0, 0), …
4
Znalezienie dokładnych rozwiązań narożnych dla programowania liniowego przy użyciu metod punktów wewnętrznych
Algorytm simpleks chciwie chodzi po rogach wielopola, aby znaleźć optymalne rozwiązanie problemu programowania liniowego. W rezultacie odpowiedź jest zawsze rogiem polytopa. Metody punktowe wewnętrzne chodzą po polytopie. W rezultacie, gdy cała płaszczyzna polytopu jest optymalna (jeśli funkcja celu jest dokładnie równoległa do płaszczyzny), możemy uzyskać rozwiązanie w środku tej płaszczyzny. …
5
Czy wszystkie problemy z całkowitym programowaniem liniowym są trudne?
Jak rozumiem, problem przypisania występuje w P, ponieważ węgierski algorytm może go rozwiązać w czasie wielomianowym - O (n 3 ). Rozumiem również, że problem z przypisaniem jest całkowitym problemem programowania liniowego , ale strona Wikipedii stwierdza, że ​​jest to NP-Hard. Dla mnie oznacza to, że problem przypisania jest w …
1
Krótki i sprytny dowód silnego twierdzenia o dualności dla programowania liniowego
Rozważ programy liniowe Primal:Ax⃗ ≤b⃗ maxc⃗ Tx⃗ Primal:Ax→≤b→maxc→Tx→\begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} Dual:c⃗ ≤y⃗ TAminy⃗ Tb⃗ Dual:c→≤y→TAminy→Tb→\begin{array}{|ccc|} \hline Dual: & \vec{c} \leq \vec{y}^TA \hspace{.5cm} & \min \vec{y}^T\vec{b} \\ \hline \end{array} Twierdzenie o słabym dualności mówi, że jeśli i spełniają ograniczenia, to …
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.