Formularea generală a problemei programării liniare (ZLP)

1. Formularea generală a problemei programării liniare (ZLP). Exemplele ZLP.
2. Soluție ZLP geometrică.
3. Teorema principală a programării liniare.
4. Metoda simplex pentru rezolvarea ZLP.
5. Dualitatea în programarea liniară.

programare liniară - ramură a matematicii care studiază metode de rezolvare a problemelor extreme, care sunt caracterizate printr-o relație liniară între variabilele și criteriul optimalității liniar.

Câteva cuvinte despre programarea pe termen liniar. Este nevoie de o înțelegere corectă. În acest caz, programarea - este, desigur, nu de programare de software. Programarea trebuie să fie interpretată ca programarea și modelarea planurilor de dezvoltare, a unui program de acțiune.

Prin problemele matematice de programare liniară includ studii de caz de situații industriale-economice, care într-o formă sau alta sunt interpretate ca problema utilizării optime a resurselor limitate.

Gama de sarcini care pot fi rezolvate folosind metode de programare liniară este destul de largă. Acest lucru, de exemplu:

· Problema utilizării optime a resurselor în planificarea producției;

· Problema amestecurilor (produs personal de planificare);

· Problema de a găsi combinația optimă a diferitelor tipuri de produse pentru depozitare (gestionarea stocurilor sau „problema rucsacului“);

· Sarcini de transport (analiza localizare a plantelor, circulația mărfurilor).

Programarea liniară - secțiunea cea mai dezvoltate și utilizate pe scară largă de programare matematică (în plus, aici includ: număr întreg, dinamic, de programare prin parametri neliniar). Acest lucru este explicat după cum urmează:

· Modele matematice ale unui număr mare de obiective economice liniare în ceea ce privește variabilele necesare;

· Acest tip de activitate este acum cel mai studiat. metode speciale prin care aceste obiective sunt proiectate pentru rezolvat, precum și programul de calculator corespunzător;

· Multe probleme de programare liniară fiind rezolvate, au fost utilizate pe scară largă;

· Unele dintre sarcinile care sunt în formularea inițială nu sunt liniare, după o serie de limitări și ipoteze suplimentare pot fi liniare, sau poate fi redus la o astfel de formă încât să poată fi rezolvate prin programarea liniară.

Modelul economic-matematic cu privire la orice problemă de programare liniară include: o funcție obiectiv. în care valoarea optimă (maximă sau minimă) este necesară pentru a găsi; constrângeri ca un sistem de ecuații liniare sau inegalități; Variabilele cerință de bază non-negativitate.

În general, modelul este scris după cum urmează:

În acest caz, AIJ. bi. cj () - constante prestabilite.

Sarcina este de a găsi valorile optime ale funcției (2.1), în conformitate cu restricțiile (2.2) și (2.3).

constrângeri de sistem (2.2) sunt numite probleme limitări funcționale și constrângeri (2.3) - drepte.

Vector satisface constrângerile (2.2) și (2.3) se numește o soluție fezabilă (planul) a problemei de programare liniară. Planul, pentru care funcția (2.1) ajunge la nazyvaetsyaoptimalnym sa maximă (minim) valoarea.

1. Problema utilizării optime a resurselor în planificarea producției.

Sensul general al acestei clase de probleme este după cum urmează.

Întreprinderea produce produse n diferite. Pentru producția lor necesită m diferite tipuri de resurse (materii prime, de timp și altele asemenea). Resursele sunt limitate, iar rezervele lor în perioada de planificare sunt, respectiv, b1. b2. unități convenționale. bm

Există, de asemenea coeficienți tehnologici AIJ. care arată cât de multe unități ale resursei i-lea este necesară pentru a produce o unitate de produs specii j-lea ().

Profiturile obținute de o întreprindere în punerea în aplicare a produsului de tip j, este cj.

În perioada de planificare valorile AIJ. bi si cj sunt constante.

Este necesară pentru a face o astfel de foaie de parcurs de produs, punerea în aplicare a care întreprinderea a fost profitul ar fi fost mai mare.

Aici este un exemplu simplu de o problemă a acestei clase.

Compania este specializată în producția de crose de hochei, și seturi de șah. Fiecare crosa aduce companiei un profit de $ 2, iar fiecare set de sah - în valoare de $, 4. La fabricarea unui crosa necesită patru ore la partea A și două ore la locul de B. Un set de șah produse cu costuri de șase ore în zona A, șase ore în zona B și o oră la locul C. disponibil porțiunii Capacitatea A este 120 N porțiune -Hours zilnic B - 72 ore și n-secțiunea C - 10 n-ore.

Câte cluburi și seturi de șah care urmează să fie emise de către Societate pe o bază de zi cu zi pentru a obține profit maxim?

Termenii acestei clase de probleme sunt adesea prezentate sub formă de tabel (vezi. Tabelul 2.1).

Tabelul 2.1 - Datele inițiale ale problemei utilizării resurselor de producție

timpul necesar pe unitatea de producție, n-oră