Întocmirea unei constrângeri suplimentare (secțiunea Gomori). Probleme de programare liniară întregi. metoda Gomori

Metoda Gomori este folosită pentru a găsi soluții întregi la probleme programare liniară.
Să se găsească o soluție la problema LP: . Soluția L i va fi un număr întreg dacă acestea. . (β i) este partea fracționară a soluției optime non-întregi x i, (d i) este partea fracțională a variabilelor nebazice. Acest raport determină (vezi figura).

Scopul serviciului. Calculatorul online este folosit pentru a rezolva probleme de programare liniară întregi folosind metoda cutoff. În timpul soluției, se folosesc tabele simplex. (vezi exemplu).

Instrucțiuni. Selectați numărul de variabile și numărul de rânduri (numărul de constrângeri), faceți clic pe Următorul. Soluția rezultată este stocată în Fișier Word(vezi un exemplu de soluție folosind metoda Gomori). În plus, un șablon de soluție este creat în format Excel.

Numărul de variabile 2 3 4 5 6 7 8 9 10
Număr de rânduri (număr de restricții) 2 3 4 5 6 7 8 9 10

În același timp, restricții precum x i ≥ 0 nu iei in calcul.

Tipuri de algoritm Gomori

1. Primul algoritm al lui Gomori pentru rezolvarea problemelor complet întregi.
2. Al doilea algoritm al lui Gomori pentru probleme de programare liniară parțial întregi.

algoritmul Gomori pentru problemele cu numere întregi include următorii pași:

1. Problema programării liniare este rezolvată fără a lua în considerare numărul întreg.
2. Dintre numerele fracționale, este selectat și compilat elementul cu cea mai mare parte fracțională restricție suplimentară.
3. Inegalitatea este transformată într-o ecuație prin introducerea unei variabile suplimentare nenegative.
4. Problema rezultată este rezolvată folosind metoda dual simplex.

Dacă, în timpul procesului de rezolvare, în tabelul simplex apare o ecuație cu termeni fără numere b i și coeficienți întregi a ij, atunci aceasta sarcina nu are o soluție optimă întreagă.

Exemplu. Asociația de Cercetare și Producție Strela este angajată în fabricarea de componente pentru întreprinderi complexe militar-industriale. La fabricarea produselor de tip A și tip B se utilizează oțel și metale neferoase. Proces tehnologic include și prelucrarea produselor pe strunguri și mașini de frezat. Conform standardelor tehnologice, producerea unui produs de tip A și a unui produs de tip B necesită o anumită cantitate de materii prime și o anumită cantitate de ore de mașină pentru prelucrarea pe mașini din atelier. Date tehnologice proces de producție sunt date în tabel.
Într-o lună, atelierul NPO Strela are resurse limitate după materii prime și după timpul de lucru în atelierele de producție (vezi tabel). Profitul din vânzarea unui produs de tip A este de 100 de ruble, iar dintr-o unitate de produs de tip B - 250 de ruble.

	Materii prime		Lucru în atelier, oră de mașină		Profit din vânzări, frecați.
	Metale neferoase	Oţel	Lucrări de strunjire	Lucrări de frezare
Produsul A	10	25	41	90	100
Produsul B	30	25	90	50	250
Resurse	4500	6250	14100	18000

Găsi plan optim producție pentru NPO Strela (cantitate de produs tip A și tip B - numere întregi), dând cel mai mare profit.

Soluţie.
Economic model matematic sarcini.
x 1 - plan de producție pentru produse de tip A, x 2 - plan de producție pentru produse de tip B,
x 1, x 2 sunt numere întregi.
Limitele resurselor
10x 1 + 30x 2 ≤ 4500
25x 1 + 25x 2 ≤ 6250
41x 1 + 90x 2 ≤ 14100
90x 1 + 50x 2 ≤ 18000
Funcție obiectivă
100x 1 + 250x 2 → max

Să rezolvăm o problemă de programare liniară directă folosind metoda simplex. Ca rezultat, obținem următorul plan optim:

Bază	B	x 1	x 2	x 3	x 4	x 5	x 6
x 2	1450 / 11	0	1	41 / 330	0	-1 / 33	0
x 4	17500 / 11	0	0	245 / 66	1	-50 / 33	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0
x 6	6500	0	0	55 / 3	0	-20 / 3	1
F(X3)	422500 / 11	0	0	125 / 33	0	50 / 33	0

