Liniowe programowanie Excel

Modele optymalizacji służą do znajdowania odpowiedzi na pytania takie jak:

• Jak zaplanować pracownikom call center, aby spełniali swoje prośby urlopowe, przetwarzali saldo i eliminowali całodobowy zegarek?
• Jakie możliwości wydobycia ropy naftowej należy wykorzystać, aby zmaksymalizować przychody przy zachowaniu kontroli nad wszystkimi zagrożeniami?
• kiedy należy składać nowe zamówienia w Chinach i jak powinny być dostarczane, aby zminimalizować koszty i zaspokoić oczekiwany popyt?

Rys. 1. Ograniczenie budżetowe sprawia, że ​​zakres dopuszczalnych wartości jest trójkątny

Pobierz notatkę w formacie Słowo lub pdf przykłady w formacie Excel

Celem optymalizacji jest zawsze „maksymalizacja” lub „minimalizacja”. Najbardziej powszechną i zrozumiałą formą optymalizacji matematycznej jest programowanie liniowe, tajny rozwój radzieckich inżynierów z końca lat 30. XX wieku, który stał się popularny w czasie II wojny światowej. Przy okazji, słowo „programowanie” w tym wyrażeniu jest reliktem ówczesnej terminologii wojskowej i nie ma nic wspólnego z programowaniem komputerowym. [1]

Zacznijmy od ulubionego przykładu ekonomistów - broni i olejów. Nadchodzi rok 1941, jesteś właścicielem francuskiego gospodarstwa mlecznego. W ciągu dnia mleczysz krowy i produkujesz masło, w nocy zbierasz automaty. Twoim celem jest maksymalny zysk, aby produkować automaty tak długo, jak to możliwe. Od pośrednika z Ruchu Oporu otrzymujesz 195 jednostek monetarnych dla każdego automatu (aby nie obciążać Excela nieistniejącymi frankami, załóżmy, że są to dolary). Za każdą baryłkę ropy na rynku płacisz 150 USD.

Warunki Koszt jednej baryłki ropy wynosi 100 USD, a jednego karabinu maszynowego 150 USD. Miesięczny budżet produkcji wynosi 1800 USD. Przechowujesz produkty w piwnicy o powierzchni 21 metrów sześciennych. Maszyna zajmuje ½ m3, baryłkę oleju 1½ m3. Ile automatów i baryłek ropy musisz sprzedać miesięcznie, aby uzyskać maksymalny zysk?

Program liniowy definiowany jest jako zestaw rozwiązań niezbędnych do optymalizacji obiektu w świetle pewnych warunków, w których zarówno obiekt, jak i warunki są liniowe. Możesz dodać, odjąć, pomnożyć przez stałe, ale nie możesz użyć funkcji nieliniowych do rozwiązania, na przykład, mnożenia zmiennych (automatów nie można pomnożyć przez olej), kwadratów lub cykli logicznych, takich jak IF.

Wyobraź sobie graficznie poprawne pole. Po pierwsze, liczba dział i baryłek ropy musi być nieujemna. Po drugie, możliwe jest wyprodukowanie aż 1800 USD / 150 USD = 12 maszyn lub 1 800 USD / 100 USD = 18 baryłek ropy (rys. 1). Wspólna nazwa tego trójkąta jest politopowa - postać z płaskimi bokami (na przykład diament). Po trzecie, piwnica może pomieścić nie więcej niż 21 / (½) = 42 automatów lub 21 / (1½) = 14 baryłek ropy (rys. 2).

Rys. 2. Ograniczona ilość piwnicy odcina część zakresu dopuszczalnych wartości.

Aby znaleźć idealny stosunek automatów i beczek, wprowadzamy do problemu koncepcję linii poziomu funkcji . Ta linia w modelu optymalizacji zawiera wartości, które przynoszą taki sam zysk. Linię poziomu można ustawić równaniem:

(195 - 150) * N automatyczny + (150 - 100) * N butelek olejowych = C,

gdzie C jest stałą.

Na przykład, gdy C = 450, linia przejdzie przez współrzędne (0; 10) i (9; 0). Graficznie idea maksymalizacji zysków realizowana jest poprzez przesunięcie linii poziomej równolegle do siebie w kierunku rosnących wartości wzdłuż osi X i Y (rys. 3). Ciekawe, że dla politopy optymalny zawsze leży na jednym z wierzchołków (lub w ogóle nie ma unikalnego rozwiązania). Algorytm metody simpleks opiera się na tej właściwości. Rozwiązanie problemu w programie Excel rozpoczyna się od utworzenia obszaru modelu (rys. 4). Wzór na funkcję celu w komórce B1 = PRODUKCJA (C4: D4; C10: D10).

Rys. 3. Poziom linii i funkcja optymalizacji zysków: a) dowolna pozycja początkowa; b) linia pozioma w optymalnej pozycji

Rys. 4. Dane dotyczące maszyn i oleju umieszczone w Excelu

Masz wszystko gotowe do kliknięcia DANE -> Wyszukaj rozwiązanie . (Jeśli nie widzisz tego przycisku, zainstaluj dodatek Find Solution; zobacz John Foreman. Wiele liczb: analiza dużych zbiorów danych w programie Excel Rozdział 1). W oknie Ustawienia wyszukiwania rozwiązania, które zostanie otwarte, ustaw podświetlone opcje i kliknij Znajdź rozwiązanie .

Rys. 5. Okno wyszukiwania rozwiązań

Excel zaktualizuje arkusz i doda do niego wyniki obliczeń (rys. 6).

Rys. 6. Zoptymalizowana tabela maszyn i baryłek ropy

Co się stanie, jeśli dodasz nieliniowość? Załóżmy, że twój pośrednik oferuje 500 USD, jeśli liczba maszyn na miesiąc jest większa niż 5. Wystarczy dodać funkcję JEŻELI do pola zysku (B1). Teraz funkcja celu wygląda następująco: = SUMPRODUCT (C4: D4; C10: D10) + IF (C4> 5; 500; 0). Kliknij Wyszukaj rozwiązanie . Awaria, Excel zgłasza błąd - warunki liniowości nie są spełnione (Rysunek 7).

Rys. 7. Excel nie pozwala na użycie operatorów logicznych w algorytmie liniowym.

Możesz wypróbować algorytm ewolucyjny, który najlepiej działa z modelami nieliniowymi i praktycznie nie ogranicza twojego wyboru funkcji. Praca algorytmu ewolucyjnego w jakiś sposób powtarza zasady pracy ewolucji biologicznej:

• generuje pulę początkowych decyzji (coś w rodzaju puli genetycznej) o różnych stopniach prawdopodobieństwa;
• każde rozwiązanie ma pewien poziom przydatności do przeżycia;
• rozwiązania są mnożone przez przeniesienie krzyżowe, to znaczy, że ich komponenty są wybierane z dwóch lub trzech istniejących rozwiązań, a następnie łączone;
• istniejące rozwiązania zmieniają się w nowe;
• istnieje lokalne wyszukiwanie, w trakcie którego generowane są nowe rozwiązania w pobliżu najlepszego rozwiązania w danej chwili w populacji;
• selekcja ma miejsce: losowo wybrani, nieudani kandydaci na decyzje są wyrzucani z puli genetycznej.

Niestety nadal istnieją problemy z algorytmem ewolucyjnym:

• Czas pracy jest znacznie dłuższy niż w przypadku metody simpleks
• Nie ma gwarancji, że znajdzie optymalne rozwiązanie. Jedyne, co jest w jego mocy, to kontrolować najlepsze rozwiązanie w populacji, aż skończy się czas, lub populacja nie zmieni się wystarczająco, by kontynuować, albo przymusowo nie przestaniesz Znajdować rozwiązania, naciskając przycisk ESC.
• Ewolucyjne poszukiwanie rozwiązania jest raczej powolne. A jeśli regiony o dopuszczalnych wartościach są złożone, często przysięga, nawet nie znajdując miejsca, z którego mógłby zacząć.
• Jeśli chcesz, aby algorytm ewolucyjny działał dobrze w Excelu, musisz zdefiniować twarde granice dla każdej zmiennej decyzyjnej. Nawet jeśli Twoje rozwiązanie jest mniej lub bardziej nieograniczone, nadal potrzebujesz ograniczeń.

Biorąc pod uwagę ostatni punkt, aby rozwiązać problem z automatami i olejem, należy dodać ograniczenie, zgodnie z którym oba rozwiązania nie powinny być większe niż 25 (rys. 8). Po ustawieniu podstawowych parametrów modelu kliknij przycisk Parametry . Po około minucie pracy algorytm ewolucyjny wytworzył oczekiwane rozwiązanie - 6 automatów i 9 baryłek ropy. Ponieważ optymalne jest wykonanie tylko trzech maszyn bez premii, a premia jest wypłacana przy produkcji więcej niż 5 maszyn, oczywiste jest, że wybór 6 maszyn będzie optymalny.

Rys. 8. Tworzenie ewolucyjnego „Poszukiwanie rozwiązania”

Rozważmy teraz bardziej złożony przykład. Pracujesz w firmie, która produkuje sok pomarańczowy, mieszając naturalne soki różnych odmian (rys. 9). Aby Twój sok spełniał najbardziej wyszukane wymagania:

• stosunek na skali Brixa / kwasowości powinien pozostać w zakresie 11,5–12,5;
• poziom kwasowości powinien pozostać między 0,75–1%;
• poziom ściągania musi wynosić 4 lub mniej;
• kolor powinien mieścić się w zakresie 4,5–5,5.

Szef powiedział ci, że w styczniu i lutym oczekuje popytu na poziomie 600 000 galonów soku miesięcznie, aw marcu - 700 000 galonów. A jednak istnieje umowa ze stanem Floryda, która przewiduje ulgi podatkowe, pod warunkiem, że firma kupuje co najmniej 40% soku miesięcznie od rolników uprawiających odmianę Valencia . Umowa powinna być przestrzegana.

Rys. 9. Lista cech do produkcji świeżo wyciśniętego soku pomarańczowego (aby powiększyć obraz, kliknij go prawym przyciskiem myszy i wybierz Otwórz obraz w nowej karcie )

Utwórz model optymalizacji (rys. 10). Formuły można badać na odpowiednim arkuszu załączonego pliku Excel. Kliknij Wyszukaj rozwiązanie i wprowadź parametry (rys. 11). Kliknij Znajdź rozwiązanie .

Rys. 10. Dostosuj tabelę miksów

Rys. 11. Wypełnione okno decyzji wyszukiwania zadania mieszania.

Rozpoczynając wyszukiwanie rozwiązania , znajdziesz optymalny koszt zakupów - 1,23 mln USD (rys. 12). Należy pamiętać, że zamówienie na Florida Valencia przechodzi przez dolną granicę warunku. Oczywiście ta transakcja nie jest najlepszą opcją, ale musisz ją zaakceptować. Drugą najpopularniejszą odmianą jest Verna z Meksyku, która jest dość cholernie tania, ale równie okropna.

Rys. 12. Rozwiązanie problemu optymalizacji mieszania soku pomarańczowego

Przedstawiasz szefowi wyniki obliczeń, ale nie jest on zadowolony i mówi, że nie chce przekroczyć budżetu 1,17 miliona dolarów, wracasz do komputera i zaczynasz rozumieć, że koszt przestał być funkcją docelową. Teraz ten warunek! Jaki jest cel Możesz obniżyć koszty zamówień tylko poprzez złagodzenie wymagań jakościowych. Postanawiasz je sformułować w kategoriach procentowej redukcji i stworzyć nowy model (rys. 13).

Rys. 13. Model o obniżonej jakości

Zauważ, że komórki B26: 29 i F26: F29 nie są już stałymi, ale formułami. Twoim nowym celem jest zminimalizowanie procentowej redukcji jakości w komórkach G26: G29. Dokładniej, chciałbyś zminimalizować maksymalną wartość w komórkach G26: G29. Jeśli jednak formuła = MAX (G26: G29) zostanie umieszczona w komórce D2, model nie będzie działać. Przypominam, że funkcja MAX nie jest liniowa. Mała sztuczka jest dostępna tutaj - możesz dodać dodatkowy warunek do modelu: $ G $ 26: $ G $ 29 <= $ D $ 2 (rys. 14) i pozostawić komórkę D2 pustą. Oznacza to, że komórka D2 zostanie zoptymalizowana nie ze względu na obecność w niej formuły, ale przez kolejne cykle wyzwalane przez ten dodatkowy warunek.

Rys. 14. Parametry poszukiwania rozwiązania w modelu o obniżonej jakości

Kliknij Znajdź rozwiązanie . Algorytm simpleks będzie próbował doprowadzić D2 do 0 jako funkcję obiektywną modelu, podczas gdy ograniczenia dotyczące smaku i koloru będą próbowały zwiększyć go tak bardzo, jak to możliwe, w celu uzyskania funkcjonalnej mieszaniny. Gdzie zatrzymuje się wartość D2? Najmniejszą możliwą wartością jest maksymalny procent czterech zredukowanych w zakresie G26: G29. Widzimy (rys. 15, komórki C26: E29), że redukcja kosztów o 5% wymaga przekroczenia ograniczeń jakości we wszystkich czterech parametrach.

Rys. 15. Rozwiązanie problemu optymalizacji z redukcją kosztów o 5%

Przesłałeś dane szefowi, który zauważył, że obniżenie kosztów o 5% nie jest warte obniżenia jakości soku, więc zgodził się na pierwszą opcję. Ale kiedy przynieśliście go do działu zaopatrzenia, pracownicy zbuntowali się. Jak można było zmiażdżyć dostawę? Dostawcy nalegają na konsolidację partii: nie więcej niż 4 dostawców miesięcznie! I siadasz do nowego modelu. Niestety nie możesz użyć funkcji IF lub KONTO, ponieważ chcesz pozostać w modelu liniowym. Dlatego znowu musisz uciekać się do sztuczek (rys. 16). Do modelu dodajesz obszar C33: E43, który definiujesz jako binarny (wartości w nim mogą być tylko 0 lub 1) i pozostaw to pole puste. Jak również obszar F33: H43, gdzie każda komórka jest równa iloczynowi wartości z obszarów C33: E43 według G5: G15. Dodajesz jeszcze jeden warunek $ C $ 15: $ E $ 15 <= $ F $ 33: $ H $ 43 i jeszcze jedną domenę zmienną - $ C $ 33: $ E $ 43 do parametrów wyszukiwania (rys. 17).

Jak będzie działał algorytm optymalizacji w tym przypadku? Po uruchomieniu wszystkie wartości w regionach C5: E15, C33: E43 i F33: H43 wynoszą zero. Załóżmy, że algorytm próbuje umieścić wartość 240 w komórce C7. Warunek C7 <= F35 będzie działał, co zwiększy wartość w F35, która z kolei jest określona przez wzór F35 = C35 * $ G7. Ponieważ G7 jest stałą, a C35 jest zmienną binarną, ta ostatnia ma wartość 1. Warunek C7 <= F35 jest spełniony, ponieważ 240 <= 1200. W ten sposób symulujesz niewygodny warunek „jeśli ... wtedy”: „jeśli zamówienie zostało wykonane, wtedy zmienna binarna jest włączona. ”

Rys. 16. Dodawanie wskaźników do modelu

Rys. 17. Wartości ustawień dla warunku „nie więcej niż 4 dostawców”

Kliknij Znajdź rozwiązanie . Zauważysz, że rozwiązanie problemu zajmuje więcej czasu ze względu na dodanie zmiennych binarnych. Jeśli z jakiegoś powodu poszukiwanie rozwiązania jest zbyt opóźnione w wyszukiwaniu, zawsze możesz nacisnąć ESC i zobaczyć najlepsze znalezione rozwiązanie.

W zasadzie jesteś już dość zaawansowanym specjalistą w dziedzinie programowania liniowego. Ale jeśli jesteś w dobrym guście i lubisz zajmować się modelami o coraz większej złożoności, oto dwa bardziej wściekłe przykłady.

Inżynierowie poinformowali, że w produkcji pojawiły się nowe „środki zmniejszające kwasowość”. Technologia ta jest w stanie zneutralizować 20% kwasu w soku przepływającym przez urządzenie. To nie tylko zmniejsza procent kwasu, ale także zwiększa wskaźnik Brixa / kwasowość o 25%. Ale dla „downer” potrzebujesz energii i materiałów eksploatacyjnych o wartości 20 $ za 1000 galonów soku. Nie cały sok pochodzący od dostawców musi być poddawany temu procesowi, jednak jeśli dostawa dla jakiegoś zamówienia jest prowadzona przez wymieniacz jonowy, to cała jego objętość musi zostać przetworzona. Zbuduj model z wymieniaczem jonowym, aby zmniejszyć koszty.

Problem z nową regułą polega na tym, że naturalny sposób modelowania jest nieliniowy, co doprowadzi do zastosowania powolnego algorytmu optymalizacji. Ale, jak w poprzednim przykładzie, możesz wprowadzić zmienną binarną w regionie C25: E35, który „włączy się”, jeśli to konieczne, zmniejszy kwasowość partii (rys. 18). Ponieważ nie można użyć „wskaźnika malejącej kwasowości (binarnej) * objętości partii”, należy utworzyć obszar C37: E47, który będzie przydatny do wyrównania objętości podlegających obniżeniu kwasowości bez bezpośredniego udziału w formułach samych objętości. Zatem obszary C25: E35 i C37: E47 nie zawierają formuł. W obszarze G25: I35 stosuje się wzory = С25: Е35 * G5: G15 (jest to ograniczenie partii o całkowitą dostępną objętość soku) oraz w obszarze K25: M35 = E5: E15-GG5: 15 * (1-Е25: E35). Ten warunek będzie działał tylko wtedy, gdy strona ulegnie zmniejszeniu kwasowości.

Rys. 18. Obszar wskaźników w modelu z „czynnikiem zmniejszającym kwasowość”

Również w modelu z „czynnikiem zmniejszającym kwasowość” formuły zostały zmienione w komórkach C16: E16 (teraz biorą pod uwagę koszt zmniejszenia kwasowości zgodnie ze wzorem „wskaźnik (binarny) * objętość partii * 20 USD) oraz w komórkach C50: E51 (teraz biorą pod uwagę wzrost współczynnika Brixa (25% kwasowość i 20% zmniejszenie kwasowości dla partii poddanych działaniu). Nowe parametry i dodatkowe warunki pojawiły się w parametrach wyszukiwania rozwiązania (rys. 19). Niestety, klikając przycisk Znajdź rozwiązanie , dowiesz się, że dodatek do rozwiązania wyszukiwania nie radzi sobie z zadaniem (rys. 20). Model stał się zbyt złożony.

Rys. 19. Parametry wyszukiwania rozwiązania w modelu z „czynnikiem zmniejszającym kwasowość”

Rys. 20. Poszukiwanie rozwiązania nie radzi sobie z zadaniem.

Musisz pobrać i zainstalować OpenSolver (zobacz, jak to zrobić). John Foreman. Wiele liczb: analiza dużych zbiorów danych w programie Excel Rozdział 1). OpenSolver „odbierze” instalacje właśnie wprowadzone w oknie Wyszukaj rozwiązanie . Po prostu kliknij przycisk Solver . Powstałe rozwiązanie - 1.235.927 $ więcej niż 100.000 $ więcej niż poprzednie minimum - 1.338,913 $.

Do tej pory uważaliśmy, że dostarczone produkty mają dokładnie określone parametry. Rozsądnie jest założyć, że parametry te podlegają zmianom, charakteryzującym się odchyleniem standardowym (rys. 21; szczegóły - patrz Określenie średniej, zmienności i kształtu rozkładu. Statystyki opisowe ). Najbardziej znaną i szeroko stosowaną dystrybucją zmiennej losowej jest rozkład normalny, zwany inaczej „krzywą w kształcie dzwonu”. Na przykład, w przypadku soku z Egiptu, średni stosunek Brix / kwasowość wyniesie 13, a odchylenie standardowe (nazywane również odchyleniem standardowym) będzie wynosić 0,9 (Rys. 21). W tym przykładzie 13 jest centrum rozkładu prawdopodobieństwa, 68% zamówień będzie zawierać się w granicach ± ​​0,9 od 13, a 95% będzie zawierać się w przedziale ± 1,8 od 13.

Rys. 21. Dodano odchylenie standardowe do parametrów soku

Twoim celem jest zaoferowanie planu mieszanego o wartości poniżej 1,25 miliona USD, który najlepiej spełnia oczekiwania jakościowe w świetle zmienności dostaw.

Używamy średniej i standardowego odchylenia charakterystyk do zastosowania symulacji Monte-Carlo (jeśli jest to pierwszy raz, gdy słyszysz tę nazwę, polecam Wykorzystanie metody Monte Carlo do obliczenia ryzyka ). W tej metodzie zamiast bezpośredniego uwzględniania parametrów rozkładu (średniej i odchylenia standardowego) w modelu tworzona jest duża liczba scenariuszy w oparciu o te same parametry dystrybucji.

Scenariusz jest jedną z możliwych odpowiedzi na pytanie: „Jeśli są to dystrybucje oparte na statystykach, jak będzie wyglądać konkretne zamówienie?” Każdy scenariusz zawiera czterdzieści parametrów dziesięciu rodzajów soku (rys. 22). Aby uzyskać jeden taki parametr, użyj funkcji NOR.OBR (więcej szczegółów na temat funkcji, patrz Normalny rozkład ). Na przykład, w komórce B33, stosunek Brix / kwasowość dla odmiany Hamlin jest określony wzorem = NORMAL OBR (RISCH (); H5; N5). Wpisz podobne formuły w obszarze B33: CW76, generując 100 skryptów. Poszukiwanie rozwiązania nie może działać z tymi formułami, ponieważ są one nieliniowe, więc skopiuj je do bufora i wklej je, ale już jako wartości.

Rys. 22. Fragment wygenerowanych scenariuszy cech soku

Ponadto dla każdego scenariusza definiujemy 4 parametry dla każdego miesiąca (Rys. 23).

Rys. 23. Obliczanie cech dla każdego scenariusza

Celem jest zminimalizowanie wartości w komórce D2. Oznacza to znalezienie rozwiązania, które najmniej obniża limity jakości dla 100 scenariuszy. Jak w przykładach na rys. 13–15, w komórce D2 nie ma formuły. Optymalizacja odbywa się poprzez ustawienie parametrów w oknie Wyszukaj rozwiązanie. Potrzebne jest jedynie umieszczenie we wszystkich scenariuszach granic jakości, a nie tylko oczekiwanych wartości cech. Zatem w stosunku Brix / kwasowość dodaje się warunki B78: CW80> = B26 i = <F26, a następnie robią to samo z kwasowością, składnikiem wiążącym smaku i koloru (rys. 24). Kliknij Znajdź rozwiązanie . Rozwiązanie jest dość szybkie. Jeśli wygenerowałeś losowe wartości samodzielnie i nie korzystałeś z tych w pliku do pobrania, twoje rozwiązanie może być inne. Dla moich stu scenariuszy najlepszym wskaźnikiem, jaki udało mi się uzyskać, jest 133% zmiana jakości.

Rys. 24. Dostosuj rozwiązania wyszukiwania dla modelu ze zmiennością cech

Jeśli chcesz poszerzyć swoją wiedzę na temat programowania liniowego, polecam książkę Książka modelowania optymalizacji AIMMS . Nie przegap dwóch rozdziałów na temat sztuczek i wskazówek - są naprawdę genialne.

[1] Napisane na podstawie książki Johna Foremana Wiele liczb: analiza dużych zbiorów danych w programie Excel . - M.: Alpina Publisher, 2016. - P. 129–186. Co do tajemnicy rozwoju i II wojny światowej, wydaje się, że jest to osobista opinia autora książki. Zobacz Wikipedia . - Ok. Baguzina .