Formularea problemelor de programare liniară

Acasă | Despre noi | feedback-ul

În formularea obiectivului sarcină de luare a deciziilor optime ar trebui să fie formulată, că este rezultatul final, care dorește să realizeze un factor de decizie.

Alegerea soluțiilor dintr-o varietate de alternative implică anumite criterii și posibilitatea de a compara opțiunile disponibile pe acest criteriu. În mod alternativ, pentru care criteriul adoptat este cea mai bună valoare, denumite optimă, iar problema găsirii unei soluții optime - optimizare sarcină.

În economie, problema de optimizare este adesea posibil să se reducă la o anumită clasă de modele economice și matematice.

Există trei tipuri principale de modele: modele deterministe de luare a deciziilor în condiții de informații incomplete și modelul de luare a deciziilor în situații de conflict.

Chemat modele deterministe de luare a deciziilor în condiții de informații complete despre valorile tuturor parametrilor incluși în starea problemei. Această clasă de probleme sunt modele matematice și de programare dinamică, probleme multicriteriale, modelele de rețea.

Modele de luare a deciziilor în condiții de informații incomplete, sunt numite modele probabilistice sau stocastic. Pentru modelele probabilistice includ, de exemplu, teoria de așteptare, și managementul inventarului. Această clasă de probleme sunt, de asemenea, modele de luare a modelelor sub incertitudine și de simulare stohastică decizie. Problemele apar în ceea ce privește de incertitudine, în lipsa unor informații exacte cu privire la sarcina și valorile parametrilor de evaluare pre probabilistă a valorilor lor posibile.

Modele de luare a deciziilor în situații de conflict sunt obiectul de studiu al teoriei jocului.

Indiferent de tipul de model de sarcini de optimizare sunt împărțite în liniare și neliniare. Probleme liniare Chemat în care toate dependențele dintre parametrii de intrare sunt liniare. Rezolvarea problemelor de optimizare liniare sunt adesea numite de programare liniară.

Capitolul 1. Programarea liniară

Formularea problemelor de programare liniară

Tehnici de programare liniară sunt folosite pentru o gamă largă de aplicații în domeniul științelor naturale și umane, precum și activitatea economică. De exemplu, modelarea matematică a proceselor de producție utilizate în formarea planului de producție, asigurând maximizarea profitului în funcție de constrângerile date privind resursele.

Matematic, problema programării liniare (ZLP) este de a găsi cele mai mari sau mai mici valori ale unei funcții liniare multivariabil sub constrângeri liniare, cum ar fi egalități și inegalitățile, atunci când există variabile sau restricții privind semnul.

În general, formularea matematică a problemei de programare liniară poate fi scrisă ca:

Aici - funcția obiectiv, liniar în argumentele sale, - numărul de variabile - numărul de constrângeri ale problemei. Condiția (2), (3) definesc constrângerile liniare privind resursele sub forma inegalităților și egalitati, condiție (4) definesc constrângeri asupra variabilelor semn.

Funcția obiectiv. care exprimă criteriul de optimizare, care reflectă obiectivul principal urmărit de obiectul de management - utilizarea eficientă a resurselor. În sectorul industrial indicatorii de performanță sunt, de obicei, venituri sau profit, rezultând într-o problemă de maximizare. Acesta (1.1) este formularea pentru maximizarea funcției obiectiv.

În mod similar, putem scrie problema minimizarea funcției obiectiv. În acest caz, obiectivul este, de obicei, pentru a minimiza costurile.

Condiția (2) pot exprima resursele limitate. De exemplu, costul materialelor, forței de muncă și timpul necesar pentru a pune în aplicare planul de producție nu trebuie să depășească oferta disponibilă. Restricțiile pot reflecta, de asemenea, cererea pentru produsele. Deci, în problemele de dieta si dieta de zi cu zi, starea (2), a stabilit cerințele minime necesare pentru ingredientele (vitamine, unități de alimentare, etc.).

Variabilele sunt numite de gestionat. Aceste variabile sunt aplicate de obicei stare non-negativitate (4), ceea ce corespunde cu sensul lor economic. Variabilele permise și disponibilitate, care nu impun condiții pe semnul.

Rezolvarea problemelor de programare lineară sunt valorile optime ale variabilelor controlate, care asigură o valoare maximă sau minimă a funcției obiectiv.

Orice set ordonat de numere. Se numește o sarcină sau o opțiune. ZLP interpretat ca un vector în spațiu.

Un plan care satisface toate constrângerile ZLP, numit plan fezabil.

În cazul problemei de maximizare (minimizarea) un plan valabil care oferă maxim (minim) funcția obiectiv este numit un plan optim.

Deoarece orice restricție sub forma ecuației poate fi redusă la constrângerile inegalității, precum și orice constrângeri de inegalitate pot fi aduse la o restricție în formă de egalitate prin introducerea de noi variabile manechinului, ZLP inițială poate fi scrisă într-unul din tipuri speciale, standard sau canonice .

Când înregistrați în formular standard, restricțiile sunt formulate sub forma unor inegalități. Standard problemă de vedere maximizarea:

Notă semnul inegalitățile în restricțiile.

Vizualizarea standard a problemei de minimizare:

Când înregistrați în forma canonică (sau clasic), constrângeri formulate sub formă de ecuații.

Forma canonică a problemei maximizare:

1). Ne indică variabilele dorite ale problemei:

- producția zilnică a produsului A (buc.);

- productia zilnica a produsului B (buc.);

- producția zilnică a produsului C (buc.).

2). Definim constrângerile problemei.

a). Limitele de resurse. Consumul de resurse utilizate nu trebuie să depășească marja lor.

b). Restricții privind semnul. volumele de producție de produse nu poate fi negativă.

3). Noi construim funcția obiectiv.

maximizează valoarea totală a producției.

Să ne scrie formularea matematică finală a problemei de maximizare a formularului standard: