Modele microeconomice de programare liniară. Modele de programare liniară dinamică

Programarea liniară este una dintre primele și cele mai amănunțite ramuri ale programării matematice. Programarea liniară a fost secțiunea din care a început să se dezvolte disciplina „programare matematică”. Termenul „programare” din numele disciplinei nu are nimic în comun cu termenul „programare (adică compilarea de programe) pentru un computer”, deoarece disciplina „programare liniară” a apărut chiar înainte de momentul în care calculatoarele au început să fie utilizate pe scară largă. în rezolvarea problemelor de matematică și de inginerie, probleme economice și de altă natură. Termenul „programare liniară” a apărut ca urmare a unei traduceri inexacte a limbajului englezesc „programare liniară”. Unul dintre semnificațiile cuvântului „programare” este a face planuri, a planifica. Prin urmare, traducere corectă„programare liniară” nu ar fi „programare liniară”, ci „planificare liniară”, care reflectă mai exact conținutul disciplinei. Cu toate acestea, termenul de programare liniară, programare neliniară etc. au devenit general acceptate în literatura noastră.

Așadar, programarea liniară a apărut după al Doilea Război Mondial și a început să se dezvolte rapid, atrăgând atenția matematicienilor, economiștilor și inginerilor datorită posibilității unei largi aplicație practică, precum și „armonie” matematică.

Putem spune că programarea liniară este aplicabilă construirii modelelor matematice ale acelor procese care se pot baza pe ipoteza unei reprezentări liniare. lumea reala: sarcini economice, sarcini de management și planificare, amplasare optimă echipamente etc.

Sarcini programare liniară se numesc probleme în care atât funcţia obiectiv cât şi constrângerile sub formă de egalităţi şi inegalităţi sunt liniare. Pe scurt, problema de programare liniară poate fi formulată după cum urmează: găsiți un vector de valori ale variabilelor care livrează extremul liniarului funcție obiectivă sub m restricţii sub formă de egalităţi sau inegalităţi liniare.

Programarea liniară este cea mai frecvent utilizată metodă de optimizare. Problemele de programare liniară includ următoarele:

· utilizare rațională materii prime și consumabile; probleme de optimizare a tăierii;
· optimizare program de producție intreprinderi;
· amplasarea optimă și concentrarea producției;
· întocmirea unui plan optim de transport și operațiune de transport;
· managementul stocurilor;
· si multe altele apartinand domeniului planificarii optime.

Astfel, conform experților americani, aproximativ 75% din numărul total de metode de optimizare utilizate sunt programare liniară. Aproximativ un sfert din timpul petrecut la calculator anul trecut pentru a efectua cercetări științifice, a fost dedicat rezolvării problemelor de programare liniară și a numeroaselor modificări ale acestora.

Formularea problemei de optimizare presupune existența unor proprietăți concurente ale procesului, de exemplu:

cantitatea produselor – consumul de materii prime
cantitatea produselor - calitatea produselor

Alegerea unei opțiuni de compromis pentru proprietățile specificate este procedura de rezolvare a problemei de optimizare.

Când configurați o problemă de optimizare, trebuie să:

1. Disponibilitatea unui obiect de optimizare și obiectiv de optimizare. Mai mult, formularea fiecărei probleme de optimizare ar trebui să necesite o valoare extremă de o singură valoare, adică. În același timp, două sau mai multe criterii de optimizare nu ar trebui să fie atribuite sistemului, deoarece Aproape întotdeauna, extremul unui criteriu nu corespunde cu extremul altuia. Să dăm exemple.

Un exemplu tipic de formulare incorectă a unei probleme de optimizare:

"Obține performanță maximă cu costuri minime.”

Greșeala constă în faptul că sarcina este de a găsi optimitatea a 2 valori care se contrazic în esența lor.

Formularea corectă a problemei ar putea fi următoarea:

a) obținerea productivității maxime la un cost dat;
b) obţinerea costului minim pentru o anumită productivitate;

În primul caz, criteriul de optimizare este productivitatea, iar în al doilea, costul.

2. Disponibilitatea resurselor de optimizare, care este înțeleasă ca abilitatea de a selecta valorile unor parametri ai obiectului optimizat.
3. Posibilitatea de evaluare cantitativă a valorii optimizate, deoarece numai în acest caz este posibil să se compare efectele alegerii anumitor acțiuni de control.
4. Luarea în considerare a restricțiilor.

De obicei, valoarea optimizată este legată de eficiența de funcționare a obiectului în cauză (dispozitiv, atelier, uzină). Versiunea optimizată a funcționării obiectului trebuie evaluată printr-o măsură cantitativă - un criteriu de optimitate.

Se numeste criteriul de optimitate cuantificare calitate optimizată a obiectului.

Pe baza criteriului de optimitate selectat se alcătuiește o funcție obiectiv, care reprezintă dependența criteriului de optimitate de parametrii care îi influențează valoarea. Se determină tipul criteriului de optimitate sau funcției obiective sarcina specifica optimizare.

Astfel, problema de optimizare se reduce la găsirea extremului funcției obiectiv.

În funcție de formularea acestuia, oricare dintre problemele de optimizare poate fi rezolvată diverse metode, și invers - orice metodă poate fi folosită pentru a rezolva multe probleme. Metodele de optimizare pot fi scalare (optimizarea se realizează după un singur criteriu), vectorială (optimizarea se realizează după mai multe criterii), căutare (inclusiv metode de căutare regulate și aleatorii), analitice (metode de calcul diferențial, metode de calcul al variațiilor etc. .), computaționale (pe baza de programare matematică, care poate fi liniară, neliniară, discretă, dinamică, stocastică, euristică etc.), probabilitate-teoretică, joc-teoretică etc. Problemele cu sau fără restricții pot fi optimizate.

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 ecuatii lineare sau inegalități; cerinţa de non-negativitate a variabilelor.

