Kolonnien generointi

kolonnien generointi tai viivästynyt kolonnien generointi on tehokas algoritmi suurten lineaaristen ohjelmien ratkaisemiseen.

yleinen ajatus on, että monet lineaariset ohjelmat ovat liian suuria tarkastelemaan kaikkia muuttujia eksplisiittisesti. Lähtökohta on, että suurin osa muuttujista on ei-basic ja olettaa arvon nolla optimaalisessa ratkaisussa. Tämän vuoksi vain muuttujien osajoukko on otettava huomioon teoriassa ongelmaa ratkaistaessa. Sarakkeen generointi hyödyntää tätä ajatusta tuottaakseen vain ne muuttujat, joilla on mahdollisuus parantaa objektiivista funktiota—eli löytää muuttujat, joilla on negatiivinen alennettu kustannus (olettaen ilman yleispätevyyttä, että ongelma on minimointiongelma).

ratkaistava ongelma jakautuu kahteen ongelmaan: pääongelmaan ja alaprobleemiin. Pääongelma on alkuperäinen ongelma, jossa tarkastellaan vain muuttujien osajoukkoa. Aliprobleema on uusi ongelma, joka on luotu uuden muuttujan tunnistamiseksi. Osaprobleemin objektiivinen funktio on uuden muuttujan alentunut kustannus suhteessa nykyisiin kaksoismuuttujiin, ja rajoitteet edellyttävät, että muuttuja noudattaa luonnossa esiintyviä rajoitteita.

prosessi toimii seuraavasti. Pääongelma on ratkaistu-tästä ratkaisusta voimme saada kaksoishinnat jokaiselle pääongelman rajoitteelle. Tätä tietoa hyödynnetään sitten osaprobleemin objektiivisessa funktiossa. Osaongelma on ratkaistu. Jos osaongelman objektiivinen arvo on negatiivinen, on yksilöity muuttuja, jonka kustannukset ovat negatiiviset. Tämän jälkeen tämä muuttuja lisätään master-ongelmaan, ja master-ongelma ratkaistaan uudelleen. Pääongelman uudelleenratkaisu luo uudet kaksiarvoiset arvot, ja prosessi toistetaan, kunnes negatiivisia vähennettyjä kustannusmuuttujia ei tunnisteta. Alaprobleemi palauttaa ratkaisun ei-negatiivisilla alennetuilla kustannuksilla, voimme päätellä, että ratkaisu pääongelmaan on optimaalinen.

monissa tapauksissa tämä mahdollistaa suurten lineaaristen ohjelmien, joita oli aiemmin pidetty hankalina, ratkaisemisen. Klassinen esimerkki ongelmasta, jossa tätä käytetään menestyksekkäästi, on leikkuuvarasto-ongelma. Eräs tietty lineaarisen ohjelmoinnin tekniikka, joka käyttää tällaista lähestymistapaa, on Dantzigin-Wolfen hajoamisalgoritmi. Lisäksi sarakkeen generointia on sovellettu moniin ongelmiin, kuten miehistön aikataulutukseen, ajoneuvon reititykseen ja kapasitoituun p-mediaaniongelmaan.

tämä sovellettuun matematiikkaan liittyvä artikkeli on tynkä. Wikipediaa voi auttaa laajentamalla sitä.