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. 11. 2019 18:48

jankincl
Zelenáč
Příspěvky: 2
Škola: Univerzita Pardubice, FCHT
Pozice: Programátor PLC
Reputace:   
 

Rozdělení výrobní kapacity na 20 strojů

Dobrý den,
jsem programátor PLC a stojím před zajímavou úlohou. Zákazník má dvacet strojů, které vyrábí stejnou věc s různou kapacitou a já mám vymyslet, které stroje spustit, tak aby celková kapacita výroby byla jen nezbytně nutně vyšší než je požadavek na celkovou výrobu. Stroje nelze řídit, lze je jen spustit nebo vypnout.
Zatím jsem vymyslel dva přístupy.
1. Seřadím stroje dle kapacit sestupně a postupně je spouštím až dosáhnu požadavku. Výhodou je jednoduchost a rychlost výpočtu, nevýhodou je jeho hrubost. Řešení není zdaleka optimální, ale z nouze to zatím chci použít.
2. Hrubou sílou vypočtu všechny kombinace (20!=2,43*10^15) a najdu tu nejlepší. To však nemohu použít, protože hrubé síly mám málo (jednoduché průmyslové PLC).
Zajímalo by mne, jestli je nějaká metoda, jak se dostat na slušnou přesnost s rozumnými výpočetními nároky. Programovací jazyk poskytuje standardní funkce (pole hodnot, IF podmínky, FOR, WHILE a REPEAT cykly apod.)
Zdraví a děkuje
Jan Kinčl

Offline

 

#2 25. 11. 2019 19:15

laszky
Příspěvky: 1584
Škola: MFF UK, FJFI CVUT
Reputace:   128 
 

Re: Rozdělení výrobní kapacity na 20 strojů

↑ jankincl:

Ahoj, jestli jsem to spravne pochopil, tak se jedna o neco velmi podobneho jako je problem batohu, nebo souctu podmnoziny. Mas ruzna cisla a chces najit takovy jejich soucet, ktery je nejbliz predepsanemu cislu. Mrkni na to, urcite na to jsou nejake algoritmy. Akorat se pry jedna o NP-uplny problem, takze by vypocet mohl chvili trvat. Ikdyz 20 stroju neni tak moc.

Offline

 

#3 25. 11. 2019 20:13 — Editoval check_drummer (25. 11. 2019 20:27)

check_drummer
Příspěvky: 2768
Reputace:   74 
 

Re: Rozdělení výrobní kapacity na 20 strojů

↑ jankincl:
Ahoj, můžeš si předem napočítat optimální rovržení strojů (pro všechna požadavky na výrobu, řekněme celočíselné) a někam uložit do paměti. tedy nemusíš tu optimalizaci provádět až když je zadán požadavek na výrobu.
Edit. Předpokládám, že kapacita strojů je předem známa a že požadavky na výroku předem známy nejsou.
A nebo není předem známa ani kapacita strojů?


Jak dokázat, že nelze dokázat, že dané tvrzení nelze dokázat?

Offline

 

#4 25. 11. 2019 20:30

check_drummer
Příspěvky: 2768
Reputace:   74 
 

Re: Rozdělení výrobní kapacity na 20 strojů

jankincl napsal(a):

2. Hrubou sílou vypočtu všechny kombinace (20!=2,43*10^15) a najdu tu nejlepší.

Pro tebe ale není podstatné pořadí těch strojů, jde jen o to, které budou vybrány ne? Takže všech možností je jen 2^{20}, tj. zhruba 10^6, to není tak zlé..


Jak dokázat, že nelze dokázat, že dané tvrzení nelze dokázat?

Offline

 

#5 25. 11. 2019 20:53 — Editoval MichalAld (25. 11. 2019 20:54)

MichalAld
Moderátor
Příspěvky: 2266
Reputace:   72 
 

Re: Rozdělení výrobní kapacity na 20 strojů

Jak zmínil lazsky, v plné obecnosti je to ten "problém batohu" - což je úplný NP problém, a ten úplně přesně nelze řešit jinak, než hrubou silou (nebo srovnatelně účinou metodou). To by nakonec taky nebyl problém, protože kombinací je ve skutečnosti jen milion (jak zmínil již check_drummer).

