Lineaarprogrammeerimine (2D)
Kahe muutujaga LP: lubatud piirkond, tippude optimeerimine
Kumerad optimeerimise piirid piiratud ruumides 🖖
Lineaarne planeerimine optimeerib lineaarset sihtfunktsiooni, mis allub lineaarsetele võrdus- ja mittevõrduskitsendustele. Staatiliselt moodustab lubatav piirkond kumera polüeedri. Lineaarse planeerimise põhiteoreem väidab, et optimaalne lahendus peab asuma selle polüeedri ühes tipus, mida lahendatakse Simpleks-algoritmiga.
Parimad lahendused peituvad nurkades 🖖
Lihtsalt öeldes žongleerid piiratud ressurssidega mitme reegli all korraga, ja iga võrratus lõikab tasandist ühe osa ära. Seal, kus kõik reeglid kattuvad, asub lubatav piirkond, ja iga selle sisene punkt on kehtiv plaan. Kuna lineaarne sihifunktsioon kasvab ühes suunas pidevalt, satub parim lahendus nurka, kus kitsendused kohtuvad. Kokkuvõte: optimeerimiseks ei kontrolli sa kunagi iga punkti, vaid ainult üksikuid nurki.
Kuidas dieediülesanne simpleksmeetodit ennustas 🖖
1945. aastal uuris majandusteadlane George Stigler kõige odavamat dieeti, mis kataks kõik toitainevajadused — lineaarülesanne 77 toiduainega. Algoritmi puudumisel tegi ta nutika hinnangu ja sai umbes $39.93 aastas (1939. aasta hinnad). Kui Dantzigi simpleksmeetod selle 1947. aastal täpselt lahendas, oli tegelik miinimum $39.69 — Stigleri käsitsi hinnang eksis vaid umbes 24 senti aastas. Nii sai kuivast majandusteadusest üks lineaarplaneerimise algusaegade näidisülesandeid.
Näiteülesanded
- Dieedi ülesanne - Klassikaline tõkestatud maksimeerimine: optimaalne lahend asub lubatud piirkonna tipus.
- Tehase toodang - Ristuvad tootmisvõimsuse piirangud moodustavad hulknurkse lubatud piirkonna.
- Minimaalne kulu - Alt tõkestatud piirangute korral valib miinimumülesanne lubatud piirkonna tipu, mis on sihtfunktsiooni suunas lähim koordinaatide alguspunktile.
- Piiramatu - Lubatud piirkond võib olla tõkestamata, mistõttu sihtfunktsioonil ei pruugi olla lõplikku optimumi.