Szczegółowe rozwiązanie online metody Gomori. Rozwiązywanie problemów programowania liczb całkowitych: metody i przykłady

MINISTERSTWO EDUKACJI FEDERACJI ROSYJSKIEJ

PAŃSTWOWY UNIWERSYTET TECHNICZNY KUZBASS

Dział technologia komputerowa i technologii informatycznych

ROZWIĄZYWANIE PROBLEMÓW PROGRAMOWANIA LINIOWEGO CAŁKOWITYCH METODĄ GOMORI

Wytyczne i zadania dot zajęcia praktyczne według stawki

„Metody ekonomiczne i matematyczne” dla studentów kierunków ekonomicznych

Opracowane przez N.Yu.Kolomarova

Zatwierdzono na posiedzeniu wydziału Protokół nr 5 z 30.11.99

Egzemplarz elektroniczny znajduje się w bibliotece gmachu głównego KuzSTU

Kemerowo 2000

1. ZASTRZEŻENIE PROBLEMU

Istnieje wiele problemów planowania optymalnego, w których zmienne mogą przyjmować tylko wartości całkowite. Zadania takie związane są z określeniem liczby jednostek niepodzielnych produktów, liczby maszyn podczas załadunku sprzętu, liczby pracowników w działach strukturalnych przedsiębiorstwa itp. Dość często pojawiają się problemy z tzw. zmiennymi boolowskimi, których rozwiązaniami są sądy typu „tak-nie”. Jeśli funkcja i ograniczenia w takich problemach są liniowe, to mówimy o problemie liniowym programowanie całkowite.

Sformułowano liniowy problem programowania liczb całkowitych

następująco: znaleźć takie rozwiązanie (plan)

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

bierze maksimum lub minimalna wartość pod ograniczeniami

2. METODA GOMORIEGO

Jedną z metod rozwiązywania problemów programowania liniowego liczb całkowitych jest metoda Gomoriego. Istotą tej metody jest konstruowanie ograniczeń odcinających niecałkowite rozwiązania problemu Programowanie liniowe, ale nie odcinając żadnego planu liczb całkowitych.

Rozważmy algorytm rozwiązywania liniowego problemu programowania liczb całkowitych przy użyciu tej metody.

1. Rozwiązanie problemu metoda simplex bez uwzględnienia warunku całkowitego. Jeśli wszystkie elementy planu optymalnego są liczbami całkowitymi, wówczas jest on optymalny dla problemu programowania liczb całkowitych. Jeśli okaże się, że problem jest nierozwiązywalny, problem programowania liczb całkowitych również jest nierozwiązywalny.

2. Jeżeli wśród składników rozwiązania optymalnego znajdują się składniki niecałkowite, to do ograniczeń problemu dodajemy nowe ograniczenie, które ma następujące właściwości:

Powinno być liniowe; - musi odciąć znalezioną optymalną liczbę niecałkowitą

plan; - nie może odcinać żadnego planu całkowitego.

Aby skonstruować ograniczenie, wybieramy element planu optymalnego z największymi część ułamkowa i korzystając z k-tego wiersza tabeli simplex odpowiadającego temu komponentowi, zapisujemy ograniczenie Gomoriego.

		fa k = ∑	fa kj x jot – S *, S * ≥ 0 ,
gdzie f k	Xj-;
	Zkj - ;
		Nowa zmienna;
Najbliższa liczba całkowita nieprzekraczająca odpowiednio x j i z kj
		Utworzone ograniczenie dodajemy do tych dostępnych w symulatorze

złożoną tabelę, uzyskując w ten sposób rozszerzony problem. Pozyskać planie referencyjnym tego problemu, należy wejść w podstawę, że

	wektor, dla którego ilość				∆ j		minimalny. A jeśli w tym stuleciu -
					f kj
	wartość torusa θ = min		jest uzyskiwany z dodatkowej linii, a następnie in
	z ij> 0

Następny stół simpleksowy uzyskany zostanie plan referencyjny. Jeśli wartość θ nie odpowiada dodatkowej linii, jest to konieczne

przejdź do problemu M (wprowadź sztuczną zmienną do ograniczenia Gomoriego).

4. Rozwiąż za pomocą zwykłego transformacje simpleksowe otrzymane zadanie. Jeśli rozwiązanie tego problemu prowadzi do optymalnego planu całkowitego, wówczas pożądany problem zostaje rozwiązany. Jeśli nie otrzymaliśmy rozwiązanie całkowite, następnie ponownie dodajemy jedno dodatkowe ograniczenie i proces obliczeń się powtarza. Po wykonaniu skończonej liczby iteracji albo otrzymujemy optymalny plan problemu programowania liczb całkowitych, albo stwierdzamy jego nierozwiązywalność.

Uwagi:

1. Jeśli dodatkowa zmienna S * jest uwzględniany w podstawie, następnie po ponownym obliczeniu każdego kolejnego planu odpowiedni wiersz i kolumnę można usunąć (w ten sposób zmniejszając wymiar problemu).

2. Jeśli dla ułamka x j okazuje się, że wszystkie współczynniki odpowiedniego równania (wiersza) są liczbami całkowitymi, wówczas problem nie ma rozwiązania całkowitego.

3. PRZYKŁADY ROZWIĄZANIA PROBLEMÓW METODĄ GOMORI

Zadanie: Na zakup nowego sprzętu firma przeznacza 19 jednostek pieniężnych. Sprzęt należy umieścić na powierzchni nieprzekraczającej 16 m2. Przedsiębiorstwo może zamówić dwa rodzaje sprzętu: maszyny typu „A” kosztujące 2 jednostki pieniężne, wymagające powierzchni produkcyjnej 4 m2 i zapewniające wydajność 8 ton produktów na zmianę oraz maszyny typu „B” kosztuje 5 jednostek pieniężnych, zajmuje powierzchnię 1 m2 i zapewnia wydajność 6 ton produktów na zmianę.

Wymagane jest opracowanie optymalnego planu nabycia sprzętu, który zapewni maksimum Całkowita wydajność.

Rozwiązanie: Oznaczmy przez x 1 , x 2 liczbę maszyn odpowiednio „A” i „B”, a przez L - ich całkowitą produktywność. Następnie model matematyczny zadania:

maks. dł. = 8 x1 +6 x2

z ograniczeniami:

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

x1, x2 - liczby całkowite

Problem rozwiązujemy metodą sympleksową bez uwzględnienia wartości całkowitych.

	∆ j
	∆ j
	∆ j

Otrzymano optymalny niecałkowity plan X opt = (61/18;22/9).

Lmaks. = 376/9.

Ponieważ składnik planu x 2 ma maksymalną część ułamkową: max(4/9;7/18) = 4/9, wówczas w pierwszej linii zapisujemy dodatkowe ograniczenie.

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 - pierwsze ograniczenie Gomoriego

Dodajemy utworzone ograniczenie do istniejących w tabeli simplex.

Po skonstruowaniu dodatkowego ograniczenia mamy nowy problem programowania liniowego z 3 ograniczeniami. Aby uzyskać plan odniesienia dla tego problemu, należy znaleźć trzecią bazę

nowy wektor. W tym celu definiujemy: min
	f kj

podstawie wprowadzamy wektor x 4.							4 / 9
Obliczamy wartość θ =
	z ij> 0						8 / 9

Z dodatkowej prostej uzyskano minimalną wartość θ, co oznacza, że ​​bez uciekania się do sztucznej zmiennej otrzymujemy plan odniesienia rozszerzonego problemu.

	∆ j

Znaleziony plan jest optymalny, ale niecałkowity. Budujemy nowe ograniczenie Gomori.

Ponieważ maksymalna część ułamkowa pomiędzy składnikami planu wynosi 1/2, wpisz dodatkowe ograniczenie w pierwszym wierszu (można też w trzecim).

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 - drugie ograniczenie Gomoriego

Dodajemy to ograniczenie do ostatniej tabeli simplex.

Otrzymaliśmy zadanie w którym występują 4 więzy, zatem w bazie powinny znajdować się 4 wektory jednostkowe.

								2. Móc

wpisz x 3 lub S 1 . Wprowadźmy wektor S 1 .

1/ 2

4 / 7

odpowiada dodatkowym

7 / 8

ograniczenie.

∆ j

Otrzymujemy nowy optymalny plan niecałkowity. Biorąc pod uwagę uwagę 1, przekreślamy wiersz i kolumnę odpowiadającą

zmienna S 1.

W powstałym planie maksimum część ułamkowa ma składową x 2, dlatego w pierwszej linii piszemy dodatkowe ograniczenie.

	4/7 = 2/7x3 + 6/7S2 - S3, S3 ≥ 0	Trzecie ograniczenie Gomoriego.
	Wyznaczamy wektor wprowadzony do bazy:

wektor x 3. Minimalna wartość θ = 2, co odpowiada dodatkowej linii.

Po wykonaniu kolejnych przekształceń simpleksowych otrzymaliśmy:

	∆ j

Plan X 5 jest optymalną liczbą niecałkowitą. W drugiej linii piszemy dodatkowe ograniczenie:

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

Czwarte ograniczenie Gomoriego.

Ponieważ składnikiem podstawowym może być S 3, określamy wartość

0. Minimalną wartość θ uzyskano przy 3

linii, a nie wzdłuż linii Gomoriego, zatem przechodzimy do problemu M:

wprowadźmy dodatkową zmienną x 5							do ograniczenia Gomoriego.
C5'	B5'	X5'
	∆ j

∆ j

∆ j

Część ułamkowa = maks. (1/3; 2/3) = 2/3

dodatkowe ograniczenie

Zapisujemy to w drugiej linijce.

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

S5 ≥

Piąte ograniczenie Gomori.

16 / 3

2 wpisz x 4.

Wektor wpisany do bazy: min

2 / 3

θ =

pasuje do linii Gomoriego.

∆ j

Plan X 8 = (3; 2; 3; 2) - optymalna liczba całkowita L max = 36.

Interpretacja ekonomiczna:Zgodnie z otrzymaną decyzją spółka potrzebuje zakupić 3 maszyny typu „A” i 2 maszyny typu „B”. W takim przypadku zostanie osiągnięta maksymalna wydajność sprzętu, równa 36 ton produktów na zmianę. Wynikające z tego oszczędności Pieniądze w ilości 3 den jednostek. można wysłać do każdy inne cele, na przykład premie dla pracowników, którzy będą debugować otrzymany sprzęt. Na nadmiarze 2 m2 możesz umieścić skrzynkę z kwiatami.

Geometryczna interpretacja metody Gomoriego: budujemy wiele

liczba planów (patrz rysunek). W punkcie 1 - optymalny plan niecałkowity.

Aby rozwiązać problemy z programowaniem liniowym na liczbach całkowitych Jakikolwiek numer zmiennych można zastosować metodę Gomoriego, za pomocą której z obszaru programu odcinane są punkty o niecałkowitych współrzędnych. Sformułujmy algorytm Gomoriego do rozwiązywania problemu programowania liniowego liczb całkowitych w postaci standardowej

Algorytm Gomoriego

GP Metodą simplex znajdujemy optymalny program. Jeśli otrzymasz wartości całkowite dla wszystkich Xj, wtedy problem zostanie rozwiązany. Inaczej wśród Xj istnieją wartości nieliczbowe.

|~2~1 Wśród liczb niecałkowitych Xj wybierz dowolny element x gł i dodaj kolejne ograniczenie do problemu

co jest równoznaczne z dodaniem jeszcze jednego wiersza do tabeli simplex, po czym nie odpowiada on już dopuszczalnemu rozwiązaniu bazowemu nowego problemu programowania liniowego, który opisuje. Ograniczenie wykorzystuje ułamkowe części elementów linii, w której się znajduje. x gł. Zapis części ułamkowej opiera się na fakcie, że każda liczba rzeczywista Na można przedstawić jako sumę Na = [y]+ (?у), gdzie [y] - cała część i (y) = U ~ [y] ~ frakcja.

[h] Znajdujemy dopuszczalne rozwiązanie podstawowe, rozważając Nowa linia zezwalający, tj. I = P + 1.

• a) Jeśli wszystkie współczynniki uc> 0, to problem nie ma rozwiązania (tzn. problem liczb całkowitych jest rozwiązany).
• b) W przeciwnym razie znajdź indeks Do takie, że

(kryterium wpisania nowej podstawy). Należy pamiętać, że wybór elementu rozdzielającego NaI* nie zmienia znaku kryterium Aj.

[4] Jeśli w nowy stół jest przynajmniej jeden x 3 i powtórz te procedury tyle razy, ile to konieczne.

[~5~| Jeśli wynikowe rozwiązanie optymalne jest liczbą całkowitą, problem jest rozwiązany. W przeciwnym razie musisz wrócić do punktu.

Przykład 4.6.1. Rozwiąż zadanie z liczbami całkowitymi, korzystając z metody Gomoriego

Rozwiązanie. Po dodaniu zmiennych pomocniczych mamy następujący problem programowania liniowego w postaci standardowej:

z matrycami

Tabela 1
	X4

Do= 1 T

Korzystając z metody rotacyjnej, wypełnij poniższe tabele. Element rozdzielczości - 6*.

Tabela 2				X 2
		„ _ 1 IZ ~_3_

k" = 2 T

Element rozdzielczości - 1/2*.

X w^0). Dlatego program (xi = 11/3, X 2 = 5) da maksimum funkcji ekonomicznej z, równe 1370/3 = 45b|, t.s. z= z maks. = 456§. "

Od tego optymalny program nie jest liczbą całkowitą, stosujemy algorytm Gomoriego, aby znaleźć optymalny program na liczbę całkowitą. Jako sznurek, na podstawie którego tworzymy dodatkowa linia Z części ułamkowych wszystkich elementów wybierz drugą linię (indeks 7’ = 1). Wypełnijmy tabelę 3”, dodając do tabeli 3 dodatkowy wiersz (4.14) z częściami ułamkowymi dla dodatkowej zmiennej Ж5 i dodatkową kolumnę. Otrzymujemy

k" = 4 T

Po dodaniu nowej linii tablica simpleksowa 3" nie odpowiada już dopuszczalnemu rozwiązaniu podstawowemu opisanego w niej problemu. Dopuszczalne rozwiązanie podstawowe znajdujemy, uznając nową linię za rozwiązującą, czyli /" = 5.

Znajdujemy kolumnę rozdzielczą, tj. indeks Do" takie, że

(kryterium wpisania nowej podstawy). Element rozdzielczości - (-2/3*). Należy pamiętać, że taki wybór elementu rozstrzygającego nie powoduje zmiany znaku kryterium Aj.

Wypełnijmy tabelę simplex 4.

Tabela 4				X2
	X2

Wartości wszystkich kryteriów ^ 0, ( X w^0). Dlatego program (xi = 3, x 2 = 6, x±= 1) daje maksimum funkcji ekonomicznej r równe 450, t.s. z = zma^= 450. Ten optymalny program jest liczbą całkowitą. ?

Przykład 4.6.2. Rozwiąż zadanie z liczbami całkowitymi, korzystając z metody Gomoriego

Rozwiązanie. Istnieje problem programowania liniowego z macierzami

Wypełnijmy tabelę simplex programem początkowym.

Tabela 1

Do= 1 T

Korzystając z metody rotacyjnej, wypełnij poniższe tabele. Element rozdzielczości - 1*.

Tabela 2				X2

Element dopuszczający - 5*.

Tabela 3

Wartości wszystkich kryteriów ^ 0, ( X w^0). W konsekwencji program (xi = 12/5, 24 = 1/5, 25 = 28/5) daje minimum funkcji ekonomicznej r równe -11/5 = -2,2, tj. z =

~min = -2.2.

Ponieważ ten optymalny program nie jest programem całkowitym, stosujemy algorytm Gomoriego, aby znaleźć optymalny program całkowitoliczbowy. Jako ciąg, na podstawie którego z części ułamkowych elementów ss tworzymy dodatkowy ciąg, wybieramy np. trzeci wiersz (indeks r = 5) z maksymalną częścią ułamkową. Wypełnijmy tabelę 3" dodając dodatkową linię (4.14) do tabeli 3 częściami ułamkowymi trzeciej linii dla dodatkowej zmiennej xq (linia ta umożliwia wycięcie z obszaru programu części zawierających punkty o nienumerycznych współrzędnych) oraz dodatkową kolumnę. Dostajemy

Tabela 3"
		G - -I

k" = 3 T

Po dodaniu nowej linii tablica simplex 3" nie odpowiada już dopuszczalnemu rozwiązaniu podstawowemu problemu, który opisuje. Dopuszczalne rozwiązanie podstawowe znajdujemy, uznając nową linię za rozwiązującą, tj. ja" = 6.

Znajdujemy kolumnę rozdzielczą, tj. indeks Do" takie, że

(kryterium wpisania nowej podstawy). Element rozdzielczości - (-3/5*). Należy pamiętać, że taki wybór elementu rozstrzygającego nie powoduje zmiany znaku kryterium Aj.

Wypełnijmy tabelę simplex 4.

Tabela 4

Wartości wszystkich kryteriów ^ 0, ( X w^0). Dlatego program (x = 2, X2 = 0, xs = 1, X 4 = 0, f 5 = 5) da minimum funkcji ekonomicznej z 9 równy (-2), t.s. z =-min = - 2. Ten optymalny program jest liczbą całkowitą. ?

Problem 4.6.1. Rozwiąż zadanie z liczbami całkowitymi, korzystając z metody Gomoriego

Odpowiedź. Program

daje minimum funkcji ekonomicznej z równe (-31), tj. z= 2 m i n = -31. Ten optymalny program jest programem całkowitym.

Zgodnie ze znaczeniem znacznej części problemów ekonomicznych związanych z problemami programowania liniowego, składniki rozwiązania muszą być wyrażone w liczbach całkowitych, tj. być liczbą całkowitą. Należą do nich np. problemy, w których zmienne oznaczają liczbę jednostek produktów niepodzielnych, liczbę maszyn przy załadunku sprzętu, liczbę statków przy dystrybucji wzdłuż linii, liczbę turbin w systemie elektroenergetycznym, liczbę komputery w kompleksie zarządzania i wielu innych.

Problem programowania liniowego w liczbach całkowitych jest sformułowany w następujący sposób: znaleźć takie rozwiązanie (plan) I, dla którego funkcja liniowa

przyjmuje wartość maksymalną lub minimalną w ramach ograniczeń

(8.2)

(8.3)

- wszystkie liczby. (8.4)

Warto zaznaczyć, że klasyk problemu transportu i kilka innych zadań rodzaj transportu„automatycznie” zapewniają rozwiązanie problemu w liczbach całkowitych (jeśli oczywiście parametry warunków są liczbami całkowitymi). Jednak w ogólnym przypadku warunek całkowity (8.4), dodany do zwykłych problemów programowania liniowego, znacznie komplikuje jego rozwiązanie.

Do rozwiązywania liniowych problemów programowania liczb całkowitych stosuje się wiele metod. Najprostszy z nich to normalna metoda Programowanie liniowe. Jeżeli składniki rozwiązania optymalnego nie są liczbami całkowitymi, zaokrągla się je do najbliższej liczby całkowitej. Metodę tę stosuje się, gdy pojedyncza jednostka populacji stanowi niewielką część objętości całej populacji. W przeciwnym razie zaokrąglenie może prowadzić do rozwiązania całkowitego, które jest dalekie od optymalnego, dlatego stosuje się specjalnie opracowane metody.

Metody optymalizacji liczb całkowitych można podzielić na trzy główne grupy: a) metody przycinania; b) metody kombinatoryczne; c) metody przybliżone. Przyjrzyjmy się bliżej metodom cięcia.

Metody przycinania. Metoda Gomoriego

Istota metod przycinania polega na tym, że problem jest najpierw rozwiązywany bez warunku integer™. Jeśli wynikowy plan jest liczbą całkowitą, problem został rozwiązany. W przeciwnym razie do ograniczeń zadania dodawane jest nowe ograniczenie o następujących właściwościach:

• musi być liniowy;
• powinien odciąć znaleziony optymalny plan niecałkowity;
• nie powinien odcinać żadnego planu całkowitego.

Nazywa się dodatkowe ograniczenie posiadające te właściwości prawidłowe cięcie.

Geometrycznie dodanie każdego więzu liniowego odpowiada narysowaniu linii prostej (hiperpłaszczyzny), która odcina jej część od wielokąta rozwiązania (wielościanu) wraz z optymalnym punktem o współrzędnych niecałkowitych, ale nie wpływa na żadną z liczb całkowitych punkty tego wielościanu. W rezultacie nowy wielościan rozwiązania zawiera wszystkie zawarte w nim punkty całkowite

w pierwotnym wielościanie rozwiązań, a zatem optymalne rozwiązanie otrzymane za pomocą tego wielościanu będzie liczbą całkowitą (ryc. 8.1).

Jeden z algorytmów rozwiązywania liniowego problemu programowania całkowitoliczbowego (8.1)-(8.4), zaproponowany przez R. Gomoriego, opiera się na metodzie sympleksowej i wykorzystuje dość prostą metodę konstruowania prawidłowego punktu odcięcia.

Niech problem programowania liniowego (8.1)-(8.3) ma ostateczne maksimum i tak dalej ostatni krok rozwiązując go metodą sympleksową otrzymaliśmy następujące równania wyrażające główne zmienne poprzez zmienne inne niż główne rozwiązania optymalnego:

(8.5)

zatem optymalnym rozwiązaniem problemu (8.1)-(8.3) jest i, w którym np. β; – składnik niecałkowity. W tym przypadku można udowodnić, że nierówność utworzona przez I- do równania układu (8.5), ma wszystkie właściwości regularnego odcięcia.

Aby rozwiązać problem programowania liniowego liczb całkowitych (8.1)-(8.4) metodą Gomoriego, stosuje się następujący algorytm.

• 1. Metodą sympleksową rozwiąż zadanie (8.1)-(8.3) bez uwzględnienia warunku całkowitego. Jeśli wszystkie składniki planu optymalnego są liczbami całkowitymi, wówczas jest on optymalny dla problemu programowania liczb całkowitych (8.1)-(8.4). Jeżeli pierwszy problem (8.1)-(8.3) jest nierozwiązywalny (to znaczy nie ma optymalnego finalu lub jego warunki są sprzeczne), to drugi problem (8.1)-(8.4) również jest nierozwiązalny.
• 2. Jeżeli wśród składników rozwiązania optymalnego znajdują się składowe niecałkowite, to wybierz ten, który jest największy cała część i zgodnie z odpowiednim równaniem układu (8.5) utwórz poprawną granicę (8.6).
• 3. Wprowadzając dodatkową nieujemną zmienną całkowitą, przekształć nierówność (8.6) w równanie równoważne i uwzględnij ją w systemie ograniczeń (8.2).
• 4. Rozwiązać otrzymany rozszerzony problem metodą sympleksową. Jeśli znaleziony optymalny plan jest liczbą całkowitą, wówczas problem programowania liczb całkowitych (8.1)–(8.4) jest rozwiązany. W przeciwnym razie wróć do kroku 2 algorytmu.

Jeśli problem można rozwiązać w liczbach całkowitych, to później skończoną liczbą kroków (iteracji), zostanie znaleziony optymalny plan liczb całkowitych.

1 W nierówności (8.6) występuje symbol ( ), oznaczający część ułamkową liczby. Część całkowita liczby a jest największą liczbą całkowitą [w] nieprzekraczającą a, część ułamkowa liczby– liczba (a), równa różnicy między tą liczbą a jej częścią całkowitą, tj. (a) = a-[b].

Na przykład dla (uwaga, dokładnie -3, a nie -2) i

Jeżeli w procesie rozwiązywania pojawi się równanie (wyrażające zmienną główną w kategoriach niepodstawowych) z niecałkowitym wolnym terminem i pozostałymi współczynnikami całkowitymi, wówczas odpowiednie równanie nie ma rozwiązania w liczbach całkowitych. W tym przypadku i to zadanie nie ma rozwiązania optymalnego w postaci całkowitej.

8.1. Na zakup sprzętu do sortowania zboża rolnik przeznaczył 34 den. jednostki Sprzęt należy umieścić na powierzchni nieprzekraczającej 60 metrów kwadratowych. m. Rolnik może zamówić dwa rodzaje sprzętu: mniejszy potężne samochody typ A warte 3 den. jednostki wymagające powierzchni produkcyjnej 3 mkw. m (wraz z przejazdami) i wydajnością na zmianę 2 ton zboża oraz mocniejsze maszyny np W warte 4 den. lokale zajmujące powierzchnię 5 mkw. m i wydajność na zmianę 3 ton wysokiej jakości ziarna.

Należy sporządzić optymalny plan zakupu sprzętu zapewniający maksymalną ogólną produktywność, pod warunkiem, że rolnik będzie mógł zakupić nie więcej niż 8 maszyn tego typu W.

Rozwiązanie. Oznaczmy odpowiednio liczbą maszyn, typem A I W, do Z – produktywność ogólna. Wtedy matematyczny model problemu przyjmie postać

(!!!8.8)

z ograniczeniami:

(8.2)

- wszystkie liczby. (8.4)

Zmniejszmy problem do Forma kanoniczna, wprowadzając dodatkowe zmienne nieujemne. Otrzymujemy system ograniczeń:

(8.5)

Problem rozwiązujemy metodą simplex. Dla przejrzystości rozwiązanie zilustrujemy graficznie (ryc. 8.2).

