Modele de programare liniară întregi. N.Yu. Kolomarova Rezolvarea problemelor de programare liniară cu numere întregi folosind metoda Gomori

După semnificația unei părți semnificative a problemelor economice legate de problemele de programare liniară, componentele soluției trebuie exprimate în numere întregi, i.e. fi întreg. Acestea includ, de exemplu, probleme în care variabilele înseamnă numărul de unități de produse indivizibile, numărul de mașini la încărcarea echipamentelor, numărul de nave atunci când se distribuie pe linii, numărul de turbine din sistemul de alimentare, numărul de calculatoare. în complexul de control și multe altele.

Problemă de programare cu numere întregi liniare este formulat astfel: găsi o astfel de soluție (plan) eu, pentru care funcţia liniară

ia valoarea maximă sau minimă sub restricții

(8.2)

(8.3)

- numere întregi. (8,4)

Trebuie remarcat că problema clasică de transport și alte probleme de tip de transport oferă „automat” o soluție la problema în numere întregi (dacă, desigur, parametrii condițiilor sunt întregi). Totuși, în cazul general, condiția întregului (8.4), adăugată problemelor obișnuite de programare liniară, complică semnificativ soluția acesteia.

O serie de metode sunt utilizate pentru a rezolva probleme de programare liniară cu numere întregi. Cea mai simplă dintre ele este metoda obișnuită de programare liniară. Dacă componentele soluției optime nu sunt întregi, ele sunt rotunjite la cel mai apropiat număr întreg. Această metodă este utilizată atunci când o singură unitate a unei populații constituie o mică parte din volumul întregii populații. În caz contrar, rotunjirea poate duce la o soluție întreagă care este departe de a fi optimă, așa că se folosesc metode special dezvoltate.

Metodele de optimizare a numărului întreg pot fi împărțite în trei grupe principale: a) metode de tăiere; b) metode combinatorii; c) metode aproximative. Să aruncăm o privire mai atentă asupra metodelor de tăiere.

Metode de tăiere. metoda Gomori

Esența metodelor de tăiere este că problema este mai întâi rezolvată fără condiția integer™. Dacă planul rezultat este întreg, problema este rezolvată. În caz contrar, se adaugă o nouă constrângere la constrângerile sarcinii cu următoarele proprietăți:

• trebuie să fie liniară;
• ar trebui să întrerupă planul non-întreg optim găsit;
• nu ar trebui să întrerupă niciun plan întreg.

O constrângere suplimentară cu aceste proprietăți este numită tăierea corectă.

Din punct de vedere geometric, adăugarea fiecărei constrângeri liniare corespunde trasării unei linii drepte (hiperplan) care decupează o parte a acesteia din poligonul soluție (poliedru) împreună cu punctul optim cu coordonate non-întregi, dar nu afectează niciunul dintre numerele întregi. punctele acestui poliedru. Ca rezultat, noul poliedru de soluție conține toate punctele întregi conținute

în poliedrul original de soluții și, în consecință, soluția optimă obținută cu acest poliedru va fi întreagă (Fig. 8.1).

Unul dintre algoritmii de rezolvare a problemei de programare cu numere întregi liniare (8.1)-(8.4), propuși de R. Gomori, se bazează pe metoda simplex și folosește o metodă destul de simplă pentru construirea unui cutoff corect.

Fie ca problema de programare liniară (8.1)-(8.3) să aibă un optim final, iar la ultimul pas de rezolvare prin metoda simplex obținem următoarele ecuații care exprimă principalele variabile prin variabile non-principale ale soluției optime:

(8.5)

deci soluția optimă a problemei (8.1)-(8.3) este i, în care, de exemplu, β; – componentă non-întreg. În acest caz, se poate dovedi că inegalitatea formată de eu- la ecuația sistemului (8.5), are toate proprietățile unei tăieturi regulate.

Pentru a rezolva problema de programare liniară întregi (8.1)-(8.4) folosind metoda Gomori, se folosește următorul algoritm.

• 1. Folosind metoda simplex, rezolvați problema (8.1)-(8.3) fără a lua în considerare condiția întregului. Dacă toate componentele planului optim sunt numere întregi, atunci este și optim pentru problema de programare a întregului (8.1)-(8.4). Dacă prima problemă (8.1)-(8.3) este de nerezolvat (adică nu are un optim final sau condițiile sale sunt contradictorii), atunci a doua problemă (8.1)-(8.4) este și ea de nerezolvat.
• 2. Dacă printre componentele soluției optime există și altele neîntregi, atunci selectați componenta cu cea mai mare parte întreagă și, folosind ecuația corespunzătoare a sistemului (8.5), formați limita corectă (8.6).
• 3. Prin introducerea unei variabile întregi nenegative suplimentare, transformați inegalitatea (8.6) într-o ecuație echivalentă și includeți-o în sistemul de restricții (8.2).
• 4. Rezolvați problema extinsă rezultată folosind metoda simplex. Dacă planul optim găsit este întreg, atunci problema de programare a întregului (8.1)–(8.4) este rezolvată. În caz contrar, reveniți la pasul 2 al algoritmului.

Dacă problema este rezolvabilă în numere întregi, atunci după un număr finit de pași (iterații) se va găsi planul întreg optim.

1 În inegalitatea (8.6) există un simbol ( ), adică partea fracțională a numărului. Parte întreagă a numărului a este cel mai mare număr întreg [în] care nu depășește a, parte fracțională a unui număr– numărul (a), egal cu diferența dintre acest număr și partea sa întreagă, i.e. (a) = a-[b].

De exemplu, pentru (rețineți, exact -3, nu -2) și

Dacă în procesul de rezolvare apare o ecuație (exprimând variabila principală în termeni de cele nebazice) cu un termen neîntreger liber și coeficienți întregi rămași, atunci ecuația corespunzătoare nu are o soluție în numere întregi. În acest caz, această problemă nu are o soluție întreagă optimă.

8.1. Pentru achiziționarea de echipamente de sortare a cerealelor, fermierul alocă 34 de den. unitati Echipamentul trebuie amplasat pe o suprafață care să nu depășească 60 de metri pătrați. m. Fermierul poate comanda două tipuri de echipamente: mașini mai puțin puternice, cum ar fi Aîn valoare de 3 den. unități care necesită o suprafață de producție de 3 mp. m (inclusiv treceri) și o productivitate pe schimb de 2 tone de cereale și mașini mai puternice precum ÎN costa 4 den. unități care ocupă o suprafață de 5 mp. m, și o productivitate pe schimb de 3 tone de cereale de înaltă calitate.

Este necesar să se întocmească un plan optim de achiziție de echipamente care să asigure productivitatea totală maximă, cu condiția ca fermierul să poată achiziționa cel mult 8 utilaje de acest tip ÎN.

Soluţie. Să notăm după numărul de mașini, respectiv tipul AȘi ÎN, prin Z – productivitatea globală. Apoi modelul matematic al problemei va lua forma

(!!!8.8)

cu restrictii:

(8.2)

- numere întregi. (8,4)

Să aducem problema în formă canonică prin introducerea unor variabile suplimentare nenegative. Obținem un sistem de restricții:

(8.5)

Rezolvăm problema folosind metoda simplex. Pentru claritate, ilustrăm soluția grafic (Fig. 8.2).

În fig. 8.2 OKLM– zona de soluții fezabile la problema (8.D)–(8.3"), limitată de linii drepte (1), (2), (3) și axe de coordonate; L(2/3; 8) – punct de soluție optimă, dar neîntreg, a problemei (8,1")–(8,3"); (4) – o linie dreaptă care decupează această soluție neîntregătoare; OKNM– zona de soluții fezabile ale problemei extinse (8.1")–(8.3"), (8.6"); N( 2; 7) – punctul soluției întregi optime.

Pasul I. Variabile de bază Variabile non-bazice

Prima soluție de bază este să presupunem

Ale mele. Valoarea funcției liniare corespunzătoare

Convertim în variabile principale variabila care este inclusă în expresia funcției liniare cu cel mai mare coeficient pozitiv. Găsim valoarea maximă posibilă a variabilei care „permite”

accepta un sistem de restricții bazat pe condiția relațiilor minime corespunzătoare:

acestea. ecuația de rezolvare (evidențiată) este a treia. La X. 2 = 8 în această ecuație X- = 0, iar variabila trece la non-bazic X 5.

Pasul II. Variabile cheie X 2, X 3, X 4.

Variabile minore.g, xy

După transformări obținem

Convertiți în variabila principală iar în cele non-principale x4.

Pasul III. Variabilele principale x, X 2, X 3.

Variabile non-principale x4, x5.

După transformări obținem

Soluție de bază X., optim pentru problema (8.1")–(8.3") (), deoarece în expresia funcției liniare

nu există variabile non-core cu coeficienți pozitivi.

Totuși, soluția X 3 nu satisface condiția întreg (8.4") Folosind prima ecuație cu variabila x care primește o valoare non-întreg în soluția optimă (2/3), creăm o constrângere suplimentară (8.6):

Vă rugăm să rețineți că, conform (8.5) și (8.6), luăm partea fracțională membru liber cu același semn, pe care le are în ecuație și părțile fracționale coeficienți pentru variabile minore x 4 și x- – cu semne opuse.

Deoarece părți fracționale ,

, apoi scriem ultima inegalitate

(8.6")

Prin introducerea unei variabile întregi suplimentare x6 ≥ 0, obținem ecuația echivalentă cu inegalitatea (8.6")

(8.7")

Ecuația (8.7") trebuie inclusă în sistemul de constrângeri (8.5") al problemei canonice inițiale și apoi repetați procesul de rezolvare a problemei folosind metoda simplex în raport cu problema extinsă. În acest caz, pentru a reduce numărul de pași (iterații), se recomandă introducerea unei ecuații suplimentare (8,7") în sistemul obținut la ultimul pas de rezolvare a problemei (fără condiția întregului).

Pasul IV. Variabile cheie X v X 2, x3, χβ.

Variabile non-principale x4, x5.

Soluția de bază nu este permisă

Ale mele. (Rețineți că după includerea unei ecuații suplimentare corespunzătoare limitei corecte în sistemul de constrângeri, se va obține întotdeauna o soluție de bază nevalidă.)

Pentru a obține o soluție de bază admisibilă, este necesară convertirea în variabila principală, care este inclusă cu un coeficient pozitiv în ecuația în care termenul liber este negativ, adică. x sau x. (în acest stadiu nu considerăm o funcție liniară). Traducem în cele de bază, de exemplu, variabila x5.

Pasul V. Variabilele principale sunt x, x2, x3, x5.

Variabile non-principale x4, x6.

Primim după transformări

Deoarece nu există variabile principale cu coeficienți pozitivi în expresia unei funcții liniare, atunci X 5 este soluția optimă.

Deci, Zmax = 25 pentru soluția optimă întreagă X* = X 5 = (2; 7; 19; 0; 1; 0), adică productivitate maximă de 25 de tone de cereale de înaltă calitate pe schimb poate fi obținută prin achiziționarea a 2 mașini de tip L și 7 mașini de tip ÎN Totodată, suprafața neocupată a incintei va fi de 19 metri pătrați. m, soldul fondurilor alocate este zero, rezerva pentru cumpărare este 1 mașină de tip ÎN(a șasea componentă nu are sens).

Cometariu. Pentru interpretarea geometrică pe planul Ox, x2 (vezi Fig. 8.2) al cutoff-ului (8.6"), variabilele incluse în acesta sunt necesare X 4 și X- exprimați prin variabilele x și x2. Obținem (vezi a 2-a și a 3-a ecuație a sistemului de restricții (8.5"))

• (vezi linia de tăiere (4) în Fig. 8.2).
• 8.2. Există un număr destul de mare de bușteni cu lungimea de 3 m Buștenii trebuie tăiați în două tipuri de piese de prelucrat: 1,2 și 0,9 m lungime și trebuie obținute cel puțin 50 și 81 de bucăți din fiecare tip de piesă. respectiv. Fiecare buștean poate fi tăiat în bucățile specificate în mai multe moduri: 1) în 2 bucăți dar 1,2 m; 2) pentru 1 bucată de 1,2 m și 2 bucăți de 0,9 m fiecare; 3) pentru 3 bucăți de 0,9 m fiecare Aflați numărul de bușteni tăiați în fiecare fel, astfel încât să se obțină bucăți de orice tip din cel mai mic număr de bușteni.

Soluţie. Să notăm prin X() x2, x3 numărul de bușteni tăiați folosind 1, 2 și, respectiv, 3 metode. Din ele puteți obține 2xj +x2 blanks de 1,2 m fiecare și 2x x +3x2 spații de 0,9 m fiecare Să notăm numărul total de bușteni Z. Apoi modelul matematic al problemei va lua forma

cu restrictii:

Prin introducerea de variabile suplimentare

reducem sistemul de inegalități la un sistem echivalent de ecuații:

(8.5")

Rezolvând problema canonică rezultată (fără condiția întregului) folosind metoda simplex, la ultimul, al treilea pas al soluției, vom găsi următoarele expresii pentru variabilele principale și o funcție liniară în ceea ce privește variabilele nebazice (noi recomandă elevilor să le obțină singuri).

Pasul III. Variabile cheie X v X 2.

Variabile non-core X la X A , X 5.

adică cu o soluție optimă

Sa dovedit că două componente ale soluției optime nu satisfac condiția întregului (8.4"), iar componenta are cea mai mare parte întreagă X 2. În conformitate cu ∏. 2 algoritmi pentru rezolvarea unei probleme de programare intregi (vezi p. 166) folosind a doua ecuatie care contine aceasta variabila X 2, creăm o constrângere suplimentară (8.6):

Să găsim părțile fracționale

și scrieți ultima inegalitate în formă

(8.6")

Prin introducerea unei variabile suplimentare obținem

ecuație echivalentă cu inegalitatea (8,6"):

(8.7")

Să exprimăm din (8.7") variabila suplimentară x6 și să introducem ecuația rezultată în sistemul de constrângeri pe care l-am avut la ultimul, III, pas de rezolvare a problemei (8.1") - (8.3") (fără condiția numărului întreg). ).

Pasul IV. Variabile cheie X{, X la X 6.

Variabile non-core X 3, x4, X 5.

Rezolvând această problemă extinsă folosind metoda simplex (invităm elevii să o facă ei înșiși), obținem următoarele.

Pasul V. Variabilele principale x); X 2, x3.

Variabile non-principale x4, x5, xb.

adică cu o soluție optimă

Soluția optimă rezultată la problema extinsă (8.1")–(8.3"), (8.6") ​​​​din nou nu satisface condiția întregului (8.4"). Conform primei ecuații cu variabila Xj primind o valoare non-întreg în optim

soluție (), lăsăm a doua limită suplimentară

citire (8.6):

pe care ni le aducem în minte

Folosind o variabilă suplimentară

Reducem această inegalitate la o ecuație echivalentă, pe care o includem în sistemul de constrângeri obținute la ultimul, V, pas de rezolvare a problemei extinse (8.G")–(8.3"), (8.6") ​​folosind metoda simplex.

pasul VI. Variabile cheie X v X 2, X la X T

Variabile non-core X 4, X-, x 6.

Omițând rezolvarea ulterioară a problemei folosind metoda simplex (sugerăm ca elevii să facă acest lucru ei înșiși), la pasul final, VII, pe care îl obținem.

Pasul VII. Variabile cheie X v X t x3, X G

Variabile non-core X v X 6, X T

Deoarece nu există variabile nebazice cu coeficienți negativi în expresia unei funcții liniare, atunci X 7 – soluție întreagă optimă a problemei inițiale.

De remarcat că în expresia rezultată a funcției liniare Z nu există variabile minore X D) și X 6. Aceasta înseamnă că, în general, există o mulțime infinită de soluții optime (orice, nu neapărat întreg), pentru care Z" = Zmjn = 46. Aceste soluții se obțin pentru valoarea variabilei non-principale X 7 (inclus în expresia pentru Z), egal cu zero (adică când X 7 = 0), iar la orice valori ale variabilelor nebaze x5 și X 6 (neinclusă în expresia pentru Z), pe care sistemul de restricții „permite” să fie acceptat: 0<лг5 X 5 ≤ 1 și 0< X(i ≤ 1. Dar datorită condiției întregi, variabilele X-Și X(> poate lua doar valorile 0 sau 1. Prin urmare, problema va avea patru soluții întregi optime când X.și *6 în orice combinație iau valorile 0 sau 1 și X 7 = 0. Înlocuind aceste valori în sistemul de restricții la pasul VII, găsim aceste soluții optime:

Prezența unor soluții întregi optime alternative face posibilă selectarea uneia dintre ele, ghidată de criterii suplimentare care nu sunt luate în considerare în modelul matematic al problemei. De exemplu, din condițiile acestei probleme rezultă că buștenii de tăiat nu produc deșeuri doar folosind metoda a 3-a, deci este firesc atunci când alegeți una dintre cele patru soluții optime să acordați prioritate soluției. X^ 3 la care numărul maxim de bușteni ( X 2 = 41) este tăiat fără deșeuri.

Deci, Zmin=46 pentru soluții întregi optime (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2). La înregistrarea soluțiilor optime am lăsat doar primele trei componente, exprimând numărul de bușteni tăiați conform metodei I, a II-a și, respectiv, a III-a și au exclus ultimele patru componente, care nu au sens semantic.

Dezavantajul metodei Gomori este cerința pentru valori întregi pentru toate variabilele - atât de bază (exprimând, de exemplu, în problema utilizării resurselor unei unități de producție), cât și suplimentare (exprimând cantitatea de resurse neutilizate, care poate fi fracționat).

• Puteți vedea că soluția problemei este mai scurtă.

Pentru a rezolva probleme de programare liniară întregi cu un număr arbitrar de variabile, puteți folosi metoda Gomori, cu ajutorul căreia puncte cu coordonate non-întregi sunt tăiate din zona programului. Să formulăm algoritmul Gomori pentru rezolvarea unei probleme de programare liniară cu numere întregi în formă standard

algoritmul Gomori

GP Folosind metoda simplex găsim programul optim. Dacă obțineți valori întregi pentru toate Xj, atunci problema este rezolvată. Altfel printre Xj există valori nenumerice.

|~2~1 Printre non-numere întregi Xj selectați un element arbitrar x gși adăugați o altă constrângere problemei

ceea ce echivalează cu adăugarea încă un rând la tabelul simplex, după care nu mai corespunde unei soluții de bază admisibile la noua problemă de programare liniară pe care o descrie. Constrângerea folosește părți fracționale ale elementelor liniei în care se află. x g. Notația folosită pentru partea fracțională se bazează pe faptul că fiecare număr real la poate fi reprezentat ca o sumă la = [y]+ (?у), unde [y] -întreaga parte și (y) = U ~ [y] ~ fracțiune.

[h] Găsim o soluție de bază admisibilă, considerând că noua linie se rezolvă, i.e. eu = P + 1.

• a) Dacă toţi coeficienţii uc> 0, atunci problema nu are soluție (adică problema întregului este rezolvată).
• b) În caz contrar, găsiți indicele La astfel încât

(criteriul pentru introducerea unei noi baze). Rețineți că alegerea elementului de rezolvare laȘi* nu schimbă semnul criteriilor Aj.

[4] Dacă noul tabel are cel puțin unul x 3 s și repetați aceste proceduri de câte ori este necesar.

[~5~| Dacă soluția optimă rezultată este întreagă, atunci problema este rezolvată. În caz contrar, trebuie să reveniți la punct.

Exemplul 4.6.1. Rezolvați o problemă cu numere întregi folosind metoda Gomori

Soluţie. După adăugarea variabilelor auxiliare, avem următoarea problemă de programare liniară în formă standard:

cu matrici

tabelul 1
	X4

La= 1 T

Folosind metoda rotației, completați următoarele tabele. Element de rezoluție - 6*.

masa 2				X 2
		„ _ 1 ȘIZ ~_3_

k" = 2 T

Element de rezoluție - 1/2*.

X în^0). Prin urmare, programul (xi = 11/3, X 2 = 5) va da maximul funcției economice z, egal cu 1370/3 = 45b|, t.s. z= z max = 456§. "

Deoarece acest program optim nu este unul întreg, aplicăm algoritmul lui Gomori pentru a găsi un program optim întreg. Ca o linie pe baza căreia formăm o linie suplimentară din părțile fracționale ale tuturor elementelor, selectăm a doua linie (indice 7’ = 1). Să completăm tabelul 3", adăugând la tabelul 3 un rând suplimentar (4.14) cu părți fracționale pentru variabila suplimentară Ж5 și o coloană suplimentară. Obținem

k" = 4 T

După adăugarea unei noi linii, tabelul simplex 3" nu mai corespunde unei soluții de bază admisibile problemei pe care o descrie. Găsim o soluție de bază admisibilă, considerând că noua linie se rezolvă, adică /" = 5.

Găsim coloana rezoluție, i.e. index La" astfel încât

(criteriul pentru introducerea unei noi baze). Element de rezoluție - (-2/3*). Rețineți că o astfel de alegere a unui element de rezolvare nu schimbă semnul criteriilor Aj.

Să completăm tabelul simplex 4.

Tabelul 4				X2
	X2

Valorile tuturor criteriilor ^ 0, ( X în^0). Prin urmare, programul (xi = 3, x 2 = 6, x±= 1) dă maximul funcției economice r egal cu 450, t.s. z = zma^= 450. Acest program optim este un număr întreg. ?

Exemplul 4.6.2. Rezolvați o problemă cu numere întregi folosind metoda Gomori

Soluţie. Există o problemă de programare liniară cu matrice

Să completăm tabelul simplex cu programul inițial.

tabelul 1

La= 1 T

Folosind metoda rotației, completați următoarele tabele. Element de rezoluție - 1*.

masa 2				X2

Element permisiv - 5*.

Tabelul 3

Valorile tuturor criteriilor ^ 0, ( X în^0). În consecință, programul (xi = 12/5, 24 = 1/5, 25 = 28/5) dă minimul funcției economice r egal cu -11/5 = -2,2, adică. z =

~min = -2.2.

Deoarece acest program optim nu este unul întreg, aplicăm algoritmul lui Gomori pentru a găsi un program optim întreg. Ca șir pe baza căruia formăm un șir suplimentar din părțile fracționale ale elementelor ss, selectăm, de exemplu, al treilea rând (indice r = 5) cu partea fracțională maximă. Să completăm tabelul 3" adăugând o linie suplimentară (4.14) la tabelul 3 cu părți fracționale din a treia linie pentru variabila suplimentară xq (această linie vă permite să tăiați din zona programului părți care conțin puncte cu coordonate nenumerice) și o coloană suplimentară. Primim

Tabelul 3"
		G - -ȘI

k" = 3 T

După adăugarea unei noi linii, tabelul simplex 3" nu mai corespunde unei soluții de bază admisibile a problemei pe care o descrie. Găsim o soluție de bază admisibilă, considerând noua linie ca fiind rezolvatoare, i.e. eu" = 6.

Găsim coloana de rezolvare, i.e. index La" astfel încât

(criteriul pentru introducerea unei noi baze). Element de rezoluție - (-3/5*). Rețineți că o astfel de alegere a unui element de rezolvare nu schimbă semnul criteriilor Aj.

Să completăm tabelul simplex 4.

Tabelul 4

Valorile tuturor criteriilor ^ 0, ( X în^0). Prin urmare programul (x = 2, X2 = 0, xs = 1, X 4 = 0, f 5 = 5) va da minimul funcției economice z 9 egal cu (-2), c.t. z =-min = - 2. Acest program optim este un număr întreg. ?

Problema 4.6.1. Rezolvați o problemă cu numere întregi folosind metoda Gomori

Răspuns. Program

dă un minim al funcției economice z egal cu (-31), adică. z= 2 m i n = -31. Acest program optim este unul întreg.

Introducere

O clasă mare de probleme de optimizare aplicate se reduce la probleme de programare liniară întregi. Pentru a rezolva aceste probleme, sunt utilizate pe scară largă metodele de tăiere, concepute pentru a rezolva o problemă generală cu numere întregi, potrivindu-o cu o problemă neîntregeră, a cărei soluție permite găsirea unei soluții.

Prima metodă pentru rezolvarea unei probleme de programare liniară întregă prin tăiere a fost propusă de Gomori și a fost numită algoritmul Gomori.

1. Enunțarea problemei

Metoda Gomori este concepută pentru rezolvarea problemelor de programare liniară cu numere întregi. Când luăm în considerare metoda Gomori, vom rezolva această problemă în formă canonică.

1.1 Forma canonică

Vom lua în considerare problema programării întregi canonice cu n variabile şi m condiții, completate de condiția întreg:

Unde c = (c 1 , c 2 , … , c n), x = (x 1 , x 2 , … , x n)- vector de dimensiune n, - produsul lor scalar (), numit și funcție obiectiv, A- matricea dimensiunilor n´ m, b- vector coloană de dimensiune m.

Condiția întregului complică semnificativ problema de programare liniară (1.1), (1.2). Se poate întâmpla ca problema (1.1)-(1.3) să aibă planuri admisibile (întregi), funcția obiectivă să fie limitată la mulțimea admisibilă, dar maximul acesteia să nu fie atins. De exemplu, în sarcină:

nu există soluții întregi, în timp ce fără această condiție, orice vector al formei poate servi ca soluție

.

În legătură cu cele de mai sus, la justificarea algoritmilor numerici pentru rezolvarea problemelor de tip (1.1)-(1.3), este necesar să se impună diferite condiții suplimentare Presupunem că mulțimea X planurile problemei (1.1), (1.2) (fără condiția întregului) este mărginită, adică este un poliedru.

Din această condiţie rezultă că setul X* toate planurile întregi ale problemei (1.1)-(1.3) sunt finite. Vom presupune că toți coeficienții c j, j=1, 2 , …, n, funcțiile țintă sunt numere întregi.

Din condiția II rezultă că pentru orice plan întreg XÎ X* sens<c, X> forma liniară de maximizat - un număr întreg. În acest caz, spunem că integritatea funcției obiectiv este garantată.

Deși condițiile I și II pentru problema (1.1) - (1.3) sunt destul de stricte, este posibil să le slăbiți doar puțin pentru a obține rezultatele necesare.

1.2 Reducerea la forma canonică

Problema programării liniare întregi poate fi formulată oarecum diferit decât a fost prezentată mai sus. Deci, de exemplu, în loc de condiția (1.2), poate exista o altă formă de restricții de scriere

Putem trece de la o astfel de notație la (1.2) adăugând o nouă variabilă la fiecare ecuație, apoi restricțiile vor lua forma

Variabilele adăugate vor avea pondere zero în funcția obiectiv.

De observat că pentru a obține, în funcție de tipul inegalității, nu trebuie doar să adunăm, ci și să scădem o variabilă în funcție de semnul inegalității, ținând cont de condiția (1.3).

Dacă în problema inițială nu pentru o variabilă x i condiția de pozitivitate nu este îndeplinită, atunci ar trebui înlocuită cu diferența a două variabile noi, pozitive.

2. Idei generale despre metodele de tăiere

Există o posibilitate fundamentală de a reduce soluția problemei (1.1) - (1.3) la găsirea planului optim pentru o problemă de programare liniară (fără condiția ca variabilele să fie întregi). Lăsa X- o multime poliedrica definita de conditiile (1.1), (1.2). Prin X* notează mulțimea tuturor vectorilor întregi X*, întins înăuntru X. Cu alte cuvinte X* este dat de condițiile (1.1)-(1.3), adică

A-prioriu X*Í X. Vom nota prin X z carcasă convexă a ansamblului X*. Apoi X zÍ X.

Astfel, am asociat multimii poliedrice X o multime convexa X zÍ X conform următoarei reguli: X z este mulțimea convexă minimă care conține toți vectorii întregi din X.

Conform Ipotezei I, X este un poliedru, de unde mulțimea X* Cu siguranță. Apoi mulțimea convexă X z este, de asemenea, un poliedru și, prin urmare, avem asta X z poate fi specificat printr-un număr finit de inegalități liniare.

Pentru a evidenția principala diferență dintre set X z din multi X, să dăm următoarea definiție.

Definiția 1. Un poliedru ale cărui puncte extreme sunt numere întregi (adică toate coordonatele lor sunt numere întregi) se numește poliedru întreg.

Evident, poliedrul X z- întreg, deoarece punctele sale extreme sunt doar puncte ale mulțimii X* planuri întregi.

Justificare pentru studierea conformității X® X z este următorul fapt simplu.

Teorema 1. Orice plan de referință optim pentru o problemă de programare liniară este o soluție a problemei (1.1)-(1.3).

Dovada. Să` X*- planul optim de referință al problemei (2.1), X*- o soluție la problema inițială (1.1)-(1.3). ` X*Î X zÍ X, Acea

<c,`X*> £ <c, X*>.

Pe de altă parte, din moment ce X* este un plan întreg, atunci X*Î X*Í X z, prin urmare

<c,`X*> ³ <c, X*>,

Unde

<c,`X*> = <c, X*>.

Dovada teoremei este completă.

Subliniem faptul că Teorema 1 precizează doar posibilitatea fundamentală de reducere a soluției unei probleme de programare liniară întregă la căutarea planurilor de referință ale unei probleme de programare liniară de forma (2.1). Principala dificultate în utilizarea acestei caracteristici este definiția explicită a poliedrului X z sistem de inegalități liniare pentru a aplica apoi metode numerice de programare liniară pentru a rezolva problema (2.1). Este probabil ca această problemă să fie la fel de dificilă din punct de vedere computațional ca problema inițială de a găsi designul întreg optim.

În ciuda acestui fapt, ideea de a „îngusta” setul X s-a dovedit a fi utilă și a condus la crearea mai multor algoritmi pentru rezolvarea problemelor de programare liniară cu numere întregi, numiți „metode de tăiere”.

Să prezentăm ideea metodelor de tăiere. Să presupunem că am reușit să construim șirul ( Lr}, r = 0, 1 , 2 , ..., probleme de programare liniară, fiecare dintre acestea fiind determinată de propriul poliedru Xrși o singură funcție obiectivă pentru toți<c, X>:

În plus, această secvență de sarcini are următoarele proprietăți:

) X 0 =X, adică la fel de X 0 luați setul de planuri pentru problema (1.1), (1.2);

) X r z = X z , r=1,2, …;

) dacă la rezolvarea unei probleme Lr vectorul optim rezultat x r * nu satisface condiția întregului, atunci nu este un plan de sarcini L r+1, adică x r *Ï X r+1.

Rețineți că dacă la un pas r vector x r *- rezolvarea problemei Lr- sa dovedit a fi un număr întreg, atunci este o soluție la problema inițială (1.1)-(1.3) datorită proprietății 2) a șirului Lr.

Este intuitiv clar că construcția secvențială a sarcinilor Lr, r=1,2,..., dă într-un sens o aproximare a mulțimii X z cu ajutorul multora Xr.

Metode pentru construirea unei secvențe ( Lr), asigură caracterul finit al procesului de rezolvare a problemei (1.1)-(1.3), au fost propuse pentru prima dată de Gomori.

3. Descrierea metodei Gomori

Să luăm acum în considerare algoritmul Gomori pentru rezolvarea problemelor de programare liniară întregi. Această metodă aparține metodelor de tăiere și pune în aplicare ideile prezentate în paragraful anterior.

3.1 Conceptul de tăiere corectă și cel mai simplu mod de a o construi

Algoritmul lui Homer de programare liniară

Să introducem limita corectă, care stă la baza multor metode numerice pentru rezolvarea problemelor de programare liniară întregi.

Definiția 2. Fie x* planul optim pentru problema (1.1), (1.2), care nu este un întreg. Inegalitate

unde g = (g 1 , g 2 , …, g n), se numește tăietură corectă dacă îndeplinește cerințele:

a) pentru un vector X* inegalitatea nu se menține, adică X*>>g 0 (condiție de întrerupere).

b) dacă X este planul întreg al problemei (1.1), (1.2) (adică planul problemei (1.1)-(1.3)), atunci X- satisface (3.1) (condiția de corectitudine).

Este clar că adăugarea inegalității (3.1) la condițiile (1.1), (1.2) restrânge mulțimea admisibilă X, păstrând în același timp toate punctele sale întregi. Astfel, aplicarea consecventă a acestei tehnici oferă o aproximare în mai multe etape a poliedrului X z folosind constrângeri liniare.

Există două probleme cu conceptul de tăiere adecvată. Prima dintre acestea este formularea unui algoritm general de tăiere pentru o problemă de programare liniară cu numere întregi arbitrare. A doua problemă este de a construi o limită corectă în așa fel încât să se asigure rezolvarea problemei (1.1)-(1.3) într-un număr finit de pași, i.e. astfel încât din mulţime X de fiecare dată când erau tăiate suprafeţe suficient de mari.

Rețineți că a doua cerință este destul de subtilă. Ca confirmare, luați în considerare metoda de construire a unui cutoff corect propusă de Danzig.

Lăsa X*- susținerea planului optim al problemei (1.1), (1.2), s și w - liste de numere de variabile de bază, respectiv nebaze, corespunzătoare unor baze ale planului X*. Apoi x j *= 0 la jÎw. Ținând cont de această proprietate, nu este dificil să construiți o limită corectă pentru proiectul x* dacă nu este un număr întreg: inegalitatea poate servi ca atare

Într-adevăr, condiția cutoff este satisfăcută trivial, deoarece . Condiția de corectitudine este de asemenea îndeplinită, întrucât dacă x = (x 1,x 2 , …,x n) este planul întreg al problemei (1.1), (1.2), apoi valoarea ținând cont de condițiile x j ³ 0, jÎ w, poate fi mai mic decât unitate numai în cazul în care x j= 0 pentru toate jÎ w. Dar în acest caz planul X- referință, iar baza planului poate fi luată ca bază X*. Planul de referință este determinat în mod unic de baza sa, din care obținem că inegalitatea implică x=x *. Acesta din urmă este însă imposibil, deoarece X este un vector întreg și X* nu este.

Această metodă de construire a unei tăieturi corecte, în ciuda simplității sale, s-a dovedit a fi ineficientă, deoarece caracterul finit al procesului de soluție este asigurat numai pentru o clasă restrânsă de probleme de programare liniară întregi.

Să descriem metoda de construire a unui cutoff corect propusă de Gomori. Pentru un număr arbitrar A, prin [ A] vom desemna întreaga sa parte, i.e. [ A] este cel mai mare număr întreg k numar nedepasitor A.

Parte fracțională ( A) numere A numit numărul ( A} = A - [A]. Să notăm proprietatea evidentă a părții fracționale a unui număr arbitrar: 0 £ ( A}<1, причем {A) = 0 dacă și numai dacă A - un număr întreg.

Lăsa X*- soluția de referință a problemei (1.1), (1.2), care nu este întreg, - baza sa si B- tabelul simplex corespunzător sub formă de coordonate.

Să luăm în considerare sistemul redus de ecuații corespunzător acestei baze (și tabelul B) plan

X*:

Deoarece x j *= 0 la jÎw, atunci numai cantitățile pot fi neîntregi x 0 * = <c, X*>, x i *, i Este.

Lăsa s- un astfel de indice (0 £ s £ n) că numărul xs*- nu întreg. Sa luam in considerare s al-lea rând dintr-un tabel simplex B (s ecuația din sistemul (3.2), (3.3)) și compuneți expresia

Teorema 2. Dacă XÎ X* este planul întreg al problemei (1.1), (1.2), atunci

Dovada. Folosind relația

Asj = [Asj] + {Asj }, j = 0, 1, 2, … , n, din (3.3) cu i= s primim

Unde

Partea stângă a acestei inegalități conține un număr întreg, deci numărul

de asemenea intregi. De la ce x j ³ 0, jÎw, folosind proprietatea părții fracționale, obținem

acestea. - z s(X) < 1, или z s(X) > -1. Având în vedere că z s(X) - întreg, vom accepta în sfârșit z s(X) ³ 0.

Consecinţă. Dacă xs*(= As0) - număr non-întreg și Set X* planurile problemei întregi (1.1)-(1.3) sunt nevide, apoi printre numerele ( Asj}, j=1, 2, …, n, sunt pozitive.

De fapt, toate numerele ( Asj), sunt evident non-negative. Să presupunem că ( Asj} = 0, j = 1, 2, …, n.

Dacă X* negol şi X* Î X*, Acea z s(X*)= - {As0), acea z s(X*) este un număr întreg, deoarece 0< {As0} < 1.

Cometariu. În demonstrarea teoremei 2, am folosit ipoteza II că funcția obiectiv este garantată a fi întreagă. Valabil în caz s= 0 valoare

este întreg (cu condiția ca XÎ X*) numai când numărul x 0 = < c, X> - întreg.

Din aceasta rezultă

Teorema 3. Dacă numărul xs*- nu este un întreg, atunci inegalitate

este limita corectă.

Dovada. Să verificăm condiția cutoff din Definiția 2. Deoarece xs* = As0, apoi din faptul că xs*- nu este un număr întreg, obținem inegalitatea ( As0) > 0. Din moment ce x j *= 0 la jО w, atunci

şi deci vectorul X* nu satisface inegalitatea (3.5). Condiția de corectitudine rezultă din enunț z s(X) ³ 0 în teorema 2.

3.3 Primul algoritm al lui Gomory

Să trecem la prezentarea primului algoritm Gomori.

Să notăm problema (1.1), (1.2) prin L 0 . Gomori a propus să găsească maximul lexicografic al problemei în prima etapă a algoritmului său L 0 . Vom nota prin

X(0) = (X 0 (0), X 1 (0), …, X n(0))

vector (n+1)-dimensional astfel încât ( X 1 (0), X 2 (0), …, X n (0)) - rezolvarea problemei lexicografice L 0, a X 0 (0) = - valoarea formei liniare. În cazurile în care acest lucru nu provoacă neînțelegeri, vom suna X(0) - plan optim pentru problema lexicografică L 0 (deși conform terminologiei general acceptate, un plan este un vector compus din ultimul n coordonate vectoriale X(0)).

De asemenea, rețineți că X(0) va fi un plan de referință, precum și un pseudoplan strict admisibil al problemei L 0 .

Dacă x(0) este un vector întreg, atunci este evident o soluție la problema (1.1) - (1.3).

În caz contrar, găsim indicele minim s, 0 £ s £ n, pentru care valoarea xs(0) nu este un număr întreg. Lăsa B(0) - tabel simplex sub formă de coordonate corespunzător vectorului X(0). Utilizarea coeficienților s al treilea rând al acestui tabel (adică coeficienții sistemului redus (3.2), (3.3)), folosind tehnica descrisă mai sus, se construiește limita corectă.

Se introduce o variabilă auxiliară x n+1 și sarcina este luată în considerare L 1:

Următoarea etapă este găsirea maximului lexicografic al problemei L 1 . Un avantaj important al algoritmului Gomori este faptul că pseudo-planul strict admisibil inițial pentru aplicarea metodei dual simplex la problemă L 1 se găsește fără dificultate. Într-adevăr, este ușor de observat că, ca atare pseudoplan, putem lua vectorul

De fapt, este evident că y(1) satisface (împreună cu vectorform X(0)) restricții (3.6), (3.7) probleme L 1 și doar una dintre restricțiile (3.8) este încălcată: x n+1 (0)= - (a s 0 } < 0. Кроме того, y(1) este referința pentru sistemul de ecuații (3.6), (3.7), deoarece dacă - baza de plan X(0) apoi sistemul

este liniar independentă și servește drept bază pentru y(1). Să arătăm asta y(1) este un pseudoplan strict admisibil. În acest scop, vom construi un tabel simplex corespunzător bazei vectoriale specificate y(1). Pentru a face acest lucru, trebuie doar să adăugați mai jos la tabel B(0) linie

Unde w = ( j 1 , j 2 , …, jn -m) - listă de numere de variabile nebaze corespunzătoare tabelului B(0) plan de referință X(0). Deoarece X(0) este un pseudoplan strict admisibil, atunci fiecare coloană b j, jÎw, mese B(0) pozitiv lexicografic: b j > 0, jÎw. De aici rezultă că în tabelul simplex sub formă de coordonate corespunzătoare vectorului suport y(1), fiecare coloană (cu excepția primei, care coincide cu y(1)) este pozitiv din punct de vedere lexicografic:

Astfel, având la dispoziție o soluție X(0) sarcină lexicografică L 0 și tabelul simplex corespunzător sub formă de coordonate B(0), fără calcule suplimentare găsim pseudoplanul inițial strict admisibil y(1) pentru sarcină L 1 și construiți tabelul simplex corespunzător sub formă de coordonate.

Se poate întâmpla ca sarcina lexicografică L 1 nu are solutie. În acest caz, soluția problemei numerelor întregi (1.1) - (1.3) ar trebui oprită deoarece

Teorema 4. Dacă în problemă L 1 nu există maxim lexicografic, apoi multimea X* punctele întregi ale problemei (1.1) - (1.3) sunt goale.

Dovada. Din moment ce multi X vectori care îndeplinesc condiţiile Topor = b, X³ 0, conform ipotezei I este mărginit, atunci setul de planuri pentru problemă este, de asemenea, mărginit L 1 . Prin urmare, singurul motiv pentru care această problemă poate să nu aibă un minim lexicografic este că setul său de planuri este gol. Să arătăm că în acest caz setul X*, de asemenea, gol.

Să presupunem contrariul, adică. Ce X* ¹ Æ, și lasă X* = (X 1 * , X 2 * , …, x n*) О X*. Prin teorema 2 aflăm că cantitatea

nenegativ. Dar asta înseamnă că vectorul = ( X 1 * , X 2 * , …, x n * , x n+1 *) este planul de sarcini L 1, în contradicție cu cele de mai sus. Teorema a fost demonstrată.

Lăsa X(1) = (X 0 (1), X 1 (1), …, x n(1), x n+1 (1)) - rezolvarea problemei lexicografice L 1 . Plecând de la sarcină L 1 și vector X(1), problemele sunt construite într-un mod similar Lr, r= 2, 3, … și soluții X(r) Î Â n +1+r sarcinile lexicografice corespunzătoare.

Rețineți că algoritmul lui Gomori determină în mod unic secvența X(r), r= 0, 1, 2, …, care rezultă din unicitatea alegerii s. Să fim atenți și la faptul că indicele sîntotdeauna nu depășește n: 0 s n. De fapt, dacă totul x j(r) la j= 0, 1, 2, …, n sunt numere întregi, atunci din teorema 2 rezultă că x n +1 (r), x n +2 (r), … - de asemenea numere întregi.

Dacă la un pas r vector

X(r) = (X 0 (r), X 1 (r), …, x n(r), …, x n +r (r))

se dovedește a fi un număr întreg, apoi vectorul ( X 0 (r), X 1 (r), …, x n(r)) este o soluție la problema (1.1) - (1.3). Dovada acestei afirmații este evidentă.

Tranziție de la vector X(r) la vector X(r+1) folosind algoritmul Gomori descris se numește o iterație mare, spre deosebire de iterațiile intermediare ale metodei dual simplex, care sunt numite mici.

Principala întrebare legată de primul algoritm al lui Gomori este: este întotdeauna posibil să se obțină un vector întreg într-un număr finit de iterații mari? X(r).

Să demonstrăm caracterul finit al primului algoritm Gomory. Vom folosi următoarea notație:

X(0) = (X 0 (0), X 1 (0), …, x n(0));

Unde ( X 1 (0), …, x n(0)) este soluția problemei lexicografice L0, și X(0) = - valoarea corespunzătoare a formei liniare (funcția obiectivă).

y(1) = (X 0 (0), X 1 (0), …, x n(0), x n +1),

vectorul y(1) servește ca pseudoplan inițial strict admisibil la rezolvarea problemei L1 folosind metoda dual simplex sub formă de coordonate: ` y(1) = (`y 0 (1), `y 1 (1), …, `y n(1), `y n+1 (1)) este vectorul rezultat din y(1) ca rezultat al primei (mici) iterații a metodei dual simplex în formă de coordonate.

Notația este introdusă în mod similar

X(r), y(r + 1), `y(r + 1), r = 1, 2, …

Din proprietățile metodei dual simplex în formă de coordonate rezultă

y(r) >`y(r) ³ X(r).

Lema 1. Lăsa s- indicele minim pentru care numărul xs(0) nu este un întreg. Apoi

Dovada. Deoarece din (3.9) rezultă y(1) >`y(1), atunci sunt posibile două cazuri:

În cazul 1, enunțul lemei este satisfăcut trivial de definiția ordinii lexicografice.

Luați în considerare cazul 2. Conform regulilor metodei dual simplex, la prima (mică) iterație de rezolvare a problemei L 1 variabilă este supusă derivării dintre cele de bază x n+1 deoarece în vector y(1) x j(0) ³ 0, jО w, x n +1 < 0. Пусть kО w este un indice astfel încât

Pentru oricine jО w, dacă -(a sj} < 0. По правилам симплексного метода в число базисных вводится переменная x k.

Cazul 2 este posibil numai în condiția b ik = 0, i = 0, 1, 2, …, s- 1. Pentru că X(0) - pseudo-plan strict admisibil al sarcinii L 0, apoi toate coloanele sale b j, jО w, tabel simplex B(0) pozitiv lexicografic; în special b k> 0 . Prin urmare, coordonata b sk din această coloană trebuie să fie nenegativă. Rețineți că b sk=a sk(adică 0 £ s £ nȘi sО w), prin condiția (3.10) numărul a sk- nu zero. De aceea

A sk> 0 și a sk³ (a sk}

Conform formulei de transformare a tabelului simplex, avem

Reținând că xs(0) = as0, obținem:

.

Ținând cont de (3.11), obținem următoarea estimare:

Lema este dovedită.

Cometariu. Dacă problema inițială (1.1) - (1.3) este admisibilă, atunci, conform corolarului teoremei 2, indicele k satisface condiția (3.10) există.

Consecinţă. Raport corect

Valabil la r= 1, această inegalitate rezultă din lemă și a doua inegalitate (3.9). Pentru a obține această declarație pentru un arbitrar r, trebuie să profitați de faptul că y j(r) = x j(r) la 0 £ j £ n, și inegalitatea y(r) ³ X(r) în (3.9).

Teorema 5. Dacă ipotezele I și II sunt îndeplinite, atunci primul algoritm al lui Gomori necesită doar un număr finit de iterații mari.

Pentru a verifica adevărul teoremei, este necesar să arătăm că pentru unii r vector X(r) = (X 0 (r), X 1 (r), …, x n +r (r)) - număr întreg. Pentru a face acest lucru, la rândul său, este suficient să demonstrăm natura întreagă a vectorului ( X 0 (r), X 1 (r), …, x n(r)), deoarece din teorema 2 rezultă că toate numerele x n +1 (r), x n +2 (r), …, x n +r (r) sunt de asemenea întregi. De asemenea, reamintim că indicele minim s pentru care numărul xs(r) nu este întreg nu depășește întotdeauna n: 0 £ s £ n. Înainte de a trece la demonstrația principală, demonstrăm următoarea lemă:

Lema 2. Pentru oricine j, 0 £ j £ n, există un astfel de număr Rj, că la r ³ Rj toate numerele x j(r) - numere întregi și egale cu același număr întreg x j(Rj).

Dovada. Lăsa s, 0 £ s £ n, - indicele minim pentru care afirmația Lemei nu este valabilă. Să notăm

În cazul când s= 0, să punem R = 0.

Lăsa r, l- astfel de indici care R £ r£ l, și numere xs(r), xs(l) - nu întreg. Să arătăm că atunci [ xs(r)] > [xs(l)]. Valabil prin definiție s avem

În acest caz s- indicele minim pentru care numărul xs(r) - număr întreg. Prin corolar lemei 1 avem [ xs(r)] ³ xs(l).

Având în vedere că xs(l) nu este un număr întreg, avem xs(l) > [xs(l)], din care obținem afirmația dorită. Din moment ce multi X planurile problemei (1.1) - (1.3) este limitată, atunci orice valoare este limitată xs(r), 0 £ s £ n, r= 1, 2, … . Prin urmare, un lanț infinit de inegalități de forma [ xs(r)] > [xs(l)] > ... nu poate exista și, prin urmare, în succesiune xs(r), r= 0, 1, …, nu poate exista un număr infinit de numere care nu sunt întregi. În mod similar, este dovedit că nu pot exista infinite numere întregi diferite în această secvență.

Lema este dovedită.

Să revenim la demonstrarea teoremei. Lăsa

unde sunt numerele Rj apar în formularea Lemei 2. Apoi, conform acestei leme, toate numerele x j(R), 0 £ j £ n, - întreg. Din teorema 2 obținem că vectorul X(R) - număr întreg. Prin urmare, algoritmul lui Gomory nu necesită mai mult de R iterații.

Teorema a fost demonstrată.

3.5 Note privind implementarea practică a primului algoritm Gomori

În implementarea practică a primului algoritm Gomori, o problemă importantă este creșterea numărului de restricții, ceea ce duce la creșterea dimensiunii tabelelor simplex. Gomori a propus o modalitate de a elimina acest dezavantaj al algoritmului, care este după cum urmează.

) În timpul rezolvării problemei Lr folosind metoda dual simplex, la fiecare iterație mică, ar trebui să utilizați o regulă rafinată de inferență din numărul de vectori de bază pentru a rezolva probleme de programare liniară folosind metoda simplex: dacă prima coloană a tabelului simplex are mai multe elemente negative b i 0 (= x i), i =1, 2, …, n, …, n + r, atunci variabila cu numărul minim trebuie eliminată dintre cele de bază.

) Dacă în timpul următoarei mici iterații la implementarea sarcinii Lr toate variabilele principale X 1 , X 2 , …, x n s-a dovedit a fi nenegativ, apoi aplicarea ulterioară a metodei dual simplex la problemă Lr ar trebui oprit, în ciuda faptului că maximul său lexicografic este posibil să nu fi fost încă atins. Dacă toate variabilele x j, j = 1, 2, …, n, sa dovedit a fi întreg, apoi după Teorema 2 toate variabilele auxiliare x n +k , k = 1, 2, …, r, sunt întregi și nenegative. Aceasta înseamnă, după cum se știe deja, că vectorul ( X 0 , X 1 , X 2 , … , x n) este o soluție a problemei întregi inițiale. În caz contrar, trecem la o nouă iterație mare.

) Rând de tabel simplex corespunzător variabilei auxiliare x n +r, este eliminat de îndată ce variabila x n +r este declarată nebază. Să ne amintim că acest lucru se întâmplă la prima mică iterație de rezolvare a problemei Lr.

) Dacă în cursul rezolvării problemei Lr variabil x n +r se încadrează din nou în numărul celor de bază, apoi rândul corespunzător nu este restaurat.

Este clar că atunci când sunt respectate regulile 3), 4), dimensiunile tabelului simplex din primul algoritm Gomori nu cresc - fiecare tabel conține n+ 2 linii corespunzătoare variabilelor principale X 0 , X 1 , … , x nși variabila auxiliară curentă x n +r la momentul introducerii sale) şi n - m+1 coloane (din moment ce numărul n - m variabilele non-bazice nu se modifică).

) La prima mică iterație a rezolvării problemei Lr+1 este ales ca variabilă derivată din bază x n +r+1, în ciuda faptului că valorile altor variabile auxiliare în acest moment pot fi și negative.

Rețineți că regula 5) este de fapt redundantă, deoarece atunci când regulile 3) și 4) sunt îndeplinite, nu știm nimic despre valoarea variabilelor rămase. x n +1 , …, x n +rîn momentul trecerii la sarcină Lr+1. Această regulă este evidențiată doar pentru a evidenția diferența dintre algoritmii luați în considerare.

Rețineți că atunci când utilizați regula 2) secvența rezultată X ’ (r) poate să nu fie maximul lexicografic al problemei Lr, deoarece valorile unora dintre variabilele auxiliare pot fi negative.

Cu toate acestea, pentru consecvență X ’ (r), r= 0, 1, 2, …, obținute folosind regulile 1) și 2), se păstrează o proprietate importantă: această secvență este unică.

Rămâne doar să demonstrăm că atunci când se utilizează regulile 1) - 4) algoritmul Gomori rămâne finit, deoarece caracterul său finit va însemna că duce la obiectiv - găsirea unei soluții întregi la problema (1.1) - (1.3). Într-adevăr, caracterul finit al numărului R iterații mari înseamnă că vectorul X ’ (R) întreg.

Să remarcăm, în primul rând, că atunci când folosiți regula 2) numărul de iterații mici de rezolvare a problemei Lr desigur - nu mai mult decât este necesar pentru a-și găsi maximul lexicografic.

Teorema 6. Sirul x’(r) care apare în procesul de aplicare a algoritmului Gomori, regula rafinată 1) - 4), este finită.

Dovada. Rețineți că în demonstrația teoremei 5 privind finititatea șirului x(r), au fost utilizate doar două circumstanțe care reglementează apariția acestei secvențe: metoda de construire a tăieturii corecte și faptul că în orice tabel simplex curent toate coloanele b j, jÎw, sunt lexicografic pozitive. Astfel, ștergerea liniei corespunzătoare variabilei auxiliare nu poate afecta decât această din urmă împrejurare. Acest lucru, însă, nu poate fi cazul, așa cum se arată în lema următoare.

Lema 3.În orice tabel simplex apărut în timpul algoritmului Gomori, rafinat prin regulile 1) - 4), pentru orice coloană

exista inegalitate

Dovada. Să presupunem că enunțul lemei nu este valabil pentru unii kО w. Din moment ce b k, atunci această presupunere înseamnă că

Prin definiția unui tabel simplex sub formă de coordonate, avem

Pentru oricine X Î Rn +1+r, dacă enunțul lemei este încălcat în timpul rezolvării problemei Lr. Formula (3.13) luând în considerare (3.12) înseamnă că o modificare a valorii variabilei x k nu afectează valoarea x i, i = 0, 1, 2, …, n. Cu alte cuvinte, pentru același set de valori x i, 0£ i£ n, variabil x k poate lua o valoare arbitrară. Rezultă, în primul rând, că k ³ n+ 1 și, în al doilea rând, că ipoteza acceptată (3.13) este incorectă, deoarece, deoarece valoarea oricărei variabile auxiliare x k, k ³ n+ 1, după cum urmează din (3.7), este determinat în mod unic de valorile variabilelor principale.

Deoarece ștergerea rândurilor corespunzătoare variabilelor auxiliare nu afectează proprietatea coloanelor b j, jÎ w, fii lexicografic pozitiv, atunci aceste rânduri nu sunt deloc necesare. Într-adevăr, ținând cont de regulile 1) - 2) variabile x n +r, devenită una dintre cele de bază, rămâne de bază până la sfârșitul calculelor, iar linia sa nu este necesară pentru a determina variabila introdusă în bază conform regulilor metodei simplex.

Astfel, elementele rând corespunzătoare variabilei x n +r, nu participați la formulele metodei dual simplex pentru calcularea valorilor tuturor celorlalte variabile.

Deoarece, după cum s-a menționat, indicele s reglarea formării tăieturii corecte nu depășește n, 0 £ s £ n, atunci variabilele auxiliare nu sunt necesare în aceste scopuri.

4. Implementarea calculatorului

În acest proiect de curs, programul este conceput pentru a găsi o soluție la o problemă de programare liniară întregă folosind metoda Gomori.

Modulul software folosește un algoritm descris în partea teoretică, ținând cont de comentariile privind aplicarea practică a metodei realizate de Gomori.

Introducerea datelor în modulul de program se face dintr-un fișier. Rezultatele programului pot fi transmise într-un fișier, pe un afișaj sau pe o imprimantă. Format fișier de intrare:

…

…

…

…

Unde n- numărul de variabile, m- numărul de restricții, c 1 , c 2 , … , c n- coeficienții formei liniare maximizate, a ij- elemente de matrice A, b j- componente vectoriale b. A, b - caracterizează restricțiile [vezi. (1.2)].

Exemplu de fișier de intrare:

2 5 0 0 0 0 0 0 0

3 1 0 0 0 0 0 0 12

2 5 0 1 0 0 0 0 0 30

3 2 0 0 1 0 0 0 0 22

2 -1 0 0 0 1 0 0 0 12

1 -3 0 0 0 0 1 0 0 0

2 5 0 0 0 0 0 -1 0 10

5 1 0 0 0 0 0 0 -1 5

Bibliografie:

1. Abramov L.A., Kapustin V.F. Programare matematică. - L.: Editura Universității de Stat din Leningrad, 1981. -328 p.

Belousova G.S. Programare liniară. Tutorial. -Krasnoyarsk: Știință, 1975. -107 p.

Kuznetsov Yu.N. şi altele Programare matematică: Manual. - Ed. a II-a, revizuită. si suplimentare -M.: Şcoala superioară, 1980. -300 p.

Ashmanov S.A., Programare liniară. M.: Știință. 1969. -240 s

Gabasov R.I. Kirillova F.M., Metode de programare liniară. Minsk: Știință. 1977. -174 s

În problemele de programare cu numere întregi, spre deosebire de problemele de programare liniară, se introduce o restricție suplimentară asupra variabilelor: acestea pot lua doar valori întregi.

În unele probleme, de exemplu, tipul de transport, această condiție este îndeplinită automat dacă datele sursă (cantitățile de mărfuri trimise și primite) sunt exprimate în numere întregi. Dar într-o problemă generală de programare liniară, metodele convenționale pentru rezolvarea valorilor întregi nu garantează dacă cantitățile originale sunt numere întregi sau fracții.

În notație matematică, o problemă generală de programare cu numere întregi arată astfel:

maximiza

in conditii

x j≥ 0, x j - întreg.

Problemele de programare liniară economică necesită cel mai adesea o soluție întreagă. Acest lucru se aplică problemelor în care variabilele indică numărul de unități de produse indivizibile, echipamente, lucrători (probleme de cea mai bună distribuție a sarcinilor de producție între întreprinderi, probleme de optimizare a programului de producție al întreprinderilor individuale, probleme de încărcare optimă a echipamentelor etc. ). Adesea, astfel de probleme sunt rezolvate folosind metoda simplex obișnuită, urmată de rotunjirea valorilor obținute ale variabilelor la numere întregi. Dar în acest caz, puteți obține doar o aproximare a planului întreg cu adevărat optim.

Într-un alt grup de probleme de programare liniară, cantitățile de determinat sunt capacitățile de producție care satisfac cel mai eficient o anumită nevoie. Întrucât „purtătorii” capacității de producție sunt întreprinderi individuale, echipamente indivizibile etc., aceste probleme se reduc și la probleme de programare liniară întregi.

Problemele de tăiere rațională a materialului dimensional (sarcini de minimizare a deșeurilor) sunt, de asemenea, cu valori întregi, deoarece variabilele din acestea, de regulă, indică numărul de semifabricate inițiale tăiate într-un fel sau altul.

În toate problemele menționate, soluția poate fi găsită folosind metodele convenționale de programare liniară, urmate de ajustări și obținerea unui plan întreg mai mult sau mai puțin apropiat de cel optim. Dar există probleme pentru care o soluție fără numere nu are sens. Acestea includ probleme de alegere în care valorile numerice ale variabilelor servesc doar la determinarea unei alternative („fie-sau”, „da-nu”).

Modelele de selecție cu numere întregi includ unele probleme de programare operațională, de exemplu, probleme legate de secvența optimă de lansare a diferitelor produse (piese) în producție. Să presupunem că trebuie să determinați ordinea de pornire n piese, fiecare dintre acestea fiind procesată secvenţial pe mai multe maşini. Variabile x ij egal cu unu dacă partea j trebuie rulat după piesa i , și zero - în toate celelalte cazuri. Pentru fiecare fix j , la fel ca pentru toată lumea i , doar unul dintre n variabilele pot fi egale cu unu, astfel încât constrângerile problemei includ următoarele:

Timpul total de procesare al tuturor pieselor pe mașinile din acest grup este redus la minimum. O soluție fără numere întregi la o astfel de problemă nu are sens.

Există mai multe metode pentru rezolvarea problemelor de programare cu numere întregi. Cel mai cunoscut metoda Gomori, bazat pe utilizarea metodei simplex.

Să ne uităm la conceptele matematice: congruenţă numere, întregȘi parte fracționară a unui număr. Număr A congruent cu numărul b dacă și numai dacă diferența a – b este un număr întreg. Congruența este indicată de trei linii orizontale ( ≡ ); Prin urmare, A ≡ b , Dacă a – b este un număr întreg.

De exemplu: 5 / 3 ≡ 2 / 3 , deoarece 5 / 3 - 2 / 3 = 1;

- 1 / 3 ≡ 2 / 3 , deoarece - 1 / 3 - 2 / 3 = 1.

Toate numerele întregi sunt congruente între ele și congruente cu zero. Elementele care nu sunt întregi pot fi reprezentate ca suma întregului și al părților fracționale ale numărului A = [A ] + {A ). Parantezele pătrate înseamnă luarea părții întregi a numărului cuprins în ele, parantezele înseamnă luarea părții fracționale a numărului.

Parte întreagă a unui număr A se numește cel mai mare număr întreg [ A ], fara sa depaseasca A .

Parte fracțională a unui număr A este definit ca cel mai mic număr nenegativ ( A ), congruent cu numărul A . Parte fracțională a unui număr A egală cu diferența dintre număr A și toată partea din ea: ( A }=A - [A ]

De exemplu, pentru A = 2 1 / 3 [A ]= 2 (a) = 1 / 3

pentru a = - 2 1 / 3 [A ]= -3 (a) = 2 / 3

Proprietățile congruenței numerelor:

1. Dacă A ≡ b , Acea ( A } = {b }.

2. {A +b } = {A } + {b }.

3. Dacă n este un număr întreg, atunci pentru oricare A

na ≡ {N / A } ≡ n {A }.

La rezolvarea problemelor de programare cu numere întregi folosind metoda Gomori, prima etapă coincide cu calculul obișnuit folosind algoritmul simplex. Soluția rezultată în formă generală va satisface toate condițiile problemei, cu excepția cerinței de întreg (este posibil, desigur, ca o soluție întreagă să poată fi obținută deja în prima etapă). Dacă printre valorile variabilelor din planul optim (punctul A din Fig. 13) există și fracționale, atunci se elaborează o constrângere suplimentară, ca și cum ar fi „taiat” partea fracționată a soluției (linia 1 în Fig. 13), dar lăsând în vigoare toate restricţiile problemei care ar trebui să satisfacă planul optim. O constrângere suplimentară este adăugată la constrângerile originale ale problemei și procedura simplex este din nou aplicată sistemului extins. Dacă soluția optimă se dovedește din nou a fi non-întreg (punctul B din Fig. 13), atunci se adaugă o altă constrângere suplimentară (linia 2 din Fig. 13) și se repetă procesul de calcul. Algoritmul ne permite să ajungem la o soluție întreagă optimă (dacă aceasta există) într-un număr finit de pași (punctul C din Fig. 13).

Orez. 13. Metoda cutoff Gomori

Exemplu rezolvarea unei probleme de programare cu numere întregi. Pentru achiziționarea de echipamente pentru noul loc de producție au fost alocate 20 de unități bănești. Echipamentul trebuie amplasat pe o suprafață care nu depășește 38 m2. O întreprindere poate comanda două tipuri de echipamente: mașini mai puternice de tip A care costă 5 unități monetare, necesită o suprafață de producție de 8 m 2 (inclusiv pasaje) și asigură o productivitate de 7 mii de unități de producție pe schimb; mașinile mai puțin puternice de tip B costă 2 unități monetare, ocupă o suprafață de 4 m 2 și produc 3 mii de unități de producție pe schimb.

Să notăm prin X 1 număr de mașini achiziționate A și prin X 2 - numărul de mașini achiziționate B, obținem condițiile matematice ale problemei:

maximizați 7x 1 + 3x 2 → max

în condiții: 5x 1 + 2x 2 ≤ 20

8x 1 + 4x 2 ≤ 38

x 1, x 2 ≥ 0 (numere întregi).

Cu ajutorul variabilelor suplimentare x 3 și x 4, inegalitățile originale sunt transformate în ecuații (reduse la formă canonică):

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

Dacă variabilele principale x 1 și x 2 sunt numere întregi, atunci din ecuații rezultă imediat că variabilele x 3 și x 4 pot lua numai valori întregi.

Problema este rezolvată mai întâi fără a lua în considerare cerința întregului.

Tabelul simplex arată astfel:

Bază	CU	Plan					θ
X 1	X 2	X 3	X 4
X 1 →X 3							20/5=4 min
X 4							38/8=4,75
f(x) = 0	-7	-3
X 1				2/5	1/5		4:2/5=10
X 2 →X 4				4/5	-8/5		6:4/5=7,5 min
f(x) =28		-1/5	7/5
X 1						-1/2
X 2		7,5			-2	5/4
f(x) =29,5				1/4

În planul optim, X 1 = 1, X 2 = 7,5; maximul funcției obiectiv este 29,5. Astfel, este necesar să cumpărați o mașină de tip A și 7 mașini de tip B (nu sunt suficienți bani sau spațiu pentru 8 mașini), atunci volumul producției va fi f(x) = 7 × 1 + 3 × 7 = 28 mii unități de producție .

Să găsim o soluție întreagă folosind metoda lui Gomori. Pentru variabila X2, care a primit o valoare non-întreg în plan, compunem următoarea ecuație, care decurge direct din tabelul simplex dat:

7,5 = X 2 – 2X 3 + 1,25X 4.

X 2 = 7,5 + 2X 3 – 1,25X 4.

Această ecuație, evident, trebuie să fie valabilă și pentru o soluție întreagă admisibilă a problemei.

Deoarece X 2 este un număr întreg, expresia din partea dreaptă a ecuației este, de asemenea, un număr întreg; prin urmare, valoarea părții din dreapta a acestei ecuații este congruentă cu zero:

7,5 + 2Х 3 – 1,25Х 4 ≡ 0,

–2Х 3 + 1,25Х 4 ≡ 7,5.

Având în vedere proprietățile de congruență de mai sus și, de asemenea, faptul că X 3 și X 4 sunt numere întregi, această expresie poate fi transformată în următoarea:

(-2)X 3 + (1,25)X 4 ≡ {7,5} ;

de aici obtinem:

0,25X 4 ≡ 0,5.

Deoarece X 4 este un întreg nenegativ, avem:

0,25X 4 = 0,5, sau 1,5, sau 2,5, ...;

prin urmare,

0,25X 4 ≥ 0,5.

Inegalitatea rezultată este convertită într-o ecuație și adăugată la sistemul original de constrângeri, care conține acum următoarele trei ecuații:

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

0,25x 4 – x 5 = 0,5.

Repetând procesul de rezolvare folosind metoda simplex în raport cu sistemul extins de constrângeri, obținem un nou plan optim în care valorile variabilelor incluse în bază sunt egale cu: X 1 = 2; X2 = 5; X 4 = 2 (zona liberă rămasă).

Astfel, s-a obținut o soluție optimă a problemei: sub aceste restricții, productivitatea maximă (29 mii unități de producție) este asigurată prin achiziționarea a 2 mașini de tip A și 5 mașini de tip B.

LECȚIE PRACTICĂ

METODA RUMULUI ȘI LEGAT

Această metodă poate fi aplicată pentru a rezolva atât probleme de programare discretă integrală, cât și parțială.

Luați în considerare modelul

sub restricții

Să presupunem că pentru fiecare variabilă întreagă se pot stabili limite superioare și inferioare, în care, desigur, sunt conținute valorile optime ale acesteia

H j ≤ X j ≤ V j ; j=1,2,…,k,…,n.

De obicei Hj = 0, dar această condiție nu este necesară. Problema este rezolvată folosind metoda simplex. Dacă Xk ia valori fracționale, credem că soluția optimă a problemei va satisface constrângerea liniară X k ≤ D k , sau constrângere liniară X k ≤ D k + 1 , Unde Dk =[Xk ] – cel mai apropiat număr întreg în jos de la valoare Xk ; D k + 1 – cel mai apropiat număr întreg în sus de la Xk . în care H j ≤ D k ≤ V j – 1 . Apoi, este necesar să se rezolve câteva probleme de programare liniară folosind metoda simplex:

A.

ÎN.

Obținem un proces iterativ reprezentat sub formă de arbore, al cărui vârf corespunde soluției problemei inițiale, iar cele două ramuri legate de acesta sunt soluții la o pereche de probleme de programare liniară A și B. Valorile rezultate ale funcțiile obiective pot fi mai mici sau egale cu valoarea funcției obiectiv a problemei inițiale f(X) A ≤ f(X)­ 0 ; f(X) B ≤ f(X)­ 0 . Fiecare dintre cele două noi vârfuri de ramificație obținute poate avea propriile ramuri ulterioare.

1) Procesul de ramificare iterativă continuă până când se obține o soluție între planurile obținute, iar valoarea funcției obiectiv trebuie să fie mai mare sau egală cu valorile funcțiilor obiectiv ale altor vârfuri de ramificare.

2) Dacă la următorul pas de iterație ambele probleme au soluții non-întregi, atunci vârful corespunzător problemei cu o valoare mare a funcției obiectiv este selectat pentru ramificare ulterioară. Pentru una dintre variabilele care a primit valori fracționale, se întocmesc noi constrângeri pentru următoarele probleme de programare liniară.

3) Dacă la următorul pas de iterație una dintre probleme are o soluție întreagă, iar dintre valorile variabilelor din a doua problemă sunt fracționale, atunci dintre ele problema cu cea mai mare valoare a funcției obiectiv este selectat. Dacă aceasta este o problemă care a primit o soluție întreagă, atunci procesul se termină, dar dacă aceasta este o problemă cu valori fracționale ale variabilelor, atunci se efectuează un alt proces de ramificare pentru aceasta.

4) Dacă la următorul pas de iterație una dintre probleme nu are o soluție, iar a doua problemă are valori fracționale dintre valorile variabilelor din soluția rezultată. Apoi, pentru prima problemă, procesul de ramificare se oprește, iar pentru transformarea ulterioară a celei de-a doua probleme este selectată una dintre variabilele non-întregi, pentru care se întocmesc constrângeri suplimentare pentru o nouă pereche de probleme de programare liniară.

5) Dacă la următorul pas de iterație una dintre probleme nu are o soluție, iar pentru cealaltă se obține o soluție întreagă și nu există alte opțiuni cu o valoare întreagă mare a funcției obiectiv și pentru care ramificarea poate fi continuată , apoi procesul se termină, iar soluția găsită este soluția întreagă optimă pentru sarcinile originale.

Dacă sarcina selectată duce la o pauză (deadlock) sau valoarea funcției este mai mică decât în ​​sarcina B.1 f(X) A.4< f(X)­ В,1 ., apoi are loc o revenire la sarcina B.1 și apare o nouă ramură.

Fig. 14. Organigramă de ramificare și algoritm legat

Orez. 15. Metoda ramurilor și legate