Constrângerea Gomori are următoarea formă. Elaborarea unei constrângeri suplimentare (secțiunea Gomori)

Metoda lui Gomori pentru rezolvarea problemelor de programare cu numere întregi este metoda de tăiere .

Esența metodei este de a construi restricții care să taie soluții non-întregi ale problemei programare liniară, dar fără a întrerupe niciun plan întreg. Pentru a face acest lucru, mai întâi decideți sarcină slăbită programare liniară fără a ține cont de condiția variabilelor întregi.

Dacă este primit rezolvarea problemei programarea liniară este întreg, apoi problema programare cu numere întregi este de asemenea rezolvată și soluția găsită este optimă și pentru aceasta. Dacă în soluția găsită a problemei de programare liniară există una sau număr mai mare variabilele nu sunt întregi, apoi pentru a găsi o soluție întreagă a problemei, se adaugă o nouă constrângere liniară, care decupează soluțiile non-întregi. Când continuați să rezolvați problema extinsă cu dual metoda simplexținând cont de această constrângere, se obține un plan întreg.

Pentru a găsi o soluție întreagă a problemei folosind metoda Gomori, se folosește următorul algoritm.

Ar trebui să fie liniar;

Ar trebui să întrerupă planul non-întreg optim găsit;

Nu ar trebui să trunchieze niciun plan întreg.

Dacă există mai multe variabile de bază non-întregi, atunci pentru a crea o constrângere selectăm o componentă a planului optim cu cea mai mare parte fracţională (dacă există mai multe astfel de variabile, atunci selectați oricare).

Această variabilă corespunde unui rând de tabel simplex numit linia care produce tăietura (linie generatoare ).

Pentru a prezenta metoda, introducem următoarele concepte. Lăsa A- numar real.

Sub întreaga parte oarecare număr A este înțeles ca număr întreg maxim [ A], nedepășind aceasta.

Sub parte fracționată oarecare număr Aînseamnă cel mai mic număr nenegativ
astfel încât diferența dintre ea și A Există [ A] – întreaga parte numere).

Pentru variabila de bază selectată cu cea mai mare parte fracţională găsim parte fracționată
această variabilă și părțile fracționale ale tuturor coeficienților pentru variabile i a linia a sistemului de restricții
(linie de producție).

Să notăm
Și
părți întregi de numere Și . Valori fracționale
Și
(
) sunt definite după cum urmează

Pentru a face acest lucru, se scrie o ecuație din rândul generator al tabelului simplex, presupunând că primul m variabilele sunt de bază pentru un plan optim dat

sau

Mutăm toate părțile întregi ale coeficienților într-o direcție, lăsând toate părțile fracționale în cealaltă:

Deoarece
<1, то заменяя в правой части
, obținem inegalitatea strictă

Deoarece partea stângă a inegalității trebuie să ia valori întregi, prin urmare, condiția necesară pentru integritatea ei poate fi scrisă doar sub următoarea formă:

Inegalitatea este convertită într-o ecuație prin introducerea unei variabile suplimentare nenegative și inclusă în tabelul simplex optim.

Rezolvăm problema folosind metoda dual simplex. Dacă noul plan optim pentru problema extinsă este întreg, atunci problema este rezolvată. Dacă soluția nu este întreagă, atunci trebuie să repetați algoritmul metodei Gomori până când se obține o soluție întreagă.

Exemplu. Folosind metoda Gomori, găsiți o soluție la o problemă de programare cu numere întregi constând în determinarea valorii maxime a unei funcții
dat fiind

Soluţie. Nivelarea inegalităților folosind variabile auxiliare X 3 , X 4, obținem problema de programare liniară în formă canonică:

Rezolvăm problema de programare liniară folosind metoda simplex, folosind o tranziție pas cu pas de la o bază la alta. Progresul rezolvării problemei și soluția optimă rezultată sunt prezentate în tabele.

În planul optim găsit, valoarea variabilei X 2 este egal cu un număr fracționar. Găsim partea ei fracțională și părțile fracționale ale tuturor elementelor liniei care conține variabila X 2, și anume:

Acum compunem inegalitatea Gomori pentru valorile găsite ale părților fracționale:

.

X 5, mutăm termenul liber al ecuației în partea dreaptă și obținem o nouă constrângere:

.

Adăugăm un rând care conține o nouă constrângere și o coloană care conține o nouă variabilă la tabelul simplex și continuăm să rezolvăm problema folosind metoda dual simplex, deoarece pseudoplanul este acum scris în tabel.

Soluția optimă rezultată pentru problema extinsă conține o valoare neîntregătoare a variabilei X 1, deci găsim pentru această linie părțile fracționale ale tuturor numerelor neîntregi, și anume:

iar noua inegalitate Gomory are forma:

Egalăm inegalitatea lui Gomori folosind o nouă variabilă auxiliară X 6, mutăm termenul liber al ecuației în partea dreaptă și obținem o nouă constrângere:
.

O adăugăm la problema care se rezolvă, o aliniem folosind o variabilă auxiliară și rezolvăm problema extinsă

Astfel, a fost găsită soluția optimă la problema programării întregi: Z max=11 la
.

Note :

Dacă în proces de rezolvare tabel simplex va apărea o ecuație cu o componentă neîntregătoare și coeficienți întregi în linia corespunzătoare a sistemului de restricții
, atunci această problemă nu are o soluție întreagă.

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ă 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 de formă poate servi ca soluție

.

În legătură cu cele de mai sus, atunci când se justifică algoritmi 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> maximizabil formă liniară- un număr întreg. În acest caz spunem că integralitatea este garantată funcție obiectivă.

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 țintă.

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*- un fel de 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 un 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 X rș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- se dovedește a fi un număr întreg, atunci este o soluție problema initiala(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 X r.

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 algoritm general reduceri 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ă și, respectiv, nebază, 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

Într-adevăr, condiția cutoff este satisfăcută trivial, deoarece . Este îndeplinită și condiția de corectitudine, î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 inegalitatea

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 aplicare dual simplex- metoda la problema 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 întregi (1.1) - (1.3) ar trebui oprită deoarece

Teorema 4. Dacă în problemă L 1 nu exista 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 metoda dual simplex, care se numesc 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 a acestei coloane 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. Să ne amintim, de asemenea, 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. Se dovedește în mod similar că această secvență nu poate conține infinite numere întregi diferite.

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

La implementare practicăÎn primul algoritm Gomori, o problemă importantă este creșterea numărului de restricții, ceea ce duce la o creștere a 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 în continuare 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 la problema numărului întreg inițial. În caz contrar, trecem la o nouă iterație mare.

) Rând 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ă evidențiate 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ă succesiune 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 în 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, indexul 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

In 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 algoritmul descris în partea teoretică, ținând cont de comentariile aplicație practică metoda realizata 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.: facultate, 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

Interpretarea economică și geometrică a problemei de programare cu numere întregi. O problemă extremă ale cărei variabile iau doar valori întregi se numește problemă de programare cu numere întregi.

În modelul matematic al problemei întregi programare atât funcția obiectiv cât și funcțiile din sistemul de constrângeri pot fi liniare, neliniare și mixte. Să ne limităm la cazul în care funcția obiectivă și sistemul de constrângeri ale problemei sunt liniare.

Exemplul 20.

S-a decis instalarea de echipamente suplimentare în atelierul întreprinderii, pentru care a fost alocat spațiu. O întreprindere poate cheltui 10 mii de ruble pentru achiziționarea de echipamente și poate cumpăra două tipuri de echipamente. Un set de echipamente de tip I costă 1.000 de ruble, iar tipul II - 3.000 de ruble. Achiziționarea unui set de echipamente de tip I vă permite să creșteți producția de producție pe schimb cu 2 unități, iar un set de echipamente de tip II - ​​cu 4 unități. Știind că instalarea unui set de echipamente de tip I necesită 2 m 2 de suprafață, iar echipamentele de tip II necesită 1 m 2 de suprafață, determinați un astfel de set de echipamente suplimentare care să facă posibilă maximizarea producției.

