Optimizare liniară

Acest capitol este destinat ca o introducere în subiectul complex al optimizării liniare (LOP). În acest context, apar câteva întrebări pe care vrem să le clarificăm treptat.

Ce se înțelege prin termenul „optimizare liniară”?
Cum poate fi formulată problema matematic?
Ceea ce sunt cunoscute utilizează cazuri de optimizare liniară?
Ce metode de soluție există?
Ce soluții sunt posibile?

Explicațiile noastre din acest capitol sunt limitate la o optimizare liniară cu două variabile.

Ce este optimizarea liniară?

Optimizarea liniară poate fi utilizată ca (practic) Aplicarea sistemelor liniare de inegalitate fii inteles. Articolul anterior „Sisteme de inegalități liniare cu două variabile” este, în consecință, baza acestui capitol.

Optimizarea liniară se ocupă de acele procese matematice care determină cea mai mare sau cea mai mică valoare a unei funcții liniare. Acestea sunt de obicei restricționate de condiții suplimentare.

optimizare liniară se ocupă cu maximizarea sau minimizarea unei funcții liniare sub constrângeri.

Formularea matematică

Un așa-numit „program liniar” (LP) constă din următoarele componente

Funcție obiectivă

Funcția liniară care urmează să fie maximizată (minimizată) se numește funcția obiectivă.

Constrângeri (restricții)

\ (\ begina_1x + b_1y & \ leq c_1 \\ a_2x + b_2y & \ leq c_2 \\\ qquad \ vdots \ qquad \ vdots \\ a_nx + b_ny & \ leq c_n \ end \)

(Starea de nonegativitate)

În majoritatea problemelor practice, variabilele de decizie sunt limitate la valori mai mari sau egale cu zero. Motivul pentru aceasta este că, de obicei, nu pot asuma valori negative. De exemplu, o companie nu poate produce un „număr negativ” de produse.

Excurs: Ce înseamnă grafic condiția de non-negativitate?

\ (x \ geq 0 \) înseamnă grafic că numai zona din dreapta axei y este relevantă pentru luare în considerare.

\ (y \ geq 0 \) înseamnă grafic că numai aria de deasupra axei x este relevantă pentru luare în considerare.

Dacă se observă atât \ (x \ geq 0 \) cât și \ (y \ geq 0 \), se constată că numai primul cadran al sistemului de coordonate este relevant pentru luarea în considerare.

Zona evidențiată este, prin urmare, zona care îndeplinește condiția de non-negativitate.

Aplicații

În practică există un număr mare de aplicații pentru optimizarea liniară. Unele dintre acestea vor fi explicate mai detaliat folosind exemple.

Deoarece condiția de non-negativitate trebuie îndeplinită în următoarele exemple, considerația grafică este limitată la primul cadran al sistemului de coordonate.

În acest moment, se recomandă insistent să ne uităm din nou la capitolul „Sisteme liniare de inegalități cu două variabile”.

a) problema producției

Două tipuri diferite de cabluri sunt produse într-o fabrică și vândute cu 150 € (tip A) și 100 € (tip B) la 100 de metri. Cablurile de tip A necesită 16 kg de plastic și 4 kg de cupru. Cablurile de tip B necesită 6 kg de plastic și 12 kg de cupru. Cantitatea de B produsă nu trebuie să fie mai mare decât dublul cantității de A. În plus, aprovizionarea cu material este în prezent doar 252 kg plastic și 168 kg cupru.

Ce cantități din cele două tipuri de cabluri maximizează cifra de afaceri a companiei, respectând în același timp constrângerile?

1.) Compilație clară a sarcinii

2.) Formularea matematică a problemei

Funcție obiectivă	\ (z (x, y) = 150x + 100y \ quad \ rightarrow \ quad \ text \)
Constrângeri	\ (\ începe 16x + 6y & \ leq 252 \\ 4x + 12y & \ leq 168 \Sfârșit\)
. și din cauza \ (y \ leq 2x \) avem:	\ (2x - y \ geq 0 \)
Starea de nonegativitate	\ (x \ geq 0 \) \ (y \ geq 0 \)

3.) Considerație grafică

Ați dori prima condiție secundară
\ (16x + 6y \ leq 252 \)
trageți într-un sistem de coordonate, trebuie să rezolvați inegalitatea pentru \ (y \) \ (6y \ leq - 16x + 252 \)
\ (y \ leq - \ fracx + 42 \)
și apoi interpretați inegalitatea ca pe o ecuație dreaptă
\ (y = - \ fracx + 42 \)

Zona colorată indică zona care îndeplinește prima condiție secundară.

Ați dori a doua condiție secundară
\ (4x + 12y \ leq 168 \)
trageți într-un sistem de coordonate, trebuie să rezolvați inegalitatea pentru \ (y \) \ (12y \ leq - 4x + 168 \)
\ (y \ leq - \ fracx + 14 \)
și apoi interpretați inegalitatea ca pe o ecuație dreaptă
\ (y = - \ fracx + 14 \)

Zona colorată indică zona care îndeplinește a doua condiție secundară.

A treia condiție secundară este:
"Cantitatea de B produsă nu trebuie să fie mai mare decât dublul cantității de A."
. sau formulat matematic: \ (y \ leq 2x \)

Zona colorată indică zona care îndeplinește a treia condiție secundară.

Soluție setată a sistemului liniar de inegalitate.
\ (16x + 6y \ leq 252 \)
\ (4x + 12y \ leq 168 \)
\ (y \ leq 2x \)
.este evidențiat în culori în graficul alăturat.

Acum știm cum arată grafic setul de soluții fezabile. Următorul pas este să căutați soluția optimă. Putem determina acest lucru fie grafic, fie prin calcul.

4.1) Determinați soluția optimă (matematică)

Deoarece optimul corespunde unui punct de colț al zonei soluției, îl citim mai întâi: \ (P_1 (0,0) \); \ (P_2 (6.12) \); \ (P_3 (12,10) \); \ (P_4 (15.75; 0) \);

Acum punem punctele în funcția obiectivă și determinăm maximul.

\ (z (0,0) = 150 \ ori 0 + 100 \ ori 0 = 0 € \)

\ (z (6.12) = 150 \ ori 6 + 100 \ ori 12 = 2.100 € \)

\ (z (12.10) = 150 \ cdot 12 + 100 \ cdot 10 = 2.800 € \ qquad \ rightarrow \ quad \ text \)

\ (z (15,75; 0) = 150 \ ori 15,75 + 100 \ ori 0 = 2,362,50 € \)

Răspuns:
Fabrica își maximizează vânzările, respectând în același timp constrângerile, atunci când produce cablu de 12 x 100m de tip A și 10 x 100m de cablu de tip B.

4.2) Determinați soluția optimă (grafic)

O puteți găsi grafic maxim, prin trasarea funcției obiective și apoi deplasarea acesteia în paralel până când linia dreaptă denotă ultimul punct de colț a zonei de soluție. Ultimul colț corespunde apoi soluției optime.

Mai întâi rezolvăm funcția obiectivă pentru \ (y \).
\ (z (x, y) = 150x + 100y = 0 \)
\ (100y = -150x \)
\ (y = -1,5x \)
.pentru a le desena în sistemul de coordonate. Apoi deplasăm linia dreaptă paralelă până ajungem la ultimul colț al zonei soluției.

Optimul (aici: maxim) este prezentat în grafic printr-un punct roșu.

b) Problema transportului

O companie aeriană dorește să stabilească o conexiune de zbor între două orașe. Scopul este de a transporta 1.600 de persoane și 96 de tone de marfă într-o anumită perioadă de timp. În prezent sunt disponibile două tipuri de aeronave: 11 avioane de tip A și 8 avioane de tip B. Costă 4.000 EUR pe zbor și poate transporta 200 de persoane și 6 tone de marfă. Tipul B costă 1.000 EUR pe zbor și poate transporta 100 de persoane și 15 tone de marfă.

La fel ca multe aeronave de fiecare tip, compania aeriană va opera sub constrângeri pentru a-și minimiza costurile?

1.) Compilație clară a sarcinii

\ începe
& \ text & \ text & \ text \\ \ hline
\ text & 200 & 100 & 1600 \\ \ hline
\ text & 6 & 15 & 96 \\ \ hline
\ text & 4.000 & 1.000 &
\Sfârșit

2.) Formularea matematică a problemei

Funcție obiectivă	\ (z (x, y) = 4000x + 1000y \ quad \ rightarrow \ quad \ text \)
Constrângeri	\ (\ începe 200x + 100y & \ geq 1600 \\ 6x + 15y & \ geq 96 \Sfârșit\)
. se aplică și:	\ (x \ leq 11 \) \ (y \ leq 8 \)
Starea de nonegativitate	\ (x \ geq 0 \) \ (y \ geq 0 \)

3.) Considerație grafică

Ați dori prima condiție secundară
\ (200x + 100y \ geq 1600 \)
trageți într-un sistem de coordonate, trebuie să rezolvați inegalitatea pentru \ (y \) \ (100y \ geq -200x + 1600 \)
\ (y \ geq -2x + 16 \)
și apoi interpretați inegalitatea ca pe o ecuație dreaptă
\ (y = -2x + 16 \)

Zona colorată indică zona care îndeplinește prima condiție secundară.

Ați dori a doua condiție secundară
\ (6x + 15y \ geq 96 \)
trageți într-un sistem de coordonate, trebuie să rezolvați inegalitatea pentru \ (y \) \ (15y \ geq - 6x + 96 \)
\ (y \ geq - 0.4x + 6.4 \)
și apoi interpretați inegalitatea ca pe o ecuație dreaptă
\ (y = - 0,4x + 6,4 \)

Zona colorată indică zona care îndeplinește a doua condiție secundară.

A treia condiție secundară
\ (x \ leq 11 \)
este o paralelă cu axa y cu intersecția axei \ (x = 11 \).

Zona colorată indică zona care îndeplinește a treia condiție secundară.

A 4-a condiție secundară
\ (y \ leq 8 \)
este o paralelă cu axa x cu intersecția axei \ (y = 8 \).

Zona colorată indică zona care îndeplinește a 4-a condiție secundară.

Soluție setată a sistemului liniar de inegalitate.
\ (200x + 100y \ geq 1600 \)
\ (6x + 15y \ geq 96 \)
\ (x \ leq 11 \)
\ (y \ leq 8 \)
.este evidențiat în culori în graficul alăturat.

Acum știm cum arată grafic setul de soluții fezabile. Următorul pas este să căutați soluția optimă. Putem determina acest lucru fie grafic, fie prin calcul.

4.1) Determinați soluția optimă (matematică)

Deoarece optimul corespunde unui punct de colț al zonei soluției, îl citim mai întâi: \ (P_1 (6,4) \); \ (P_2 (4.8) \); \ (P_3 (11.8) \); \ (P_4 (11.2) \);

Acum punem punctele în funcția obiectivă și determinăm minimul.

\ (z (6,4) = 4.000 \ ori 6 + 1.000 \ ori 4 = 28.000 € \)

\ (z (4.8) = 4.000 \ ori 4 + 1.000 \ ori 8 = 24.000 € \ qquad \ rightarrow \ quad \ text \)

\ (z (11,8) = 4.000 \ ori 11 + 1.000 \ ori 8 = 52.000 € \)

\ (z (11.2) = 4.000 \ ori 11 + 1.000 \ ori 2 = 46.000 € \)

Răspuns:
Compania aeriană își minimizează costurile în conformitate cu constrângerile dacă operează 4 aeronave de tip A și 8 aeronave de tip B.

4.2) Determinați soluția optimă (grafic)

O puteți găsi grafic minim, prin trasarea funcției obiective și apoi deplasarea acesteia în paralel până când linia dreaptă denotă primul punct din colț a zonei de soluție. Primul colț corespunde apoi soluției optime.

Mai întâi rezolvăm funcția obiectivă pentru \ (y \).
\ (z (x, y) = 4000x + 1000y = 0 \)
\ (1000y = -4000x \)
\ (y = -4x \)
.pentru a le desena în sistemul de coordonate. Apoi deplasăm linia dreaptă paralelă până ajungem în primul colț al zonei soluției.

Optimul (aici: minim) este afișat în grafic printr-un punct roșu.

Solutii posibile

În exemplele de mai sus, am văzut deja că o problemă de optimizare poate avea o soluție unică. De asemenea, este posibil să existe mai multe soluții sau deloc soluții.

În cele ce urmează veți găsi un exemplu grafic pentru fiecare soluție. Scopul este întotdeauna de a găsi un minim.

Soluție optimă clară

. Am analizat deja două exemple în detaliu mai sus.

Număr infinit de soluții optime

Dacă funcția obiectivă este paralelă cu o restricție, există mai multe soluții. Grafic, aceasta înseamnă că odată cu deplasarea paralelă, funcția obiectivului coincide cu această linie de restricție.

Nu este o soluție optimă

Există cazuri în care nu există o soluție optimă.

Concluzie

Când vine vorba de subiectul „optimizării liniare”, de multe ori trebuie să ne ocupăm de problemele cuvintelor. Este important să puteți citi elementele esențiale ale sarcinii și să le rezumați într-un tabel. Cu ajutorul acestei reprezentări clare, formularea matematică ulterioară este enorm simplificată.

Dacă programul liniar are doar două variabile, o analiză grafică este potrivită pentru rezolvarea sarcinii de optimizare.

maxim poate fi găsit grafic trasând funcția obiectivă și deplasând-o în paralel până când ajunge la ultimul punct de colț a zonei de soluție.
minim poate fi găsit grafic trasând funcția obiectivă și deplasând-o în paralel până când ajunge la primul punct din colț a zonei de soluție.

În principiu, sarcinile de optimizare liniară pot avea un număr clar, infinit sau nici o soluție (optimă).

Pentru programele liniare cu mai mult de două variabile, o vizualizare grafică (în cea mai mare parte) nu este posibilă. În practică, în acest caz, optimul este calculat folosind așa-numitul algoritm simplex.

Numele meu este Andreas Schneider și conduc, din 2013, platforma gratuită și premiată de învățare a matematicii www.mathebibel.de. Până la un milion de studenți, părinți și profesori îmi văd declarațiile în fiecare lună. Public conținut nou aproape în fiecare zi. Abonați-vă la newsletter-ul meu acum și primiți 3 dintre cele 46 de cărți electronice gratuite!

PS: Am văzut deja episodul actual al seriei mele #MatheAmMontag?