Články

3.1: Maximalizačné aplikácie


Učebné ciele

V tejto časti sa naučíte:

  1. Rozpoznať typickú formu problému lineárneho programovania
  2. Formulujte maximalizačné problémy lineárneho programovania
  3. Graf oblastí uskutočniteľnosti pre maximalizáciu problémov lineárneho programovania
  4. Určte optimálne riešenia pre maximalizáciu problémov lineárneho programovania.

Problémy s aplikáciou v podnikaní, ekonómii, sociálnych vedách a vedách o živote nás často žiadajú, aby sme sa rozhodovali na základe určitých podmienok. Podmienky alebo obmedzenia majú často podobu nerovností. V tejto časti začneme tieto problémy formulovať, analyzovať a riešiť na jednoduchej úrovni, aby sme porozumeli mnohým zložkám takéhoto problému.

Typický lineárne programovanie problém spočíva v nájdení extrémnej hodnoty lineárnej funkcie podliehajúcej určitým obmedzeniam. Snažíme sa buď maximalizovať alebo minimalizovať hodnotu tejto lineárnej funkcie, napríklad maximalizovať zisk alebo príjem alebo minimalizovať náklady. Preto sú tieto problémy lineárneho programovania klasifikované ako maximalizácia alebo minimalizačné problémy, alebo len optimalizačné problémy. Funkcia, ktorú sa snažíme optimalizovať, sa nazýva objektívna funkciaa volajú sa podmienky, ktoré musia byť splnené obmedzenia.

Typickým príkladom je maximalizácia zisku z výroby niekoľkých výrobkov s výhradou obmedzení týkajúcich sa materiálov alebo zdrojov potrebných na výrobu týchto výrobkov; problém si vyžaduje, aby sme určili množstvo každej vyrobenej položky. Ďalším typom problému je plánovanie; musíme určiť, koľko času treba venovať každej z niekoľkých aktivít, aby sme maximalizovali príjem z (alebo minimalizovali náklady) z týchto aktivít, s výhradou časových a iných zdrojov dostupných pre každú činnosť.

V tejto kapitole budeme pracovať s problémami, ktoré zahŕňajú iba dve premenné, a preto ich možno vyriešiť pomocou grafov. V nasledujúcej kapitole sa naučíme algoritmus na numerické nájdenie riešenia. To nám poskytne nástroj na riešenie problémov s viac ako dvoma premennými. V tom čase s trochou ďalších znalostí o lineárnom programovaní preskúmame tiež mnoho spôsobov, ako sa tieto techniky používajú v podnikaní, a v širokej škále ďalších oblastí.

Začíname riešením problému maximalizácie.

Príklad ( PageIndex {1} )

Niki má dve brigády, Job I a Job II. Nikdy nechce pracovať viac ako 12 hodín týždenne. Zistila, že na každú hodinu práce na Job I potrebuje 2 hodiny času na prípravu a na každú hodinu práce na Job II potrebuje hodinu prípravy a na prípravu nemôže venovať viac ako 16 hodín.

Ak Nikki zarába 40 dolárov za hodinu na Job I a 30 dolárov za hodinu na Job II, koľko hodín by mala týždenne pracovať v každom zamestnaní, aby maximalizovala svoj príjem?

Riešenie

Začneme výberom našich premenných.

  • Nech (x ) = počet hodín týždenne, keď bude Niki pracovať na Job I.
  • Nech (y ) = počet hodín týždenne, keď bude Niki pracovať na Job II.

Teraz napíšeme objektívnu funkciu. Keďže Niki dostáva v práci I 40 dolárov za hodinu a v práci II 30 dolárov za hodinu, jej celkový príjem I je daný nasledujúcou rovnicou.

[I = 40x + 30y nonumber ]

Našou ďalšou úlohou je nájsť obmedzenia. Druhá veta problému uvádza: „Nikdy nechce pracovať viac ako 12 hodín týždenne.“ To znamená nasledujúce obmedzenie:

[x + y leq 12 nonumber ]

V tretej vete sa uvádza: „Za každú hodinu práce na Job I potrebuje 2 hodiny času na prípravu a na každú hodinu práce na Job II potrebuje jednu hodinu času na prípravu a nemôže stráviť viac ako 16 hodín príprava. ““ Nasleduje preklad.

