Treść zadania

Rozwiązania

• 

  5 0

  antekL1 11.10.2020 (10:54)

  To jest zadanie z tzw. "programowania liniowego".
  Polega ono na znalezieniu max z "funkcji celu" określonej wyrażeniem (7)
  pod warunkiem, że zmienne x1, x2 spełniają nierówności (pierwszego stopnia)
  opisane przez wyrażenia od (1) do (6).
  
  Można to dla dwóch zmiennych rozwiązać graficznie - patrz załącznik *.PNG.
  Na płaszczyźnie zaznaczamy obszar, w którym wszystkie nierówności są spełnione.
  
  Zacznijmy od warunków (5) i (6).
  Na poziomej osi jest zmienna x1, na pionowej zmienna x2.
  Zauważ, że jednoczesne spełnienie wszystkich czterech warunków (5) i (6)
  zachodzi w zielonym kwadracie ABCD, więc nasza funkcja celu MUSI mieć
  argumenty z wnętrza tego kwadratu. Ale to nie koniec.
  
  Weźmy nierówności (1) i (3).
  Można je (dzieląc nierówność 3 na pół) zapisać jako: 9000 ≤ x1 + x2 ≤ 12 000.
  Aby graficznie to rozwiązać rysujemy najpierw prostą odpowiadającą RÓWNANIU
  x2 = 12000 - x1
  
  Jeśli zastąpimy równanie przez nierówność x1 + x2 ≤ 12 000
  to punkty (x1,x2) będą leżeć na PÓŁPLASZCZYŻNIE po którejś stronie tej prostej.
  Aby sprawdzić po której najprościej jest zobaczyć, czy punkt (0;0) spełnia nierówność.
  Spełnia. Więc rozwiązaniem nierówności (1) jest półpłaszczyzna leżąca poniżej i na lewo
  od prostej x2 = 12000 - x1.
  
  Podobnie rozwiązaniem nierówności (3) jest półpłaszczyzna leżąca na górze i po prawej
  od prostej x2 = 9000 - x1.
  Jednoczesne rozwiązanie 9000 ≤ x1 + x2 ≤ 12 000 to pasek płaszczyzny między
  obydwiema prostymi.
  Wiemy już, że warunki (1), (3), (5), (6) to przecięcie zielonego kwadratu i tego paska.
  
  Podobnie traktujemy warunek (2) -x1 + 2x2 ≥ 2 000
  Rysujemy prostą x2 = 1000 + x1 / 2 wyznaczamy półpłaszczyznę.
  Punkt (0;0) nie spełnia tej nierówności więc jest to ta półpłaszcyzna nad prostą.
  Analogicznie warunek (4) -2x1 + 3x2 ≤ 6 000
  daje cześć płaszczyzny pod prostą x2 = 2000 + 2x1 / 3.
  
  Przecięcie WSZYSTKICH półpłaszczyzn wyznacza błękitny wielokąt EFGHIJ.
  Max funkcji szukamy w tym wielokącie, a z teorii wiadomo, że musi to być
  BRZEG lub WIERZCHOŁEK tego wielokąta (zwanego "symplex").
  -----------------------------------
  
  Teraz jest ważny moment: Funkcja celu to (7) F(x1, x2) = 20x1 + 30x2
  Załóżmy, że mamy jakąś jej wartość (ja przyjąłem 100000).
  Mamy równanie: 20x1 + 30x2 = 100000,, stąd:
  x2 = 10000 - 2x1 / 3 <------------ to jest przerywana, czerwona linia na rysunku.
  Zauważ, że WSZYSTKIE punkty (x1;x2) leżące na tej linii dają ten sam wynik na F.
  Teraz jeśli przesuniemy tą linię RÓWNOLEGLE w górę to dostaniemy inne proste
  dla których wartości F są jednakowe. No to przesuwamy możliwie najwyżej aby
  zmaksymalizować funkcję F. Pamiętamy jednak, że rozwiązania mają leżeć
  w błękitnym wielokącie.
  W ten sposób znajdujemy punkt E (6000,6000) - jak widzisz jest to wierzchołek.
  ===================================
  
  Rozwiązanie za pomocą "Solver". Miałem tylko LibreOffice, ale Excelu robi się podobnie.
  Najpierw przygotowujemy dane.
  
  1) wybieramy dwie komórki reprezentujące zmienne x1, x2.
  U mnie są to B1 i B2. Wpisujemy tam początkowo zera.
  
  2) Wybieramy komórki do wpisywania warunków.
  Wpisujemy tam wyrażenia odpowiadające nierównościom.
  Przykład: Jeśli nierówność to x1 + x2 <= 12000 to wpisujemy TYLKO x1 + x1
  tak jak wpisałem w komórkę B6 sumę, czyli wyrażenie " = B1 + B2 "
  Jeśli mamy warunek typu x1 < 1000, to wpisujemy tylko B1
  
  3) W jedną z komórek (u mnie B13) wpisujemy wyrażenie na funkcję celu
  czyli 20*B1 + 30*B2
  
  4) Uruchamiamy "solver" (w LibreOffice jest on pod Narzędzia (Tools))
  Jest tam pole opisujące "W której komórce jest funkcja celu". U mnie w B13
  więc piszę $B$13 (koniecznie z dolarami).
  Następnie wpisujemy pola, które chcemy zmieniać, czyli x1 i x2 w postaci
  $B$1:$B$2
  (dlatego warto trzymać te zmienne obok siebie)
  Potem wybieramy "maksymalizuj". Dalej jest dużo linii w których określamy
  nierówności. Na przykład dla nierówności x1 + x2 <= 12000 wpisujemy
  $B$6 - to jest komórka zawierająca wyrażenie B1 + B2.
  Wybieramy operator <=, =, >= i wpisujemy wartość 12000.
  To trzeba powtórzyć wiele razy, dla podwójnych nierówności typu 6000 < x1 < 10000
  wpisujemy oddzielnie warunek $B10 < 10000 i oddzielnie $B10 > 6000.
  
  5) Jak to się zrobi i sprawdzi czy nie ma błędu klikamy "Solve" - i gotowe.
  W komórkach B1, B2 mamy szukane x1, x2, w komórce B13 mamy wartość F.
  ===================================
  
  Gdyby coś "źle szło" to warto w Opcje sprawdzić, czy wybraliśmy NAJPROSTSZĄ
  metodę rozwiązania, np. dla LibreOffice jest to "LibreOfice Solver".
  U mnie rozwiązanie pojawiło się praktycznie natychmiast.
  Powodzenia, w razie pytań pisz proszę na priv.

  Załączniki

  • grafika.png (787 KB)
  • solver.ods (12 KB)

  Dodaj komentarz - Zgłoś nadużycie

  Zaloguj się lub załóź konto aby dodać komentarz.

  Dodaj