Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 25. 05. 2018 15:33

hynekp1
Zelenáč
Příspěvky: 3
Škola: ČVUT FS
Pozice: projektant
Reputace:   
 

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: 29795
Škola: MITHT (abs. 1986)
Pozice: plním požadavky ostatních
Reputace:   89 
 

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

hynekp1
Zelenáč
Příspěvky: 3
Škola: ČVUT FS
Pozice: projektant
Reputace:   
 

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: 29795
Škola: MITHT (abs. 1986)
Pozice: plním požadavky ostatních
Reputace:   89 
 

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

 

#5 16. 07. 2018 13:12

hynekp1
Zelenáč
Příspěvky: 3
Škola: ČVUT FS
Pozice: projektant
Reputace:   
 

Re: kombinace utahovaček při min. ceně

Dobrý den.

k b):
předepsaný počet šroubů ano, ale pořadí se může měnit.
Řešením je vybavení utahováček na operaci, to se ale může měnit viz příklad na začátku.

Díky a pěkný den

Offline

 

#6 16. 07. 2018 16:11

MichalAld
Příspěvky: 944
Reputace:   27 
 

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: 29795
Škola: MITHT (abs. 1986)
Pozice: plním požadavky ostatních
Reputace:   89 
 

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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson