Zadanie z optymalizacji

Pytania o rozwiązania zadań.
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Janek9003
Rozkręcam się
Rozkręcam się
Posty: 40
Rejestracja: 19 lut 2018, 16:06
Podziękowania: 18 razy
Otrzymane podziękowania: 1 raz
Płeć:

Zadanie z optymalizacji

Post autor: Janek9003 »

Metalowe pręty o długości 300 cm należy pociąć na krótsze odcinki tak, aby odpad powstały w procesie cięcia był minimalny. Zgłoszone zapotrzebowanie to:
  • 120 prętów o długości 140 cm,
  • 60 prętów o długości 110 cm,
  • 680 prętów o długości 40 cm.

Na ten moment nie znam żadnych algorytmów dlatego prosiłbym o rozwiązanie/podpowiedź używając tylko najbardziej podstawowych metod.
alicja-korepetycje
Dopiero zaczynam
Dopiero zaczynam
Posty: 24
Rejestracja: 10 lut 2011, 23:15
Otrzymane podziękowania: 3 razy
Płeć:
Kontakt:

Re: Zadanie z optymalizacji

Post autor: alicja-korepetycje »

Generalnie jest to temat programowania liniowego, w którym funkcja celu ma być minimalizowana.
Jest to zadanie na znalezienie odpowiednich metod cięcia, które pozwolą zrealizować zamówienia, które muszą jako nasze ograniczenia być spełnione.

Najpierw należy zapisać problem decyzyjny (zmienne decyzyjne, funkcja celu i ograniczenia), a potem wybrać odpowiednią metodę rozwiązania.

Mój film na YouTube jest tutaj na ten temat: https://youtu.be/ZYzF6j1zCAs
Powinien dać jakieś pierwsze wskazówki, jak do tego tematu podejść.

Metoda rozwiązywania to pewnie będzie simpleks [filmik liczenia ręcznie simpleksu na minimum: https://youtu.be/57pY3rQP3Os.
Wątpię, aby dało się to rozwiązać metodą graficzną, ale należałoby to po prostu sprawdzić. Simpleks jest uniwersalną metodą.
Ewentualnie rozwiązanie w programie obliczeniowym z użyciem dodatku optymalizacji, np. Solver. Przykład wykorzystania tego dodatku przy minimalizacji funkcji celu: https://youtu.be/npNTlbhAWbo
kerajs
Fachowiec
Fachowiec
Posty: 2963
Rejestracja: 14 lis 2016, 14:38
Podziękowania: 33 razy
Otrzymane podziękowania: 1303 razy
Płeć:

Re: Zadanie z optymalizacji

Post autor: kerajs »

30 prętów tniesz na: 110+110+40+40=300
120 prętów tniesz na: 140+40+40+40+40=300
20 prętów tniesz na: 40+40+40+40+40+40+40+20=300
odpady są tylko w ostatnich 20 prętach.
alicja-korepetycje
Dopiero zaczynam
Dopiero zaczynam
Posty: 24
Rejestracja: 10 lut 2011, 23:15
Otrzymane podziękowania: 3 razy
Płeć:
Kontakt:

Re: Zadanie z optymalizacji

Post autor: alicja-korepetycje »

odcinki\metoda cięcia X1 X2 X3 X4 minimalna liczba sztuk
140: 2*X1 +1*X2 + 0*X3 + 0*X4 ≥ 120
110: 0*X3+ 1*X2+ 2*X3+ 1*X4 ≥ 60
40: 0*X1+ 1*X2+ 2*X3+ 4*X4 ≥ 680
Odpad w cm (=> min): 20*X1+ 10*X2+ 0*X3+ 30*X4
X1 ≥ 0, X2 ≥ 0, X3 ≥ 0, X4 ≥ 0


Zmienne decyzyjne:
X1 – liczba zastosowań I metody cięcia
X2 – liczba zastosowań II metody cięcia
X3 – liczba zastosowań III metody cięcia
X4 – liczba zastosowań IV metody cięcia

Funkcja celu z= 20x1 + 10x2 + 30x4 → min

Ograniczenia:
(1) 2x1 + x2 ≥ 120
(2) x2 + 2x3 + x4 ≥ 60
(3) x2 + 2x3 + 4x4 ≥ 680
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

Mamy 4 zmienne decyzyjne, a 3 ograniczenia, więc albo simpleks, albo narzędzie optymalizacyjne typu Solver.
Ostatnio zmieniony 09 paź 2019, 22:32 przez alicja-korepetycje, łącznie zmieniany 1 raz.
korki_fizyka
Expert
Expert
Posty: 6261
Rejestracja: 04 lip 2014, 14:55
Podziękowania: 83 razy
Otrzymane podziękowania: 1523 razy
Płeć:

Re: Zadanie z optymalizacji

Post autor: korki_fizyka »

Jak dla mnie jest to proste zadanie na zdroworozsądkowe logiczne myślenie, które od małego należy kształtować i ćwiczyć czytając np. Jeleńskiego Lilavati czy Śladami Pitagorasa oraz rozwiązując zagadki logiczne np. Kowala.
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
alicja-korepetycje
Dopiero zaczynam
Dopiero zaczynam
Posty: 24
Rejestracja: 10 lut 2011, 23:15
Otrzymane podziękowania: 3 razy
Płeć:
Kontakt:

Re: Zadanie z optymalizacji

Post autor: alicja-korepetycje »

To typowe zadanie z programowania liniowego w ramach przedmiotu o nazwie Badania operacyjne (alternatywnie: Ekonometria).
To zadanie dla studentów kierunków ekonomicznych. :)
korki_fizyka
Expert
Expert
Posty: 6261
Rejestracja: 04 lip 2014, 14:55
Podziękowania: 83 razy
Otrzymane podziękowania: 1523 razy
Płeć:

