Keskustelu: Ohjelmointikysymykset: Määrän optimointi VBA:lla

Kuinka ihmeessä seuraavaa ongelmaa olisi syytä lähteä ratkomaan?

Ongelma:

On tarve katkoa eri mittaisia ja eri määrän omaavia kappaleita vakio mittaisesta aihiosta siten että halutaan optimoida katkaistavien aihioiden lukumäärä mahdollisimman pieneksi.

Lähtötietoina annetaan (pyydetään):
- terän paksuus (jonka katkaisu "hävittää" aihiosta/katkaisukohta. Eli leikattavan mitan aihiosta ottama määrä on terän paksuus+leikattava mitta)
- katkaistavat pituudet ja lukumäärät/pituus (mitta > 10 mm, täysiä millejä)
- aihion pituus (max 6000 mm)

Tuloksena pitäisi saada:
- katkaisu lista/ aihio (eli montako kappaletta mitäkin mittaa katkaistaan aihiosta, jotta saadaan kaikki tarpeelliset palikat katkottua)
- aihioiden lukumäärä

Kaikki nämä tietysti vielä tallennetaan excel taulukkoon jotta voidaan tulostaa katkaisu listat aihioittain.

Asiaa pohtineena täytyy tunnustaa että ihan heti ei kyllä aukene tarvittavat laskutoimenpiteet..

Oliskohan joku jo mahdollisesti ratkaissut asian??

Muodosta ensin rajoiteyhtälöt ja minimointifunktio. Jos saat lineaarisen minimointitehtävän, ratkaise vaikka simplexillä(http://en.wikipedia.org/wiki/Simplex_algorithm).

Epälineaarisen minimointitehtävän ratkaisemiseen joudut käyttämään jotain muuta. Jos on laiska, eikä parasta ratkaisua tarvitse ja haluaa käyttää raakaa voimaa, voi käyttää vaikka differentiaalievoluutioalgoritmia(http://en.wikipedia.org/wiki/Differential_evolution) tehtävän rakaisemiseen.

Tehtävä vaikuttaa sellaiselta, että siihen ei ole oleellisesti parempaa ratkaisua kuin kokeilla kaikki vaihtoehdot läpi ja valita paras. Hakua voi kuitenkin nopeuttaa erilaisten optimointien avulla.

Ohjelma voisi toimia niin, että ensin yritetään leikata palikoita yhdestä aihiosta, sitten kahdesta, sitten kolmesta jne., kunnes lopulta kaikki palikat saadaan leikattua, kun aihioiden määrä on valittu riittävän suureksi.

Tietyllä aihioiden määrällä sopivan leikkaustavan etsiminen voisi näyttää tältä pseudokoodina:

funktio haku(p):
    jos kaikki palikat on leikattu:
        tulosta ratkaisu
    muuten:
        käy läpi kaikki aihiot:
            jos aihiosta pystyy leikkaamaan palikan p:
                leikkaa palikka aihiosta
                haku(p + 1)
                palauta palikka aihioon

Koodissa p tarkoittaa leikattavan palikan numeroa. Koodissa ei ole mitään optimointeja: esim. jos palikoiden yhteispituus on suurempi kuin aihioiden yhteispituus, haku kannattaa tietysti lopettaa heti.

Samasta aiheesta on keskusteltu aikaisemminkin täällä:
https://www.ohjelmointiputka.net/keskustelu/16248-taloudellinen-sahausohjelma

Tack, tack.

Koodaus ei olekaan se ongelma, vaan matemaattisten funktioden löytyminen.
Eri vaihtoehtoja saa helposti aikaan pari miljardia, joten ratkaisuun tarvitaan tietysti vaihtoehtojen rajaamista aika rajusti, muuten ohjelma pyörii helposti vuosi tolkulla hakien eri vaihtoehtoja.

Tämä vanha keskustelu toi eniten ajatuksia asiaan.

Tämä ongelma kävisi Putkapostista :) Itse asiassa ratkaisin tuoreimman Putkapostin hyvin samalla tavalla.

Syvyyshaku on paras äkkiä mieleentuleva algoritmi, mutta se tukehtuisi tietysti oikein isoihin määriin. Se laskisi eri yhdistelmien vaihtoehdot jäljellä olevista paloista aina yhtä aihiota kohti kerrallaan. Pisin sijoittamatta oleva palanen tulisi aina nykyisen aihion alkuun, koska se rajoittaa laskennan määrää.

Turhat haarat jätettäisiin laskematta. Haku katkaisisi yli aihionpituuden menevät laskennat. Samoin jos se törmää juoksevana summana täsmälleen aihionpituuteen, koska se on optimiratkaisu. Haku etenisi aina pisimmistä palasista lyhimpiin, eli samojen palayhdistelmien eri järjestyksiä ei käytäisi läpi.

Haku laskisi siis aina aihion kerrallaan käyttäen sen mahdollisimman tarkasti hyväksi. Laskettua palayhdistelmää käytetään seuraavaankin aihioon, jos paloja on katkaisematta tarvittava määrä. Muuten tehdään uusi syvyyshaku jäljellä olevista paloista.

Tämä menetelmä jättäisi pisimmän mahdollisen (= helpoimmin hyödynnettävän) hukkapätkän viimeiseen aihioon.

Chiman kirjoitti:

Haku laskisi siis aina aihion kerrallaan käyttäen sen mahdollisimman tarkasti hyväksi. Laskettua palayhdistelmää käytetään seuraavaankin aihioon, jos paloja on katkaisematta tarvittava määrä. Muuten tehdään uusi syvyyshaku jäljellä olevista paloista.

Optimaalista tapaa ei vaan valitettava saa pelkästään yhtä aihiota kerrallaan tarkkailematta, koska siihen ensimmäiseen saattaa mennä ne pari sopivan pituista palaa jolla seuraavat pätkät saisi tehtyä kahdesta palasta kolmen asemesta.

Minkälaisista palamääristä tässä puhutaan? Jos määrä on luokkaa alle sata, niin sitten tietokone kyllä jauhaa ne optimaaliseen järjestykseen lyhyehkössä ajassa. Jos taas paloja tulee satoja tuhansia, niin sitten päästään kyllä aika hyvään lopputulokseen vähemmän optimaalisellakin algoritmilla.

Yksi todella yksinkertainen algoritmi olisi ottaa aina pisin jäljellä olevaan pätkään mahtuva pala ja sahata se ja jatkaa tätä niin kauan kunnes mitään ei enää mahdu. Riippuen paloista tämä voi toimia erittäin hyvin, erittäin huonosti tai mitä tahansa siltä väliltä.

Grez kirjoitti:

Optimaalista tapaa ei vaan valitettava saa pelkästään yhtä aihiota kerrallaan tarkkailematta, koska siihen ensimmäiseen saattaa mennä ne pari sopivan pituista palaa jolla seuraavat pätkät saisi tehtyä kahdesta palasta kolmen asemesta.

Totta, hyvä pointti. Esimerkki: aihion pituus = 10, terän paksuus = 1:

xxxxxxxxxx aihio
4444 22 22
333 333
333 333
333
vs.
4444 333
333 333 22
333 333 22

jos teidän leikattavat kappaleet ovat vakiokokoisia, niin itse vaan valitsisin mitkä halutaan yhdestä aihiosta saada ja tilaisin aihion kappaleiden mukaan, enkä tekisi niin että yrittäisin laskea kuinka monta erikokoista kappaletta yhdestä vakiokokoisesta aihiosta saisi.