Witam serdecznie,
Chciałbym prosić o pomoc i sprawdzenie przez kogoś mądrzejszego ode mnie, czy moje rozwiązanie dwóch bliźniaczych zadań dotyczących optymalizacji w zadaniu programowania liniowego całkowitoliczbowego ma sens. Poniżej treść zadań:
(Wstęp identyczny)
Załóżmy, że zbiór \(\displaystyle{ Q \subset R^{n} }\) jest wielościennym zbiorem wypukłym, zaś funkcje \(\displaystyle{ f_{i}(x) }\) i \(\displaystyle{ g_{i}(x)}\) dla \(\displaystyle{ i = 1, 2, ..., m}\) są liniowe i spełniają warunki: \(\displaystyle{ a \le f_{i}(x) \le b}\) , \(\displaystyle{ a \le g_{i}(x) \le b}\) dla każdego \(\displaystyle{ i = 1, 2, ..., m}\) przy \(\displaystyle{ x \in Q}\). Następujące zadanie programowania liniowego przedstawić w postaci zadania programowania liniowego ciągłego (jeśli to możliwe) albo całkowitoliczbowego.
a) \(\displaystyle{ \max \left\{ {{ \min_{ i = 1, 2, ..., m } f_{i}(x) : \min_{ i = 1, 2, ..., m } g_{i}(x) \le c \wedge x \in Q } }\right\} }\)
b) \(\displaystyle{ \max \left\{ {{ \max_{ i = 1, 2, ..., m } f_{i}(x) : \max_{ i = 1, 2, ..., m } g_{i}(x) \le c \wedge x \in Q } }\right\} }\)
... i moje próby:
a) Wprowadźmy zmienne pomocnicze \(\displaystyle{ z = \min_{ i = 1, 2, ..., m } f_{i}(x)}\) oraz \(\displaystyle{ v}\), wówczas:
\(\displaystyle{ \max \left\{ {{ z : z \le \min_{ i = 1, 2, ..., m } f_{i}(x) \wedge \min_{ i = 1, 2, ..., m } g_{i}(x) \le v \wedge v \le c \wedge x \in Q }}\right\} }\)
ZPL przedstawiać się wtedy będzie następująco:
Funkcja celu: \(\displaystyle{ \max z}\)
Przy ograniczeniach: \(\displaystyle{ z \le f_{i}(x)}\) dla \(\displaystyle{ i = 1, 2, ..., m}\),
\(\displaystyle{ v \ge g_{i}(x) - Mu_{i}}\) // tego niespecjalnie rozumiem, wyczytałem ze slajdów w prezentacji prowadzącego o fladze binarnej i jej wykorzystaniu, ale nie mam pojęcia, czy dobrze to interpretuję
\(\displaystyle{ x \in Q \wedge v \le c \wedge u_{i} = 0 \underline{\vee} u_{i} = 1}\) dla \(\displaystyle{ i = 1, 2, ..., m}\)
\(\displaystyle{ \sum_{i = 1}^{i = m} u_{i} \le m - 1}\)
b) Wprowadźmy zmienne pomocnicze \(\displaystyle{ z = \max_{ i = 1, 2, ..., m } f_{i}(x)}\) oraz \(\displaystyle{ v}\), wówczas:
\(\displaystyle{ \max \left\{ {{ z : z \ge \max_{ i = 1, 2, ..., m } f_{i}(x) \wedge \max_{ i = 1, 2, ..., m } g_{i}(x) \ge v \wedge v \ge c \wedge x \in Q }}\right\} }\)
ZPL przedstawiać się wtedy będzie następująco:
Funkcja celu: \(\displaystyle{ \min z}\)
Przy ograniczeniach: \(\displaystyle{ z \ge f_{i}(x)}\) dla \(\displaystyle{ i = 1, 2, ..., m}\),
\(\displaystyle{ v \le g_{i}(x) - Mu_{i}}\) // ta sama uwaga, co powyżej
\(\displaystyle{ x \in Q \wedge v \ge c \wedge u_{i} = 0 \underline{\vee} u_{i} = 1}\) dla \(\displaystyle{ i = 1, 2, ..., m}\)
\(\displaystyle{ \sum_{i = 1}^{i = m} u_{i} \le m - 1}\)
Pozdrawiam
mbyron95