#1 25. 05. 2018 15:33
kombinace utahovaček při min. ceně
Vyrábím výrobek kde je nutno zašroubovat 3 šrouby. K tomu mám k dispozici 3 typy utahovaček, kde různé typy umí zašroubovat různé šrouby. Vzhledem k výrobní kapacitě vím, že abych byl schopen vyrobit požadovaný výrobek, musím mít 2 výrobní operace, takže potřebuji 2 utahovačky.
Šroub 1 Šroub 2 Šroub 3 Cena [Kč]
UT 1 ano ano ne 100
UT 2 ano ne ano 200
UT 3 ano ano ano 100
Cílem je najít takovou kombinaci 2ks utahovaček, aby cena byla minimální.
Existují 2 řešení:
• UT1 + UT3
• UT3 + UT3
Potřeboval bych poradit, jak tuto úlohu spočítat matematicky. Toto je jednoduchý příklad, ale když utahovaček bude 50ks a šroubů bude 1500, tak už to bude trochu složité.
Offline
#2 27. 05. 2018 09:22
- jelena
- Jelena
- Místo: Opava
- Příspěvky: 30020
- Škola: MITHT (abs. 1986)
- Pozice: plním požadavky ostatních
- Reputace: 100
Re: kombinace utahovaček při min. ceně
Zdravím,
mohla bych poprosit o upřesnění?
a) cena v tabulce je cena za 1 utahovák (ten, který je uveden v řádce),
b) "potřebuji 2 operace" - rozumí se, že v každé operaci mohu utahovat šrouby všech uvedených typů a tedy pro každou operaci potřebuji kompletní sadu utahováků (např. že takovou kompletní sadou vybavím pracovníka provádějícího 1. operaci a stejnou sadou - pracovníka provádějícího 2. operaci)? Potom bych počet operací neřešila a sada utahováků se bude sestavovat na 1 operaci (na závěr se vypočte celkový počet sad). Jiná situace je, pokud operace se vztahuje k použití určitého typu utahováku (ale z "existují 2 řešení..." bych rozuměla, že stačí sestavit sadu utahováků pro 1 operaci).
Prosím tedy o upřesnění (popř. o vymyšlený příklad se sestavení nábytku z nesestaveného stavu, to snad prováděl skoro každý a půjde to lépe představit). Děkuji.
Offline
#3 29. 05. 2018 12:42
Re: kombinace utahovaček při min. ceně
Pěkný den.
a) ano, cena je za jednu utahovačku, co řádek, to jiná cena
b) "potřebuji 2 operace" - znamená, že pro utažení všech šroubů v daném výrobním taktu potřebuji 2ks utahovaček, mezi které se šroubové spoje rozdělí (př. když bude výrobní takt linky 10s, zvládnu za těchto 10s zašroubovat jen 2 spoje. Proto budu potřebovat dalších 10s pro zašroubování zbylého. 2 výrobní operace, takže 2ks utahovaček)
Snad jsem to popsal srozumitelně :-)
Offline
#4 29. 05. 2018 13:22
- jelena
- Jelena
- Místo: Opava
- Příspěvky: 30020
- Škola: MITHT (abs. 1986)
- Pozice: plním požadavky ostatních
- Reputace: 100
Re: kombinace utahovaček při min. ceně
↑ hynekp1:
děkuji, a) je jasné.
K b): v daném výrobním taktu provedu určitý počet operací, čímž technologický krok považuji za ukončený. V každé operaci (která trvá přesně danou dobu) umím (mám stihnout) zašroubovat jen přesně daný počet šroubů v přesně daném pořadí. Potom řeším jen vybavení utahováků na každou operaci.
V čem je variabilita procesu? Děkuji a pozdrav.
Offline
#6 16. 07. 2018 16:11
Re: kombinace utahovaček při min. ceně
Je docela možné, že to patří mezi nějaké formy NP problému. To by znamenalo, že neexistuje žádný efektivní algoritmus jak optimální řešení vyhledat. A zbývá jen vyzkoušet všechny možné kombinace.
Takových problémů je celá řada, jednoduše pochopitelný je třeba "problém batohu". Víme že batoh obsahuje několik závaží (o známých hmotnostech, třeba 1kg, 3kg, 15kg, 21kg....), celkem váží třeba 7 tun (je to "matematický batoh"), máme zjistit, jaká závaží obsahuje. Na to taky "hezký" postup neexistuje, musíme vyzkoušet všechny možnosti.
Nevím, jestli tvůj problém spadá do kategorie "těžkých NP problémů". NP problém je obecně každý, kde když uhádneme nějaké řešení, můžeme snadno zkusit, jestli je správné. V tvém případě jestli je zvolená kombinace utahovaček funkční, a levnější než nějaké zvolené číslo.
Offline
#7 16. 07. 2018 22:32
- jelena
- Jelena
- Místo: Opava
- Příspěvky: 30020
- Škola: MITHT (abs. 1986)
- Pozice: plním požadavky ostatních
- Reputace: 100
Re: kombinace utahovaček při min. ceně
Zdravím,
↑ MichalAld: ano, na nějaký párovací problém to vypadá a uvažuji, jak by šlo nasadit některou metodu lineárního programování. Zkusím popsat ruční postup, třeba se ještě upřesní (pořadí utahování šroubu se mi nezdá zatím jako vlivný moment k úvaze, snad ještě upřesnit).
Ručně bych provedla tak, že do sloupců tabulky dám šrouby, do řádku utahováky (stejně, jak v 1. příspěvku), označím 1 - utahovák vhodný pro šroub, 0 - nevhodný. Potom součet v řádku mi dává počet šroubů, co mohu ošetřit jedním utahovákem. Ve sloupci - počet utahováků vhodných pro určitý šroub. Začnu od šroubu s nejmenší variabilitou utahováků: pokud je jen 1 utahovák, to je jasné. Pokud je více, zvolím ten, který pokrývá více šroubu. Vyškrtnu všechny šrouby, co jsem již zašroubovala a jdu k dalšímu šroubu s aktuálně minimálním počtem utahováků.
Měla bych ještě doplnit cenu utahováku - v řádku s celkovým počtem utažených šroubů podělím cenu utahováku počtem možných utažení šroubů, to mi vyjde cena na utažení. Měla bych to zohlednit při předchozím kroku volbu (pokrývá více šroubů nebo cena na šroub je minimální).
↑ hynekp1: děkuji za upřesnění. Popisuji alespoň přibližně to, co je požadováno řešit? Algoritmické řešení - viz kolega ↑ MichalAld: (tedy pokud z některého upřesnění nevzejde formulace úlohy lineárního programování nebo jiného způsobu optimální úlohy, uvidíme).
Offline