On 2012-09-25 21:16, M.M. wrote:
> W dniu wtorek, 25 września 2012 19:47:42 UTC+2 użytkownik Kacper Rzepecki napisał:
>> Popraw mnie, jeżeli się mylę ale czy nie da się przekształcić tego
>> problemu do serii problemów programowania liniowego? W każdym problemie
>> zakładasz że jedna z twoich funkcji f jest minimalna (i zabezpieczasz to
>> założenie odpowiednimi ograniczeniami) po czym dokonujesz jej
>> maksymalizacji.
>
> Nie jestem pewny, ale chyba sie mylisz. Czy takie zadanie miesci sie w ramach
programowania liniowego. Jesli pozostale funkcje przerobimy na warunki, to funkcja
celu stanie sie jakas dziwna: jej wartosc nie bedzie zalezala tylko od
optymalizowanej funkcji, ale takze od warunkow. Jesli ktorys z warunkow spadnie
ponizej optymalizowanej funkcji, to funkcja celu bedzie rowna temu warunkowi. Wlasnie
ulozylem takie zadanie w calcu i uzylem slovera. Ladnie policzyl dla pierwszej
funkcji, ale dla drugiej krzyknal ze zadanie jest nierealistyczne. Nie umial
maksymalizowac drugiej funkcji pod warunkiem ze jest mniejsza od wszystkich
pozostalych funkcji. Moze sie zdarzyc ze jedna z funkcji zawsze bedzie wieksza od
ktorejs z pozostalych dla dowolnych wartosci x.
>

Chyba sie jednak nie myle, dlaczego to nie mialby byc problem PL?
Wszystkie ograniczenia i funkcja celu sa w postaci liniowej.

Jeżeli chodzi o to że funkcja celu zależy od warunków: Twój podproblem
PL szuka maksymalnej wartości funkcji f_k przy założeniu że jest ona
mniejsza równa od pozostałych (czyli minimalna). W ujęciu formalnym ona
nie zależy od warunków. Warunki zabezpieczają to, że to akurat f_k jest
funkcją minimalną. Nie ma w tym niczego dziwnego - to typowe przy PL.

Jeżeli jeden z problemów jest niespełnialny to znaczy ze dana funkcja
celu nigdy nie bedzie mniejsza równa od pozostałych, stad też nie moze
byc rozwiazaniem twojego problemu - to jest ok, spojrz chociazby na taki
przyklad:

z1 = {0},
z2 ={1},
f_1 = 0 * x
f_2 = 1 * x

W takim przypadku f_2 nigdy nie bedzie minimalna. Stad twoj "podproblem"
dla k=2 nie ma rozwiazania dopuszczalnego. Co nie zmienia faktu ze
calosc dziala.

Wydaje mi się,że możesz nawet ułożyc jeden problem PL który zagreguje
wybór najlepszego rozwiązania spośród twoich "podproblemow".
Prawdopodobnie musialbys zastosowac zmienne sztuczne.