Programowanie liniowe — optymalizacja celów liniowych przy ograniczeniach liniowych
- Autor metody
- George B. Dantzig
- Rok
- 1947
- Typ
- Mathematical programming / continuous optimization
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Programowanie liniowe (LP), którego pionierem był George B. Dantzig w 1947 roku, to metoda matematyczna służąca do znajdowania optymalnej wartości liniowej funkcji celu — takiej jak minimalny koszt lub maksymalny zysk — podlegającej zestawowi liniowych ograniczeń w postaci nierówności i równości.
Jest to podstawowa technika w badaniach operacyjnych, leżąca u podstaw planowania produkcji, alokacji zasobów, logistyki, problemów dietetycznych i niezliczonych innych scenariuszy decyzyjnych w inżynierii, ekonomii i naukach przyrodniczych.
Intuicja stojąca za metodą
Wyobraź sobie, że prowadzisz małą fabrykę produkującą dwa produkty. Każdy produkt przynosi określony zysk, ale jego wytworzenie zużywa ograniczone surowce i czas pracy maszyn. Programowanie liniowe znajduje dokładną kombinację produktów, która wyciska największy zysk z twoich stałych zasobów — bez naruszania jakichkolwiek fizycznych lub kontraktowych ograniczeń. „Liniowość” oznacza, że zysk i zużycie zasobów skalują się w prostoliniowej zależności z ilościami, które produkujesz. Dopuszczalne wybory tworzą wielokąt (w dwóch wymiarach) lub wielościan (w wyższych wymiarach), a optymalna odpowiedź zawsze znajduje się w jednym z jego wierzchołków.
Historia
Systematyczny rozwój programowania liniowego rozpoczął się w 1947 roku, kiedy George B. Dantzig, pracując dla Sił Powietrznych USA, wynalazł algorytm Simplex do automatyzacji planowania logistyki wojskowej. Dantzig opublikował podstawową teorię w swojej monografii z 1963 roku, która pozostaje kanonicznym odniesieniem. Niezależne i równoległe prace Leonida Kantorowicza w Związku Radzieckim (1939) dotyczyły planowania produkcji przy użyciu podobnych idei matematycznych, a Kantorowicz otrzymał Nagrodę Nobla w dziedzinie ekonomii w 1975 roku częściowo za ten wkład. Teoretyczne pytanie o rozwiązywalność w czasie wielomianowym zostało rozstrzygnięte przez metodę elipsoidalną Chaczijana (1979), a później przez metodę punktów wewnętrznych Karmarkara (1984), która okazała się praktycznie szybka dla problemów na dużą skalę. Dziś komercyjne i otwarte solvery LP są wbudowane w systemy planowania zasobów przedsiębiorstwa, planowania lotów i systemy energetyczne na całym świecie.
Kiedy stosować
Programowanie liniowe jest odpowiednie zawsze, gdy trzeba zoptymalizować wielkość, która liniowo zależy od zestawu zmiennych decyzyjnych, a wszystkie ograniczenia są również liniowe. Nie wymaga żadnych założeń dotyczących rozkładu ani minimalnej wielkości próby — jest to deterministyczny model matematyczny, a nie estymator statystyczny. Metoda ma zastosowanie, gdy zmienne decyzyjne są ciągłe (wartości ułamkowe są sensowne); jeśli zmienne muszą być liczbami całkowitymi lub binarnymi, zamiast tego potrzebne jest programowanie całkowitoliczbowe. LP jest szeroko stosowane w planowaniu produkcji, logistyce łańcucha dostaw, problemach dietetycznych i mieszania, optymalizacji portfela finansowego, problemach transportowych i przydziału oraz dyspozycji energii.
Ograniczenia i uwagi
- Wymóg liniowości: jeśli funkcja celu lub jakiekolwiek ograniczenie jest nieliniowe, model LP jest błędnie specyfikowany, a rozwiązanie może być nieprawidłowe lub niewykonalne.
- Tylko zmienne ciągłe: gdy zmienne decyzyjne muszą przyjmować wartości całkowite lub binarne, relaksacja LP daje dolną granicę, ale nie prawidłowe rozwiązanie; należy użyć programowania całkowitoliczbowego.
- Deterministyczny: LP nie modeluje niepewności w parametrach; programowanie stochastyczne lub optymalizacja odporna są potrzebne, gdy dane są niepewne.
- Degeneracja i cykliczność: w rzadkich przypadkach metoda Simplex może cyklicznie przechodzić między zdegenerowanymi bazami bez zbieżności, chociaż reguły antycykliczne (np. reguła Blanda) rozwiązują ten problem.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Gwarantowane globalne optimum: ponieważ obszar dopuszczalny jest wypukłym wielościanem, każde lokalne optimum jest również optimum globalnym, bez ryzyka utknięcia w rozwiązaniu suboptymalnym.
- Wysoka skalowalność: nowoczesne solvery (HiGHS, Gurobi, CPLEX) obsługują modele z milionami zmiennych i ograniczeń w ciągu sekund.
- Bogate informacje po rozwiązaniu: ceny cieni i zakresy wrażliwości dostarczają użytecznych informacji o wartości zasobów i solidności rozwiązania bez dodatkowych uruchomień.
- Brak założeń dotyczących rozkładu: LP jest modelem czysto algebraicznym, więc nie wymaga normalności ani żadnej statystycznej właściwości danych.
Zastosowania
- Planowanie produkcji: znajdowanie optymalnej kombinacji produktów, która maksymalizuje zysk przy jednoczesnym poszanowaniu zdolności maszyn i limitów surowców.
- Logistyka łańcucha dostaw i transportu: minimalizowanie kosztów wysyłki w sieci magazynów i klientów.
- Problemy dietetyczne i mieszania: wybieranie ilości składników, które spełniają wymagania żywieniowe przy minimalnym koszcie.
- Optymalizacja portfela finansowego: alokacja kapitału między aktywa w celu maksymalizacji oczekiwanego zwrotu z uwzględnieniem ryzyka i ograniczeń regulacyjnych.
- Dyspozycja energii i planowanie sieci energetycznej: minimalizowanie kosztów paliwa przy jednoczesnym zaspokojeniu zapotrzebowania na energię elektryczną i limitów mocy generatorów.
- Planowanie personelu i harmonogramów pracy: przydzielanie zmian pracownikom w celu pokrycia zapotrzebowania przy minimalnych kosztach pracy.
Jak to działa
Jak to działa
Rzeczywisty problem decyzyjny jest tłumaczony na symbole matematyczne. Identyfikujesz zmienne decyzyjne (ilości, które możesz kontrolować), zapisujesz funkcję celu (co chcesz maksymalizować lub minimalizować) jako liniową kombinację tych zmiennych i zapisujesz każde ograniczenie — limity zasobów, limity pojemności, wymagania popytu — jako liniową nierówność lub równość. Dobrze sformułowany model LP ma jasny cel, jawne granice zmiennych i każde ograniczenie strukturalne wyrażone liniowo.
Model jest przekształcany do postaci kanonicznej lub standardowej, którą może przetworzyć solver. Nierówności są zamieniane na równości poprzez wprowadzenie nieujemnych zmiennych luzu (slack) lub nadwyżki (surplus), a każda nieograniczona zmienna jest zastępowana różnicą dwóch zmiennych nieujemnych. Ten mechaniczny krok tworzy tablicę lub reprezentację macierzową, na której działa algorytm, i nie zmienia problemu — jedynie przekształca go do obliczeń.
Solver przeszukuje dopuszczalny wielościan w poszukiwaniu optymalnego wierzchołka. Klasyczna metoda Simplex przesuwa się od wierzchołka do wierzchołka wzdłuż krawędzi wielościanu, zawsze poprawiając (lub utrzymując) funkcję celu, aż nie ma już sąsiada poprawiającego. Metody punktów wewnętrznych (barierowe) natomiast przemieszczają się przez wnętrze obszaru dopuszczalnego wzdłuż centralnej ścieżki, co jest szczególnie efektywne dla bardzo dużych modeli. Obie rodziny gwarantują znalezienie globalnego optimum, jeśli takie istnieje, ponieważ obszar dopuszczalny jest wypukły.
Solver zwraca optymalne wartości zmiennych decyzyjnych i optymalną wartość funkcji celu, wraz ze zmiennymi dualnymi (cenami cieniami) i zakresami wrażliwości. Ceny cieni ilościowo określają, o ile poprawiłaby się funkcja celu, gdyby wiążące ograniczenie zostało rozluźnione o jedną jednostkę — bezpośrednio wskazując decydentowi, gdzie dodatkowe zasoby byłyby najbardziej wartościowe. Analiza wrażliwości identyfikuje, o ile może zmienić się współczynnik kosztu lub wartość prawej strony, zanim bieżąca baza przestanie być optymalna.
Częste pułapki
- Stosowanie LP, gdy ograniczenia lub funkcja celu są nieliniowe — rozwiązanie będzie błędne lub solver odrzuci model.
- Ignorowanie wymagań całkowitoliczbowych: zaokrąglanie ciągłego rozwiązania LP do liczb całkowitych zazwyczaj nie daje wykonalnego ani optymalnego rozwiązania całkowitoliczbowego; zamiast tego należy użyć programowania całkowitoliczbowego.
- Niewykonalne lub nieograniczone modele: jeśli obszar dopuszczalny jest pusty (sprzeczne ograniczenia) lub funkcja celu jest nieograniczona (brak ograniczeń granicznych), solver zgłosi błąd — zawsze sprawdzaj strukturę modelu przed uruchomieniem.
- Traktowanie wyników LP jako rekomendacji bez analizy wrażliwości: rozwiązanie, które jest technicznie optymalne, może znajdować się na bardzo cienkiej granicy, gdzie niewielka zmiana danych zmienia rekomendację — zakresy wrażliwości powinny być zawsze sprawdzane.
Najczęściej zadawane pytania
Co sprawia, że problem jest „liniowy” dla celów LP?
Zarówno funkcja celu, jak i każde ograniczenie muszą być liniowe — co oznacza, że każdy człon jest stałą pomnożoną przez pojedynczą zmienną decyzyjną, bez iloczynów zmiennych, bez wykładników i bez funkcji nieliniowych. Jeśli choć jedno ograniczenie lub funkcja celu zawiera, powiedzmy, x razy y lub x do kwadratu, standardowe LP przestaje mieć zastosowanie i potrzebny jest solver programowania nieliniowego lub kwadratowego.
Dlaczego optymalne rozwiązanie zawsze leży w wierzchołku obszaru dopuszczalnego?
Obszar dopuszczalny zdefiniowany przez ograniczenia liniowe jest wypukłym wielościanem (lub politopem). Liniowa funkcja celu jest sama w sobie liniowa, więc nie może być „ciągnięta” w kierunku wnętrza zbioru wypukłego — zawsze osiąga swoją ekstremalną wartość na granicy, a konkretnie w wierzchołku (punkcie narożnym). Jest to geometryczna podstawa strategii metody Simplex polegającej na przechodzeniu od wierzchołka do wierzchołka.
Kiedy powinienem użyć programowania całkowitoliczbowego zamiast LP?
Zawsze, gdy jedna lub więcej zmiennych decyzyjnych musi przyjmować wartości całkowite lub binarne (0/1) — na przykład, czy otworzyć obiekt (tak/nie), ile ciężarówek wysłać (liczby całkowite) lub które elementy uwzględnić w wyborze. Samo rozwiązanie LP i zaokrąglenie ciągłego rozwiązania nie jest niezawodne: zaokrąglone rozwiązania mogą być niewykonalne lub dalekie od optymalnych. Programowanie całkowitoliczbowe poprawnie obsługuje całkowitość, kosztem większych nakładów obliczeniowych.
Co mówią mi ceny cieni?
Cena cienia (zmienna dualna) dla wiążącego ograniczenia wskazuje, o ile poprawiłaby się optymalna wartość funkcji celu, gdyby prawa strona tego ograniczenia została rozluźniona o jedną jednostkę, przy zachowaniu wszystkich innych czynników stałych. Na przykład, cena cienia wynosząca 3 dla ograniczenia godzin pracy oznacza, że dodanie jednej godziny pracy poprawiłoby funkcję celu o 3 jednostki. Ograniczenia, które nie są wiążące, mają cenę cienia równą zero — nie ograniczają one bieżącego optimum.
Pokrewne metody
Źródła
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ISBN: 9780691059136Skopiowano.Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
Otwórz odnośnik DOISkopiowano.