MODEL PROGRAMOWANIA LINIOWEGO
1 Matematyczny opis modelu programowania liniowego
2 Metody implementacji modeli programowania liniowego
3 Problem podwójnego programowania liniowego
Model programowania liniowego(LP) ma miejsce, jeśli w badanym układzie (obiekcie) ograniczenia zmiennych i funkcji celu liniowy.
Modele LP służą do rozwiązywania dwóch głównych typów stosowanych problemów:
1) optymalne planowanie w każdej sferze działalności człowieka - społecznej, gospodarczej, naukowej, technicznej i wojskowej. Na przykład przy optymalnym planowaniu produkcji: dystrybucja zasobów finansowych, pracy i innych zasobów, dostawa surowców, zarządzanie zapasami itp.
2) zadanie transportowe (znalezienie optymalnego planu dla różnych rodzajów transportu, optymalnego planu rozmieszczenia różnych środków na obiektach o różnym przeznaczeniu itp.)
MATEMATYCZNY OPIS MODELU PROGRAMOWANIA LINIOWEGO
Wymagane jest znalezienie nieujemnych wartości zmiennych
spełnianie ograniczeń liniowych w postaci równości i nierówności
,
gdzie 
- podane liczby,
i dostarczanie ekstremum liniowej funkcji celu
,
gdzie podane są liczby, co jest napisane jako
Akceptowalne rozwiązanie każdy zestaw nazywa się 
, spełniające warunki.
Domena dopuszczalnych rozwiązań to zbiór wszystkich dopuszczalnych rozwiązań.
Optymalne rozwiązanie 
, dla którego 
.
Uwagi
1. Zredukowany model LP to ogólny. Istnieje również standard oraz kanoniczny formy modeli LP.
2. Warunki istnienia wdrożenie modelu LP:
– zbiór dopuszczalnych rozwiązań nie jest pusty;
- funkcja celu 
ograniczone przez (przynajmniej od góry przy szukaniu maksimum i od dołu przy szukaniu minimum).
3.LP opiera się na dwóch twierdzeniach
Twierdzenie 1. Wiele G, określony przez system więzów formy, jest wypukłym zbiorem domkniętym ( wypukły wielościan w z punktami narożnymi - szczyty.)
Twierdzenie 2.
Forma liniowa 
, zdefiniowany na wypukłym wielościanie
j=1,2,…,s
ja=s+1,s+2,…, m,
osiąga ekstremum na jednym z wierzchołków tego wielościanu.
Twierdzenie to nazywa się twierdzeniem ekstremum o postaci liniowej.
Zgodnie z twierdzeniem Weierstrassa optymalne rozwiązanie jest unikalne i stanowi globalne ekstremum.
Istnieje ogólne podejście analityczne do implementacji modelu LP - metoda simplex. Przy rozwiązywaniu problemów programowania liniowego często nie ma rozwiązania. Dzieje się tak z następujących powodów.
Zilustrujmy pierwszy powód przykładem.
Z takiego powodu mówią, że ograniczenia są niespójne. Domeną dopuszczalnych rozwiązań jest zbiór pusty.
Drugi powód komentuje następujący przykład:
W tym przypadku obszar możliwych rozwiązań nie jest ograniczony od góry. Obszar dopuszczalnych rozwiązań nie jest ograniczony.
Podążając za tradycjami programowania liniowego, nadamy zagadnieniu LP ekonomiczną interpretację. Pozwól nam mieć m typy zasobów. Numer zasobu typu j równa się . Zasoby te są potrzebne do produkcji n rodzaje towarów. Oznaczmy ilość tych towarów symbolami 
odpowiednio. Typ przedmiotu i koszty . Produkcja towarów typu i powinien być ograniczony do 
odpowiednio. Do produkcji jednostki towaru typu i rodzaj zużytego zasobu j. Konieczne jest ustalenie takiego planu produkcji towarów ( 
), aby ich całkowity koszt był minimalny.
Problemy programowania liniowego stosowane do optymalizacji funkcjonowania obiektów rzeczywistych zawierają znaczną liczbę zmiennych i ograniczeń. Uniemożliwia to ich rozwiązywanie metodami graficznymi. Przy dużej liczbie zmiennych i ograniczeń stosowane są metody algebraiczne, które opierają się na iteracyjnych procedurach obliczeniowych. W programowaniu liniowym opracowano wiele metod algebraicznych, które różnią się sposobem konstruowania wstępnego rozwiązania dopuszczalnego oraz warunkami przejścia z jednej iteracji do drugiej. Wszystkie te metody opierają się jednak na ogólnych założeniach teoretycznych.
Ogólność głównych postanowień teoretycznych prowadzi do tego, że metody algebraiczne rozwiązywania problemów programowania liniowego są w dużej mierze do siebie podobne. W szczególności prawie każdy z nich wymaga wstępnej redukcji problemu programowania liniowego do postaci standardowej (kanonicznej).
Algebraiczne metody rozwiązywania problemu LP zaczynają się od zredukowania go do forma standardowa (kanoniczna):
,
,
i=1,..,n;j=1,..,m.
Każdy problem programowania liniowego można zredukować do postaci standardowej. Porównanie modelu ogólnego z modelem kanonicznym pozwala stwierdzić, że aby sprowadzić problem LP do postaci standardowej, konieczne jest, po pierwsze, przejście z systemu nierówności do równości, a po drugie, takie przekształcenie wszystkich zmiennych, że są nieujemne.
Przejście do równości odbywa się poprzez dodanie nieujemnej zmiennej rezydualnej po lewej stronie ograniczeń dla nierówności typu , i odjęcie nieujemnej zmiennej nadmiarowej z lewej strony dla nierówności typu . Na przykład nierówność 
przechodząc do postaci standardowej przekształca się w równość 
i nierówności 
- do równości 
. W tym przypadku zarówno zmienna rezydualna, jak i zmienna nadwyżkowa są nieujemne.
Zakłada się, że prawa strona nierówności jest nieujemna. W przeciwnym razie można to osiągnąć mnożąc obie strony nierówności przez „-1” i zmieniając jej znak na przeciwny.
Jeżeli w pierwotnym zadaniu programowania liniowego zmienna nie jest ograniczona znakiem, można ją przedstawić jako różnicę dwóch zmiennych nieujemnych 
, gdzie 
.
Ważna cecha zmiennych 
jest to, że dla każdego dopuszczalnego rozwiązania tylko jedno z nich może przyjąć wartość dodatnią. Oznacza to, że jeśli 
, następnie 
i wzajemnie. W związku z tym można ją uznać za zmienną rezydualną, ale - zmienną redundantną.
Przykład Niech zostanie podany problem programowania liniowego:
,
.
Musisz doprowadzić to do standardowej formy. Zauważ, że pierwsza nierówność pierwotnego problemu ma znak , dlatego konieczne jest wprowadzenie do niej zmiennej reszty. W rezultacie otrzymujemy .
Druga nierówność ma znak i do przekształcenia do postaci standardowej wymaga wprowadzenia zmiennej redundantnej , wykonując tę operację otrzymujemy .
Ponadto zmienna nie jest ograniczona znakiem. Dlatego zarówno w funkcji celu, jak i w obu ograniczeniach należy ją zastąpić różnicą 
. Po wykonaniu podstawienia otrzymujemy zadanie programowania liniowego w postaci standardowej, równoważne pierwotnemu zadaniu:
.
Problem programowania liniowego, napisany w postaci standardowej, to problem znajdowania ekstremum funkcji celu na zbiorze wektorów będących rozwiązaniami układu równań liniowych z uwzględnieniem warunków nieujemności. Jak wiecie, układ równań liniowych może nie mieć rozwiązań, mieć jedno rozwiązanie lub mieć nieskończoną liczbę rozwiązań. Optymalizacja funkcji celu jest możliwa tylko wtedy, gdy system: ma nieskończony wiele rozwiązań. Układ równań liniowych ma nieskończoną liczbę rozwiązań, jeżeli jest niesprzeczny (ranga macierzy głównej jest równa rangowi rozszerzonej) i jeżeli rang macierzy głównej jest mniejszy niż liczba niewiadome.
Niech rząd macierzy systemu ograniczeń będzie równy m. Oznacza to, że macierz ma co najmniej jedną mniejszą m rząd nie jest równy zero. Bez utraty ogólności możemy założyć, że minor znajduje się w lewym górnym rogu macierzy. Można to zawsze osiągnąć zmieniając numerację zmiennych. Ta niezerowa ranga drugorzędna m nazywa się bazą. Zróbmy system od początku m równania układu, pisząc to w następujący sposób:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Państwowa uczelnia wyższa
kształcenie zawodowe
„Moskiewski Państwowy Uniwersytet Techniczny im. N.E. Baumana”
Oddział Kaługa
"Rozwiązanie problemu programowania liniowego metodą simpleks"
Cel pracy: zbadanie i nauczenie się praktycznego zastosowania simpleksu – metody rozwiązywania problemów bezpośrednich i dualnych programowania liniowego
Część teoretyczna.
Matematyczne sformułowanie problemu programowania liniowego.
Z praktyki rozpatrywania problemów programowania matematycznego wynika, że rozwiązywanie ich w kategoriach ogólnych jest prawie niemożliwe. Wskazane jest rozważenie odrębnych klas (rodzajów) problemów. Dla każdej takiej klasy możliwe jest sformułowanie algorytmu rozwiązania, który jest akceptowalny tylko dla tej klasy problemów. Najbardziej rozwinięte w programowaniu matematycznym są problemy programowania liniowego (LP).
W problemach programowania liniowego funkcja celu jest liniowa, a warunki ograniczające zawierają liniowe równości i liniowe nierówności. Zmienne mogą, ale nie muszą podlegać wymogowi nieujemności. Ten sam problem programowania liniowego można zapisać w różnych formach. Jeśli wszystkie ograniczenia mają postać nierówności, to problem jest napisany w postaci standardowej. Jeśli wszystkie jego ograniczenia z wyjątkiem
są równościami, to problem programowania liniowego jest zapisany w postaci kanonicznej.
Ogólny widok problemu programowania liniowego
,
Ograniczenia:
1. Właściwe części wszystkich ograniczeń muszą być nieujemne 
. Jeśli którykolwiek ze współczynników< 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;
2. Wszystkie ograniczenia muszą być przedstawione jako równości, dlatego przy przechodzeniu od nierówności do równości stosuje się aparat dodatkowych zmiennych.
Jeśli początkowe ograniczenia określają zużycie jakiegoś zasobu (znak „”), to zmienne 
należy interpretować jako pozostałą lub niewykorzystaną część zasobu. W tym przypadku jest to zmienna rezydualna i jest wpisywana do równania ze znakiem „+”.
Jeżeli ograniczenia początkowe określają nadmiar jakiegoś zasobu (znak „”), to wprowadzana jest zmienna nadmiarowa 
podpisać "-".
Zmienne:
Wszystkie zmienne muszą być nieujemne, tj. 
.
Jeśli zmienna nie ma ograniczenia w postaci znaku, to musi być reprezentowana jako różnica dwóch zmiennych nieujemnych: , gdzie . Takie podstawienie powinno być stosowane we wszystkich ograniczeniach zawierających tę zmienną, a także w wyrażeniu na funkcję celu.
Jeżeli taka zmienna mieści się w optymalnym rozwiązaniu, to
Funkcja docelowa:
Maksymalizować lub minimalizować.
System ograniczeń w postaci równości i nierówności tworzy zbiór wypukły – wielościan wypukły. Ten zestaw może być limitowany lub nieograniczony. Funkcja celu zadania programowania liniowego jest również funkcją wypukłą. Zatem problem programowania liniowego jest szczególnym przypadkiem problemu programowania wypukłego.
Rozważ układ ograniczeń dla problemu programowania liniowego w postaci równości
(1)
Układ (1) równań liniowych jest zgodny, jeśli ma co najmniej jedno rozwiązanie. System (1) nazywany jest redundantnym, jeśli jedno z równań można wyrazić jako liniową kombinację pozostałych.
W systemie (1) liczba zmiennych (n niewiadomych) jest większa niż liczba ograniczeń m. Założymy, że ranga tego systemu jest równa m (system nie jest nadmiarowy) i że system (1) jest zgodny.Wtedy m zmiennych z ich całkowitej liczby tworzy zmienne podstawowe, a inne zmienne nazywamy niepodstawowymi.Jeżeli układ równań ma rozwiązanie, to ma również rozwiązanie podstawowe.Rozwiązanie układu równań (1) nazywa się dopuszczalnym, jeśli wszystkie jego składowe są nieujemne.Jeżeli układ równań liniowych ma rozwiązanie dopuszczalne, to ma również rozwiązanie dopuszczalne podstawowe.wszystkich rozwiązań dopuszczalnych układu (1) jest zbiorem wypukłym, czyli zbiorem rozwiązania problemu programowania liniowego są wypukłe. Ponieważ zbiór ten tworzą płaszczyzny (hiperpłaszczyzny), ma on postać wielościanu wypukłego. istnieje optymalne rozwiązanie problemu programowania liniowego, to istnieje podstawa jest optymalnym rozwiązaniem.
Funkcją celu problemu programowania liniowego jest równanie płaszczyzny (lub hiperpłaszczyzny dla więcej niż trzech zmiennych). Funkcja celu zadania programowania liniowego osiąga maksymalną lub minimalną wartość albo na wierzchołku wielościanu wypukłego, albo na jednej z jego ścian. Tak więc rozwiązanie (rozwiązania) problemu programowania liniowego leży na wierzchołkach wielościanu wypukłego, a do jego znalezienia konieczne jest obliczenie wartości funkcji celu na wierzchołkach wielościanu wypukłego określonych warunkami -ograniczenia problemu.
Rozwiązywanie problemu programowania liniowego metodą graficzną.
Trudność budowy modelu matematycznego polega na identyfikacji zmiennych i późniejszej reprezentacji celu i ograniczeń w postaci funkcji matematycznych tych zmiennych. Jeżeli model zawiera tylko dwie zmienne, to problem programowania liniowego można rozwiązać graficznie. W przypadku trzech zmiennych rozwiązanie graficzne staje się mniej wizualne, a przy większej wartości zmiennych jest to wręcz niemożliwe. Jednak rozwiązanie graficzne pozwala na wyciągnięcie wniosków, które służą jako podstawa do opracowania ogólnej metody rozwiązywania problemu programowania liniowego.
Pierwszym krokiem w zastosowaniu metody graficznej jest geometryczne przedstawienie możliwych rozwiązań, tj. konstrukcja dziedziny rozwiązań dopuszczalnych (ODD.), w której wszystkie ograniczenia modelu są jednocześnie spełnione. Po uzyskaniu rozwiązania graficznego zmienna jest wykreślana wzdłuż osi poziomej, a - wzdłuż osi pionowej. Przy tworzeniu SDE należy zapobiegać otrzymywaniu rozwiązań niedopuszczalnych, które wiążą się z koniecznością spełnienia warunku nieujemności zmiennych. Przed budową konieczne jest określenie kwadrantów, w których będzie zlokalizowany ODR. Kwadranty są określone przez znaki zmiennych i . Warunki nieujemności zmiennych i ograniczają zakres ich dopuszczalnych wartości do pierwszego kwadrantu. Jeżeli zmienna nie jest ograniczona znakiem, to obszar jest ograniczony przez pierwszą i drugą ćwiartkę, jeśli , to - przez pierwszą i czwartą ćwiartkę. Pozostałe granice przestrzeni rozwiązań na płaszczyźnie wyznaczają linie proste skonstruowane według równań więzów, pod warunkiem, że znak zostanie zastąpiony znakiem „=”. W takim przypadku należy wziąć pod uwagę, co następuje: prawe strony wszystkich wiązań muszą być nieujemne . Jeśli jakiekolwiek ograniczenie< 0, то необходимо коэффициенты соответствующего ограничения слева и справа до-множить на "-1" и изменить знак неравенства данного ограничения на противоположный. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.
W wyniku konstrukcji powstaje wielokąt, który wyznacza przestrzeń rozwiązań. Jeśli jedno z ograniczeń ma znak „=”, to ODD degeneruje się w segment.
W każdym punkcie, który należy do obszaru lub granic wielokąta rozwiązania, wszystkie więzy są spełnione, więc wszystkie rozwiązania odpowiadające tym punktom są ważne. Przestrzeń rozwiązań zawiera nieskończoną ilość takich punktów, mimo to możliwe jest znalezienie rozwiązania optymalnego. W tym celu należy skonstruować w płaszczyźnie zmiennych gradient funkcji celu. Wyznaczenie optymalnego punktu zależy od problemu do rozwiązania.
Jeżeli w funkcji celu zdefiniowany zostanie problem maksymalizacji, to punkt optymalny będzie znajdował się w kierunku zwiększania gradientu, jeśli zdefiniowany zostanie problem minimalizacji, to w kierunku malejącego gradientu funkcji celu. Aby wyznaczyć optymalny punkt, przesuniemy funkcję celu w kierunku zwiększania (zmniejszania) gradientu, aż przesunie się ona w obszar rozwiązań niedopuszczalnych.
Po znalezieniu optymalnego punktu w przestrzeni rozwiązań wyznaczane są jego współrzędne oraz wartość znajdującej się w nim funkcji celu. Poprawność wyboru punktu optymalnego można sprawdzić obliczając funkcję celu na wierzchołkach wielościanu rozwiązania. W LLP domeną rozwiązań dopuszczalnych jest zawsze zbiór wypukły, czyli taki zbiór, że wraz z dowolnymi dwoma punktami należącymi do tego zbioru, odcinek łączący te dwa punkty również należy do tego samego zbioru. Każda funkcja rośnie najszybciej w kierunku jej gradientu.
Rozwiązywanie zadania programowania liniowego metodą simpleks.
bezpośrednie zadanie.
Rozważ problem programowania liniowego w postaci kanonicznej:
Znajdź maksimum (minimum) funkcji 
na warunkach
Zakłada się, że istnieje rozwiązanie tego problemu. Aby znaleźć optymalne rozwiązanie, należy znaleźć dopuszczalne rozwiązania podstawowe i wybrać z nich optymalne rozwiązanie podstawowe.
Metoda simpleks to algebraiczna metoda rozwiązywania problemów programowania liniowego. W trakcie obliczeń wierzchołki wielościanu rozwiązania (ODP) są sekwencyjnie omijane ze sprawdzeniem warunków optymalności na każdym wierzchołku. Ponadto każdemu przejściu do sąsiedniego wierzchołka towarzyszy poprawa funkcji celu.
Procedury obliczeniowe metody simplex.
Przy graficznej metodzie rozwiązywania LLP optymalne rozwiązanie zawsze odpowiada jednemu z punktów narożnych (skrajnych) przestrzeni rozwiązań. Wynik ten leży u podstaw konstrukcji metody simplex. Metoda simpleks nie zapewnia widoczności geometrycznej reprezentacji przestrzeni rozwiązań.
Metoda simpleks realizuje uporządkowany proces, w którym, zaczynając od pewnego początkowego dopuszczalnego punktu narożnego, wykonywane są kolejne przejścia od jednego dopuszczalnego skrajnego punktu do drugiego, aż do znalezienia optymalnego punktu rozwiązania.
Oznaczmy: - całkowitą liczbę zmiennych w LLP, przedstawioną w postaci kanonicznej; - liczba zmiennych początkowych; - liczba ograniczeń, - liczba dodatkowych zmiennych, to 
.
Każdy wierzchołek wielościanu rozwiązania ma - zmienne niezerowe i () - zmienne zerowe.
Zmienne niezerowe nazywane są podstawowymi, zmienne zerowe nazywane są niepodstawowymi.
Uzupełniamy system równości o równość funkcji celu, przy czym zakładamy, że jest to zmienna podstawowa, która jest zawsze obecna w bazie każdego wierzchołka.
Aby uzyskać rozwiązanie, zestawia się wstępną dopuszczalną podstawę, w której podstawowe zmienne muszą być reprezentowane jako wektory jednostkowe. Oznacza to, że równania reprezentujące dany wierzchołek muszą zawierać każdą zmienną bazową tylko w jednym wierszu ze współczynnikiem 1.
Wybierając początkową akceptowalną podstawę do zestawienia tablicy simpleksowej, w pierwszym kroku CT(0) zmienne początkowe są zerowane i są niepodstawowe, spośród wprowadzanych zmiennych dodatkowych wybierane są zmienne o współczynnikach równych jeden. Zmienne w równościach (2) - (4) są podstawowe i wpisują się w linię - o współczynnikach równych 0. Aby wypełnić tabelę simpleks należy przekształcić funkcję celu do postaci 
. W ten sposób w końcu otrzymujemy:
Podczas kompilowania tabeli simpleks przestrzegane są następujące zasady:
skrajna lewa kolumna zawiera podstawowe zmienne i ;
kolumna po prawej stronie zawiera właściwe części ograniczeń;
Pierwsza linia zawiera zmienne w określonej kolejności:
najpierw, potem zmienne niepodstawowe, zmienne podstawowe znajdują się w ostatnich kolumnach przed prawą stroną (IF). Piszemy współczynniki w CT(0):
| JEŚLI | |||||||
| 1 | 0 | 0 | 0 | 0 | |||
| 0 | 1 | 0 | 0 | ||||
| 0 | 0 | 1 | 0 | ||||
| 0 | 0 | 0 | 1 |
Optymalność dowolnego z wierzchołków określają współczynniki zmiennych niepodstawowych w wierszu aktualnej tablicy simpleksowej:
W przypadku problemu maksymalizacji wierzchołek ten jest optymalny, jeśli wszystkie współczynniki dla zmiennych niepodstawowych w wierszu – są nieujemne (>0);
W przypadku problemu minimalizacji wierzchołek ten jest optymalny, jeśli wszystkie współczynniki dla zmiennych niepodstawowych w wierszu - są niedodatnie (< 0).
Jeżeli w zadaniu maksymalizacji (minimalizacji) jedna zmienna niepodstawowa w wierszu – ma współczynnik<0(>0), to aktualny punkt nie jest optymalny i konieczna jest zmiana bazy. Aby to zrobić, wybierz zmienną niepodstawową, która ma najbardziej ujemny (dodatni) współczynnik w wierszu -. Wybrana zmienna niepodstawowa zostanie uwzględniona w nowej podstawie, dlatego nazywana jest zmienną uwzględnianą. Zmienna bazowa, która zostanie usunięta z bazy, nazywana jest zmienną wykluczającą.
Wykluczona zmienna będzie zmienną podstawową, która najpierw zmieni się na „0” po przejściu do sąsiedniego wierzchołka po wprowadzeniu zmiennej uwzględnianej.
Kolumna uwzględnianej zmiennej będzie nazywana kolumną rozstrzygającą.
Ciąg wykluczonej zmiennej zostanie nazwany łańcuchem rozstrzygającym.
Przecięcie kolumny zezwalającej i wiersza definiuje element zezwalający (RE).
Aby zdefiniować wykluczoną zmienną:
podziel prawe części wszystkich podstawowych zmiennych (z wyjątkiem wiersza) przez odpowiednie dodatnie współczynniki kolumny rozstrzygającej;
wybierz najmniejszy z otrzymanych wskaźników.
Dzielenie przez „0” i wartość ujemną jest niedozwolone, ponieważ prowadzi to do braku przecinającego się wierzchołka lub wierzchołka poza ODT.
Aby przejść do sąsiedniego wierzchołka, konieczne jest utworzenie macierzy przejścia B(0), która określi zależność między ST(0) i ST(1): ST(1) = B(0) ST(0).
W przypadku dowolnej macierzy kwadratowej o wymiarze n, która ma jednostkowe orty jako (n - 1) kolumny, ułożone zgodnie z jednostkowymi ortami macierzy jednostkowej i jedną dowolną kolumnę z niezerowym elementem na głównej przekątnej, odwrotność macierz znajduje się według następującej zasady:
Każdy element kolumny j jest podzielony przez RE i zmienia znak na przeciwny, z wyjątkiem rozstrzygającego elementu.
Sztuczna podstawa początkowa. M - metoda.
Jeżeli początkowe ograniczenie jest zapisane w postaci równości „=” lub ma znak „”, to nie można od razu uzyskać akceptowalnego początkowego rozwiązania podstawowego, ponieważ pisząc problem w postaci standardowej, po wprowadzeniu dodatkowych zmiennych, wariant może się okazać, gdy otrzymane równania nie pozwalają na utworzenie początkowej dopuszczalnej bazy w postaci wektorów jednostkowych.
W tym przypadku, aby znaleźć początkową dopuszczalną podstawę, wprowadza się dodatkowe zmienne sztuczne. Zmienne sztuczne nie są związane z treścią zadania, ich wprowadzenie jest dopuszczalne tylko wtedy, gdy odpowiedni schemat obliczeniowy zapewni optymalne rozwiązanie, w którym wszystkie zmienne sztuczne będą równe zeru.
Zmienne R określają początkową dopuszczalną podstawę z punktu widzenia ewentualnego dalszego przejścia do jednego z wierzchołków ODT. Za wykorzystanie zmiennych sztucznych w funkcji celu wprowadza się karę M. W zadaniu maksymalizacji M ujemna (M<<0), в задаче минимизации М положительное (М>>0).
Właściwość M: Podczas dodawania (odejmowania) z dowolną skończoną wartością, która określa dowolną wartość, jaką może przyjąć każda ze zmiennych oryginalnego LLP, jej wartość (zmienna M) nie zmienia się, a mianowicie
Wzór (1.2), ograniczenia na nieujemność zmiennych (tak, nie) - wzór (1.3) (1.1) i = 1, ... m (1.2) (1.3) Algorytm rozwiązywania problemów programowania liniowego wymaga ich sprowadzenia do postaci kanonicznej, gdy funkcja celu ...
Podstawowe pojęcia modelowania
W procesie ludzkiego życia rozwijane są idee dotyczące pewnych właściwości rzeczywistych obiektów i ich interakcji. Reprezentacje te są tworzone przez osobę w postaci opisów obiektów, dla których używany jest język opisu. Może to być opis słowny (modele werbalne), rysunek, rysunek, wykres, układ itp. Wszystko to podsumowuje jedna koncepcja. Model, i proces budowania modelu modelowanie.
Modelowanie to uniwersalny sposób badania procesów i zjawisk świata rzeczywistego. Modelowanie ma szczególne znaczenie w badaniu obiektów niedostępnych dla bezpośredniej obserwacji i badań. Należą do nich w szczególności zjawiska i procesy społeczno-gospodarcze.
Badanie dowolnego obiektu, jakiejkolwiek formy ruchu, jest ujawnieniem nie tylko jego jakościowych, ale także ilościowych wzorców badanych przez matematykę. Powyższe w pełni odnosi się do gospodarki.
Gospodarka- jest to system produkcji społecznej, który realizuje rzeczywistą produkcję, dystrybucję, wymianę i konsumpcję dóbr materialnych niezbędnych społeczeństwu.
Odpowiednio, model ekonomiczny i matematyczny jest abstrakcją ekonomiczną wyrażoną w formalnych terminach matematycznych, której strukturę logiczną określają zarówno obiektywne właściwości przedmiotu opisu, jak i subiektywny czynnik docelowy badania, dla którego ten opis jest podejmowany.
Za pomocą metod matematycznych rozwiązywane są problemy ekonomiczne i matematyczne w rolnictwie. Wśród nich najbardziej rozwinięte są metody programowania liniowego (LP). Takie metody służą do rozwiązywania problemów ekonomicznych i matematycznych, w których zależności ilościowe wyrażane są liniowo, tj. wszystkie warunki są wyrażone jako układ równań i nierówności liniowych, a kryterium optymalności wyrażane jest jako funkcja liniowa dążąca do minimum lub maksimum (do ekstremum).
Problem programowania liniowego składa się z funkcji celu, układu ograniczeń i warunku, aby zmienne były nieujemne.
Niech funkcja n zmienne Konieczne jest znalezienie największej lub najmniejszej wartości tej funkcji, pod warunkiem, że argument 
Tak postawiony problem optymalizacji nazywany jest problemem programowania matematycznego. Wiele X nazywana jest zbiorem możliwych rozwiązań, a funkcja nazywana jest funkcją celu lub funkcją celu. Rozwiązanie dopuszczalne, dla którego funkcja przyjmuje największą (lub najmniejszą) wartość nazywamy optymalnym rozwiązaniem problemu.
Jeśli funkcja celu jest liniowa, a zbiór X jest podany za pomocą układu równań liniowych i nierówności, to problem nazywa się problemem programowania liniowego (LPP). Zatem ogólne sformułowanie problemu programowania liniowego jest następujące:
znajdź ekstremum funkcji
pod ograniczeniami
w warunkach nienegatywności
Wprowadźmy notację:
Dyby i-ty typ zasobu;
wydatki i-ty rodzaj zasobu do produkcji j-ty rodzaj produktu;
zysk jednostkowy j-ty rodzaj produktu.
W notacji zwartej problem programowania liniowego ma postać:
Notacja zwarta pokazuje, że model ogólnego problemu programowania liniowego zawiera pięć głównych elementów:
Zmienne, których wartość znajduje się w procesie rozwiązywania problemu;
Współczynniki techniczno-ekonomiczne dla zmiennych w ograniczeniach;
Objętość prawej strony nierówności, które nazywane są stałymi problemu;
Współczynniki dla zmiennych w funkcji celu, zwane oszacowaniami zmiennych;
Indeks zmiennej;
indeks ograniczenia.
funkcja docelowa(funkcja celu) to wyrażenie matematyczne, dla którego chcesz znaleźć ekstremum, czyli wartość maksymalną lub minimalną.
Zmienne x j wyznaczyć takie rodzaje i metody działania, których wymiary nie są znane i muszą być ustalone w trakcie rozwiązywania problemu. Zwykle w zadaniach dotyczących rolnictwa zmienne oznaczają pożądaną wielkość gałęzi gospodarki, rodzaje pasz w diecie, marki ciągników i maszyn rolniczych itp. Ta sama uprawa lub rodzaj inwentarza żywego może być wyrażony przez więcej niż jedną zmienną w określonych warunkach. Na przykład ziarno towarowe i paszowe; kukurydza na ziarno, kiszonkę, zielonkę; trawy wieloletnie na siano, sianokiszonkę, zielonkę, mączkę z traw i nasiona itp.
Zmienne mogą zmieniać się dowolnie w warunkach rozważanego problemu. Zmienny , którego współczynniki tworzą kolumnę jednostkową nazywa się podstawowy. Formularz zmiennych podstawowych podstawa jednostki systemy. Zmienne nieuwzględnione w podstawie jednostki noszą nazwę darmowy.
Całkowita liczba zmiennych zawartych w zadaniu jest zdeterminowana charakterem zadania, specyficznymi warunkami produkcji, możliwością zbierania informacji itp.
Zmienne mogą być wyrażone w różnych jednostkach miary: ha, q, kg, szt., szt., itp. Z natury zmienne dzielą się na główne, dodatkowe i pomocnicze. Główne zmienne to rodzaje poszukiwanej działalności: sektory gospodarki, rodzaje pasz, marki samochodów. Dodatkowe zmienne nazywane są zmiennymi, które powstają w procesie przekształcania nierówności w równania. Mogą oznaczać niewykorzystaną część zasobów, nadwyżkę nad prawą stroną nierówności (jeśli jest to nierówność typu „no more”). Zmienne pomocnicze są uwzględnione w zadaniu w celu określenia szacunkowych wartości nabytych zasobów produkcyjnych, szacunkowych wartości wskaźników efektywności ekonomicznej produkcji.
Zmienne dodatkowe i pomocnicze zawsze mają współczynniki jednostkowe (+1 lub -1).
Współczynniki techniczno-ekonomiczne (a ij) ze zmiennymi w systemie ograniczeń wyrażają one stawki nakładów zasobów produkcyjnych lub stawki produkcji na jednostkę miary zmiennej.
W obu przypadkach konieczne jest, aby współczynniki techniczno-ekonomiczne dokładnie odpowiadały okresowi planowania, dla którego problem jest rozwiązywany. Na przykład, jeśli problem zostanie rozwiązany dla analizy ekonomicznej i matematycznej produkcji za miniony okres, to współczynniki zostaną obliczone zgodnie z danymi sprawozdawczymi. Jeśli zostanie podjęta decyzja na przyszłość, to współczynniki należy obliczyć dla tej perspektywy.
Wskaźniki wydatkowania zasobów określane są najczęściej na podstawie podręczników i muszą być dostosowane do odpowiednich specyficznych warunków. Współczynniki wydajności produktu są obliczane na podstawie planowanych plonów plonów i produktywności zwierząt.
W przypadkach, w których konieczne jest uwzględnienie z góry określonych relacji między zmiennymi, współczynniki techniczno-ekonomiczne stanowią współczynniki proporcjonalności. Na przykład udział upraw w płodozmianie lub udział niektórych pasz w całej grupie paszowej itp.
Ograniczenia z prawej strony (b i) nazywane są stałymi, tj. stałe wartości. Należą do nich wielkości zasobów produkcyjnych - ziemia, robocizna, sprzęt, nawozy, inwestycje itp. Zasoby produkcyjne należy określić z uwzględnieniem ich stanu faktycznego i koniecznie uwzględnić okres planowania. Ponadto te zasoby produkcyjne, których wykorzystanie jest nierównomierne w ciągu roku, liczone są nie tylko za cały rok, ale również za poszczególne okresy lub miesiące pracowitości (zasoby pracy).
Zasoby produkcyjne definiowane są w różnych jednostkach: grunty – w ha, zasoby pracy – w osobodniach lub roboczogodzinach, sprzęt – w liczbie zmian maszyn, zmian lub produkcji dobowej itp.
Zatem określenie dostępności zasobów produkcyjnych nie jest sprawą prostą. Należy dokładnie przeanalizować działalność produkcyjną gospodarki, wykorzystanie siły roboczej, ziemi, zasobów technicznych i innych, a dopiero potem uwzględnić ich wielkość w ograniczeniach.
Prawa strona ograniczeń odzwierciedla nie tylko ilość zasobów, ale także ilość produktów wytwarzanych na wyższym lub niższym poziomie. Niższy poziom jest pokazany w tych przypadkach, gdy wielkość produkcji jest znana z góry, poniżej której gospodarstwo nie powinno produkować, a górny nie pozwala na wytwarzanie produktów powyżej określonej wielkości. Te ograniczenia nie zawsze są wymagane. Jednak prawie żaden problem z określeniem kombinacji branż nie obejdzie się bez odpowiednich ograniczeń produktowych, w przeciwnym razie rezultatem będzie jednostronne rozwiązanie. Wynika to z faktu, że efektywność branż nie jest taka sama.
We wszystkich innych ograniczeniach zera umieszcza się po prawej stronie, ponieważ określają one warunki produkcji i użytkowania produktów lub odzwierciedlają ograniczenia proporcjonalnej komunikacji.
Ograniczenie to wyrażenie matematyczne odnoszące się do zmiennych w postaci równości i nierówności. Formularz wszystkich ograniczeń system ograniczeń zadania. Układ ograniczeń w postaci matematycznej charakteryzuje warunki problemu. Kompletność odzwierciedlenia tych warunków zależy od składu ograniczeń. Dlatego przy ustalaniu liczby ograniczeń należy wziąć pod uwagę dwie okoliczności:
v uwzględniać w problemie tylko te warunki, które realnie ograniczają możliwości produkcyjne;
v zbyt wiele ograniczeń zwiększa rozmiar problemu i czyni go trudnym do rozwiązania
Istnieją trzy typy ograniczeń: równe (=), nierówności typu mniejsze lub równe (≤), nierówności typu większe lub równe (≥). Na przykład,
gdzie i = 1, 2, … , m. Oznaczono współczynniki dla zmiennych aij, gdzie indeks i– numer ograniczenia, indeks j jest numerem zmiennej, oznaczono wolne elementy (prawa strona ograniczeń) b ja, indeks i– numer ograniczenia.
Ograniczenia pierwszego typu nazywane są ograniczeniami górnymi, ponieważ lewa strona nierówności nie może przekroczyć pewnej wartości (stałej). Ograniczenia trzeciego typu nazywane są ograniczeniami niższymi, ponieważ lewa strona nierówności nie może być mniejsza niż określona wartość (stała).
Pod względem znaczeniowym wszystkie ograniczenia można podzielić na podstawowe, dodatkowe i pomocnicze.
Główne ograniczenia to są to te, które nakładają się na wszystkie lub większość zmiennych zadaniowych. Z reguły przy ich pomocy odzwierciedlane są główne warunki zadania - dla ziemi, pracy, paszy, składników odżywczych, technologii itp.
Dodatkowe ograniczenia nakładają się na część zmiennych lub na jedną zmienną. Ograniczenia te wprowadza się w przypadkach, gdy konieczne jest ograniczenie wielkości poszczególnych zmiennych od góry lub od dołu, np. z uwzględnieniem wymagań płodozmianu lub uwzględnienia fizjologicznych granic nasycenia diety poszczególnymi paszami lub ich grupami. W ten sposób dodatkowe ograniczenia odzwierciedlają różne dodatkowe warunki, które pojawiają się podczas procesu modelowania. Ale każde dodatkowe ograniczenie zawęża obszar wolności wyboru. Dlatego należy je wprowadzać w problem ostrożnie, w rozsądnych granicach iw koniecznych przypadkach.
Ograniczenia pomocnicze, z reguły nie mają one samodzielnego znaczenia i są wprowadzane do problemu w celu sformalizowania poszczególnych warunków. Należą do nich ograniczenia, które ustanawiają proporcjonalny związek między poszczególnymi zmiennymi lub ich grupami.
Ocena zmiennych w funkcji celu (z j) są współczynnikami wyrażającymi kwotę całkowitego dochodu lub kosztów na jednostkę miary zmiennej. Ocena zmiennej z reguły wyraża przyjęte kryterium optymalności. Może być prezentowany zarówno w naturze, jak i w gotówce, tj. koszty na jednostkę produkcji (koszt produkcji).
Warunek nieujemności zmiennych jest zapisany jako
x j≥ 0, j = 1, 2, …, n.
W rzeczywistym życiu produkcyjnym, w oparciu o warunki zadania, zgodnie z tym zapisem strukturalnego modelu ekonomicznego i matematycznego (EMM), zestawia się listę zmiennych i ograniczeń, przygotowuje wstępne informacje, budowane jest szczegółowe zadanie EMM , który jest następnie zapisywany w postaci macierzy (tabeli), wprowadzany do komputera i zgodnie z odpowiednim programem, wyniki są obliczane i analizowane.i = 1, …, m, (1.5)
j = 1, …, n. (1.6)
Wektor x = (x 1 , x 2 , …, x n), składniki x j które spełniają ograniczenia (1.2) i (1.3) [lub (1.5) i (1.6) w zadaniu minimum] nazywamy akceptowalne rozwiązanie lub akceptowalny plan Zadania LP. Zbiór wszystkich dopuszczalnych planów nosi nazwę wiele możliwych planów.
Kanoniczny postać zadania programowania liniowego charakteryzuje się tym, że zawiera funkcję celu, wszelkie ograniczenia równość, wszystkie zmienne są nieujemne.
Każdy problem programowania liniowego można zredukować do problemu programowania liniowego w postaci kanonicznej. Aby to zrobić, w ogólnym przypadku musisz być w stanie zredukować problem maksymalizacji do problemu minimalizacji; przejdź od ograniczeń nierówności do ograniczeń równości i zastąp zmienne, które nie spełniają warunku nieujemności.
Reguła redukcji problemu programowania liniowego do postaci kanonicznej składa się z następujących elementów:
1) jeżeli w pierwotnym zadaniu wymagane jest wyznaczenie maksimum funkcji liniowej, to należy zmienić znak i poszukać minimum tej funkcji;
2) jeżeli prawa strona ograniczeń jest ujemna, to ograniczenie to należy pomnożyć przez -1;
3) jeśli wśród ograniczeń występują nierówności, to przez wprowadzenie dodatkowych zmiennych zmiennych nieujemnych przekształca się je w równości. Na przykład dodatkowe zmienne Sj ograniczenia typu mniejsze lub równe (£) są wprowadzane ze znakiem plus:
Dodatkowe zmienne Sj większe lub równe (≥) ograniczenia typu są wprowadzane ze znakiem minus:
Aby wyeliminować ujemność dodatkowych zmiennych − Sj wprowadź sztuczne zmienne ze znakiem plus + Mj o bardzo dużych wartościach.
T10. Stwierdzenie problemu programowania liniowego
model matematyczny Problem ekonomiczny to zbiór zależności matematycznych opisujących proces gospodarczy.
Aby skompilować model matematyczny, konieczne jest:
1. wybrać zmienne zadania;
2. opracować system ograniczeń;
3. ustawić funkcję celu.
Zmienne zadania nazywamy wielkościami x 1 , x 2 ,…, x n, które w pełni charakteryzują proces gospodarczy. Zwykle zapisuje się je jako wektor X \u003d (x 1, x 2, ..., x n).
System ograniczeń zadań to zbiór równań i nierówności, które są spełniane przez zmienne problemu i które wynikają z ograniczonych zasobów i innych warunków ekonomicznych, na przykład dodatniości zmiennych. Ogólnie wyglądają tak:
Funkcja celu nazywa się funkcja F(X) = f(x 1 , x 2 ,…, x n) zmiennych zadania, które charakteryzują jakość zadania i których ekstremum należy znaleźć.
Ogólny problem programowania matematycznego formułuje się następująco: znajdź zmienne zadania x 1 , x 2 ,…, x n, które dostarczają ekstremum funkcji celu
F (X) \u003d f (x 1, x 2, ..., x n) ® max (min) (2)
i spełniają system ograniczeń (1).
Jeżeli funkcja celu (2) i system ograniczeń (1) są liniowe, to problem programowania matematycznego nazywa się problem programowania liniowego (LPP).
Wektor X (zbiór zmiennych zadaniowych) nazywa się akceptowalne rozwiązanie, lub plan PLP, jeśli spełnia system ograniczeń (1). Wykonalny plan X, który zapewnia ekstremum funkcji celu, nazywa się optymalne rozwiązanie ZLP.
2. Przykłady kompilacji modeli matematycznych problemów ekonomicznych
Badanie konkretnych sytuacji produkcyjnych prowadzi do ZLP, które są interpretowane jako problemy optymalnego wykorzystania ograniczonych zasobów.
1.Problem z optymalnym planem produkcji
Do produkcji dwóch rodzajów produktów T 1 i T 2 stosuje się trzy rodzaje zasobów S 1 , S 2 , S 3 . Zapasy zasobów, liczba jednostek zasobów wydanych na produkcję jednostki produkcyjnej, a także zysk ze sprzedaży jednostki produkcyjnej pokazano w tabeli:
Wymagane jest znalezienie takiego planu produkcji wyrobów, w którym zysk z jego sprzedaży będzie maksymalny.
Rozwiązanie.
Oznaczmy x 1, x 2 - liczbę jednostek produkcyjnych, odpowiednio T 1 i T 2, planowanych do produkcji. Do ich produkcji wymagane będą (x 1 + x 2) jednostki zasobu S 1, (x 1 + 4x 2) jednostki zasobu S 2, (x 1) jednostki zasobu S 3. Zużycie zasobów S 1 , S 2 , S 3 nie powinno przekraczać ich rezerw, odpowiednio 8, 20 i 5 jednostek.
Wówczas model ekonomiczno-matematyczny problemu można sformułować następująco:
Znajdź plan produkcji X \u003d (x 1, x 2), który spełnia system ograniczeń: 
i stan
pod którym funkcja przyjmuje wartość maksymalną.
Problem można łatwo uogólnić na przypadek wytwarzania n rodzajów produktów przy użyciu m rodzajów zasobów.
2.Problem optymalnej diety
Istnieją dwa rodzaje żywności K 1 i K 2 zawierające składniki odżywcze S 1 , S 2 i S 3 . Zawartość liczby jednostek składników pokarmowych w 1 kg każdego rodzaju paszy, wymagane minimum składników pokarmowych, a także koszt 1 kg paszy przedstawiono w tabeli:
Konieczne jest sporządzenie dziennej racji pokarmowej o minimalnym koszcie, w której zawartość każdego rodzaju odżywki nie byłaby mniejsza niż ustalony limit.
Rozwiązanie.
Oznaczmy x 1, x 2 - ilość paszy K 1 i K 2 zawarta w dziennej diecie. Wtedy dieta ta będzie zawierała (3x 1 + x 2) jednostki substancji odżywczej S 1, (x 1 + 2x 2) jednostki substancji S 2, (x 1 + 6x 2) jednostki substancji odżywczej S 3. Ponieważ zawartość składników odżywczych S 1 , S 2 i S 3 w diecie powinna wynosić odpowiednio 9, 8 i 12 jednostek, ekonomiczno-matematyczny model problemu można sformułować w następujący sposób:
Skomponuj codzienną dietę X \u003d (x 1, x 2), spełniając system ograniczeń:
i stan
pod którym funkcja przyjmuje wartość minimalną.
Formularze zapisu PLP
W LLP wymagane jest znalezienie ekstremum liniowej funkcji celu:
z ograniczeniami:
i warunek nienegatywności
gdzie a ij , b i , c j ( , ) mają stałe.
Tak napisano ZLP ogólny Formularz. Jeśli system ograniczeń zawiera tylko nierówności, to LLP jest reprezentowany w standard Formularz. Kanoniczny (główny) forma notacji ZLP jest notacją, gdy system ograniczeń zawiera tylko równości. Tak więc powyższe licencje LLP są napisane w standardowej formie.
Ogólne, standardowe i kanoniczne formy LLP są równoważne w tym sensie, że każdą z nich za pomocą prostych przekształceń można przepisać w innej formie. Oznacza to, że jeśli istnieje sposób na rozwiązanie jednego z tych problemów, wówczas można określić optymalny plan dla dowolnego z nich.
Aby przejść z jednej formy notacji LLP do innej, trzeba być w stanie przejść od ograniczeń nierówności do ograniczeń równości i vice versa.
Ograniczenie nierówności (£) można przekształcić w ograniczenie równości, dodając dodatkową nieujemną zmienną po jego lewej stronie, a ograniczenie nierówności (³) można przekształcić w ograniczenie równości, odejmując dodatkową nieujemną zmienną od jej lewa strona. Liczba wprowadzonych dodatkowych zmiennych nieujemnych jest równa liczbie transformowanych ograniczeń nierównościowych.
Wprowadzono dodatkowe zmienne mają sens ekonomiczny. Zatem, jeżeli ograniczenia pierwotnego potoku PLP odzwierciedlają zużycie i dostępność zasobów, wówczas wartość dodatkowej zmiennej PLP w postaci kanonicznej jest równa objętości niewykorzystanego odpowiedniego zasobu.
Przykład 1. Napisz w formie kanonicznej ZLP:
z ograniczeniami:
Rozwiązanie.
Funkcja celu pozostaje niezmieniona:
System nierówności zostaje przekształcony w system równości:
Przy rozwiązywaniu LLP metodą graficzną wymagane jest przejście z formy kanonicznej do formy standardowej.
Aby sprowadzić LLP do standardowej formy, użyj Metoda Jordana-Gaussa Rozwiązania SLAU. W przeciwieństwie do metody Gaussa, w której rozszerzona macierz układu sprowadzana jest do postaci schodkowej, w metodzie Jordana-Gaussa w ramach macierzy rozszerzonej formowana jest macierz jednostkowa. Dlatego ruch wsteczny nie jest tutaj wymagany.
Aby przekonwertować oryginalny kanoniczny LLP na równoważny standardowy LLP:
a) w rozszerzonej macierzy układu ograniczeń wybierany jest niezerowy element aqp. Ten element nazywa się dozwalający, a q - i wiersz i p-ta kolumna o nazwie włącz wiersz i włącz kolumnę.
b) łańcuch rozstrzygający jest przepisany bez zmian, a wszystkie elementy kolumny rozstrzygającej, z wyjątkiem kolumny rozstrzygającej, są zastępowane zerami. Pozostałe elementy macierzy rozszerzonej są określane za pomocą „reguły prostokąta”:
Rozważmy cztery elementy rozszerzonej macierzy: element a ij do przekształcenia, element rozstrzygający aqp oraz elementy a i p i aqj . Aby znaleźć element a ij, od elementu a ij należy odjąć iloczyn elementów a i p oraz qj znajdujących się w przeciwległych wierzchołkach prostokąta, podzielony przez rozstrzygający element a qp:
c) dozwolone niewiadome są jednocześnie wyłączone z funkcji celu. W tym celu w rozwiniętej macierzy w ostatnim wierszu zapisywane są współczynniki funkcji celu. Obliczenia uwzględniają fakt, że nie można wybrać elementu włączającego w ostatniej linii.
Przykład 2. Zmień na standardowy formularz:
Rozwiązanie.
Stosując metodę Jordana-Gaussa, sprowadzamy układ równań ograniczających LLP do równoważnego układu nierówności. Wybierzmy trzeci element pierwszego wiersza jako rozstrzygający element:
Liczba -9 uzyskana w ostatniej kolumnie ostatniego wiersza musi być wpisana do funkcji celu z przeciwnym znakiem. W wyniku przekształceń LLP przyjmuje postać:
Dlatego zmienne x 2 i x 3 są nieujemne, następnie odrzucając je, możemy zapisać ZLP w postaci symetrycznej:
W kanonicznej formie LLP funkcja celu może być zarówno minimalizowana, jak i maksymalizowana. Aby przejść od znalezienia maksimum do znalezienia minimum lub na odwrót, wystarczy zmienić znaki współczynników funkcji celu: F 1 = - F. Powstały problem i oryginalny LLP mają to samo optymalne rozwiązanie, a wartości funkcji celu na tym rozwiązaniu różnią się tylko podpisać.
Nieruchomości ZLP
1. Zbiór wszystkich dopuszczalnych rozwiązań układu ograniczeń zadania programowania liniowego jest wypukły.
Zbiór punktów nazywa się wypukły, jeśli zawiera cały odcinek łączący dowolne dwa punkty tego zbioru.
Zgodnie z tą definicją wielokąt z rys. 1a jest zbiorem wypukłym, podczas gdy wielokąt z rys. 1b nie jest, ponieważ odcinek MN między jego dwoma punktami M i N nie należy całkowicie do tego wielokąta.
Zbiory wypukłe mogą być nie tylko wielokątami. Przykładami zestawów wypukłych są okrąg, sektor, segment, sześcian, piramida itp.
2. Jeżeli LLP ma rozwiązanie optymalne, to funkcja liniowa przyjmuje wartość maksymalną (minimalną) w jednym z punktów narożnych wielościanu decyzyjnego. Jeśli funkcja liniowa przyjmuje wartość maksymalną (minimalną) w więcej niż jednym punkcie narożnym, to przyjmuje ją w dowolnym punkcie, który jest wypukłą kombinacją liniową tych punktów.
Punkt X nazywa się wypukła kombinacja liniowa punkty X 1 , X 2 ,…, X n, jeżeli spełnione są następujące warunki:
X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n,
αj ≥ 0, Σαj = 1.
Jest oczywiste, że w szczególnym przypadku dla n = 2 wypukła kombinacja liniowa dwóch punktów jest łączącym je odcinkiem.
3. Każdemu dopuszczalnemu rozwiązaniu podstawowemu kanonicznego układu więzów LLP odpowiada punkt narożny wielościanu rozwiązania i odwrotnie, każdemu punktowi narożnemu wielościanu rozwiązania odpowiada dopuszczalne rozwiązanie podstawowe.
Z dwóch ostatnich właściwości wynika, że jeśli LLP ma rozwiązanie optymalne, to pokrywa się z co najmniej jednym z jego dopuszczalnych rozwiązań podstawowych.
Zatem ekstremum funkcji liniowej LLP należy szukać wśród skończonej liczby jej dopuszczalnych rozwiązań podstawowych.
W praktyce ograniczenia w problemie programowania liniowego są często podawane nie przez równania, ale przez nierówności.
Pokażmy, jak można przejść od problemu z ograniczeniami nierównościowymi do głównego problemu programowania liniowego.
Niech będzie problem programowania liniowego ze zmiennymi , w którym ograniczenia nałożone na zmienne mają postać nierówności liniowych. W niektórych z nich może występować znak nierówności, a w innych (drugi typ sprowadza się do pierwszego przez prostą zmianę znaku obu części). Dlatego wszystkie ograniczenia nierówności ustalamy w postaci standardowej:
Wymagane jest znalezienie takiego zbioru wartości nieujemnych, który spełniałby nierówności (4.1), a dodatkowo minimalizowałby funkcję liniową:
Z tak postawionego problemu łatwo przejść do głównego problemu programowania liniowego. Rzeczywiście, wprowadzamy notację:
gdzie są nowe zmienne, które nazwiemy "dodatkowymi". Zgodnie z warunkami (4.1), te dodatkowe zmienne, tak jak powinny, muszą być nieujemne.
Mamy więc do czynienia z problemem programowania liniowego w następującym sformułowaniu: znaleźć takie nieujemne wartości zmiennych, aby spełniały układ równań (4.3) i jednocześnie zminimalizować liniową funkcję tych zmiennych:
Jak widać, mamy przed sobą w czystej postaci główny problem programowania liniowego (LPP). Równania (4.3) podane są w postaci już rozwiązanej w odniesieniu do zmiennych podstawowych, które są wyrażone w postaci zmiennych swobodnych. Funkcja L jest wyrażona tylko w kategoriach zmiennych „początkowych” (współczynniki zmiennych „dodatkowych” w niej są równe zero).
W ten sposób sprowadziliśmy problem programowania liniowego z ograniczeniami nierównościowymi do głównego problemu programowania liniowego, ale z większą liczbą zmiennych niż pierwotnie w zadaniu.
Przykład 1 Istnieje problem programowania liniowego z ograniczeniami nierównościowymi: znajdź nieujemne wartości zmiennych, które spełniają warunki
i zminimalizowanie funkcji liniowej
Wymagane jest sprowadzenie tego problemu do postaci OLP.
Rozwiązanie. Nierówności (4.4) sprowadzamy do standardowej postaci;
Wprowadzamy dodatkowe zmienne:
Zadanie polega na znalezieniu nieujemnych wartości zmiennych
spełnianie równań (4.6) i minimalizowanie funkcji liniowej (4.5).
Pokazaliśmy, jak można przejść od problemu programowania liniowego z ograniczeniami nierównościowymi do problemu z ograniczeniami równościowymi (ELP). Odwrotne przejście jest zawsze możliwe - od LLP do problemu z ograniczeniami nierówności. Jeśli w pierwszym przypadku zwiększyliśmy liczbę zmiennych, to w drugim zmniejszymy ją, eliminując zmienne podstawowe i pozostawiając tylko wolne.
Przykład 2. Istnieje problem programowania liniowego z ograniczeniami równości (OLP):
i funkcja do zminimalizowania
Wymagane jest zapisanie go jako problemu programowania liniowego z ograniczeniami nierównościowymi.
Rozwiązanie. Ponieważ wybieramy jakieś dwie zmienne jako wolne. Zauważ, że zmienne nie mogą być wybrane jako wolne, ponieważ są powiązane pierwszym z równań (4 7): wartość jednej z nich jest całkowicie określona przez wartość drugiej, a zmienne wolne muszą być niezależne
Z tego samego powodu nie można wybrać zmiennych jako wolnych (łączy je drugie równanie). Wybieramy jako wolne zmienne i wyrażamy całą resztę za pomocą nich:
Ponieważ warunki (4 9) można zastąpić nierównościami:
Przekażmy w wyrażeniu funkcji liniowej L zmienne wolne Podstawiając w L zamiast i ich wyrażenia (4.9). Dostawać.
