Formularea problemelor de programare liniară: metode de rezolvare și formare

Pentru economiști, este adesea necesară optimizarea unei funcții de producție, pentru a o maximiza sau minimiza, de exemplu, profitul, pierderea sau alte date supuse unei constrângeri liniare. Înțelegerea problemelor de programare liniară și formularea problemelor - acest lucru necesită cunoștințe de matematică și statistică de bază. Problema de programare liniară (LP) este de a defini o funcție pentru a obține datele optime. Acesta este unul dintre cele mai importante instrumente de cercetare a operațiunilor de afaceri. Este, de asemenea, utilizat pe scară largă ca un ajutor de decizie în multe industrii: economie, informatică, matematică și alte cercetări practice moderne.

Caracteristicile problemelor de programare liniară

Distingem următoarele caracteristici ale LP:

1. Optimizare. La baza problemelor de programare liniară și a formulării problemelor de optimizare se află maximizarea sau minimizarea unei baze de date care face obiectul studiului. Acest lucru este obișnuit în economie, afaceri, publicitate și multe alte domenii care necesită eficiență pentru a conserva resursele. Acestea includ aspecte legate de generarea profitului, achiziționarea de resurse, timpul de producție și alți indicatori economici importanți.
2. Linearitate. După cum sugerează și numele, toate problemele LP au o caracteristică de liniaritate. Cu toate acestea, este uneori înșelătoare, deoarece liniaritatea se referă numai la variabile de gradul 1, excluzând funcțiile de putere, rădăcinile pătrate și alte dependențe neliniare. Aceasta nu înseamnă că funcțiile problemei LP au o singură variabilă. Ea tratează variabilele ca coordonate ale punctelor de pe o linie dreaptă, excluzând orice curbură.
3. Funcția obiectiv. La baza problemelor de programare liniară și a formulării problemelor de obiective stau variabilele care se schimbă la voință, de exemplu timpul petrecut la lucru, unitățile produse. Funcția țintă se scrie cu majusculă "Z".
4. Constrângeri. Toate LP-urile sunt constrânse de variabilele din cadrul funcției. Aceste constrângeri iau forma unor inegalități, de exemplu "b<3", unde b poate reprezenta unități de cărți scrise de autor pe lună. Aceste inegalități definesc modul în care funcția obiectiv poate fi maximizată/minimizată, deoarece împreună definesc zonele de luarea deciziilor.

Termenii de referință definirea sarcinilor

Companiile doresc să maximizeze profitabilitatea operațiunilor lor, astfel încât trebuie să maximizeze utilizarea resurselor pe care le au la dispoziție: umane, materiale, echipamente, instalații și alte resurse. LP este reprezentat de ca un util instrument care să ajute la determinarea celei mai bune soluții în cadrul companiei.

Condiții pentru probleme de programare liniară și enunțuri de probleme necesare pentru maximizarea profitului net. Pentru a rezolva o problemă LP, aceasta trebuie să aibă:

1. Constrângeri sau resurse limitate, de exemplu, un număr limitat de angajați, un număr maxim de clienți sau o limită a pierderilor de producție.
2. Obiectiv: maximizarea veniturilor sau minimizarea costurilor.
3. Liniaritate proporțională. Ecuațiile care generează variabilele de rezolvare trebuie să fie liniare.
4. Omogenitate: caracteristicile variabilelor de decizie și ale resurselor sunt aceleași. De exemplu, orele de muncă ale unei persoane sunt la fel de productive sau bunurile fabricate pe o mașină sunt identice.
5. Divizibilitate: produsele și resursele pot fi reprezentate sub formă de fracții.
6. Fără negativitate: soluțiile trebuie să fie pozitive sau egale cu zero.

Funcția obiectiv în stabilirea unei probleme de programare liniară de bază exprimă matematic scopul care trebuie atins în rezolvarea problemei. De exemplu, pentru a maximiza profitul firmei sau pentru a minimiza costurile de producție.

Aceasta este reprezentată de o ecuație cu soluție variabilă, unde: X 1, X 2, X 3, ..., X n sunt variabile de decizie; C 1, C 2, C 3, ..., C n sunt constante.

Fiecare constrângere este exprimată matematic prin oricare dintre aceste atribute:

1. mai mică sau egală cu (≤). Atunci când există o limită superioară, de exemplu, orele suplimentare nu pot fi mai mult de 2 ore pe zi.
2. Egal (=). Indică o relație obligatorie, de exemplu, stocul final este egal cu stocul inițial plus producția minus vânzările.
3. Mai mare sau egal cu (≥). De exemplu, atunci când există o limită inferioară, producția unui anumit produs trebuie să fie mai mare decât cererea preconizată.
4. Formularea generală a unei probleme de programare liniară începe cu stabilirea constrângerilor.
5. Orice problemă LP trebuie să aibă una sau mai multe constrângeri.
6. Variabilele de decizie pozitive ar trebui să fie luate în considerare în cadrul constrângerilor.

Etapele formulării problemei

Enunțarea generală a unei probleme de programare liniară și formularea ei se referă la transpunerea problemei reale sub forma unor ecuații matematice care pot fi rezolvate.

Etape în stabilirea unei probleme de programare liniară cu numere întregi:

1. Definirea unui număr care dezvăluie comportamentul funcției țintă pentru optimizare.
2. Găsiți un set de constrângeri și exprimați-le sub formă de ecuații sau inegalități liniare. Se va stabili astfel un domeniu în spațiul n-dimensional al funcțiilor optimizate.
3. Trebuie impusă o condiție de non-negativitate pentru variabilele problemei, adică toate trebuie să fie pozitive.
4. Exprimați funcția sub forma unei ecuații liniare.
5. Optimizarea funcției pe cale grafică sau matematică atunci când este îndeplinită formularea matematică a problemei de programare liniară.

Metoda grafică

Metoda grafică este utilizată pentru a realiza probleme LP în două variabile. Această metodă nu se aplică pentru rezolvarea problemelor, care au trei sau mai multe variabile de soluție.

Problema standard de maximizare a necunoscutelor din problemele LP, în care se mărește funcția, supusă unor constrângeri de forma:

x ≥ 0, y ≥ 0, z ≥ 0 și alte constrângeri de formă:

Ax + By + C z +. , ≤ N,

unde A, B, C și N sunt numere nenulegative.

Inegalitățile trebuie să fie "≤" și nu "=" sau "≥".

Metoda grafică LP cu două necunoscute este următoarea:

1. Determinați zonele posibile ale graficului.
2. Calculați coordonatele unghiulare ale punctelor.
3. Înlocuindu-le pentru a vedea valoarea optimă. Acest moment dă o soluție la LP.
4. Minimizați funcția și, dacă coeficienții săi sunt nenegativi, soluția există.

Identificarea soluțiilor existente:

1. Limitați zona prin adăugarea unei linii verticale la dreapta celui mai din dreapta punct de colț și a unei linii orizontale deasupra celui mai înalt punct de colț.
2. Calculați coordonatele noilor puncte de colț.
3. Găsiți punctul de colț cu cea mai bună valoare.
4. Dacă este valabil în punctul inițial al regiunii nemărginite, atunci problema LP are o soluție în punctul dat. În caz contrar, se află de cealaltă parte a liniei, atunci nu are o soluție optimă.

Schițați un set de soluții

Selectați punctul de referință și marcați zona blocată.

Desenați aria reprezentată de o inegalitate a două variabile într-o problemă de programare liniară. Pe scurt, pentru un exemplu:

1. Desenați o linie obținută prin transformarea unei inegalități în egalitate.
2. Selectați punctul de referință (0,0). O alegere bună în cazul în care linia trece prin origine.
3. Dacă punctul de control satisface o inegalitate, atunci setul de soluții este întreaga zonă de pe aceeași parte a liniei cu punctul de control. În caz contrar, se află de cealaltă parte a liniei.
4. Regiunea permisă este definită de un set de inegalități liniare și este un set de puncte care satisfac toate inegalitățile.
5. Pentru a-l desena, definit de un set de inegalități liniare cu două variabile, executați suprafețele reprezentate de fiecare inegalitate pe același grafic, amintindu-vă să nuanțați părțile de plan care nu sunt necesare.

Metoda simplex pentru maximizarea

O problemă de programare liniară cu un model matematic de maximizare poate fi enunțată prin metoda simplex:

