optymalizacja - problem szafy na zakręcie
optymalizacja - problem szafy na zakręcie
Mamy korytarz, który zakręca pod kątem 90 stopni. Część przed zakrętem może mieć inną szerokość niż część za zakrętem, czyli wierzchołek wewnętrzny zakrętu może nie być położony na dwusiecznej kąta na którym leży wierzchołek zewnętrzny. Mamy szafę w postaci prostokąta. Znamy jeden wymiar szafy, grubość albo szerokość. Mamy podać największą długość nieznanego wymiaru szafy, żeby ta szafa jeszcze zmieściła się na zakręcie żeby ją przetransportować poza ten zakręt do dalszej części korytarza.
Czy to się da obliczyć układając równania i na przykład biorąc maksimum funkcji, jak to po kolei zrobić?
Czy też może taki problem nie może być równaniami obliczony i potrzebne jest programowanie liniowe żeby wyznaczyć maksimum równania macierzowego algorytmem próbkującym?
Czy to się da obliczyć układając równania i na przykład biorąc maksimum funkcji, jak to po kolei zrobić?
Czy też może taki problem nie może być równaniami obliczony i potrzebne jest programowanie liniowe żeby wyznaczyć maksimum równania macierzowego algorytmem próbkującym?
-
- Użytkownik
- Posty: 7917
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
optymalizacja - problem szafy na zakręcie
Jest to problem optymalizacyjny
Jeżeli przez \(\displaystyle{ l}\) oznaczymy długość szafy , przez \(\displaystyle{ a,}\) część korytarza przed zakrętem a przez \(\displaystyle{ b}\) szerokość korytarza po zakręcie, to zachodzi równość (rys.)
\(\displaystyle{ l = \frac{a}{\sin(\phi)} + \frac{b}{\cos(\phi)}\ \ (1)}\)
Proszę zbadać ekstremum lokalne funkcji \(\displaystyle{ (1)}\) i stwierdzić, że przyjmuje ona wartość minimalną dla \(\displaystyle{ \phi^{*} = \arctg \sqrt[3]{\frac{b}{a}}}\)
i
\(\displaystyle{ l_{max} = \left(a^{\frac{2}{3}}+ b^{\frac{2}{3}}\right)^{\frac{3}{2}}\ \ m.}\).
Jeżeli przez \(\displaystyle{ l}\) oznaczymy długość szafy , przez \(\displaystyle{ a,}\) część korytarza przed zakrętem a przez \(\displaystyle{ b}\) szerokość korytarza po zakręcie, to zachodzi równość (rys.)
\(\displaystyle{ l = \frac{a}{\sin(\phi)} + \frac{b}{\cos(\phi)}\ \ (1)}\)
Proszę zbadać ekstremum lokalne funkcji \(\displaystyle{ (1)}\) i stwierdzić, że przyjmuje ona wartość minimalną dla \(\displaystyle{ \phi^{*} = \arctg \sqrt[3]{\frac{b}{a}}}\)
i
\(\displaystyle{ l_{max} = \left(a^{\frac{2}{3}}+ b^{\frac{2}{3}}\right)^{\frac{3}{2}}\ \ m.}\).
Re: optymalizacja - problem szafy na zakręcie
Ale ten wzór nie uwzględnia grubości szafy. Im grubsza szafa tym musi być krótsza.
Re: optymalizacja - problem szafy na zakręcie
Pisałem na początku, że szafa jest prostokątem. Jeśli liczymy długość szafy, to drugi bok prostokąta jest podany w postaci stałej.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: optymalizacja - problem szafy na zakręcie
No to nie ma on tutaj zastosowania, jeśli nie pomijamy szerokości. Moje pierwsze skojarzenie jest z tym wątkiem: 376560.htm
- mdd
- Użytkownik
- Posty: 1897
- Rejestracja: 14 kwie 2013, o 10:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 512 razy
optymalizacja - problem szafy na zakręcie
Ostatni post wydaje się być rozwiązaniem problemu, tylko rysunki diabli zabrali.Premislav pisze: Moje pierwsze skojarzenie jest z tym wątkiem: 376560.htm
optymalizacja - problem szafy na zakręcie
No, nawet intuicyjnie widać, że jeśli szafa stanowi odcinek, to nie jest to to samo, gdy mamy szafę grubą. Gruba szafa będzie się klinować na zakręcie podczas gdy odcinek jeszcze przejdzie. Chodzi o to, że odcinek i prostokąt liczymy inaczej. Prostokąt liczymy tak, że zamiast obliczeń dla odcinka który opiera się na obu osiach (wierzchołki boków szafy dotykają zewnętrznych ścian korytarza), bierzemy obliczenia pozycji odcinka równoległego do niego (o tej samej długości) który jest bliżej wewnętrznego rogu i nie opiera się na osiach. To on styka się z rogiem który go klinuje. Jest to na tyle proste że nie musze tego wyjaśniać graficznie. Tym samym poprzedni wzór trzeba poprawić. On i tak wyszedł skomplikowany no to teraz będzie już wyglądał jak koszmarnie trudny. Nawet nie pytam skąd się ten wzór wziął.janusz47 pisze:Ten wzór jest zależny tylko od długości: szafy, statku, kija, deski ...
- mdd
- Użytkownik
- Posty: 1897
- Rejestracja: 14 kwie 2013, o 10:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 512 razy
optymalizacja - problem szafy na zakręcie
Rysunki ocalały
Załóżmy, że wierzchołek \(\displaystyle{ A}\) (o długości \(\displaystyle{ L}\) i szerokości \(\displaystyle{ s}\)) porusza się cały czas po osi pionowej, zaś wierzchołek \(\displaystyle{ B}\) - po osi poziomej. Należy rozważyć sposób poruszania się punktu \(\displaystyle{ P(x_{\lambda},y_{\lambda})}\) na prostej \(\displaystyle{ l}\), zawierającej jeden z boków szafy. Analizując rysunek otrzymujemy współrzędne tego punktu:
\(\displaystyle{ x_{\lambda}=\left( L-\lambda\right) \cdot \cos\alpha+s \cdot \sin \alpha \\
y_{\lambda}=\lambda \cdot \sin \alpha + s \cdot \cos \alpha}\)
gdzie: \(\displaystyle{ 0\le \lambda \le L}\)
Dochodzimy też do wniosku, że równanie rodziny prostych \(\displaystyle{ l}\) przedstawia się następująco:
\(\displaystyle{ y \cos \alpha+ x \sin \alpha=s+L \sin \alpha \cos \alpha}\)
Obwiednia powyższej rodziny prostych oraz obwiednia trajektorii zakreślanych przez punkt \(\displaystyle{ P(x_{\lambda},y_{\lambda})}\) ma równania parametryczne:
\(\displaystyle{ x=s \cdot \sin \alpha+L \cdot \cos^3 \alpha \\
y=s \cdot \cos \alpha+L \cdot \sin^3 \alpha}\)
(prawie Asteroida)
Re: optymalizacja - problem szafy na zakręcie
Jak rozumiem nie wiadomo z góry który punkt boku wewnętrznego zetknie się z rogiem wewnętrznym korytarza (przy założeniu że szafa ma wymiar na styk) bo każdy ten punkt przesuwa się według innego wykresu krzywej, ale jak zróżniczkujemy te równania to miejsce zerowe pochodnej będzie rozwiązaniem?
- mdd
- Użytkownik
- Posty: 1897
- Rejestracja: 14 kwie 2013, o 10:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 512 razy
optymalizacja - problem szafy na zakręcie
Poszukaj w sieci, w literaturze, informacji o obwiedni rodziny krzywych \(\displaystyle{ F\left( x,y, \alpha\right)=0}\)
optymalizacja - problem szafy na zakręcie
Ten problem był kiedyś omawiany na zawodach informatycznych.
... Movers.htm
Wygląda na to, że nie potrafili określić wzoru i rozwiązywali zadanie przez próbkowanie. Autor pyta czy znamy wzór. Niestety on niedawno zmarł. Gary Darby
... Movers.htm
Wygląda na to, że nie potrafili określić wzoru i rozwiązywali zadanie przez próbkowanie. Autor pyta czy znamy wzór. Niestety on niedawno zmarł. Gary Darby
- mdd
- Użytkownik
- Posty: 1897
- Rejestracja: 14 kwie 2013, o 10:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 512 razy
optymalizacja - problem szafy na zakręcie
Znamy wzór w tym sensie, że zadanie sporowadzone tutaj zostało do znalezienia parametrów odpowiednio dopasowanej "prawie Asteroidy" do zadanego skrzyżowania (wpisanej w to skrzyżowanie), czyli do znalezienia par \(\displaystyle{ \left( L, s\right)}\). Otrzymujemy w efekcie układ równań, który należy rozwiązać. Oczywiście tych par będzie nieskończenie dużo.MariuszJ pisze:Ten problem był kiedyś omawiany na zawodach informatycznych.
... Movers.htm
Wygląda na to, że nie potrafili określić wzoru i rozwiązywali zadanie przez próbkowanie. Autor pyta czy znamy wzór.
Np. przy zadanej długości \(\displaystyle{ L}\) szafy i współrzędnych \(\displaystyle{ x_{o}, y_{o}}\) "wewnętrznego rogu" skrzyżowania (pardon, nie chce mi się rysować; wyobraź sobie że skrzyżowanie jest umieszczone w pierwszej ćwiartce prostokątnego układu współrzędnych) otrzymujemy układ równań:
\(\displaystyle{ x_{o}=s \cdot \sin \alpha+L \cdot \cos^3 \alpha \\ y_{o}=s \cdot \cos \alpha+L \cdot \sin^3 \alpha}\)
ze zmiennymi:
\(\displaystyle{ \alpha, s}\)
Patrząc na rysunek w linku przyszedł mi kolejny pomysł do głowy. Trochę dziwne, że autorowi strony on nie przyszedł do głowy i musiał "próbkować". Ale o tym potem.
optymalizacja - problem szafy na zakręcie
Widziałem odmianę tego zadania gdzie szafa ma nieregularny kształt. Na przykład nie jest prostokątem tylko wielobokiem z pięcioma bokami. Bok, który kontaktuje z wierzchołkiem wewnętrznym zakrętu korytarza, jest podzielony na dwa boki które nie tworzą linii prostej. Wtedy wzory matematyczne robią się tak skomplikowane że prościej jest zrobić próbkowanie.