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?
Maksymalizacja funkcji
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Fachowiec
- Posty: 1039
- Rejestracja: 04 sty 2020, 12:47
- Podziękowania: 9 razy
- Otrzymane podziękowania: 388 razy
- Płeć:
Re: Maksymalizacja funkcji
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:
Jak widać, maksymalizowałem tam licznik, więc maksymalna prędkość średnia to właśnie 150.
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]]
-
- Fachowiec
- Posty: 1039
- Rejestracja: 04 sty 2020, 12:47
- Podziękowania: 9 razy
- Otrzymane podziękowania: 388 razy
- Płeć:
Re: Maksymalizacja funkcji
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.
Output jest dość skomplikowany, ale interesuje nas pierwszych kilka linijek.
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.
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)
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
-
- Expert
- Posty: 6272
- Rejestracja: 04 lip 2014, 14:55
- Podziękowania: 83 razy
- Otrzymane podziękowania: 1523 razy
- Płeć:
Re: Maksymalizacja funkcji
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
mailto: korki_fizyka@tlen.pl
-
- Fachowiec
- Posty: 1039
- Rejestracja: 04 sty 2020, 12:47
- Podziękowania: 9 razy
- Otrzymane podziękowania: 388 razy
- Płeć:
Re: Maksymalizacja funkcji
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?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ć.
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.
-
- Expert
- Posty: 6272
- Rejestracja: 04 lip 2014, 14:55
- Podziękowania: 83 razy
- Otrzymane podziękowania: 1523 razy
- Płeć:
Re: Maksymalizacja funkcji
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
mailto: korki_fizyka@tlen.pl
-
- Fachowiec
- Posty: 1039
- Rejestracja: 04 sty 2020, 12:47
- Podziękowania: 9 razy
- Otrzymane podziękowania: 388 razy
- Płeć:
Re: Maksymalizacja funkcji
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.
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.
-
- Expert
- Posty: 6272
- Rejestracja: 04 lip 2014, 14:55
- Podziękowania: 83 razy
- Otrzymane podziękowania: 1523 razy
- Płeć:
Re: Maksymalizacja funkcji
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
mailto: korki_fizyka@tlen.pl