ÎN vedere generala modelul este scris astfel:

Funcție obiectivă:

În acest caz, aij, bi, cj () primesc valori constante.

Sarcina este de a găsi valoare optimă funcția (1.1) supusă constrângerilor (1.2) și (1.3).

Sistemul de constrângeri (1.2) se numește constrângeri funcționale ale problemei, iar constrângerile (1.3) sunt numite directe.

Un vector care satisface constrângerile (1.2) și (1.3) se numește soluție admisibilă (plan) a unei probleme de programare liniară. Planul în care funcția (1.1) își atinge valoarea maximă (minimă) se numește optim.

Model de programare liniară– model inclusiv funcție liniară obiective definite dependență liniară pe mai multe variabile și restricții liniare asupra acestor variabile.

Provocări extreme

Să ne amintim asta cuvânt latin extremumînseamnă „extrem”. Are două semnificații specifice în matematică: maxim(abreviat max) - cel mai mare și minim(abreviat min) - cel puțin. În această înțelegere extremum are mai mult sens restrâns, Cum optim, tradus din latină ca „cel mai bun”.
Problema găsirii valorii maxime sau minime funcţie dată pe o mulţime dată se numeşte problema extrema.
Există două tipuri de probleme extreme - o problemă maximă și o problemă minimă. Simbolic ele sunt scrise astfel:

Se numește funcția f(x). funcția țintă, și X - set de soluții fezabile. Soluția optimă probleme se numește pereche (x*,f(x*)), unde x* este punctul maxim (minim), iar f(x*) este valoarea funcției f în acest punct, adică maximul acesteia ( minim) pe set X.
Rezolvarea problemelor înseamnă: fie găsirea soluției optime; sau asigurați-vă că soluția optimă nu există.
Rezolvarea problemei presupune rezolvarea a trei probleme: 1) problema existenţei soluție optimă; 2) problema stabilirii semnelor necesare și suficiente de optimitate (adică proprietăți caracteristice inerente punctelor maxime și minime); 3) problema calculului numeric al soluţiilor optime.

Exemplul nr. 1. Construiți un model matematic al următoarei probleme a activității economice. Pentru aceasta:

Identificați problema și formulați scopul cercetării.
Descrieți variabilele proces economic sau obiect.
Scrieți formularea matematică a funcției scop.
Formulați restricțiile impuse de condițiile problemei și notați sistemul de restricții.
Propuneți o metodă de rezolvare.

Designerii de mașini au sarcina de a proiecta cea mai ieftină caroserie posibilă material din tabla, sticla si plastic. Principalele caracteristici ale materialelor sunt prezentate în tabel.

Caracteristici	Materiale
Caracteristici	Metal	Sticlă	Plastic
Cost (mii de ruble/m2)	25	20	40
Greutate (kg/m2)	10	15	3

Suprafața totală a caroseriei (inclusiv ușile și ferestrele) trebuie să fie de 14 m2: din aceasta, cel puțin 3,5 m2 și nu mai mult de 5 m2 trebuie alocate sub sticlă. Greutatea corpului nu trebuie să depășească 150 kg, iar greutatea plasticului nu trebuie să depășească 20% din greutatea corpului. Componenta metalică a suprafeței corpului trebuie să fie de cel puțin două ori mai mare decât suprafața sticlei. Cât metal, sticlă și plastic ar trebui să folosească cel mai bun design.

Problema constă în resursele limitate pentru a obține rezultate optime.

Descrierea variabilelor.
x 1 - cantitate de metal, m 2
x 2 - cantitate de sticlă, m 2
x 3 - cantitate de plastic, m 2

Funcția de gol.

Restrictii:

Suprafața totală a corpului
x 1 + x 2 + x 3 ≥ 14
Cerințe de sticlă
x 2 ≥ 3,5
x 2 ≤ 5
Restricții de greutate
10x 1 + 15x 2 + 3x 3 ≤ 150
Cerințe de greutate din plastic
3x 3 ≤ (10x 1 + 15x 2 + 3x 3)*20%
Restricții de suprafață
x 1 ≥ 2x 2

Sistemul de restricții.
x 1 + x 2 + x 3 ≥ 14
10x 1 + 15x 2 + 3x 3 ≤ 150
2x 1 + 3x 2 - 2,4x 3 ≥ 0
x 1 - 2x 2 ≥ 0
x 2 ≥ 3,5
x 2 ≤ 5
x 1 , x 2 , x 2 ≥ 0
F(x) = 25x 1 + 20x 2 + 40x 3 → min

Exemplul nr. 2. Fabrica produce țesături din două articole. Fiecare dintre aceste țesături este supusă procesării secvențiale pe trei tipuri de mașini. Mai jos sunt indicate: productivitatea fiecărui tip de mașină în producerea țesăturilor articolelor 1 și 2; capacitatea totală a parcului de mașini al fabricii pe o săptămână de lucru; costurile forței de muncă pentru întreținerea mașinilor în minute de timp de lucru la 1 oră de funcționare a mașinii; prețul unui metru de țesătură pentru fiecare articol. De asemenea, se știe că resursa de muncă săptămânală pentru întreținerea mașinilor este de 14.800 de ore.

Tip mașină	Putere (mii de ore)	Costuri cu forța de muncă (min/h)	Productivitate, m/h
Tip mașină	Putere (mii de ore)	Costuri cu forța de muncă (min/h)	articolul 1	Articolul 2
1	22	10	20	15
2	40	6	12	6
3	75	6	6	4
Prețul 1 m de țesătură (mii de ruble)			18	25

Este necesar să se întocmească un plan săptămânal de producție a țesăturilor pentru a maximiza profitul produselor fabricate, dacă se plătește 1 oră în valoare de 5400 de ruble, iar 1 oră de oprire a mașinii de primul tip este de 1800 de ruble, al 2-lea. tipul este de 2000 de ruble, al treilea tip este de 1400 de ruble. Costul materiilor prime nu este luat în considerare. La rezolvarea problemei, ar trebui să se țină cont de faptul că producția de material textil de la articolul 1 trebuie să fie de cel puțin 2 ori mai mare decât producția de material textil de la articolul 2.

Descrierea variabilelor.
x 1 - producția de țesături articolul 1, m
x 2 - producția de țesături articolul 2, m

y 1 - timpul de funcționare al primei mașini, oră.
y 2 - timpul de funcționare al celei de-a 2-a mașini, oră.
y 3 - timpul de funcționare al celei de-a 3-a mașini, oră.

y 1 = x 1 /20 + x 2 /15
y 2 =x 1 /12 + x 2 /6
y 3 =x 1 /6 + x 2 /4
x 1, x 2, y 1, y 2, y 3 ≥ 0

Restrictii:

după structura de ieşire
x 1 ≥ 2x 2
prin costurile forţei de muncă
10/60 ani 1 + 6/60 ani 2 +6/60 ani 3 ≤ 14800
sau
1/6a 1 + 1/10a 2 +1/10a 3 ≤ 14800
in functie de capacitatile disponibile:
y 1 ≤ 22000
y 2 ≤ 40000
y 3 ≤ 75000

Funcția de gol.
Profit = Venituri - Costuri = Preț*Cantitate - Costuri de oprire a mașinii - Costuri cu forța de muncă
Venituri = 18x 1 + 25x 2
Costurile de oprire a mașinii = 1,8 ai 1 + 2 ai 1 + 1,4 ai 3
Costurile forței de muncă = 5,4(1/6a 1 + 1/10a 2 +1/10a 3)

F(x) = 18x 1 + 25x 2 - 1.8y 1 - 2y 2 - 1.4y 3 - 5.4(1/6y 1 + 1/10y 2 +1/10y 3)→ max
sau
F(x) = 1/50 (900x 1 +1250x 2 -135y 1 -127y 2 -97y 3) → max

Tinand cont
y 1 = x 1 /20 + x 2 /15
y 2 =x 1 /12 + x 2 /6
y 3 =x 1 /6 + x 2 /4

avem:

Sistemul de restricții.
x 1 ≥ 2x 2
1/6(x 1/20 + x 2/15) + 1/10(x 1/12 + x 2/6) +1/10(x 1/6 + x 2/4) ≤ 14800
x 1 /20 + x 2 /15≤ 22000
x 1 /12 + x 2 /6 ≤ 40000
x 1 /6 + x 2 /4 ≤ 75000

x 1 ≥ 2x 2
x 1 /30+19x 2 /360 ≤ 14800
x 1 /20 + x 2 /15≤ 22000
x 1 /12 + x 2 /6 ≤ 40000
x 1 /6 + x 2 /4 ≤ 75000

F(x) = 17,33x 1 +23,91x 2 → max

Exemplul nr. 3. Întreprinderea are două ateliere. Primul atelier angajează 50 de muncitori, dintre care 20 au categoria a 6-a și 30 au categoria a treia. În al doilea atelier, din 100 de muncitori, 50 au categoria a 6-a, iar restul au a treia. Este necesară finalizarea unei comenzi pentru producția a 2 tipuri de piese. Un lucrător din categoria a 6-a petrece 10 minute pentru fabricarea unei piese de primul tip, iar un lucrător din categoria a 3-a petrece 15 minute. Un lucrător din categoria a 6-a petrece 25 de minute pentru fabricarea unei piese de al doilea tip, iar un lucrător din a treia categorie petrece 30 de minute.
13) întocmește un plan de producție pentru fiecare dintre ateliere pe o săptămână, pe baza duratei standard a săptămânii de lucru, maximizând volumul total de producție, ținând cont de faptul că necesarul de piese de al doilea tip este la jumătate la fel ca nevoia de piese de primul tip.
14) Determinați planul de producție pentru fiecare dintre ateliere pentru o săptămână, pe baza duratei standard a săptămânii de lucru, maximizând profitul, ținând cont de faptul că un muncitor de categoria a 6-a primește 300 de ruble/lună, iar un muncitor de categoria a 3-a primește 200 de ruble/lună. , în ciuda faptului că prețul de vânzare al unei părți din primul tip este de 20 de ruble/buc, iar al doilea tip este de 34 de ruble/buc.

Soluţie.
x 11 - numărul de piese de tip 1 produse de lucrătorii din categoria a 6-a pe săptămână,
x 12 - numărul de piese de tip 2 produse de lucrătorii din categoria a 6-a pe săptămână,
x 21 - numărul de piese de tip 1 produse de lucrători din categoria 3 pe săptămână,
x 22 - numărul de piese de tip 2 produse de lucrători din categoria 3 pe săptămână,

13) Funcția obiectivă
20x 11 + 50x 21 + 30x 12 + 50x 22 = max

Restrictii:
2(x 12 +x 22) ≤ x 11 +x 21

14) Funcția obiectivă: Profit = Venituri - Costuri = Număr de piese * Preț de vânzare - Salariul angajaților
Vom reduce costurile cu salariile muncitorilor la cele săptămânale, adică împărțim câștigurile lunare la 4.
F(x) = 20(20x 11 + 50x 21) + 23(30x 12 + 50x 22) - [(20+50)*300 + (30+50)*200]/4 = max.

