Lineaarprogrammeerimine (2D)

Kahe muutujaga LP: lubatud piirkond, tippude optimeerimine

Näidisarvutus — Lineaarprogrammeerimine (2D)

Maksimeeri	3x + 2y

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Lubatud piirkond ei ole lubadus vastusest 🖖

Nurgareeglil on kergesti vahelejääv eeldus: optimum peab üldse olemas olema. Laadi tõkestamata eelseade — maksimeeri 2x + y tingimustel x ≥ 0, y ≥ 0, x + y ≥ 2 — ja lubatud piirkond on täiesti mittetühi, kuid ükski nurk ei ole parim, sest võid kõndida kirdesse lõputult ja aina paremaks minna. Seepärast annab see tööriist ühe kolmest otsusest, mitte ainult ühe: optimaalne, lubamatu või tõkestamata. Kolmandani jõuab ta parandava retsessioonisuuna kontrollimisega, mitte tippude leidmise ebaõnnestumise kaudu. Lülita sama eelseade minimeerimisele ja lõplik vastus ilmub kohe punktis (0, 2). Lubatavus ja lahenduvus on eri küsimused.

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.

LINEAARPLANEERIMINE — MIKS VAADATAKSE ALATI AINULT NURKI

Millise lineaarplaneerimise juhtumiga on tegemist?

Iga lineaarne ülesanne küsib sama: kui kaugele saab sirgjoonelist sihifunktsiooni lükata piirkonnas, mille aiaks on sirgjoonelised kitsendused? Kuna mõlemad on sirged, saab parim punkt olla ainult nurk — just seepärast seisnebki meetod nurkade loetlemises ja võrdlemises. Kumma juhtumiga on tegu, sõltub sellest, kas piirkond üldse sulgeb sihifunktsiooni sisse ja kas antud nurk on arv, mida saab tegelikult kasutada.

Tõkestatud piirkond — optimum asub nurgas z = 10 → (2, 2)

Parim nurk on murdarvuline — ja see on juba teine ülesanne z = 24 → (8/3, 8/3)

Tõkestamata piirkond tõkestatud vastusega min z = 13

Lõplikku optimumi pole — ja nurkade vaatamine ei ütle seda z → ∞

Tõkestatud piirkond — optimum asub nurgas

Mida te teate: Maksimeeritav sihifunktsioon ja piisavalt ≤-kitsendusi, et piirkond sulgeda. Lubatav hulk on hulknurk.

Mida kontrollida: z = 10 → (2, 2)

Näidisarvutus: Maksimeeri 3x + 2y tingimustel x + y ≤ 4, x ≤ 2, y ≤ 3. Nurgad on (0,0), (2,0), (2,2), (1,3), (0,3) ning z = 10 punktis (2,2) võidab kõik.

Ava see juhtum: Dieedi ülesanne

Tõkestatud piirkond — optimum asub nurgas. Sihijoon libiseb üles ja paremale, kuni puudutab hulknurka veel vaid ühesainsas nurgas. Maksimeeritav sihifunktsioon ja piisavalt ≤-kitsendusi, et piirkond sulgeda. Lubatav hulk on hulknurk. — Sihijoon libiseb üles ja paremale, kuni puudutab hulknurka veel vaid ühesainsas nurgas.

Parim nurk on murdarvuline — ja see on juba teine ülesanne

Mida te teate: Jälle tõkestatud piirkond, kuid sihifunktsiooni valitud nurk ei lange täisarvudele.

Mida kontrollida: z = 24 → (8/3, 8/3)

Näidisarvutus: Maksimeeri 5x + 4y tingimustel 2x + y ≤ 8, x + 2y ≤ 8, x ≤ 4, y ≤ 4. Optimum on z = 24 punktis (8/3, 8/3), ligikaudu (2,67, 2,67).

Ava see juhtum: Tehase toodang

Parim nurk on murdarvuline — ja see on juba teine ülesanne. Kaks siduvat kitsendust lõikuvad ruudustikust mööda, nii et parimal nurgal on murdarvulised koordinaadid. Jälle tõkestatud piirkond, kuid sihifunktsiooni valitud nurk ei lange täisarvudele. — Kaks siduvat kitsendust lõikuvad ruudustikust mööda, nii et parimal nurgal on murdarvulised koordinaadid.

Tõkestamata piirkond tõkestatud vastusega

Mida te teate: Minimeerimine ≥-kitsendustega. Lubatav piirkond ulatub lõpmatusse, kuid sihifunktsioonil on ikkagi põrand.

Mida kontrollida: min z = 13

Näidisarvutus: Minimeeri 2x + 3y tingimustel x + y ≥ 6, x ≥ 2, y ≥ 1. Piirkond on lõpmatu, ent miinimum on siiski z = 13 punktis (5,1).

Ava see juhtum: Minimaalne kulu

Tõkestamata piirkond tõkestatud vastusega. Piirkond ulatub alguspunktist eemale piiritult, kuid sihifunktsioon saavutab miinimumi selle lähedal asuvas nurgas. Minimeerimine ≥-kitsendustega. Lubatav piirkond ulatub lõpmatusse, kuid sihifunktsioonil on ikkagi põrand. — Piirkond ulatub alguspunktist eemale piiritult, kuid sihifunktsioon saavutab miinimumi selle lähedal asuvas nurgas.

Lõplikku optimumi pole — ja nurkade vaatamine ei ütle seda

Mida te teate: Sihifunktsioon paraneb suunas, mida ükski kitsendus ei tõkesta. Parimat punkti ei ole olemas.

Mida kontrollida: z → ∞

