Primele soluții de algoritm Gomory probleme complet întregi

13.3.1 Primele soluții de Gomory algoritm probleme complet întregi

Să considerăm o problemă complet întreg liniar de programare (13,4) - (13,7) în care n1 = n.

Să - programul de sprijin optim al problemei pe întreg. Dacă acestea sunt toate numere întregi, atunci. Dacă cel puțin una dintre coordonatele, de exemplu. Acesta nu este un număr întreg, vom proceda după cum urmează.

Să N Notăm mulțimea de variabile nonbasic și exprimă funcția obiectiv și toate variabilele din punct de vedere al variabilelor nonbasic pe baza ultimului tabel simplex.

Deoarece - valoare non-număr întreg reprezintă cel mai apropiat întreg care să nu depășească. prin [] (partea întreagă) și determină partea fracționară (<>):<>= -.

Teorema13.5. Să - o soluție fezabilă pentru problema. Apoi, relația

determină tăiere corespunzătoare.

Dovada. Scriem expresia (13.10), sub forma

Folosind expresia (13.11), obținem

Pe baza ipotezelor teoremei privind admisibilitatea rezolvării problemei - ansamblu. Valoarea întregului, prin definiție. Prin urmare, de asemenea, întregul.

Vom dovedi că. Să presupunem că. Acest lucru înseamnă că

Prin definiție, partea fracționară. Prin ipoteză, x - o soluție fezabilă pentru problema. asa. În consecință ,. . Aici. sau ceea ce este același lucru. Deci - nu este un număr întreg, dar este contrar a ceea ce tocmai a fost dovedit. Prin urmare, ipoteza este greșită. Acest lucru dovedește teorema.

Corolar. Orice problemă soluție optimă X (D. F) (D. F), nu este o soluție viabilă la problema nu îndeplinește corect cut-off (13.11).

Dovada. Fie X (D. F) - soluția optimă a problemei (D. F), fracționată. Noi pretindem că nu îndeplinește condiția de cut-off. Optimalitatea planului ar trebui să fie asta. Prin urmare. Având în vedere că, înlocuim în (13.11):

ceea ce contrazice ipoteza.

O problemă importantă este în creștere metoda de tăiere a numărului de restricții suplimentare ca soluții sarcini auxiliare, planuri optime care conțin coordonate non-întregi, adică există o problemă de dimensiune. Gomory propusă tehnica restrânge mărimea numărului considerat extins simplex de masă (n + 2) (k + 1), unde n - numărul de variabile de probleme. k - numărul variabilelor nonbasic. Această tehnică se bazează pe faptul că restricțiile suplimentare (clipping corectă) de interes pentru noi doar ca o modalitate de a reduce soluții noninteger optime și tranziția de la o sarcina la alta. Rețineți că variabila este derivat din bază imediat după introducerea de restricții:

Gomori ilustrează ideea unui exemplu specific.

Exemplu. Complet rezolva problema număr întreg de programare liniară:

Îndepărtând stare integralității, vom rezolva problema prin metoda simplex.

După al II-lea iterație vom obține ultima masa de soluție optimă simplex. Această decizie nu este un număr întreg. Prin urmare, trecerea la sarcinile de construcție. Cu o valoare non-integrală a două linii - prima și a doua. Numărul k ales din starea

În cazul nostru. Apoi, este selectată prima linie pentru a forma o secțiune transversală, și anume, k = 1. Scriem prima secțiune a Gomory:

Deoarece = 1/2 = 7/22 = 1/22, obținem

Transferarea variabilă membru în partea dreaptă și introducând o variabilă sold non-negativ. Obținem secțiune transversală sub forma unei a treia ecuație suplimentară. (13.12)

Atașarea-l la cele două anterioare, am ajuns la problema. Rezolvarea ei poate începe cu tabelul simplex finală pentru. ecuație adăugare (13,12).

În ecuația (13.12) poate fi bază variabilă, dar coeficientul este -1, deci pentru o sarcină din tabela sursă nu este o referință soluție bazică. Deci, trebuie să obțineți soluția de referință inițială.

Aloca o a treia linie suplimentară pentru coloane având în ea elementele pozitive (în acest caz, pentru 3 si 4), se calculează raportul. Dacă există o coloană pentru care min <> Aceasta corespunde liniei selectate, linia de date și coloana selectați ca permite, după care variabila imediat deduse din baza și devine un nou suport de decizie. Dacă nu există nici o astfel de coloană, coloana selectată ca permisivă cu cel mai mic element din rândul selectat și rândul de min <>. După aceea, procesul de conversie este simplex începe de masă.

În acest caz, min <> corespunde coloanei treilea rând selectat. Prin urmare, permițând al treilea rând și a treia coloană, se obține imediat o soluție de referință care simultan și optim :. În ceea ce-l din nou, nu este un număr întreg, apoi se trece la sarcinile de construcție.

secțiunea relevantă din următoarele:

Din moment ce avem noua ecuație patra

Prin introducerea unei variabile de echilibru non-negativ. Obținem secțiunea 4 din ecuațiile suplimentare pentru problema.

După efectuarea iterație am o solutie de suport, care este în același timp optim și întreg. Astfel. .

Să ne dea o interpretare geometrică a soluției. Fig. 13.2 Suprafața construită de soluții fezabile ale problemei și arată determinarea soluției sale optime. În rezolvarea problemei, introduceți prima secțiune a Gomory. Eliminarea variabilelor și folosind ecuațiile originale, obținem. Această inegalitate corespunde liniei de delimitare. tăieturi din domeniu a găsit soluția non-întreg. dar păstrează toate soluțiile întregi.

Pentru noua zona pentru a găsi soluția optimă a problemei; Noi construim o a doua secțiune în tranziția la problema. care, după eliminarea variabilelor de bază și ia forma. În noul domeniu al soluției optime este numărul întreg dorit.

În anumite condiții, este posibil să se dovedească teorema finitudinea primului algoritm Gomory, pe care am stat fără dovezi.

Teorema13.6.Pust set de probleme de planificare optimă este limitată și sunt îndeplinite următoarele condiții:

1) garantează întregimii funcției obiectiv (de exemplu, toate - întregul) și linia funcției obiectiv este luată în considerare atunci când se selectează linia corectă pentru construirea de cut-off:

2) deține cel puțin una dintre următoarele afirmații: a funktsiyaogranichena țintă de mai jos pe. o problemă are cel puțin un plan.

Apoi, primul algoritm Gomory necesită doar un număr finit de iterații mari.