Na ryc. 8.2 OKLM– regionu dopuszczalne rozwiązania problemy (8.D)–(8,3”), ograniczone liniami prostymi (1), (2), (3) i osiami współrzędnych; L(2/3; 8) – punkt optymalnego, ale niecałkowitego rozwiązania problemu (8,1”)–(8,3”); (4) – prosta odcinająca to niecałkowite rozwiązanie; OKNM– obszar możliwych rozwiązań rozszerzonego problemu (8,1") – (8,3"), (8,6"); N( 2; 7) – punkt optymalnego rozwiązania całkowitego.

Krok I. Zmienne podstawowe Zmienne niepodstawowe

Pierwszym podstawowym rozwiązaniem jest założenie

Mój. Odpowiednia wartość funkcja liniowa

Na zmienne główne zamieniamy zmienną, która jest zawarta w wyrażeniu funkcji liniowej o największym dodatnim współczynniku. Znajdujemy maksymalną możliwą wartość zmiennej, która „pozwala”

zaakceptować system ograniczeń oparty na warunku minimalnych odpowiednich relacji:

te. rozwiązujące (podświetlone) równanie jest trzecim. Na X. 2 = 8 w tym równaniu X- = 0, a zmienna przechodzi do wartości innej niż podstawowa X 5.

Krok II. Kluczowe zmienne X 2, X 3, X 4.

Drobne zmienne.g, xy

Po przekształceniach otrzymujemy

Konwertuj na zmienną główną i w innych niż główne x4.

III krok. Główne zmienne x, X 2, X 3.

Zmienne inne niż główne x4, x5.

Po przekształceniach otrzymujemy

Podstawowe rozwiązanie X., optymalne dla problemu (8,1") – (8,3") (), ponieważ w wyrażeniu funkcji liniowej

nie ma zmiennych niekluczowych o dodatnich współczynnikach.

Jednak rozwiązanie X 3 nie spełnia warunku całkowitego (8,4”) Wykorzystując pierwsze równanie, w którym zmienna x otrzymuje w rozwiązaniu optymalnym wartość niecałkowitą (2/3), tworzymy dodatkowe ograniczenie (8.6):

Należy pamiętać, że zgodnie z (8.5) i (8.6) bierzemy część ułamkową członek wolny z tym samym znakiem, które ma w równaniu i części ułamkowe współczynniki dla mniejszych zmiennych x 4 i x- – o przeciwnych znakach.

Ponieważ części ułamkowe ,

, piszemy ostatnią nierówność

(8.6")

Wprowadzając dodatkową zmienną całkowitą x6 ≥ 0, otrzymujemy równanie równoważne nierówności (8,6")

(8.7")

Równanie (8,7") należy włączyć do układu więzów (8,5") pierwotnego problemu kanonicznego, a następnie powtórzyć proces rozwiązywania problemu metodą sympleksową w odniesieniu do problemu rozszerzonego. W takim przypadku, aby zmniejszyć liczbę kroków (iteracji), zaleca się wprowadzenie do układu otrzymanego na ostatnim etapie rozwiązywania problemu dodatkowego równania (8,7”) (bez warunku całkowitego).

IV krok. Kluczowe zmienne X w X 2, x3, χβ.

Zmienne inne niż główne x4, x5.

Rozwiązanie podstawowe jest niedozwolone

Mój. (Zauważ, że po włączeniu dodatkowego równania odpowiadającego prawidłowemu odcięciu w układzie wiązań, zawsze otrzymane zostanie nieprawidłowe rozwiązanie bazowe.)

Aby uzyskać ważne podstawowe rozwiązanie należy dokonać konwersji na zmienną główną, która jest uwzględniona z dodatnim współczynnikiem w równaniu, w którym wolny wyraz jest ujemny, tj. x lub x. (na tym etapie nie rozważamy funkcji liniowej). Tłumaczymy na podstawowe, na przykład zmienną x5.

Krok V. Główne zmienne to x, x2, x3, x5.

Zmienne inne niż główne x4, x6.

Otrzymujemy po przekształceniach

Ponieważ w wyrażeniu funkcji liniowej nie ma zmiennych głównych o dodatnich współczynnikach X 5 jest rozwiązaniem optymalnym.

Zatem Zmax = 25 dla optymalnego rozwiązania całkowitego X* = X 5 = (2; 7; 19; 0; 1; 0), tj. maksymalna wydajność 25 ton wysokiej jakości zboża na zmianę można uzyskać kupując 2 maszyny typu L i 7 maszyn typu W Jednocześnie niezamieszkana powierzchnia lokalu wyniesie 19 metrów kwadratowych. m, saldo przydzielonych środków wynosi zero, rezerwa na zakup to 1 maszyna tego typu W(szósty składnik nie ma żadnego znaczącego znaczenia).

Komentarz. Do interpretacji geometrycznej na płaszczyźnie Ox, x2 (patrz rys. 8.2) odcięcia (8,6") niezbędne są zawarte w niej zmienne X 4 i X- wyrazić poprzez zmienne x i x2. Otrzymujemy (patrz drugie i trzecie równanie układu ograniczeń (8,5”))

• (patrz linia odcięcia (4) na ryc. 8.2).
• 8.2. Jest wystarczająco dużo duża liczba kłody o długości 3 m. Kłody należy pociąć na dwa rodzaje półfabrykatów o długości 1,2 i 0,9 m i uzyskać co najmniej 50 i 81 sztuk każdego rodzaju półfabrykatu. odpowiednio. Każdą kłodę można pociąć na określone kawałki na kilka sposobów: 1) na 2 części, ale o długości 1,2 m; 2) za 1 sztukę o długości 1,2 m i 2 sztuki o długości 0,9 m; 3) na 3 sztuki po 0,9 m. Znajdź liczbę kłód wyciętych każdą metodą tak, aby z jak najmniejszej liczby kłód otrzymano kawałki dowolnego rodzaju.

Rozwiązanie. Oznaczmy przez X() x2, x3 liczba kłód przetartych odpowiednio metodami 1, 2 i 3. Z nich można uzyskać 2xj +x2 półfabrykaty o długości 1,2 m każdy i 2x x +3x2 półfabrykaty po 0,9 m. Oznaczmy całkowitą liczbę kłód Z. Wtedy matematyczny model problemu przyjmie postać

z ograniczeniami:

Poprzez wprowadzenie dodatkowych zmiennych

sprowadzamy układ nierówności do równoważnego układu równań:

(8.5")

Rozwiązywanie otrzymanych problem kanoniczny(bez warunku całkowitego) stosując metodę sympleksu, w ostatnim, trzecim kroku rozwiązania znajdziemy następujące wyrażenia zmiennych głównych i funkcję liniową w postaci zmiennych niepodstawowych (zalecamy, aby uczniowie uzyskali je na ich własny).

III krok. Kluczowe zmienne X w X 2.

Zmienne inne niż podstawowe X Na X A , X 5.

czyli z rozwiązaniem optymalnym

Okazało się, że dwa elementy optymalnego rozwiązania nie spełniają warunku liczby całkowitej (8,4 cala), a składnik ma największą część całkowitą X 2. Zgodnie z ∏. 2 algorytmy rozwiązywania problemu programowania liczb całkowitych (patrz s. 166) z wykorzystaniem drugiego równania zawierającego tę zmienną X 2, tworzymy dodatkowe ograniczenie (8.6):

Znajdźmy części ułamkowe

i zapisz ostatnią nierówność w postaci

(8.6")

Wprowadzając dodatkową zmienną otrzymujemy

równanie równoważne nierówności (8,6"):

(8.7")

Wyraźmy z (8,7") dodatkową zmienną x6 i otrzymane równanie wprowadźmy do układu więzów, który mieliśmy na ostatnim, III etapie rozwiązywania problemu (8,1") - (8,3") (bez warunku całkowitego ).

IV krok. Kluczowe zmienne X{, X Na X 6.

Zmienne inne niż podstawowe X 3,x4, X 5.

Rozwiązując to rozszerzone zadanie metodą simplex (zapraszamy uczniów do samodzielnego wykonania), otrzymujemy co następuje.

Krok V. Główne zmienne x); X 2, x3.

Zmienne inne niż główne x4, x5, xb.

czyli z rozwiązaniem optymalnym

Otrzymane optymalne rozwiązanie rozszerzonego problemu (8,1”) – (8,3”), (8,6”) ponownie nie spełnia warunku całkowitego (8,4”). Zgodnie z pierwszym równaniem, w którym zmienna Xj otrzymuje wartość niecałkowitą w optymie

rozwiązanie (), pozostawiamy drugi dodatkowy limit

czytanie (8.6):

które przywołujemy na myśl

Użycie dodatkowej zmiennej

Nierówność tę sprowadzamy do równoważnego równania, które włączamy do układu więzów otrzymanego w ostatnim, V, etapie rozwiązywania rozszerzonego problemu (8.G”)–(8.3”), (8.6”) przy użyciu metoda simplex.

Krok VI. Kluczowe zmienne X w X 2, X Na X T

Zmienne inne niż podstawowe X 4, X-, x 6.

Pomijając dalsze rozwiązanie zadania metodą sympleksową (sugerujemy, aby uczniowie zrobili to sami), w końcowym, VII kroku otrzymujemy.

Krok VII. Kluczowe zmienne X w X tx3, X G

Zmienne inne niż podstawowe X w X 6, X T

Ponieważ w wyrażeniu funkcji liniowej nie ma zmiennych niepodstawowych o ujemnych współczynnikach X 7 – optymalne całkowite rozwiązanie pierwotnego problemu.

Należy zauważyć, że w otrzymanym wyrażeniu funkcji liniowej Z nie ma zmiennych drugorzędnych X D) i X 6. Oznacza to, że ogólnie rzecz biorąc, istnieje zbiór nieskończony optymalne rozwiązania(dowolna, niekoniecznie całkowita), dla której Z" = Zmjn = 46. Rozwiązania te otrzymuje się dla wartości zmiennej innej niż główna X 7 (zawarte w wyrażeniu Z), równy zeru(tj. kiedy X 7 = 0) i przy każdy wartości zmiennych niepodstawowych x5 i X 6 (nie ujęte w wyrażeniu na Z), które system ograniczeń „dopuszcza” do przyjęcia: 0<лг5 X 5 ≤ 1 i 0< X(i ≤ 1. Ale ze względu na warunek całkowity zmienne X- I X(> może przyjmować tylko wartości 0 lub 1. Dlatego problem będzie miał cztery optymalne rozwiązania całkowite, gdy X. i *6 w dowolnej kombinacji przyjmują wartości 0 lub 1, oraz X 7 = 0. Podstawiając te wartości do systemu ograniczeń w kroku VII znajdujemy takie optymalne rozwiązania:

Obecność alternatywnych optymalnych rozwiązań całkowitych umożliwia wybór jednego z nich, kierując się dodatkowymi kryteriami, które nie są brane pod uwagę w matematycznym modelu problemu. Przykładowo z warunków tego problemu wynika, że ​​piłowanie kłód nie powoduje powstawania odpadów jedynie przy użyciu 3. metody, dlatego też wybierając jedno z czterech optymalnych rozwiązań, naturalne jest preferowanie rozwiązania X^ 3 przy którym maksymalna liczba kłód ( X 2 = 41) jest piłowany bez odpadów.

Zatem Zmin=46 dla optymalnych rozwiązań całkowitych (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2). Przy zapisie rozwiązań optymalnych pozostawiliśmy tylko trzy pierwsze składowe, wyrażające liczbę kłód wyciętych odpowiednio metodą 1., 2. i 3., a wykluczyliśmy cztery ostatnie składowe, które nie mają znaczenia semantycznego.

Wadą metody Gomoriego jest wymóg podawania wartości całkowitych dla wszystkich zmiennych – zarówno podstawowych (wyrażających się np. w problemie wykorzystania zasobów jednostki produkcyjnej), jak i dodatkowych (wyrażających ilość niewykorzystanych zasobów, które mogą być ułamkowy).

• Widać, że rozwiązanie problemu jest krótsze.

Ekonomiczna i geometryczna interpretacja problemu programowania liczb całkowitych. Ekstremalny problem, którego zmienne przyjmują tylko wartości całkowite, nazywany jest problemem programowania liczb całkowitych.

W modelu matematycznym problemu całkowitego programowanie zarówno funkcja celu, jak i funkcje w układzie więzów mogą być liniowe, nieliniowe i mieszane. Ograniczmy się do przypadku, gdy funkcja celu i układ ograniczeń problemu są liniowe.

Przykład 20.

Podjęto decyzję o zainstalowaniu dodatkowego wyposażenia w warsztacie przedsiębiorstwa, na które przeznaczono miejsce. Przedsiębiorstwo może wydać 10 tysięcy rubli na zakup sprzętu i może kupić dwa rodzaje sprzętu. Zestaw sprzętu typu I kosztuje 1000 rubli, a typu II – 3000 rubli. Zakup jednego kompletu urządzeń typu I pozwala na zwiększenie wydajności produkcyjnej na zmianę o 2 szt., a jednego kompletu urządzeń typu II – o 4 szt. Wiedząc, że zainstalowanie jednego zestawu urządzeń typu I wymaga 2 m 2 powierzchni, a urządzenia typu II 1 m 2 powierzchni, określ taki zestaw dodatkowego wyposażenia, który pozwoli zmaksymalizować wydajność produkcji

Rozwiązanie. Stwórzmy matematyczny model problemu. Załóżmy, że przedsiębiorstwo zakupi x 1 komplet sprzętu typu I i komplet sprzętu typu II. Wtedy zmienne x 1 i muszą spełniać następujące nierówności:

Jeśli przedsiębiorstwo zakupi określoną ilość sprzętu, wówczas całkowity wzrost produkcji wyniesie

Zgodnie z treścią ekonomiczną zmienne x 1 i mogą przyjmować tylko nieujemne wartości całkowite, tj.

x 1 , – liczby całkowite. (73)

W ten sposób dochodzimy do następującego problemu matematycznego: znaleźć maksymalną wartość funkcji liniowej (71) przy spełnieniu warunków (70), (72) i (73). Ponieważ niewiadome mogą przyjmować tylko wartości całkowite, zadanie (70) – (73) jest problemem programowania liczb całkowitych. Ponieważ liczba niewiadomych w zadaniu wynosi dwa, rozwiązanie tego problemu można znaleźć, korzystając z jego interpretacji geometrycznej. W tym celu najpierw skonstruujemy wielokąt rozwiązań zadania polegającego na wyznaczeniu maksymalnej wartości funkcji liniowej (71) przy spełnieniu warunków (70) i ​​(72) (rys. 11). Współrzędne wszystkich punktów skonstruowanego wielokąta rozwiązania OAEVS spełniają układ nierówności liniowych (70) i ​​warunek nienegatywność zmienne (72). Jednocześnie warunek (73), tj. warunek uczciwość zmienne spełniają współrzędne tylko 12 punktów zaznaczonych na ryc. 11. Aby znaleźć punkt, którego współrzędne określają rozwiązanie pierwotnego problemu, zamień wielokąt OABC wielokąt OKEMNF, zawierający wszystkie ważne punkty o współrzędnych całkowitych i takie, że współrzędne każdego wierzchołka są liczbami całkowitymi. Oznacza to, że jeśli znajdziemy maksymalny punkt funkcji (71) na wielokącie OKEMNF, wówczas współrzędne tego punktu określą optymalny plan problemu.

W tym celu skonstruujemy również linię prostą przechodzącą przez wielokąt rozwiązania OKEMNF(liczba 12 jest przyjmowana arbitralnie). Konstruowaną linię przesuwamy w kierunku wektora, aż przejdzie ona przez swój ostatni punkt wspólny z danym wielokątem. Współrzędne tego punktu wyznaczają plan optymalny, a wartość funkcji celu w nim jest maksymalna.

W tym przypadku wymaganym punktem jest mi(1; 3), w którym funkcja celu przyjmuje maksymalną wartość C, a zatem współrzędne punktu mi określić optymalny plan rozwiązania problemu (70) – (73). Zgodnie z tym planem przedsiębiorstwo powinno zakupić jeden komplet sprzętu typu 1 i trzy komplety sprzętu typu II. Zapewni to przedsiębiorstwu, przy istniejących ograniczeniach dotyczących przestrzeni produkcyjnej i funduszy, maksymalny wzrost produkcji wynoszący 14 jednostek. na zmianę.

Przykład 21.

Do wykonania pracy można użyć P mechanizmy. Wydajność I-ty mechanizm podczas wykonywania J – ta praca jest równa . Zakładając, że każdy mechanizm może być wykorzystany tylko w jednym zadaniu i każde zadanie może być wykonane tylko przez jeden mechanizm, ustal przypisanie mechanizmów do zadań zapewniających maksymalną produktywność. Zbuduj model matematyczny problemu.

Rozwiązanie. Wprowadźmy zmienną x ij, której wartość jest równa 1, jeśli podczas wykonywania i-t wykorzystana praca J – mechanizm, a w przeciwnym razie równa się 0. Wówczas warunki wykorzystania każdego mechanizmu tylko w jednym zadaniu wyrażają się równościami

(74)

oraz warunki wykonywania pracy tylko przez jeden mechanizm - równości

(75)

Zatem zadaniem jest określenie takich wartości niewiadomych , spełniający układy równań (74) i (75) oraz warunek (76), przy którym osiągana jest maksymalna wartość funkcji

Sformułowany problem jest problemem programowania liczb całkowitych.

Wyznaczanie optymalnego planu problemu programowania liczb całkowitych. Rozważmy problemy programowania liczb całkowitych, w których zarówno funkcja celu, jak i funkcje w układzie ograniczeń są liniowe. W związku z tym formułujemy podstawowe zadanie programowania liniowego, w którym zmienne mogą przyjmować wyłącznie wartości całkowite. Ogólnie problem ten można zapisać w następujący sposób: znajdź maksimum funkcji

na warunkach

(79)

– całe (81)

Jeśli rozwiązanie problemu (78) – (81) znajdziesz metodą sympleksową, to może się okazać, że jest to liczba całkowita, ale nie musi (przykładem, którego rozwiązaniem jest zawsze liczba całkowita, jest problem transportu). W ogólnym przypadku, aby określić optymalny plan problemu (78) – (81), wymagane są specjalne metody. Obecnie istnieje kilka takich metod, z których najbardziej znana jest Metoda Gomoriego, który opiera się na opisanej powyżej metodzie simpleksowej.

Metoda Gomoriego. Znalezienie rozwiązania problemu programowania liczb całkowitych metodą Gomoriego rozpoczyna się od wyznaczenia optymalnego planu zadania (78) – (80) metodą simplex, bez uwzględnienia uczciwość zmienne. Po znalezieniu planu następuje przegląd jego elementów. Jeżeli pomiędzy składnikami nie ma liczb ułamkowych, to znaleziony plan jest planem optymalnym dla problemu programowania liczb całkowitych (78) – (81). Jeżeli w optymalnym planie zadania (78) – (80) zmienna przyjmuje wartość ułamkową, to nierówność jest dodawana do układu równań (79)

(82)

i znajdź rozwiązanie problemu (78) – (80), (82).

W nierówności (82) i – przekształcone wielkości początkowe i których wartości są pobierane z ostatniej tabeli sympleksu, oraz – części ułamkowe liczb (część ułamkowa pewnej liczby a jest najmniejszą liczbą nieujemną B tak, że różnica pomiędzy A I B jest całość). Jeżeli w optymalnym planie zadania (78) – (80) wartości ułamkowe przyjmują kilka zmiennych, to wyznaczana jest dodatkowa nierówność (82) największy ułamek część.

Jeżeli w znalezionym planie problemu (78) – (80), (82) zmienne przyjmują wartości ułamkowe, to ponownie dodawane jest jedno dodatkowe ograniczenie i proces obliczeniowy się powtarza. Wykonując skończoną liczbę iteracji, albo otrzymuje się optymalny plan problemu programowania liczb całkowitych (78) – (81), albo stwierdza się jego nierozwiązywalność.

Jeśli wymaganie uczciwość(81) dotyczy tylko niektórych zmiennych, wtedy takie problemy nazywa się częściowo całkowita. Ich rozwiązanie można znaleźć również poprzez sekwencyjne rozwiązywanie problemów, z których każdy uzyskuje się z poprzedniego poprzez wprowadzenie dodatkowego ograniczenia. W tym przypadku takie ograniczenie ma postać

gdzie wyznaczane są z zależności:

1) for , które może przyjmować wartości niecałkowite,

(84)

2) for , które może przyjmować wyłącznie wartości całkowite,

(85)

Z powyższego wynika, że ​​proces wyznaczania optymalnego planu problemu programowania liczb całkowitych metodą Gomoriego obejmuje: główne etapy:

1. Metodą sympleksową znaleźć rozwiązanie problemu (78) – (80) bez uwzględnienia wymagania uczciwość zmienne.

2. Utwórz dodatkowe ograniczenie dla zmiennej, która w optymalnym planie problemu (78) – (80) ma maksymalnie ułamkowy wartość, a w planie optymalnym zadanie (78) – (81) powinno być liczbą całkowitą.

3. Korzystając z dualności, znajdź rozwiązanie problemu wynikającego z problemu (78) – (80) w wyniku dodania dodatkowego ograniczenia.

4. W razie potrzeby utwórz kolejne dodatkowe ograniczenie i kontynuuj proces iteracyjny aż do uzyskania optymalnego planu problemu (78) – (81) lub ustalenia jego nierozwiązywalności.

Przykład 22.

Użyj metody Gomoriego, aby znaleźć maksymalną wartość funkcji

jeśli się uwzględni

(87)

– całe (89)

Rozwiązanie. Aby określić optymalny plan dla problemu (86) – (89), najpierw znajdujemy optymalny plan dla problemu (86) – (88) (Tabela 22).

Tabela 22

		C b	R 0

Jak widać z tabeli. 22, znaleziono optymalny plan problem (86) – (88) nie jest optymalnym planem dla problemu (86) – (89), ponieważ dwa składniki mają wartości niecałkowite. Co więcej, części ułamkowe tych liczb są sobie równe. Dlatego dla jednej z tych zmiennych tworzone jest dodatkowe ograniczenie. Zróbmy na przykład takie ograniczenie dla zmiennej. Z ostatniej tabeli simplex (Tabela 22) mamy

Zatem do układu więzów problemu (86) – (89) dodajemy nierówność

Lub

Tabela 23

		C b	R 0

Znajdujemy teraz maksymalną wartość funkcji (86), gdy spełnione są warunki (87), (88) i (90) (tabela 23).

Z tabeli 23 widać, że pierwotny problem programowania liczb całkowitych ma plan optymalny P W tym planie wartość funkcji celu jest równa . Podajmy geometryczną interpretację rozwiązania problemu. Obszar dopuszczalnych rozwiązań problemu (86) – (88) jest wielokątem OABCD(ryc. 12). Z ryc. 12 widać, że funkcja celu przyjmuje w tym punkcie maksymalną wartość Z(19/2; 7/2), tj. Co X =(19/2; 7/2; 0; 0; 34) to plan optymalny. Wynika to bezpośrednio z tabeli 22. Ponieważ X= (19/2; 7/2; 0; 0; 34) nie jest optymalnym planem dla problemu (86) – (89) (liczby i są ułamkowe), wówczas wprowadza się dodatkowe ograniczenie. Wykluczając z tego i zastępując odpowiednie wartości z równań układu więzów (87), otrzymujemy odcięcie od wielokąta OABCD trójkąt EFC.

Jak widać z rys. 12 obszar możliwych rozwiązań powstałego problemu jest wielokątem OABEFD. W punkcie mi(9; 4) tego wielokąta funkcja celu tego problemu przyjmuje wartość maksymalną. Ponieważ współrzędne punktu mi są liczbami całkowitymi i niewiadomymi i przy podstawieniu wartości do równania (87) przyjmują wartości całkowite jest optymalnym planem problemu (86) – (89). Wynika to również z tabeli 23.

Przykład 23.

Korzystając z metody Gomoriego, znajdź rozwiązanie problemu wyznaczania maksymalnej wartości funkcji

na warunkach

- cały. (94)

Podaj geometryczną interpretację rozwiązania problemu.

Rozwiązanie. Przepiszmy sformułowane zadanie w następujący sposób: znajdź maksymalną wartość funkcji

na warunkach

(96)

- cały. (98)

Problem (95) – (98) jest częściowo liczbą całkowitą, gdyż zmienne i mogą przyjmować wartości niecałkowite.

Metodą sympleksu znajdujemy rozwiązanie problemu (95) – (97) (tabela 24).

Tabela 24

		C b	R 0
		C b	R 0
							–1/3 nie jest planem problemu (95) – (98), ponieważ zmienna

Metoda Gomoriego służąca do rozwiązywania problemów programowania liczb całkowitych to: metoda odcięcia .

Istotą tej metody jest konstruowanie ograniczeń, które odcinają niecałkowite rozwiązania problemu programowania liniowego, ale nie odcinają żadnego planu całkowitego. Aby to zrobić, najpierw zdecyduj osłabione zadanie programowanie liniowe bez uwzględnienia warunku zmiennych całkowitych.

Jeżeli wynikowym rozwiązaniem problemu programowania liniowego jest liczba całkowita, wówczas problem programowania liczb całkowitych również zostaje rozwiązany i znalezione rozwiązanie jest dla niego optymalne. Jeśli w znalezionym rozwiązaniu problemu programowania liniowego jedna lub więcej zmiennych nie jest liczbą całkowitą, wówczas w celu znalezienia rozwiązania problemu w postaci liczby całkowitej dodaje się nowe ograniczenie liniowe, które odcina rozwiązania niecałkowite. Kontynuując rozwiązywanie rozszerzonego problemu metodą dual simplex, biorąc pod uwagę to ograniczenie, otrzymuje się plan liczb całkowitych.

Aby znaleźć rozwiązanie całkowite problemu za pomocą metody Gomoriego, stosuje się następujący algorytm.

Powinno być liniowe;

Należy odciąć znaleziony optymalny plan niecałkowity;

Nie należy obcinać żadnego planu liczb całkowitych.

Jeśli istnieje kilka zmiennych bazowych niecałkowitych, to aby utworzyć ograniczenie, wybieramy składnik optymalnego planu z największą częścią ułamkową (jeśli takich zmiennych jest kilka, wybierz dowolną).

Ta zmienna odpowiada wierszowi tabeli simplex o nazwie linia wykonująca cięcie (linia generująca ).

Aby przedstawić metodę, wprowadzamy następujące pojęcia. Pozwalać A- prawdziwy numer.

Pod cała część jakiś numer A rozumiana jest jako maksymalna liczba całkowita [ A], nie przekraczając tego.

Pod część ułamkowa jakiś numer A oznacza najmniejszą liczbę nieujemną
tak, że różnica między nim a A Jest [ A] - część całkowita liczby).

Dla wybranej zmiennej bazowej z największą częścią ułamkową znajdź część ułamkową
tej zmiennej i części ułamkowe wszystkich współczynników dla zmiennych I linia systemu ograniczeń
(linia produkcyjna).

Oznaczmy
I
całe części liczb I . Wartości ułamkowe
I
(
) są zdefiniowane w następujący sposób

W tym celu zapisuje się równanie z wiersza generującego tabeli sympleksowej, zakładając, że jest to pierwsze M zmienne są podstawowe dla danego planu optymalnego

Lub

Przesuwamy wszystkie części całkowite współczynników w jednym kierunku, pozostawiając wszystkie części ułamkowe w drugim:

Ponieważ
<1, то заменяя в правой части
, otrzymujemy ścisłą nierówność

Ponieważ lewa strona nierówności musi przyjmować wartości całkowite, dlatego warunek konieczny jej całkowitości można zapisać jedynie w postaci:

Nierówność przekształca się w równanie poprzez wprowadzenie dodatkowej nieujemnej zmiennej i umieszcza w optymalnej tabeli sympleksowej.

Problem rozwiązujemy metodą dual simplex. Jeżeli nowy optymalny plan rozszerzonego problemu jest liczbą całkowitą, wówczas problem jest rozwiązany. Jeśli rozwiązanie nie jest liczbą całkowitą, należy powtórzyć algorytm metody Gomoriego, aż do uzyskania rozwiązania w postaci liczby całkowitej.

Przykład. Korzystając z metody Gomoriego, znajdź rozwiązanie problemu programowania liczb całkowitych polegającego na określeniu maksymalnej wartości funkcji
jeśli się uwzględni

Rozwiązanie. Wyrównywanie nierówności za pomocą zmiennych pomocniczych X 3 , X 4 otrzymujemy problem programowania liniowego w postaci kanonicznej:

Problem programowania liniowego rozwiązujemy metodą simplex, stosując stopniowe przejście z jednej podstawy na drugą. Postęp rozwiązania problemu i wynikające z niego optymalne rozwiązanie przedstawiono w tabelach.

	Z B			Z 2 =11
∆ J =Z J -Z J

	Z B			Z 2 =11
∆ J =Z J -Z J

W znalezionym planie optymalnym wartość zmiennej X 2 jest równe liczbie ułamkowej. Znajdujemy jej część ułamkową oraz części ułamkowe wszystkich elementów linii zawierającej zmienną X 2, a mianowicie:

Teraz tworzymy nierówność Gomoriego dla znalezionych wartości części ułamkowych:

.

X 5, przesuwamy wolny wyraz równania na prawą stronę i otrzymujemy nowe ograniczenie:

.

Do tabeli simplex dodajemy wiersz zawierający nowe ograniczenie i kolumnę zawierającą nową zmienną i kontynuujemy rozwiązywanie problemu metodą dual simplex, ponieważ pseudoplan jest teraz zapisany w tabeli.

∆ J =Z J –Z J

	Z B			Z 2 =11
∆ J =Z J –Z J

Otrzymane optymalne rozwiązanie rozszerzonego problemu zawiera niecałkowitą wartość zmiennej X 1, więc dla tej linii znajdujemy części ułamkowe wszystkich liczb niecałkowitych, a mianowicie:

a nowa nierówność Gomory'ego ma postać:

Wyrównujemy nierówność Gomoriego za pomocą nowej zmiennej pomocniczej X 6, przesuwamy wolny wyraz równania na prawą stronę i otrzymujemy nowe ograniczenie:
.

Dodajemy go do rozwiązywanego problemu, dopasowujemy za pomocą zmiennej pomocniczej i rozwiązujemy rozszerzony problem

	Z B			Z 2 =11
∆ J =Z J –Z J

	Z B			Z 2 =11
∆ J =Z J –Z J

Znaleziono zatem optymalne rozwiązanie problemu programowania liczb całkowitych: Z maks=11 o godz
.

Notatki :

Jeżeli podczas procesu rozwiązywania w tabeli simplex pojawi się równanie ze składnikiem niecałkowitym i współczynniki całkowite w odpowiedniej linii systemu ograniczeń
, to problem ten nie ma rozwiązania w postaci całkowitej.