Strona 1 z 3

optymalizacja - problem szafy na zakręcie

: 5 maja 2019, o 17:00
autor: MariuszJ
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?

optymalizacja - problem szafy na zakręcie

: 5 maja 2019, o 17:57
autor: janusz47
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.}\).

Re: optymalizacja - problem szafy na zakręcie

: 5 maja 2019, o 19:28
autor: MariuszJ
Ale ten wzór nie uwzględnia grubości szafy. Im grubsza szafa tym musi być krótsza.

optymalizacja - problem szafy na zakręcie

: 5 maja 2019, o 19:50
autor: janusz47
Nie uwzględnia. Co to jest grubość szafy?

Re: optymalizacja - problem szafy na zakręcie

: 5 maja 2019, o 19:55
autor: MariuszJ
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.

optymalizacja - problem szafy na zakręcie

: 5 maja 2019, o 20:05
autor: janusz47
Ten wzór jest zależny tylko od długości: szafy, statku, kija, deski ...

Re: optymalizacja - problem szafy na zakręcie

: 5 maja 2019, o 20:11
autor: Premislav
No to nie ma on tutaj zastosowania, jeśli nie pomijamy szerokości. Moje pierwsze skojarzenie jest z tym wątkiem: 376560.htm

optymalizacja - problem szafy na zakręcie

: 6 maja 2019, o 09:26
autor: mdd
Premislav pisze: Moje pierwsze skojarzenie jest z tym wątkiem: 376560.htm
Ostatni post wydaje się być rozwiązaniem problemu, tylko rysunki diabli zabrali.

optymalizacja - problem szafy na zakręcie

: 6 maja 2019, o 09:56
autor: MariuszJ
janusz47 pisze:Ten wzór jest zależny tylko od długości: szafy, statku, kija, deski ...
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ął.

optymalizacja - problem szafy na zakręcie

: 7 maja 2019, o 23:28
autor: mdd
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

: 8 maja 2019, o 09:20
autor: MariuszJ
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?

optymalizacja - problem szafy na zakręcie

: 19 maja 2019, o 12:57
autor: mdd
Poszukaj w sieci, w literaturze, informacji o obwiedni rodziny krzywych \(\displaystyle{ F\left( x,y, \alpha\right)=0}\)

optymalizacja - problem szafy na zakręcie

: 14 cze 2019, o 16:30
autor: MariuszJ
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

optymalizacja - problem szafy na zakręcie

: 19 cze 2019, o 17:00
autor: mdd
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.
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.

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

: 21 cze 2019, o 08:48
autor: MariuszJ
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.