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 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, deplasăm linia dreaptă până la prima atingere a zonei desemnate. Pe grafic, această linie este indicată printr-o linie punctată.

Drept
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:
.

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

.

Unde putem afla valoarea maxima a functiei obiectiv: .

Răspuns:
și
.

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
în următoarele condiții-restricții:
.

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 : în prima egalitate introducem o variabilă X 6 ;

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 substituim în funcția obiectiv: sau.

Matricea coeficientilor
acest sistem de ecuații are forma:
.

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 bază actuală nu este optimă deoarece există coeficienți pozitivi în rândul indicelui. Vom alege coloana corespunzătoare variabilei x 2 drept prima, deoarece acesta este cel mai mare coeficient. Calculați valorile D i și alegeți cel mai mic dintre ele: min(4: 1 , 2: 2 , 10: 2) = 1.

Prin urmare, a doua linie conduce.

Elementul de rezoluție este egal cu (2) și este situat la intersecția coloanei principale și a rândului de început.

		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 bază actuală nu este optimă deoarece există coeficienți pozitivi în rândul indicelui. Vom alege ca principală coloana corespunzătoare variabilei x 1, deoarece acesta este cel mai mare coeficient. Calculați valorile D i după rânduri ca coeficient de împărțire: iar dintre ele o alegem pe cea mai mică: min (3: 1 1 / 2, -, 8: 2) = 2.

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:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Condiția de echilibru este îndeplinită. Stocurile sunt egale cu nevoi. Prin urmare, modelul problemei de transport 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 problemei transportului.

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

Teste pentru controlul actual al cunoștințelor

1. Orice economie - model matematic O problemă de programare liniară constă în:

A. funcţie obiectivă şi sistem de constrângeri

b.funcţie obiectiv, sisteme de constrângeri şi condiţii pentru nonnegativitatea variabilelor

C. Sisteme de constrângeri și condiții pentru nonnegativitatea variabilelor

D. Funcția obiectivă și condițiile pentru nenegativitatea variabilelor

A.funcție obiectivă

B. sistem de ecuaţii

C. sistem de inegalităţi

D. condiţia de non-negativitate a variabilelor

3. Soluția optimă a problemei programării matematice este

A. soluţie admisibilă a sistemului de constrângeri

B. orice soluţie a sistemului de constrângeri

C.soluţie admisibilă a sistemului de constrângeri care duce la maximul sau minim al funcţiei obiectiv

D. soluţia maximă sau minimă a sistemului de constrângeri

4. Un sistem de constrângeri se numește standard dacă conține

A. toate mărcile

b.toate semnele

C. toate mărcile

D. toate semnele

5. Problema programării liniare se rezolvă în mod grafic, dacă în problemă

A. o variabilă

b.două variabile

C. trei variabile

D. patru variabile

6. Inegalitatea formei descrie

B. circumferinta

C.semiplan

d. avion

7. Se găsește maximul sau minimul funcției obiectiv

A. la origine

B. pe laturile unui poligon soluție convexă

C. în interiorul unui poligon soluție convexă

D.la vârfurile unui poligon soluție convexă

8. Forma canonică a LLP este o astfel de formă în care sistemul de restricții conține semne

A. toate mărcile

B. toate mărcile

C.toate semnele

D. toate semnele

9. Dacă constrângerea este specificată cu semnul „>=”, atunci în această constrângere se introduce o variabilă suplimentară cu un coeficient

b.-1

10. Se introduc variabile suplimentare în funcţia obiectiv cu coeficienţi

C.0

A.cantitatea de resursă cu numărul i necesară pentru fabricarea a 1 unitate de produs de tipul j-a

B. resurse neutilizate de tip i-lea

C. profit din vânzarea a 1 unitate de producţie de tip j --lea

D. cantitatea de produse de tipul j-a

12. Coloana de rezolvare la rezolvarea LLP pentru funcția obiectiv maxim este selectată în funcție de condiție

A.cea mai mare valoare pozitivă a coeficientului Cj al funcției obiectiv

B. cea mai mică valoare pozitivă a coeficientului Cj al funcţiei obiectiv

C. cea mai mare valoare negativă a coeficientului Cj al funcţiei obiectiv

D. orice coloană de coeficienți pentru necunoscute

13. Valoarea funcţiei obiectiv din tabelul cu planul optim este

A. la intersecția rândului de coeficienți ai funcției obiectiv cu coloana de coeficienți la x1

b.la intersecția rândului de coeficienți ai funcției obiectiv cu coloana b

C. în coloana de coeficienţi la xn

D. la intersecția rândului de coeficienți ai funcției obiectiv cu coloana bazei inițiale

14. Variabilele artificiale sunt introduse în sistemul de constrângeri în formă canonică cu coeficientul

A.1

15. Optimitatea planului din tabelul simplex este determinată de

A. prin coloana b

b.prin șirul de valori ale funcției obiective

C. Linia de permisiune

D. prin coloana de permisiune

16. Având în vedere o problemă de programare liniară

b.1

17. Având în vedere o problemă de programare liniară

Numărul de variabile artificiale pentru această problemă este

C.2

18. Dacă LLP-ul original are forma

apoi constrângerile problemei duale

A. au forma

b.arată ca

C. arata ca

D. arata ca

19. Dacă LLP-ul original are forma

A. au forma

B. au forma

C. arata ca

D.arată ca

20. Coeficienții pentru funcțiile obiective necunoscute ale problemei duale sunt

A. coeficienți pentru funcții obiective necunoscute ale problemei inițiale

b.membri liberi ai sistemului de constrângeri ai problemei originale

C. necunoscute ale problemei originale

D. coeficienţi pentru necunoscute ai sistemului de constrângeri ale problemei iniţiale

21. Dacă LLP inițial a fost la maximul funcției obiectiv, atunci sarcina dublă va fi

A. tot la maxim

B. fie maxime, fie minime

C. atât maxime cât şi minime

D.la minim

22. Legătura dintre problemele originale și cele duale este aceea

A. ambele sarcini trebuie rezolvate

b.solutia unuia dintre ele se obtine din solutia celuilalt

C. din rezolvarea problemei duale este imposibil să se obţină soluţii la original

D. ambele au aceleaşi soluţii

23. Dacă LLP-ul original are forma

apoi funcţia obiectivă a problemei duale

A. au forma

B. au forma

C.arată ca

D. arata ca

24. Dacă LLP-ul original are forma

atunci numărul de variabile din problema duală este

b.2

25. Modelul sarcinii de transport este închis,

A.dacă

26. Ciclul în problema transportului este

A. o polilinie dreptunghiulară închisă, ale cărei toate vârfurile sunt în celule ocupate

B. o polilinie dreptunghiulară închisă, ale cărei toate vârfurile sunt în celule libere

C. o polilinie dreptunghiulară închisă, dintre care un vârf este într-o celulă ocupată, restul sunt în celule libere

D. o polilinie dreptunghiulară închisă, dintre care un vârf este într-o celulă liberă, iar restul în celule ocupate

27. Potențialele problemei de transport de dimensiune (m * n) sunt m + n numere ui și vj, pentru care condițiile

A.ui+vj=cij pentru celulele ocupate

B. ui+vj=cij pentru celule libere

C. ui+vj=cij pentru primele două coloane ale tabelului de distribuție

D. ui+vj=cij pentru primele două rânduri ale tabelului de alocare

28. Estimările unei probleme de transport de dimensiune (m + n) sunt numerele

yij=cij-ui-vj care sunt calculate

A. pentru celule ocupate

b.pentru celule libere

C. pentru primele două rânduri ale tabelului de distribuţie

D. pentru primele două coloane ale tabelului de distribuţie

29. Când se rezolvă o problemă de transport, valoarea funcției obiectiv ar trebui de la iterație la iterație

A. spor

B. creste sau nu se schimba

C. creşterea cu valoarea oricărui punctaj

D.scad sau rămân neschimbate

30. Numărul de celule ocupate dintr-un plan nedegenerat al problemei transportului trebuie să fie egal cu

C.m+n-1

31. sens economic funcţia obiectivă a sarcinii de transport

A. trafic total

b.costul total al transportului

C. livrări totale

D. nevoi totale

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 programare matematică, cercetare operațională, programare liniară, teorie decizii 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 propriu-zise. 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. LA caz 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 sistemul de ecuații al metodei cele mai mici pătrate(MNK). 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 mulțimea 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ă prin dependență liniarăîntre variabile și un test liniar. Astfel de probleme își găsesc aplicații extinse în domenii diverse activitate umana. 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 diferite feluri produse pentru depozitare î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: funcția obiectiv, valoare optimă care (maxim sau minim) trebuie găsit; restricții sub forma unui sistem ecuatii lineare sau inegalități; cerinţa de non-negativitate a variabilelor.

LA vedere generala modelul este scris astfel:

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 în care 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 modele din toate opțiunile posibile. LA anul trecut 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 ca 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 obiectiv 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, cum ar fi satisfacția clienților, 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 găsire a maximului prin inversarea semnului funcției obiectiv. Această tehnică este ilustrată în Figura 6.3.

Spațiu de proiectare

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 care trebuie luate în considerare la găsirea unei soluții. Ele reflectă legile naturii, economiei, drepturile, gusturile predominante și disponibilitatea materialele 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 în care are funcția obiectiv cea mai mare valoare comparativ 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- aceasta este problema matematica, care constă în găsirea valorii optime (adică maximă sau minimă) a funcției obiectiv, iar valorile variabilelor trebuie să aparțină unui anumit interval de valori acceptabile (ODV).

În general, formularea unei probleme extreme de programare matematică constă în determinarea celui mai mare sau cea mai mică valoare o funcție numită funcție obiectivă, în condiții (restricții), unde și – funcții predefinite, ș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ă sunt împărțite î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.

Găsiți printr-o metodă grafică maximul funcției obiectiv

F= 2X 1 + 3X 2 ® max

Cu restricții

Decizie folosind foi de calcul Excel

Să construim mai întâi pe o foaie solutie excel sisteme de inegalităţi.

Luați în considerare prima inegalitate.

Să construim o linie de limită din două puncte. Notați linia cu (L1) (sau Rândul 1). Coordonatele X 2 numărăm după formulele:

Pentru a construi, selectați un grafic de dispersie

Alegerea datelor pentru o linie dreaptă

Schimbați numele liniei:

Alegeți un aspect de diagramă. Schimbați numele axelor de coordonate:

Linie dreaptă (L1) pe diagramă:

Soluția la inegalitatea strictă poate fi găsită folosind un singur punct de testare care nu aparține dreptei (L1). De exemplu, folosind punctul (0; 0)W(L1).

0+3×0< 18 или 0 < 18 .

Inegalitatea este adevărată, prin urmare, soluția inegalității (1) va fi semiplanul în care se află punctul de testare (în figura de sub linia L1).

Apoi rezolvăm inegalitatea (2) .

Să construim linia de delimitare 2 din două puncte. Se notează linia cu (L2).

Linie dreaptă (L2) pe diagramă:

Soluția inegalității stricte 2 poate fi găsită folosind singurul punct de testare care nu aparține dreptei (L2). De exemplu, folosind punctul (0; 0)W(L2).

Înlocuind coordonatele punctului (0; 0), obținem inegalitatea

2×0 + 0< 16 или 0 < 16 .

Inegalitatea este adevărată, prin urmare, soluția inegalității (2) va fi semiplanul în care se află punctul de testare (în figura de mai jos, dreapta L2).

Apoi rezolvăm inegalitatea (3) .

Să construim o linie de limită din două puncte. Notați linia cu (L3).

Linie dreaptă (L3) pe diagramă:

Soluția inegalității stricte 2 poate fi găsită folosind singurul punct de testare care nu aparține dreptei (L3). De exemplu, folosind punctul (0; 0)W(L3).

Înlocuind coordonatele punctului (0; 0), obținem inegalitatea

Inegalitatea este adevărată, prin urmare, soluția inegalității (3) va fi semiplanul în care se află punctul de testare (în figura de mai jos, linia L3).

Apoi rezolvăm inegalitatea (4) .

Să construim o linie de limită din două puncte. Notați linia cu (L4).

Adăugați date în foaia Excel

Linie dreaptă (L4) pe diagramă:

Soluția inegalității stricte 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

Înlocuind coordonatele punctului (0; 0), obținem inegalitatea

Inegalitatea este adevărată, prin urmare, soluția inegalității (4) va fi semiplanul în care se află punctul de testare (în stânga dreptei L4 din figură).

Prin rezolvarea a două inegalități (5) și (6)

este primul sfert mărginit de liniile de coordonate și .

