Laboratorul 2 Algoritmul Simplex Metoda Celor Dou - Â Faze [PDF]

Zitiervorschau

Laboratorul 2 Algoritmul simplex primal. Metoda celor dou¼ a faze Problema 1 S¼ a se rezolve:

Rezolvare

8 sup(3x1 + 4x2 ) > > > > < x1 + 4x2 28 3x1 + x2 21 : > > > x1 + x2 10 > : x1 0; x2 0

Problema este în form¼ a canonic¼ a ¸si pentru aplicarea algoritmului simplex trebuie s¼ a o aducem mai întâi la forma standard, întroducând variabilele ecart x3 ; x4 ; x5 : 8 sup(3x1 + 4x2 ) > > > > 28 < x1 + 4x2 + x3 = 3x1 + x2 + x4 = 21 > > + x5 = 10 > x1 + x2 > : xi 0; i = 1; 5

:

Baza ini¸tial¼ a B0 este o matrice unitate I3 , variabilele de baz¼ a sunt x3 ; x4 ¸si x5 iar variabilele secundare x1 ¸si x2 : Solu¸tia de baz¼ a corespunz¼ atoare este x1 = x2 = 0; x3 = 28; x4 = 21; x5 = 10: Baza B0 = (a3 a4 a5 ) este primal admisibil¼ a pentru c¼ a xB = B0 1 b = b = (28 21 10)T 0; B = f3; 4; 5g ; R = f1; 2g :

Determinarea unui program de baz¼ a ini¸ tial Determinarea unei baze primal admisibile la pasul 0 al algoritmului simplex constituie uneori o parte important¼ a a rezolv¼ arii modelului pentru care exist¼ a metode speciale ca metoda celor dou¼a faze ( a bazei arti…ciale) ¸si metoda coe…cien¸tilor de penalizare. Nu se aleg la întâmplare m coloane din cele n coloane ale matricii A pentru c¼ a ele ar putea … liniar dependente sau solu¸tia de baz¼ a corespunz¼ atoare ar putea … neadmisibil¼ a. Metoda celor dou¼ a faze Fie modelul de programare liniar¼ a în forma standard:

(1)

8 < sup(inf)cT x Ax = b : x 0: 1

Presupunem b 0; în caz contrar se înmul¸teste ecua¸tia al c¼ arei termen liber este negativ cu 1. Scriind coloanele matricei A se pun în eviden¸ta¼ vectorii unitari ei = (0; :::; 1; :::0)T care se g¼ asesc printre coloanele ei: Dac¼ a exist¼ a to¸ti a o baz¼ a B = Im care este ¸si cei m vectori unitari ei ; i = 1; m; ace¸stia formeaz¼ primal admisibil¼ a pentru c¼ a B 1 b = b 0: Altfel, introducem unele variabile suplimentare numite variabile arti…ciale, totdeauna cu coe…cientul +1, în anumite restric¸tii, convenabil alese, pân¼ a când matricea sistemului de restric¸tii con¸tine m vectori unitari. Se ob¸tine un model extins ale c¼ arui solu¸tii nu corespund totdeauna cu solu¸tiile modelului ce trebuie rezolvat. Pentru a putea extrage din solu¸tia modelului extins o solu¸tie pentru modelul dat trebuie ca, în aceast¼ a solu¸tie, variabilele arti…ciale s¼ a ia valoarea zero. Astfel, vom c¼ auta s¼ a for¸t a¼m anularea variabilelor arti…ciale într-o prim¼ a faz¼ a de rezolvare, în care consider¼ am drept func¸tie obiectiv, suma tuturor variabilelor arti…ciale, care trebuie s¼ a devin¼ a minim¼ a:

(2)

8 < inf xan+1 + ::: + xan+m Ax + xa = b : x 0; xa 0

unde xai+n ; 1 i m sunt variabilele arti…ciale. Matricea coe…cien¸tilor sise = (AIm ) ¸si are m linii, m + n coloane ¸si rang(A) e = temului Ax + xa = b este A m < m + n: Bazei ini¸tiale Im care este ¸si primal admisibil¼ a îi corespunde programul xa = b; x = 0: Se aplic¼ a algoritmul simplex modelului extins (2) cu aceast¼ a baz¼ a ini¸tial¼ a. Dac¼ a se ajunge la o solu¸tie optim¼ a a modelului extins, f¼ ar¼ a ca toate variabilele arti…ciale s¼ a aib¼ a valori nule în aceast¼ a solu¸tie, atunci modelul (1) este imposibil. In cazul în care dup¼ a prima faz¼ a valoarea func¸tiei obiectiv este zero, ultima baz¼ a (cea optim¼ a pentru modelul (2)) se foloseste ca baz¼ a ini¸tial¼ a pentru (1). Problema 2 . S¼ a se rezolve problema: 8 sup(5x1 + 5x2 + 4x3 ) > > > > < x1 + x2 + x3 + x4 = 60 2x1 + x2 + 3x3 x5 = 90 > > x2 + 2x3 x6 = 40 > > : xi 0; i = 1; 6

Rezolvare Matricea A corespunz¼ atoare acestui sistem de restric¸tii con¸tine un singur vector unitar a4 = (1 0 0)T : Pentru a face ca în matricea sistemului de restric¸tii s¼ a apar¼ a ¸si ceilal¸ti doi vectori unitari, introducem variabilele arti…ciale xa7 ¸si xa8 în a doua ¸si respectiv a treia restric¸tie: 2

Problema devine: 8