Programowanie liniowe to metoda rozwiązywania problemów optymalizacyjnych.
W pierwszych zadaniach optymalizacyjnych konieczne było ustalenie, ile różnych produktów trzeba było wyprodukować, aby uzyskać maksymalny dochód, jeśli znana jest ilość zasobów (surowce, czas pracy, wyposażenie) i ceny, przy których można uzyskać gotowe produkty. Innym rodzajem zadania jest ustalenie, w jakich warunkach zmniejszyć koszty do minimum (na przykład problem żywienia). Zatem ogólny problem programowania liniowego jest problemem, w którym wymagane jest znalezienie maksimum lub minimum (optimum) funkcji, zwanej funkcją celu, z ograniczeniami określonymi przez system nierówności liniowych lub równań.
W tym przypadku zmienne najczęściej zgodnie z warunkami problemu powinny przyjmować wartości nieujemne (czyli dodatnie lub zerowe), ale są też wyjątki, które są nieco niższe.
Funkcja celu w problemie programowania liniowego jest zwykle zapisywana jako:
.
Lub w formie skróconej z sigma:
.
Oznaczenie funkcji celu można znaleźć przez C i F.
System ograniczeń w problemie programowania liniowego w formie kanonicznej jest zapisany jako:
.
Lub w skróconej formie:
Zarówno system ograniczeń, jak i funkcja celu są liniowe , to znaczy zawierają zmienne tylko w pierwszym stopniu.
Problem kanonicznego programowania liniowego jest problemem, w którym, jak pokazano powyżej, wymagane jest znalezienie maksimum funkcji celu w ramach ograniczeń określonych przez układ równań liniowych.
Problem programowania liniowego w standardzie lub, jak mówią inaczej, forma normalna , jest problemem, w którym chcesz znaleźć maksimum funkcji celu z ograniczeniami określonymi przez system nierówności jednego znaczenia, to znaczy z tym samym znakiem, a ten znak jest „mniejszy lub równy” ponadto warunek braku negatywności zmiennych jest również ważny. Jeśli w zadaniu programowania liniowego podanym w standardowej formie wymagane jest znalezienie minimum funkcji celu, to system ograniczeń składa się z systemu nierówności o znaku większym lub równym.
Problem programowania liniowego w formie ogólnej lub, jak mówią inaczej, w postaci mieszanej , jest problemem, w którym wymagana jest maksymalna lub minimalna funkcja celu, a system ograniczeń może obejmować nierówności o różnych znakach, a także równania, to znaczy równość. Jednocześnie w przypadku problemu zdefiniowanego w formie ogólnej warunek braku negatywności zmiennych niekoniecznie musi być spełniony, to znaczy niektóre zmienne mogą być bez ograniczenia znaku, a dla niektórych (a czasami także wszystkich) zmiennych można nadać warunek niepozytywności.
Jeśli wszystkie lub niektóre ograniczenia w systemie są podane przez nierówności, problem można zredukować do kanonicznego sposobu przekształcania nierówności w równania.
Zbiór liczb (zapis sekwencji X) spełniający system ograniczeń nazywany jest rozwiązaniem tego systemu. Rozwiązanie systemu jest często nazywane planem , a nieco rzadziej programem , ale właśnie z tego pochodzi nazwa „programowanie liniowe”.
Optymalnym rozwiązaniem problemu programowania liniowego jest rozwiązanie systemu, w którym funkcja celu zamienia się w maksimum lub minimum, w zależności od stanu problemu lub, w sensie ogólnym, optymalnego .
Rozwiązanie problemu programowania liniowego nazywa się zdegenerowanym, jeśli w nim niektóre zmienne są równe zero. W przeciwnym razie rozwiązanie nie jest generowane .
Jak wspomniano powyżej, zmienne w problemie programowania liniowego najczęściej powinny być nieujemne, ale, jak już się dowiedzieliśmy, ogólna forma zapisu zadania umożliwia również ujemne wartości zmiennych. Jeśli zmienne (X z indeksem) oznaczają przepływy pieniężne firmy, które chcesz skierować na różne potrzeby, ale według niektórych artykułów firma jest winna więcej pieniędzy niż ma, to możemy założyć, że odpowiednie zmienne są ujemne.
Do powyższych definicji należy dodać następującą regułę, która ma wartość praktyczną. Aby rozwiązanie problemu miało sens, ograniczenia problemu programowania liniowego muszą być podane w tych samych jednostkach. Na przykład, jeśli osoby biorące udział w zadaniu programowania liniowego są dniami roboczymi, konieczne jest ustalenie, czy jest to kwestia dni roboczych w tygodniu lub w miesiącu oraz przestrzeganie określonej specyfikacji w całym rozwiązaniu problemu.
Przeanalizujmy kilka rodzajów problemów gospodarczych i napiszmy je w postaci relacji matematycznych. Innymi słowy, skonstruujemy matematyczny model domeny.
Aby to zrobić, jak wynika z poprzedniego akapitu, należy przedstawić obszar tematu w taki sposób, aby uzyskać następujące atrybuty problemu programowania liniowego .
Funkcja celu Musi być zmaksymalizowany lub zminimalizowany. Aby zmaksymalizować funkcję, zmienne będące jej składnikami powinny przyjmować tak duże wartości, jak to możliwe, zgodnie z warunkami problemu. Podczas minimalizowania - wręcz przeciwnie, mniejsze. Zazwyczaj funkcja celu wyraża dochód lub wydatki.
Zmienne . Każda zmienna z reguły oznacza zapasy jednego z czynników produkcji - rodzaj surowców, czas, pracę, możliwości technologiczne lub coś innego.
Ograniczenia . Bardzo proste. Na przykład w każdym równaniu (nierówności) określono ograniczenia powyższego lub innych zapasów wykorzystywanych do produkcji określonego rodzaju produktu.
Przykład 1. Schemat problemu wykorzystania surowców.
Sformułuj następujący problem do rozwiązania jako problem programowania liniowego .
Do produkcji dwóch rodzajów produktów 
i 
wymagane są cztery rodzaje zasobów (surowce): 
, 
, 
, 
. Zapasy surowców - odpowiednio 
, 
, 
, 
jednostki.
Przychody ze sprzedaży jednej jednostki produkcji równa się 
y e. i dochody ze sprzedaży jednej jednostki produkcji równa się 
y e. Wymagane, aby uzyskać największy dochód z produkcji produktów. i to znaczy, dowiedz się ile jednostek i ile jednostek musisz z istniejącego zapasu surowców uzyskać maksymalny dochód.
Decyzja. Dla wygody najpierw zapisujemy wszystkie dane w tabeli:
Następnie, na podstawie tabeli, zapisywane są nierówności (ograniczenia):
W rzeczywistości do produkcji każdej jednostki produkcji jest konieczne 
surowce i do produkcji 
wymagane jednostki 
surowce . Do produkcji 
jednostki produkcji wymagane 
surowce . Jako zapasy surowców uzupełnić , natężenie przepływu nie może przekroczyć . W rezultacie otrzymujemy pierwszą nierówność:
Z pozostałych wierszy tabeli tworzymy kolejne 3 nierówności systemu.
Przychody ze sprzedaży jednostki produkcji przez y e. dla każdej jednostki jest 
y e. Podobnie, przychody ze sprzedaży jednostki produkcji przez y e. dla każdej jednostki będzie 
y e. Następnie całkowity dochód ze sprzedaży dwóch rodzajów produktów i napisane w 
. Zadaniem jest znalezienie maksymalnego dochodu, czyli znalezienie maksymalnej funkcji celu. 
.
Na naszej stronie jest graficznie rozwiązać numeryczny przykład tego problemu .
Strona ma Kalkulator online do rozwiązywania problemów programowania liniowego metodą simpleks .
Przykład 2. Schemat problemu mieszanki.
Sformułuj następujący problem do rozwiązania jako problem programowania liniowego .
Wymagane jest znalezienie najtańszego zestawu dostępnych surowców, które zapewniają mieszankę o pożądanych właściwościach. Powstałe mieszaniny muszą mieć w swoim składzie różne składniki w określonych ilościach, a same składniki są częściami składowymi materiałów wyjściowych. Dla uproszczenia zakładamy, że n = 3 im = 4. Niech koszt jednej jednostki materiału wynosi odpowiednio 
, 
, 
, 
. Z kolei wymagana ilość każdego ze składników w mieszaninie wynosi odpowiednio , , .
Decyzja. Budujemy stół:
Współczynniki pokazują liczbę j- tego składnika w jednostce i- tego materiału. Wymagane jest uzyskanie mieszaniny o pożądanych właściwościach przy najniższych kosztach zakupu materiałów.
Problem piszemy w postaci relacji matematycznych. Oznaczamy przez liczbę materiałów i-tego typu wchodzących do mieszaniny. Następnie zadanie jest ograniczone do znalezienia minimum funkcji.
z ograniczeniami
Jednym szczególnym przypadkiem ogólnego problemu mieszanin jest problem żywienia. Do niej teraz i ruszaj dalej.
Strona ma Kalkulator online do rozwiązywania problemów programowania liniowego metodą simpleks .
Przykład 3. Schemat problemu żywienia.
Sformułuj następujący problem do rozwiązania jako problem programowania liniowego .
Dla normalnego funkcjonowania organizmu konieczne jest codzienne spożywanie określonej ilości składników odżywczych: tłuszcz, białko, węglowodany, witaminy. Są one zawarte w różnych produktach w różnych ilościach. Odpowiednio koszt jednej jednostki produktu , , 
. Konieczne jest zorganizowanie żywności w taki sposób, aby organizm otrzymał wymaganą ilość składników odżywczych, a koszt żywności był najniższy.
Decyzja. Budujemy stół:
W powyższej tabeli, na przykład, numer 
oznacza ilość białka zawartą w jednej jednostce produktu . Liczba - To dzienne spożycie węglowodanów itp.
Problem piszemy w postaci relacji matematycznych. W zadaniu nieznana jest ilość każdego rodzaju produktu. Dlatego oznaczamy ilość produktu list ilość produktu - list ilość produktu 
- list 
.
Uzyskujemy system nierówności (ograniczeń):
Wymagane jest znalezienie nieujemnego rozwiązania systemu ograniczeń, dla którego funkcja celu 
odwoła się do minimum.
Strona ma Kalkulator online do rozwiązywania problemów programowania liniowego metodą simpleks .
Przykład 4. Schemat problemu wykorzystania pojemności sprzętu.
Sformułuj następujący problem do rozwiązania jako problem programowania liniowego .
Firma jest potrzebna na czas, aby uwolnić jednostki produkcji i jednostki produkcji. Każdy z tych dwóch rodzajów produktów może być produkowany przez trzy maszyny. Stwórz optymalny plan działania maszyn, to znaczy znajdź czas na załadowanie maszyn, aby koszty produkcji wszystkich produktów były minimalne.
Moc maszyn podana jest w poniższej tabeli:
W tej tabeli 
- liczba jednostek wyprodukowanych w jednostce czasu.
Cena jednej jednostki czasu pracy na produkcję jednej jednostki produkcji na każdej maszynie jest podana w poniższej tabeli:
W tej tabeli, na przykład, numer 
oznacza cenę jednej jednostki czasu pracy maszyny, przeznaczoną na produkcję jednej jednostki produkcyjnej.
Problem piszemy w postaci relacji matematycznych. Nieznany jest czas ładowania maszyn do produkcji produktów. Oznacz jako 
czas ładowania maszyny do produkcji produktów, poprzez 
- czas ładowania maszyny do wytwarzania produktów. Podobnie 
- czas ładowania maszyny do wytwarzania produktów, 
- czas ładowania maszyny do wytwarzania produktów, 
- czas ładowania maszyny do wytwarzania produktów, 
czas ładowania maszyny do produkcji produktów.
Maszyny pracują w tym samym czasie, więc jeśli oznaczymy literą czas jednoczesnego działania wszystkich trzech maszyn, otrzymamy system nierówności:
Zajęte produkty do produkcji maszyn jednostki czasu włączone 
jednostki produkcji. Maszyna zajęta jednostki czasu według 
jednostki produkcji.
Podobnie maszyna jest zajęta tworzeniem jednostki czasu według 
jednostki produkcji itp. Suma potrzebnych jednostek i jednostek.
Oznacza to, że dostajemy inny system:
Następnie całkowity koszt wszystkich produktów jest zapisany w formie równości:
.
Wreszcie otrzymujemy system ograniczeń składający się ze stosunków:
Zadanie polega na znalezieniu takiego nieorientującego rozwiązania ostatniego z danych systemów, aby funkcja celu C przyjęła wartość minimalną.
Przykład 5. Zadanie transportowe (schemat).
Sformułuj następujący problem do rozwiązania jako problem programowania liniowego .
Na dwóch stacjach odlotowych 
i 
dostępne odpowiednio 
i 
jednostki niektórych ładunków. Ta przesyłka powinna być dostarczona do trzech miejsc docelowych. 
, 
, 
i w każdym z nich muszą być odpowiednio dostarczone , , jednostki tego ładunku. Koszt transportu jednej jednostki ładunku z punktu 
wskazać 
równa się 
.
Utwórz plan transportu, aby całkowity koszt wszystkich przesyłek był minimalny.
Decyzja. Uważamy, że zapasy wszystkich ładunków w obu punktach wyjścia są równe zapotrzebowaniu na ten ładunek we wszystkich trzech miejscach, tj.
Problem piszemy w postaci relacji matematycznych. Liczba jednostek ładunku wysłanych z punktu wskazać , oznaczamy 
i utwórz matrycę transportową (tabelę):
W powyższej tabeli każda komórka miejsca docelowego jest podzielona na dwie części. Na szczycie zarejestrowanego kosztu transportu, a na dole - ilości ładunku. Na przykład w klatce 
(w komórce znajdującej się na przecięciu linii 
z kolumną 
numer 
oznacza koszt transportu z punktu wskazać .
Następnie system ograniczeń jest zapisywany w postaci równań:
Celem problemu jest znalezienie nieujemnego rozwiązania układu równań, dla którego funkcja celu 
był minimalny.
Strona ma artykuł poświęcony rozwiązaniu problemu transportowego metodą dystrybucji .
W większości problemów programowania liniowego ograniczenia nie są definiowane jako układ równań, ale jako system nierówności liniowych i możliwe są różne formy takich systemów: lewa strona jest mniejsza lub równa (mniejsza niż) prawej, lewa strona jest większa lub równa (więcej niż) prawej. Ponadto system ograniczeń może być mieszany: część ograniczeń nierówności pierwszego z powyższych typów, część drugiego typu, a część jest podawana w postaci równań.
Jednak każdy system ograniczeń można zredukować do układu równań. Aby to zrobić, wystarczy dodać do lewej strony każdej nierówności, jeśli system jest pierwszego typu, lub odjąć, jeśli system jest drugiego typu, pewna liczba nieujemna jest dodatkową zmienną, tak że każda nierówność zamienia się w równanie. Działania te nazywane są redukcją problemu programowania liniowego do problemu kanonicznego.
Przykład 6. Napisz system nierówności
w postaci równań w celu zredukowania problemu programowania liniowego do problemu kanonicznego.
Decyzja. Dodając do lewej strony nierówności względem jednej dodatkowej zmiennej, uzyskujemy układ równań:
Zatem bez względu na to, jak pierwotnie podane są ograniczenia problemu programowania liniowego, zawsze można je zredukować do układu równań, wykorzystując do tego dodatkowe zmienne.
Strona ma Kalkulator online do rozwiązywania problemów programowania liniowego metodą simpleks .
Nasza strona zawiera również przykłady rozwiązywania problemów z programowaniem liniowym. metoda graficzna bez zmniejszania zadania do kanonicznego i metoda simplex ze wstępnym zmniejszeniem problemu do kanonicznego .
Aby znaleźć optymalne rozwiązanie spośród nieskończonej liczby dopuszczalnych rozwiązań systemu ograniczeń w jakimkolwiek rodzaju programowania liniowego, potrzebujemy szeregu twierdzeń, o których rozważeniu się zwrócimy.
Twierdzenie 1. Zbiór wszystkich dopuszczalnych rozwiązań systemu ograniczeń problemu programowania liniowego jest wypukły.
Zestaw rozwiązań problemu programowania liniowego jest określony przez zestaw ograniczeń liniowych, dlatego taki zestaw jest geometrycznie wypukłym wielościanem lub nieograniczoną domeną wielościenną, z wyjątkiem sytuacji, gdy system ograniczeń jest niezgodny.
O tym, co jest zestawami wypukłymi - w lekcji Układy nierówności liniowych i zbiorów wypukłych punktów .
Twierdzenie 2. Jeśli istnieje, a ponadto unikalne, optymalne rozwiązanie problemu programowania liniowego, to pokrywa się ono z jednym z punktów narożnych zestawu możliwych rozwiązań.
Twierdzenie to pozwala stwierdzić, że poszukiwanie optymalnego rozwiązania można ograniczyć, wyliczając skończoną liczbę punktów narożnych. Jednak znalezienie punktów narożnych wymaga zbudowania domeny rozwiązań dla systemu ograniczeń. Ta konstrukcja jest możliwa tylko dla przestrzeni dwu- lub trójwymiarowej, aw ogólnym przypadku problem pozostaje nierozwiązywalny. Dlatego musisz mieć pewną metodę analityczną, która pozwala znaleźć współrzędne punktów narożnych. W tym celu potrzebujemy dwóch następujących twierdzeń.
Twierdzenie 3. Każde dopuszczalne podstawowe rozwiązanie problemu programowania liniowego odpowiada punktowi narożnemu regionu dopuszczalnych rozwiązań systemu ograniczeń.
Twierdzenie 4 (odwrotność). Każdy punkt narożny zestawu dopuszczalnych rozwiązań systemu ograniczeń odpowiada dopuszczalnemu rozwiązaniu bazowemu.
Dochodzenie. Jeśli istnieje, a ponadto unikalne, optymalne rozwiązanie problemu programowania liniowego, to pokrywa się ono z jednym z dopuszczalnych podstawowych rozwiązań systemu ograniczeń.
Ważność tego stwierdzenia wynika z twierdzeń 2 i 4.
Optymalne kształty liniowe. Jedk jako Dlatego potrzebujemy pewnego rodzaju schematu obliczeniowego, który pozwala na przejście od jednego akceptowalnego podstawowego rozwiązania do drugiego, w którym forma liniowa jest albo zbliżona do optimum, albo przynajmniej nie zmieniła swojego znaczenia. Taki schemat obliczeniowy to na przykład metoda simplex do rozwiązywania problemów z programowaniem liniowym .
Kontynuacja tematu „Programowanie liniowe”
Udostępnij znajomym
