Programowanie liniowe. Metodyczne podstawy opracowywania decyzji zarządczych Rozwiązanie nazywa się optymalnym

Obecnie w programie kształcenia specjalności związanych z ekonomią, finansami i zarządzaniem znajduje się dyscyplina „Metody podejmowania decyzji optymalnych”. W ramach tej dyscypliny studenci studiują matematyczną stronę optymalizacji, badań operacyjnych, podejmowania decyzji i modelowania. Główną cechą tej dyscypliny jest wspólne badanie metod matematycznych z ich zastosowaniem do rozwiązywania problemów ekonomicznych.

Zadania optymalizacyjne: informacje ogólne

Jeśli weźmiemy pod uwagę przypadek ogólny, wówczas znaczenie problemu optymalizacji polega na znalezieniu tzw. rozwiązania optymalnego, które maksymalizuje (minimalizuje) funkcję celu w określonych warunkach ograniczających.

W zależności od właściwości funkcji problemy optymalizacyjne można podzielić na dwa typy:

  • problem programowania liniowego (wszystkie funkcje są liniowe);
  • problem programowania nieliniowego (przynajmniej jedna z funkcji nie jest liniowa).

Szczególnymi przypadkami problemów optymalizacyjnych są problemy programowania ułamkowo-liniowego, dynamicznego i stochastycznego.

Najczęściej badanymi problemami optymalizacyjnymi są problemy programowania liniowego (LPP), których rozwiązania przyjmują wyłącznie wartości całkowite.

PPP: formułowanie, klasyfikacja

Problem programowania liniowego w ogólnym przypadku polega na znalezieniu minimum (maksimum) funkcji liniowej przy pewnych ograniczeniach liniowych.

Ogólny ZLP to problem formy

pod ograniczeniami

gdzie są zmienne, są podane liczby rzeczywiste, są funkcją celu, są planem problemu, (*)-(***) są ograniczeniami.

Ważną cechą ZLP jest to, że ekstremum funkcji celu osiągane jest na granicy obszaru rozwiązań dopuszczalnych.

Praktyczne zastosowania ekonomiczne metod optymalnego rozwiązania znajdują się w rozwiązywaniu problemów typu:

  • problemy dotyczące mieszanin (tj. planowanie składu produktów);
  • problemy optymalnej alokacji zasobów w planowaniu produkcji;

PAP: przykłady

Problem z mieszaniną

Rozwiązanie problemu mieszanin polega na znalezieniu najtańszego zestawu, składającego się z określonych materiałów wyjściowych, które zapewnią mieszaninę o pożądanych właściwościach.

Problem alokacji zasobów

Firma produkuje N różne produkty, których produkcja wymaga M różnego rodzaju zasoby. Zasoby wykorzystanych zasobów są ograniczone i wynoszą odpowiednio b 1, b 2,…, b m c.u. Ponadto znane są współczynniki technologiczne ij, które pokazują, ile jednostek I--ty zasób potrzebny do wytworzenia jednej jednostki produktu J-ty typ (). Zysk, jaki firma uzyskuje ze sprzedaży produktu J-ty typ, wynosi c j jednostki monetarne Konieczne jest sporządzenie planu produkcji produktów, którego zysk przedsiębiorstwa podczas realizacji będzie największy.

Problemy dotyczące mieszanin i alokacji zasobów są często zapisywane w formie tabelarycznej.

Zasoby Wymagania Rezerwy
B 1 … Bn
1 b 1
… …
Jestem b m
Zysk c 1 … c n

Problemy dotyczące mieszanin i alokacji zasobów można rozwiązać na kilka sposobów:

  • metoda graficzna (w przypadku małej liczby zmiennych w modelu matematycznym);
  • metoda simpleksowa (jeśli liczba zmiennych w modelu matematycznym jest większa niż dwa).

Problem transportu odnosi się do klasy zadań, które mają pewną specyficzną strukturę. Najprostszym problemem transportowym jest problem transportu produktu do miejsca docelowego z punktów wyjścia przy minimalnych kosztach transportu wszystkich produktów.

Dla przejrzystości i łatwości postrzegania stan problemu transportowego jest zwykle zapisywany w poniższej tabeli:

Ogólnie rzecz biorąc, rozwiązywanie problemu transportowego odbywa się w kilku etapach:

  • Etap I: budowa wstępnego planu odniesienia;
  • Etap II: sprawdzenie planu referencyjnego pod kątem optymalności;
  • Etap III: doprecyzowanie planu referencyjnego, jeżeli nie jest on optymalny.

Istnieje kilka metod uzyskania początkowego planu odniesienia, na przykład metoda północno-zachodniego narożnika, metoda Vogla i metoda minimalnych kosztów.

Plan sprawdzany jest pod kątem optymalności metodą potencjału:

- dla zajętych komórek,
- dla niezajętych komórek.

Jeśli plan nie jest optymalny, budowany jest cykl i redystrybucja transportu.

Wniosek

Nie jest możliwe omówienie całej teorii i praktyki metod optymalnego rozwiązania w ramach jednego artykułu, dlatego uwzględniono jedynie niektóre punkty, które pozwalają dać ogólne pojęcie o tej dyscyplinie, problemach i metodach ich rozwiązywania.

Dodatkowo warto zaznaczyć, że do sprawdzania uzyskanych rozwiązań problemów optymalizacyjnych można bardzo efektywnie wykorzystać dodatek „Solution Search” pakietu MS Excel. Ale to właściwie inna historia, podobnie jak szczegółowe rozważenie metod rozwiązywania problemów optymalizacyjnych.

Oto kilka podręczników do studiowania metod optymalnych rozwiązań:

  1. Bandi B. Podstawy programowania liniowego: Trans. z angielskiego – M.: Radio i Łączność, 1989. – 176 s.
  2. Kremer N.Sh. Badania operacyjne w ekonomii: Proc. podręcznik dla uniwersytetów / N.Sh. Kremer, BA Putko, I.M. Trishin, M.N. Friedmana; wyd. prof. N.Sh. Kremera. – M.: JEDNOŚĆ, 2005. – 407 s.

Rozwiązanie niestandardowych metod optymalizacji

Pomożemy Ci rozwiązać wszelkie problemy, stosując optymalne metody rozwiązywania. Rozwiązania problemów możesz zamówić na naszej stronie internetowej. Wystarczy wskazać termin i załączyć plik z zadaniem. Twoje zamówienie jest bezpłatne.

Problem programowania liniowego (LPP) to problem znalezienia największej (lub najmniejszej) wartości funkcji liniowej na zbiorze wielościennym wypukłym.

Metoda simpleksowa jest metodą rozwiązywania problemów programowania liniowego. Istota metody polega na znalezieniu wstępnego planu wykonalnego, a następnie jego ulepszaniu, aż do osiągnięcia maksymalnej (lub minimalnej) wartości funkcji celu w danym zbiorze wielościennym wypukłym lub ustalenia nierozwiązywalności problemu.

Rozważ następujący problem programowania liniowego w postaci kanonicznej:

(1)
(2)
(3)

Metoda sztucznej bazy

Jak pokazano powyżej, dla problemu zapisanego w postaci kanonicznej, jeśli należy do wektorów kolumnowych macierzy A Jest M jednostkowe i liniowo niezależne, można bezpośrednio określić plan referencyjny. Jednak w przypadku wielu problemów programowania liniowego zapisywanych w postaci kanonicznej i posiadających plany odniesienia, wśród wektorów kolumnowych macierzy A nie zawsze dostępne M jednostkowe i liniowo niezależne. Rozważ następujący problem:

Załóżmy, że musimy znaleźć maksimum funkcji

na warunkach

gdzie są pierwsi N elementy są zerowe. Zmienne nazywane są sztucznymi. Kolumny wektorów

(28)

tworzą tak zwaną sztuczną podstawę M-wymiarowa przestrzeń wektorowa.

Ponieważ rozszerzony problem ma plan odniesienia, jego rozwiązanie można znaleźć metodą sympleksową.

Twierdzenie 4. Jeśli w planie optymalnym rozszerzony problem (24)−(26) wartości zmiennych sztucznych , To jest optymalnym planem problemu (21)−(23).

Zatem jeśli w znalezionym optymalnym planie dla rozszerzonego problemu wartości zmiennych sztucznych są równe zeru, to otrzymuje się optymalny plan dla pierwotnego problemu. Zastanówmy się bardziej szczegółowo nad znalezieniem rozwiązania rozszerzonego problemu.

Wartość funkcji celu dla planu odniesienia (27):

Zauważamy to F(X) i składają się z dwóch niezależnych części, z których jedna jest zależna M, a drugi - nie.

Po obliczeniu F(X) i ich wartości, a także początkowe dane rozszerzonego zadania są wprowadzane do tabeli simplex, jak pokazano powyżej. Jedyna różnica polega na tym, że ta tabela zawiera o jeden wiersz więcej niż zwykła tabela jednostronna. W tym samym czasie ( M Linia +1) zawiera współczynniki, które nie zawierają M, i w ( M+2) linia – współczynniki dla M.

Podczas przechodzenia z jednego planu odniesienia do drugiego wektor odpowiadający największej liczbie ujemnej w wartości bezwzględnej ( M+2) linie. Sztuczny wektor wyłączony z bazy nie ma sensu ponownie wprowadzać do bazy. Przy przejściu na inny plan odniesienia może się zdarzyć, że żaden ze sztucznych wektorów nie zostanie wykluczony z podstawy. Ponowne obliczenie tabeli simpleksowej przy przejściu z jednego planu odniesienia do drugiego odbywa się zgodnie ze zwykłymi zasadami metody simpleksowej (patrz wyżej).

Proces iteracyjny realizowany jest wg M Linia +2 o długości elementów M+2 linie odpowiadające zmiennym nie stanie się nieujemna. Co więcej, jeśli z podstawy wykluczy się zmienne sztuczne, wówczas znaleziony plan rozszerzonego problemu odpowiada pewnemu planowi odniesienia problemu pierwotnego.

M+2 rzędy, kolumny X 0 jest ujemne, wówczas pierwotny problem nie ma rozwiązania.

Jeśli nie, wszystkie zmienne sztuczne są wyłączone z podstawy i elementu M+2 rzędy, kolumny X 0 jest równe zero, to plan odniesienia pierwotnego problemu jest zdegenerowany i baza zawiera przynajmniej jeden z wektorów sztucznej bazy.

Jeżeli pierwotny problem zawiera kilka wektorów jednostkowych, to należy je uwzględnić w sztucznej bazie.

Jeśli podczas iteracji M Linia +2 nie zawiera już elementów ujemnych, następnie proces iteracji jest kontynuowany M Linia +1, aż do znalezienia optymalnego planu rozszerzonego problemu lub ujawnienia się nierozwiązywalności problemu.

Zatem proces znajdowania rozwiązania problemu programowania liniowego (21)−(23) przy użyciu metody sztucznej bazy obejmuje następujące główne etapy:

  • Skomponuj rozszerzony problem (24)−(26).
  • Znajdź plan odniesienia rozszerzonego problemu.
  • Stosując metodę sympleksową, z podstawy wyklucza się sztuczne wektory. W rezultacie odnajduje się plan odniesienia pierwotnego problemu lub rejestruje się jego nierozwiązywalność.
  • Korzystając ze znalezionego planu odniesienia ZLP (21)−(23), albo znajdują optymalny plan pierwotnego problemu, albo ustalają jego nierozwiązywalność.

Aby rozwiązać problemy z programowaniem liniowym online, użyj kalkulatora

Ogólny problem programowania liniowego (GLP) jest sformułowany w następujący sposób - znajdź zmienne problemu X 1 , X 2 , ..., X n , które zapewniają ekstremum funkcji celu

Dopuszczalne rozwiązanie (plan) problemu programowania liniowego (LPP) jest dowolne N-wektor wymiarowy X=(X 1 , X 2 , ..., X n) spełnienie systemu równości i nierówności. Zbiór możliwych rozwiązań problemu stanowi dziedzinę możliwych rozwiązań D.

Optymalne rozwiązanie (plan) problemu programowania liniowego to rozwiązanie wykonalne, które spełnia funkcję celu Z(X) osiąga ekstremum.

Kanoniczny problem programowania liniowego (CLP) ma postać

(1.2)

Różni się od OZLP tym, że jego system ograniczeń jest układem składającym się wyłącznie z równań, a wszystkie zmienne są nieujemne.

Doprowadzenie OPLP do postaci kanonicznej OPLP:

Aby zastąpić pierwotny problem minimalizacji problemem maksymalizacji (lub odwrotnie problem maksymalizacji problemem minimalizacji), wystarczy pomnożyć funkcję celu przez „-1” i poszukać maksimum (minimum) wynikowej funkcji;

Jeżeli pomiędzy ograniczeniami występują nierówności, to poprzez wprowadzenie dodatkowych zmiennych nieujemnych X n +1 ≥ 0 przekształcają się w równości:

nierówność A ja 1 X 1 +…+A W X n ≥ B i zastępuje się równością A ja 1 X 1 +…+A W X n+ X n +1 = B I,

nierówność A ja 1 X 1 +…+A W X n ≤ B i zastępuje się równością A ja 1 X 1 +…+A W X n+ X n +1 = B I;

Jeśli jakaś zmienna X k nie ma ograniczeń co do znaku, wówczas zostaje zastąpiony (w funkcji celu i we wszystkich ograniczeniach) różnicą pomiędzy dwiema nowymi zmiennymi nieujemnymi: X k = X" k – X” k , Gdzie X" k ≥ 0. X” k ≥ 0.

Graficzna metoda rozwiązywania ZLP z dwiema niewiadomymi

ZLP z dwiema niewiadomymi ma postać:

Metoda opiera się na możliwości graficznego zobrazowania obszaru rozwiązań dopuszczalnych i znalezienia spośród nich rozwiązania optymalnego.

Obszar możliwych rozwiązań (ADA) problemu jest wielokątem wypukłym i jest skonstruowany jako przecięcie (część wspólna) obszarów rozwiązań każdej z nierówności ograniczeń problemu.

Dziedzina rozwiązania nierówności A ja 1 X 1 +A ja 2 X 2 ≤ B i jest jedną z dwóch półpłaszczyzn, na których znajduje się linia A ja 1 X 1 +A ja 2 X 2 = B i odpowiadający tej nierówności dzieli płaszczyznę współrzędnych. Aby określić, która z dwóch półpłaszczyzn jest obszarem rozwiązania, wystarczy podstawić do nierówności współrzędne dowolnego punktu nie leżącego na linii podziału:

Jeżeli nierówność jest prawdziwa, to obszarem rozwiązania jest półpłaszczyzna zawierająca ten punkt;

Jeśli nierówność nie jest prawdziwa, wówczas dziedziną rozwiązania jest półpłaszczyzna niezawierająca tego punktu.

Aby znaleźć optymalne spośród możliwych rozwiązań, stosuje się linie poziomu.

Linia pozioma jest linią prostą Z 1 X 1 +Z 2 X 2 = l, Gdzie l= const, przy której funkcja celu problemu przyjmuje stałą wartość. Wszystkie linie poziomu są do siebie równoległe.

Gradient funkcji celu absolwent Z(X) określa wektor normalny C = (C 1 , C 2) linie poziomu. Funkcja celu na liniach poziomu wzrasta, jeśli linie poziomu przesuwają się w kierunku ich normalnej, i maleje w kierunku przeciwnym.

Linią odniesienia jest linia pozioma, która ma co najmniej jeden punkt wspólny z ODR i w stosunku do której ODR leży w jednej z półpłaszczyzn. Nieparzysty charakter problemu ma nie więcej niż dwie linie wsparcia.

Optymalne rozwiązanie ZLP leży na linii odniesienia w punkcie narożnym wielokąta ODR. ZLP ma unikalne rozwiązanie, jeśli linia odniesienia przechodzi przez jeden punkt narożny ODR i nieskończoną liczbę rozwiązań, jeśli linia nośna przechodzi przez krawędź wielokąta ODR. ZLP nie ma rozwiązania, jeśli ODP jest zbiorem pustym (kiedy układ ograniczeń jest niespójny) i jeśli ODP jest nieograniczony w kierunku ekstremum (funkcja celu jest nieograniczona).

Algorytm graficznej metody rozwiązywania ZLP z dwiema niewiadomymi:

    Zbuduj ODR.

    Konstruuj wektor normalny C = (C 1 , C 2) i linię poziomą Z 1 X 1 +Z 2 X 2 = 0 przechodzące przez początek i prostopadle do wektora Z.

    Przesuń linię poziomu do linii odniesienia w kierunku wektora Z w problemie max lub w odwrotnym kierunku – w problemie min.

    Jeżeli, gdy linia poziomu przesuwa się w kierunku ekstremum, ODR dąży do nieskończoności, to ZLP nie ma rozwiązania ze względu na nieograniczoną funkcję celu.

    Jeżeli ZLP ma rozwiązanie optymalne, to aby je znaleźć, należy rozwiązać łącznie równania prostych ograniczających ODR i mających punkty wspólne z linią odniesienia. Jeżeli ekstremum zostanie osiągnięte w dwóch punktach narożnych, to ZLP ma nieskończony zbiór rozwiązań należących do krawędzi ODR ograniczonej tymi punktami narożnymi. W tym przypadku obliczane są współrzędne obu punktów narożnych.

    Oblicz wartość funkcji celu w punkcie ekstremalnym.

Simpleksowa metoda rozwiązywania problemów

Metoda simplex opiera się na następujących założeniach:

ODP problemu programowania liniowego jest zbiorem wypukłym ze skończoną liczbą punktów narożnych;

Optymalne rozwiązanie ZLP jest jednym z punktów narożnikowych ODR. Punkty narożne ODR reprezentują algebraicznie niektóre podstawowe (odniesienia) rozwiązania układu ograniczeń ZLP.

Rozwiązaniem podstawowym (referencyjnym) ZLP jest takie rozwiązanie dopuszczalne X 0 =(X 10 , X 20 , ..., X m 0 , 0,…0), dla których wektory warunków (kolumny współczynników dla nieznanych więzów w systemie) są liniowo niezależne.

Niezerowe współrzędne X 10 , X 20 , ..., X m 0 rozwiązań X 0 nazywane są zmiennymi bazowymi, pozostałe współrzędne rozwiązania X 0 - zmienne wolne. Liczba niezerowych współrzędnych rozwiązania odniesienia nie może być większa od rangi R systemy ograniczeń PLP (liczba liniowo niezależnych równań w układzie ograniczeń PLP). Następnie zakładamy, że układ ograniczeń PLP składa się z liniowo niezależnych równań, tj. R = M.

Znaczenie metody simpleksowej polega na celowym przejściu od jednego rozwiązania referencyjnego PLP do innego (tj. od jednego punktu narożnego ODP do drugiego) w kierunku ekstremum i składa się z sekwencji etapów:

Znajdź początkowe rozwiązanie wsparcia;

Dokonaj przejścia z jednego rozwiązania referencyjnego na drugie;

Określ kryterium osiągnięcia optymalnego rozwiązania lub wyciągnij wniosek o braku rozwiązania.

Algorytm wykonaniaMetoda simpleksowa ZLP

Algorytm metody simpleks przechodzi z jednego rozwiązania referencyjnego PLP do drugiego w kierunku ekstremum funkcji celu.

Niech ZLP będzie podane w postaci kanonicznej (1.2) i warunek będzie spełniony

B ja ≥ 0, I=1,2,…,M, (1.3)

zależność (1.3) można zawsze spełnić mnożąc odpowiednie równanie przez „-1” w przypadku wartości ujemnej B I. Wierzymy również, że układ równań w ograniczeniach problemu (1.2) jest liniowo niezależny i ma rangę R = M. W tym przypadku wektor rozwiązania podporowego ma M niezerowe współrzędne.

Niech pierwotny problem (1.2), (1.3) sprowadzi się do postaci, w której występują zmienne podstawowe X 1 , X 2 , ..., X m są wyrażone w postaci zmiennych wolnych X M + 1 , X M + 2 , ..., X N

(1.4)

Na podstawie tych zależności skonstruujemy tabelę 1

Tabela 1.

Tabela 1 nazywana jest tabelą simplex. Wszelkie dalsze przekształcenia wiążą się ze zmianami zawartości tej tabeli.

Algorytm zmetoda złożona:

1. W ostatniej linijce Z Tabele Simplex w zadaniu min znajdują najmniejszy element dodatni (w problemie max najmniejszy element ujemny), nie licząc terminu wolnego. Kolumna odpowiadająca temu elementowi nazywana jest kolumną włączającą.

2. Oblicz stosunek wyrazów wolnych do elementów dodatnich kolumny rozdzielczości (stosunek simpleksowy). Znajdź najmniejszą z tych relacji simpleks; odpowiada ona ciągowi rozdzielczości.

3. Na przecięciu rozdzielającego rzędu i rozstrzygającej kolumny znajduje się element rozstrzygający.

4. Jeżeli istnieje kilka relacji simpleksowych o tej samej wielkości, wybierz którąkolwiek z nich. To samo dotyczy dodatnich elementów ostatniego wiersza tabeli simplex.

5. Po znalezieniu elementu rozstrzygającego przejdź do kolejnej tabeli. Nieznane zmienne odpowiadające wierszowi i kolumnie rozdzielczości są zamieniane. W tym przypadku zmienna podstawowa staje się zmienną wolną i odwrotnie. Tabela simplex jest konwertowana w następujący sposób (tabela 2):

Tabela 2

6. Element tabeli 2, odpowiadający elementowi rozdzielczemu tabeli 1, jest równy odwrotności elementu rozdzielającego.

7. Elementy wiersza tabeli 2 odpowiadające elementom wiersza dopuszczającego tabeli 1 uzyskuje się poprzez podzielenie odpowiednich elementów tabeli 1 przez element dopuszczający.

8. Elementy kolumny tabeli 2 odpowiadające elementom kolumny rozdzielczej tabeli 1 uzyskuje się poprzez podzielenie odpowiednich elementów tabeli 1 przez element rozdzielający i przyjmuje się je z przeciwnym znakiem.

9. Pozostałe elementy obliczane są wg reguła prostokąta: W tabeli 1 rysujemy w myślach prostokąt, którego jeden wierzchołek pokrywa się z elementem rozstrzygającym (Re), a drugi z elementem, którego szukamy; Oznaczmy element w nowej tablicy 2 przez (Ne), a element w tym samym miejscu starej tablicy 1 przez (Se). Pozostałe dwa wierzchołki A i B uzupełniają figurę w prostokąt. Wtedy wymagany element He z tabeli 2 jest równy He = Se – A*B/Re.

10. Kryterium optymalności. Gdy tylko zostanie uzyskana tabela, w której wszystkie elementy ostatniego wiersza w zadaniu min są ujemne (w zadaniu max wszystkie elementy są dodatnie), uznaje się, że znaleziono ekstremum. Optymalna wartość funkcji celu jest równa członowi swobodnemu w wierszu Z, a optymalne rozwiązanie wyznaczają wolne wyrazy zmiennych bazowych. Wszystkie wolne zmienne są ustawione na zero.

11. Jeżeli wszystkie elementy w kolumnie rozdzielczości są ujemne, problem nie ma rozwiązań (nie osiągnięto minimum).

Metoda sztucznej bazy rozwiązywania ZLP

Algorytm metody simpleks ma zastosowanie, jeśli wybrane zostanie dowolne rozwiązanie odniesienia PLP, tj. oryginalny PLP (1.2) zostanie zredukowany do postaci (1.4). Metoda sztucznej bazy oferuje procedurę konstruowania takiego rozwiązania referencyjnego.

Metoda sztucznej bazy polega na wprowadzeniu sztucznych zmiennych bazowych y 1 , y 2 ,…, y m , za pomocą którego system ograniczeń PLP (2.2)

(1.5)

można przekształcić do postaci

(1.6)

Systemy (1.5) i (1.6) będą równoważne, jeśli wszystkie y I będzie równa zeru. Tak jak poprzednio wierzymy, że wszystko B I ≥ 0. W celu Na I były równe 0, musimy przekształcić problem tak, aby wszystkie sztuczne zmienne bazowe y I przełączone na zmienne wolne. Takiego przejścia można dokonać wykorzystując algorytm metody simplex w odniesieniu do dodatkowej funkcji celu

F(y) = y 1 + y 2 + ... + y m = D 0 – (D 1 X 1 +D 2 X 2 +…+D N X N). (2.7)

