Programare liniară soluții optime admisibile. Cercetări operaționale

Luați în considerare principala problemă de programare liniară (LPP): găsiți valori nenegative ale variabilelor x1, x2, ..., xn care îndeplinesc condițiile m - egalități

și maximizarea funcției liniare a acestor variabile

Pentru simplitate, vom presupune că toate condițiile (1) sunt liniar independente (r \u003d m) și vom argumenta sub această ipoteză.

Orice set de valori non-negative x1, x2,…, xn care îndeplinește condițiile (1) se numește o soluție admisibilă a LPLP. O soluție optimă este cea a soluțiilor admisibile care maximizează funcția (2). Este necesar să se găsească soluția optimă.

Are această problemă întotdeauna o soluție? Nu, nu întotdeauna.

LPP este indecidabil (nu are o soluție optimă):

Datorită incompatibilității sistemului de restricții. Acestea. sistemul nu are o singură soluție, așa cum se arată în Figura 1.

Figura 1 - Incoerența sistemului de restricții

Datorită nelimitării funcției obiective pe setul de soluții. Cu alte cuvinte, atunci când se rezolvă LPP la max, valoarea funcției obiective tinde spre infinit, iar în cazul LPP la min, la minus infinit, așa cum se arată în Figura 2.

Figura 2 - Nelimitarea funcției obiective pe setul de soluții

LPP este rezolvabil:

Multe soluții sunt alcătuite dintr-un singur punct. De asemenea, este optim, așa cum se arată în Figura 3.

Figura 3 - Multe soluții constau dintr-un singur punct

Singura soluție optimă pentru LPP. Linia dreaptă corespunzătoare funcției obiective la pozițiile limitative se intersectează cu multe soluții la un moment dat, așa cum se arată în Figura 4.

Figura 4 - Singura soluție optimă

Soluția optimă pentru LPP nu este singura. Vectorul N este perpendicular pe una dintre laturile setului de soluții. În acest caz, orice punct de pe segmentul AB este optim, așa cum se arată în Figura 5.

Figura 5 - Soluția optimă nu este singura

Rezolvarea problemelor de programare liniară folosind metoda simplex

Metoda simplex este un algoritm pentru rezolvarea problemei LP, care implementează enumerarea punctelor de colț din regiunea soluțiilor fezabile în direcția îmbunătățirii valorii funcției obiective C. Metoda simplex este principala în programarea liniară.

Utilizarea acestei metode în proiectul de diplomă pentru a rezolva problema LP se datorează următorilor factori:

Metoda este universală, aplicabilă oricărei probleme de programare liniară în formă canonică;

Natura algoritmică a metodei face posibilă programarea și implementarea cu succes a acesteia cu ajutorul mijloacelor tehnice.

Extremitatea funcției obiective este întotdeauna atinsă în punctele de colț ale regiunii soluțiilor fezabile. În primul rând, se găsește o soluție inițială (suport) fezabilă, adică orice punct de colț al regiunii de soluții fezabile. Procedura metodei vă permite să răspundeți la întrebarea dacă această soluție este optimă. Dacă da, atunci problema este rezolvată. Dacă este „nu”, atunci se face o tranziție la punctul de colț adiacent al zonei soluției fezabile, unde valoarea funcției obiectivului se îmbunătățește. Procesul de enumerare a punctelor de colț din regiunea soluțiilor fezabile se repetă până când se găsește un punct, care corespunde extremului funcției obiective.

Deoarece numărul vârfurilor politopului este limitat, atunci într-un număr finit de pași este garantat să se găsească valoarea optimă sau să se stabilească faptul că problema este de nerezolvat.

Sistemul de constrângeri este un sistem de ecuații liniare în care numărul de necunoscute este mai mare decât numărul de ecuații. Dacă rangul sistemului este egal, atunci este posibil să alegeți necunoscute care sunt exprimate în termeni de necunoscute rămase. Pentru claritate, se presupune de obicei că sunt selectate primele necunoscute consecutive. Aceste necunoscute (variabile) se numesc de bază, restul sunt gratuite. Numărul de variabile de bază este întotdeauna egal cu numărul de constrângeri.

Atribuind anumite valori variabilelor libere și calculând valorile celor de bază (exprimate în termeni de libere), se obțin diverse soluții la sistemul de constrângeri. De un interes deosebit sunt soluțiile obținute în cazul în care variabilele libere sunt egale cu zero. Astfel de decizii sunt numite de bază. O soluție de bază se numește o soluție de bază admisibilă sau o soluție de suport dacă valorile variabilelor din ea sunt non-negative. Acesta îndeplinește toate restricțiile.

Având un sistem de constrângeri, se găsește orice soluție de bază a acestui sistem. Dacă prima soluție de bază găsită s-a dovedit a fi admisibilă, atunci se verifică optimitatea. Dacă nu este optim, atunci se efectuează trecerea la o altă soluție de bază admisibilă.

Metoda simplex garantează că, cu această nouă soluție, forma liniară, dacă nu atinge optimul, o va aborda. Cu o nouă soluție de bază admisibilă, fac același lucru până când găsesc o soluție optimă.

Dacă prima soluție de bază găsită se dovedește a fi inacceptabilă, atunci folosind metoda simplex, tranziția la alte soluții de bază se efectuează până când la un moment dat al soluției soluția de bază se dovedește a fi admisibilă sau se poate concluziona că sistemul de constrângeri este inconsecvent.

Astfel, aplicarea metodei simplex se împarte în două etape:

Găsirea unei soluții de bază admisibile la un sistem de restricții sau stabilirea faptului că este incompatibilă;

Găsirea soluției optime în cazul compatibilității sistemului de constrângeri.

Algoritmul pentru trecerea la următoarea soluție fezabilă este după cum urmează:

În rândul coeficienților funcției obiective, se selectează cel mai mic număr negativ la găsirea maximului. Numărul de serie al coeficientului este. Dacă nu există, atunci soluția de bază originală este optimă;

Dintre elementele matricei cu numărul coloanei (această coloană se numește conducătoare sau permisivă), sunt selectate elemente pozitive. Dacă nu există, atunci funcția obiectivă este nelimitată în domeniul valorilor admisibile ale variabilelor și problema nu are soluții;

Dintre elementele selectate ale coloanei de bază a matricei, este selectat cel pentru care valoarea raportului termenului liber corespunzător cu acest element este minimă. Acest element se numește conducător, iar linia în care este situat se numește conducător;

Variabila de bază corespunzătoare rândului elementului principal trebuie transferată în categoria celor libere, iar variabila liberă corespunzătoare coloanei elementului principal trebuie introdusă în numărul celor de bază. Este construită o nouă soluție care conține un număr nou de variabile de bază.

Condiția optimității planului la rezolvarea problemei maxime: nu există elemente negative între coeficienții funcției obiective.

Formularea generală a problemei de programare liniară (LPP). Exemple de LPP

Programarea liniară este o ramură a matematicii care studiază metodele de rezolvare a problemelor extreme, care se caracterizează printr-o relație liniară între variabile și un criteriu liniar de optimitate. Câteva cuvinte despre termenul de programare liniară. Necesită înțelegere corectă. În acest caz, programarea nu este, desigur, scrierea de programe pentru computer. Programarea aici ar trebui interpretată ca planificare, formarea planurilor, dezvoltarea unui program de acțiune. Problemele matematice ale programării liniare includ studiul unor situații specifice de producție și economice, care într-o formă sau alta sunt interpretate ca probleme ale utilizării optime a resurselor limitate. Gama de sarcini care pot fi rezolvate folosind metode de programare liniară este destul de largă. Acesta este, de exemplu:

• - problema utilizării optime a resurselor în planificarea producției;
• - problema amestecurilor (planificarea compoziției produselor);
• - problema găsirii combinației optime a diferitelor tipuri de produse pentru depozitare în depozite (gestionarea stocurilor sau „problema rucsacului”);
• - sarcini de transport (analiza locației întreprinderii, deplasarea mărfurilor). Programarea liniară este cea mai dezvoltată și utilizată pe scară largă ramură a programării matematice (în plus, aceasta include: programare întreagă, dinamică, neliniară, parametrică). Acest lucru se datorează următoarelor:
• - modelele matematice ale unui număr mare de probleme economice sunt liniare în raport cu variabilele căutate;
• - acest tip de problemă este în prezent cea mai studiată. Pentru el, au fost dezvoltate metode speciale cu ajutorul cărora sunt rezolvate aceste sarcini și programele de computer corespunzătoare;
• - multe probleme ale programării liniare, după ce au fost rezolvate, au găsit o aplicare largă;
• - unele probleme, care în formularea originală nu sunt liniare, după o serie de restricții și ipoteze suplimentare pot deveni liniare sau pot fi reduse la o astfel de formă încât pot fi rezolvate prin metode de programare liniare. Modelul economic și matematic al oricărei probleme de programare liniară include: o funcție obiectivă, a cărei valoare optimă (maximă sau minimă) trebuie găsită; restricții sub forma unui sistem de ecuații liniare sau inegalități; cerința non-negativității variabilelor. În termeni generali, modelul este scris după cum urmează:
• - funcție obiectivă:

C1x1 + c2x2 + ... + cnxn\u003e max (min); - restricții:

a11x1 + a12x2 + ... + a1nxn (? \u003d?) b1,

a21x1 + a22x2 + ... + a2nxn (? \u003d?) b2

am1x1 + am2x2 + ... + amnxn (? \u003d?) bm;

Cerință de non-negativitate:

În acest caz, aij, bi, cj () sunt date constante. Problema este de a găsi valoarea optimă a funcției (2.1) supusă constrângerilor (2.2) și (2.3). Sistemul de constrângeri (2.2) se numește constrângeri funcționale ale problemei, iar constrângerile (2.3) sunt numite directe. Un vector care îndeplinește constrângerile (2.2) și (2.3) se numește o soluție fezabilă (plan) a problemei de programare liniară. Proiectarea în care funcția (2.1) atinge valoarea maximă (minimă) se numește optimă.

Mai jos sunt exemple de câteva probleme tipice rezolvate folosind metode de programare liniară. Astfel de sarcini au un conținut economic real. Acum le vom formula doar în termeni de LPP și vom lua în considerare metodele de rezolvare a acestor probleme mai jos.

1. Problema utilizării optime a resurselor în planificarea producției. Înțelesul general al sarcinilor acestei clase este următorul. Întreprinderea produce n produse diferite. Producția lor necesită m diferite tipuri de resurse (materii prime, materiale, timp de muncă etc.). Resursele sunt limitate, rezervele lor în perioada de planificare sunt, respectiv, b1, b2, ..., bm unități convenționale. Există, de asemenea, coeficienți tehnologici aij, care arată câte unități ale resursei i-a sunt necesare pentru a produce o unitate a produsului de tip j-a (). Profitul primit de întreprindere din vânzarea produsului de tip j-th este egal cu cj. În perioada de planificare, valorile aij, bi și cj rămân constante. Este necesar să se întocmească un astfel de plan de producție, în a cărui implementare profitul întreprinderii ar fi cel mai mare. Mai jos este un exemplu simplu de activitate a acestei clase.

Compania este specializată în producția de bețe de hochei și seturi de șah. Fiecare club generează profit de 2 USD pentru companie și 4 USD pentru fiecare set de șah. Este nevoie de patru ore pentru a crea un club în site-ul A și două ore în site-ul B. Un set de șah este realizat cu șase ore în site-ul A, șase ore în site-ul B și o oră în site-ul C. Capacitatea de producție disponibilă în site-ul A este 120 Nm. - ore pe zi, secțiunea B - 72 n-ore și secțiunea C - 10 n-ore. Câte cluburi și seturi de șah ar trebui să producă zilnic o companie pentru a maximiza profiturile?

Condițiile pentru problemele acestei clase sunt adesea prezentate sub formă de tabel (vezi Tabelul 2.1).

În această condiție, formulăm o problemă de programare liniară. Să desemnăm: x1 - numărul de bețe de hochei produse zilnic, x2 - numărul seturilor de șah produse zilnic. Formularea ZLP:

4x1 + 6x2? 120,

Să subliniem că fiecare inegalitate din sistemul de constrângeri funcționale corespunde în acest caz cu unul sau alt sit de producție, și anume: primul la situl A, al doilea la situl B și al treilea la situl C.

Sistemul de variabile în problema optimizării structurii suprafețelor însămânțate, ținând cont de rotațiile culturilor

Problema generală de programare liniară (LPP) este formulată după cum urmează - găsiți variabilele problemei x 1 , x 2 , ..., x n, care asigură extremitatea funcției obiective

O soluție (plan) admisibilă a unei probleme de programare liniară (LPP) este orice n-vector dimensional X=(x 1 , x 2 , ..., x n) satisfacerea sistemului de constrângeri de egalitate și inegalitate. Setul de soluții fezabile la problemă formează aria soluțiilor fezabile D.

Soluția optimă (planul) unei probleme de programare liniară este o soluție fezabilă astfel încât funcția obiectivă Z(X) ajunge la o extremă.

Problema de programare liniară canonică (LCPP) are forma

(1.2)

Acesta diferă de OZLP prin faptul că sistemul său de constrângeri este un sistem de doar ecuații și toate variabilele sunt nenegative.

Aducerea OZLP la forma canonică a ZLP:

Pentru a înlocui problema originală de minimizare cu o problemă de maximizare (sau invers, o problemă de maximizare cu o problemă de minimizare), este suficient să multiplicați funcția obiectivului cu „-1” și să căutați maximul (minimul) funcției obținute;

Dacă există inegalități între constrângeri, atunci prin introducerea de variabile suplimentare nenegative x n +1 ≥ 0 se convertesc în egalități:

inegalitate a i 1 x 1 +…+a în x n ≥ b i este înlocuit de egalitate a i 1 x 1 +…+a în x n + x n +1 \u003d b eu,

inegalitate a i 1 x 1 +…+a în x n ≤ b i este înlocuit de egalitate a i 1 x 1 +…+a în x n + x n +1 \u003d b i;

Dacă unele variabile x k nu are restricții de semn, apoi este înlocuit (în funcția obiectivă și în toate restricțiile) de diferența dintre două noi variabile non-negative: x k = x" k – x” k , unde x" k ≥ 0. x” k ≥ 0.

Metoda grafică pentru rezolvarea LPP cu două necunoscute

LPP cu două necunoscute are forma:

Metoda se bazează pe posibilitatea de a afișa grafic zona soluțiilor fezabile și de a găsi soluția optimă printre acestea.

Domeniul soluțiilor fezabile (ODS) al problemei este un poligon convex și este construit ca intersecție (parte comună) a domeniilor de soluții la fiecare dintre inegalitățile constrângerilor problemei.

Domeniul soluției pentru inegalitate a i 1 x 1 +a i 2 x 2 ≤ b i este unul dintre cele două semiplane la care se află linia a i 1 x 1 +a i 2 x 2 = b I-ul corespunzător acestei inegalități împarte planul de coordonate. Pentru a determina care dintre cele două jumătăți de plan este regiunea soluțiilor, este suficient să se substituie coordonatele unui punct care nu se află pe linia de despărțire în inegalitate:

Dacă inegalitatea este adevărată, atunci domeniul soluțiilor este semiplanul care conține acest punct;

Dacă inegalitatea nu este adevărată, atunci domeniul soluțiilor este un semiplan care nu conține acest punct.

Liniile de nivel sunt folosite pentru a găsi soluția optimă printre soluțiile fezabile.

Linia de nivel se numește linie dreaptă. din 1 x 1 +din 2 x 2 = l, unde l= const, pe care funcția obiectivă a sarcinii capătă o valoare constantă. Toate liniile de nivel sunt paralele între ele.

Gradientul funcției obiective grad Z(X) definește vectorul normal C = (c 1 , c 2) linii de nivel. Funcția obiectivă pe liniile de nivel crește dacă liniile de nivel sunt deplasate în direcția normală și scad în direcția opusă.

Linia de referință este o linie de nivel care are cel puțin un punct comun cu ODR și față de care ODR este situat într-unul din semiplanele. IDD-ul problemei nu are mai mult de două linii de suport.

Soluția optimă a ZLP se află pe linia de sprijin în punctul de colț al poligonului ODR. ZLP are o soluție unică dacă linia de suport trece printr-un punct de colț al ODR, un set infinit de soluții dacă linia de suport trece prin marginea poligonului ODR. LPP nu are nicio soluție dacă ODR este un set gol (atunci când sistemul de constrângeri este inconsistent) și dacă ODR este nelimitat în direcția extremului (funcția obiectivului este nelimitată).

Algoritmul unei metode grafice pentru rezolvarea LPP cu două necunoscute:

Construiți un SDT.

Construiește vectorul normal C = (c 1 , c 2) și linia de nivel din 1 x 1 +din 2 x 2 \u003d 0 care trece prin origine și perpendicular pe vector DIN.

Mutați linia de nivel la linia de referință în direcția vectorului DIN în problema pentru max, sau în direcția opusă - în problema pentru min.

Dacă, atunci când linia de nivel se mișcă în direcția extremului, ODR merge la infinit, atunci LPP nu are nicio soluție din cauza nelimitării funcției obiective.

