Przykład zastosowania programowania liniowego do wyznaczenia optymalnej struktury asortymentu w piekarni

PROWADZIMY FIRMĘ

Każdy, kto rozumie matematykę na poziomie szkoły podstawowej, może przeprowadzić w swojej piekarni proces optymalizacji. Jego wynikiem będzie wyraźnie zauważalny wzrost zysków lub zmniejszenie ryzyka. Każdy właściciel piekarni ma kilka obszarów, gdzie widzi możliwość optymalizacji, oszczędności lub wzrostu zysków.

Osobiście nie znam nikogo, kto lubiłby matematykę. Nie znam też nikogo, kto by nie wykorzystywał kalkulacji do zarabiania albo chociaż ułatwiania sobie życia. Z matematyką wiążą się więc skrajne emocje, z jednej strony unikamy jej, a z drugiej nie potrafimy bez niej żyć.

Instynktownie czujemy, że umiejętnie kalkulując możemy podnieść nasze zarobki, skrócić czas dojazdu albo zminimalizować ryzyko. Widzimy, jak wiele chleba idzie do utylizacji, jak niedostatecznie zaprojektowaliśmy strukturę asortymentu. Czujemy się bezradni, bo nie wiemy, jak zabrać się do optymalizacji.

Czujemy, że aby tego dokonać musimy wejść głęboko w analizę matematyczną, działania różniczkowe, jakieś wzoryiwykresy. Kto ma dzisiaj na to czas. Często nie mamy czasu zrobić podstawowych podsumowań. Mamy kłopoty z podstawowymi kalkulacjami. Wewnętrznie czujemy, że zaproponowany przez księgową podział kosztów na stałe i zmienne jest niewłaściwy. Niechętnie wchodzimy na nieznany grunt, zwłaszcza grunt przepojony zasadami i równaniami, grunt spowity mgłą abstrakcyjnych wyrażeń matematycznych.

Prawda jest jednak inna. Dzięki takim publikacjom jak ta oraz nowym kalkulatorom działającym w sieci online możemy stosunkowo łatwo i bezboleśnie przeprowadzić pewne ważne usprawnienia.

Jest to pierwszy artykuł z cyklu publikacji promujących zastosowanie prostej matematyki do poprawy jakości naszego biznesu, wzrostu rentowności, spadku ryzyka i ogólnie poprawy własności naszych procesów. Dzisiaj dowiemy się, w jaki sposób zoptymalizować asortyment sprzedawanych produktów. Użyjemy algorytmów tzn. programowania liniowego. Na tyle prostych, że każdy kto miał minimalny kontakt z matematyką je zrozumie.

Czym jest i kiedy powstało programowanie liniowe?

Programowanie liniowe, w najprostszej formie, składa się z równania celu oraz kilku nierówności przedstawiających ograniczenia.

Programowanie liniowe było bardzo szeroko wykorzystywane podczas II wojny światowej. Alianci zdawali sobie sprawę z tego, że mogą nie wygrać z III Rzeszą i cesarstwem Japonii stosując tradycyjne metody zarządzania logistyką i zaopatrzeniem. Mając ograniczone zasoby środków do prowadzenia wojny musieli wiedzieć, jak nimi dysponować, aby ich wykorzystanie było jak najlepsze. Na pomoc przyszli matematycy. Dzięki nim procesy logistyczne w armii amerykańskiej znacznie się poprawiły. Równania zmniejszyły ryzyko utraty ładunku, maksymalizowano dostępność środków opatrunkowych i straty w szeregach wroga. Co ciekawe, programowanie liniowe wynalazł w 1939 roku radziecki ekonomista Leonid Kantorowicz.

Przykiad programowania liniowego

Załóżmy, że w naszej piekarni produkujemy trzy rodzaje chleba. W tabeli pokazany jest zysk netto ze sprzedaży każdego rodzaju chleba.

SG He 0 0 + | Chleb | Zysk netto na bochenku | Hmm Hm ne + | Chleb Baltonowski | 1.0 zł i +--mrao nen c 00 42000000 mom 0000 + | chleb Staropolski | 2.4 zł l paw wwa mamma ra am EEEE koka + | Chleb Sierpecki | 1.2 zł ] pom nna pam mn inw mmc nm +

Chleby te różnią się nieznacznie składnikami, różny jest też ich zysk jednostkowy. Mieszkańcy miasteczka, w którym sprzedajemy nasze produkty, wydają się nie mieć szczególnych preferencji i kupią od nas każdy rodzaj chleba. W tym zadaniu, jako właściciele piekarni, chcemy maksymalizować zysk ze sprzedaży chleba poprzez zmianę struktury sprzedaży.

