Przejdź do treści
Wróć do wyników wyszukiwania

Metoda Simplex

Autor metody
George Dantzig
Rok
1947
Typ
algorithm
Rodzina
Optimization

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Metoda Simplex, opracowana przez George'a Dantzinga w 1947 roku, jest fundamentalnym algorytmem do rozwiązywania problemów programowania liniowego.

Systematycznie bada wierzchołki obszaru dopuszczalnego, aby znaleźć optymalne rozwiązanie, gdzie funkcja celu jest maksymalizowana lub minimalizowana przy zachowaniu liniowych ograniczeń.

Intuicja stojąca za metodą

Metoda działa poprzez rozpoczęcie od punktu narożnego (wierzchołka) obszaru dopuszczalnego zdefiniowanego przez liniowe ograniczenia, a następnie przemieszczanie się do sąsiednich wierzchołków, które poprawiają wartość funkcji celu. Kontynuuje się do momentu osiągnięcia wierzchołka, gdzie żaden sąsiedni wierzchołek nie oferuje dalszej poprawy, co gwarantuje optymalność. Algorytm wykorzystuje geometryczną właściwość, że programy liniowe mają swoje optymalne rozwiązania w wierzchołkach wielościanu ograniczeń.

Historia

George Dantzig wprowadził metodę Simplex w 1947 roku, rewolucjonizując badania operacyjne i stając się standardowym algorytmem programowania liniowego na dziesięciolecia. Klee i Minty (1972) wykazali wykładniczą złożoność w najgorszym przypadku, jednak empirycznie metoda pozostawała szybka. Lata 80. przyniosły rozwój metod punktów wewnętrznych jako alternatyw, ale metoda Simplex pozostała dominująca dla wielu praktycznych zastosowań ze względu na jej solidność i zaawansowanie nowoczesnych implementacji.

Kiedy stosować

Zastosuj metodę Simplex przy rozwiązywaniu problemów programowania liniowego z ograniczonymi obszarami dopuszczalnymi i liniową funkcją celu. Jest szczególnie skuteczna w problemach z setkami lub tysiącami zmiennych i ograniczeń. Unikaj jej stosowania, jeśli problem jest nieliniowy lub nieograniczony. Metody punktów wewnętrznych mogą być preferowane dla problemów o bardzo dużej skali.

Ograniczenia i uwagi

  • Wykładnicza złożoność czasowa w najgorszym przypadku (choć rzadka w praktyce)
  • Może działać słabo na problemach silnie zdegenerowanych
  • Mniej konkurencyjna niż metody punktów wewnętrznych dla problemów o bardzo dużej skali
  • Wymaga, aby problemy były w postaci standardowej z jawną obsługą ograniczeń

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Gwarantuje znalezienie optymalnego rozwiązania w skończonym czasie dla programów liniowych
  • Wydajna w praktyce przy starannej implementacji i obsłudze degeneracji
  • Szeroko zaimplementowana i wspierana przez dojrzałe biblioteki optymalizacyjne
  • Podstawa do zrozumienia bardziej zaawansowanych algorytmów optymalizacyjnych

Zastosowania

  • Planowanie produkcji: optymalizacja ilości produkcji w celu minimalizacji kosztów przy jednoczesnym spełnieniu ograniczeń popytu
  • Transport i logistyka: określanie optymalnych tras i ilości wysyłek między magazynami a centrami dystrybucji
  • Optymalizacja portfela: alokacja kapitału między aktywa w celu maksymalizacji zwrotów przy zachowaniu ograniczeń ryzyka i budżetu
  • Alokacja zasobów: dystrybucja ograniczonych zasobów, takich jak praca i materiały, w celu maksymalizacji wyników organizacji
  • Problemy mieszania: mieszanie surowców w optymalnych proporcjach w celu spełnienia specyfikacji jakościowych i minimalizacji kosztów
  • Harmonogramowanie pracy: przydzielanie pracowników do zmian w celu minimalizacji kosztów pracy przy jednoczesnym spełnieniu popytu

Jak to działa

Jak to działa

1

Przekształć program liniowy do postaci standardowej ze zmiennymi uzupełniającymi i zidentyfikuj początkowe bazowe rozwiązanie dopuszczalne (zazwyczaj początek układu współrzędnych, jeśli jest dopuszczalny).

2

Wykonaj operacje obrotu na tablicy simpleks: wybierz zmienną wchodzącą o ujemnym koszcie zredukowanym, zidentyfikuj zmienną wychodzącą za pomocą testu minimalnego stosunku i zaktualizuj bazę.

3

Sprawdź warunki optymalności za pomocą kosztów zredukowanych; jeśli wszystkie koszty zredukowane są nieujemne dla maksymalizacji, bieżące rozwiązanie jest optymalne; w przeciwnym razie wróć do kroku obrotu.

Częste pułapki

  • Niewłaściwa obsługa cykliczności przy napotkaniu zdegenerowanych baz (użyj reguły Blanda lub metod perturbacji)
  • Nieprawidłowy wybór obrotu lub błędy arytmetyczne w aktualizacjach tablicy prowadzące do niestabilności numerycznej
  • Nie sprawdzanie nieograniczoności lub niedopuszczalności przed rozpoczęciem algorytmu

Najczęściej zadawane pytania

Dlaczego metoda Simplex nazywa się 'Simplex'?

Termin 'simplex' odnosi się do najprostszej formy wielościanu w dowolnym danym wymiarze. Algorytm działa poprzez przemieszczanie się wzdłuż krawędzi i wierzchołków wielościanu zdefiniowanego przez ograniczenia.

Jaka jest różnica między metodą Simplex a metodą punktów wewnętrznych?

Metoda Simplex pozostaje na granicy obszaru dopuszczalnego w wierzchołkach, podczas gdy metody punktów wewnętrznych przechodzą przez jego wnętrze. Metody punktów wewnętrznych mają lepszą złożoność w najgorszym przypadku, ale Simplex jest często szybszy w praktyce dla problemów średniej wielkości.

Jak radzić sobie z niedopuszczalnością lub nieograniczonością?

Użyj dwuetapowej metody Simplex: etap pierwszy rozwiązuje problem pomocniczy w celu znalezienia bazowego rozwiązania dopuszczalnego lub określenia niedopuszczalności; etap drugi stosuje standardową metodę Simplex do oryginalnego problemu.

Czym jest degeneracja i dlaczego ma znaczenie?

Degeneracja występuje, gdy bazowe rozwiązanie dopuszczalne ma więcej niż jedną reprezentację bazową, co może powodować cykliczność. Radzi sobie z nią za pomocą reguły Blanda (wybieraj zmienne według kolejności indeksów) lub metod perturbacji.

Pokrewne metody

Źródła

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.

    Otwórz odnośnik DOI
    Skopiowano.