Î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.

Sarcina numărul 2

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.

Apoi ; ; - valoarea minima a functiei.

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 ; ; funcţia obiectivă maximă este atinsă când ; .

Sarcina numărul 3

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:

Întreaga perioadă de 4 ani este împărțită în 4 etape, fiecare fiind 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 la k - acea etapă, 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);

Agenția Federală pentru Educație

Instituție de învățământ de la bugetul de stat

studii profesionale superioare

„Universitatea Tehnică de Stat din Omsk”

CALCUL SI LUCRARE GRAFICA

prin disciplina"TEORIA CONTROLULUI OPTIM »

pe subiect "METODE DE OPTIMIZARE ȘI CERCETARE OPERAȚIONALĂ »

varianta 7

Efectuat:

student prin corespondență

Grupa de anul 4 ZA-419

Nume: Kuzhelev S. A.

Verificat:

Devyaterikova M.V.

Omsk - 2012
^

Sarcina 1. Metodă grafică de rezolvare a problemelor de programare liniară.

7) 7X 1 + 6X 2 → max 20X 1 + 6X 2 ≤ 15 16X 1 − 2X 2 ≤ 18 8X 1 + 4X 2 ≤ 20 13X 1 + 3X 2 ≤ 4 X 1 , X 2 ≥ 0.

Pasul 1. Construirea unei zone valide

Condițiile de nenegativitate a variabilelor și pătratelor limitează intervalul valorilor lor admisibile la primul cadran. Fiecare dintre celelalte patru constrângeri-inegalități ale modelului corespunde unui semiplan. Intersecția acestor semiplane cu primul cadran formează setul de soluții fezabile ale problemei.

Prima constrângere a modelului este . Înlocuind semnul ≤ din el cu semnul =, obținem ecuația . Pe fig. 1.1 definește o linie (1) care împarte planul în două semiplane, în acest caz deasupra și sub linie. Pentru a alege care dintre ele satisface inegalitatea , substituim în el coordonatele oricărui punct care nu se află pe linia dată (de exemplu, originea X 1 = 0, X 2 = 0). Deoarece obținem expresia corectă (20 0 + 6 0 = 0 ≤15), semiplanul care conține originea (marcat cu o săgeată) satisface inegalitatea. Altfel, un alt semiplan.

Procedăm în mod similar cu restul constrângerilor problemei. Intersecția tuturor semiplanurilor construite cu primul cadran se formează ABCD(vezi fig. 1). Acesta este scopul valid al sarcinii.

Pasul 2. Construirea unei linii de nivel Linie de nivel funcția obiectiv este un set de puncte din plan în care funcția obiectiv ia o valoare constantă. O astfel de mulțime este dată de ecuație f ( X) = const. Să punem, de exemplu, const = 0 și trageți o linie la nivel f ( X) = 0, adică în cazul nostru, direct 7 X 1 + 6X 2 = 0.

Această dreaptă trece prin origine și este perpendiculară pe vector. Acest vector este gradientul funcției obiectiv la (0,0). Gradientul unei funcții este un vector de valori ale derivatelor parțiale ale unei anumite funcții în punctul în cauză. În cazul problemei LP, derivatele parțiale ale funcției obiectiv sunt egale cu coeficienții Ceu, j = 1 , ..., n.

Gradientul arată direcția celei mai rapide creșteri a funcției. Mutarea liniei de nivel al funcției obiectiv f ( X) = const. perpendicular pe direcția gradientului, găsiți ultimul punct în care se intersectează cu zona. În cazul nostru, acesta este punctul D, care va fi punctul maxim al funcției obiectiv (vezi Fig. 2)

Se află la intersecția dreptelor (2) și (3) (vezi Fig. 1) și stabilește soluția optimă.

^ Rețineți că, dacă este necesară găsirea valorii minime a funcției obiectiv, linia de nivel este deplasată în direcția opusă direcției gradientului.

^ Pasul 3. Determinarea coordonatelor punctului maxim (minim) și a valorii optime a funcției obiectiv

Pentru a găsi coordonatele punctului C, este necesar să se rezolve un sistem format din ecuațiile directe corespunzătoare (în acest caz, din ecuațiile 2 și 3):

16X 1 − 2X 2 ≤ 18

8X 1 + 4X 2 ≤ 20

Se obține soluția optimă = 1,33.

^ Valoarea optimă a funcției obiectiv f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8

Decizie: găsiți valoarea maximă și minimă a funcției \(f (x, y)\) sub următoarele constrângeri $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min \ \ \begin(cases) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end(cases) $$
Este recomandabil să se folosească metoda grafică de rezolvare a problemei pentru probleme cu două variabile care sunt scrise într-o formă simetrică, precum și pentru probleme cu multe variabile, cu condiția ca notația lor canonică să nu conțină mai mult de două variabile libere.

În acest caz, o sarcină cu două variabile.

Algoritm pentru rezolvarea problemei „interpretarea geometrică a unei probleme de programare liniară”:

1. Să construim domeniul soluțiilor admisibile pe planul xOy.
2. Selectați zona soluțiilor nenegative.

4. Să construim o familie de funcții obiective.
5. Aflați valoarea maximă (minimă) a funcției obiectiv.

1. Construim domeniul solutiilor admisibile ale problemei \(D\).

Pentru a construi zona de soluții fezabile:
1) Construim linii de delimitare:
transformăm inegalitățile în egalități, iar apoi în ecuația unei drepte în segmente pe axele formei \(\frac(x)(a)+\frac(y)(b) = 1\), apoi \ (x=a\) este un segment tăiat pe axa Ox, \(y=b\) - pe axa Oy $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ - x+2y = 8 \end(cases) => \begin(cases) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac( y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ Pentru fiecare linie, puneți deoparte segmente pe axe și conectați-le. Avem liniile potrivite.

2) Găsim semiplanuri care satisfac inegalitățile date:
Pentru inegalitatea \(2x+3y\geq 6\) este semiplanul care se află deasupra dreptei \(2x+3y = 6\). AC direct
Pentru inegalitatea \(3x-2y\leq 18 => -3x+2y \geq -18\) este un semiplan care se află deasupra dreptei \(3x-2y = 18\). CB direct
Pentru inegalitatea \(-x+2y\leq 8\) este semiplanul care se află sub dreapta \(-x+2y = 8\). Direct AB

Domeniul soluțiilor fezabile este definit ca partea comună a celor trei semiplanuri corespunzătoare inegalităților date. Această zonă este un triunghi \(ABC\)

Regiunea \(D\) este triunghiul \(ABC\) vezi fig.

2. Selectați zona soluțiilor nenegative.

Regiunea soluțiilor nenegative este situată în primul trimestru și este o parte comună a tuturor celor cinci semiplanuri, trei dintre acestea fiind regiunea \(D\) obținută din inegalități și în plus două inegalități \(x \geq 0\ ) - semiplanul superior (sferturi I și II) și \(y \geq 0\) - semiplanul drept (sferturi I și IV), care exprimă condiția de nenegativitate a variabilelor \(x; y\). S-a obținut zona dorită de soluții nenegative \(DEBFG\)

3.Găsiți coordonatele vârfurilor regiunii.
Coordonatele celor patru vârfuri sunt deja cunoscute (acestea sunt punctele de intersecție a dreptelor cu axele).
Să notăm aceste coordonate:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
Aflați coordonatele punctului \(B\), ca puncte de intersecție ale dreptelor \(-x+2y = 8\) și \(3x-2y = 18\). Rezolvați sistemul de ecuații și găsiți coordonatele acestui punct $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x -2y = 18 \end(cases)=> \begin(cases) x = 13\\ y =10.5\end(cases)$$
Obținem coordonatele punctului \(B(13;10.5)\)

4. Construim o familie de funcții obiective.
Ecuația \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) definește pe planul xOy o familie de cercuri concentrice centrate în punctul cu coordonatele \ (Q(4 ;3)\), fiecare dintre acestea corespunde unei anumite valori a parametrului \(f\). După cum știți, pentru ecuația unui cerc parametrul \(f=R^2\).

Să reprezentăm în același sistem de coordonate o familie de cercuri concentrice \(f\) și o familie de drepte. Problema determinării punctului maxim (minim) al punctului \(f\) se va reduce la găsirea în zona admisibilă a punctului prin care trece cercul familiei \(f=const\), care este responsabil pentru cea mai mare (cea mai mică) valoare a parametrului \(f\).

5. Aflați valoarea maximă (minimă) a funcției obiectiv.

Valoarea minimă a funcției obiective: Prin creșterea treptată a razei cercului, am obținut că primul vârf prin care trece cercul este punctul \(G(3;0)\). Funcția obiectiv în acest punct va fi minimă și egală cu \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

Valoarea maximă a funcției obiectiv: Prin creșterea în continuare a razei cercului, am obținut că ultimul vârf prin care va trece cercul este punctul \(B(13;10.5)\). Funcția obiectiv în acest punct va fi maximă și egală cu \(f(13,10.5)=(13-4)^2 + (10.5-3)^2 = 137.25\)

Puteți verifica corectitudinea soluției înlocuind coordonatele vârfurilor rămase în ecuația funcției obiective:
la vârful \(D(0;2)\) valoarea funcției obiectiv este egală cu \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
la vârful \(E(0;4)\) valoarea funcției obiectiv este egală cu \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
la vârful \(F(6;0)\) valoarea funcției obiectiv este \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Am inteles

Răspuns:
valoarea minimă a funcției obiectiv \(f_(min) = 10\)
valoarea maximă a funcției obiectiv \(f_(max) = 137,25\)

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.

Exemple

Funcții netede și sisteme de ecuații

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.

Programare liniară

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.

Optimizare combinatorie

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.

Capitolul 1. Enunţarea problemei principale a programării liniare

1. Programare liniară

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

(1.2) cerințe de non-negativitate

(1.3) unde X j– variabile (necunoscute);

- coeficienţii problemei de programare liniară.

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.

1.2. Metoda simplex pentru rezolvarea problemelor de programare liniară

Metoda simplex a fost dezvoltată și aplicată pentru prima dată pentru a rezolva probleme în 1947 de către matematicianul american J. Dantzig.

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.

6.1 Introducere

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.

6.2 Fundamentele teoriei optimizării

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

X1, x2, x3,...,xn.

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 , conceput pentru a transporta 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:

Probleme de programare liniară

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ții (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ă:

, (5.1)

, , (5.2)

, , (5.3)

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 nenegativitate 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:

,

, , (5.5)

.

Sarcină 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 canonice LP.