Soluţie. Să creăm un model matematic al problemei. Să presupunem că întreprinderea va achiziționa x 1 seturi de echipamente de tip I și seturi de echipamente de tip II. Atunci variabilele x 1 și trebuie să satisfacă următoarele inegalități:

Dacă întreprinderea achiziționează cantitatea specificată de echipamente, atunci creșterea totală a producției va fi

În funcție de conținutul lor economic, variabilele x 1 și pot lua numai valori întregi nenegative, i.e.

x 1 , – numere întregi. (73)

Astfel, ajungem la următoarele problema de matematica: găsiți valoarea maximă funcție liniară(71) când sunt îndeplinite condițiile (70), (72) și (73). Deoarece necunoscutele pot lua numai valori întregi, problema (70) – (73) este o problemă de programare cu numere întregi. Deoarece numărul de necunoscute din problemă este de două, soluția acestei probleme poate fi găsită folosind interpretarea sa geometrică. Pentru a face acest lucru, în primul rând, vom construi un poligon de soluții la problema constând în determinarea valorii maxime a funcției liniare (71) când sunt îndeplinite condițiile (70) și (72) (Fig. 11). Coordonatele tuturor punctelor poligonului soluție construit OAEVS satisface sistemul de inegalități liniare (70) și condiția non-negativitatea variabile (72). În același timp, condiția (73), adică condiția integritate variabilele sunt satisfăcute de coordonatele a doar 12 puncte marcate în Fig. 11. Pentru a găsi punctul ale cărui coordonate determină soluția problemei inițiale, înlocuiți poligonul OABC poligon OKEMNF, care conține toate punctele valide cu coordonate întregi și astfel încât coordonatele fiecăruia dintre vârfuri să fie numere întregi. Aceasta înseamnă că dacă găsim punctul maxim al funcției (71) pe poligon OKEMNF, atunci coordonatele acestui punct vor determina planul optim pentru problemă.

Pentru a face acest lucru, vom construi și o linie dreaptă care trece prin poligonul soluției OKEMNF(numărul 12 este luat în mod arbitrar). Deplasăm linia construită în direcția vectorului până când trece prin ultimul său punct comun cu poligonul dat. Coordonatele acestui punct determină planul optim, iar valoarea funcției obiectiv la acesta este maximă.

ÎN în acest caz, punctul cerut este E(1; 3), în care funcția obiectiv ia valoarea maximă C, deci coordonatele punctului E determinați planul optim pentru problemă (70) – (73). În conformitate cu acest plan, întreprinderea ar trebui să achiziționeze un set de echipamente de tip 1 și trei seturi de echipamente de tip II. Acest lucru va oferi întreprinderii restricțiile existente privind spațiul de producție și fonduri mărire maximă producție egală cu 14 unități. pe schimb.

Exemplul 21.

Pentru a efectua lucrarea poate fi folosit P mecanisme. Performanţă i--lea mecanism la executare j – lucrarea este egală cu . Presupunând că fiecare mecanism poate fi utilizat doar la un loc de muncă și fiecare job poate fi executat printr-un singur mecanism, determinați alocarea mecanismelor la locuri de muncă care asigură productivitate maximă. Construiți un model matematic al problemei.

Soluţie. Să introducem o variabilă x ij a cărei valoare este 1 dacă, la executare i-a munca folosita j – al-lea mecanism și este egal cu 0 în caz contrar. Atunci condițiile de utilizare a fiecărui mecanism pe un singur loc de muncă sunt exprimate prin egalități

