Subiect 2.4. Metoda simplă de programare liniară.
Problemele bidimensionale ale programării liniare sunt rezolvate grafic. Pentru cazul N = 3, putem lua în considerare un spațiu tridimensional și funcția obiectivă va ajunge la valoarea sa optimă la unul dintre vârfurile polyedronului.
În forma generală, atunci când problema implicate N sunt necunoscute, se poate spune că regiunea fezabilă definită de constrângeri de sistem, apare poliedru convex în n spațiu -dimensional, și o valoare optimă a funcției obiectiv este atins într-una sau mai multe noduri. Rezolvați sarcini de date grafic, atunci când numărul de variabile mai mare de 3 este foarte dificil. Există o metodă universală pentru rezolvarea problemelor de programare liniară, numită metoda simplex.
Metoda simplex este fundamentală în programarea liniară. Soluția problemei începe cu luarea în considerare a unuia dintre vârfurile condiției polyhedron. Dacă vârful în cauză nu corespunde cu cel maxim (minim), atunci ei merg la cel vecin, mărind valoarea funcției țintă atunci când rezolvă problema la un maxim și scade-o la rezolvarea problemei la minimum. Astfel, trecerea de la un vârf la altul îmbunătățește valoarea funcției țintă. Deoarece numărul de vârfuri al unui polyhedron este mărginit, un număr finit de pași garantează găsirea valorii optime sau stabilirea faptului că problema este nedecisibilă.
Această metodă este universală, aplicabilă oricărei probleme de programare liniară în formă canonică. Sistemul de constrângere este un sistem de ecuații liniare în care numărul de necunoscute este mai mare decât numărul de ecuații. Dacă rangul sistemului este r. atunci putem alege r necunoscute, pe care le exprimăm prin necunoscutele rămase. Pentru certitudine, să presupunem că prima, consecutivă, necunoscută X 1. X 2. X r este aleasă. Apoi sistemul nostru de ecuații poate fi scris ca
În această formă, puteți aduce orice sistem comun. de exemplu, prin metoda Gauss. Adevărat, nu este întotdeauna posibil să exprimăm prin primele r necunoscute (am făcut acest lucru din motive de claritate a înregistrării). Cu toate acestea, există în mod necesar asemenea necunoscute. Aceste necunoscute (variabile) sunt numite de bază, restul sunt libere.
Prin atribuirea anumitor valori variabilelor libere și calculării valorilor variabilelor de bază (exprimate prin variabile libere), vom obține diferite soluții pentru sistemul nostru de constrângeri. Astfel, puteți obține orice soluție. Vom fi interesați de soluțiile speciale obținute în cazul în care variabilele libere sunt zero. Astfel de soluții se numesc soluții de bază. numărul acestora este același cu numărul diferitelor tipuri de bază ale acestui sistem de restricții. O soluție de bază este numită soluție de bază admisibilă sau soluție de suport. dacă valorile variabilelor din acesta nu sunt negative. Dacă variabilele de bază sunt X 1. X 2. X r. atunci soluția este 1. b 2. b r. 0. 0> va fi un suport, cu condiția ca b 1. b 2. b r ≥ 0.
Metoda simplex se bazează pe o teoremă care se numește teorema fundamentală a metodei simplex. Printre planurile optime ale problemei de programare liniară în formă canonică, este neapărat o soluție de sprijin a sistemului său de constrângere. Dacă planul optim al problemei este unic, atunci coincide cu o soluție de suport. Diferitele soluții de susținere a sistemului de constrângeri sunt finite. Prin urmare, soluția problemei în formă canonică ar putea fi căutată de o căutare a soluțiilor de susținere și de alegerea dintre ele una pentru care valoarea lui F este cea mai mare. Dar, în primul rând, toate soluțiile suport sunt necunoscute și trebuie găsite și, în al doilea rând, în problemele reale ale acestor soluții, multă căutare directă este aproape imposibilă. Metoda simplex este o anumită procedură de căutare direcțională a soluțiilor de suport. Plecând de la unele soluții de suport găsite în avans pentru un anumit algoritm al metodei simplex, se calculează o nouă soluție de suport, pe care valoarea funcției obiective F nu este mai mică decât cea veche. După o serie de pași, ajungem la o soluție de suport, care este planul optim.
Astfel, metoda simplex introduce o ordine definită atât în găsirea primei soluții de bază, cât și în trecerea la alte soluții de bază. Ideea lui este după cum urmează.
Având un sistem de constrângeri. redusă la o formă generală, adică la un sistem de ecuații lineare m cu n variabile (m
Articole similare
Trimiteți-le prietenilor: