Witam, mam dane takie zagadnienie prymalne:
\(\displaystyle{ \begin{cases} 20x_1+12x_2+12x_3 \rightarrow min\\3x_1+2x_2+2x_3\geqslant 3\\ 4x_1+4x_2+3x_3\geqslant 9\\x_1,x_2,x_3\geqslant 0\end{cases}}\)
Utworzyłem do niego takie zagadnienie dualne:
\(\displaystyle{ \begin{cases} 3y_1+y_2 \rightarrow max\\3y_1+4y_2\leqslant 20\\2y_1+4y_2\leqslant 12\\2y_1+3y_2\leqslant 12\\y_1,y_2\geqslant 0\end{cases}}\)
Wyznaczyłem rozwiązanie optymalne zadania dualnego \(\displaystyle{ A = (0,3)}\), i tutaj zaczyna się problem. Mam teraz wyznaczyć rozwiązanie optymalne zadania prymalnego, korzystając z twierdzeń o dualności. Mógłby mi ktoś pojaśnić jak to się robi ?
Twierdzenia o dualności - zastosowanie
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Twierdzenia o dualności - zastosowanie
Nie znam się na tym, ale ja bym to robił tak:
Skoro mamy wyznaczone \(\displaystyle{ A=(0,3)}\), to podstawiamy je do \(\displaystyle{ 3y_1+y_2}\), żeby wyliczyć maksimum drugiego zagadnienia. Z twierdzenia o dualności wiemy, że jest to jednocześnie minimum pierwszego zagadnienia. Rozwiązanie pierwszego zagadnienia leży w którymś z wierzchołków wielościanu, więc będzie to rozwiązanie układu trzech równań, gdzie pierwsze równanie to
\(\displaystyle{ 20x_1+12x_2+12x_3=max}\),
gdzie \(\displaystyle{ max}\) jest wyliczonym maksimum.
Dwa pozostałe równania to dwie z pięciu nierówności, z zamienionymi znakami \(\displaystyle{ \ge}\) na \(\displaystyle{ =}\). Które dwie, tego nie wiem, więc sprawdzałbym po kolei. Najpierw
\(\displaystyle{ \begin{cases}20x_1+12x_2+12x_3=max\\x_1=0\\x_2=0\end{cases}}\)
i pozostałe z dwoma zerami, bo są najprostsze do sprawdzenia. Potem przypadki z jednym zerem, itd. Jak znajdziemy układ niesprzeczny, to już.
Jeszcze raz podkreślam, że kompletnie się na tym nie znam, więc być może istnieje jakiś szybszy sposób niż podany przeze mnie.
Skoro mamy wyznaczone \(\displaystyle{ A=(0,3)}\), to podstawiamy je do \(\displaystyle{ 3y_1+y_2}\), żeby wyliczyć maksimum drugiego zagadnienia. Z twierdzenia o dualności wiemy, że jest to jednocześnie minimum pierwszego zagadnienia. Rozwiązanie pierwszego zagadnienia leży w którymś z wierzchołków wielościanu, więc będzie to rozwiązanie układu trzech równań, gdzie pierwsze równanie to
\(\displaystyle{ 20x_1+12x_2+12x_3=max}\),
gdzie \(\displaystyle{ max}\) jest wyliczonym maksimum.
Dwa pozostałe równania to dwie z pięciu nierówności, z zamienionymi znakami \(\displaystyle{ \ge}\) na \(\displaystyle{ =}\). Które dwie, tego nie wiem, więc sprawdzałbym po kolei. Najpierw
\(\displaystyle{ \begin{cases}20x_1+12x_2+12x_3=max\\x_1=0\\x_2=0\end{cases}}\)
i pozostałe z dwoma zerami, bo są najprostsze do sprawdzenia. Potem przypadki z jednym zerem, itd. Jak znajdziemy układ niesprzeczny, to już.
Jeszcze raz podkreślam, że kompletnie się na tym nie znam, więc być może istnieje jakiś szybszy sposób niż podany przeze mnie.