Restrictii:
2(x 12 +x 22) ≤ x 11 +x 21
10/60x 11 + 15/60x 21 + 25/60x 11 + 30/60x 21 ≤ N
N - fond de timp săptămânal în ore.

Programare matematică(„planificare”) este o ramură a matematicii care se ocupă cu dezvoltarea metodelor de găsire a valorilor extreme ale unei funcții ale cărei argumente sunt supuse restricțiilor. Ideea programării liniare a apărut în 1939, când broșura lui Leonid Vitalievich Kantorovich " Metode matematice organizarea și planificarea producției.” Matematicianul american A. Danzig a dezvoltat în 1947 o metodă specifică foarte eficientă pentru rezolvarea numerică a problemelor de programare liniară (a fost numită metoda simplex ).

Prezentarea ulterioară a materialului presupune că studenții au studiat teoria programării liniare într-un curs de matematică. Prin urmare, este recomandat să combinați citirea acestui capitol cu vizualizarea prezentărilor. Versiunile electronice ale prezentărilor se află în folderul „Programare liniară”. În același timp, o parte din material este destinată restabilirii cunoștințelor dobândite la cursul de matematică, iar o parte a acestuia este extinderea și aprofundarea acestuia, cu accent pe capacitățile aplicate ale modelelor teoretice.

Teoria programarii liniare

Prezentarea generală a problemei

Ideea de programare liniară este prezentată în format de prezentare, versiune electronica care se află în fișierul „Idee - Programare liniară”.

Interpretarea geometrică și metoda grafica solutii

Este recomandabil să folosiți o metodă grafică pentru rezolvarea problemelor de programare liniară:

1. Să rezolve probleme cu două variabile, când constrângerile sunt exprimate prin inegalități.

2. Soluții la probleme cu multe variabile, cu condiția ca notația canonică a acestora să nu conțină mai mult de două variabile libere.

Metoda geometrică pentru rezolvarea problemelor de programare liniară este prezentată în format de prezentare - fișierul „Metoda Geometric LP”

2.2. metoda simplex, caracteristici generale, criteriul de optimitate pentru un plan de bază admisibil

Metoda grafică rezolvarea unei probleme de programare liniară arată că soluția optimă a acestei probleme este întotdeauna asociată cu un punct de colț al spațiului de soluții (în matematică se mai numește punctul extrem al setului ). Aceasta este idee cheie la dezvoltarea unei metode simplex algebrice generale pentru rezolvarea oricărei probleme de programare liniară.

Trecerea de la metoda geometrică de rezolvare a unei probleme de programare liniară la metoda simplex se realizează prin descrierea algebrică a punctelor extreme ale spațiului soluției. Pentru a implementa această tranziție, mai întâi trebuie să aduceți problema de programare liniară la forma standard (canonică):

· transformarea inegalităților de restricții în egalități prin introducerea de variabile suplimentare;

· convertirea variabilelor libere în variabile nenegative;

· transforma problema de maximizare într-o problemă de minimizare.

Forma standard a problemei de programare liniara este necesara deoarece ne permite sa obtinem solutie de baza(folosind sistemul de ecuații generat de constrângeri). Această soluție de bază (algebrică) determină complet toate punctele extreme (geometrice) ale spațiului soluției. Metoda simplex vă permite să găsiți eficient soluția optimă dintre toate cele de bază.

Vă puteți restabili cunoștințele de rezolvare a problemelor folosind metoda simplex folosind prezentarea „Metoda Simplex”.

Probleme duble

Orice problemă de programare liniară are o natură duală. Regula de construcție dubla problema:

Dacă problema initiala pe max, apoi dual pe min si invers.

Într-o problemă duală există atâtea variabile câte constrângeri există în formularea originală. În acest caz, variabilele corespund restricțiilor și invers.

Coeficienții funcției obiective a problemei duale sunt părțile din dreapta ale constrângerilor problemei inițiale.

Matricea coeficienților de constrângere a problemei duale se obține prin transpunerea matricei de coeficienți de constrângere a problemei inițiale.

Părțile din dreapta ale constrângerilor problemei duale sunt coeficienții funcției obiective a celei originale.

Constrângerile de inegalitate ale problemei inițiale corespund variabilelor nenegative ale problemei duale, iar constrângerile de egalitate corespund variabilelor de orice semn și invers.

Teorema 1: Dacă problema inițială are un plan optim x*, atunci problema duală are și un plan optim y*, iar valorile funcțiilor de pe aceste planuri sunt egale: f(x*)=g(y* ).

Teorema 2: Dacă problemele originale și duale au planuri, atunci au și planuri optime, iar f(x*)=g(y*).

Criterii de optimizare pentru probleme duble:

Semnul 1: Dacă problemele originale și duale au planuri X și Y și f(X)=g(Y), atunci aceste planuri sunt optime.

Definiție: Constrângerile situate pe aceeași linie în diagrama unei perechi de probleme duale se numesc conjugate.

Semnul 2: Pentru ca planurile X și Y ale problemelor originale și duale să fie optime, este necesar și suficient ca pe aceste planuri cel puțin una din fiecare pereche de constrângeri conjugate să fie o egalitate.

A doua caracteristică permite, cunoscând planul optim al uneia dintre sarcini, să se găsească planul optim al altei sarcini.

Principiile principale ale problemei duale sunt prezentate în prezentările „Teoria dualității” și „Problema duală”.

Sarcini de transport

Problema transportului este una dintre cele mai comune probleme speciale de programare liniară. Prima producție strictă problema de transportîi aparține lui F. Hitchcock, iar prima metodă de soluție exactă a fost dezvoltată de L. V. Kantorovich și M. K. Gavurin.