Re: Zadanie z optymalizacji

Post autor: korki_fizyka »

Janek studiujesz ekonomię ?
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
radagast
Guru
Guru
Posty: 17549
Rejestracja: 09 lis 2010, 07:38
Lokalizacja: Warszawa
Podziękowania: 41 razy
Otrzymane podziękowania: 7435 razy
Płeć:

Re: Zadanie z optymalizacji

Post autor: radagast »

Niekoniecznie... Patrz zbiór zadań dla 2 klasy liceum , wyd. Pazdro, Kurczab Świda zadania 1.207-1.221.
W dzisiejszych czasach, bez programowania liniowego ani rusz :)
korki_fizyka
Expert
Expert
Posty: 6261
Rejestracja: 04 lip 2014, 14:55
Podziękowania: 83 razy
Otrzymane podziękowania: 1523 razy
Płeć:

Re: Zadanie z optymalizacji

Post autor: korki_fizyka »

radagast pisze: 10 paź 2019, 07:09 Niekoniecznie... Patrz zbiór zadań dla 2 klasy liceum , wyd. Pazdro, Kurczab Świda zadania 1.207-1.221.
W dzisiejszych czasach, bez programowania liniowego ani rusz :)
Programowanie liniowe = myślenie + olej w głowie do smarowania trybików ;)
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
Janek9003
Rozkręcam się
Rozkręcam się
Posty: 40
Rejestracja: 19 lut 2018, 16:06
Podziękowania: 18 razy
Otrzymane podziękowania: 1 raz
Płeć:

Re: Zadanie z optymalizacji

Post autor: Janek9003 »

korki_fizyka pisze: 09 paź 2019, 22:45 Janek studiujesz ekonomię ?
Informatyka.

Na ten moment znam już sympleks, niby są to tylko algorytmy więc nawet jak się tego nie rozumie zawsze można to po prostu wkuć, ale problem mam z rozpisaniem zadania tekstowego.
Aczkolwiek widzę, że już tutaj kilka osób to rozpisało to może do rozwiązania dotrę. Niestety nie mam odpowiedzi to się nie dowiem czy jest dobrze.
Janek9003
Rozkręcam się
Rozkręcam się
Posty: 40
Rejestracja: 19 lut 2018, 16:06
Podziękowania: 18 razy
Otrzymane podziękowania: 1 raz
Płeć:

Re: Zadanie z optymalizacji

Post autor: Janek9003 »

alicja-korepetycje pisze: 09 paź 2019, 20:34 odcinki\metoda cięcia X1 X2 X3 X4 minimalna liczba sztuk
140: 2*X1 +1*X2 + 0*X3 + 0*X4 ≥ 120
110: 0*X3+ 1*X2+ 2*X3+ 1*X4 ≥ 60
40: 0*X1+ 1*X2+ 2*X3+ 4*X4 ≥ 680
Odpad w cm (=> min): 20*X1+ 10*X2+ 0*X3+ 30*X4
X1 ≥ 0, X2 ≥ 0, X3 ≥ 0, X4 ≥ 0


Zmienne decyzyjne:
X1 – liczba zastosowań I metody cięcia
X2 – liczba zastosowań II metody cięcia
X3 – liczba zastosowań III metody cięcia
X4 – liczba zastosowań IV metody cięcia

Funkcja celu z= 20x1 + 10x2 + 30x4 → min

Ograniczenia:
(1) 2x1 + x2 ≥ 120
(2) x2 + 2x3 + x4 ≥ 60
(3) x2 + 2x3 + 4x4 ≥ 680
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