[2x + y leq 16 nonumber ]

Skutočnosť, že (x ) a (y ) nikdy nemôžu byť záporné, predstavujú nasledujúce dve obmedzenia:

[x geq 0 text {a} y geq 0 nonumber. ]

Dobrá správa! Sformulovali sme problém. Preformulovali sme to ako

begin {pole} {ll}
textbf {Maximalizovať} & mathrm {I} = 40 mathrm {x} +30 mathrm {y}
textbf {Podlieha:} & mathrm {x} + mathrm {y} leq 12
& 2 mathrm {x} + mathrm {y} leq 16
& mathrm {x} geq 0; mathrm {y} geq 0
end {pole}

Na vyriešenie problému zostrojíme graf obmedzení a zatienime oblasť, ktorá vyhovuje všetko obmedzenia nerovnosti.

Na vykreslenie čiar pre obmedzenia je možné použiť akúkoľvek vhodnú metódu. Najjednoduchšou metódou je však často nakresliť čiaru tak, že zakreslíme čiary x a y.

Čiara pre obmedzenie rozdelí rovinu na dve oblasti, z ktorých jedna spĺňa nerovnostnú časť obmedzenia. Skúšobným bodom sa určí, ktorá časť roviny sa má zafarbiť, aby sa vyrovnala nerovnosť. Ako skúšobný bod je možné použiť akýkoľvek bod v rovine, ktorý sa nenachádza na priamke.

  • Ak skúšobný bod spĺňa nerovnosť, potom oblasť roviny, ktorá spĺňa nerovnosť, je oblasť obsahujúca skúšobný bod.
  • Ak skúšobný bod nevyhovuje nerovnosti, potom oblasť, ktorá uspokojuje nerovnosť, leží na opačnej strane čiary ako skúšobný bod.

V nasledujúcom grafe boli po grafe čiar predstavujúcich obmedzenia pomocou vhodnej metódy z kapitoly 1 bod (0,0) použitý ako testovací bod na stanovenie toho, že

  • (0,0) spĺňa obmedzenie (x + y leq 12 ), pretože (0 + 0 <12 )
  • (0,0) spĺňa obmedzenie (2x + y leq 16 ), pretože (2 (0) + 0 <16 )

Preto v tomto príklade zatienime oblasť, ktorá je pod a naľavo od oboje riadky obmedzení, ale tiež nad osou x a napravo od osi y, aby sa ďalej uspokojili obmedzenia (x geq 0 ) a (y geq 0 ).

Tieňovaná oblasť, v ktorej sú splnené všetky podmienky, sa nazýva región uskutočniteľnosti alebo polygón uskutočniteľnosti.

The Základná veta o lineárnom programovaní uvádza, že maximálna (alebo minimálna) hodnota objektívnej funkcie sa vždy odohráva na vrcholoch oblasti uskutočniteľnosti.

Preto identifikujeme všetky vrcholy (rohové body) oblasti uskutočniteľnosti. Voláme tieto body kritické body. Sú uvedené ako (0, 0), (0, 12), (4, 8), (8, 0). Aby sme maximalizovali Nikiho príjem, nahradíme tieto body v objektívnej funkcii, aby sme zistili, ktorý bod nám dáva najvyšší príjem za týždeň. Výsledky uvádzame nižšie.

Kritické bodyPríjem
(0, 0)40(0) + 30(0) = $0
(0, 12)40(0) + 30(12) = $360
(4, 8)40(4) + 30(8) = $400
(8, 0)40(8) + 30(0) = $320

Je zrejmé, že bod (4, 8) dáva najväčší zisk: 400 dolárov.

Preto sme dospeli k záveru, že Niki by mala pracovať 4 hodiny v Job I a 8 hodín v Job II.

Príklad ( PageIndex {2} )