Denumirea „problemă de transport” combină o gamă largă de probleme cu un singur model matematic. Aceste probleme aparțin problemelor de programare liniară și pot fi rezolvate folosind metoda simplex. Cu toate acestea, matricea sistemului de constrângeri a problemei transportului este atât de unică încât au fost dezvoltate metode speciale pentru a o rezolva. Aceste metode, cum ar fi metoda simplex, fac posibilă găsirea unei soluții inițiale de referință, iar apoi, îmbunătățind-o, obținerea unei soluții optime.

Termenul „sarcini de transport” se referă la o gamă largă de sarcini nu numai de natură de transport. Ceea ce au în comun este, de regulă, distribuția resurselor deținute de m producatori (furnizori), conform n consumatori ai acestor resurse. Există două tipuri de probleme de transport: conform criteriul costului(planul de transport este optim dacă se realizează costurile minime pentru implementarea lui) și dupa criteriul timpului(un plan este optim dacă se petrece un minim de timp pentru implementarea lui).

Cele mai frecvente sarcini legate de transport sunt:

· Atașarea consumatorilor de resurse de producători;

· legarea punctelor de plecare cu punctele de destinație;

· legătura reciprocă a fluxurilor directe și directe de marfă direcții inverse;

· sarcini individuale de încărcare optimă a echipamentelor industriale;

· distributie optima volumele producției industriale între fabricile de producție etc.

Enunțuri de probleme de tip transport, algoritmi de rezolvare a acestora și exemple uz practic prezentat în trei prezentări:

1. „Problemă generalizată de transport (problema λ).”

2. „Problemă de transport închis. Metoda potențialelor”.

3. „Formulări complicate ale problemei transportului.”

Aplicații economice

Varietate de aplicații economice modelare matematică Să luăm în considerare metodele de programare liniară folosind exemple de formulare de formulări specifice ale problemelor aplicate (împrumutate dintr-un curs de prelegeri de A.P. Diyazitdinova).

Problema 1

Pentru a menține funcțiile normale de viață, o persoană trebuie să consume cel puțin 120 de unități convenționale de proteine (unități arb.), grăsimi – cel puțin 70 și vitamine – cel puțin 10 unități convenționale pe zi. unitati Conținutul lor în fiecare unitate de produse P 1 și P 2 este egal, respectiv, cu (0,2; 0,075; 0) și respectiv (0,1; 0,1; 0,1) arb. unitati

Cost 1 unitate. produs P 1 – 2 frecții, P 2-3 frecare.

Construiți un model matematic al problemei care vă permite să organizați alimentația în așa fel încât costul acesteia să fie minim, iar organismul să primească suma necesară nutrienți.

Problema 2

Trenurile de pasageri și cele rapide pleacă de la punctul A la punctul B în fiecare zi. Datele privind organizarea transportului sunt următoarele:

Câte trenuri rapide și de călători trebuie să fie formate pentru a transporta cel mai mare număr pasageri?

Problema 3

Patru depozite de legume furnizează trei magazine cu cartofi în fiecare zi. Magazinele au depus oferte pentru 17, 12 și, respectiv, 32 de tone. Spațiile de depozitare a legumelor au o capacitate de 20, 20, 15 și, respectiv, 25 de tone. Tarifele (în unități pe 1 tonă) sunt indicate în următorul tabel:

Problema 4

Există două depozite pentru produse finite: A 1 și A 2 cu stocuri de marfă omogenă de 200 și 300 de tone. Această marfă trebuie să fie livrată la trei consumatori ÎN 1 , ÎN 2 și ÎN 3 în cantități de 100, 150 și, respectiv, 250 de tone. Costul transportului a 1 tonă de marfă dintr-un depozit A 1 consumatori ÎN 1 , ÎN 2 și ÎN 3 este egal cu 5, 3,6 unități, iar din depozit A 2 la aceiași consumatori – 3, 4, 2 unități. respectiv.

Creați un plan de transport care minimizează costurile totale de transport.

Problema 5

La îngrășare, fiecare animal trebuie să primească cel puțin 9 unități. proteine, 8 unități. carbohidrați și 11 unități. proteină. Pentru alcătuirea dietei se folosesc două tipuri de furaje, prezentate în tabelul următor.

Costul a 1 kg de furaj de primul tip este de 4,00, al doilea – 6,00.

Creați un plan alimentar zilnic care are un cost minim.

Problema 6

Ferma dispune de urmatoarele resurse: suprafata - 100 unitati, manopera - 120 unitati, tractiune - 80 unitati. Ferma produce patru tipuri de produse: P 1 , P 2 , P 3 și P 4 . Organizarea producției este caracterizată de următorul tabel:

Întocmește un plan de producție care să asigure fermei profit maxim.

Sarcina 7.

Atelierul produce două tipuri de transformatoare. Fierul și sârma sunt folosite pentru a face ambele tipuri de transformatoare. Furnizarea totală de fier este de 3 tone, sârmă - 18 tone. Un transformator de primul tip consumă 5 kg de fier și 3 kg de sârmă, iar un transformator de al doilea tip consumă 3 kg de fier și 2 kg de sârmă. Pentru fiecare transformator vândut de primul tip, instalația primește un profit de 3 unități, din al doilea - 4 unități.

Întocmește un plan pentru producția de transformatoare care să asigure un profit maxim pentru centrală.

Problema 8

Ferma de stat a alocat trei mase de teren de 5000, 8000 și 9000 de hectare pentru plantarea de secară, grâu și porumb. Randamentul mediu în cenți la 1 hectar pentru matrice este indicat în următorul tabel:

Culturi	Matrice
eu	II	III
secară
grâu
porumb

