Optymalizacja pomaga znaleźć najlepszy wynik, który przyniesie zysk, obniży koszty lub ustawi parametr powodujący awarie procesów biznesowych.
Ten proces jest również nazywany programowaniem matematycznym. Rozwiązuje problem określenia rozkładu ograniczonych zasobów niezbędnych do osiągnięcia celu wyznaczonego przez kierownika zadania optymalizacyjnego. Spośród wszystkich możliwych opcji pożądane jest znalezienie takiej, która maksymalizuje (lub zmniejsza) parametr kontrolny, na przykład zysk lub koszt. Modele optymalizacji są również nazywane nakazowymi lub normatywnymi, ponieważ mają na celu znalezienie realnej strategii dla firmy.
Historia rozwoju
Programowanie liniowe (LP) działa z klasą problemów optymalizacji, w których wszystkie ograniczenia są liniowe.
Przedstawienie krótkiej historii rozwoju LP:
- W 1762 roku Lagrange rozwiązał proste problemy optymalizacyjne z ograniczeniami równości.
- W 1820 r. Gauss zdecydowałliniowy układ równań z wykorzystaniem eliminacji.
- W 1866 roku Wilhelm Jordan udoskonalił metodę znajdowania błędów najmniejszych kwadratów jako kryterium dopasowania. Nazywa się to teraz metodą Gaussa-Jordana.
- Komputer cyfrowy pojawił się w 1945 roku.
- Danzig wynalazł metody simpleks w 1947 roku.
- W 1968 roku Fiacco i McCormick wprowadzili metodę Inside Point.
- W 1984 roku Karmarkar zastosował metodę wnętrza do rozwiązywania programów liniowych, dodając swoją innowacyjną analizę.
LP okazał się niezwykle potężnym narzędziem zarówno do modelowania rzeczywistych problemów, jak i jako szeroko stosowana teoria matematyczna. Jednak wiele interesujących problemów optymalizacyjnych ma charakter nieliniowy.
Co zrobić w takim przypadku? Badanie takich problemów obejmuje zróżnicowaną mieszankę algebry liniowej, rachunku różniczkowego wielu zmiennych, analizy numerycznej i metod obliczeniowych. Naukowcy opracowują algorytmy obliczeniowe, w tym metody punktów wewnętrznych do programowania liniowego, geometrii, analizy zbiorów i funkcji wypukłych oraz badania problemów o specjalnej strukturze, takich jak programowanie kwadratowe.
Optymalizacja nieliniowa zapewnia podstawowe zrozumienie analizy matematycznej i jest szeroko stosowana w różnych dziedzinach, takich jak inżynieria, analiza regresji, zarządzanie zasobami, eksploracja geofizyczna i ekonomia.
Klasyfikacja problemów optymalizacji
Ważny krok wProces optymalizacji polega na klasyfikacji modeli, ponieważ algorytmy ich rozwiązania są dostosowane do konkretnego typu.
1. Problemy z optymalizacją dyskretną i ciągłą. Niektóre modele mają sens tylko wtedy, gdy zmienne przyjmują wartości z dyskretnego podzbioru liczb całkowitych. Inne zawierają dane, które mogą mieć jakąkolwiek rzeczywistą wartość. Zwykle są łatwiejsze do rozwiązania. Udoskonalenia algorytmów w połączeniu z postępami w technologii komputerowej radykalnie zwiększyły rozmiar i złożoność problemu optymalizacji programowania liniowego.
2. Nieograniczona i ograniczona optymalizacja. Kolejną ważną różnicą są zadania, w których nie ma ograniczeń na zmienne. Może mieć szeroki zakres, od prostych estymatorów po systemy równości i nierówności, które modelują złożone relacje między danymi. Takie problemy optymalizacyjne można dalej klasyfikować zgodnie z naturą funkcji (liniowe i nieliniowe, wypukłe i gładkie, różniczkowalne i nieróżnicowalne).
3. Zadania wykonalności. Ich celem jest znalezienie wartości zmiennych, które spełniają ograniczenia modelu bez określonego celu optymalizacji.
4. Zadania komplementarne. Są szeroko stosowane w technologii i ekonomii. Celem jest znalezienie rozwiązania spełniającego warunki komplementarności. W praktyce zadania mające kilka celów są często przeformułowane na zadania jednocelowe.
5. Optymalizacja deterministyczna a stochastyczna. Optymalizacja deterministyczna zakłada, że dane dlazadania są całkowicie dokładne. Jednak w wielu aktualnych kwestiach nie można ich poznać z wielu powodów.
Pierwszy ma związek z prostym błędem pomiaru. Drugi powód jest bardziej fundamentalny. Polega na tym, że niektóre dane reprezentują informacje o przyszłości, na przykład popyt na produkt lub cenę na przyszły okres. Podczas optymalizacji w warunkach optymalizacji stochastycznej niepewność jest zawarta w modelu.
Główne komponenty
Funkcją celu jest ta, która ma zostać zminimalizowana lub zmaksymalizowana. Większość typów problemów optymalizacyjnych ma jedną funkcję celu. Jeśli nie, często można je przeformułować, aby działały.
Dwa wyjątki od tej reguły:
1. Docelowe zadanie wyszukiwania. W większości aplikacji biznesowych menedżer chce osiągnąć określony cel przy jednoczesnym spełnieniu ograniczeń modelu. Użytkownik nie chce specjalnie czegoś optymalizować, więc nie ma sensu definiować funkcji celu. Ten typ jest powszechnie określany jako problem spełnialności.
2. Wiele obiektywnych funkcji. Często użytkownik chciałby zoptymalizować kilka różnych celów jednocześnie. Zwykle są niezgodne. Zmienne optymalizujące jeden cel mogą nie być najlepsze dla innych.
Typy komponentów:
- Kontrolowane wejście to zestaw zmiennych decyzyjnych, które wpływają na wartość funkcji celu. W zadaniu produkcyjnym zmienne mogą obejmować rozkład różnych dostępnych zasobów lub pracy wymaganej do:każde działanie.
- Ograniczenia to relacje między zmiennymi decyzyjnymi a parametrami. W przypadku problemu produkcyjnego nie ma sensu spędzać dużej ilości czasu na jakiejkolwiek czynności, więc ogranicz wszystkie „tymczasowe” zmienne.
- Możliwe i optymalne rozwiązania. Wartość decyzji dla zmiennych, przy której spełnione są wszystkie ograniczenia, nazywamy spełnialną. Większość algorytmów najpierw go znajduje, a następnie próbuje go ulepszyć. Na koniec zmieniają zmienne, aby przejść od jednego wykonalnego rozwiązania do drugiego. Proces ten powtarza się, aż funkcja celu osiągnie maksimum lub minimum. Ten wynik nazywa się rozwiązaniem optymalnym.
Szeroko stosowane są algorytmy problemów optymalizacyjnych opracowane dla następujących programów matematycznych:
- Wypukły.
- Możliwość rozdzielenia.
- Kwadratowy.
- Geometryczne.
Liniowe rozwiązywanie Google
Optymalizacja liniowa lub programowanie to nazwa nadana procesowi obliczeniowemu optymalnego rozwiązania problemu. Jest modelowany jako zbiór zależności liniowych, które powstają w wielu dyscyplinach naukowych i inżynierskich.
Google oferuje trzy sposoby rozwiązywania problemów optymalizacji liniowej:
- Biblioteka open source Glop.
- Dodatek optymalizacji liniowej do Arkuszy Google.
- Usługa optymalizacji liniowej w Google Apps Script.
Glop jest wbudowany w Googlesolwer liniowy. Jest dostępny w otwartym kodzie źródłowym. Dostęp do Glop można uzyskać poprzez opakowanie solwera liniowego OR-Tools, które jest opakowaniem dla Glop.
Moduł optymalizacji liniowej dla Arkuszy Google umożliwia wykonanie liniowego stwierdzenia problemu optymalizacji poprzez wprowadzenie danych do arkusza kalkulacyjnego.
Programowanie kwadratowe
Platforma Premium Solver wykorzystuje rozszerzoną wersję LP/kwadratową metody Simplex z limitami przetwarzania problemów LP i QP wynoszącymi do 2000 zmiennych decyzyjnych.
SQP Solver dla problemów o dużej skali wykorzystuje nowoczesną implementację metody aktywnych zbiorów z rzadkimi rozwiązaniami problemów programowania kwadratowego (QP). Silnik XPRESS Solver wykorzystuje naturalne rozszerzenie metody „Interior Point” lub Newton Barrier do rozwiązywania problemów QP.
MOSEK Solver stosuje osadzone metody „Inside Point” i metody auto-dual. Jest to szczególnie skuteczne w przypadku luźno powiązanych problemów QP. Może również rozwiązywać problemy z ograniczeniami kwadratowymi skali (QCP) i programowaniem stożka drugiego rzędu (SOCP).
Obliczenia wielu operacji
Są one z powodzeniem wykorzystywane przy wykorzystaniu funkcji pakietu Microsoft Office, na przykład przy rozwiązywaniu problemów z optymalizacją w programie Excel.
W powyższej tabeli symbole to:
- K1 - K6 - klienci, którzy muszą dostarczyć towary.
- S1 - S6 to potencjalne zakłady produkcyjne, które można w tym celu zbudować. Można stworzyć1, 2, 3, 4, 5 lub wszystkie 6 lokalizacji.
Istnieją koszty stałe dla każdego obiektu wymienionego w kolumnie I (Poprawka).
Jeśli lokalizacja niczego nie zmieni, nie będzie się liczyła. Wtedy nie będzie stałych kosztów.
Zidentyfikuj potencjalne lokalizacje, aby uzyskać najniższy koszt.
W tych warunkach lokalizacja jest ustalona lub nie. Te dwa stany to: „PRAWDA – FAŁSZ” lub „1 – 0”. Istnieje sześć stanów dla sześciu lokalizacji, na przykład 000001 jest ustawione tylko na szóstą, 111111 jest ustawione na wszystkie.
W systemie liczb binarnych są dokładnie 63 różne opcje od 000001 (1) do 111111 (63).
L2-L64 powinien teraz brzmieć {=WIELE OPERACJI (K1)}, to są wyniki wszystkich alternatywnych rozwiązań. Wtedy minimalna wartość to=Min (L), a odpowiednia alternatywa to INDEKS (K).
Programowanie liczb całkowitych CPLEX
Czasami liniowy związek nie wystarcza, aby dotrzeć do sedna problemu biznesowego. Jest to szczególnie ważne, gdy decyzje dotyczą dyskretnych wyborów, takich jak otwarcie magazynu w określonej lokalizacji. W takich sytuacjach należy użyć programowania całkowitoliczbowego.
Jeśli problem dotyczy zarówno dyskretnych, jak i ciągłych wyborów, jest to program mieszanych liczb całkowitych. Może mieć liniowe, wypukłe problemy kwadratowe i te same ograniczenia drugiego rzędu.
Programy liczb całkowitych są znacznie bardziej złożone niż programy liniowe, ale mają ważne zastosowania biznesowe. OprogramowanieOprogramowanie CPLEX wykorzystuje złożone metody matematyczne do rozwiązywania problemów z liczbami całkowitymi. Jego metody polegają na systematycznym wyszukiwaniu możliwych kombinacji zmiennych dyskretnych przy użyciu liniowych lub kwadratowych relaksacji oprogramowania w celu obliczenia granic wartości optymalnego rozwiązania.
Do obliczania ograniczeń używają również LP i innych metod rozwiązywania problemów optymalizacyjnych.
Standardowy Solver Microsoft Excel
Ta technologia wykorzystuje podstawową implementację głównej metody Simplex do rozwiązywania problemów LP. Jest ograniczona do 200 zmiennych. „Premium Solver” wykorzystuje ulepszoną podstawową metodę simpleks z dwustronnymi ograniczeniami dla zmiennych. Platforma Premium Solver wykorzystuje rozszerzoną wersję LP/Quadratic Simplex Solver do rozwiązania problemu optymalizacji z maksymalnie 2000 zmiennymi decyzyjnymi.
Wielkoskalowy LP dla platformy Premium Solver wykorzystuje najnowocześniejszą implementację prostej i podwójnej metody simplex, która wykorzystuje rzadkość w modelu LP w celu zaoszczędzenia czasu i pamięci, zaawansowane strategie aktualizacji i refaktoryzacja macierzy, wielokrotna i częściowa wycena i rotacje oraz przezwyciężenie degeneracji. Ten silnik jest dostępny w trzech wersjach (zdolnych do obsługi do 8000, 32 000 lub nieograniczonej liczby zmiennych i limitów).
MOSEK Solver zawiera podstawowy i podwójny simpleks, metodę, która również wykorzystuje rzadkość i wykorzystuje zaawansowane strategie aktualizacji macierzy i „refaktoryzacji”. Rozwiązuje problemy o nieograniczonych rozmiarach, byłoprzetestowane na problemach programowania liniowego z milionami zmiennych decyzyjnych.
Przykład krok po kroku w programie EXCEL
Aby zdefiniować model problemu optymalizacji w programie Excel, wykonaj następujące czynności:
- Uporządkuj dane dotyczące problemu w arkuszu kalkulacyjnym w formie logicznej.
- Wybierz komórkę do przechowywania każdej zmiennej.
- Utwórz w komórce wzór do obliczenia docelowego modelu matematycznego problemu optymalizacji.
- Twórz formuły, aby obliczyć lewą stronę każdego ograniczenia.
- Użyj okien dialogowych w programie Excel, aby poinformować Solvera o zmiennych decyzyjnych, celach, ograniczeniach i pożądanych granicach tych parametrów.
- Uruchom „Solver”, aby znaleźć optymalne rozwiązanie.
- Utwórz arkusz Excela.
- Uporządkuj dane dotyczące problemu w programie Excel, gdzie obliczana jest formuła funkcji celu i ograniczenia.
W powyższej tabeli komórki B4, C4, D4 i E4 zostały zarezerwowane do reprezentowania zmiennych decyzyjnych X 1, X 2, X 3 i X 4. Przykłady decyzji:
- Model asortymentu produktów (450 USD, 1150 USD, 800 USD i 400 USD zysku na produkt) został wprowadzony odpowiednio w komórkach B5, C5, D5 i E5. Pozwala to na obliczenie celu w F5=B5B4 + C5C4 + D5D4 + E5E4 lub F5:=SUMPRODUCT (B5: E5, B4: E4).
- W B8 wprowadź ilość zasobów wymaganych do wytworzenia każdego typu produktu.
- Formuła dla F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Skopiuj toformuła w F9. Znaki dolara w $B$4:$E$4 wskazują, że ten zakres komórek pozostaje stały.
- W G8 wprowadź dostępną ilość zasobów każdego typu, odpowiadającą wartościom ograniczeń po prawej stronie. Pozwala to wyrazić je w następujący sposób: F11<=G8: G11.
- Odpowiada to czterem limitom F8<=G8, F9 <=G9, F10 <=G10 i F11=0
Obszary praktycznego zastosowania metody
Optymalizacja liniowa ma wiele praktycznych zastosowań jako przykład problemu optymalizacyjnego:
Firma może wytwarzać kilka produktów ze znaną marżą wkładu. Wyprodukowanie jednostki każdego przedmiotu wymaga znanej ilości ograniczonych zasobów. Zadaniem jest stworzenie programu produkcyjnego, który określi, ile każdego produktu należy wyprodukować, aby zysk firmy był maksymalizowany bez naruszania ograniczeń zasobów.
Problemy z mieszaniem to rozwiązanie problemów optymalizacji związanych z łączeniem składników w produkt końcowy. Przykładem tego jest problem diety badany przez George'a Danziga w 1947 roku. Podano szereg surowców, takich jak owies, wieprzowina i olej słonecznikowy, wraz z ich wartościami odżywczymi, takimi jak białko, tłuszcz, witamina A oraz ich cena za kilogram. Wyzwaniem jest zmieszanie jednego lub więcej produktów końcowych z surowców przy możliwie najniższych kosztach, przy jednoczesnym przestrzeganiu minimalnych i maksymalnych limitów ich wartości odżywczej.
Klasycznym zastosowaniem problemu optymalizacji liniowej jest określenie trasowania dla potrzebruch w sieciach telekomunikacyjnych lub transportowych. Jednocześnie przepływy muszą być kierowane przez sieć w taki sposób, aby wszystkie wymagania dotyczące ruchu były spełnione bez naruszania warunków przepustowości.
W teorii matematycznej optymalizacja liniowa może być używana do obliczania optymalnych strategii w grach o sumie zerowej dla dwóch osób. W tym przypadku obliczany jest rozkład prawdopodobieństwa dla każdego uczestnika, który jest współczynnikiem losowego mieszania jego strategii.
Żaden pomyślny proces biznesowy na świecie nie jest możliwy bez optymalizacji. Dostępnych jest wiele algorytmów optymalizacji. Niektóre metody są odpowiednie tylko dla niektórych rodzajów problemów. Ważne jest, aby móc rozpoznać ich cechy i wybrać odpowiednią metodę rozwiązania.