Nicméně - milion variant (i kdyby byla každá jiná) vyžaduje také znalost cyklu strojů s přesností na jednu miliontinu (1ppm) a to je úplná pitomost. No a plánování výroby s přesností na ppm je pitomost taky.

Bude úplně bohatě stačit, když to budeš mít s přesností na několik procent. Takže bych to asi řešil radikálním způsobem - udělal bych si program (ale ne v PLC, to by asi nešlo), který mi spočítá všechny ty kombinace (bude jich mega, to je celkem prd pro dnešní počítače), setřídí je podle produkce a pak z nich nějaké vybereš (abys jich měl třeba stovku - nejlépe takové, aby měli konstantní rozestupy). Tabulku přepíšeš do PLC a máš to.

Případně, pokud máš k dispozici počítač trvale to můžeš počítat vždy znova, bude to trvat jen chvíli - nejdéle asi to třídění.

Dále budeš asi muset řešit problém, že jednomu času bude (zhruba) odpovídat vícero kombinací - a budeš muset nějak rozhodnout, jestli je lepší pustit jeden rychlý nebo 3 pomalé stroje.

Offline

 

#6 25. 11. 2019 21:22

jankincl
Zelenáč
Příspěvky: 2
Škola: Univerzita Pardubice, FCHT
Pozice: Programátor PLC
Reputace:   
 

Re: Rozdělení výrobní kapacity na 20 strojů

Díky všem za nasměrování. Zkusím nejprve výpočet všech možností v PLC, milion možností by mohlo dát a je to nejjednodušší na programování. Dám vědět, jak to dopadlo.

Offline

 

#7 26. 11. 2019 16:13

MichalAld
Moderátor
Příspěvky: 2266
Reputace:   72 
 

Re: Rozdělení výrobní kapacity na 20 strojů

Záleží, co máš za PLC. Pokud máš opravdu "kvalitní" PLC, jako je OMRON či MITSUBICHI, co se musí programovat v tom jejich ladderu, tak to tam možná ani neuděláš (protože tam nejde udělat cyklus).

Pokud máš PLC vybavené nějakým rozumným jazykem (jako třeba B&R, Beckhoff), tak by to nemusel být až takový problém.

Dále - existuje celkem jednoduchý trik - totiž neprocházet všech milion kombinací, ale vybírat je náhodně ("vybírání" není zrovna názorný pojem, jde prostě o to ta čísla generovat náhodně a zkoušet je). Nezískáš sice úplně přesný výsledek - nebo až po velmi dlouhém čase, ale přibližný výsledek můžeš mít už možná po pár stovkách pokusů. A ty to nepotřebuješ mít úplně přesné, když to bude na procento či dvě, musí to stačit.

Z hlediska času bude nejkritičtější ten výpočet celkové produktivity při nějaké kombinaci zapnutí strojů. Každá instrukce navíc ti celkový čas dost prodlouží. Všechny výpočty co není nutné dělat pokaždé je třeba mít udělané dopředu. Tady jen sčítat...

Pokud bys chtěl procházet opravdu všechny kombinace, je zase lepší využívat nějaké mezisoučty, abys celkovou produktivitu nepočítal pokaždé se všech strojů dohromady. Navíc pak můžeš část výpočtů ušetřit - když má jeden ze strojů produktivitu třeba 100ks/h, a ty chceš jen 50/h, tak jej můžeš vynechat rovnou (a tím se ti počet nutných kroků sníží na polovinu, když to máš správně napsané).

Hezky by to šlo také rekurzivním voláním funkce - ale to v PLC nenapíšeš.

Offline

 

#8 26. 11. 2019 17:04

check_drummer
Příspěvky: 2768
Reputace:   74 
 

Re: Rozdělení výrobní kapacity na 20 strojů

A pak ještě existují aproximační algoritmy, které dají suboptimální řešení, které může být i dost blízko tomu optimálnímu.


Jak dokázat, že nelze dokázat, že dané tvrzení nelze dokázat?

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson