Ograniczenie w formie kanonicznej ma postać. Różne formy pisania problemu programowania liniowego
Forma kanoniczna, jeśli chcesz maksymalizować funkcję celu, wszystkie ograniczenia systemu są równaniami, a na wszystkie zmienne nałożony jest warunek nieujemności.
Zadanie Programowanie liniowe nadciągnąć symetryczny kształt, jeśli wymagana jest maksymalizacja funkcji celu, wszystkie ograniczenia systemu są nierównościami „” (lub minimalizacja funkcji celu, wszystkie ograniczenia systemu są nierównościami „”) i na wszystkie zmienne nałożony jest warunek nieujemności.
Nazywa się zbiór liczb akceptowalne rozwiązanie (plan), jeżeli spełnia system ograniczeń ZLP.
Mnóstwo wszystkich dopuszczalne rozwiązania zwany obszar możliwych rozwiązań(ODR).
Dopuszczalne rozwiązanie, dla którego osiągnięta jest maksymalna (minimalna) wartość funkcji, nazywa się optymalny plan dla PAP.
Terminy „plan” i „plan optymalny” wywodzą się z zastosowań ekonomicznych.
Wszystkie trzy formy zapisu ZLP są równoważne w tym sensie, że istnieją algorytmy przejścia z jednej formy do drugiej. Jeśli więc istnieje sposób rozwiązania problemu w jednej z postaci, to zawsze można wyznaczyć optymalny plan dla problemu podanego w dowolnej innej formie. Problem rozwiązano w formie symetrycznej metoda graficzna, a w postaci kanonicznej – metodą sympleksową.
Rozważmy algorytmy przejścia z jednej formy do drugiej.
Symetryczny kanoniczny. Przejście odbywa się poprzez dodanie dodatkowej, nieujemnej zmiennej po lewej stronie każdej nierówności. Jeżeli nierówność wynosiła „≤”, to zmienną bilansową dopisuje się po lewej stronie nierówności ze znakiem „+”. Jeżeli nierówność wynosiła „”, wówczas zmienną bilansową dodaje się po lewej stronie nierówności ze znakiem „–”. Nowe wprowadzone zmienne to tzw bilans. Problem minimalizacji funkcji Z zastępuje się problemem maksymalizacji funkcji (–Z) i przyjmuje się, że min Z = –max (–Z).
Kanoniczny symetryczny. Aby dokonać takiego przejścia, znajduje się ogólne rozwiązanie układu równań – więzów, funkcję celu wyraża się w postaci zmiennych wolnych. Następnie, korzystając z nieujemności zmiennych bazowych, możemy je wykluczyć z problemu. Symetryczna postać problemu będzie zawierała nierówności dotyczące wyłącznie zmiennych wolnych oraz funkcję celu zależną wyłącznie od zmiennych wolnych. Wartości podstawowych zmiennych znajdują się na podstawie ogólnego rozwiązania pierwotnego układu równań.
Ogólne kanoniczne. Każda zmienna, na którą nie nałożono warunku nieujemności, jest reprezentowana jako różnica dwóch nowych zmiennych nieujemnych. Nierówności przekształca się w równania poprzez wprowadzenie zmiennej bilansującej po lewej stronie każdej nierówności w taki sam sposób, jak opisano to przy przejściu z postaci symetrycznej do kanonicznej. Problem minimalizacji funkcji Z zastępuje się problemem maksymalizacji funkcji (–Z) w taki sam sposób, jak opisano to podczas przejścia z postaci symetrycznej do kanonicznej.
Graficzna metoda rozwiązywania problemu programowania liniowego
Zbiór punktów nazywa się wypukły, jeśli dla dowolnych dwóch punktów zbioru zawiera odcinek je łączący.
Przykład 1
Następujące zbiory punktów na płaszczyźnie są wypukłe:
Następujące zbiory punktów na płaszczyźnie nie są wypukłe: 
Twierdzenie 1 Przecięcie dowolnej liczby zbiorów wypukłych jest zbiorem wypukłym.
Twierdzenie 2 Niech będą dwa dowolne punkty w przestrzeni R N. Następnie dla dowolnego punktu odcinka [ PQ] musi zostać wykonane: .where .
Hipersamolot w kosmosie R N jest zbiorem punktów spełniającym równanie. Należy zauważyć, że w przypadku dwuwymiarowym hiperpłaszczyzna jest linią prostą.
Połowa przestrzeni jest zbiorem punktów spełniającym jedną z nierówności lub . Hiperpłaszczyzna dzieli punkty przestrzeni na dwie półprzestrzenie. W przypadku dwuwymiarowym hiperpłaszczyzna jest półpłaszczyzną.
Twierdzenie 3 Półprzestrzeń jest zbiorem wypukłym.
Konsekwencja Przecięcie dowolnej liczby półprzestrzeni jest zbiorem wypukłym.
Wielościan nazywa się przecięciem jednej lub większej liczby półprzestrzeni. Wielościan w przypadku dwuwymiarowym nazywany jest wielokątem.
Przykład 2
Poniższe zbiory to wielokąty.
Limitowany zestaw
Nieograniczony zestaw
Pojedyńczy punkt
Pusty zestaw
Nazywa się punkt zbioru wypukłego kątowy, jeśli nie leży w żadnym odcinku łączącym dwa inne punkty zbioru.
Przykład 3
Punkty narożne trójkąta to jego wierzchołki (są trzy). Punkty narożne okręgu to punkty okręgu, który go ogranicza (jest ich nieskończona liczba).
Punkt narożny wielościanu nazywa się jego szczyt.
Rozważmy ZLP podany w postaci symetrycznej.
Twierdzenie 4 Plan optymalny ZLP odpowiada wierzchołkowi wielościanu decyzyjnego wyznaczonego przez jego system więzów.
W ogólnym przypadku problem programowania liniowego jest zapisywany w taki sposób, że ograniczeniami są zarówno równania, jak i nierówności, a zmienne mogą być albo nieujemne, albo dowolnie zmienne. W przypadku, gdy wszystkie ograniczenia są równaniami i wszystkie zmienne spełniają warunek nieujemności, problem programowania liniowego nazywa się kanonicznym. Można go przedstawić w postaci współrzędnych, wektora lub zapisu macierzowego.
1. Problem kanonicznego programowania liniowego w zapisie współrzędnych ma postać
.
W bardziej zwartej formie to zadanie można zapisać za pomocą znaku sumowania,
(1.7)
2. Problem kanonicznego programowania liniowego w notacji wektorowej ma postać
(1.8)
Gdzie 
,
.
3. Problem kanonicznego programowania liniowego w zapisie macierzowym ma postać
(1.9)
, 
.
Tutaj A– macierz współczynników układu równań, X– macierz-kolumna zmienne problemowe, – macierz-kolumna odpowiednich części systemu ograniczeń.
Często stosowane są problemy programowania liniowego, tzw symetryczny, które w zapisie macierzowym mają postać
(1.10)
(1.11)
1.4. Przynoszący wspólne zadanie Programowanie liniowe
do postaci kanonicznej
W większości metod rozwiązywania problemów programowania liniowego przyjmuje się, że układ więzów składa się z równań i warunków naturalnych nieujemności zmiennych. Jednak przy kompilowaniu modeli matematycznych zadania gospodarcze ograniczenia formują się głównie w układy nierówności, dlatego konieczna jest umiejętność przejścia od układu nierówności do układu równań. W tym celu udowodnimy następujące twierdzenie.
Twierdzenie 1.1. O zastąpieniu nierówności równaniem. Każda decyzja 
nierówności
odpowiada jednoznacznemu rozwiązaniu równania
i nierówności
, (1.14)
i odwrotnie, każdemu rozwiązaniu równania (1.13) i nierówności (1.14) odpowiada unikalne rozwiązanie nierówności (1.12).
Dowód. Pozwalać 
jest rozwiązaniem nierówności (1.12), to . Oznaczmy różnicę między prawą i lewą stroną tej nierówności przez , tj.
Oczywiście 
. Zamiast tego podstawmy do równania (1.13). wartości zmienne 
, otrzymujemy
Spełnia zatem równanie (1.13) i nierówność (1.14). Oznacza to, że pierwsza część twierdzenia została udowodniona.
Spełnijmy teraz równanie (1.13) i nierówność (1.14), czyli mamy
I 
Odrzucając wartość nieujemną po lewej stronie ostatniej równości, otrzymujemy
tj. 
spełnia nierówność (1.12). Twierdzenie zostało udowodnione.
Jeżeli nierówność wynosi , to w jej lewą stronę należy wprowadzić dodatkową zmienną nieujemną ze znakiem minus, tj.
Nazywa się zmienne nieujemne wprowadzone do ograniczeń nierówności w celu przekształcenia ich w równania dodatkowe zmienne. Dodatkowe zmienne wprowadzane są do funkcji celu z zerowymi współczynnikami i dlatego nie wpływają na jej wartość.
W przypadku, gdy problem ma zmienne dowolnie zmieniające się, wówczas każdą taką zmienną zastępuje się różnicą dwóch zmiennych nieujemnych, tj. 
, Gdzie 
I 
.
Czasami konieczne staje się przejście od znalezienia minimum do znalezienia maksimum i odwrotnie. Aby to zrobić, wystarczy zmienić znaki wszystkich współczynników funkcji celu na przeciwne, a w przeciwnym razie pozostawić problem bez zmian. Uzyskane w ten sposób optymalne rozwiązania problemów maksymalnych i minimalnych pokrywają się, a wartości funkcji celu optymalne rozwiązania różnią się jedynie znakiem.
Przykład 1.1. Sprowadź problem programowania liniowego do postaci kanonicznej.
| D |
Rozwiązanie. Przejdźmy do problemu znalezienia maksimum funkcji celu. W tym celu zmieniamy znaki współczynników funkcji celu. Aby przekształcić drugą i trzecią nierówność układu więzów w równania, wprowadzamy nieujemne zmienne dodatkowe (na model matematyczny operacja ta oznaczona jest literą D). Zmienną wprowadza się po lewej stronie drugiej nierówności ze znakiem „+”, ponieważ nierówność ma postać . Zmienną wprowadza się po lewej stronie trzeciej nierówności ze znakiem „-”, gdyż nierówność ma postać . Zmienne wprowadza się do funkcji celu ze współczynnikiem równy zeru. Zmienną, na którą nie nałożono warunku nieujemności, zastępuje się różnicą 
, 
. Zapisujemy zadanie Forma kanoniczna
W niektórych przypadkach konieczne staje się zabranie ze sobą problem kanoniczny Do problem symetryczny. Spójrzmy na przykład.
Przykład 1.2. Sprowadź problem programowania liniowego do postaci symetrycznej
Strona 1
Forma kanoniczna problem charakteryzuje się trzema cechami: 1) jednorodnym układem więzów w postaci układu równań; 2) jednorodne warunki nieujemności, które mają zastosowanie do wszystkich zmiennych objętych problemem oraz 3) maksymalizacja, funkcja liniowa. W tym problemie wszystkie trzy funkcje są naruszone.
Kanoniczną postać problemu charakteryzują trzy następujące cechy: 1) jednorodny układ więzów w postaci układu równań; 2) jednorodne warunki nieujemności, które mają zastosowanie do wszystkich zmiennych objętych problemem oraz 3) maksymalizacja funkcji liniowej. W tym problemie wszystkie trzy funkcje są naruszone.
Kanoniczna postać problemu programowania liniowego jest wygodna, ponieważ łatwo jest znaleźć wierzchołek początkowy ważny obszar.
Rozważmy postać kanoniczną problemu programowania liniowego i metodę eliminacji Jordana-Gaussa.
Często wygodna jest postać kanoniczna problemu programowania liniowego.
Przekształcając układ więzów do postaci kanonicznej problemu programowania liniowego, nierówności (12) i (13) należy zastąpić równościami. W tym celu wprowadza się dodatkowe zmienne nieujemne.
Udowodnić, że macierze rzeczywiste dojeżdżające parami są jednocześnie redukowane do postaci kanonicznej Zadania 1128 poprzez transformację podobieństwa przy użyciu macierzy ortogonalnej.
Zasadniczo (4) - (5) można uznać za kanoniczną postać problemu programowania nieliniowego, ponieważ metody opisane w rozdz. Zwykle w programowaniu nieliniowym nie ma wymogu, aby zmienne były liczbami całkowitymi.
| Rodzaje ograniczeń i metody ich transformacji. |
Postać kanoniczną problemu charakteryzuje się jednorodnością układu więzów w postaci układu równań; maksymalizacja funkcji celu; warunek nieujemności wszystkich zmiennych związanych z problemem.
Nic dodatkowe funkcje kanoniczna postać problemów nie dodaje się do rozważanego schematu obliczeniowego.
Rozważmy najpierw drugą postać kanoniczną problemu minimalnego.
Algorytm simplex-mete można podzielić na dwa etapy. W pierwszym etapie, eliminując zmienne, znajdujemy podstawowe rozwiązanie. Jeśli zostanie znaleziony, to mamy kanoniczną postać problemu, aby przejść do drugiego etapu. Drugim krokiem jest sprawdzenie, czy istnieje ograniczone maksimum. Jeżeli istnieje, wyznacza się dopuszczalne rozwiązania podstawowe i spośród nich wybiera się optymalne.
Jeśli problem zostanie rozwiązany w formie kanonicznej, wówczas stosowana jest tylko część operacji wprowadzonych w akapicie drugim. Zatem dla problemu minimum kanonicznego realizowany jest tylko przypadek z paragrafu 3.4.1 i potrzebne są jedynie operacje cyklicznego przestawiania kolumn, przepuszczania kolumny przez pionową strefę graniczną, korygowanie naruszeń konstrukcyjnych i część operacji obcięcia. Symetrycznie, przy rozwiązywaniu problemu maksimum kanonicznego, realizowany jest tylko przypadek z paragrafu 3.4.2 i operacje cyklicznego przestawiania strun, przepuszczania struny przez poziomą strefę graniczną, korekta naruszeń strukturalnych i kolejna część operacji obcięcia potrzebne. W przeciwnym razie kanoniczna postać problemu nie dodaje żadnej dodatkowej specyfiki.
W pierwszym akapicie wstępu pokazano, jak ogólny problem programowania liniowego można sprowadzić do jednej z postaci kanonicznych. Dla kanonicznych (te same zadania opis metody konsekwentna poprawa jest formalnie uproszczone, gdyż nie ma potrzeby rozważania dwóch możliwości naruszenia warunków optymalności i dwóch możliwości dotarcia do kolejnego wierzchołka. Zwiększa to jednak rozmiar macierz bazowa A [ /, J ], które głównie określają złożoność jednego shata. Jednak w wielu przypadkach zastosowanie metody do postaci kanonicznych problemu okazuje się korzystne i w tym podrozdziale zatrzymamy się na wariantach metody uzyskanych dla poszczególnych problemów programowania liniowego.
Strony: 1
Problem programowania liniowego w postaci ax = b gdzie a jest macierzą współczynników, b jest wektorem więzów.
Przykład:
W każdym problemie LP wartości zmiennych poszukuje się pod warunkiem, że:
- wartości te spełniały pewien system równania liniowe lub nierówności;
- przy tych wartościach funkcja celu osiągnęłaby minimum lub maksimum.
Instrukcje. Wybierz liczbę zmiennych i liczbę wierszy (liczbę ograniczeń). Powstałe rozwiązanie jest zapisywane w pliku Word.
Jeden z metody uniwersalne Płyta jest metoda simplex, które jednak można zastosować, jeśli problem LP ma postać kanoniczną.
Definicja. Problem LP ma postać kanoniczną, jeśli wszystkie ograniczenia układu składają się tylko z równań (z wyjątkiem nierówności wyrażających nieujemność zmiennych), a funkcja celu musi być zminimalizowana.
Przykładem takiego problemu LP w formie kanonicznej jest Problem 1 – zrównoważony problem transportu z układem ograniczeń (1) i funkcją celu (2).
Jednak w większości problemów ekonomicznych najczęściej układ ograniczeń obejmuje początkowo nie tylko równania, ale także nierówności.
Oświadczenie. Każdy ogólny problem LP można sprowadzić do postaci kanonicznej.
Sprowadzenie ogólnego problemu LP do postaci kanonicznej osiąga się poprzez wprowadzenie nowych (nazywanych dodatkowymi) zmiennymi.
Układ więzów (3) tego problemu składa się z czterech nierówności. Poprzez wprowadzenie dodatkowych zmiennych y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, możemy przejść do systemu ograniczeń: 
Te dodatkowe zmienne y mam absolutnie jasny sens ekonomiczny, a mianowicie chodzi o ilość niewykorzystanego czasu pracy (przestoju maszyny I-tego typu).
Przykładowo, jeśli maszyny pierwszego typu przepracowały całe 18 godzin, to x + y = 18, zatem y 1 = 0. Dopuszczamy jednak możliwość niepełnego wykorzystania czasu pracy maszyny pierwszego X + y<18. В этом случае y 1 przyjmuje wartość dodatnią i można ją uznać za termin niewykorzystany. Przykładowo znając rozwiązanie tego problemu z punktu 3.3.2, X = 12, y= 6, z układu ograniczeń (3.9) możemy wywnioskować, że y 1 = y 2 = y 3 = 0 i y 4 = 12 – 6 = 6. Oznacza to, że maszyny pierwszego, drugiego, trzeciego typu całkowicie wykorzystują swój czas pracy. Ale czwarta maszyna jest tylko w połowie załadowana, 6 godzin i, biorąc pod uwagę optymalny plan, jest bezczynna. Być może po takich wnioskach szef przedsiębiorstwa będzie chciał go obciążyć inną pracą, wynająć na ten czas itp.
Zatem wprowadzając dodatkowe zmienne, możemy zredukować dowolne ograniczenie typu nierówności do równania.
Rozważmy problem mieszaniny. System ograniczeń ma postać: 
Nierówności sprowadzono w stronę „więcej”, dlatego wprowadzając dodatkowe zmienne y 1, y 2, y 3 ≥ 0, należy je odjąć od lewej strony, aby zrównać ją z prawą. Otrzymujemy system ograniczeń w formie kanonicznej:
Zmienne y i będą miały również sens ekonomiczny. Jeśli pamiętasz praktyczną treść zadania, to zmienna y 1 będzie oznaczać ilość nadmiaru substancji A w mieszaninie, y 2 będzie oznaczać ilość nadmiaru substancji W w mieszance y 3 – nadwyżka Z w mieszance.
Zadanie znalezienia maksymalnej wartości funkcji celu można sprowadzić do znalezienia minimum funkcji - F ze względu na oczywistość stwierdzenia max F = –min (–F). Spójrz na zdjęcie: jeśli w pewnym momencie X= X 0 funkcji y= F(X) osiąga maksimum, wówczas funkcja y= –F(X), symetrycznie do niego względem osi WÓŁ, w tym samym punkcie X 0 osiągnie minimum i F maks. = – (– F min) o godz X = X 0 .
Wniosek. Aby przedstawić problem LP w postaci kanonicznej, konieczne jest:
- przekształcić nierówności zawarte w układzie ograniczeń problemu w równania poprzez wprowadzenie dodatkowych zmiennych;
- jeśli funkcja celu F→max (maksymalizuje), zastępuje go funkcja – F→ min (która jest zminimalizowana).
Zadania posła
Ogólne ZLP nazywa się <,=,>=)bi (i=1,n) (2) z zastrzeżeniem xj>
Symetryczny < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Kanoniczny mieszany.
min f(x) = -max(-f(x))
<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>
Interpretacja geometryczna funkcji celu i ograniczeń ZLP. Sformułowanie geometryczne ZLP.
Niech będzie dane zadanie f=c1x1+c2x2-max (1).
a11x1+a12x2<=b1 }
am1x1+am2x2<=bm}
x1>=0, x2>=0 (3)
Plan zadania (x1,x2) to punkt na płaszczyźnie. Każda nierówność z-my 2 reprezentacje. jest półpłaszczyzną. Półpłaszczyzna jest zbiorem wypukłym. Wypukły nazywa się zbiorem, w którym należące do tego zbioru punkty łączące odcinek (x1 i x2) również należą do tego zbioru. C-ma 2 reprezentuje przecięcie półpłaszczyzn. Przechodząc możesz otrzymać:
1) wypukły wielokątny obszar zamknięty.
2) wypukły otwarty obszar wielokątny
3) pojedynczy punkt
4) zestaw pusty
5) belka i segment
Interpretacja geometryczna funkcji celu: Funkcja 1 to rodzina równoległych linii prostych, które nazywane są liniami poziomu (prostymi o stałej wartości funkcji celu). Pochodne cząstkowe funkcji względem x1 i x2 pokazują szybkość wzrostu funkcji celu wzdłuż współrzędnych osi. Wektor gradientu pokazuje kierunek najszybszego wzrostu funkcji celu Dla zadania 1-3 wektor gradientu = (c1; c2) opuszcza punkt (0,0) i kieruje się do punktu o współrzędnych (c1; c2). Wektor gradientu jest prostopadły do linii poziomu. Zwykle nazywa się przecięcie półpłaszczyzn obszar dopuszczalnych rozwiązań (ADD).
Główne twierdzenie LP. Schemat rozwiązanie ZLP, które wynika z tego twierdzenia.
Jeżeli ZLP ma rozwiązanie, to funkcja celu osiąga wartość ekstremalną w co najmniej jednym z skrajnych punktów wielościanu planu. Jeżeli funkcja celu osiąga wartość ekstremalną w więcej niż jednym skrajnym punkcie, to w dowolnym punkcie osiąga jedną i tę samą wartość, która jest ich wypukłą kombinacją liniową. Przy ręcznym rozwiązywaniu ZLP wygodnie jest skorzystać z wpisu tabelarycznego.
| BP | SP -Xm+1 -Xm+2 -Xn | |
| x1 | b1o | b11 b12 b1n-m |
| x2 | b2o | b21 b22 b2n-m |
| xm | bm | bm1 bm2 bmn-m |
| F | gwizd | bo1 bo2 bon-m |
Algorytm metody simplex.
1. doprowadzić model problemu do postaci kanonicznej;
2. znajdź początkowy planie referencyjnym;
3. napisz problem w prostej formie. tabela;
5. przejść na nowy plan referencyjny, na nowy symp. tabela. Aby przejść na nowy plan referencyjny wystarczy zastąpić jedną zmienną podstawową wolną. Zmienną wchodzącą w skład podstawy i odpowiadającą jej kolumnę rozdzielczości wyznacza największy bezwzględnie ujemny element rzędu f. Zmienną wykluczającą z bazy i odpowiadającą jej linię rozdzielczą wyznacza się poprzez najmniejszy współczynnik sympleksowy, tj. stosunek elementów kolumny jednostki do odpowiedniego elementu kolumny rozdzielczości. Stosunek simpleks jest wielkością nieujemną. Na przecięciu rozdzielającego wiersza i rozdzielającej kolumny znajduje się element rozstrzygający, w odniesieniu do którego transformacja simpleksowa Następny zasada: 1. Elementy ciągu zezwalającego dzielimy na element zezwalający; 2. elementy kolumny rozdzielczości dzielą się na element rozdzielczości i zmieniają swój znak na przeciwny; 3. pozostałe elementy tabeli układamy zgodnie z zasadą prostokąta:
bij bis bkj=(bkj*bis-bij*bks)/bi
Drugie twierdzenie o dualności.
jeśli jeden z problemów dualnych ma plan optymalny, to drugi również daje się rozwiązać, tj. ma plan optyczny. W tym przypadku skrajne wartości funkcji celu pokrywają się (j=od 1 do n) Σcjxj*= (i=od 1 do m)Σbiyi* jeśli w oryginale. problem, funkcja celu jest nieograniczona na zbiorze planów, a następnie w podwójny problem system ograniczeń jest niespójny.
Twierdzenie o rzędzie macierzy TK.
Ranga macierzy A problemu transportu jest o jeden mniejsza od liczby równań: r(A)=m+n-1.
39. Algorytm konstrukcji wstępnego planu odniesienia ZLP.
Aby znaleźć początkowy plan referencyjny, możemy zaproponować następujące rozwiązania algorytm:
1. Zapisz problem w postaci tablicy Jordana tak, aby wszystkie elementy kolumny wyrazów wolnych były nieujemne, tj. nierówność aio>=0 (i=1,m) została spełniona. Równania, w których wolne wyrazy są ujemne, są najpierw mnożone przez -1.
| -x1….. -xn | ||
| 0= | a1o | a11…. a1n |
| ….. | ….. | ……………………….. |
| 0= | amo | jestem1…..rano |
| f= | -c1…. -cn |
Przekształć tabelę, stosując etapy eliminacji Jordana, zastępując zera w lewej kolumnie odpowiednimi x. Jednocześnie na każdym kroku można wybrać opcję zezwalającą dowolna kolumna zawierająca co najmniej jeden element dodatni. Rozwiązujący rząd jest wyznaczany przez najmniejszy ze stosunków wolnych wyrazów do odpowiednich dodatnich elementów kolumny rozdzielającej. Jeżeli w procesie eliminacji natkniemy się na wiersz zerowy, którego wszystkie elementy są zerowe, a wyraz wolny jest niezerowy, to układ równań z więzami nie ma rozwiązań. Jeżeli natrafiamy na rząd 0, w którym poza wyrazem wolnym nie ma innych elementów dodatnich, to układ równań restrykcyjnych nie ma rozwiązań nieujemnych. wspólny, to po określonej liczbie kroków wszystkie zera w lewej kolumnie zostaną zastąpione przez x, uzyskując w ten sposób pewną podstawę, a co za tym idzie odpowiedni plan odniesienia.
40. Algorytm konstrukcji optymalnego planu odniesienia ZLP.
Początkowy plan wsparcia Ho jest sprawdzany pod kątem optymalności.
Jeśli w wierszu f nie ma elementów ujemnych (nie licząc wolnego terminu), plan jest optymalny. Jeśli w rzędzie f również nie ma elementów zerowych, wówczas istnieje tylko jeden optymalny plan; jeśli wśród elementów jest przynajmniej jedno zero, to istnieje nieskończona liczba optymalnych planów. Jeśli w wierszu f znajduje się co najmniej jeden element ujemny, a w odpowiedniej kolumnie nie ma elementów dodatnich, to funkcja celu nie jest ograniczona w obszarze dopuszczalnym. Problemu nie da się rozwiązać. Jeśli w pierwszym rzędzie znajduje się przynajmniej jeden element ujemny, a w każdej kolumnie z takim elementem znajduje się przynajmniej jeden element dodatni, to można przejść do nowego planu odniesienia, bliższego optymalnemu. Aby to zrobić, przyjmuje się kolumnę z elementem ujemnym w wierszu f dozwalający; Wyznaczają ciąg rozdzielający na podstawie minimalnej relacji sympleksowej i wykonują krok eliminacji Jordana. Powstały plan odniesienia jest ponownie sprawdzany pod kątem optymalności. Powtarza się to do momentu znalezienia optymalnego planu odniesienia lub ustalenia nierozwiązywalności problemu.
Algorytm metody Gomori.
1. Stosując metodę simplex, znajduje się optymalny plan problemu. Jeśli wszystkie elementy planu optymalnego są liczbami całkowitymi, wówczas jest on optymalny. W przeciwnym razie przejdź do kroku 2
2. Spośród składników niecałkowitych należy wybrać ten, który ma frakcja jest największa i korzystając z odpowiedniego wiersza tabeli simplex, sformułuj prawidłową wartość odcięcia, korzystając ze wzoru
(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)
3. Przekształć sformułowaną nierówność w równoważną równość zerową i uwzględnij ją stół simpleksowy z niecałkowitym planem optymalnym
4. Powstały rozszerzony problem rozwiązuje się metodą sympleksową. Jeśli wynikowy plan nie jest liczbą całkowitą, przejdź do kroku 2.
Jeśli podczas rozwiązywania pojawi się linia zawierająca niecałkowity wyraz wolny i inne współczynniki całkowite, wówczas odpowiadające równanie nie ma rozwiązania w liczbach całkowitych. W tym przypadku i oryginalny problem nierozstrzygalny w liczbach całkowitych. Metoda Gomoriego ma ograniczone zastosowanie. Przy jego pomocy wskazane jest rozwiązywanie drobnych problemów, ponieważ... liczba interakcji może być bardzo duża.
Różne formy notacji ZLP (ogólne, kanoniczne, symetryczne)
Zadania posła: określenie optymalnego planu, określenie optymalnej wielkości produkcji, określenie optymalnej kombinacji upraw, utworzenie optymalnego pakietu aktywów, maksymalizacja zysków banku itp.
Ogólne ZLP nazywa się problem maksymalizacji (minimalizacji). funkcja liniowa f=Σcj*xj-max(min) (1) przy ograniczeniach liniowych ∑aij *xj(=<,=,>=)bi (i=1,n) (2) pod warunkiem xj>=0(j=1,n1), xj-arbitrary (j=n1+1,n)(3) gdzie cj,aij, bi-stałe liczby .
Symetryczny Formę zapisu ZLP nazywa się problemem maksymalizacji funkcji (1) przy ograniczeniach liniowych w nierównościach ze znakiem< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >lub = i zmienne nieujemne. Kanoniczny Formę zapisu ZLP nazywamy problemem funkcji maksymalnej (1) przy liniowych ograniczeniach równości i zmiennych nieujemnych. Każda inna forma nazywa się mieszany.
min f(x) = -max(-f(x))
Przekształcenie nierówności w równanie i odwrotnie odbywa się w oparciu o Lemat: dla każdego rozwiązania x1...xn nierówności a1x1+...+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) i odwrotnie. Każde rozwiązanie x1…xn,xn+1 równania 6 i nierówności 7 odpowiada rozwiązaniu x1…xn nierówności 5.
Aby przejść z tylnej formy sim do tylnej formy kanonicznej, musisz wejść zmienne równoważące (wyrównujące). Opiera się to na twierdzeniu o nierówności: każdą nierówność można przedstawić w postaci równania lub prostej nierówności.