Formułowanie funkcji celu

Zapiszmy więc naszą funkcję celu:

| F(x, X,, x.) = 1.0x, + 2.4x, + 1.2x, > max |

Powyższe wyrażenie przedstawia sumę zysków ze sprzedaży poszczególnych chlebów. Chodzi nam o to, aby ta suma była jak największa. Mówimy wtedy o maksymalizacji funkcji celu.

W naszym równaniu x, oznacza liczbę bochenków sprzedanego chleba baltonowskiego, x, - staropolskiego, x, — sierpeckiego.

Załóżmy, że sprzedaliśmy 80 sztuk chleba sierpeckiego, wtedy zysk jednostkowy z bochenka 1,2 zł mnożymy przez 80 sztuk, co daje nam 96 zł zysku ze sprzedaży.

Ponieważ naszym celem jest maksymalizacja zysku, więc intuicyjne rozumiemy, że powinniśmy sprzedać maksymalną liczbę tego chleba, który ma najwyższą marżę.

Niestety, zarówno w życiu, jak iw piekarni, nie ma nic za darmo.

Mamy ograniczone zasoby produkcyjne i musimy wziąć je pod uwagę w maksymalizacji naszego zysku.

rzy 'ze

- | - | - | - | -

Dw am

m V

Formułowanie ograniczeń

Poniższa tabela przedstawia zużycie dwóch składników, które muszą być obecne przy produkcji chleba.

x,, x, musi być większa lub równa zero. Gdybyśmy o tym zapomnieli, algorytm maksymalizujący zysk ze sprzedaży mógłby pokazać nam wartości ujemne. Matematyka jest nauką wymagającą precyzji. Algorytm nie wie, że nie istnieje ujemna sprzedaż.

Właśnie utworzyliśmy

EEEE EEEE Hoen onana nn pore manonnnawa EEEE + . ramowania | Surowce | Baltonowski xi | Staropolski x2 | Sierpecki x3 | Limit surowców | algorytm Prog , FIDE PONOWNE do acaretw wrót weta wrze Żarowie wawa KORENINNNANN 4+ liniowego. Formułowanie | Składnik 1 ! 0.65 I 0.03 I 0.8 I 266 | algorytmu jest najtrudniej- RON EEEEE | +00 0000 eee nanownam + | Składnik 2 i 0.61 | 0.06 I 0.04 | 318 | Szym etapem pracy. Czyn- ZE ZE EEEE EE EE +

Teraz musimy zapisać powyższe ograniczenia jako nierówności matematyczne.

Ograniczenie związane z użyciem składnika 1 można zapisać w następujący sposób:

0.05, + 0.03,, < 260

Jak pamiętamy x, to liczba wyprodukowanego chleba baltonowskiego. Przy produkcji każdego bochenka tego chleba zużywa się 0,05 g składnika 1. Produkcję można kontynuować aż do wyczerpania składnia 1, czyli do wyczerpania 260 kg zapasu. Wszystkie warunki ograniczające w tym zadaniu można zapisać w następujący sposób.

0.05:x, + 0.03x> < 260

0.012, + 0.0622 + 0.04x3 < 310 Xi Z ż0 Xx20 xż0

Na uwagę zasługują trzy ostatnie nierówności mówiące, że liczba poszczególnych chlebów: x,,

ność ta wymaga pewnej wprawy i abstrakcyjnego myślenia. Wystarczy tutaj podstawowa znajomość zasad matematyki.

Rozwiązanie algorytmu

Do niedawna rozwiązanie podobnych algorytmów stanowiło nie lada wyczyn. Konieczna była znajomość operacji na macierzach oraz dokładne poznanie żmudnych procedur obliczeniowych. Na szczęście żyjemy w czasach, w których większość problemów możemy rozwiązać przez internet. Podobnie jest i tutaj. Wystarczy wpisać do przeglądarki hasło: „Simplex calculator”, aby znaleźć wiele dostępnych online formularzy do wpisania i obliczenia naszego algorytmu. Ja skorzystałem z kalkulatora ze strony maslowski.pl

Rozwiązanie algorytmu

za pomocą biblioteki PuL.P

Profesjonalni analitycy nie korzystają z kalkulatorów internetowych. Aby obliczyć nasz algorytm skorzystam z bezpłatnej biblioteki Pulp języka Python.

dsęawócyii znakiem dziesiętnym jest . (kropka). a nie , (przecinek) |

—— z Govgie | [ema] slowski.pl „awe masłowski.pl > bada ka = sniplex pn.line SIMPLEX omrline - wprowadzanie tanych kJ BADANIA FA OPERACYJNE Podana iczba zmiermych go: 3 = zadania Podana liczba ograniczeń ta: 5 * BALKA - konkurs Funkcja celu z: z * fiteratura z=[i 4 Ę [za ja + [2] kę - [max H - Giro 2004 « Giro 2605 Ograniczenia: ; wą tn |005 lą + [003 ka+[0_ k;(soj[2% | -TaF 2 te) [0.01 h +[008 Ją * [o0s k;(sw][310 | - TAF 2006 + TdE 2007 mj k+jo k+p_ kwEo_ POCZTA NA 15 [0 6 je + [O w e |] mastowski. pi (5) [o _Je* m sEH | —*

PROWADZIMY FIRMĘ

In [4]: from putp import * $ Anitialize Class model = LpProblem( "Zadanie 16_STR._30”, LpMaximize) In [5]: Qut[5]: Max _zysku produkcji In [6]: śż* Definiowanie zmiennych decyzyjnych xl = Lpvarieblef 'x1', lowBound=o, cat='Integar') xX2 = LpVariable|('x2', lowBound=©, cat='Integer") x3 = LpVariable( x3', lowBaund=2, cat='Integer')

LpVariable(name="Max zysku produkcji”, lowBound=©, upBoundzNone, cat='Internal', e=None)

Po zdefiniowaniu celu i zmiennych x1, x2, x3 wprowadzam zdefiniowany przez nas algorytm.

Należałoby wtedy w naszym algorytmie zmienić

warunek z x, >= 0 na x, >= 2500. Po przeliczeniu

okazuje się, że całkowity zysk ze sprzedaży

Definiowanie funkcji celu

model .solvef]

P 3 /prir

Należy produkować 2332.68 xl Należy produkować 4778.8 x2 Należy produkować 8.8 x3 print(*Maksymalny zysk ze sprzedaży:", z)

Maksymalny zysk ze sprzedaży: 13799. 199999999999

In [7]: model += 1.0%x1 + 2.4%x2 + 1.2%x3 Definiowanie ograniczeń In [8]: model += 09.85*x1 + 6.03*x2 <= 266 model += 9.61*x1 + 0.06*x2 + 0.04*%x3 <= 310 In [9]: £ Solve sodel print("Należy produkować (> x1'.format(x1.varValue) | nt("Należy produkować t) x2" format (x2.varyalue) | ("Należy produkować f) x3" .format(x3.varvalue) |

In [10]: z = XL.varVaLue*1.0 + x2.varValue*2.4 + x3.varValue*l.2

zmniejszył się do 13 466 zł.

Oznacza to, że do sprzedaży każdego chleba sierpeckiego dopłacamy 333 zł/2500 = 0,13 zł. Powinniśmy więc podnieść cenę tego chleba tak, aby zysk jednostkowy zbliżył się do poziomu 1,33 zł.

Z algorytmu optymalizacji wynika, że możemy wyprodukować 2500 bochenków chleba sierpeckiego pod warunkiem podniesienia zysku jednostkowego z tego chleba do poziomu 1,33 zł. Taka cena chleba daje możliwość uzyskania zysku w wysokości 13 792 zł.

Podsumowanie Zastosowanie programowania liniowego w celu optymalizacji procesów produk- | cyjnych może przynieść duże korzyści. Jak

Zdefiniowany przez nas algorytm wskazał, że z posiadanych zapasów składnika 1 i składnika 2 należy wyprodukować 2332 chleby baltonowskie oraz 4778 chlebów staropolskich. Taka struktura sprzedaży spowoduje maksymalizację zysku ze sprzedaży do wysokości 13 799 zł. Algorytm wskazał, że nie należy produkować chleba sierpeckiego.

Co by się stało, gdyby jednak mieszkańcy miasteczka lubili i chcieli kupować chleb sierpecki?

Według naszych szacunków, chleb ten sprzedałby się na poziomie 2500 bochenków.

pokazałem, najtrudniejszym elementem jest sformułowanie równań i nierówności matematycznych. Nie jest tu potrzebna wiedza z zakresu matematyki, lecz zdrowy rozsądek i odrobina abstrakcyjnego myślenia.

Kiedyś prawdziwym problemem było obliczenie algorytmów optymalizacyjnych. Dzisiaj możemy posłużyć się kalkulatorami simplex, które w zupełności wystarczą, aby uzyskać prawidłowe wyniki.

Wojciech Moszczyński