Näidisarvutus: Maksimeeri 2x + y tingimustel x + y ≥ 2, x ≥ 0, y ≥ 0. Liikuge mööda kasvavat x-i lõputult ja sihifunktsioon kasvab lõputult; vastus on tõkestamata.

Ava see juhtum: Piiramatu

Lõplikku optimumi pole — ja nurkade vaatamine ei ütle seda. Varjutatud piirkond on üles ja paremale avatud ning sihifunktsioon paraneb seal lõputult edasi. Sihifunktsioon paraneb suunas, mida ükski kitsendus ei tõkesta. Parimat punkti ei ole olemas. — Varjutatud piirkond on üles ja paremale avatud ning sihifunktsioon paraneb seal lõputult edasi.

Allikad (3)

The diet problem in the history block: Stigler, G. J. (1945). "The Cost of Subsistence." Journal of Farm Economics 27(2), 303.
Simplex, and the vertex theorem it relies on: Dantzig, G. B. Linear Programming and Extensions. Princeton University Press, 1963.
Unboundedness and recession directions, the tool’s third verdict: Boyd, S. & Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004, §2.5. ISBN 978-0-521-83378-3.

Ülesanne täielikult lahendatud

Dieediülesanne Z = 3x + 2y maksimeerimiseks 5 sammu
Mis nurgapunkt võidab ja mida on väärt selle kõrvalasuv nurgapunkt? See on Dieediprobleem: maksimiseerida Z = 3x + 2y tingimustel x + y ≤ 4, x ≤ 2 ja y ≤ 3, kus nii x kui ka y on vähemalt 0.
1. Võtke mis tahes kaks lubatavat punkti ja liikuge neid ühendavat sirglõiku pidi. Lineaarne sihtfunktsioon sellel sirglõigul on oma kahe otsaväärtuse kaalutud keskmine ning kaalutud keskmine ei ületa kunagi suuremat otsaväärtust. Seega ei saa ükski rangelt kahe teise vahel asuv punkt olla ainus parim lahend ning selle põhimõtte rakendamine kordamööda igas suunas jätab optimumi kindlalt mõnda nurgapunkti.
  
  $Z (λ A + (1 - λ) B) = λ Z (A) + (1 - λ) Z (B) \leq max {Z (A), Z (B)}, 0 \leq λ \leq 1$
2. Nurgapunkt on koht, kus kaks rajajoont lõikuvad, seega saadakse kandidaadid, võttes viis joont paarikaupa. Kümne paari seas on kaks paralleelset ning ülejäänud kaheksast täidavad vaid viis neid kitsendusi, millest neid ei moodustatud — x + y = 4 lõikub sirgega x = 0 punktis (0, 4), mis rikub tingimust y ≤ 3.
  
  ${x + y = 4, x = 2} \Rightarrow (2, 2); {x + y = 4, y = 3} \Rightarrow (1, 3); (0, 0), (2, 0), (0, 3)$
3. Viis arvutuslikku väärtustamist ja üks võrdlus ning otsing ongi lõppenud. Kontrollimiseks ei ole jäänud ühtegi sisepunkti ega läbimiseks ühtegi serva.
  
  $Z = 3 x + 2 y : 0, 6, 10, 9, 6 ⟹ (x^{*}, y^{*}) = (2, 2), Z^{*} = 10$
4. Võitvas nurgapunktis on nii x + y = 4 kui ka x = 2 aktiivsed, samas kui y = 2 asub terve ühiku võrra allpool oma ülempiiri 3. Varuga täidetud kitsendus ei piira midagi, seega selle leevendamine ei muuda midagi; ülejäänud kahe puhul tasub ülesanne uuesti lahendada, lisades kumbagile ühe ühiku.
  
  $b_{1} : 4 \to 5 \Rightarrow (2, 3), Z = 12, y_{1} = 2; b_{2} : 2 \to 3 \Rightarrow (3, 1), Z = 11, y_{2} = 1; y^{*} = 2 < 3 \Rightarrow y_{3} = 0$
5. Kaaluge kõiki neid kolme hinda selle järgi, kui palju vastavat ressurssi ülesandes anti.
  
  $b_{1} y_{1} + b_{2} y_{2} + b_{3} y_{3} = 4 (2) + 2 (1) + 3 (0) = 10 = Z^{*}$
Vastus

Tööriist kuvab tulemuseks x* = 2, y* = 2 ja Z* = 10, mis on viiest nurgapunkti väärtusest kolmas. Sammu 4 arvud — 2, 1 ja 0 — on varjuhinnad ning need vastavad küsimusele, millele graafik ei vasta: üks täiendav x + y eelarve ühik on väärt kaks korda rohkem kui üks täiendav x-i ühik ning üks täiendav y-i ühik ei ole väärt mitte midagi. Samm 5 väljendab tugevat duaalsust ega ole nende arvude juhuslik kokkulangevus; ressursside kogustega kaalutud hinnad taastavad alati optimumi, mis teebki neist hinnad. Varjuhinnal on samuti oma kehtivuspiir. Kitsenduse x + y eelarve annab 2 ühiku kohta vaid kuni väärtuseni 5, kus nurgapunkt jõuab koordinaatideni (2, 3), ülejäänud kaks kitsendust muutuvad aktiivseks ning Z jääb püsima väärtusel 12 — sellest punktist edasi on hind 0 ja iga ostetud lisaühik on raisatud.

$max {c^{⊤} x : A x \leq b, x \geq 0} = min {b^{⊤} y : A^{⊤} y \geq c, y \geq 0} = 10$

42Mathi meeskond · Uuendatud 2026-08-17

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Statistika & rahandus õppetunnid →

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.