Introducere
Etapa modernă a dezvoltării umane este diferită prin aceea că secolul energiei este înlocuit de epoca informaticii. Există o introducere intensivă a noilor tehnologii în toate sferele activității umane. Există o adevărată problemă de tranziție la societatea informațională, pentru care dezvoltarea educației ar trebui să devină o prioritate. Structura cunoașterii în societate se schimbă și ea. Cunoștințele fundamentale care contribuie la dezvoltarea creativă a individului devin din ce în ce mai importante pentru viața practică. De asemenea, este importantă caracterul constructiv al cunoștințelor dobândite, capacitatea de a le structura în conformitate cu scopul. Pe baza cunoștințelor se formează noi resurse informaționale ale societății. Formarea și dobândirea de noi cunoștințe ar trebui să se bazeze pe o metodologie strictă a unei abordări sistematice, în cadrul căreia un loc separat este ocupat de o abordare model. Posibilitățile abordării modelării sunt extrem de diverse atât în ceea ce privește modelele formale utilizate, cât și în modalitățile de implementare a metodelor de modelare. Modelarea fizică face posibilă obținerea de rezultate fiabile pentru sisteme destul de simple.
În prezent, este imposibil de a numi o zonă a activității umane în care, într-o măsură sau alta, metodele de modelare nu ar fi utilizate. Acest lucru este valabil mai ales pentru managementul diverselor sisteme, unde principalele sunt procesele decizionale bazate pe informațiile primite.
1. Enunțarea problemei
funcție obiectiv minimă
Rezolvați problema găsirii minimului funcției obiectiv pentru sistemul de constrângeri specificat de poligonul de decizie în conformitate cu opțiunea nr. 16 a sarcinii. Poligonul de decizie este prezentat în Figura 1:
Figura 1 - Poligonul soluțiilor problemei
Sistemul de constrângeri și funcția obiectivă a problemei sunt prezentate mai jos:
Este necesar să se rezolve problema folosind următoarele metode:
Metoda grafica de rezolvare a problemelor LP;
Metoda algebrică de rezolvare a problemelor LP;
Metoda simplex pentru rezolvarea problemelor LP;
Metodă de găsire a unei soluții fezabile la problemele LP;
Rezolvarea problemei dual LP;
Metoda „ramurilor și limitelor” pentru rezolvarea problemelor LP întregi;
metoda lui Gomory pentru rezolvarea problemelor LP cu numere întregi;
Metoda Balash pentru rezolvarea problemelor booleene LP.
Comparați rezultatele soluției prin diferite metode pentru a trage concluziile adecvate asupra lucrării.
2. Rezolvarea grafică a problemei de programare liniară
Metoda grafică de rezolvare a problemelor de programare liniară este utilizată în cazurile în care numărul de necunoscute nu depășește trei. Este convenabil pentru un studiu calitativ al proprietăților soluțiilor și este utilizat împreună cu alte metode (algebrică, ramificată și legată etc.). Ideea metodei se bazează pe soluția grafică a unui sistem de inegalități liniare.
Orez. 2 Rezolvarea grafică a problemei LP
Punct scăzut
Ecuația unei drepte care trece prin două puncte A1 și A2:
AB: (0;1); (3;3)
Soare: (3;3); (4;1)
CD: (4;1); (3;0)
EA: (1;0); (0;1)
CF: (0;1); (5;2)
cu restrictii:
Rezolvarea unei probleme de programare liniară prin metoda simplex algebrică
Aplicarea metodei algebrice de rezolvare a problemei necesită o generalizare a reprezentării problemei LP. Sistemul original de constrângeri dat sub formă de inegalități este convertit la notația standard atunci când constrângerile sunt date sub formă de egalități. Convertirea unui sistem de constrângeri într-o formă standard include următorii pași:
Transformați inegalitățile în așa fel încât variabilele și membrii liberi să fie în stânga și 0 în dreapta, adică. ca partea stângă să fie mai mare sau egală cu zero;
Introduceți variabile suplimentare, al căror număr este egal cu numărul de inegalități din sistemul de restricții;
Introducerea unor restricții suplimentare privind non-negativitatea variabilelor adăugate, înlocuiți semnele de inegalitate cu semne egale stricte.
La rezolvarea problemei LP prin metoda algebrică se adaugă o condiție: funcția obiectiv ar trebui să tindă la minim. Dacă această condiție nu este îndeplinită, este necesară transformarea adecvată a funcției obiectiv (înmulțirea cu -1) și rezolvarea problemei de minimizare. După ce se găsește soluția, înlocuiți valorile variabilelor din funcția originală și calculați valoarea acesteia.
Rezolvarea problemei folosind metoda algebrică este considerată optimă atunci când valorile tuturor variabilelor de bază sunt nenegative, iar coeficienții pentru variabilele libere din ecuația funcției obiective sunt, de asemenea, nenegativi. Dacă aceste condiţii nu sunt îndeplinite, este necesară transformarea sistemului de inegalităţi, exprimând unele variabile în termenii altora (schimbarea variabilelor libere şi de bază) pentru a realiza restricţiile de mai sus. Se presupune că valoarea tuturor variabilelor libere este zero.
Metoda algebrică de rezolvare a problemelor de programare liniară este una dintre cele mai eficiente metode de rezolvare manuală a problemelor de dimensiuni mici. nu necesită un număr mare de calcule aritmetice. Implementarea automată a acestei metode este mai complicată decât, de exemplu, pentru metoda simplex, deoarece algoritmul de rezolvare prin metoda algebrică este într-o oarecare măsură euristic iar eficacitatea soluției depinde în mare măsură de experiența personală.
variabile libere
Lane Sf - adăuga. trusa
Condițiile de non-negativitate sunt îndeplinite, prin urmare, se găsește soluția optimă.
3. Rezolvarea unei probleme de programare liniară folosind un tabel simplex
Soluție: Să aducem problema într-o formă standard pentru rezolvare folosind un tabel simplex.
Reducem toate ecuațiile sistemului la forma:
Construim un tabel simplex:
În colțul de sus al fiecărei celule a tabelului introducem coeficienții din sistemul de ecuații;
Selectăm elementul pozitiv maxim în rândul F, cu excepția faptului că aceasta va fi coloana generală;
Pentru a găsi elementul general, construim o relație pentru toate cele pozitive. 3/3; 9/1;- raport minim in linia x3. Prin urmare - șir general și =3 - element general.
Găsim =1/=1/3. Aducem în colțul inferior al celulei, unde se află elementul general;
În toate colțurile inferioare necompletate ale liniei generale, introducem produsul valorii din colțul superior al celulei prin;
Selectați colțurile superioare ale liniei generale;
În toate colțurile inferioare ale coloanei generale introducem produsul valorii din colțul de sus prin - și selectăm valorile rezultate;
Celulele rămase ale tabelului sunt completate ca produse ale elementelor selectate corespunzătoare;
Apoi construim un nou tabel în care denumirile celulelor elementelor coloanei generale și ale rândului sunt inversate (x2 și x3);
În colțul de sus al fostului rând și al coloanei generale, sunt scrise valorile care au fost anterior în colțul de jos;
Suma valorilor colțurilor superioare și inferioare ale acestor celule din tabelul anterior este scrisă în colțul superior al celulelor rămase
4. Rezolvarea problemei de programare liniară prin găsirea unei soluții fezabile
Să fie dat un sistem de ecuații algebrice liniare:
Putem presupune că totul, altfel înmulțim ecuația corespunzătoare cu -1.
Introducem variabile auxiliare:
Introducem și o funcție auxiliară
Vom minimiza sistemul sub constrângeri (2) și condiții.
REGULĂ PENTRU GĂSIREA O SOLUȚIE FEZIZĂ: Pentru a găsi o soluție fezabilă pentru sistemul (1), minimizăm forma (3) sub constrângerile (2), ca necunoscute libere luăm xj drept bază.
Când rezolvați o problemă prin metoda simplex, pot apărea două cazuri:
min f=0, atunci tot i trebuie să fie egal cu zero. Și valorile rezultate xj vor fi o soluție fezabilă pentru sistemul (1).
min f>0, adică sistemul original nu are o soluție fezabilă.
Sistem sursă:
Se folosește condiția problemei subiectului anterior.
Să adăugăm variabile suplimentare:
Se găsește o soluție admisibilă a problemei inițiale: x1 = 3, x2 = 3, F = -12. Pe baza soluției fezabile obținute, găsim soluția optimă a problemei inițiale folosind metoda simplex. Pentru a face acest lucru, vom construi un nou tabel simplex din tabelul obținut mai sus prin ștergerea rândului și a rândului cu funcția țintă a sarcinii auxiliare:
Analizând tabelul simplex construit, vedem că soluția optimă pentru problema inițială a fost deja găsită (elementele din rândul corespunzătoare funcției obiectiv sunt negative). Astfel, soluția fezabilă găsită la rezolvarea problemei auxiliare coincide cu soluția optimă a problemei inițiale:
6. Problema duală a programării liniare
Sistemul inițial de constrângeri și funcția obiectivă a problemei sunt prezentate în figura de mai jos.
cu restrictii:
Soluție: Aducem sistemul de restricții la forma standard:
Sarcina dublă cu aceasta va arăta astfel:
Problema duală va fi rezolvată prin metoda simplex.
Să transformăm funcția obiectiv astfel încât problema de minimizare să fie rezolvată și să notăm sistemul de constrângeri în forma standard pentru rezolvarea prin metoda simplex.
y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)
y7 = 5 - (-3y1 - y2 + y3 + y4)
Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min
Să construim tabloul simplex inițial pentru rezolvarea problemei LP duale.
Al doilea pas al metodei simplex
Deci, la a treia etapă a metodei simplex s-a găsit soluția optimă a problemei de minimizare cu următoarele rezultate: y2 = -7 /8, y1 = -11/8, Ф = 12. Pentru a afla valoarea lui funcția obiectivă a problemei duale, substituim valorile găsite ale variabilelor de bază și libere în funcția de maximizare:
Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12
Deoarece valoarea funcției obiective a problemelor directe și duale este aceeași, se găsește soluția problemei directe și este egală cu 12.
Fmin \u003d Fmax \u003d -12
7. Rezolvarea problemei programării liniare întregi folosind metoda „ramurilor și limitelor”.
Să transformăm problema inițială în așa fel încât condiția întregului să nu fie satisfăcută atunci când rezolvăm prin metode convenționale.
Poligonul inițial de soluții la o problemă de programare cu numere întregi.
Să construim un nou sistem de constrângeri pentru poligonul soluție transformat.
Notăm sistemul de constrângeri sub formă de egalități, pentru rezolvare prin metoda algebrică.
Ca urmare a soluției s-a găsit planul optim de sarcini: x1 = 9/4, x2 = 5/2, F = -41/4. Această soluție nu îndeplinește condiția de integralitate stabilită în problemă. Împărțim poligonul soluției inițiale în două regiuni, excluzând regiunea 3 din acesta Schimbat poligonul soluțiilor problemei Să compunem noi sisteme de restricții pentru regiunile formate ale poligonului soluție. Zona din stânga este un patrulater (trapez). Sistemul de constrângeri pentru regiunea din stânga a poligonului soluție este prezentat mai jos. Sistem de restricție pentru zona stângă Regiunea dreaptă reprezintă punctul C. Sistemul de constrângeri pentru zona de decizie corectă este prezentat mai jos. Noile sisteme de constrângeri sunt două probleme subsidiare care trebuie rezolvate independent una de cealaltă. Să rezolvăm problema programării întregi pentru regiunea din stânga a poligonului soluție. Ca rezultat al soluției, a fost găsit planul optim de sarcini: x1 = 3, x2 = 3, F = -12. Acest plan satisface condiția variabilelor întregi din problemă și poate fi luat ca plan de referință optim pentru problema originală de programare liniară întregă. Nu are sens să se realizeze soluția pentru regiunea de soluție potrivită. Figura de mai jos arată progresul rezolvării unei probleme de programare liniară cu numere întregi sub forma unui arbore. Cursul de rezolvare a unei probleme de programare liniară întregă prin metoda Gomory. În multe aplicații practice, problema programării întregi este de mare interes, în care sunt date un sistem de inegalități liniare și o formă liniară. Este necesară găsirea unei soluții întregi a sistemului (1), care să minimizeze funcția obiectiv F, în plus, toți coeficienții sunt numere întregi. Una dintre metodele de rezolvare a problemei de programare cu numere întregi a fost propusă de Gomori. Ideea metodei este de a folosi metode de programare liniară continuă, în special metoda simplex. 1) Folosind metoda simplex se determină soluția problemei (1), (2), pentru care se elimină cerința ca soluția să fie întreagă; dacă soluția se dovedește a fi întreagă, atunci se va găsi și soluția dorită pentru problema întregului; 2) În caz contrar, dacă o coordonată nu este un întreg, se verifică soluția obținută a problemei pentru posibilitatea existenței unei soluții întregi (prezența punctelor întregi într-un poliedru admis): dacă în orice linie cu un membru liber fracționar, toți ceilalți coeficienți se dovedesc a fi numere întregi, atunci nu există numere întregi, puncte într-un poliedru admisibil, iar problema programării întregilor nu are soluție; În caz contrar, se introduce o constrângere liniară suplimentară, care decupează din poliedrul admisibil o parte care nu este promițătoare pentru găsirea unei soluții la o problemă de programare cu numere întregi; 3) Pentru a construi o constrângere liniară suplimentară, selectați al-lea rând cu un membru liber fracțional și notați constrângerea suplimentară unde și sunt, respectiv, părțile fracționale ale coeficienților și libere membru. Să introducem o variabilă auxiliară în constrângerea (3): Să determinăm coeficienții și incluși în constrângerea (4): unde și sunt cele mai apropiate numere întregi inferioare pentru și, respectiv. Gomory a demonstrat că un număr finit de astfel de pași duce la o problemă de programare liniară a cărei soluție este întreagă și, prin urmare, cea dorită. Soluție: Reducem sistemul de constrângeri liniare și funcția scop la forma canonică: Să determinăm soluția optimă a sistemului de constrângeri liniare, eliminând temporar condiția întregului. Folosim metoda simplex pentru aceasta. Tabelele de mai jos prezintă succesiv soluția inițială a problemei, iar transformările tabelului inițial sunt date pentru a obține soluția optimă a problemei: Rezolvarea problemelor booleene LP prin metoda Balash. Compuneți independent o variantă pentru problema programării liniare întregi cu variabile booleene, ținând cont de următoarele reguli: problema folosește cel puțin 5 variabile, cel puțin 4 restricții, coeficienții de restricții și funcția obiectiv sunt alese arbitrar, dar în astfel de un mod în care sistemul de restricții este compatibil. Sarcina este de a rezolva ZCLP cu variabile booleene folosind algoritmul Balash și de a determina reducerea complexității de calcul în raport cu rezolvarea problemei prin căutare exhaustivă. Executarea restricțiilor Valoarea F Constrângere de filtrare: Calcul Reducere Determinare Rezolvarea problemei prin metoda de căutare exhaustivă este 6*25=192 expresii calculate. Rezolvarea problemei prin metoda Balash este 3*6+(25-3)=47 expresii calculate. Reducerea totală a complexității calculelor în raport cu rezolvarea problemei prin metoda de căutare exhaustivă este. Concluzie Procesul de proiectare a sistemelor informaționale care implementează noi tehnologii informaționale este în mod constant îmbunătățit. Sistemele din ce în ce mai complexe devin în centrul atenției inginerilor de sisteme, ceea ce face dificilă utilizarea modelelor fizice și crește importanța modelelor matematice și a simulării pe computer a sistemelor. Modelarea mașinilor a devenit un instrument eficient pentru cercetarea și proiectarea sistemelor complexe. Relevanța modelelor matematice este în continuă creștere datorită flexibilității lor, adecvării la procesele reale, costurilor reduse de implementare pe baza computerelor moderne. Din ce în ce mai multe oportunități sunt oferite utilizatorului, adică unui specialist în modelarea sistemelor prin intermediul tehnologiei informatice. Utilizarea modelării este eficientă în special în etapele incipiente ale proiectării sistemelor automatizate, când costul deciziilor eronate este cel mai semnificativ. Instrumentele de calcul moderne au făcut posibilă creșterea semnificativă a complexității modelelor utilizate în studiul sistemelor, a devenit posibilă construirea de modele combinate, analitice și de simulare care iau în considerare întreaga varietate de factori care au loc în sistemele reale, adică utilizarea unor modele care sunt mai adecvate fenomenelor studiate. Literatură: 1. Liascenko I.N. Programare liniară și neliniară / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K .: „Școala superioară”, 1975, 372 p. 2. Orientări pentru implementarea proiectului de curs la disciplina „Matematică aplicată” pentru studenții specialității „Sisteme și rețele de calculatoare” forme de învățământ cu frecvență redusă și cu frecvență redusă / Alcătuit de: I.A. Balakireva, A.V. Skatkov - Sevastopol: Editura SevNTU , 2003. - 15 p. 3. Orientări pentru studiul disciplinei „Matematică aplicată”, secțiunea „Metode de căutare globală și minimizare unidimensională” / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: Editura SevGTU, 2000. - 31s. 4. Orientări pentru studierea disciplinei „Matematică aplicată” pentru studenții specialității „Sisteme și rețele de calcul” Secțiunea „Rezolvarea problemelor de programare liniară cu numere întregi” ale formelor de învățământ cu frecvență și corespondență / Alcătuit de: I.A. Balakireva, A.V. Skatkov - Sevastopol : Editura SevNTU, 2000. - 13 p. 5. Akulich I.L. Programare matematică în exemple și sarcini: 6. Proc. indemnizatie pentru economie studenteasca. specialist. universități.-M.: Mai înaltă. scoala, 1986.- 319s., ill. 7. Andronov S.A. Metode optime de proiectare: Textul cursului / SPbGUAP. SPb., 2001. 169 p.: ill. Algoritm pentru rezolvarea problemelor de programare liniară prin metoda simplex. Construirea unui model matematic al unei probleme de programare liniară. Rezolvarea unei probleme de programare liniară în Excel. Găsirea profitului și a planului optim de producție. lucrare de termen, adăugată 21.03.2012 Rezolvarea grafică a problemelor. Întocmirea unui model matematic. Determinarea valorii maxime a funcţiei obiectiv. Rezolvarea printr-o metodă simplex cu o bază artificială a unei probleme de programare liniară canonică. Verificarea optimității soluției. test, adaugat 04.05.2016 Bazele teoretice ale programării liniare. Probleme de programare liniara, metode de rezolvare. Analiza soluției optime. Rezolvarea unei probleme de programare liniară cu un singur indice. Declarația problemei și introducerea datelor. Construirea modelului și etapele soluției. lucrare de termen, adăugată 12/09/2008 Construirea unui model matematic. Selectarea, justificarea și descrierea metodei de rezolvare a problemei directe a programării liniare prin metoda simplex, folosind un tabel simplex. Formularea și rezolvarea unei probleme duale. Analiza modelului pentru sensibilitate. lucrare de termen, adăugată 31.10.2014 Construirea unui model matematic pentru a maximiza profitul întreprinderii, o soluție grafică a problemei. Rezolvarea problemelor folosind suplimentul SOLVER. Analiza modificărilor rezervelor de resurse. Determinarea limitelor de modificare a coeficienților funcției obiectiv. lucrare de termen, adăugată 17.12.2014 Programare matematică. Programare liniară. Probleme de programare liniară. Metodă grafică pentru rezolvarea unei probleme de programare liniară. Formularea economică a problemei programării liniare. Construirea unui model matematic. lucrare de termen, adăugată 13.10.2008 Rezolvarea unei probleme de programare liniară printr-o metodă grafică, verificarea acesteia în MS Excel. Analiza structurii interne a soluției problemei în program. Optimizarea planului de productie. Rezolvarea problemei prin metoda simplex. Sistem de așteptare multicanal. test, adaugat 05.02.2012 Rezolvarea problemei programării liniare prin metoda simplex: stabilirea problemei, construirea unui model economic și matematic. Rezolvarea problemei transportului prin metoda potenţialelor: construirea planului de referinţă iniţial, determinarea valorii optime a acestuia. test, adaugat 04.11.2012 Enunțarea problemei programării neliniare. Determinarea punctelor staţionare şi tipul acestora. Construcția liniilor de nivel, un grafic tridimensional al funcției obiectiv și restricții. Rezolvarea grafică și analitică a problemei. Manual de utilizare și schema de algoritm. lucrare de termen, adăugată 17.12.2012 Analiza soluției unei probleme de programare liniară. Metoda simplex folosind tabele simplex. Modelarea și rezolvarea problemelor LP pe calculator. Interpretarea economică a soluției optime a problemei. Formularea matematică a problemei transportului. Împărțim al treilea rând la elementul cheie egal cu 5, obținem al treilea rând al noului tabel. Coloanele de bază corespund coloanelor simple. Calculul valorilor rămase din tabel: „BP - Plan de bază”: ; "x1": "x5": Valorile rândului index sunt nenegative, prin urmare obținem soluția optimă: , ; Răspuns: profitul maxim din vanzarea produselor manufacturate, egal cu 160/3 unitati, se asigura prin eliberarea numai de produse de al doilea tip in valoare de 80/9 unitati. Este dată problema programării neliniare. Găsiți maximul și minimul funcției obiectiv folosind o metodă analitică grafică. Compuneți funcția Lagrange și arătați că condițiile minime (maximale) suficiente sunt îndeplinite la punctele extreme. pentru că ultima cifră a cifrului este 8, apoi A=2; B=5. pentru că penultima cifră a cifrului este 1, atunci ar trebui să alegeți sarcina numărul 1. Decizie: 1) Să desenăm aria pe care o definește sistemul de inegalități. Această zonă este un triunghi ABC cu coordonatele vârfurilor: A(0; 2); B(4; 6) și C(16/3; 14/3). Nivelurile funcției obiectiv sunt cercuri centrate în punctul (2; 5). Pătratele razelor vor fi valorile funcției obiectiv. Apoi figura arată că valoarea minimă a funcției obiectiv este atinsă în punctul H, valoarea maximă este fie în punctul A, fie în punctul C. Valoarea funcţiei obiectiv la punctul A: ; Valoarea funcţiei obiectiv în punctul C: ; Aceasta înseamnă că valoarea maximă a funcției este atinsă în punctul A(0; 2) și este egală cu 13. Să găsim coordonatele punctului H. Pentru a face acest lucru, luați în considerare sistemul: O dreaptă este tangentă la un cerc dacă ecuația are o soluție unică. O ecuație pătratică are o soluție unică dacă discriminantul este 0. 2) Compuneți funcția Lagrange pentru a găsi soluția minimă: La X 1
=2.5;
X 2
=4.5
primim: Sistemul are o soluție pentru , i.e. sunt îndeplinite suficiente condiții extreme. Compunem funcția Lagrange pentru găsirea soluției maxime: Condiții suficiente pentru un extremum: La X 1
=0;
X 2
=2
primim: Sistemul are și o soluție, adică. sunt îndeplinite suficiente condiții extreme. Răspuns: se atinge minimul funcţiei obiectiv la Două întreprinderi sunt alocate fonduri în sumă d unitati. Când este alocată primei întreprinderi timp de un an X unități de fond pe care le oferă venituri k 1
X unități și atunci când sunt alocate celei de-a doua întreprinderi y unități de fond, oferă venituri k 1
y unitati. Soldul fondurilor la sfârșitul anului pentru prima întreprindere este egal cu nx, iar pentru al doilea Ale mele. Cum să distribuiți toate fondurile în decurs de 4 ani, astfel încât venitul total să fie cel mai mare? Rezolvați problema prin programare dinamică. i=8, k=1. A=2200; k1 =6; k2=1; n=0,2; m=0,5. Decizie: Împărțim întreaga perioadă de 4 ani în 4 etape, fiecare dintre ele egală cu un an. Să numărăm etapele începând din primul an. Fie X k și Y k fondurile alocate, respectiv, întreprinderilor A și B la etapa k. Apoi suma X k + Y k =a k este suma totală a fondurilor utilizate la k - acea etapă și rămase din etapa anterioară k - 1. la prima etapă sunt utilizate toate fondurile alocate și a 1 =2200 unități. venitul care va fi primit în etapa k-a, când sunt alocate unități X k și Y k, va fi 6X k + 1Y k . fie venitul maxim primit la ultimele etape începând de la k - acea etapă este f k (a k) unități. Să scriem ecuația funcțională Bellman care exprimă principiul optimității: oricare ar fi starea inițială și soluția inițială, soluția ulterioară trebuie să fie optimă în raport cu starea obținută ca urmare a stării inițiale: Pentru fiecare etapă, trebuie să alegeți valoarea X k și valoarea Y k=ak- Xk. Având în vedere acest lucru, vom găsi venituri în etapa k-a: Ecuația funcțională Bellman va arăta astfel: Luați în considerare toate etapele, începând cu ultima. (deoarece maximul funcției liniare este atins la capătul segmentului la x 4 = a 4); funcție obiectivă- functia reala sau intreaga a mai multor variabile, supusa optimizarii (minimizarea sau maximizarea) in vederea rezolvarii unei probleme de optimizare. Termenul este folosit în programarea matematică, cercetarea operațională, programarea liniară, teoria deciziei statistice și alte domenii ale matematicii, în primul rând de natură aplicativă, deși scopul optimizării poate fi și soluția unei probleme matematice în sine. Pe lângă funcția obiectiv, în problema de optimizare, variabilele pot fi supuse unor restricții sub forma unui sistem de egalități sau inegalități. În cazul general, argumentele funcției obiectiv pot fi specificate pe mulțimi arbitrare. Problema rezolvării oricărui sistem de ecuații ( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matrix) )\dreapta.) poate fi formulată ca o problemă de minimizare a funcţiei obiectiv S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad(1)) Dacă funcțiile sunt netede, atunci problema de minimizare poate fi rezolvată prin metode de gradient. Pentru orice funcție obiectiv netedă, se pot echivala cu 0 (\displaystyle 0) derivatele parțiale în raport cu toate variabilele. Funcția obiectiv optimă va fi una dintre soluțiile unui astfel de sistem de ecuații. În cazul funcției (1) (\displaystyle (1)) acesta va fi un sistem de ecuații cu cele mai mici pătrate (LSM). Orice soluție a sistemului original este o soluție a sistemului celor mai mici pătrate. Dacă sistemul original este inconsecvent, atunci sistemul LSM, care are întotdeauna o soluție, face posibilă obținerea unei soluții aproximative a sistemului original. Numărul de ecuații ale sistemului LSM coincide cu numărul de necunoscute, ceea ce facilitează uneori rezolvarea sistemelor inițiale comune. Un alt exemplu binecunoscut de funcție obiectiv este o funcție liniară care apare în problemele de programare liniară. Spre deosebire de funcția obiectiv pătratică, optimizarea unei funcții liniare este posibilă numai dacă există restricții sub forma unui sistem de egalități sau inegalități liniare. Un exemplu tipic de funcție obiectiv combinatorie este funcția obiectiv a problemei vânzătorului ambulant. Această funcție este egală cu lungimea ciclului hamiltonian de pe grafic. Este dat pe setul de permutare n − 1 (\displaystyle n-1) a vârfurilor graficului și este determinat de matricea lungimii muchiei graficului. Soluția exactă a unor astfel de probleme se rezumă adesea la enumerarea opțiunilor. Programarea liniară este o ramură a programării matematice care studiază metode de rezolvare a problemelor extreme care se caracterizează printr-o relație liniară între variabile și un criteriu liniar. Astfel de sarcini își găsesc aplicații extinse în diverse sfere ale activității umane. Un studiu sistematic al problemelor de acest tip a început în 1939–1940. în lucrările lui L.V. Kantorovich. Problemele matematice ale programării liniare includ studiul situațiilor specifice de producție și economice, care într-o formă sau alta sunt interpretate ca probleme de utilizare optimă a resurselor limitate. Gama de probleme rezolvate cu ajutorul metodelor de programare liniară este destul de largă, acestea sunt, 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 depozitarea în depozite (gestionarea stocurilor sau); sarcini de transport (analiza locației întreprinderii, circulația mărfurilor). Programarea liniară este secțiunea cea mai dezvoltată și utilizată pe scară largă a programării matematice (în plus, aceasta include: programare întregă, dinamică, neliniară, parametrică). Acest lucru se explică după cum urmează: modelele matematice ale unui număr mare de probleme economice sunt liniare în raport cu variabilele cerute; acest tip de probleme este în prezent cel mai studiat. Pentru el s-au dezvoltat metode speciale cu ajutorul cărora se rezolvă aceste probleme și programele de calculator corespunzătoare; multe probleme de programare liniara, fiind rezolvate, si-au gasit aplicatie larga; unele probleme care nu sunt liniare în formularea originală, după o serie de restricții și ipoteze suplimentare, pot deveni liniare sau pot fi reduse la o astfel de formă încât să poată fi rezolvate prin metode de programare liniară. 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 de non-negativitate a variabilelor. În general, modelul este scris după cum urmează: funcție obiectivă (1.1) conform restricțiilor Problema este de a găsi valoarea optimă a funcției (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 constrângeri directe. Un vector care satisface constrângerile (1.2) și (1.3) se numește o soluție fezabilă (plan) a unei probleme de programare liniară. Planul pentru care funcția (1.1) își atinge valoarea maximă (minimă) se numește optim. Metoda simplex a fost dezvoltată și aplicată pentru prima dată pentru a rezolva probleme în 1947 de către matematicianul american J. Danzig. Problemele de programare liniară bidimensională sunt rezolvate grafic. Pentru cazul N=3, putem considera un spațiu tridimensional și funcția obiectiv își va atinge valoarea optimă la unul dintre vârfurile poliedrului. O soluție admisibilă (un plan admisibil) a unei probleme LP dată în formă standard este o mulțime ordonată de numere (x1, x2, ..., xn) care satisfac constrângerile; este un punct din spațiul n-dimensional. Setul de soluții admisibile formează zona soluțiilor admisibile (SDR) a problemei LP. ODR este un poliedru (poligon) convex. În termeni generali, atunci când în problemă sunt implicate N-necunoscute, putem spune că aria soluțiilor fezabile specificate de sistemul de condiții limită este reprezentată de un poliedru convex în spațiu n-dimensional și valoarea optimă a obiectivului. funcția este realizată la unul sau mai multe vârfuri. O soluție se numește de bază dacă toate variabilele libere sunt egale cu zero. O soluție de referință este o soluție de bază nenegativă. Soluția de suport poate fi nedegenerată și degenerată. O soluție suport se numește nedegenerată dacă numărul coordonatelor sale non-nule este egal cu rangul sistemului, în caz contrar este degenerată. O soluție fezabilă, în care funcția obiectiv atinge valoarea sa extremă, se numește optimă și se notează Este foarte dificil să rezolvi aceste probleme grafic când numărul de variabile este mai mare de 3. Există o modalitate universală de a rezolva probleme de programare liniară, numită metoda simplex. Metoda simplex este o metodă universală de rezolvare a problemelor LP, care este un proces iterativ care începe cu o singură soluție și, în căutarea celei mai bune opțiuni, se deplasează de-a lungul punctelor de colț ale zonei de soluții fezabile până când atinge valoarea optimă. . Poate fi folosit pentru a rezolva orice problemă de programare liniară. Metoda simplex se bazează pe ideea îmbunătățirii succesive a soluției rezultate. Sensul geometric al metodei simplex este de a trece secvenţial de la un vârf al poliedrului de constrângere la cel vecin, în care funcţia obiectiv ia cea mai bună (sau cel puţin nu cea mai proastă) valoare până când se găseşte soluţia optimă - vârful unde valoarea optimă este atinsă funcția scop (dacă problema are un optim finit). Astfel, având un sistem de constrângeri redus la forma canonică (toate constrângerile funcționale sunt sub formă de egalități), se găsește orice soluție de bază a acestui sistem, având grijă doar să o găsească cât mai simplu. Dacă prima soluție de bază găsită s-a dovedit a fi fezabilă, atunci se verifică optimitatea. Dacă nu este optimă, atunci se face o tranziție la o altă soluție de bază, neapărat admisibilă. Metoda simplex garantează că, cu această nouă soluție, funcția obiectiv, dacă nu ajunge la optim, atunci se apropie de el (sau cel puțin nu se îndepărtează de ea). Cu o nouă soluție de bază admisibilă se procedează la fel până când se găsește o soluție optimă. Procesul de aplicare a metodei simplex implică implementarea celor trei elemente principale ale sale: o metodă pentru a determina o soluție de bază fezabilă inițială a problemei; regula de tranziție la cea mai bună (mai precis, nu cea mai rea) soluție; criteriu de verificare a optimităţii soluţiei găsite. Metoda simplex include un număr de pași și poate fi formulată ca un algoritm clar (o instrucțiune clară pentru a efectua operații secvențiale). Acest lucru vă permite să îl programați și să îl implementați cu succes pe un computer. Problemele cu un număr mic de variabile și constrângeri pot fi rezolvate manual prin metoda simplex. Optimizare. Partea 1 Metodele de optimizare vă permit să alegeți cea mai bună opțiune de design dintre toate opțiunile posibile. În ultimii ani, s-a acordat multă atenție acestor metode și, ca urmare, au fost dezvoltați o serie de algoritmi extrem de eficienți care fac posibilă găsirea opțiunii optime de proiectare folosind un computer digital. Acest capitol conturează bazele teoriei optimizării, ia în considerare principiile care stau la baza construcției algoritmilor pentru soluții optime, descrie cei mai cunoscuți algoritmi și analizează avantajele și dezavantajele acestora. Termenul „optimizare” din literatură se referă la un proces sau o secvență de operații care vă permite să obțineți o soluție rafinată. Deși scopul final al optimizării este găsirea celei mai bune soluții sau „optimale”, de obicei trebuie să se mulțumească cu îmbunătățirea soluțiilor cunoscute, mai degrabă decât cu perfecționarea lor. Prin urmare, optimizarea este mai probabil să fie înțeleasă ca căutarea perfecțiunii, care, poate, nu va fi atinsă. Având în vedere un sistem arbitrar descris de m ecuații cu n necunoscute, putem distinge trei tipuri principale de probleme. Dacă m=n , problema se numește algebrică. O astfel de problemă are de obicei o singură soluție. Dacă m>n, atunci problema este redefinită și, de regulă, nu are soluție. În sfârșit, pentru m Înainte de a trece la discuția problemelor de optimizare, introducem o serie de definiții. Parametrii de proiectare
Acest termen denotă parametrii variabili independenți care definesc complet și fără ambiguitate problema de proiectare care se rezolvă. Parametrii de proiectare sunt cantități necunoscute, ale căror valori sunt calculate în timpul procesului de optimizare. Orice mărime de bază sau derivată care servește la descrierea cantitativă a sistemului poate servi drept parametri de proiectare. Deci, pot fi valori necunoscute de lungime, masă, timp, temperatură. Numărul de parametri de proiectare caracterizează gradul de complexitate al acestei probleme de proiectare. De obicei, numărul de parametri de proiectare este notat cu n, iar parametrii de proiectare înșiși cu x cu indicii corespunzători. Astfel, n parametri de proiectare ai acestei probleme vor fi notați cu funcție obiectivă
Aceasta este expresia a cărei valoare inginerul caută să o maximizeze sau să o minimizeze. Funcția obiectiv vă permite să comparați cantitativ două soluții alternative. Din punct de vedere matematic, funcția obiectiv descrie o suprafață (n + 1) - dimensională. Valoarea acestuia este determinată de parametrii de proiectare M=M(x1, x2,...,x n). Exemple de funcție obiectiv, des întâlnite în practica inginerească, sunt costul, greutatea, rezistența, dimensiunile, eficiența. Dacă există un singur parametru de proiectare, atunci funcția obiectiv poate fi reprezentată printr-o curbă pe un plan (Fig. 6.1). Dacă există doi parametri de proiectare, atunci funcția țintă va fi reprezentată printr-o suprafață în spațiul de trei dimensiuni (Fig. 6.2). Cu trei sau mai mulți parametri de proiectare, suprafețele specificate de funcția obiectiv se numesc hipersuprafețe și nu pot fi reprezentate. zheniya mijloace convenționale. Proprietățile topologice ale suprafeței funcției țintă joacă un rol important în procesul de optimizare, deoarece alegerea celui mai eficient algoritm depinde de ele. Funcția obiectivă în unele cazuri poate lua cele mai neașteptate forme. De exemplu, nu este întotdeauna posibil să o exprimați în Fig. 1. Funcția obiectiv unidimensională. Fig.6.2.Funcția obiectiv bidimensională. formă matematică închisă, în alte cazuri se poate să fie o funcție lină pe bucăți. O funcție obiectivă poate necesita uneori un tabel cu date tehnice (de exemplu, un tabel cu starea aburului) sau poate fi necesar să se efectueze un experiment. În unele cazuri, parametrii de proiectare iau doar valori întregi. Un exemplu ar fi numărul de dinți dintr-o roată dințată sau numărul de șuruburi dintr-o flanșă. Uneori, parametrii de proiectare au doar două valori - da sau nu. Parametrii calitativi, precum satisfacția clientului, fiabilitatea, estetica, sunt greu de luat în considerare în procesul de optimizare, deoarece sunt aproape imposibil de cuantificat. Oricum, sub orice formă este prezentată funcția obiectiv, aceasta trebuie să fie o funcție cu o singură valoare a parametrilor de proiectare. Într-un număr de probleme de optimizare, este necesară introducerea a mai mult de o funcție obiectivă. Uneori, unul dintre ele poate fi incompatibil cu celălalt. Un exemplu este proiectarea aeronavelor, când este necesar să ofere rezistență maximă, greutate minimă și cost minim în același timp. În astfel de cazuri, proiectantul trebuie să introducă un sistem de priorități și să atribuie un multiplicator adimensional fiecărei funcție obiectiv. Ca rezultat, apare o „funcție de compromis”, care permite utilizarea unei singure funcții obiectiv compozit în procesul de optimizare. Găsirea minimului și maximului
Unii algoritmi de optimizare sunt adaptați pentru găsirea maximului, alții pentru găsirea minimului. Totuși, indiferent de tipul problemei extremum care se rezolvă, se poate folosi același algoritm, deoarece problema de minimizare poate fi ușor transformată într-o problemă de maxim prin schimbarea semnului funcției obiectiv la opus. Această tehnică este ilustrată în Figura 6.3. Amenajare spatiu
Acesta este numele zonei definite de toți n parametrii de proiectare. Spațiul de proiectare nu este atât de mare pe cât ar părea, deoarece este de obicei limitat la un număr de condiţiile asociate cu esenţa fizică a problemei. Constrângerile pot fi atât de puternice încât sarcina nu va avea niciuna Fig.6.3.Schimbarea semnului funcției obiectiv la invers Sarcina maximă devine sarcina minimă. solutie satisfacatoare. Constrângerile sunt împărțite în două grupe: constrângeri - egalități și constrângeri - inegalități. Constrângeri – egalitate
Constrângeri – egalități – reprezintă dependența dintre parametrii de proiectare de care trebuie să se țină seama la găsirea unei soluții. Ele reflectă legile naturii, economiei, drepturile, gusturile predominante și disponibilitatea materialelor necesare. Numărul de restricții - egalitățile pot fi oricare. Arata ca C 1 (x 1 , x 2 ,...,x n)=0, C2 (x 1 , x 2 ,...,x n)=0, .................. Cj (x 1 , x 2 ,...,x n)=0. Dacă oricare dintre aceste relații poate fi rezolvată în raport cu unul dintre parametrii de proiectare, atunci acest lucru vă permite să excludeți acest parametru din procesul de optimizare. Acest lucru reduce numărul de dimensiuni ale spațiului de proiectare și simplifică rezolvarea problemei. Constrângeri – inegalități
Acesta este un tip special de constrângere exprimat prin inegalități. În cazul general, pot exista orice număr de ele și toate au forma z 1 r 1 (x 1 , x 2 ,...,x n) Z 1 z 2 r 2 (x 1 , x 2 ,...,x n) Z 2 ....................... z k r k (x 1 , x 2 ,...,x n) Z k De remarcat că de foarte multe ori, din cauza limitărilor, valoarea optimă a funcției obiectiv nu este atinsă acolo unde suprafața acesteia are un gradient zero. Adesea, cea mai bună soluție se află la una dintre granițele domeniului designului. Optim local
Acesta este numele punctului din spațiul de proiectare la care funcția obiectiv are cea mai mare valoare în comparație cu valorile sale din toate celelalte puncte din imediata sa vecinătate. Fig.6.4.O funcție obiectiv arbitrară poate avea mai multe optime locale. Pe fig. Figura 6.4 prezintă o funcție obiectiv unidimensională care are două optime locale. Adesea, spațiul de proiectare conține multe optime locale și trebuie avut grijă să nu confundați primul cu soluția optimă a problemei. Global Optimum
Optimul global este soluția optimă pentru întreg spațiul de proiectare. Este mai bun decât toate celelalte soluții corespunzătoare optimelor locale și asta caută designerul. Este posibil cazul mai multor optime globale egale situate în diferite părți ale spațiului de proiectare. Modul în care se pune problema de optimizare este cel mai bine ilustrat printr-un exemplu. Exemplul 6.1
Să fie necesară proiectarea unui container dreptunghiular cu un volum de 1 m , destinat transportului de fibre neambalate. Este de dorit ca pentru fabricarea unor astfel de containere să fie cheltuit cât mai puțin material (presupunând o grosime constantă a peretelui, aceasta înseamnă că suprafața ar trebui să fie minimă), deoarece va fi mai ieftin. Pentru a facilita preluarea containerului cu un stivuitor, lățimea acestuia trebuie să fie de cel puțin 1,5 m. Să formulăm această problemă într-o formă convenabilă pentru aplicarea algoritmului de optimizare. Parametri de proiectare: x 1 , x 2 , x 3 . Funcția obiectiv (care trebuie redusă la minimum) este aria suprafeței laterale a containerului: A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2. Constrângere - egalitate: Volumul \u003d x 1 x 2 x 3 \u003d 1m3. Constrângere - inegalitate: Programare liniară (LP) este una dintre secțiunile de programare matematică - o disciplină care studiază probleme extreme (de optimizare) și dezvoltă metode de rezolvare a acestora. Problema de optimizare este o problemă de matematică care constă în găsirea valorii optime (adică maximă sau minimă) a funcției obiectiv, iar valorile variabilelor trebuie să aparțină unei anumite zone de valori admisibile (ODV). În general, formularea unei probleme extreme de programare matematică constă în determinarea celei mai mari sau mai mici valori a funcției, numită funcție obiectivă, în condițiile (restricții) , unde și sunt date funcții și sunt date constante. În același timp, restricțiile sub formă de egalități și inegalități determină mulțimea (regiunea) soluțiilor fezabile (ODS) și sunt numite parametrii de proiectare. În funcție de tipul de funcții și probleme de programare matematică se împart într-un număr de clase (liniară, neliniară, convexă, întreg, stocastică, programare dinamică etc.). LA vedere generala Problema LP are următoarea formă: , unde , , sunt date constante. Funcția (5.1) se numește funcție obiectiv; sisteme (5.2), (5.3) - printr-un sistem de constrângeri; condiția (5.4) este condiția de non-negativitate a parametrilor de proiectare. Setul de parametri de proiectare care satisfac constrângerile (5.2), (5.3) și (5.4) se numește solutie acceptabila sau plan. Soluția optimă sau plan optim Problema LP se numește soluție fezabilă, în care funcția obiectiv (5.1) ia valoarea optimă (maximum sau minim). Sarcină standard LP se numește problema găsirii valorii maxime (minime) a funcției obiectiv (5.1) în condiția (5.2) și (5.4), unde , , i.e. acestea. restricțiile numai sub formă de inegalități (5.2) și toți parametrii de proiectare satisfac condiția de non-negativitate și nu există condiții sub formă de egalități: Sarcina canonică (principală). LP se numește problema găsirii valorii maxime (minime) a funcției obiectiv (5.1) în condiția (5.3) și (5.4), unde , , i.e. acestea. restricțiile numai sub formă de egalități (5.3) și toți parametrii de proiectare satisfac condiția de non-negativitate și nu există condiții sub formă de inegalități: Problema canonică LP poate fi scrisă și sub formă matriceală și vectorială. Forma matriceală a problemei canonice LP are următoarea formă: Forma vectorială a problemei LP canonice. Dacă există un singur factor limitator (de exemplu, o mașină rară), soluția poate fi găsită folosind formule simple (vezi linkul de la începutul articolului). Dacă există mai mulți factori limitatori, se utilizează metoda de programare liniară. Programare liniară este numele dat unei combinații de instrumente utilizate în știința managementului. Această metodă rezolvă problema alocării resurselor limitate între activitățile concurente pentru a maximiza sau a minimiza o anumită valoare numerică, cum ar fi câștigurile sau costurile marginale. În afaceri, poate fi utilizat în domenii precum planificarea producției pentru a maximiza profiturile, selectarea componentelor pentru a minimiza costurile, selectarea portofoliului de investiții pentru a maximiza profitabilitatea, optimizarea transportului de mărfuri pentru a reduce distanțe, alocarea personalului pentru a maximiza eficiența muncii și programarea lucrărilor în pentru a economisi timp. Descărcați nota în , desene în format Programarea liniară presupune construirea unui model matematic al problemei luate în considerare. După aceea, soluția poate fi găsită grafic (discutat mai jos), folosind Excel (va fi luat în considerare separat) sau programe de calculator specializate. Poate că construirea unui model matematic este cea mai dificilă parte a programării liniare, necesitând traducerea problemei luate în considerare într-un sistem de variabile, ecuații și inegalități - un proces care depinde în cele din urmă de abilitățile, experiența, abilitățile și intuiția compilator al modelului. Luați în considerare un exemplu de construire a unui model matematic de programare liniară Nikolai Kuznetsov conduce o mică fabrică mecanică. Luna viitoare, intenționează să producă două produse (A și B), pentru care profitul marginal specific este estimat la 2.500 și, respectiv, 3.500 de ruble. Fabricarea ambelor produse necesită costul de prelucrare, materii prime și forță de muncă (Fig. 1). Pentru fabricarea fiecărei unități de produs A se alocă 3 ore de prelucrare la mașină, 16 unități de materii prime și 6 unități de muncă. Cerințele corespunzătoare pentru unitatea B sunt 10, 4 și 6. Nikolai prezice că luna viitoare va putea furniza 330 de ore de prelucrare, 400 de unități de materii prime și 240 de unități de muncă. Tehnologia procesului de producție este de așa natură încât cel puțin 12 unități de produs B trebuie produse într-o anumită lună. Orez. 1. Utilizarea și asigurarea resurselor Nikolai vrea să construiască un model pentru a determina numărul de unități de produse A și B pe care ar trebui să le producă în luna următoare pentru a maximiza profitul marginal. Modelul liniar poate fi construit în patru pași. Etapa 1. Definirea variabilelor Există o variabilă țintă (să o notăm Z) care trebuie optimizată, adică maximizată sau minimizată (de exemplu, profit, venituri sau cheltuieli). Nikolay caută să maximizeze profitul marginal, prin urmare, variabila țintă este: Z = profitul marginal total (în ruble) primit în luna următoare ca urmare a producției de produse A și B. Există o serie de variabile necunoscute necunoscute (să le notăm x 1, x 2, x 3 etc.), ale căror valori trebuie determinate pentru a obține valoarea optimă a funcției obiectiv, care, în cazul nostru, este profitul marginal total. Această marjă de contribuție depinde de cantitatea de produse A și B produse. Trebuie calculate valorile acestor cantități și, prin urmare, sunt variabilele dorite în model. Deci, să notăm: x 1 = numărul de unități de produs A produse în luna următoare. x 2 = numărul de unități de produs B produse în luna următoare. Este foarte important să definiți clar toate variabilele; acordați o atenție deosebită unităților de măsură și perioadei de timp la care se referă variabilele. Etapă. 2. Construirea funcției obiectiv O funcție obiectiv este o ecuație liniară care trebuie fie maximizată, fie minimizată. Conține variabila țintă exprimată în termenii variabilelor dorite, adică Z exprimat în termeni de x 1 , x 2 ... ca o ecuație liniară. În exemplul nostru, fiecare produs fabricat A aduce 2500 de ruble. profitul marginal, iar la fabricarea x 1 unități de produs A, profitul marginal va fi de 2500 * x 1. În mod similar, profitul marginal din fabricarea x 2 unități de produs B va fi 3500 * x 2. Astfel, profitul marginal total primit in luna urmatoare datorita producerii a x 1 unitati de produs A si x 2 unitati de produs B, adica variabila tinta Z va fi: Z = 2500 * x 1 + 3500 * x 2 Nikolay încearcă să maximizeze acest indicator. Astfel, funcția obiectiv din modelul nostru este: Maximizați Z = 2500 * x 1 + 3500 * x 2 Etapă. 3. Definirea restricţiilor Constrângerile sunt un sistem de ecuații liniare și/sau inegalități care limitează mărimea variabilelor necesare. Ele reflectă matematic disponibilitatea resurselor, factorii tehnologici, condițiile de marketing și alte cerințe. Constrângerile pot fi de trei tipuri: „mai mici decât sau egale”, „mai mari decât sau egale”, „strict egale”. În exemplul nostru, produsele A și B necesită timp de procesare, materii prime și forță de muncă pentru a produce, iar aceste resurse sunt limitate ca disponibilitate. Volumele de producție ale acestor două produse (adică valorile x 1 din 2) vor fi astfel limitate de faptul că cantitatea de resurse necesară în procesul de producție nu poate depăși ceea ce este disponibil. Luați în considerare situația cu timpul de procesare a mașinii. Producția fiecărei unități de produs A necesită trei ore de prelucrare automată, iar dacă sunt produse x 1 unități, atunci se vor cheltui 3 * x 1 ore din această resursă. Producția fiecărei unități de produs B necesită 10 ore și, prin urmare, dacă se produc x 2 produse, atunci vor fi necesare 10 * x 2 ore. Astfel, cantitatea totală de timp de mașină necesară pentru a produce x 1 unități de produs A și x 2 unități de produs B este 3 * x 1 + 10 * x 2 . Timpul total al mașinii nu poate depăși 330 de ore. Din punct de vedere matematic, aceasta este scrisă după cum urmează: 3 * x 1 + 10 * x 2 ≤ 330 Considerații similare se aplică materiilor prime și forței de muncă, permițând să se noteze încă două restricții: 16 * x 1 + 4 * x 2 ≤ 400 6 * x 1 + 6 * x 2 ≤ 240 În sfârșit, trebuie menționat că există o condiție conform căreia trebuie fabricate cel puțin 12 unități de produs B: Etapa 4. Scrierea condiţiilor de non-negativitate Variabilele cerute nu pot fi numere negative, care trebuie scrise ca inegalități x 1 ≥ 0 și x 2 ≥ 0. În exemplul nostru, a doua condiție este redundantă, deoarece s-a determinat mai sus că x 2 nu poate fi mai mic de 12. Modelul complet de programare liniară pentru problema de producție a lui Nikolai poate fi scris astfel: Maximizați: Z = 2500 * x 1 + 3500 * x 2 Cu condiția ca: 3 * x 1 + 10 * x 2 ≤ 330 16 * x 1 + 4 * x 2 ≤ 400 6 * x 1 + 6 * x 2 ≤ 240 Luați în considerare o metodă grafică pentru rezolvarea unei probleme de programare liniară. Această metodă este potrivită numai pentru probleme cu două variabile necesare. Modelul construit mai sus va fi folosit pentru a demonstra metoda. Axele de pe grafic reprezintă cele două variabile necunoscute (Fig. 2). Nu contează ce variabilă să traseze de-a lungul cărei axe. Este important să alegeți o scară care vă va permite în cele din urmă să construiți o diagramă vizuală. Deoarece ambele variabile trebuie să fie nenegative, este trasat doar primul cadran. Orez. 2. Axe grafice de programare liniară Luați în considerare, de exemplu, prima constrângere: 3 * x 1 + 10 * x 2 ≤ 330. Această inegalitate descrie aria de sub linie: 3 * x 1 + 10 * x 2 = 330. Această linie intersectează axa x 1 la x 2 \u003d 0, adică ecuația arată astfel: 3 * x 1 + 10 * 0 \u003d 330, iar soluția sa: x 1 \u003d 330 / 3 \u003d 110 În mod similar, calculăm punctele de intersecție cu axele x 1 și x 2 pentru toate condițiile de constrângere: Grafic, prima limitare este prezentată în Fig. 3. Orez. 3. Construirea domeniului soluțiilor fezabile pentru prima constrângere Orice punct din triunghiul selectat sau de pe marginile acestuia va respecta această constrângere. Astfel de puncte sunt numite valide, iar punctele din afara triunghiului sunt numite invalide. În mod similar, reflectăm restul restricțiilor pe diagramă (Fig. 4). Valorile x 1 și x 2 pe sau în interiorul zonei umbrite ABCDE vor respecta toate constrângerile modelului. O astfel de regiune se numește domeniul soluțiilor admisibile. Orez. 4. Zona de soluții fezabile pentru modelul în ansamblu Acum, în zona soluțiilor fezabile, este necesar să se determine valorile x 1 și x 2 care maximizează Z. Pentru a face acest lucru, în ecuația funcției obiective: Z = 2500 * x 1 + 3500 * x 2 împărțim (sau înmulțim) coeficienții înainte de x 1 și x 2 cu același număr, astfel încât valorile rezultate să se încadreze în intervalul afișat pe grafic; în cazul nostru, un astfel de interval este de la 0 la 120; deci coeficienții pot fi împărțiți la 100 (sau 50): Z = 25x 1 + 35x 2 apoi atribuiți lui Z o valoare egală cu produsul coeficienților înainte de x 1 și x 2 (25 * 35 = 875): 875 = 25x 1 + 35x 2 și, în final, găsiți punctele de intersecție ale dreptei cu axele x 1 și x 2: Să trasăm această ecuație țintă pe grafic în același mod ca și constrângerile (Fig. 5): Orez. 5. Aplicarea funcției obiectiv (linia punctată neagră) în zona soluțiilor fezabile Valoarea Z este constantă pe toată linia funcției obiectiv. Pentru a găsi valorile x 1 și x 2 care maximizează Z, trebuie să transferați paralel linia funcției obiectiv într-un astfel de punct în limitele ariei soluțiilor admisibile, care este situat la maxim. distanța de la linia inițială a funcției obiectiv în sus și spre dreapta, adică până la punctul C (Fig. 6). Orez. 6. Linia funcției obiectiv a atins maximul în regiunea soluțiilor fezabile (la punctul C) Se poate concluziona că soluția optimă va fi situată într-unul din punctele extreme ale zonei de decizie. În care, va depinde de panta funcției obiectiv și de ce problemă rezolvăm: maximizarea sau minimizarea. Astfel, nu este necesar să desenați o funcție obiectiv - tot ce este necesar este să determinați valorile lui x 1 și x 2 la fiecare dintre punctele extreme citind din diagramă sau rezolvând perechea corespunzătoare de ecuații. Valorile găsite ale lui x 1 și x 2 sunt apoi substituite în funcția obiectiv pentru a calcula valoarea corespunzătoare a lui Z. Soluția optimă este cea în care se obține valoarea maximă a lui Z la rezolvarea problemei de maximizare și cea minimă. la rezolvarea problemei de minimizare. Să definim, de exemplu, valorile lui x 1 și x 2 în punctul C. Rețineți că punctul C se află la intersecția dreptelor: 3x 1 + 10x 2 = 330 și 6x 1 + 6x 2 = 240. Soluția acestui sistem de ecuații dă: x 1 = 10, x 2 = 30. Rezultatele calculului pentru toate vârfurile ariei soluțiilor fezabile sunt date în tabel: Astfel, Nikolai Kuznetsom trebuie să planifice producția a 10 articole A și 30 de articole B pentru luna următoare, ceea ce îi va permite să primească un profit marginal de 130 de mii de ruble. Pe scurt, esența metodei grafice pentru rezolvarea problemelor de programare liniară poate fi rezumată după cum urmează: CONTROLUL MUNCII LA DISCIPLINA: „METODE DE SOLUȚII OPTIME” Opțiunea numărul 8 1.
Rezolvați o problemă de programare liniară folosind o metodă grafică. Găsiți maximul și minimul funcției sub constrângeri date: Decizie Este necesar să se găsească valoarea minimă a funcției obiectiv și cea maximă, în cadrul sistemului de restricții: 9x1 +3x2 ≥30, (1) X 1 + x 2 ≤4, (2) x 1 + x 2 ≤8, (3) Să construim domeniul soluțiilor admisibile, i.e. rezolvați grafic sistemul de inegalități. Pentru a face acest lucru, construim fiecare linie dreaptă și definim semiplanurile date de inegalități (semiplanurile sunt marcate cu un prim). Intersecția semiplanurilor va fi aria ale cărei coordonate ale punctelor satisfac condiția inegalităților sistemului de constrângeri ale problemei. Să notăm limitele regiunii poligonului soluție. Să construim o dreaptă corespunzătoare valorii funcției F = 0: F = 2x 1 +3x 2 = 0. Vectorul de gradient compus din coeficienții funcției obiectiv indică direcția de minimizare a lui F(X). Începutul vectorului este punctul (0; 0), sfârșitul este punctul (2; 3). Să mutam această linie în mod paralel. Deoarece ne interesează soluția minimă, deci, mutam linia dreaptă până la prima atingere a zonei desemnate. Pe grafic, această linie este indicată printr-o linie punctată. Drept După ce am rezolvat sistemul de ecuații, obținem: x 1 = 3,3333, x 2 = 0. Unde putem afla valoarea minima a functiei obiectiv: . Luați în considerare funcția obiectivă a problemei. Să construim o dreaptă corespunzătoare valorii funcției F = 0: F = 2x 1 +3x 2 = 0. Vectorul gradient compus din coeficienții funcției obiectiv indică direcția de maximizare a lui F(X). Începutul vectorului este punctul (0; 0), sfârșitul este punctul (2; 3). Să mutam această linie în mod paralel. Deoarece ne interesează soluția maximă, mutam linia dreaptă până la ultima atingere a zonei desemnate. Pe grafic, această linie este indicată printr-o linie punctată. Drept Unde putem afla valoarea maxima a functiei obiectiv: . Răspuns: 2
.
Rezolvați o problemă de programare liniară folosind metoda simplex: Decizie Să rezolvăm problema directă a programării liniare prin metoda simplex, folosind tabelul simplex. Să determinăm valoarea minimă a funcției obiectiv Pentru a construi primul plan de referință, reducem sistemul de inegalități la un sistem de ecuații prin introducerea de variabile suplimentare. În prima inegalitate de sens (≥), introducem variabila de bază X 3
cu semnul minus. În a 2-a inegalitate de sens (≤), introducem variabila de bază X 4
. În sensul a 3-a inegalitate (≤), introducem variabila de bază x 5 . Să introducem variabile artificiale Pentru a seta sarcina la minim, scriem funcția obiectiv astfel: . Pentru utilizarea variabilelor artificiale introduse în funcția obiectiv se impune o așa-numită penalizare a lui M, un număr pozitiv foarte mare, care de obicei nu este specificat. Baza rezultată se numește artificială, iar metoda soluției se numește metoda bazei artificiale. Mai mult, variabilele artificiale nu au legătură cu conținutul sarcinii, dar vă permit să construiți un punct de plecare, iar procesul de optimizare obligă aceste variabile să ia valori zero și să asigure admisibilitatea soluției optime. Din ecuații exprimăm variabile artificiale: x 6 \u003d 4-x 1 -x 2 +x 3, pe care le înlocuim în funcția obiectiv: sau. Matricea coeficientilor Să rezolvăm sistemul de ecuații în raport cu variabilele de bază: X 6
, X 4
, X 5.
Presupunând că variabilele libere sunt 0, obținem prima linie de bază: X1 = (0,0,0,2,10,4) O soluție de bază se numește admisibilă dacă este nenegativă. X 1
X 2
X 3
X 4
X 5
X 6
X 6
X 4
X 5
Linia de referință actuală nu este optimă deoarece există coeficienți pozitivi în rândul indicelui. Vom alege ca principală coloana corespunzătoare variabilei x 2, deoarece acesta este cel mai mare coeficient. Calculați valorile D i Prin urmare, a doua linie conduce. Elementul de rezoluție este egal cu (2) și este situat la intersecția coloanei de conducere și a rândului principal. X 1
X 2
X 3
X 4
X 5
X 6
X 6
X 4
X 5
Formăm următoarea parte a tabelului simplex. În locul variabilei x 4, variabila x 2 va intra în planul 1. Linia corespunzătoare variabilei x 2 din planul 1 se obține prin împărțirea tuturor elementelor dreptei x 4 din planul 0 la elementul de activare RE=2. În locul elementului de rezolvare, obținem 1. În celulele rămase ale coloanei x 2, scriem zerouri. Astfel, în noul plan se umple 1 rând x 2 și coloana x 2. Toate celelalte elemente ale noului plan 1, inclusiv elementele rândului index, sunt determinate de regula dreptunghiului. X 1
X 2
X 3
X 4
X 5
X 6
X 6
X 2
X 5
1 1 / 2 +1 1 / 2 M Linia de referință actuală nu este optimă deoarece există coeficienți pozitivi în rândul indicelui. Vom alege coloana corespunzătoare variabilei x 1 drept prima, deoarece acesta este cel mai mare coeficient. Calculați valorile D i după rânduri ca coeficient de împărțire: Prin urmare, prima linie conduce. Elementul de rezolvare este egal cu (1 1 / 2) și este situat la intersecția coloanei principale și a rândului principal. X 1
X 2
X 3
X 4
X 5
X 6
X 6
1
1
/
2
X 2
X 5
-1
1
/
2
+1
1
/
2
M Formăm următoarea parte a tabelului simplex. În loc de variabila x 6 , variabila x 1 va fi inclusă în planul 2. Obținem un nou tabel simplex: X 1
X 2
X 3
X 4
X 5
X 6
X 1
X 2
X 5
Niciuna dintre valorile rândului indexului nu este pozitivă. Prin urmare, acest tabel determină planul optim de sarcini. Versiunea finală a tabelului simplex: X 1
X 2
X 3
X 4
X 5
X 6
X 1
X 2
X 5
Deoarece nu există variabile artificiale în soluția optimă (sunt egale cu zero), această soluție este fezabilă. Planul optim poate fi scris după cum urmează: x 1 \u003d 2, x 2 \u003d 2:. Răspuns: 3.
Compania „Trei bărbați grasi” este angajată în livrarea de conserve de carne din trei depozite situate în diferite părți ale orașului către trei magazine. Stocurile de conserve disponibile în depozite, precum și volumul comenzilor din magazine și ratele de livrare (în unități monetare convenționale) sunt prezentate în tabelul de transport. Găsiți un plan de transport care oferă cele mai puține costuri în numerar (efectuați planul de transport inițial folosind metoda „colțul de nord-vest”). Decizie Să verificăm condiția necesară și suficientă pentru rezolvarea problemei: Condiția de echilibru este îndeplinită. Stocurile sunt egale cu nevoi. Prin urmare, modelul problemei transportului este închis. Să introducem datele inițiale în tabelul de distribuție. Are nevoie Folosind metoda colțului de nord-vest, vom construi primul plan de bază al sarcinii de transport. Planul începe să fie completat din colțul din stânga sus. Elementul dorit este 4. Pentru acest element stocurile sunt 300, nevoile sunt 250. Deoarece minimul este 250, îl scadem: . 300 - 250 = 50
250 - 250 = 0
Elementul dorit este 2. Pentru acest element stocurile sunt 50, nevoile sunt 400. Deoarece minimul este 50, îl scadem: . 50 - 50 = 0
400 - 50 = 350
Elementul dorit este 5. Pentru acest element stocurile sunt 300, nevoile sunt 350. Deoarece minimul este 300, îl scadem: 300 - 300 = 0
350 - 300 = 50
Elementul dorit este 3. Pentru acest element, stocurile sunt 200, nevoile sunt 50. Deoarece minimul este 50, îl scadem: 200 - 50 = 150
50 - 50 = 0
Elementul dorit este 6. Pentru acest element stocurile sunt 150, nevoile sunt 150. Deoarece minimul este 150, îl scadem: 150 - 150 = 0
150 - 150 = 0
Are nevoie
Documente similare
;
; 
;
; 
.
.
Sarcina numărul 2
ó
ó 
Apoi 
; ; 
- valoarea minima a functiei.
ó 
ó 
ó 
; ; funcţia obiectivă maximă este atinsă când 
; .
Sarcina numărul 3
Exemple
Funcții netede și sisteme de ecuații
Programare liniară
Optimizare combinatorie
Capitolul 1. Enunţarea problemei principale a programării liniare
Programare liniară
(1.2) cerințe de non-negativitate
(1.3) unde X j– variabile (necunoscute);
- coeficienţii problemei de programare liniară.1.2. Metoda simplex pentru rezolvarea problemelor de programare liniară
.6.1 Introducere
6.2 Fundamentele teoriei optimizării
X1, x2, x3,...,xn.
Probleme de programare liniară
, (5.1)
, , (5.2)
, (5.3) , , , (5.5)
. ,
.
Interval acceptabil
Limita valorilor permise
Intersecția cu axa x 1
Intersecția cu axa x 2
3 * x 1 + 10 * x 2 ≤ 330
3 * x 1 + 10 * x 2 = 330
x 1 = 110; x 2 = 0
x 1 = 0; x 2 = 33
16 * x 1 + 4 * x 2 ≤ 400
16 * x 1 + 4 * x 2 = 400
x 1 = 25; x 2 = 0
x 1 = 0; x 2 = 100
6 * x 1 + 6 * x 2 ≤ 240
6 * x 1 + 6 * x 2 = 240
x 1 = 40; x 2 = 0
x 1 = 0; x 2 = 40
x 2 ≥ 12
x 2 = 12
nu traversează; merge paralel cu axa x 1
x 1 = 0; x 2 = 12
Punct
Valoare x 1
Valoare x 2
Z \u003d 2500x 1 + 3500x 2
DAR
22
12
97 000
LA
20
20
120 000
Cu
10
30
130 000
D
0
33
115 500
E
0
12
42 000
,
.
intersectează regiunea în punctul C. Deoarece punctul C se obține ca rezultat al intersecției dreptelor (4) și (1), atunci coordonatele sale satisfac ecuațiile acestor drepte: 
.
intersectează regiunea în punctul B. Deoarece punctul B se obține ca rezultat al intersecției dreptelor (2) și (3), atunci coordonatele sale satisfac ecuațiile acestor drepte: 
.
și 
.
.
în următoarele condiții-restricții: 
.
: în prima egalitate introducem o variabilă X 6
;
acest sistem de ecuații are forma: 
.
și alegeți cel mai mic dintre ele: min(4: 1 , 2: 2 , 10: 2) = 1.
iar dintre ele o alegem pe cea mai mică: min (3: 1 1 / 2, -, 8: 2) = 2.
,
.
=
300 + 300 + 200 = 800 .
=
250 + 400 + 150 = 800.