x 1 = 54 6 / 11 , x 2 = 131 9 / 11
F(X) = 250 131 9 / 11 + 100 54 6 / 11 = 38409 1 / 11

Planul optim rezultat nu este întreg, așa că folosim metoda Gomori. Cea mai mare parte fracțională se află în a doua ecuație pentru variabila x 4 (10 / 11). Creăm o restricție suplimentară:
q 2 - q 21 x 1 - q 22 x 2 - q 23 x 3 - q 24 x 4 - q 25 x 5 - q 26 x 6 ≤0
q 2 = b 2 - = 1590 10 / 11 - 1590 = 10 / 11
q 2 1 = a 2 1 - = 0 - 0 = 0
q 2 2 = a 2 2 - = 0 - 0 = 0
q 2 3 = a 2 3 - = 3 47 / 66 - 3 = 47 / 66
q 2 4 = a 2 4 - = 1 - 1 = 0
q 2 5 = a 2 5 - = -1 17 / 33 + 2 = 16 / 33
q 2 6 = a 2 6 - = 0 - 0 = 0

10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 ≤ 0

10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 + x 7 = 0

Deoarece metoda dual simplex folosit pentru a găsi minimul funcție obiectivă, facem transformarea F(x) = -F(X).

Bază	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	1450 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	17500 / 11	0	0	245 / 66	1	-50 / 33	0	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	55 / 3	0	-20 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F(X0)	-422500 / 11	0	0	-125 / 33	0	-50 / 33	0	0

Prima iterație a lui Gomori. 1. Verificarea criteriului de optimitate. Planul dintr-un tabel simplex este un pseudo-plan, așa că determinăm rândul și coloana de început.
2. Definirea unei noi variabile libere. Dintre valorile negative ale variabilelor de bază, o selectăm pe cea mai mare în valoare absolută. Linia principală va fi a cincea linie, iar variabila x 7 ar trebui derivată din bază.
3. Definirea unei noi variabile de bază. Valoarea minimă a lui θ corespunde celei de-a cincea coloane, adică. variabila x 5 trebuie introdusă în bază. La intersecția rândului și coloanei principale există un element de rezoluție (RE) egal cu (-16 / 33).

Bază	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	131 9 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	1590 10 / 11	0	0	3 47 / 66	1	-1 17 / 33	0	0
x 1	54 6 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	18 1 / 3	0	-6 2 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F(X0)	-38409 1 / 11	0	0	-3 26 / 33	0	-1 17 / 33	0	0
θ		-	-	-3 26 / 33: (-47 / 66) = 5 15 / 47	-	-1 17 / 33: (-16 / 33) = 3 1 / 8	-	-

4. Recalculăm tabelul simplex folosind metoda Jordano-Gauss.