Továreň vyrába dva typy prístrojov, pravidelné a prémiové. Každý modul gadget vyžaduje použitie dvoch operácií, a to montáže a dokončenia. Pre každú operáciu je k dispozícii najviac 12 hodín. Bežný modul gadget vyžaduje 1 hodinu montáže a 2 hodiny dokončenia, zatiaľ čo prémiový modul gadget vyžaduje 2 hodiny montáže a 1 hodinu dokončenia. Z dôvodu ďalších obmedzení môže spoločnosť vyrobiť najviac 7 pomôcok denne. Ak sa dosiahne zisk 20 dolárov za každú bežnú pomôcku a 30 dolárov za prémiovú pomôcku, koľko z nich by sa malo vyrobiť, aby sa maximalizoval zisk?

Riešenie

Vyberáme svoje premenné.

  • Nech (x ) = počet bežných gadgetov vyrábaných každý deň.
  • a (y ) = počet prémiových gadgetov vyrábaných každý deň.

Objektívna funkcia je

[P = 20x + 30 rokov nečíslo ]

Teraz píšeme obmedzenia. Štvrtá veta hovorí, že spoločnosť môže vyrobiť najviac 7 vychytávok denne. To sa prekladá ako

[x + y leq 7 nonumber ]

Pretože bežný modul gadget vyžaduje jednu hodinu montáže a prémiový modul gadget vyžaduje dve hodiny montáže, pričom pre túto operáciu je k dispozícii najviac 12 hodín, dostaneme

[x + 2r leq 12 nonumber ]

Bežný modul gadget podobne vyžaduje dve hodiny dokončenia a prémiový modul gadget jednu hodinu. Na dokončenie je opäť k dispozícii najviac 12 hodín. Toto nám dáva nasledujúce obmedzenie.

[2x + y leq 12 nonumber ]

Skutočnosť, že (x ) a (y ) nikdy nemôžu byť záporné, predstavujú nasledujúce dve obmedzenia:

[x geq 0 text {a} y geq 0 nonumber. ]

Problém sme formulovali takto:

[ begin {array} {ll}
textbf {Maximalizovať} & mathrm {P} = 20 mathrm {x} +30 mathrm {y}
textbf {Podlieha:} & mathrm {x} + mathrm {y} leq 7
& mathrm {x} +2 mathrm {y} leq 12
& 2 mathrm {x} + mathrm {y} leq 12
& mathrm {x} geq 0; mathrm {y} geq 0
end {pole} nonumber ]

S cieľom vyriešiť problém, urobíme ďalší graf obmedzení a oblasti uskutočniteľnosti.

Opäť sme zatienili oblasť uskutočniteľnosti, kde sú splnené všetky obmedzenia.

Pretože extrémna hodnota objektívnej funkcie sa vždy odohráva vo vrcholoch oblasti uskutočniteľnosti, identifikujeme všetky kritické body. Sú uvedené ako (0, 0), (0, 6), (2, 5), (5, 2) a (6, 0). Aby sme maximalizovali zisk, nahradíme tieto body v objektívnej funkcii, aby sme zistili, ktorý bod nám dáva maximálny zisk každý deň. Výsledky sú uvedené nižšie.

Kritický bodPríjem
(0, 0)20(0) + 30(0) = $0

(0, 6)
20(0) + 30(6) = $180

(2, 5)
20(2) + 30(5) = $190

(5, 2)
20(5) + 30(2) = $160
(6,0)
20(6) + 30(0) = $120

Bod (2, 5) dáva najväčší zisk a tento zisk je 190 dolárov.
Preto sme dospeli k záveru, že by sme mali každý deň vyrábať 2 bežné gadgety a 5 prémiových gadgetov, aby sme dosiahli maximálny zisk 190 dolárov.

Doteraz sme sa sústredili na „štandardné maximalizačné problémy" v ktorom

  1. Objektívna funkcia sa má maximalizovať
  2. Všetky obmedzenia majú tvar (ax + by leq c )
  3. Všetky premenné sú obmedzené na záporné ( (x ≥ 0 ), (y ≥ 0 ))

Ďalej zvážime príklad, kde to tak nie je. Náš ďalší problém údajne má „zmiešané obmedzenia”, Pretože niektoré obmedzenia nerovnosti majú tvar (ax + o ≤ c ) a niektoré majú tvar (ax + o ≥ c ). Obmedzenia týkajúce sa negativity sú stále dôležitou požiadavkou v každom lineárnom programe.

Príklad ( PageIndex {3} )

Vyriešte nasledujúci problém s maximalizáciou graficky.

[ begin {array} {ll}
textbf {Maximalizovať} & mathrm {P} = 10 mathrm {x} +15 mathrm {y}
textbf {Podlieha:} & mathrm {x} + mathrm {y} geq 1
& mathrm {x} +2 mathrm {y} leq 6
& 2 mathrm {x} + mathrm {y} leq 6
& mathrm {x} geq 0; mathrm {y} geq 0
end {pole} nonumber ]

Riešenie

Graf je uvedený nižšie.

Na vyššie uvedenom obrázku je uvedených päť kritických bodov. Čitateľ by si mal všimnúť, že prvé obmedzenie (x + y ≥ 1 ) vyžaduje, aby oblasť uskutočniteľnosti musela byť ohraničená čiarou (x + y = 1 ); testovací bod (0,0) nevyhovuje (x + y ≥ 1 ), takže oblasť na opačnej strane čiary od testovacieho bodu (0,0) vytieňujeme.

Kritický bodPríjem
(1, 0)10(1) + 15(0) = $10
(3, 0)10(3) + 15(0) = $30
(2, 2)10(2) + 15(2) = $50
(0, 3)10(0) + 15(3) = $45
(0,1)10(0) + 15(1) = $15

Je zrejmé, že bod (2, 2) maximalizuje objektívnu funkciu na maximálnu hodnotu 50.

Je dôležité poznamenať, že ak bod (0,0) leží na priamke obmedzenia, potom (0,0) nemôže byť použitý ako testovací bod. Potrebovali by sme zvoliť akýkoľvek iný bod, ktorý chceme, ktorý by ležal na priamke, ktorá by sa v tejto situácii nemohla použiť ako testovací bod.

Na záver sa venujeme dôležitej otázke. Je možné určiť bod, ktorý dáva maximálnu hodnotu, bez výpočtu hodnoty v každom kritickom bode?

Odpoveď je áno.

Napríklad ( PageIndex {2} ) sme v objekte nahradili body (0, 0), (0, 6), (2, 5), (5, 2) a (6, 0). funkcia (P = 20x + 30y ) a dostali sme hodnoty $ 0, 180 $, 190 $, 160 $, 120 $.

Niekedy to nie je najefektívnejší spôsob hľadania optimálneho riešenia. Namiesto toho by sme mohli nájsť optimálnu hodnotu aj pomocou grafu objektívnej funkcie.

Aby sme určili najväčší (P ), urobíme graf (P = 20x + 30y ) pre ľubovoľnú hodnotu (P ) podľa nášho výberu. Povedzme, že zvolíme (P = 60 ). Vytvoríme graf (20x + 30y = 60 ).

Teraz posúvame čiaru rovnobežne so sebou, to znamená, že neustále udržiavame rovnaký sklon. Pretože posúvame čiaru rovnobežne so sebou, sklon sa udržiava rovnaký a jediné, čo sa mení, je P. Keď sa vzďaľujeme od počiatku, hodnota P sa zvyšuje. Najväčšia možná hodnota P sa dosiahne, keď sa čiara dotkne posledného rohového bodu oblasti uskutočniteľnosti.

Obrázok nižšie zobrazuje pohyby čiary a optimálne riešenie sa dosiahne v bode (2, 5). Pri problémoch s maximalizáciou, keď sa čiara posúva od počiatku, je tento optimálny bod najvzdialenejším kritickým bodom.

Zhrňujeme:

Maximalizácia problémov lineárneho programovania

  1. Napíšte objektívnu funkciu.
  2. Napíš obmedzenia.
    1. Pre štandardné problémy maximalizácie lineárneho programovania sú obmedzenia v tvare: (ax + o ≤ c )
    2. Pretože premenné nie sú záporné, zahrnieme aj obmedzenia: (x ≥ 0 ); (y ≥ 0 ).
  3. Vytvorte obmedzenia.
  4. Tieň regiónu uskutočniteľnosti.
  5. Nájdite rohové body.
  6. Určte rohový bod, ktorý dáva maximálnu hodnotu.
    1. To sa deje tak, že sa v každom rohovom bode zistí hodnota objektívnej funkcie.
    2. To sa dá urobiť aj pohybom čiary spojenej s objektívnou funkciou.