Dacă LPP are o soluție optimă, atunci pentru a o găsi, rezolvați împreună ecuațiile liniilor drepte care limitează GDR și au puncte comune cu linia de sprijin. Dacă extremitatea este atinsă în două puncte de colț, atunci LPP are un set infinit de soluții aparținând marginii ODR delimitată de aceste puncte de colț. În acest caz, se calculează coordonatele ambelor puncte de colț.

Calculați valoarea funcției obiective la punctul extrem.

Metoda simplă pentru rezolvarea LPP

Metoda simplex se bazează pe următoarele prevederi:

ODS al unei probleme de programare liniară este un set convex cu un număr finit de puncte de colț;

Soluția optimă a LPP este unul dintre punctele de colț ale SDT. Punctele de colț ale ODR reprezintă algebric câteva soluții de bază (suport) ale sistemului de constrângere LPP.

Soluția de bază (suport) a LPP se numește o astfel de soluție admisibilă X 0 =( X 10 , x 20 , ..., x m 0, 0, ... 0), pentru care vectorii de condiții (coloane de coeficienți pentru necunoscute în sistemul de constrângeri) sunt liniar independenți.

Coordonate diferite de zero x 10 , x 20 , ..., x m 0 soluții X 0 se numesc variabile de bază, restul coordonatelor soluției X 0 - variabile libere. Numărul de coordonate diferite de zero ale soluției de referință nu poate fi mai mare decât rangul r Sistemul de constrângeri LPP (numărul de ecuații liniar independente din sistemul de constrângeri LPP). Mai mult, presupunem că sistemul de constrângeri LPP constă din ecuații liniar independente, adică r = m.

Semnificația metodei simplex constă într-o tranziție intenționată de la o soluție de referință a LPP la alta (adică, de la un punct de colț al SDT la altul) în direcția extremului și constă într-o succesiune de etape:

Găsiți soluția inițială de asistență;

Efectuați tranziția de la o soluție de referință la alta;

Determinați criteriul pentru realizarea soluției optime sau concluzionați că nu există nicio soluție.

Algoritmul de execuțieMetoda Simplex ZLP

Algoritmul metodei simplex face tranziția de la o soluție de referință a LPP la alta în direcția extremului funcției obiective.

Să se dea LPP în forma canonică (1.2) și condiția

b i ≥ 0, eu=1,2,…,m, (1.3)

relația (1.3) poate fi întotdeauna îndeplinită prin înmulțirea ecuației corespunzătoare cu „-1” în cazul negativității b eu. De asemenea, presupunem că sistemul de ecuații din constrângerile problemei (1.2) este liniar independent și are rang r = m... În acest caz, vectorul soluției de suport are m coordonate diferite de zero.

Să se reducă problema inițială (1.2), (1.3) la forma în care variabilele de bază x 1 , x 2 , ..., x m sunt exprimate în termeni de variabile libere x m + 1 , x m + 2 , ..., x n

(1.4)

Pe baza acestor rapoarte, construim tabelul 1

Tabelul 1.

Tabelul 1 se numește tabel simplex. Toate transformările ulterioare sunt asociate cu modificări ale conținutului acestui tabel.

Algoritm cumetoda implex:

1. În ultima linie Z tabelele simplex din problema min găsesc cel mai mic element pozitiv (în problema max - cel mai mic element negativ), fără a lua în calcul termenul liber. Coloana corespunzătoare acestui element se numește permisivă.

2. Calculați raportul dintre membrii liberi și elementele pozitive ale coloanei de rezolvare (raport simplex). Găsiți cea mai mică dintre aceste relații simplex, se potrivește șirului de rezolvare.

3. La intersecția liniei de rezolvare și a coloanei de rezolvare se află elementul de rezolvare.

4. Dacă există mai multe relații simplex - de aceeași dimensiune, atunci alegeți oricare dintre ele. Același lucru este valabil și pentru elementele pozitive ale ultimului rând al tabelului simplex.

5. După ce ați găsit elementul de rezolvare, mergeți la tabelul următor. Variabilele necunoscute corespunzătoare rândului și coloanei de rezolvare sunt schimbate. În acest caz, variabila de bază devine o variabilă liberă și invers. Simplex - tabelul este convertit după cum urmează (tabelul 2):

masa 2

6. Elementul din tabelul 2 corespunzător elementului permisiv al tabelului 1 este egal cu reciprocitatea elementului permisiv.

7. Elementele rândului din tabelul 2, corespunzător elementelor liniei de autorizare a tabelului 1, se obțin prin împărțirea elementelor corespunzătoare din tabelul 1 la elementul de autorizare.