Bază	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16
x 4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16
x 6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4
x 5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16
F(X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8

Planul optim rezultat conține numere fracționare. Folosind prima ecuație cu variabila x2, care a primit o valoare non-întreg în planul optim cu cea mai mare parte fracțională 7/8, creăm o constrângere suplimentară:
q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 ≤0
q 1 = b 1 - = 131 7 / 8 - 131 = 7 / 8


q 1 3 = a 1 3 - = 27 / 160 - 0 = 27 / 160



q 1 7 = a 1 7 - = -1 / 16 + 1 = 15 / 16
O restricție suplimentară are forma:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 ≤ 0
Să transformăm inegalitatea rezultată în ecuația:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 + x 8 = 0
ai căror coeficienţi îi introducem ca linie suplimentară în optim tabel simplex.

Bază	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8	0
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4	0
x 5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F(X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8	0

A doua iterație a lui Gomroya. 1. Verificarea criteriului de optimitate. Planul dintr-un tabel simplex este un pseudo-plan, așa că determinăm rândul și coloana de început.
2. Definirea unei noi variabile libere. Dintre valorile negative ale variabilelor de bază, cea mai mare în valoare absolută este variabila x8. Ar trebui să fie derivat din bază.
3. Valoarea minimă a lui θ corespunde celei de-a șaptea coloane, adică. variabila x 7 trebuie introdusă în bază.

Bază	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	131 7 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	1593 3 / 4	0	0	5 15 / 16	1	0	0	-3 1 / 8	0
x 1	54 3 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	6512 1 / 2	0	0	28 1 / 8	0	0	1	-13 3 / 4	0
x 5	1 7 / 8	0	0	1 15 / 32	0	1	0	-2 1 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F(X0)	-38406 1 / 4	0	0	-1 9 / 16	0	0	0	-3 1 / 8	0
θ		-	-	-1 9 / 16: (-27 / 160) = 9 7 / 27	-	-	-	-3 1 / 8: (-15 / 16) = 3 1 / 3	-

4. Efectuați transformarea New Gomori cut.

Bază	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15
x 4	4790 / 3	0	0	13 / 2	1	0	0	0	-10 / 3
x 1	271 / 5	1	0	-11 / 25	0	0	0	0	1 / 5
x 6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3
x 5	19 / 5	0	0	46 / 25	0	1	0	0	-11 / 5
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-16 / 15
F(X0)	-115210 / 3	0	0	-1	0	0	0	0	-10 / 3

Planul optim conține numere fracționale. Cea mai mare parte fracțională a variabilei este x 2 (14 / 15). Creăm o constrângere suplimentară: q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 - q 18 x 8 ≤0
q 1 = b 1 - = 131 14 / 15 - 131 = 14 / 15
q 1 1 = a 1 1 - = 0 - 0 = 0
q 1 2 = a 1 2 - = 1 - 1 = 0
q 1 3 = a 1 3 - = 9 / 50 - 0 = 9 / 50
q 1 4 = a 1 4 - = 0 - 0 = 0
q 1 5 = a 1 5 - = 0 - 0 = 0
q 1 6 = a 1 6 - = 0 - 0 = 0
q 1 7 = a 1 7 - = 0 - 0 = 0
q 1 8 = a 1 8 - = -1 / 15 + 1 = 14 / 15
O restricție suplimentară are forma:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 ≤ 0
Să transformăm inegalitatea rezultată în ecuația:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 + x 9 = 0
ai căror coeficienți vor fi introduși ca o linie suplimentară în tabelul simplex optim.

Bază	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	4790 / 3	0	0	13 / 2	1	0	0	0	-10 / 3	0
x 1	271 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3	0
x 5	19 / 5	0	0	46 / 25	0	1	0	0	-11 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-16 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F(X0)	-115210 / 3	0	0	-1	0	0	0	0	-10 / 3	0

A treia iterație prin metoda Gomori. Variabila x 9 ar trebui derivată din bază. Valoarea minimă a lui θ corespunde celei de-a opta coloane, adică. variabila x 8 trebuie introdusă în bază.

Bază	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	131 14 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	1596 2 / 3	0	0	6 1 / 2	1	0	0	0	-3 1 / 3	0
x 1	54 1 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	6525 1 / 3	0	0	30 3 / 5	0	0	1	0	-14 2 / 3	0
x 5	3 4 / 5	0	0	1 21 / 25	0	1	0	0	-2 1 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-1 1 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F(X0)	-38403 1 / 3	0	0	-1	0	0	0	0	-3 1 / 3	0
θ		-	-	-1: (-9 / 50) = 5 5 / 9	-	-	-	-	-3 1 / 3: (-14 / 15) = 3 4 / 7	-

4. Efectuați conversia.

Bază	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	132	0	1	27 / 140	0	0	0	0	0	-1 / 14
x 4	1600	0	0	50 / 7	1	0	0	0	0	-25 / 7
x 1	54	1	0	-67 / 140	0	0	0	0	0	3 / 14
x 6	6540	0	0	234 / 7	0	0	1	0	0	-110 / 7
x 5	6	0	0	317 / 140	0	1	0	0	0	-33 / 14
x 7	2	0	0	27 / 70	0	0	0	1	0	-8 / 7
x 8	1	0	0	27 / 140	0	0	0	0	1	-15 / 14
F(X0)	-38400	0	0	-5 / 14	0	0	0	0	0	-25 / 7

Soluția s-a dovedit a fi întreagă. Planul întreg optim poate fi scris astfel: x 1 = 54, x 2 = 132. F(X) = 38400

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ă liniară programare cu numere întregi 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 faptul că clasicul problema de transportși alte probleme de tip transport „automat” oferă o soluție la problema în numere întregi (dacă, desigur, parametrii condițiilor sunt întregi). Totuși, în cazul general, condiția întreg (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. Cel mai simplu dintre ele este metoda normala 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 a numerelor î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 ultima etapă a soluției sale metoda simplex se obţin următoarele ecuaţii exprimând 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 întregi, atunci este 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: mai puțin mașini puternice tip 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, cum ar fi Î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.

Se impune intocmirea unui plan optim de achizitie de echipamente care sa asigure maxim performanța generală cu condiția ca fermierul să poată achiziționa nu mai mult de 8 mașini 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ă reducem problema la formă canonică, introducând 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– zonă 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) – linie dreaptă, tăierea aceasta nu este soluție întreagă; 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 corespunzătoare funcție liniară

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

acceptă 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 valabil solutie de baza este necesara convertirea in variabila principala, care este inclusa cu un coeficient pozitiv in ecuatia in care termenul liber este negativ, i.e. 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ă. performanță maximă 25 de tone de cereale de înaltă calitate pe schimb pot fi obținute 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, rămâne Bani dintre cele alocate sunt egale cu zero, în rezerva de cumpărare - 1 utilaj 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. Sunt destui un numar mare de Bușteni de 3 m lungime. 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 prin fiecare metodă, astfel încât bucăți de orice tip să se obțină 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 acestea se pot obține 2xj +x2 semifabricate 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ă singuri), 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.

Coborarea decizie ulterioară probleme folosind metoda simplex (sugerăm ca elevii să facă acest lucru singuri), 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ă solutii optime(oricare, 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 valorile 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ă.

De obicei, problemele de programare liniară nu necesită coordonatele planului să fie numere întregi. Cu toate acestea, în practică se întâlnesc adesea probleme în care coordonatele planurilor optime trebuie să fie numere întregi, iar astfel de probleme se numesc probleme . La rezolvarea problemelor de programare liniară folosind metoda grafică și metoda simplex, nu există nicio garanție că coordonatele planului optim vor fi numere întregi.

În unele cazuri, rezultatele pot fi rotunjite. De exemplu, dacă planul optim prevede că ar trebui produse 499683,3 mașini, atunci este justificat din punct de vedere economic să rotunjim rezultatul la 499683 sau chiar la 500000.

Există, totuși, probleme în care o astfel de rotunjire poate crea o eroare mare. De exemplu, dacă planul optim prevede că ar trebui construite 0,67 centrale, atunci rotunjirea formală la 0 sau 1 este inacceptabilă.

Prin urmare, metodele de rezolvare a problemelor de programare liniară au o mare importanță practică, cu ajutorul cărora puteți găsi planul optim, ale cărui coordonate sunt numere întregi. Sarcini programare cu numere întregi sunt rezolvate folosind exact aceste metode.

Dacă problema de programare cu numere întregi dat în formă canonică, se formulează după cum urmează:

găsiți maximul funcției obiectiv (forma liniară)

cu un sistem de restricţii

Astfel, sarcina programare cu numere întregi iar problema de programare liniară corespunzătoare diferă doar în condiția ca necunoscutele să fie întregi.

Ca și problemele de programare liniară, problemele de programare cu numere întregi necesită ca planul optim să maximizeze funcția obiectiv (forma liniară).

Metoda Gomori pentru rezolvarea problemelor de programare cu numere întregi

metoda Gomori este o metodă universală de rezolvare a problemelor de programare cu numere întregi, cu care, după un număr finit de iterații, puteți găsi planul optim sau vă puteți asigura că problema nu are soluții. Cu toate acestea, valoarea practică a metodei lui Gomori este foarte limitată, deoarece trebuie efectuate destul de multe iterații atunci când se rezolvă probleme.

La rezolvarea problemelor de programare cu numere întregi folosind metoda Gomori, submulțimile care nu conțin planuri întregi sunt eliminate treptat din setul de planuri optime pentru o problemă de programare liniară.

La prima iterație, trebuie să rezolvați o problemă de programare liniară folosind metoda simplex. Dacă necunoscutele găsite satisfac cerința întregului, atunci problema de programare a întregului este rezolvată. Dacă printre necunoscutele găsite, cel puțin unul este un număr fracționar, atunci ar trebui creată o condiție suplimentară (cum să o compuneți - mai multe despre cele de mai jos) și atașată sistemului de constrângeri al problemei de programare a întregilor. Astfel, din setul de planuri se elimina submultimea care nu contine planuri intregi. Dacă planul optim al problemei augmentate în acest fel este întreg, atunci problema de programare a întregului este rezolvată. Procesul de rezolvare continuă până când la o iterație este găsit un plan optim întreg sau se poate verifica că problema nu are soluție.

Acum să vorbim despre cum să creăm condiția suplimentară menționată. Ea, o condiție suplimentară, se obține dintr-una dintre ecuațiile sistemului de restricții din coeficienții necunoscutelor și necunoscutelor în sine conform formulei

, unde în paranteze sunt părțile fracționale ale termenului liber și, respectiv, coeficienții necunoscutelor.

De exemplu, dintr-un tabel simplex obținem următoarea ecuație:

.

Obținem partea fracțională a termenului liber scăzând partea sa întreagă din numărul însuși, după cum urmează:

În mod similar, obținem părțile fracționale ale coeficienților pentru necunoscutele:

(la X3 ),

(la X4 ).

Și regula generală pentru găsirea părților fracționale este următoarea: prin partea întreagă a unui număr real A Cel mai mare număr întreg se numește [ A], fara sa depaseasca A; parte fracțională a unui număr real A numita diferenta {A} = A - [A] numărul în sine Ași întreaga ei parte [ A] .

.

În exemplul nostru, folosind formula de mai sus, se obține următoarea ecuație:

.

Exemplul 1. Rezolvați următoarea problemă de programare cu numere întregi folosind metoda Gomori. Aflați maximul funcției obiectiv

cu un sistem de restricţii

Soluţie. Rezolvăm problema folosind metoda simplex. Din moment ce avem lecție despre rezolvarea problemelor de programare liniară folosind metoda simplex, metoda în sine nu va fi explicată aici, ci vor fi date numai tabele simplex.

Necunoscute suplimentare X3 Și X4 Să o luăm ca de bază. Să exprimăm necunoscutele de bază și funcția scop prin variabile nebazice:

Să creăm un tabel simplex din coeficienți:

Alcătuim următoarele tabele până când obținem planul optim:

Tabelul 3
Necunoscute de bază	Membri gratuiti	Necunoscute gratuite		Coeficienți auxiliari
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
CU	65/7	10/7	1/7	1/2

Din tabelul 3 găsim planul optim . Deoarece acest plan optim nu satisface condiția întregului, trebuie să creăm o condiție suplimentară. Partea fracționară a coordonatei este numărul, iar partea fracțională a coordonatei este numărul.

Prima ecuație bazată pe tabel va fi scrisă după cum urmează:

.

După ce am determinat părțile fracționale ale coeficienților pentru necunoscutele și termenii liberi, obținem următoarea condiție suplimentară:

sau, prin introducerea unei variabile suplimentare,

.

Obținem un nou rând în tabelul simplex obținut din tabelul 3 și adunând coeficienții din ecuația tocmai obținută:

Tabelul 4
Necunoscute de bază	Membri gratuiti	Necunoscute gratuite		Coeficienți auxiliari
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
X5	-5/7	-4/7	-6/7
CU	65/7	10/7	1/7	1/2

Finalizăm pasul metodei simplex și obținem tabelul:

Tabelul 5
Necunoscute de bază	Membri gratuiti	Necunoscute gratuite		Coeficienți auxiliari
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
CU	55/6	4/3	1/6	-1/7

Am primit planul optim . Acest plan, ca și cel precedent, nu satisface condiția întregului. Prin urmare, este necesară din nou o condiție suplimentară. În acest caz, puteți utiliza prima sau a treia ecuație. Primim următoarea condiție suplimentară:

.

Să creăm următorul tabel:

Tabelul 6
Necunoscute de bază	Membri gratuiti	Necunoscute gratuite		Coeficienți auxiliari
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
X6	-5/6	-2/3	-5/6
CU	55/6	4/3	1/6	-1/7

Planul optim obținem din următorul tabel final:

Tabelul 7
Necunoscute de bază	Membri gratuiti	Necunoscute gratuite		Coeficienți auxiliari
		X3	X6
X1	3	4/5	-1/5	1/6
X2	0	-3/5	2/5	-1/3
X4	2	8/5	-7/5	7/6
X5	1	4/5	-6/5
CU	9	6/5	1/5	-1/6

Deoarece planul optim găsit satisface condiția întregului, problema de programare a întregului este rezolvată. Coordonatele X5 Și X6 poate fi ignorat, deoarece condițiile inițiale ale problemei conțin doar patru necunoscute. Prin urmare, planul optim final va fi scris după cum urmează:

,

iar maximul funcției obiectiv este 9.

Metoda ramificată și legată pentru rezolvarea problemelor de programare cu numere întregi

Metoda ramurilor și legate este convenabilă pentru rezolvarea problemelor de programare cu numere întregi în care numărul de necunoscute este mic sau cerințele întregului nu se aplică tuturor necunoscutelor. Esența metodei ramificații și legate este aceea că, pentru acele necunoscute cărora li se aplică cerința numărului întreg, este necesar să se determine limitele în care se pot afla valorile acestor necunoscute. Apoi se rezolvă problemele de programare liniară corespunzătoare.

Specificarea limitelor în care trebuie să se afle valorile necunoscutelor într-o problemă de programare cu numere întregi poate fi scrisă după cum urmează:

În practică, în multe cazuri, limitele valorilor necunoscute sunt deja incluse în sistemul de constrângeri ale problemei de programare cu numere întregi sau pot fi determinate pe baza conținutului economic al problemei. În caz contrar, putem presupune că limita inferioară este , iar limita superioară este , unde M- un număr pozitiv destul de mare.

Cum ajută metoda ramificată și legată la clarificarea limitelor valorilor acceptabile ale necunoscutelor?

În primul rând, o problemă de programare liniară corespunzătoare unei probleme de programare cu numere întregi este rezolvată, de exemplu, folosind metoda simplex. Să se găsească planul optim în această problemă și valoarea oricăreia dintre coordonatele sale să fie un număr fracționar. Apoi va trebui să creați două noi probleme de programare liniară. Cum să o facă?

Să notăm partea întreagă a coordonatei ca . Într-una dintre noile probleme de programare liniară, limita inferioară a valorii coordonatei va fi numărul , adică partea întreagă a valorii coordonatei mărită cu unu. Se va scrie astfel:

.

Într-o altă problemă nouă de programare liniară, limita superioară a valorii coordonatei va fi partea întreagă a valorii coordonatei în sine. Se va scrie astfel:

Astfel, două noi probleme „s-au ramificat” din prima problemă de programare liniară, în care limitele valorilor permise ale unei necunoscute s-au schimbat. Când rezolvați fiecare dintre aceste probleme, sunt posibile trei cazuri:

• planul optim nu este un număr întreg,
• planul optim este întreg,
• problema nu are solutii.

Numai în primul caz este posibil să „ramificați” sarcini noi în modul arătat mai sus. În al doilea și al treilea caz, „ramificarea” se oprește.

La fiecare iterație de rezolvare a unei probleme de programare cu numere întregi, se rezolvă o problemă. Să introducem conceptul: o listă de probleme de programare liniară de rezolvat. Din listă, selectați problema de rezolvat la iterația corespunzătoare. La iterații ulterioare, lista se modifică, deoarece problemele rezolvate nu mai sunt incluse în ea și, în locul lor, sarcini noi care s-au „ramificat” de la sarcinile anterioare sunt incluse în listă.

Pentru a limita „ramificarea”, adică pentru a reduce numărul de probleme de rezolvat, la fiecare iterație este necesară determinarea limitei inferioare a valorii maxime a funcției obiectiv. Acest lucru se face după cum urmează:

Conform algoritmului de rezolvare a unei probleme de programare cu numere întregi folosind metoda ramificației și legaturilor, pe fiecare p A treia iterație necesită 4 pași.

Exemplul 2. Rezolvați următoarea problemă de programare cu numere întregi folosind metoda ramurilor și legate. Aflați maximul funcției obiectiv

cu un sistem de restricţii

Soluţie. Să presupunem că următoarele limite ale valorilor optime ale necunoscutelor sunt date sau determinate:

.

Deoarece problema este dată în formă normală, are un plan întreg și o limită inferioară a valorii maxime a funcției obiectiv.

Lista sarcinilor de rezolvat include prima sarcină:

Iterația 1.

Pasul 1. Prin utilizarea metoda simplex s-a obtinut solutia primei probleme:

Deoarece planul găsit nu este un întreg, urmează pasul 4.

Pasul 4. Deoarece planul optim are o coordonată fracțională de 1,2, atunci . Aplicând limitele pe valorile necunoscutelor primei probleme, obținem noi probleme. În a 2-a problemă, limita inferioară pentru este , iar în a 3-a problemă, limita superioară pentru este .

MINISTERUL EDUCAȚIEI AL FEDERATIEI RUSE

UNIVERSITATEA TEHNICĂ DE STAT KUZBASS

Departamentul de Informatică și Tehnologia Informației

SOLUȚIONAREA PROBLEMELOR DE PROGRAMARE LINEARĂ A ÎNTREGĂRI CU METODĂ GOMORI

Instrucțiuni metodologice și teme pentru orele practice ale cursului

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

Compilat de N.Yu Kolomarova

Aprobat în şedinţa compartimentului Procesul-verbal nr.5 din 30.11.99

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 legate de 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ă cu numere î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 componentele soluției optime există și altele neîntregi, atunci 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		se obține dintr-o linie suplimentară, apoi în
	z ij> 0

următorul tabel simplex va obține 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, necesită o suprafață de producție de 4 mp și asigură 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ă.

Este necesar să se creeze un plan optim de achiziție a echipamentelor care să asigure productivitate totală maximă.

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 modelul matematic al problemei:

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țională 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 o nouă problemă de programare liniară cu 3 constrângeri. 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 minimă a lui θ 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

linia, și nu de-a lungul liniei 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 scriem 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

Planul 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 atinge productivitatea maximă a utilajelor, egală cu 36 de tone de produse pe schimb. Economiile de numerar rezultate în valoare de 3 unități monetare. 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.

Esența metodelor de tăiere este că problema este mai întâi rezolvată fără condiția întregului. 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ă;

· trebuie să taie planul non-întreg optim găsit;

· nu trebuie 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 taie o parte din partea sa împreună cu coordonatele non-întregi din poligonul (poliedrul) soluțiilor, dar nu afectează niciunul dintre numerele întregi. punctele acestui poliedru. Ca urmare, noul poliedru de soluție conține toate punctele întregi conținute în poliedrul de soluție original și, în consecință, soluția optimă obținută cu acest poliedru va fi întreg (Fig. 6.24).

Unul dintre algoritmii de rezolvare a problemei de programare cu numere întregi liniare (6.59)…(6.62), propuși de Gomori, se bazează pe metoda simplex și folosește o metodă destul de simplă pentru a construi o limită corectă.

Orez. 6.18. Ilustrare grafică a unei soluții întregi

Fie ca problema de programare liniară (6.52)…(6.55) să aibă un optim final și la ultimul pas de rezolvare folosind metoda simplex obținem următoarele ecuații care exprimă principalele variabile prin variabile minore ale soluţiei optime

(6.56)

astfel încât soluția optimă a problemei (6.52)...(6.55) este , în care, de exemplu, β i− componentă neîntregătoare. În acest caz se poate dovedi că inegalitatea

format de i Ecuația sistemului (6.56), are toate proprietățile unei tăieturi corecte.

În inegalitatea (6.57) există un simbol care indică partea fracționară a numărului. Număr A numit congruent cu un număr V(notat cu ) dacă și numai dacă diferența A- V− întreg.

Parte întreagă a unui număr A este cel mai mare număr întreg care nu depășește A. Partea fracționară a unui număr este definită ca diferența dintre acest număr și partea sa întreagă, adică. . De exemplu, pentru = 2, ; pentru = -3 și .

Pentru a rezolva problema de programare liniară cu numere întregi (6.52)…(6.55) folosind metoda Gomori, se folosește următorul algoritm:

1. Folosind metoda simplex, rezolvați problema (6.52)…(6.55) fără a lua în considerare condiția întregului. Dacă toate componentele planului optim sunt numere întregi, atunci este optim pentru problema de programare a întregului (6.52)…(6.55). Dacă prima problemă (6.52)…(6.54) este de nerezolvat (adică nu are un optim final sau condițiile sale sunt contradictorii), atunci a doua problemă (6.52)…(6.55) este de asemenea nerezolvabilă.

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 (6.56), formați limita corectă (6.57).

3. Prin introducerea unei variabile întregi nenegative suplimentare, transformați inegalitatea (6.57) într-o ecuație echivalentă

și includeți-l în sistemul de restricții (6.53).

4. Rezolvați problema extinsă rezultată folosind metoda simplex. Dacă planul optim găsit este întreg, atunci problema de programare a întregului (6.52)…(6.55) 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.

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

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 variabile suplimentare (exprimând cantitatea de resurse neutilizate, care poate fi fracţional).

Rețineți că trecerea la forma canonică într-o problemă de programare liniară completă, care conține constrângeri - inegalități

nu conduce, în general, la o problemă complet întreagă în formă canonică, deoarece în constrângerile transformate (6.59)

variabile auxiliare xn+i nu sunt supuse cerinței numărului întreg.

Cu toate acestea, dacă toți coeficienții a ij, b iîn (6.59) sunt numere întregi, atunci condiția întregului poate fi extinsă la xn+i, așa cum sa făcut în rezolvarea Exemplului 6.10.

O problemă complet întreagă în formă canonică poate fi obținută și dacă în (6.59) a ij, b i− numere raţionale. Pentru aceasta, înmulțiți (6.59) cu multiplu comun al numitorilor coeficienților − a ij, b i(adică, mergeți la coeficienți întregi din (6.59)) și numai după aceea introduceți variabile auxiliare.

Exemplul 6.20. Rezolvați o problemă de programare cu numere întregi

sub restricții

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

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

Orez. 6.19. Ilustrare grafică a soluției problemei

În fig. 6,19 0 KLM– zona de soluții fezabile la problemă 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 ; (4) – o linie dreaptă care taie această soluție neîntregătoare; 0 KNM– regiunea soluțiilor fezabile ale problemei extinse (6.64") N(2; 7) – punctul soluției întregi optime.

Pasul I

	X 1	X 2
X 3
X 4
X 5

Prima soluție de bază X 1 = (0;0;60;34;8) – acceptabil. Valoarea funcției liniare corespunzătoare f 1 = 0.

Conversia variabilei în variabilele principale X 2, care este inclusă în expresia funcției liniare cu cel mai mare coeficient pozitiv. Găsirea valorii maxime posibile a variabilei X 2, care ne permite să acceptăm un sistem de restricții, din condiția minimului relațiilor corespunzătoare:

,

acestea. ecuația de rezolvare (evidențiată) este a treia. La X 2 = 8 în această ecuație X 5 = 0 și merge la variabile non-principale X 5 .

Pasul II. Variabile de bază; variabile non-core.

	X 1	X 5
X 3		-5
X 4		-4
X 2
		-3	-24

X 2 = (0;8;20;2;0); f= 24. Convertiți în variabile principale X 1 , , și în non-core X 4 .

Sh pas. Variabile de bază; variabile non-core. După transformări obținem:

	X 4	X 5				X 4	X 5
X 3	-3	-3		X 3	-1	-1
X 1		-4		X 1	1/3	-4/3	2/3
X 2				X 2
	-2	-1	-76		-2/3	-1/3	-76/3

Soluție de bază X 3 este optim pentru sarcină , deoarece în expresia unei funcții liniare nu există variabile nebazice cu coeficienți pozitivi.

Totuși, soluția X 3 nu satisface condiția întregului (6.55"). Conform primei ecuații cu variabila X 1 , care a primit o valoare non-întreg în soluția optimă (2/3), creăm o constrângere suplimentară (6.57):

Atragem atenția că, conform (6.56) și (6.57), luăm partea fracționară a termenului liber cu același semn pe care îl are în ecuație și părțile fracționale ale coeficienților pentru variabile minore. X 4 și X 5 – cu semne opuse.

Deoarece părți fracționale

apoi scriem ultima inegalitate sub forma

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

Ecuația (6.58) trebuie inclusă în sistemul de constrângeri (6.56") 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 în sistem a unei ecuații suplimentare (6,58"), obținută la ultimul pas de rezolvare a problemei (fără condiția întregului).

Pasul IV. Variabile de bază; variabile non-core.

	X 4	X 5
X 1	1/3	-4/3	2/3
X 2
X 3	-1	-1
X 6	-1/3	-2/3	-2/3
	-2/3	-1/3	-76/3

Soluție de bază − inacceptabil. 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 4 sau X 5 (în această etapă nu luăm în considerare funcția liniară). Traducem în cele de bază, de exemplu, o variabilă X 5 .

Pasul V. Variabile de bază; variabile non-core. După transformări obținem:

	X 4	X 6				X 4	X 6
X 1	-6/9	4/3	-12/9	X 1		-2
X 2	1/3	-1	-14/3	X 2	-1/2	3/2
X 3	1/3		38/3	X 3	-1/2	-3/2
X 5	-1/3		-2/3	X 5	1/2	-3/2
	3/9	1/3	150/9		-1/2	-1/2	-25

X 5 = (2;7;19;0;1;0); f 5 = 25.

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

Asa de, f max = 25 cu o soluție întreagă optimă A șasea componentă nu are sens.

Pentru interpretarea geometrică pe planul 0 X 1 X 2 (vezi Fig. 6.19) limite (6.57") variabilele necesare incluse în acesta X 4 și X 5 exprima prin variabile X 1 și X 2. Obținem (vezi a 2-a și a 3-a ecuație ale sistemului de restricții (6.56"):

(vezi linia de tăiere (4) în Fig. 6.19).