Pentru 1 chintal de secară ferma de stat primește 2 UC, pentru 1 chintal de grâu – 2,8 UM, pentru 1 chintal de porumb – 1,4 UC. Câte hectare și pe ce suprafețe ar trebui să dedice ferma de stat fiecărei culturi pentru a obține venituri maxime, dacă conform planului este obligată să livreze cel puțin 1.900 de tone de secară, 158.000 de tone de grâu și 30.000 de tone de porumb?

Problema 9

Un amestec este format din trei produse - I, II, III. Amestecul trebuie să conțină cel puțin 6 unități. substanță chimică A, 8 unități. – substanțe B și cel puțin 12 unități. substanțele C. Structura substanțelor chimice este dată în următorul tabel:

Produs	Conținut chimic într-o unitate. produse	Cost 1 unitate. produse
A	ÎN	CU
eu
II
III		1,5	2,5

Faceți cel mai ieftin amestec posibil.

Problema 10

Școala organizează un concurs pentru cel mai bun ziar de perete. Un elev a primit următoarea sarcină:

cumpărați vopsea de acuarelă la un preț de 30 de ruble. per cutie, creioane colorate pret la 20.00. per cutie, rigle pentru 12 ruble, blocnote pentru 10 ruble;

Trebuie să cumpărați cel puțin trei cutii de vopsele, tot atâtea caiete câte cutii de creioane și vopsele sunt împreună, nu mai mult de cinci rigle. Cel puțin 300 de ruble sunt alocate pentru achiziții.

În ce cantitate trebuie studentul să cumpere articolele specificate pentru a numărul total au fost cele mai puține articole?

Problema 11

Există trei ateliere specializate în repararea motoarelor. Capacitățile lor de producție sunt egale cu 100, 700, respectiv 980 de reparații pe an. În cele cinci zone deservite de aceste ateliere, necesarul de reparații este respectiv de 90, 180, 150, 120, 80 de motoare pe an. Costurile transportului unui motor de la raioane la ateliere sunt următoarele:

Districte	Ateliere

	4,5	3,7	8,3
	2,1	4,3	2,4
	7,5	7,1	4,2
	5,3	1,2	6,2
	4,1	6,7	3,1

Planificați numărul de reparații pentru fiecare atelier pentru fiecare zonă care minimizează costurile totale de transport.

Problema 12

Rafinăria de petrol primește patru semifabricate: 400 de mii de litri de alchilat, 250 de mii de litri de benzină cracată, 350 de mii de litri de benzină de distilare directă și 100 de mii de litri de izopentonă. Ca rezultat al amestecării acestor patru componente în proporții diferite, se formează trei grade de benzină pentru aviație: benzină A-2:3:5:2, benzină B-3:1:2:1, benzină C-2:2:1 :3. Costul a 1 mie de litri din aceste tipuri de benzină este caracterizat de numerele 120 de ruble, 100 de ruble, 150 de ruble.

Întocmește un plan pentru producerea diferitelor grade de benzină de aviație pe baza condiției obținerii costului maxim al tuturor produselor.

Problema 13

Pentru a participa la competiții, un club sportiv trebuie să prezinte o echipă formată din sportivi de categoriile I și II. Competițiile se desfășoară la Bug, cataramă înaltă și săritură în lungime. La alergare trebuie să participe 5 sportivi, 8 sportivi la săritura în lungime și cel mult 10 la săritura în înălțime.Numărul de puncte garantate unui sportiv din fiecare categorie pentru fiecare eveniment este indicat în tabel:

Distribuiți sportivii pe echipe astfel încât punctele totale ale echipei să fie cele mai mari, dacă se știe că doar 10 sportivi din echipă au prima categorie.

Problema 14

Ferma de blană crește vulpi negre și maro și vulpi arctice. Există 10.000 de cuști în ferma de blănuri. Pot fi fie 2 vulpi, fie 1 vulpe arctică într-o cușcă. Conform planului, în fermă ar trebui să existe cel puțin 3.000 de vulpi și 6.000 de vulpi arctice. Într-o zi, este necesar să dați fiecărei vulpi 4 unități de hrană, iar fiecărei vulpi arctice – 5 unități. O fermă nu poate avea mai mult de 200.000 de unități de furaj zilnic. Din vânzarea unei piei de vulpe, ferma primește un profit de 10,00, iar din vânzarea unei piei de vulpe arctică - 5,00.

Câte vulpi și vulpi arctice ar trebui ținute la fermă pentru a obține cel mai mare profit?

Problema 15

Există două lifturi, care stochează 4.200, respectiv 1.200 de tone de cereale. Cerealele trebuie transportate la trei brutării în cantități de 1000, 2000 și 1600 de tone fiecare. Distanța de la lift până la brutărie este indicată în următorul tabel:

Costul transportului a 1 tonă de produs pe 1 km este de 25 CU. Planificați-vă transportul cerealelor pentru a minimiza costurile de transport.

Problema 16

Din două grade de benzină se formează două amestecuri - A și B. Amestecul A conține 60% benzină clasa I și 40% clasa a II-a; amestec B – 80% clasa I și 20% clasa a II-a. Pretul a 1 kg de amestec A este de 10 euro, iar al amestecului B este de 12 euro.

Întocmește un plan de formare a amestecurilor care să genereze venituri maxime dacă sunt disponibile 50 de tone de benzină de clasa I și 30 de tone de benzină de clasa a doua.

Problema 17

Există două zone edoclimatice, ale căror suprafețe sunt de 0,8 și respectiv 0,6 milioane de hectare. Datele privind randamentele de cereale sunt prezentate în tabel:

Determinați dimensiunea suprafețelor însămânțate de culturi de iarnă și primăvară necesare pentru a obține randamentul maxim al producției în termeni valorici.