8. Elementele coloanei din tabelul 2, corespunzătoare elementelor coloanei de autorizare din tabelul 1, se obțin prin împărțirea elementelor corespunzătoare din tabelul 1 la elementul de autorizare și sunt luate cu semnul opus.

9. Restul elementelor sunt calculate de regulă dreptunghiulară: desenează mental un dreptunghi în tabelul 1, un vârf al cărui coincide cu elementul de rezolvare (Re), iar celălalt cu elementul pe care îl căutăm; să denotăm elementul din noul tabel 2 până la (Ne), iar elementul care stă în același loc în vechiul tabel 1 - prin (Se). Celelalte două vârfuri A și B completează forma într-un dreptunghi. Apoi elementul necesar Ne din tabelul 2 este egal cu Ne \u003d Se - A * B / Re.

10. Criteriul de optimitate. De îndată ce obțineți un tabel în care în ultimul rând din problema pentru min toate elementele sunt negative (în problema pentru max toate elementele sunt pozitive), se consideră că extremul a fost găsit. Valoarea optimă a funcției obiective este egală cu termenul liber din linia Z, iar soluția optimă este determinată de termenii liberi cu variabilele de bază. Toate variabilele libere sunt setate egale cu zero.

11. Dacă în coloana de rezolvare toate elementele sunt negative, atunci problema nu are soluții (minimul nu este atins).

Metoda bazei artificiale pentru rezolvarea LPP

Algoritmul metodei simplex este aplicabil dacă este selectată o soluție de suport pentru LPP, adică LPP original (1.2) este redus la forma (1.4). Metoda bazei artificiale oferă o procedură pentru construirea unei astfel de soluții de referință.

Metoda bazei artificiale se bazează pe introducerea variabilelor bazei artificiale y 1 , y 2 ,…, y m, cu ajutorul căruia sistemul constrângerilor LPP (2.2)

(1.5)

poate fi convertit în formă

(1.6)

Sistemele (1.5) și (1.6) sunt echivalente dacă toate y eu va fi egal cu zero. Ca și înainte, credem că totul b eu ≥ 0. Pentru a la eu au fost egale cu 0, trebuie să transformăm problema în așa fel încât toate variabilele artificiale de bază y eu trecute în variabile libere. O astfel de tranziție poate fi realizată de algoritmul metodei simplex în ceea ce privește funcția obiectivă suplimentară

F(y) = y 1 + y 2 + ... + y m \u003d d 0 – (d 1 x 1 + d 2 x 2 +…+d n x n). (2.7)

Tabelul simplex original pentru această metodă este

În primul rând, tabelul simplex este transformat în raport cu funcția obiectivă F(y) până se obține soluția de referință. Soluția de referință se găsește atunci când se îndeplinește următorul criteriu: F(y) \u003d 0 și toate variabilele artificiale la eu traduse în variabile libere. Apoi o linie este ștearsă din tabelul simplex pentru F(y) și coloane pentru la eu și rezolvați problema pentru funcția obiectivă originală Z(x) până se obține o soluție optimă.

O problemă de programare liniară (LPP) este problema de a găsi cea mai mare (sau cea mai mică) valoare a unei funcții liniare pe un set poliedric convex.

Metoda simplex este o metodă pentru rezolvarea unei probleme de programare liniară. Esența metodei este de a găsi un plan inițial fezabil, iar în îmbunătățirea ulterioară a planului până la atingerea valorii maxime (sau minime) a funcției obiective într-un set poliedric convex dat sau clarificarea insolvabilității problemei.

Luați în considerare următoarea problemă de programare liniară în formă canonică:

(1)

(2)

(3)

Metoda bazei artificiale

Așa cum se arată mai sus, pentru o problemă scrisă în formă canonică, dacă este printre vectorii coloanei matricei A există m unic și liniar independent, puteți specifica linia de bază direct. Cu toate acestea, pentru multe probleme de programare liniară scrise în formă canonică și având planuri de suport, printre vectorii de coloană ai matricei A nu întotdeauna acolo m unic și liniar independent. Luați în considerare următoarea problemă:

Să fie necesar să se găsească maximul funcției

în condiții

unde sunt primii n elementele sunt zerouri. Variabile sunt numite artificiale. Coloane de vectori

(28)

formează așa-numita bază artificială m-spatiu vectorial dimensional.

Deoarece problema extinsă are un plan de bază, soluția sa poate fi găsită folosind metoda simplex.