Sistemul de inegalități este rezolvat. Soluția sistemului de inegalități (1) - (6) din acest exemplu este un poligon convex în colțul din stânga jos al figurii, delimitat de liniile L1, L2, L3, L4 și liniile de coordonate și . Vă puteți asigura că poligonul este ales corect prin înlocuirea unui punct de testare, de exemplu (1; 1) în fiecare inegalitate a sistemului original. Înlocuind punctul (1; 1), obținem că toate inegalitățile, inclusiv constrângerile naturale, sunt adevărate.

Luați în considerare acum funcția obiectiv

F= 2X 1 + 3X 2 .

Să construim linii de nivel pentru valorile funcției F=0și F=12(valorile numerice sunt alese arbitrar). Adăugați date în foaia excel

Linii de nivel pe diagramă:

Să construim un vector de direcții (sau un gradient) (2; 3). Coordonatele vectoriale coincid cu coeficienții funcției obiectiv F.

TEMA: PROGRAMARE LINEARĂ

SARCINA 2.A. Rezolvarea unei probleme de programare liniară printr-o metodă grafică

Atenţie!

Aceasta este o VERSIUNE DE INTRODUCERE a lucrării nr. 2073, prețul originalului este de 200 de ruble. Proiectat în Microsoft Word.

Plată. Contacte.

Opțiunea 7. Găsiți valorile maxime și minimefuncția liniară Ф \u003d 2x 1 - 2 x 2cu restricții: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1,2.

Decizie:

Înlocuind condiționat semnele de inegalități cu semne de egalitate, obținem un sistem de ecuații x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Construim drepte conform acestor ecuații, apoi, în conformitate cu semnele inegalităților, selectăm semiplanurile și obținem partea comună a acestora - regiunea soluțiilor admisibile a EDO - patrulaterul MNPQ.

Valoarea minimă a funcției

tsii - în punctul M (2; 2)

Ф min = 2 2 - 2 2 = 0.

Valoarea maximă este atinsă în punctul N (10; 0),

Ф max \u003d 2 10 - 2 0 \u003d 20.

Opțiunea 8. Găsiți valorile maxime și minime

funcția liniară Ф \u003d x 1 + x 2

cu restricţii: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1,2.

Decizie:

Înlocuind condiționat semnele de inegalități cu semne de egalitate, obținem un sistem de ecuații x1 - 4 x2 = 4;

3 x1 - x2 = 0;

Construim drepte conform acestor ecuații, apoi, în conformitate cu semnele inegalităților, selectăm semiplanuri și obținem partea lor comună - regiunea soluțiilor admisibile a EDO - un poligon nemărginit MNPQ.

Valoarea minimă a funcției

- pe o linie dreaptă NP, de exemplu

în punctul Р(4; 0)

Ф min = 4 + 0 = 4.

ODE nu este limitată de sus, prin urmare, Ф max = + ∞.

Opțiunea 10. Găsiți valorile maxime și minime

funcția liniară Ф \u003d 2 x 1 - 3 x 2

cu restricții: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 < 5;

x i ≥ 0, i = 1,2.

Înlocuind condiționat semnele de inegalități cu semne de egalitate, obținem un sistem de ecuații

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Construim drepte conform acestor ecuații, apoi, în conformitate cu semnele inegalităților, selectăm semiplane și obținem partea lor comună - regiunea soluțiilor admisibile a EDO - poligonul MNPQRS.

Construim vectorul Г(2; -3) și desenăm prin origine linie de nivel- Drept.

Mutăm linia de nivel în direcție, în timp ce valoarea lui F crește. În punctul S(7; 0), funcția obiectiv atinge maximul Ф max =2·7–3·0= = 14. Deplasăm linia de nivel în direcție, în timp ce valoarea lui Ф scade. Valoarea minimă a funcției este în punctul N(0; 5)

Ф min = 2 0 – 3 5 = –15.

SARCINA 2.B. Rezolvarea unei probleme de programare liniară

metoda analitică simplex

Opțiunea 7. Minimizați funcția obiectiv Ф \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

sub restricții: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Decizie:

Numărul de necunoscute n=6, numărul de ecuații m=3. Prin urmare, r = n-m = 3 necunoscute pot fi considerate libere. Să alegem x 1 , x 3 și x 6 .

Exprimăm variabilele de bază x 2 , x 4 și x 5 în termeni de variabile libere și aducem sistemul la baza unității

x 2 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

Funcția obiectiv va arăta astfel:

Ф \u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 - 5 x 3 - 7 x 6

Să punem x 1 \u003d x 3 \u003d x 6 \u003d 0, în timp ce variabilele de bază vor prelua valorile x 2 \u003d 2; x 4 \u003d 9; x 5 \u003d 6, adică prima soluție fezabilă (0; 2; 0; 9; 6; 0), funcție obiectiv Ф 1 \u003d 13.

Variabilele x 3 și x 6 sunt incluse în funcția obiectiv cu coeficienți negativi, prin urmare, cu creșterea valorilor lor, valoarea lui Ф va scădea. Luați, de exemplu, x 6 . Din prima ecuație a sistemului (*) se poate observa că o creștere a valorii x 6 este posibilă până la x 6 \u003d 1 (atât timp cât x 2 ³ 0). În acest caz, x 1 și x 3 păstrează valori egale cu zero. Acum, ca variabile de bază, luăm x 4, x 5, x 6, ca liber - x 1, x 2, x 3. Să exprimăm noile variabile de bază în termenii noilor variabile libere. obține

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

Ф \u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

Atribuiți valori zero variabilelor libere, adică x 1 \u003d x 2 \u003d x 3 \u003d 0, în timp ce x 6 \u003d 1, x 4 \u003d 3, x 5 \u003d 4, adică a treia soluție validă (0; 0; 0; 3; 4; 1). În acest caz, Ф 3 \u003d 6.

Variabila x 3 este inclusă în funcția obiectiv cu un coeficient negativ, prin urmare, o creștere a x 3 față de zero va duce la o scădere a lui F. Din ecuația a 2-a se poate observa că x 3 poate crește până la 1/ 4, de la a 3-a ecuație - până la 2/3 . A doua ecuație este mai critică. Traducem variabila x 3 în numărul celor de bază, x 4 în numărul celor libere.

Acum luăm x 1 , x 2 și x 4 ca noi variabile libere. Să exprimăm noi variabile de bază x 3 , x 5 , x 6 în termenii lor. Să luăm sistemul

x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Funcția obiectiv va lua forma

Ф \u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Variabilele x 1 și x 2 sunt incluse în funcția obiectiv cu coeficienți negativi, prin urmare, cu creșterea valorilor lor, valoarea lui Ф va scădea. Luați, de exemplu, x2. Din a doua ecuație a sistemului, se poate observa că o creștere a valorii lui x 2 este posibilă până la x 2 \u003d 5 (atât timp cât x 5 ³ 0). În acest caz, x 1 și x 4 păstrează valori zero, valorile altor variabile sunt egale cu x 3 = 3/2; x 5 \u003d 0, x 6 \u003d 3/2, adică a patra soluție validă (0; 5; 3/2; 0; 0; 3/2). În acest caz, Ф 4 \u003d 5/4.

Acum luăm x 1 , x 4 și x 5 ca noi variabile libere. Să exprimăm noi variabile de bază x 2 , x 3 , x 6 în termenii lor. Să luăm sistemul

x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Funcția obiectiv va lua forma

F \u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Coeficienții pentru ambele variabile din expresia pentru Ф sunt pozitivi, prin urmare, o scădere suplimentară a valorii lui Ф este imposibilă.

Adică, valoarea minimă a lui Ф min = - 5, ultima soluție fezabilă (0; 5; 3/2; 0; 0; 3/2) este optimă.

Opțiunea 8. Maximizați funcția obiectiv Ф = 4 x 5 + 2 x 6

cu restricții: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 18;

Decizie:

Numărul de ecuații este 4, numărul de necunoscute este 6. Prin urmare, r = n - m = 6 - 4 = 2 variabile pot fi alese ca libere, 4 variabile ca bază. Alegem x 5 și x 6 ca libere, x 1, x 2, x 3, x 4 ca cele de bază. Exprimăm variabilele de bază în termeni de cele libere și reducem sistemul de ecuații la baza unității

x 1 \u003d 12 - x 5 - x 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 9 - 3/2 x 5 + x 6;

Scriem funcția obiectiv sub forma Ф = 4 x 5 + 2 x 6 . Atribuim valori zero variabilelor libere x 5 = x 6 = 0. În acest caz, variabilele de bază vor lua valorile x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , adică vom obține prima soluție fezabilă (12, 30 , 6, 9, 0,) și Ф 1 = 0.

Ambele variabile libere intră în funcția țintă cu coeficienți pozitivi, adică este posibilă o creștere suplimentară a F. Să traducem, de exemplu, x 6 în numărul celor de bază. Ecuația (1) arată că x 1 = 0 la x 5 = 12, în (2) ÷ (4) x 6 intră cu coeficienți pozitivi. Să trecem la o nouă bază: variabile de bază - x 6, x 2, x 3, x 4, libere - x 1, x 5. Să exprimăm noile variabile de bază prin noi variabile libere

x 6 \u003d 12 - x 1 - x 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 21 - x 1 - 5/2 x 5;

Funcția obiectiv va lua forma Ф = 24 - 2 x 1 + 2 x 5 ;

Atribuim valori zero variabilelor libere x 1 = x 5 = 0. În acest caz, variabilele de bază vor lua valorile x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , adică vom obține a doua soluție fezabilă (0, 42 , 30, 21, 0, 12) și Ф 2 = 24.

Funcția țintă x 5 intră cu un coeficient pozitiv, adică este posibilă o creștere suplimentară a F. Să trecem la o nouă bază: variabile de bază - x 6, x 5, x 3, x 4, libere - x 1 , x 2. Să exprimăm noi variabile de bază prin noi libere

x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 7/2 - 7/12 x 1 + 5/12 x 5;

Funcția obiectiv va lua forma Ф = 38 - 7/2 x 1 - 1/3 x 2;

Atribuiți valori zero x 1 = x 2 = 0 variabilelor libere. În acest caz, variabilele de bază vor lua valorile x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/ 2, adică vom obține a treia soluție fezabilă X 3 = (0, 0, 9, 7/2, 7, 5) și Ф 3 = 38.

Ambele variabile intră în funcția țintă cu coeficienți negativi, adică o creștere suplimentară a Ф este imposibilă.

Prin urmare, ultima soluție fezabilă este optimă, adică Х opt = (0, 0, 9, 7/2, 7, 5) și Ф max = 38.

Opțiunea 10. Maximizați funcția obiectiv Ф \u003d x 2 + x 3

sub restricții: x 1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 2.

Decizie:

Sistemul de ecuații - constrângeri este consistent, deoarece rangurile matricei sistemului de ecuații și ale matricei extinse sunt aceleași și egale cu 2. Prin urmare, două variabile pot fi luate drept libere, alte două variabile - de bază - pot fi exprimată liniar în termeni de două libere.

Să luăm ca variabile libere x 2 și x 3. Atunci variabilele x 1 și x 2 vor fi cele de bază, pe care le vom exprima în termeni liberi.

x 1 \u003d 1 + x 2 - x 3; (*)

x 4 \u003d 2 - x 2 + 2 x 3;

Funcția țintă a fost deja exprimată în termeni de x 2 și x 3 , adică Ф = x 2 + x 3 .

La x 2 \u003d 0 și x 3 \u003d 0, variabilele de bază vor fi egale cu x 1 \u003d 1, x 4 \u003d 2.

Avem prima soluție fezabilă X 1 = (1, 0, 0, 2), în timp ce Ф 1 = 0.

O creștere a Ф este posibilă cu o creștere, de exemplu, a valorii lui x 3, care este inclusă în expresia pentru Ф cu un coeficient pozitiv (x 2 rămâne egal cu zero). În prima ecuație a sistemului (*), se poate observa că x 3 poate fi crescut la 1 (din condiția x 1 ³0), adică această ecuație impune o restricție la creșterea valorii lui x 3. Prima ecuație a sistemului (*) se rezolvă. Pe baza acestei ecuații, trecem la o nouă bază, schimbând x 1 și x 3 locuri. Acum variabilele de bază vor fi x 3 și x 4, libere - x 1 și x 2. Acum exprimăm x 3 și x 4 în termeni de x 1 și x 2.

Obținem: x 3 \u003d 1 - x 1 + x 2; (**)

x 4 \u003d 4 - 2 x 1 + x 2;

Ф \u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2