1. Transformați datele într-un sistem de ecuații, introducând variabile slabe pentru a transforma constrângerile în ecuații și rescrieți funcția într-o formă standard.
2. Scrieți tabelul original.
3. Selectați coloana de răspândire, numărul negativ cu cea mai mare valoare din rândul de jos, cu excepția celei mai din dreapta. Coloana sa este cumulativă. În cazul în care există doi candidați, selectați unul. Dacă toate numerele din rândul de jos sunt zero sau pozitive, cu excepția celei mai din dreapta, totul este pregătit și soluția de bază maximizează funcția țintă.
4. Selectați tija din coloană. Axa trebuie să fie întotdeauna un număr pozitiv. Pentru fiecare intrare pozitivă "b" din coloana de date sintetice, se calculează raportul "a/b", unde "a" este răspunsul din acest rând. Se alege un raport minim dintre rapoartele de testare, iar numărul corespunzător "b" va fi atunci axa.
5. Folosiți tija pentru a șterge coloana în mod obișnuit, asigurându-vă că urmați întocmai prescripțiile pentru formularea operațiilor pe șiruri descrise în Metoda Gauss-Jordan, și apoi schimbați coloana cu eticheta din coloana.
6. Variabila care desemnează inițial rândul din rezumat este ieșirea, iar variabila care desemnează coloana este intrarea.

Pentru a obține o soluție de bază corespunzătoare oricărui tabel din metoda simplex, setați la zero toate variabilele care nu sunt afișate ca etichete de rânduri. Valoarea etichetei liniei afișate (variabila activă) este numărul din coloana cea mai din dreapta a liniei, împărțit la numărul din această linie din coloana marcată cu aceeași variabilă.

Restricții nestandardizate

Pentru a rezolva o problemă LP cu constrângeri de forma (Ax + By +. , .≥ N) cu N pozitiv, se scade variabila suplimentară din partea stângă (în loc să se adauge variabila slabă). Soluția de bază corespunzătoare tabelului inițial nu va fi fezabilă deoarece unele dintre variabilele active vor fi negative. Regulile pentru rotația inițială sunt, prin urmare, diferite de cele prezentate mai sus.

Apoi, marcați toate rândurile care dau o valoare negativă pentru variabila activă asociată, cu excepția variabilei țintă. În cazul în care există linii marcate, începeți de la etapa I.

I pas. Găsiți cel mai mare număr pozitiv din prima linie. Folosiți coeficienții de testare ca în secțiunea anterioară pentru a găsi rezumatul din această coloană, apoi extindeți această intrare. Se repetă până când nu mai rămân linii marcate, apoi se trece la etapa II.

Etapa a II-a utilizează metoda simplex pentru problema standard de maximizare. În cazul în care există valori negative în rândul din stânga jos după etapa I, se utilizează metoda problemelor standard de maximizare.

Un exemplu de joc care poate fi rezolvat prin metoda simplex.

Instrument online PHPSimplex

În zilele noastre, instrumentele tehnologice facilitează multe activități din viața profesională, iar metodele de rezolvare a problemelor LP nu fac excepție. Acestea au avantajul de a, că este posibil să se obțină soluție optimă de pe orice calculator cu acces la internet.

PHPSimplex este un instrument online excelent pentru rezolvarea problemelor LP. Această aplicație poate rezolva probleme fără restricții privind numărul de variabile și constrângeri. Pentru problemele cu două variabile, demonstrează o soluție grafică și prezintă întregul proces de calcul al soluției optime într-un mod simplu și ușor de înțeles. Are o interfață prietenoasă, apropiată de utilizator, ușor de utilizat și intuitivă, disponibilă în mai multe limbi.

WanerMath: aplicații fără limite

Warneth oferă 2 instrumente pentru a rezolva probleme de programare liniară:

1. Grafic de programare liniară (două variabile).
2. Metoda simplex.

Spre deosebire de alte instrumente în care sunt plasați doar coeficienții, aici sunt incluse toate funcțiile cu variabile. Acest lucru nu este foarte dificil pentru Utilizatori începători, Așa cum site-ul de profil a instrucțiuni de utilizare. În plus, site-ul web dispune de o funcție "Exemple" care creează automat probleme pentru ca utilizatorul să poată evalua performanțele sale, de exemplu, atunci când rezolvă o problemă de programare liniară a transporturilor.

