Programowanie liniowe

[kasztan00126]

Witam mam zrobic takie zadanie ale nie wiem jak Wyznaczyc \(\displaystyle{ \max \{f(x,y)=x+y\}}\) przy warunkach \(\displaystyle{ x \le 3 , x+2y \le 4, x \ge 0, y \ge 0}\)

[szw1710]

Przede wszystkim zrób rysunek zbioru wyznaczonego przez zadane ograniczenia. A potem zamieść ten rysunek tutaj. Wtedy pomogę Ci z dalszą częścią.

[kasztan00126]

To jest ten obszar i dalej nie wiem co zrobic

AU

cb89ebcb30a8af93med.jpg (17.35 KiB) Przejrzano 130 razy

[/url]

[szw1710]

Rysunek OK. Mógłby być większy, ale jest widoczny

Teraz narysuj prostą (może innym kolorem) o równaniu \(\displaystyle{ x+y=0.}\) Oznacza ona zysk zerowy. Jeśli będziemy przesuwali ją równolegle do góry, to będziemy otrzymywać proste postaci \(\displaystyle{ x+y=a.}\) Oznacza to, że wtedy zysk będzie miał wartość \(\displaystyle{ a.}\) Przesuwaj prostą zysku do góry do czasu, aż opuści obszar rozwiązań dopuszczalnych - ten narysowany czworokąt. W jakim położeniu jest to osiągane?

Może na razie tyle, zakończymy, gdy wykonasz moje polecenia.

[kasztan00126]

x+y=0 inaczej x=-y ok to teraz przesuwam do gory

x y
1 1
2 2
3 3(poza obszarem na osi OY)

ta prosta x+y=0 ma byc na krawedzi obu obszarów czy może sie łapać na krawedz jednego i to tez bedzie to max?

AU

47463c2766fd9ee6med.jpg (19.35 KiB) Przejrzano 130 razy

[/url]

nie da sie tego jakos policzyc ? czy trzeba wysowac i z wykresu odczytywac?

[szw1710]

Rysunek nie za dobrze - jaki kąt tworzy z osią \(\displaystyle{ x}\) żółta prosta? I narysuj ją później w tym najwyższym położeniu.

Obliczenia są znacznie bardziej skomplikowane niż metoda graficzna. Oczywiście metodę graficzną można zastosować do problemów z co najwyżej trzema zmiennymi decyzyjnymi. Dalej już niestety rachunki. Albo metoda rozwiązań bazowych, albo metoda simplex. To już wyższa szkoła jazdy, a metoda graficzna daje wgląd, na czym tak naprawdę polega programowanie liniowe.

[kasztan00126]

żółta prosta z osia x tworzy kat 45 (stopni) prosta musi sie zawierac w przedziale na obu osiach??

[szw1710]

Tak. Dokładnie \(\displaystyle{ 135^{\circ},}\) ale rozumiem.

Wystartuj od położenia jak na rysunku. Prosta ma równanie \(\displaystyle{ x+y=0,}\) więc opisuje zerowy zysk. Wywinduj ją nieco do góry. Np. narysuj prostą \(\displaystyle{ x+y=1.}\) Co obserwujemy? Przecina nasz czworokąt. Winduj jeszcze: \(\displaystyle{ x+y=2.}\) Też przecina? Częścią wspólną jest odcinek. Winduj jeszcze, aż częścią wspólną będzie jeden punkt. Bo żadem z boków czworokąta nie jest równoległy do prostej zysku i tak jak piszę, na pewno się zdarzy. Jakie równanie ma przesunięta prosta? \(\displaystyle{ x+y=a.}\) Wyznacz to \(\displaystyle{ a.}\)

Im bardziej windujesz prostą zysku do góry, tym bardziej zwiększa się zysk. Rzecz w tym, żeby część wspólna prostej zysku z obszarem rozwiązań dopuszczalnych była jeszcze niepusta.

[Zordon]

Z ogólnej teorii wynika, że max będzie osiągnięty w pewnym wierzchołku, więc wystarczy w nich policzyć wartości. Nie mniej jednak powyższe rozważania prowadzą do lepszego zrozumienia o co w tym chodzi, zatem warto je przeprowadzić

[szw1710]

I dlatego pół dnia człowiekowi pomagam Mam robotę na komputerze i z doskoku patrzę na forum. To, co mówię, nie wymaga żadnej wiedzy poza umiejętnością narysowania zbioru rozwiązań układu nierówności liniowych oraz prostej. Tutaj programowanie liniowe jest jedną z wielu strasznych nazw. W sytuacji ogólnej nie da się tego jednak zrobić w opisany sposób. Dla większej liczby zmiennych decyzyjnych właśnie metody rozwiązań bazowych czy simplex pozwalają te wierzchołki wyznaczyć. Rozwiązania bazowe dają wszystkie wierzchołki, simplex szuka od razu w dobrym kierunku. I ideologia jest wtedy taka, jak opisujesz.

Twierdzenie jest ogólniejsze: minimum funkcji wypukłej jest osiągane w punkcie ekstremalnym zbioru rozwiązań dopuszczalnych. Po przemnożeniu przez \(\displaystyle{ -1}\) mamy analogiczną tezę dla funkcji wklęsłych. Funkcja liniowa (afiniczna) jest i wypukła, i wklęsła. A zatem mamy oprócz twierdzenia o przyjmowaniu maksimum w punkcie ekstremalnym, także twierdzenie o minimum. Jego zastosowanie w naszym zadaniu jest jednak pozbawione sensu, bo minimum jest widoczne gołym okiem

[kasztan00126]

czyli z tego wynika za to max to a=3,5 ??

[szw1710]

Dokładnie tak.

[kasztan00126]

a mam jeszcze takie pytanie jak poznac czy zadanie jest z programowania liniowego bo mialem takie zadanie na egzaminie. nie pamietam treści ale może jest jakiś człon który musi być w każdym zadaniu z programowania liniowego?

[szw1710]

1. Funkcja celu musi być liniowa, tj. mieć postać \(\displaystyle{ f(x_1,\dots,x_n)=c_1x_1+\dots+c_nx_n.}\)
2. Zbiór rozwiązań dopuszczalnych musi być określony układem nierówności liniowych, tj.

\(\displaystyle{ \left\{\begin{aligned}
a_{11}x_1+\dots+a_{1n}x_n&\le b_1\\
a_{21}x_1+\dots+a_{2n}x_n&\le b_2\\
&\vdots\\
a_{m1}x_1+\dots+a_{mn}x_n&\le b_m
\end{aligned}\right.}\)

[kasztan00126]

wielkie dzieki