Echivalând variabilele libere cu zero, obținem a doua soluție de bază admisibilă X 2 = (0; 0; 1; 4), în care Ф 2 =1.

O creștere a lui F este posibilă cu o creștere a x 2. Creșterea în x 2, judecând după ultimul sistem de ecuații (**), nu este limitată. Prin urmare, Ф va prelua toate valorile pozitive mari, adică Ф max = + ¥.

Deci, funcția obiectiv Ф nu este mărginită de sus, deci nu există o soluție optimă.

SARCINA 2.D. Scrieți o problemă duală cu cea dată.

sarcina originală.

Opțiunea 7. Maximizați funcția obiectiv Ф = 2× x 1 - x 4

cu restricții: x 1 + x 2 \u003d 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Decizie:

Aducem sistemul de constrângeri într-o singură formă, de exemplu, canonică prin introducerea de variabile suplimentare în ecuația a 2-a și a 3-a

x 1 + x 2 = 20,

x 2 + 2 × x 4 - x 5 \u003d 5,

- x 1 + x 2 + x 3 + x 6 \u003d 8.

Avem o problemă asimetrică de al 2-lea tip. Problema dublă va arăta astfel:

Minimizează funcția obiectiv F = 20 × y 1 + 5 × y 2 + 8 × y 3

pentru y 1 — y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

y 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Opțiunea 8. Maximizați funcția obiectiv Ф \u003d x 2 - x 4 - 3× x 5

cu restricții: x 1 + 2× x 2 - x 4 + x 5 \u003d 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (i = 1, 6)

Decizie:

Avem problema de maximizare originală cu un sistem de constrângeri sub formă de ecuații, adică o pereche de probleme duale are o formă asimetrică de al 2-lea tip, al cărui model matematic sub formă de matrice are forma:

Problemă inițială: Problemă dublă:

F = C × X max F = B T × Ymin

la un × X \u003d B la A T × Y ≥ C T

În problema inițială, rândul-matrice de coeficienți pentru variabilele din funcția obiectiv are forma С = (0; 1; 0; -1; -3; 0),

matricea coloanei de termeni liberi și matricea de coeficienți pentru variabilele din sistemul de constrângeri au forma

B \u003d 2, A \u003d 0 - 4 1 2 -1 0

Găsiți matricea de coeficienți transpusă, rândul matricei de coeficienți pentru variabilele din funcția obiectiv și coloana matricei de membri liberi

0 1 0 0 V T \u003d (1; 2; 5)

A T = -1 2 0 C T = -1

Problema duală poate fi scrisă în următoarea formă:

găsiți valoarea minimă a funcției obiectiv F = y 1 + 2 × y 2 + 5 × y 3

sub restricții y 1 ≥ 0,

2× y 1-4 × y 2 + 3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Opțiunea 10. Minimizați funcția Ф = x 1 + x 2 + x 3

limitat: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Decizie:

Avem problema de minimizare originală cu un sistem de constrângeri sub formă de inegalități, adică o pereche de probleme duale are o formă simetrică de al 3-lea tip, al cărui model matematic sub formă de matrice are forma:

Problemă inițială Problemă dublă

F = C × X min F \u003d B T × Ymax

la un × X ≥ B la A T × Y ≤ CT

X ≥ 0 Y ≥ 0

În problema originală, matricea-rând de coeficienți pentru variabilele din funcția obiectiv, matricea-coloana de termeni liberi și matricea de coeficienți pentru variabilele din sistemul de constrângeri au forma

C \u003d (1; 1; 1), B \u003d 3, A \u003d 6 4 5

Să găsim matricele problemei duale

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Problema dublă este formulată astfel:

Maximizați funcția obiectiv F = 2y 1 + 3y 2 + 4y 3

sub restricții 3 × y 1 + 6 × y 2 + 8 × y 3 ≤ 1,

9× y 1 + 4 × y 2 + 2 × y 3 ≤ 1,

7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

SARCINA 2.C. Rezolvarea unei probleme de programare liniară folosind tabele simplex.

Opțiunea 7. Maximizați funcția obiectiv Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

sub restricții: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Decizie:

Reducem sistemul de constrângeri la forma canonică

2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Avem un sistem de 3 ecuații cu 7 necunoscute. Alegem x 1 , z 1 , z 3 ca 3 variabile de bază, x 2 , x 3 , x 4 , z 2 ca libere, exprimăm variabilele de bază prin ele.

Din (2) avem x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Înlocuind în (1) și (3), obținem

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \u003d 2.

Compuneți un tabel simplex

Iterație Tabelul 1

De bază AC	Libertate. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 \u003d (1; 0; 0; 0; 2; 0; 4) F 1 \u003d 2.

II iterație Tabelul 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 \u003d (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 \u003d 4.

III iterație Tabelul 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 \u003d (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 \u003d 52/7.

Iterația IV Tabelul 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 \u003d 149/14.

Nu există numere negative în rândul index al ultimului tabel, adică în expresia pentru funcția obiectiv, toate Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Răspuns: Ф max = 149/14,

soluție optimă (0; 0; 25/14; 37/14; 1/2; 0; 0)

Opțiunea 8. Minimizați funcția obiectiv Ф = 5 x 1 - x 3

sub restricții: x 1 + x 2 + 2 x 3 - x 4 \u003d 3,

x 2 + 2 x 4 \u003d 1,

Decizie:

Numărul de variabile este 4, rangul matricei este 2, prin urmare numărul de variabile libere este r \u003d 4 - 2 \u003d 2, numărul de variabile de bază este, de asemenea, 2. Luăm x 3, x 4 ca variabile libere, vom exprima variabilele de bază x 1, x 2 în termeni de liber și aducem sistemul la baza unității:

x 2 \u003d 1 - 2 x 4,

x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 2 - 2 x 3 + 3 x 4

Ф \u003d 5 x 1 - x 3 \u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \u003d 10 - 10 x 3 + 15 x 4 - x 3 \u003d 10 - 11 x 3 + 15 x 4

Scriem sistemul de ecuații și funcția obiectiv într-o formă convenabilă pentru tabelul simplex, adică x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

Ф + 11 x 3 - 15 x 4 \u003d 10

Să facem o masă

Iterație Tabelul 1

De bază AC	Libertate. AC
x1	2	1	0		— 3		1/2
x2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 \u003d (2; 1; 0; 0) F 1 \u003d 10.

II iterație Tabelul 2

x3	1	1/2	0	1	-3/2		3/4
x2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 \u003d (0; 1; 1; 0) F 2 \u003d -1.

III iterație Tabelul 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 \u003d (0; 0; 7/4; 1/2) F 3 \u003d -7/4.

Nu există numere pozitive în rândul index al ultimului tabel, adică în expresia funcției obiectiv, toate Г i > 0. Avem cazul I, prin urmare, ultima soluție de bază este optimă.

Răspuns: Ф min = -7/4, soluție optimă (0; 0; 7/4; 1/2)

********************

Opțiunea 10. Minimizați funcția obiectiv Ф \u003d x 1 + x 2,

cu restricții: x 1 -2 x 3 + x 4 \u003d 2,

x 2 - x 3 + 2 x 4 \u003d 1,

Decizie:

Numărul de variabile este 5, rangul matricei este ​​3, prin urmare numărul de variabile libere este r \u003d 6-3 \u003d 2. Luăm x 3 și x 4 ca variabile libere, x 1, x 2, x 5 ca cele de bază. Toate ecuațiile sistemului au fost deja reduse la o singură bază (variabilele de bază sunt exprimate în termeni de cele libere), dar sunt scrise într-o formă care nu este convenabilă pentru utilizarea tabelelor simplex. Scriem sistemul de ecuații sub forma

x 1 - 2 x 3 + x 4 \u003d 2

x 2 - x 3 +2 x 4 \u003d 1

x 5 + x 3 - x 4 . = 5

Exprimăm funcția obiectiv în termeni de variabile libere și o scriem sub forma Ф - 3 x 3 +3 x 4 = 3

Să facem o masă

Iterație Tabelul 1

De bază AC	Libertate. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 \u003d (2; 3; 0; 0; 5) F 1 \u003d 3.

masa 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 \u003d (3/2; 0; 0; 1/2; 11/2) F 2 \u003d 3/2.

Nu există numere pozitive în rândul index al ultimului tabel, adică în expresia funcției obiectiv, toate Гi > 0. Avem cazul 1, prin urmare, ultima soluție de bază este optimă.

Răspuns: Ф min = 3/2, soluția optimă este (3/2; 0; 0; 1/2; 11/2).