JSimplex este un alt instrument online. Permite rezolvarea problemelor LP fără a limita numărul de variabile. Dispune de o interfață de gestionare simplă care vă solicită să specificați o țintă și un număr de variabile. Utilizatorul scrie coeficienții funcției țintă, constrângerile și face clic pe "solve". Se va prezenta integrarea, calculul celei mai bune opțiuni și rezultatele fiecărei variabile.

După cum puteți vedea, aceste instrumente sunt extrem de utile pentru a învăța cu ușurință cum să rezolvați programarea liniară.

Exemplu simplu de LP

Compania produce calculatoare portabile și științifice. Proiecțiile pe termen lung indică o cerere zilnică preconizată de 150 de calculatoare științifice și 100 de calculatoare portabile. Daily capacitatea de producție permite producerea unui număr maxim de 250 de calculatoare științifice și 200 de calculatoare portabile în fiecare zi.

Pentru a îndeplini contractul de livrare, trebuie să se producă un minim de 250 de calculatoare. Realizarea unuia duce la o pierdere de 20 de ruble, dar fiecare calculator portabil face un profit de 50 de ruble. Trebuie să efectuați calculul pentru a obține profitul net maxim.

Algoritm pentru executarea unui exemplu de problemă de programare liniară:

1. Soluții variabile. Deoarece a fost dat un număr optim de calculatoare, acestea vor fi variabilele pe care le voi folosi în această problemă: x este numărul de calculatoare științifice, y este numărul de calculatoare portabile, y este numărul de calculatoare portabile.
2. Stabiliți o constrângere deoarece compania nu poate produce un număr negativ de calculatoare pe zi, constrângerea naturală ar fi: x ≥ 0, y ≥ 0.
3. Limita inferioară: x ≥ 150, y ≥ 100.
4. Stabiliți o limită superioară pentru aceste variabile din cauza constrângerilor de producție ale întreprinderii: x ≤ 250, y ≤ 200.
5. Constrângere comună asupra valorilor "x" și "y" din cauza comenzii minime de livrat: x + y ≥ 250
6. Optimizați funcția de profit net: P = -20x + 50y.
7. Soluția problemei: Maximizarea lui P = -20x + 50y, cu condiția ca 150 ≤ x ≤ 250; 100 ≤ y ≤ 200; x + y ≥ 250.

Domenii de aplicare

Dintre aplicațiile programării liniare, cele mai frecvente sunt:

1. Planificarea cumulativă a vânzărilor și a operațiunilor. Obiectivul este de a minimiza costurile de producție pe termen scurt, de exemplu, trei și șase luni, satisfăcând cererea preconizată.
2. Planificarea produselor: găsirea celei mai bune combinații de produse, având în vedere că acestea necesită resurse diferite și au costuri diferite. De exemplu, găsiți amestecul optim de elemente chimice pentru benzină, vopsele, alimentație umană și hrană pentru animale.
3. Fluxul de producție: determinarea fluxului optim pentru producția unui produs, care trebuie să treacă prin mai multe procese de lucru în succesiune, în care fiecare are propriile costuri și caracteristici de producție.
4. Formularea unei probleme de transport cu programare liniară, orar. Metoda este utilizată pentru a programa mai multe rute ale unui anumit număr de vehicule pentru a servi clienții sau pentru a obține materiale care trebuie transportate între diferite locații. Fiecare vehicul poate avea o sarcină utilă și o capacitate diferită.
5. Gestionarea stocurilor: determinarea combinației optime de produse care trebuie să fie disponibile în stoc la punctul de vânzare.
6. Programarea personalului: elaborarea unui plan de personal care să satisfacă cererea variabilă preconizată de specialiști cu un număr minim posibil de personal.
7. Controlul deșeurilor: cu ajutorul programării liniare, puteți calcula cum să reduceți deșeurile la minimum.

Acestea sunt câteva dintre cele mai frecvente Aplicații în care se utilizează programarea liniară. În general, orice problemă de optimizare care satisface condițiile de mai sus poate fi rezolvată cu ajutorul acestuia.