Tak wygląda początkowa tabela simplex dla tej metody

Po pierwsze, tabela simplex jest przekształcana w odniesieniu do funkcji celu F(y) aż do uzyskania roztworu odniesienia. Rozwiązanie referencyjne zostaje znalezione, gdy spełnione jest kryterium: F(y) = 0 i wszystkie zmienne sztuczne Na I przetłumaczone na zmienne wolne. Następnie przekreśla się wiersz z tabeli simplex dla F(y) i kolumny dla Na I i rozwiązać problem dla pierwotnej funkcji celu Z(X) aż do uzyskania optymalnego rozwiązania.

Programowanie liniowe to dział matematyki zajmujący się metodami znajdowania minimum lub maksimum funkcji liniowej skończonej liczby zmiennych, pod warunkiem, że zmienne spełniają skończoną liczbę ograniczeń w postaci równań liniowych lub nierówności liniowych.

Zatem ogólny problem programowania liniowego (GLP) można sformułować w następujący sposób.

Znajdź wartości zmiennych rzeczywistych, dla których funkcja celu

przyjmuje minimalną wartość na zbiorze punktów, których współrzędne spełniają system ograniczeń

Jak wiadomo, uporządkowany zbiór wartości N zmienne , , … jest reprezentowane przez punkt w przestrzeni n-wymiarowej. W dalszej części będziemy oznaczać ten punkt X=( , , … ).

W postaci macierzowej problem programowania liniowego można sformułować w następujący sposób:

, A– macierz rozmiarów,

Kropka X=( , , … ), spełniający wszystkie warunki, nazywa się ważny punkt . Nazywa się zbiór wszystkich dopuszczalnych punktów ważny obszar .

Optymalne rozwiązanie (optymalny plan) problem programowania liniowego nazywany jest rozwiązaniem X=( , , … ), należący do obszaru dopuszczalnego i dla którego funkcja liniowa Q przyjmuje wartość optymalną (maksymalną lub minimalną).

Twierdzenie. Zbiór wszystkich możliwych rozwiązań układu ograniczeń problemu programowania liniowego jest wypukły.

Zbiór punktów nazywa się wypukły , jeśli wraz z dowolnymi dwoma punktami zawiera ich dowolną wypukłą kombinację liniową.

Kropka X zwany wypukła kombinacja liniowa punktów, jeżeli spełnione są warunki

Zbiór wszystkich możliwych rozwiązań problemu programowania liniowego to wypukły obszar wielościenny, który będziemy odtąd nazywać wielościan rozwiązań .

Twierdzenie. Jeżeli ZLP ma rozwiązanie optymalne, to funkcja celu przyjmuje wartość maksymalną (minimalną) w jednym z wierzchołków wielościanu rozwiązania. Jeżeli funkcja celu przyjmuje wartość maksymalną (minimalną) w więcej niż jednym punkcie, to przyjmuje tę wartość w dowolnym punkcie będącym wypukłą liniową kombinacją tych punktów.

Wśród wielu rozwiązań systemu M równania liniowe opisujące wielościan rozwiązań, wyróżnia się tzw. rozwiązania podstawowe.

Podstawowe rozwiązanie systemu M równania liniowe z n zmiennymi to rozwiązanie, w którym wszystko n-m zmienne inne niż podstawowe wynoszą zero. W problemach programowania liniowego takie rozwiązania nazywane są dopuszczalne rozwiązania podstawowe (plany referencyjne).

Twierdzenie. Każdemu dopuszczalnemu rozwiązaniu podstawowemu problemu programowania liniowego odpowiada wierzchołek wielościanu rozwiązania i odwrotnie, każdemu wierzchołkowi wielościanu rozwiązania odpowiada dopuszczalne rozwiązanie podstawowe.


Z powyższych twierdzeń wynika ważny wniosek:

Jeśli problem programowania liniowego ma rozwiązanie optymalne, to pokrywa się ono z co najmniej jednym z możliwych rozwiązań podstawowych.

W konsekwencji optymalnej funkcji liniowej celu zadania programowania liniowego należy szukać wśród skończonej liczby jego możliwych rozwiązań podstawowych.