Problema 18

Fabrica produce patru tipuri de produse. Din vanzari 1 unitate. Pentru fiecare produs, planta primește un profit de 2, 1, 3, 5, respectiv. Trei tipuri de resurse sunt cheltuite pentru fabricarea produselor: energie, materiale și forță de muncă.

Date despre proces tehnologic sunt prezentate în următorul tabel:

Planificați producția astfel încât profitul din vânzarea lor să fie cel mai mare.

Modelele de programare liniară sunt utilizate: a) în serviciile aeriene comerciale pentru a crea orare de zbor și orare de ieșire a echipajului de zbor;

b) pentru optimizare componente amestecuri la elaborarea rațiilor alimentare;

c) zile de optimizare a parametrilor Procese de producțieîn industrie;

d) băncile comerciale la gestionarea soldurilor financiare;

e) pentru planificarea pe termen lung a capacităţii de producţie a unei întreprinderi;

f) să optimizeze portofoliul de comenzi al companiilor la investiții; g) pentru optimizarea fluxurilor de trafic.

Din punct de vedere al managementului, problemele de programare liniară sunt probleme utilizare optimă resurse. În fiecare caz de planificare a producției, este necesar să se țină seama de faptul că diverse resurse de producție (forță de muncă, materii prime, materiale, unelte de producție) sunt limitate, o rată cunoscută de consum al acestor resurse pt. tipuri diferite sunt posibile produse și numeroase opțiuni pentru distribuirea resurselor de producție. Sarcina este de a găsi alocarea optimă a resurselor de producție. În acest caz, criteriile pot fi, de exemplu, producția maximă, profitul maxim, costurile minime de producție și altele asemenea.

Un exemplu de dezvoltare a unui model de programare liniară pentru producția a două produse

Să presupunem că o fabrică chimică produce două tipuri de bunuri - A și B în cantități egale cu X și respectiv Y. Managerul a analizat informațiile relevante și a primit datele rezumate în tabelul 5.9. Scopul său este să obțină profit maxim (Pr). În acest caz, funcția obiectiv are forma:

Tabelul 5.9. Indicatori de cost ai mărfurilor

FORMULAREA LIMITĂRILOR

Timpul de lucru al echipamentelor în producția de mărfuri este caracterizat de următoarele cifre:

Figura 5.20. Soluție grafică liniară model de optimizare (5.17) - (5.22)

Atractivitatea utilizării variabilelor de rezervă (în cazul nostru, durata timpului de nefuncţionare a echipamentului) poate fi demonstrată în exemplul următor. Să presupunem că sunt produse 9 unități de produs A și sunt produse 14 unități de produs B. Apoi, pe baza ecuației (5.23) obținem că

Sarcina de transport

Costul transportului a 1 tonă de marfă în grivne de la fiecare punct de plecare A1 și A2 la fiecare destinație B1, B2 și VZ este prezentat în acest formular (cifre condiționate):

Este necesar să se întocmească un plan de transport în care costul total să fie cel mai mic.

Să notăm cu X1, X2 și X3 numărul de mărfuri care trebuie transportate de la punctul A1, respectiv, la punctele B1, B2 și B3 și cu Y1, Y2 și Y3 - numărul de mărfuri care trebuie transportate din de la A2 la punctele B1, B2 și B3. Hai sa o scriem asa:

Astfel, formularea matematică a problemei transportului (după criteriul costului transportului) are forma acestui sistem de cinci ecuații de gradul întâi cu șase necunoscute.

SOLUȚIA GEOMETRICĂ A PROBLEMEI DE TRANSPORT

Luați în considerare sistemul (a). Dacă adunăm primele trei ecuații termen cu termen și le scădem pe a patra, obținem a cincea ecuație. Aceasta înseamnă că în sistemul (a) a cincea ecuație este de prisos. Se spune că o astfel de ecuație este rezultatul a patru ecuații și se spune că întregul sistem este dependent liniar. Dacă excludem a cincea ecuație, atunci cele patru ecuații rămase sunt liniar independente. Astfel, obținem patru ecuații liniar independente de gradul I cu șase necunoscute. În aceste ecuații, cele patru necunoscute pot fi exprimate în termenii ultimelor două. În acest caz, se spune că sistemul are patru necunoscute dependente și două necunoscute libere. Să alegem X1 și X2 ca necunoscute gratuite și să obținem:

Printre soluțiile sistemului (a "), trebuie să găsiți una pentru care formă liniară F capătă cea mai mică semnificație. Pentru a rezolva această problemă, să luăm un sistem de coordonate dreptunghiular pe plan și să construim un poligon abсd solutii posibile sistem de inegalități "(Figura 5.21). Să scriem funcția obiectiv sub formă de matrice:

Figura 5.21. Rezolvarea grafică a problemei transportului

În Figura 5.21, funcția obiectiv este reprezentată prin linii întrerupte F. Valoarea funcției scade odată cu creșterea valoare absolută termen liber în ecuația funcției obiective. Deplasând dreapta funcției obiectiv la dreapta paralelă cu ea însăși și îndepărtând-o de origine, vedem că aceasta are cea mai mică valoare în punctul de intersecție a dreptelor (I) și (III). Aceasta corespunde soluției optime: X1 = 200, X2 = 200 (punctul C). În acest caz, F = 12000. Din ecuațiile (a ") aflăm că X3 = 0, Y1 = 0, Y2 = 400, K3 = 200. Astfel, planul optim pentru transportul mărfurilor este o astfel de livrare de la punctul A1 de 200 de tone. la B1 și B2 și de la punctul A2 400 de tone la B2 și 200 de tone la B3. Costul de transport este cel mai mic (12.000 UAH).

Dezavantajul metodei grafice (manuale) de rezolvare a unui model de programare liniară este că este potrivită pentru probleme cu doar două sau cel mult trei variabile. Pentru Mai mult variabilele de care aveți nevoie pentru a utiliza așa-numita metodă simplex.

Modelele discutate mai sus pot fi clasificate ca modele de programare liniară statică, deoarece în ele intervalul de timp era fix. Dacă este nevoie să găsiți o soluție pentru un interval de timp diferit, atunci trebuie să reintroduceți datele în model și să produceți noua optimizare. Cu alte cuvinte, în abordarea discutată mai sus, s-a presupus că toate intervalele de timp sunt independente și pentru fiecare interval de timp trebuie rezolvată propria sa problemă de optimizare.
ÎN modele dinamice Comportamentul sistemului este luat în considerare pe mai multe intervale de timp, iar căutarea unei soluții se efectuează o singură dată, optimizând comportamentul modelului pe toate intervalele de timp deodată.
Modelele dinamice sunt mai realiste și descriu mai adecvat multe situații de producție. Dependența luării deciziilor de comportamentul sistemului în timp face ca modelele dinamice să fie o metodă extrem de utilă de analiză economică, dar se dovedesc a fi mult mai complexe decât modelele statice în formularea lor și, de regulă, conțin număr mare variabilele necesită o anumită abilitate la întocmirea unui model tabelar.
Ca exemplu, luați în considerare un model practic semnificativ de gestionare a stocurilor (un alt nume pentru acest model este modele de gestionare a stocurilor în mai multe faze). De dragul generalității rezultatelor, nu vom atribui parametri valori numerice. După construirea modelului, va fi posibil să se specifice valorile explicite ale parametrilor și să se obțină o soluție numerică.

Exemplul 3.10
Luați în considerare o companie chimică care produce poliuretan. Producătorul are comenzi pentru furnizarea de poliuretan în cantitate de d i tone pe lună pentru următoarele patru luni (i=1,2,…,4). Fie costul producerii unei tone de poliuretan să fie C i mie de ruble, iar volumul maxim de producție de poliuretan pe lună este limitat și egal cu Ki tone pe lună. O companie de producție are posibilitatea de a stoca produse într-un depozit, iar costul depozitării unei tone de produse pe lună este de n i mie de ruble. In perioada initiala, stocul de poliuretan din depozit era de L 0 tone. Managerul companiei trebuie să întocmească un plan lunar de producție de poliuretan care să asigure onorarea comenzilor la costul minim de producție și depozitare a produsului.
Soluţie
Rețineți că, dacă nu ar fi posibilă stocarea produselor într-un depozit, atunci sarcina ar fi împărțită în patru sarcini statice independente și ar pierde orice semnificație pentru noi.
Să creăm o ecuație a bilanțului material care ne permite să calculăm cantitatea de produse stocate în depozit în timpul lunii a I-a. Fie x i cantitatea de poliuretan produsă în a-a oară perioadă. Apoi, în prima lună, stocul din depozit va fi egal cu L 1 =L 0 +x 1 -d 1. Inventarul lunii a doua

Continuând acest proces, este ușor să obțineți o formulă generală de inventar pentru orice interval de timp:

. (3.24)
După ce am derivat ecuația (3.24), care descrie comportamentul inventarului, este ușor să scriem modelul matematic al problemei:

(3.25)
Problema enunțată (3.25) este o problemă tipică de programare liniară și poate fi rezolvată destul de ușor folosind programul Găsirea unei soluții. Utilizarea valorilor numerice ale costurilor unitare de producție

și volumul necesar de provizii și capacitatea de producție pe lună
Se impune intocmirea unui plan optim de productie de poliuretan daca la 1 ianuarie stocul de poliuretan din depozit era de 15 tone.

Model tabelar sarcini de gestionare a stocurilor
Modelul tabelar al problemei după găsirea soluției optime este prezentat în Fig. 21.

Orez. 21. Modelul tabelar al problemei programare dinamică

Ar trebui spuse câteva cuvinte despre raportul de stabilitate pentru acest model, prezentat în Fig. 22.

Orez. 22. Raport de stabilitate pentru modelul dinamic

Dacă se folosește o simplă constrângere asupra valorii variabilelor optimizate (x i ≤K i în cazul nostru), atunci în raportul de sustenabilitate prețurile umbră pentru aceste restricții sunt plasate în coloana costului normalizat și informații despre intervalul acceptabil de umbră. prețurile pentru aceste restricții nu sunt afișate. Astfel, dacă creșteți capacitatea de producție cu o tonă în ianuarie, costurile totale vor scădea cu 1,7 mii de ruble.
Necesită explicații suplimentare și coloană Raportul țintă raport de sustenabilitate. Dat aici valori Excel calculează singur. Semnificația coeficientului țintă pentru o variabilă este că arată cât de mult va crește valoarea funcției țintă atunci când valoarea optimă a variabilei crește cu unu.
Acest lucru este ușor de verificat în practică. Valoarea optimă pentru producția de poliuretan în ianuarie este de 60 de tone, iar costurile totale sunt de 4.776,45 mii de ruble. Dacă înlocuim numărul 61 ca valoare optimă pentru ianuarie și recalculăm costurile totale, vom obține o nouă valoare - 4.805,50. Diferența dintre aceste cifre este exact egală cu 29,05 – coeficientul țintă pentru variabila volum producție în ianuarie.
Alte formulări ale problemelor de programare dinamică sunt, de asemenea, cunoscute pe scară largă. Unele dintre ele (model de înlocuire a echipamentelor și model de investiție) vor fi discutate în cadrul orelor practice.