Teorema 4. Dacă în plan optim problema extinsă (24) - (26) valorile variabilelor artificiale atunci este planul optim pentru problema (21) - (23).

Astfel, dacă în planul optim găsit al problemei extinse, valorile variabilelor artificiale sunt egale cu zero, atunci se obține planul optim al problemei inițiale. Să ne gândim mai în detaliu la găsirea unei soluții la problema extinsă.

Valoarea funcției obiective cu planul de referință (27):

Rețineți că F (X) și constă din două părți independente, dintre care una depinde de Miar cealaltă nu este.

După calcul F (X) iar valorile lor, precum și datele inițiale ale problemei extinse, sunt introduse într-un tabel simplex, așa cum se arată mai sus. Singura diferență este că acest tabel conține încă un rând decât un tabel simplex obișnuit. Mai mult, în ( m+1) -al rând sunt plasate coeficienți care nu conțin M, si in ( m+2) -Rândul - coeficienți la M.

Când se trece de la un plan de referință la altul, un vector este introdus în baza care corespunde celui mai mare număr negativ în valoare absolută ( m+2) șiruri. Un vector artificial exclus din bază nu are sens să îl reintroducem în bază. Când treceți la un alt plan de referință, se poate întâmpla ca niciunul dintre vectorii artificiali de la bază să nu fie exclus. Recalcularea unui tabel simplex atunci când se trece de la un plan de bază la altul se efectuează conform regulilor uzuale ale metodei simplex (vezi mai sus).

Procesul iterativ se realizează conform m+2 linie atâta timp cât elementele m+2 linii corespunzătoare variabilelor nu va deveni non-negativ. Mai mult, dacă variabilele artificiale sunt excluse din bază, atunci planul găsit al problemei extinse corespunde unui anumit plan de bază al problemei inițiale.

m+2 rânduri, coloane x 0 este negativ, atunci problema inițială nu are nicio soluție.

Dacă nu toate variabilele artificiale sunt excluse din bază și din element m+2 rânduri, coloane x 0 este egal cu zero, atunci planul de bază al problemei inițiale este degenerat, iar baza conține cel puțin unul dintre vectorii bazei artificiale.

Dacă problema originală conține mai mulți vectori unitari, atunci ar trebui să fie incluși în baza artificială.

Dacă în timpul iterațiilor mLinia +2 nu mai conține elemente negative, apoi procesul iterativ continuă cu m+1 linie, până când se găsește planul optim al problemei extinse sau problema este indecidabilă.

Astfel, procesul de găsire a unei soluții la problema de programare liniară (21) - (23) prin metoda bazei artificiale include următoarele etape principale:

• Problema extinsă (24) - (26) este constituită.
• Găsiți planul de bază al sarcinii extinse.
• Folosind metoda simplex, vectorii artificiali sunt excluși din bază. Ca urmare, se găsește planul de bază al problemei inițiale sau se rezolvă indecidabilitatea acesteia.
• Folosind planul de sprijin găsit al LPP (21) - (23), fie se găsește planul optim al problemei inițiale, fie se stabilește indecidabilitatea acesteia.

Pentru a rezolva probleme de programare liniară online, utilizați un calculator

Componentele modelului matematic

Modelele matematice stau la baza rezolvării problemelor economice.

Model matematic sarcina este un set de relații matematice care descriu esența sarcinii.

Compilarea unui model matematic include:

• selectarea variabilelor sarcinii
• întocmirea unui sistem de restricții
• alegerea funcției obiective

Sarcini variabile se numesc cantitățile X1, X2, Xn, care caracterizează pe deplin procesul economic. De obicei, acestea sunt scrise ca vector: X \u003d (X1, X2, ..., Xn).

Un sistem de restricții problemele sunt numite un set de ecuații și inegalități care descriu resursele limitate din problema luată în considerare.

Funcția țintă sarcina se numește funcția variabilelor sarcinii, care caracterizează calitatea sarcinii și extremitatea pe care doriți să o găsiți.

În general, o problemă de programare liniară poate fi scrisă după cum urmează:

Această notație înseamnă următoarele: găsiți extremul funcției obiective (1) și variabilele corespunzătoare X \u003d (X1, X2, ..., Xn), cu condiția ca aceste variabile să satisfacă sistemul de constrângeri (2) și non-negativitate condiții (3).

O soluție validă (planul) unei probleme de programare liniară este orice vector n-dimensional X \u003d (X1, X2, ..., Xn) care satisface sistemul de constrângeri și condiții de non-negativitate.

Setul de soluții (planuri) fezabile ale formelor problemei gama de soluții fezabile (ODR).

Soluția optimă (planul) unei probleme de programare liniară este o soluție (plan) fezabilă a problemei, în care funcția obiectivă atinge un extremum.

Un exemplu de compilare a unui model matematic Problema utilizării resurselor (materii prime)

Condiție: Pentru fabricarea a n tipuri de produse, se utilizează m tipuri de resurse. Realizați un model matematic.

Cunoscut:

• bi (i \u003d 1,2,3, ..., m) - rezervele fiecărui al i-lea tip de resursă;
• aij (i \u003d 1,2,3, ..., m; j \u003d 1,2,3, ..., n) sunt costurile fiecărui al i-lea tip de resursă pentru producerea unei unități de volum de al j-lea tip de produs;
• cj (j \u003d 1,2,3, ..., n) - profit din vânzarea unei unități de volum a celui de-al zecelea tip de produs.

Este necesar să se elaboreze un plan pentru producția de produse care să asigure un profit maxim pentru constrângeri date asupra resurselor (materii prime).

Decizie:

Introducem vectorul variabilelor X \u003d (X1, X2, ..., Xn), unde xj (j \u003d 1,2, ..., n) este volumul de producție al celui de-al treilea tip de produs.

Costurile pentru al i-lea tip de resursă pentru fabricarea unui anumit volum xj de produse sunt egale cu aijxj, prin urmare, restricția privind utilizarea resurselor pentru producerea tuturor tipurilor de produse este următoarea:
Profitul din vânzarea celui de-al doilea tip de produs este egal cu cjxj, prin urmare funcția obiectivă este egală cu:

Răspuns - Modelul matematic este:

Forma canonică a problemei de programare liniară

În cazul general, o problemă de programare liniară este scrisă astfel încât atât ecuațiile, cât și inegalitățile să fie constrângeri, iar variabilele pot fi atât negative, cât și variabile în mod arbitrar.

În cazul în care toate constrângerile sunt ecuații și toate variabilele îndeplinesc condiția de non-negativitate, problema de programare liniară se numește canonic.

Poate fi reprezentat în notație coordonată, vectorială și matricială.

Problema de programare liniară canonică în notația coordonată are forma:

Problema de programare liniară canonică în notația matricială are forma:

• A este matricea coeficienților sistemului de ecuații
• X - matrice-coloană a variabilelor sarcinii
• Ao - coloana matricei din partea dreaptă a sistemului de restricții

Adesea utilizate sunt probleme de programare liniară, numite simetrice, care în notația matricială au forma:

Reducerea problemei generale de programare liniară la forma canonică

În majoritatea metodelor de rezolvare a problemelor de programare liniară, se presupune că sistemul de constrângeri constă din ecuații și condiții naturale pentru non-negativitatea variabilelor. Cu toate acestea, atunci când se compilează modele de probleme economice, constrângerile se formează în principal sub forma unui sistem de inegalități, deci este necesar să se poată trece de la un sistem de inegalități la un sistem de ecuații.

Acest lucru se poate face după cum urmează:

Luați inegalitatea liniară a1x1 + a2x2 + ... + anxn≤b și adăugați o valoare xn + 1 în partea stângă, astfel încât inegalitatea se transformă în egalitatea a1x1 + a2x2 + ... + anxn + xn + 1 \u003d b . Mai mult, această valoare xn + 1 nu este negativă.

Să luăm în considerare totul cu un exemplu.

Exemplul 26.1

Aduceți problema de programare liniară la forma canonică:

Decizie:
Să ne întoarcem la problema găsirii maximului funcției obiective.
Pentru a face acest lucru, schimbăm semnele coeficienților funcției obiective.
Pentru a transforma a doua și a treia inegalitate a sistemului de constrângeri în ecuații, introducem variabile suplimentare non-negative x4 x5 (pe modelul matematic, această operație este marcată cu litera D).
Variabila x4 este introdusă în partea stângă a celei de-a doua inegalități cu semnul "+", deoarece inegalitatea are forma "≤".
Variabila x5 este introdusă în partea stângă a celei de-a treia inegalități cu semnul "-", deoarece inegalitatea are forma "≥".
Variabilele x4 x5 sunt introduse în funcția obiectiv cu un coeficient. egal cu zero.
Scriem sarcina sub forma canonică: