Maksymalizacja funkcji

Algebra liniowa, algebra, wektory, liczby zespolone
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
skrupulat
Witam na forum
Witam na forum
Posty: 5
Rejestracja: 18 mar 2021, 10:55
Podziękowania: 1 raz
Płeć:

Maksymalizacja funkcji

Post autor: skrupulat »

Treść zadania:
Uczestnik rajdu ma do pokonania kolejno cztery odcinki specjalne o długościach: 30, 40, 10 i 20 km.
Z powodów ograniczeń technicznych i wytrzymałościowych samochodu, średnia prędkość osiągana na
każdym odcinku nie może przekroczyć 180 km/h, a na każdych dwóch kolejnych odcinkach nie może
przekroczyć 150 km/h. Jakie prędkości średnie na każdym odcinku powinien osiągać, żeby średnia prędkość
na całej trasie była maksymalna?

Pytanie:
Czy może ktoś pomóc w zdefiniowaniu funkcji i ograniczeń dla podanego problemu?
grdv10
Fachowiec
Fachowiec
Posty: 1039
Rejestracja: 04 sty 2020, 12:47
Podziękowania: 9 razy
Otrzymane podziękowania: 388 razy
Płeć:

Re: Maksymalizacja funkcji

Post autor: grdv10 »

To proste.

Prędkość średnia:\[\frac{30x_1+40x_2+10x_3+20x_4}{100}\rightarrow\max.\]Ograniczenia:
\[
\left\{\begin{aligned}x_1&\geqslant 0\\x_2&\geqslant 0\\x_3&\geqslant 0\\x_4&\geqslant 0\\x_1&\leqslant 180\\x_2&\leqslant 180\\x_3&\leqslant 180\\x_4&\leqslant 180\\\dfrac{30x_1+40x_2}{70}&\leqslant 150\\\dfrac{40x_2+10x_3}{50}&\leqslant 150\\\dfrac{10x_3+20x_4}{30}&\leqslant 150\end{aligned}\right.
\]

Zadanie rozwiązujemy metodą simplex, bo i zagadnienie proste, o dualne, jest za trudne na metodę graficzną.

Rozwiązanie z Maximy:

Kod: Zaznacz cały

load("simplex");
maximize_lp(30*x+40*y+10*z+20*t,[x<180,y<180,z<180,t<180,30*x+40*y<70*150,40*y+10*z<50*150,10*z+20*t<30*150]);
[15000,[t=135,z=180,y=285/2,x=160]]
Jak widać, maksymalizowałem tam licznik, więc maksymalna prędkość średnia to właśnie 150.
skrupulat
Witam na forum
Witam na forum
Posty: 5
Rejestracja: 18 mar 2021, 10:55
Podziękowania: 1 raz
Płeć:

Re: Maksymalizacja funkcji

Post autor: skrupulat »

Wiedziałem, że źle podejdę do problemu. Dzięki wielkie ;)
grdv10
Fachowiec
Fachowiec
Posty: 1039
Rejestracja: 04 sty 2020, 12:47
Podziękowania: 9 razy
Otrzymane podziękowania: 388 razy
Płeć:

Re: Maksymalizacja funkcji

Post autor: grdv10 »

Dla ciekawości zadanie rozwiązałem jeszcze w R. Interesujące jest, że podane jest inne rozwiązanie, ale z tą samą wartością funkcji celu. Tak więc na pewno jest nieskończenie wiele rozwiązań optymalnych. Kwestia jak w obu programach zaimplementowano algorytm simplex.

Kod: Zaznacz cały

library('linprog')
cel<-c(30,40,10,20)/100
macierz<-rbind(
  c(1,0,0,0),
  c(0,1,0,0),
  c(0,0,1,0),
  c(0,0,0,1),
  c(30,40,0,0)/70,
  c(0,40,10,0)/50,
  c(0,0,10,20)/30
)
ograniczenia<-c(rep(180,4),rep(150,3))

sol<-solveLP(cel,ograniczenia,macierz,maximum=T)
print(sol)
Output jest dość skomplikowany, ale interesuje nas pierwszych kilka linijek.

Kod: Zaznacz cały

Results of Linear Programming / Linear Optimization

Objective function (Maximum): 150 

Iterations in phase 1: 0
Iterations in phase 2: 5
Solution
  opt
1 130
2 165
3  90
4 180

Basic Variables
    opt
1   130
2   165
3    90
4   180
S 1  50
S 2  15
S 3  90

Constraints
  actual dir bvec free dual dual.reg
1    130  <=  180   50  0.0  50.0000
2    165  <=  180   15  0.0  15.0000
3     90  <=  180   90  0.0  90.0000
4    180  <=  180    0  0.0  45.0000
5    150  <=  150    0  0.7  55.7143
6    150  <=  150    0  0.0  30.0000
7    150  <=  150    0  0.3  20.0000

All Variables (including slack variables)
    opt cvec min.c max.c marg marg.reg
1   130  0.3   0.0   Inf   NA       NA
2   165  0.4  -Inf   0.8   NA       NA
3    90  0.1   0.0   Inf   NA       NA
4   180  0.2  -Inf   Inf   NA       NA
S 1  50  0.0    NA   0.3  0.0       NA
S 2  15  0.0  -0.4   Inf  0.0       NA
S 3  90  0.0  -Inf   0.1  0.0       NA
S 4   0  0.0  -Inf   0.0  0.0  45.0000
S 5   0  0.0  -Inf   0.7 -0.7  55.7143
S 6   0  0.0  -Inf   0.0  0.0  30.0000
S 7   0  0.0  -Inf   0.3 -0.3  20.0000
A skoro jest więcej możliwości, to można by jeszcze zminimalizować zużycie paliwa. Ale to już inna bajka. I inny problem programowania liniowego.
korki_fizyka
Expert
Expert
Posty: 6261
Rejestracja: 04 lip 2014, 14:55
Podziękowania: 83 razy
Otrzymane podziękowania: 1523 razy
Płeć:

Re: Maksymalizacja funkcji

Post autor: korki_fizyka »

Czy trzeba wytaczać działa aby rozwiązać ten logiczny problem? Aby przejechać najszybciej całą trasę, czyli żeby prędkość średnia była największa dobrze by było jechać cały czas z największą dopuszczalną szybkością czyli 180 km/h ale skoro na następnym odcinku trzeba by zwolnić tak aby średnia na tych dwu odcinkach wyniosła max 150 km/h, to wydaje się logiczne, że należy jechać cały czas z tą dolną wartością żeby ciągle nie przyspieszać i nie zwalniać.
Pomoc w rozwiązywaniu zadań z fizyki, opracowanie statystyczne wyników "laborek", przygotowanie do klasówki, kolokwium, matury z matematyki i fizyki itd.
mailto: korki_fizyka@tlen.pl
grdv10
Fachowiec
Fachowiec
Posty: 1039
Rejestracja: 04 sty 2020, 12:47
Podziękowania: 9 razy
Otrzymane podziękowania: 388 razy
Płeć:

Re: Maksymalizacja funkcji

Post autor: grdv10 »

korki_fizyka pisze: 18 mar 2021, 19:45 Czy trzeba wytaczać działa aby rozwiązać ten logiczny problem? Aby przejechać najszybciej całą trasę, czyli żeby prędkość średnia była największa dobrze by było jechać cały czas z największą dopuszczalną szybkością czyli 180 km/h ale skoro na następnym odcinku trzeba by zwolnić tak aby średnia na tych dwu odcinkach wyniosła max 150 km/h, to wydaje się logiczne, że należy jechać cały czas z tą dolną wartością żeby ciągle nie przyspieszać i nie zwalniać.
Zanim będziesz wytaczać argument prostej logiki, podaj tą metodą rozwiązanie optymalne. Gdyby to było takie proste jak mówisz, na co nam w ogóle programowanie liniowe?

A może zrobimy jakąś nową matematykę... prostszą, bez zbędnych metod jak tutaj simplex, czy gradient descent, czy metoda Simpsona w całkowaniu przybliżonym itd. itp. :)
korki_fizyka
Expert
Expert
Posty: 6261
Rejestracja: 04 lip 2014, 14:55
Podziękowania: 83 razy
Otrzymane podziękowania: 1523 razy
Płeć:

Re: Maksymalizacja funkcji

Post autor: korki_fizyka »

Wydaje mi się logiczne to co przedstawiłem. Należałoby porównywać kolejne dwa odcinki trasy i liczyć średnie i ciągle "zjeżdżać" z nią do wartości 150 jeśli przypadkiem nadepnęlibyśmy mocniej na pedał gazu więc LOGICZNE wydaje mi się, żeby od razu wziąć tę wartość (150) za optymalną. Co innego gdyby zakres zmienności szybkości był dowolny lub tylko miał ograniczenie z góry.
Pomoc w rozwiązywaniu zadań z fizyki, opracowanie statystyczne wyników "laborek", przygotowanie do klasówki, kolokwium, matury z matematyki i fizyki itd.
mailto: korki_fizyka@tlen.pl
grdv10
Fachowiec
Fachowiec
Posty: 1039
Rejestracja: 04 sty 2020, 12:47
Podziękowania: 9 razy
Otrzymane podziękowania: 388 razy
Płeć:

Re: Maksymalizacja funkcji

Post autor: grdv10 »

To jest logiczne. I na tej intuicji zasadza się idea metody simplex. Od jakiegoś rozwiązania dopuszczalnego to lepszego. Ona na każdym kroku poprawia jakość rozwiązania.

Rozwiązanie układu ostatnich trzech równań (postulujesz maksymalne prędkości odcinkowe) będzie z jednym parametrem. No i teraz kwestia określenia, jakie rozwiązania spełniają wszystkie kryteria. Ale też mamy uzasadnienie, że - jak mówią moje oba rozwiązania - problem ma nieskończenie wiele rozwiązań optymalnych.

Mamy wtedy\[x_1=\dfrac{750-2x_4}{3},\quad x_2=\dfrac{x_4+150}{2},\quad x_3=-2x_4+450.\]Analizując oba moje rozwiązania: to z Maximy, i to z R, wstawiając odpowiednie \(x_4\), wszystko się zgadza.

Tak więc pozostaje podziękować za głos w dyskusji. Argument był rzeczywiście logiczny.

Matematyzacja zagadnienia - tak jak w moim poście - tego nie przeskoczymy. Ale tym razem sposób rozwiązania podany przez Ciebie nie wymagał użycia metody simplex, a ponadto pokazał, że jest nieskończenie wiele rozwiązań.

Masz ode mnie dwie łapki.
korki_fizyka
Expert
Expert
Posty: 6261
Rejestracja: 04 lip 2014, 14:55
Podziękowania: 83 razy
Otrzymane podziękowania: 1523 razy
Płeć:

Re: Maksymalizacja funkcji

Post autor: korki_fizyka »

Czasem wystarczy mieć tylko trochę oleju w głowie :)
Pomoc w rozwiązywaniu zadań z fizyki, opracowanie statystyczne wyników "laborek", przygotowanie do klasówki, kolokwium, matury z matematyki i fizyki itd.
mailto: korki_fizyka@tlen.pl
ODPOWIEDZ