Mamy 4 zmienne decyzyjne, a 3 ograniczenia, więc albo simpleks, albo narzędzie optymalizacyjne typu Solver.
Czy mógłbym prosić o dokładniejsze wyjaśnienie? Nie jestem w stanie zrozumieć skąd to się wzięło, czemu 4 zmienne itd. Algorytm +- znam, na internecie jest nawet dostępny, w wielu "wariantach", samo rozpisanie zadania jest problemem.
alicja-korepetycje
Dopiero zaczynam
Dopiero zaczynam
Posty: 24
Rejestracja: 10 lut 2011, 23:15
Otrzymane podziękowania: 3 razy
Płeć:
Kontakt:

Re: Zadanie z optymalizacji

Post autor: alicja-korepetycje »

Metalowe pręty o długości 300 cm należy pociąć na krótsze odcinki tak, aby odpad powstały w procesie cięcia był minimalny. Zgłoszone zapotrzebowanie to:
120 prętów o długości 140 cm,
60 prętów o długości 110 cm,
680 prętów o długości 40 cm.

Mając 1 pręt o długości 300 cm maksymalnie prętów o długości 140 cm można wykonać 2 (zostanie 20 cm odpadu), a innych prętów nie wykonamy, a więc: z tej 1. metody cięcia można wyprodukować odpowiednio prętów o długości 140 cm - 2 szt., o długości 110 cm - 0 szt., o długości 40 cm - 0 szt.

Teraz zmniejszamy rozważaną liczbę prętów o długości 140 cm do 1 szt. Z 300 cm zostanie 160 cm na pozostałe pręty, a więc: z tej 2. metody cięcia można wyprodukować odpowiednio prętów o długości 110 cm - 1 szt., zostanie więc 50 cm do wykorzystania na pręty o długości 40 cm - 1 szt. wyjdzie maksymalnie i zostanie odpad = 10 cm.
A więc: z tej 2. metody cięcia można wyprodukować odpowiednio prętów o długości 140 cm - 1 szt., o długości 110 cm - 1 szt., o długości 40 cm - 1 szt.

Teraz nie rozważamy już prętów o długości 140 cm - liczba tych prętów niech wynosi 0 szt. Z 300 cm zostanie 300 cm na pozostałe pręty, a więc: z tej 3. metody cięcia można wyprodukować odpowiednio prętów o długości 110 cm - 2 szt., zostanie więc 80 cm do wykorzystania na pręty o długości 40 cm - 2 szt. wyjdą maksymalnie i zostanie odpad = 0 cm.
A więc: z tej 3. metody cięcia można wyprodukować odpowiednio prętów o długości 140 cm - 0 szt., o długości 110 cm - 2 szt., o długości 40 cm - 2 szt.

Dalej nadal nie rozważamy już prętów o długości 140 cm - liczba tych prętów niech wynosi 0 szt. Z 300 cm zostanie 300 cm na pozostałe pręty, a więc: z tej 4. metody cięcia chcemy wyprodukować mniej prętów o długości 110 cm - 1 szt., zostanie więc 190 cm do wykorzystania na pręty o długości 40 cm - 4 szt. wyjdą maksymalnie i zostanie odpad = 30 cm.
A więc: z tej 4. metody cięcia można wyprodukować odpowiednio prętów o długości 140 cm - 0 szt., o długości 110 cm - 1 szt., o długości 40 cm - 4 szt.

Metod można doszukiwać się więcej - najbardziej efektywne się liczą.
np. niewypisana przeze mnie metoda 5. jest lepsza niż 4.:
Z 4. metody cięcia można wyprodukować odpowiednio prętów o długości 140 cm - 1 szt., o długości 110 cm - 0 szt., o długości 40 cm - 4 szt. Odpad daje = 0 cm.

Lepiej jest eliminować te metody, które dają wyższy odpad niż inne, a więc metoda 4. powinna być zastąpiona metodą 5.

140: 2*X1 +1*X2 + 0*X3 + 1*X4 ≥ 120
110: 0*X3+ 1*X2+ 2*X3+ 0*X4 ≥ 60
40: 0*X1+ 1*X2+ 2*X3+ 4*X4 ≥ 680
Odpad w cm (=> min): 20*X1+ 10*X2+ 0*X3+ 0*X4
X1 ≥ 0, X2 ≥ 0, X3 ≥ 0, X4 ≥ 0
Załączniki
Najlepiej to w xls rozpisać. Rozpisywanie idzie sprawniej.
Najlepiej to w xls rozpisać. Rozpisywanie idzie sprawniej.
ODPOWIEDZ