(74)

și condițiile pentru efectuarea muncii printr-un singur mecanism - egalități

(75)

Astfel, sarcina este de a determina astfel de valori ale necunoscutelor , satisfacând sistemele de ecuații (74) și (75) și condiția (76), în care se realizează valoarea maximă a funcției

Problema formulată este o problemă de programare cu numere întregi.

Determinarea planului optim pentru o problemă de programare cu numere întregi. Să luăm în considerare problemele de programare cu numere întregi în care atât funcția obiectiv, cât și funcțiile din sistemul de constrângeri sunt liniare. În acest sens, formulăm problema de bază de programare liniară în care variabilele pot lua doar valori întregi. În general, această problemă poate fi scrisă astfel: găsiți maximul funcției

in conditii

(79)

– întreg (81)

Dacă găsiți o soluție la problema (78) – (81) folosind metoda simplex, atunci poate fi sau nu întreg (un exemplu, a cărui soluție este întotdeauna întreagă, este problema transportului). În cazul general, pentru a determina planul optim pentru problema (78) – (81) sunt necesare metode speciale. În prezent, există mai multe astfel de metode, dintre care cea mai faimoasă este metoda Gomori, care se bazează pe metoda simplex descrisă mai sus.

metoda Gomori. Găsirea unei soluții la o problemă de programare cu numere întregi folosind metoda Gomori începe cu determinarea planului optim al problemei (78) – (80) folosind metoda simplex, fără a lua în considerare integritate variabile. Odată ce acest plan este găsit, componentele sale sunt revizuite. Dacă nu există numere fracționale între componente, atunci planul găsit este planul optim pentru problema de programare a întregilor (78) – (81). Dacă în planul optim al problemei (78) – (80) variabila ia o valoare fracțională, atunci inegalitatea se adaugă sistemului de ecuații (79)

(82)

și găsiți o soluție la problema (78) – (80), (82).

În inegalitate (82) și – mărimile inițiale transformate și ale căror valori sunt preluate din ultimul tabel simplex și – părți fracționale ale numerelor (partea fracțională a unui anumit număr a este cel mai mic număr nenegativ b astfel încât diferența dintre AȘi b există un întreg). Dacă în planul optim al problemei (78) – (80) valorile fracționale iau mai multe variabile, atunci se determină inegalitatea suplimentară (82) cea mai mare fracție parte.

Dacă în planul găsit al problemei (78) – (80), (82) variabilele iau valori fracționale, atunci se adaugă din nou o constrângere suplimentară și se repetă procesul de calcul. Efectuând un număr finit de iterații, se obține fie planul optim pentru problema de programare cu numere întregi (78) – (81), fie se stabilește insolubilitatea acestuia.

Dacă cerința integritate(81) se aplică numai unor variabile, atunci se numesc astfel de probleme parțial întreg. Soluția lor se găsește și prin rezolvarea secvențială a problemelor, fiecare dintre ele obținută din cea anterioară folosind introducerea restricție suplimentară. În acest caz, o astfel de restricție are forma

unde se determină din următoarele relații:

1) pentru , care poate lua valori non-întregi,

(84)

2) pentru , care poate lua numai valori întregi,

(85)

Din cele de mai sus rezultă că procesul de determinare a planului optim pentru o problemă de programare cu numere întregi folosind metoda Gomori include următoarele etapele principale:

1. Folosind metoda simplex, găsiți o soluție la problema (78) – (80) fără a lua în considerare cerința integritate variabile.

2. Creați o constrângere suplimentară pentru variabilă, care în planul optim al problemei (78) – (80) are fracționar maxim valoare, iar în planul optim, problema (78) – (81) ar trebui să fie întreagă.

3. Folosind dualul , găsiți o soluție la problema rezultată din problema (78) – (80) ca urmare a adăugării unei constrângeri suplimentare.

4. Dacă este necesar, creați o altă constrângere suplimentară și continuați procesul iterativ până când se obține un plan optim pentru problema (78) – (81) sau se stabilește insolubilitatea acesteia.

Exemplul 22.

Utilizați metoda Gomori pentru a găsi valoarea maximă a funcției

dat fiind

(87)

– întreg (89)

Soluţie. Pentru a determina planul optim pentru problema (86) – (89), găsim mai întâi planul optim pentru problema (86) – (88) (Tabelul 22).

Tabelul 22

		C b	R 0

După cum se vede din tabel. 22, plan optim găsit problema (86) – (88) nu este un plan optim pentru problema (86) – (89), deoarece două componente au valori non-întregi. În plus, părțile fracționale ale acestor numere sunt egale între ele. Prin urmare, se elaborează o constrângere suplimentară pentru una dintre aceste variabile. Să facem, de exemplu, o astfel de constrângere pentru variabila Din ultimul tabel simplex (Tabelul 22) avem

Astfel, la sistemul de constrângeri ale problemei (86) – (89) adăugăm inegalitatea

sau

Tabelul 23

		C b	R 0

Găsim acum valoarea maximă a funcției (86) când sunt îndeplinite condițiile (87), (88) și (90) (Tabelul 23).

Din Tabelul 23 se poate observa că problema originală de programare cu numere întregi are un plan optim PÎn acest plan, valoarea funcției obiectiv este egală cu . Să oferim o interpretare geometrică a soluției problemei. Regiunea soluțiilor fezabile la problema (86) – (88) este un poligon OABCD(Fig. 12). Din fig. 12 se poate observa că funcția obiectiv își ia valoarea maximă în punct CU(19/2; 7/2), adică Ce X =(19/2; 7/2; 0; 0; 34) este planul optim. Acest lucru este direct evident din Tabelul 22. Din moment ce X= (19/2; 7/2; 0; 0; 34) nu este planul optim pentru problema (86) – (89) (numerează și sunt fracționari), atunci se introduce o constrângere suplimentară. Excluzând din acesta și înlocuind în schimb valorile corespunzătoare din ecuațiile sistemului de constrângeri (87), obținem un cutoff din poligon OABCD triunghi EFC.

După cum se poate observa din fig. 12, regiunea soluțiilor fezabile la problema rezultată este un poligon OABEFD. La punctul E(9; 4) a acestui poligon, funcția obiectiv a acestei probleme ia valoarea maximă. Deoarece coordonatele punctului E sunt numere întregi și necunoscute și iau valori întregi atunci când înlocuiți valorile și în ecuația (87), atunci este planul optim pentru problema (86) – (89). Acest lucru reiese și din Tabelul 23.

Exemplul 23.

Folosind metoda Gomori, găsiți o soluție la problema determinării valorii maxime a unei funcții

in conditii

- întreg. (94)

Oferiți o interpretare geometrică a soluției problemei.

Soluţie. Să rescriem problema formulată astfel: găsiți valoarea maximă a funcției

in conditii

(96)

- întreg. (98)

Problema (95) – (98) este parțial întreagă, deoarece variabilele și pot lua valori non-întregi.

Folosind metoda simplex, găsim soluția problemei (95) – (97) (Tabelul 24).

Tabelul 24

		C b	R 0
		C b	R 0
							–1/3 nu este un plan pentru problema (95) – (98), deoarece variabila

Î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 inițiale sunt numere întregi sau fracții.

În notație matematică sarcină comună programarea 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 program de producțieîntreprinderi individuale, probleme de încărcare optimă a echipamentelor etc.). Adesea, astfel de probleme sunt rezolvate folosind metoda simplex obișnuită cu rotunjirea ulterioară a valorilor obținute variabile 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 se poate găsi o soluție metode convenționale programare liniara cu ajustare ulterioara si obtinerea unui plan intreg mai mult sau mai putin 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.

Sa luam in considerare concepte 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 vedere generala va satisface toate condițiile problemei, cu excepția cerinței întregului (este posibil, desigur, ca o soluție întregă 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 procesul de calcul se repetă. 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 a cumpăra echipament pentru un nou loc de producție a alocat 20 de unităţi monetare. Echipamentul trebuie amplasat pe o suprafață care să nu depășească 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 inițiale 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.

Un tabel simplex are următoarea vedere:

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 sistem original 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ă putem seta un și limita inferioara, în cadrul căruia, desigur, este cuprins valori optime

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 întreg în latura mare din 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 pentru ramificarea ulterioară vârful corespunzător problemei cu de mare valoare funcții de scop. 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 printre valorile variabilelor din a doua problemă se numără și fracționale, atunci problema care are cea mai mare valoare funcții de scop. Dacă aceasta este o problemă care a primit o soluție întreagă, atunci procesul se termină, dar dacă aceasta este o problemă cu valorile fracționale ale variabilelor, atunci proces ulterior ramificare.

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 soluție, iar pentru cealaltă se obține o soluție întreagă și nu există alte opțiuni cu o valoare întreagă mai mare a funcției de obiectiv și pentru care ramificarea poate fi continuată , atunci procesul se termină și soluția găsită este optimă soluție întreagă sarcina originală.

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ă a algoritmului de ramificare și legat

Orez. 15. Metoda ramurilor și legate

MINISTERUL EDUCATIEI AL FEDERATIEI RUSA

UNIVERSITATEA TEHNICĂ DE STAT KUZBASS

Departament tehnologia calculatoarelorși tehnologia informației

SOLUȚIONAREA PROBLEMELOR DE PROGRAMARE A NUMERILOR ÎNTREGI LINEAR FOLOSIND METODEA GOMORI

Orientări și sarcini pentru exercitii practice la rata

„Metode economice și matematice” pentru studenții specialităților economice

Compilat de N.Yu Kolomarova

Aprobat în ședința departamentului Procesul-verbal nr.5 din 30 noiembrie 1999

O copie electronică se află în biblioteca clădirii principale a KuzSTU

Kemerovo 2000

1. DECLARAȚIA PROBLEMEI

Există o serie de probleme de planificare optimă în care variabilele pot lua doar valori întregi. Astfel de sarcini sunt asociate cu determinarea numărului de unități de produse indivizibile, a numărului de mașini la încărcarea echipamentelor, a numărului de angajați din diviziile structurale ale întreprinderii etc. Destul de des, apar probleme cu așa-numitele variabile booleene, ale căror soluții sunt judecăți de tip „da-nu”. Dacă funcția și constrângerile din astfel de probleme sunt liniare, atunci vorbim despre o problemă de programare liniară cu numere întregi.

Se formulează problema de programare liniară întregi

este după cum urmează: găsi o astfel de soluție (plan)

X = (x1, x2, ..., xn),

ia valoarea maximă sau minimă sub restricții

2. METODA GOMORI

Una dintre metodele de rezolvare a problemelor de programare cu numere întregi liniare este metoda Gomori. Esența metodei este de a construi constrângeri care elimină soluțiile non-întregi la o problemă de programare liniară, dar nu elimină niciun plan întreg.

Să luăm în considerare un algoritm pentru rezolvarea unei probleme de programare liniară întregi folosind această metodă.

1. Rezolvăm problema folosind metoda simplex fără a ține cont de condiția întregului. Dacă toate componentele unui plan optim sunt numere întregi, atunci este optim pentru o problemă de programare cu numere întregi. Dacă se constată că o problemă nu este rezolvabilă, atunci problema de programare cu numere întregi este, de asemenea, de nerezolvată.

2. Dacă printre componente soluție optimă nu sunt întregi, apoi la constrângerile problemei adăugăm o nouă constrângere care are următoarele proprietăți:

Ar trebui să fie liniar; - trebuie să taie neîntregul optim găsit

plan; - nu trebuie să întrerupă niciun plan întreg.

Pentru a construi o constrângere, selectăm o componentă a planului optim cu cea mai mare parte fracţională iar folosind rândul k al tabelului simplex corespunzător acestei componente notăm constrângerea Gomori.

		f k = ∑	f kj x j − S * ,S * ≥ 0 ,
unde f k	Xj - ;
	Zkj -;
		Variabilă nouă;
Cel mai apropiat număr întreg care nu depășește x j și, respectiv, z kj
		Adăugăm constrângerea creată la cele disponibile în sim-

tabel complex, obținând astfel o problemă extinsă. Pentru a obține planul de referință pentru această problemă, trebuie să introduceți baza că

	un vector pentru care cantitatea				∆ j		minim. Și dacă pentru acest secol -
					f kj
	valoarea torusului θ = min		rezultă conform linie suplimentară, apoi în
	z ij> 0

următorul tabel simplex va produce planul de referință. Dacă valoarea θ nu corespunde liniei suplimentare, atunci este necesar

mergeți la problema M (introduceți o variabilă artificială în constrângerea Gomori).

4. Rezolvăm problema rezultată folosind transformări simplex obișnuite. Dacă soluția acestei probleme duce la un plan optim întreg, atunci problema dorită este rezolvată. Dacă obținem o soluție non-întreg, atunci adăugăm din nou o constrângere suplimentară și procesul de calcul se repetă. După finalizarea unui număr finit de iterații, fie obținem un plan optim pentru problema de programare cu numere întregi, fie stabilim imposibilitatea acesteia.

Note:

1. Dacă variabila suplimentară S * este inclus în bază, apoi după recalcularea oricărui plan ulterior, rândul și coloana corespunzătoare pot fi șterse (reducend astfel dimensiunea problemei).

2. Dacă pentru fracţional x j rezultă că toți coeficienții ecuației (rândul) corespunzătoare sunt numere întregi, atunci problema nu are o soluție întreagă.

3. EXEMPLE DE REZOLVARE A PROBLEMELOR CU METODEA GOMORI

Sarcină: Pentru achiziționarea de echipamente noi, compania alocă 19 unități monetare. Echipamentul trebuie amplasat pe o suprafață care nu depășește 16 mp. O întreprindere poate comanda două tipuri de echipamente: mașini de tip „A” care costă 2 unități monetare, care necesită o suprafață de producție de 4 mp și oferă o productivitate de 8 tone de produse pe schimb și mașini de tip „B” costând 5 unități monetare, ocupând o suprafață de 1 mp și asigurând o productivitate de 6 tone de produse pe tură.

Se impune intocmirea unui plan optim de achizitie de echipamente care sa asigure maxim performanța generală.

Rezolvare: Să notăm cu x 1 , x 2 numărul de mașini de tip „A” și, respectiv, „B”, și cu L - productivitatea totală a acestora. Apoi model matematic sarcini:

max L = 8 x1 +6 x2

cu restrictii:

2x 1	5x2
4x 1
x 1≥		0, x2 ≥ 0

x1, x2 - numere întregi

Rezolvăm problema folosind metoda simplex fără a lua în considerare valorile întregi.

	∆ j
	∆ j
	∆ j

Sa obținut planul optim non-intger X opt = (61/18;22/9).

Lmax = 376/9.

Deoarece componenta planului x 2 are o parte fracționară maximă: max(4/9;7/18) = 4/9, apoi scriem o constrângere suplimentară pe prima linie.

22/9 - = (2/9 - )x 3 + (-1/9 - [-1/9])x 4 -S 1 , S 1 ≥0 22/9 - 2 = (2/9 - 0) x 3 + (-1/9 - (-1))x 4 -S 1 , S 1 ≥0

4/9 = 2/9x3 + 8/9x4 - S1, S1 ≥ 0 - prima constrângere Gomori

Adăugăm constrângerea creată celor existente în tabelul simplex.

După construirea unei constrângeri suplimentare avem sarcina noua programare liniară, care are 3 restricții. Pentru a obține un plan de referință pentru această problemă, este necesar să găsiți a treia bază

ny vector. Pentru a face acest lucru, definim: min
	f kj

pe baza introducem vectorul x 4.							4 / 9
Se calculează valoarea θ =
	z ij> 0						8 / 9

Valoarea minimaθ a fost obținut dintr-o linie suplimentară, ceea ce înseamnă că fără a recurge la o variabilă artificială, obținem planul de referință al problemei extinse.

	∆ j

Planul găsit este optim, dar nu este întreg. Construim o nouă constrângere Gomori.

Deoarece partea fracțională maximă dintre componentele planului este 1/2, scrieți o restricție suplimentară pe prima linie (puteți și pe a treia).

5/2 - = (1/4 - )x 3 + (-1/8 - [-1/8])S 1 -S 2 , S 2 ≥0

1/2 = 1/4x3 + 7/8S1 - S2, S2 ≥ 0 - constrângere Gomori secundă

Adăugăm această constrângere la ultimul tabel simplex.

Am primit o problemă în care există 4 constrângeri, prin urmare, ar trebui să existe 4 vectori unitari în bază.

								2. Poate sa

introduceți fie x 3 fie S 1 . Să introducem vectorul S 1 .

1/ 2

4 / 7

corespunde suplimentar

7 / 8

prescripţie.

∆ j

Obținem un nou plan optim non-întreg. Ținând cont de observația 1, tăiem rândul și coloana corespunzătoare re-

variabila S 1.

În planul rezultat, componenta x2 are partea fracțională maximă, așa că notăm o constrângere suplimentară pe prima linie.

	4/7 = 2/7x3 + 6/7S2 - S3, S3 ≥ 0	A treia limitare a lui Gomori.
	Determinăm vectorul introdus în bază:

vector x 3. Valoarea minimă a lui θ = 2, care corespunde unei linii suplimentare.

După efectuarea următoarelor transformări simplex, am obținut:

	∆ j

Planul X 5 este optim non-intreg. Scriem o restricție suplimentară pe a doua linie:

1/2 = 1/4S3 - S4, S4 ≥ 0

A patra limitare a lui Gomori.

Deoarece componenta de bază poate fi S 3, determinăm valoarea

0. Valoarea minimă a lui θ a fost obținută la 3

linie, și nu după linia Gomori, prin urmare, trecem la problema M:

să introducem o variabilă suplimentară x 5							la limitarea Gomori.
C5'	B5 '	X5 '
	∆ j

∆ j

∆ j

Partea fracțională = max(1/3; 2/3) = 2/3

restricție suplimentară

O notăm pe a doua linie.

2/3 = 1/3x4 + 2/3S4 - S5

S5 ≥

A cincea limitare a lui Gomori.

16 / 3

2 introduceți x 4.

Vector introdus în bază: min

2 / 3

θ =

se potrivește cu linia lui Gomori.

∆ j

Plan X 8 = (3; 2; 3; 2) - întreg optim L max = 36.

Interpretare economică:Conform deciziei primite, compania trebuie să achiziționeze 3 utilaje de tip „A” și 2 utilaje de tip „B”. În acest caz se va realiza performanță maximă funcţionarea echipamentului egal cu 36 de tone de produse pe schimb. Economii rezultate Baniîn valoare de 3 den. poate fi trimis la orice alte scopuri, de exemplu, pentru bonusuri pentru muncitorii care vor depana echipamentele primite. Puteți pune o cutie de flori pe suprafața în exces de 2 mp.

Interpretarea geometrică a metodei lui Gomori: construim multe

numărul de planuri (vezi figura). La punctul 1 - planul optim non-întreg.