Plik Programowanie liniowe jest metodą matematyczną używaną do optymalizacji (maksymalizacji lub minimalizacji zgodnie z wymaganiami) funkcji, której zmienne podlegają ograniczeniom, o ile funkcja i ograniczenia są liniowo zależne od zmiennych.
Zasadniczo funkcja, która ma zostać zoptymalizowana, modeluje sytuację praktyczną, taką jak zysk producenta, którego nakłady, siła robocza lub maszyny są ograniczone.
Jednym z najprostszych przypadków jest maksymalizacja funkcji liniowej, która zależy tylko od dwóch zmiennych, tzw zmienne decyzje. Może mieć postać:
Z = k1x + kdwaY
Dzięki k1 i kdwa stały. Ta funkcja jest znana jako Funkcja celu. Oczywiście istnieją sytuacje, które wymagają więcej niż dwóch zmiennych do badania, są bardziej złożone:
Z = k1x1 + kdwaxdwa + k3x3 +... .
Ograniczenia są również modelowane matematycznie przez system równań lub nierówności, równie liniowych x i Y.
Zbiór rozwiązań tego systemu nosi nazwę wykonalne rozwiązania lub wykonalne punkty. A wśród możliwych do zrealizowania punktów jest przynajmniej jeden, który optymalizuje funkcję celu.
Programowanie liniowe zostało niezależnie opracowane przez amerykańskiego fizyka i matematyka George'a Dantziga (1914-2005) oraz rosyjskiego matematyka i ekonomistę Leonida Kantorowicza (1912-1986) krótko po drugiej wojnie światowej..
Metoda rozwiązywania problemów znana jako metoda simplex Jest pomysłem Dantziga, który pracował dla Sił Powietrznych Stanów Zjednoczonych, Uniwersytetu w Berkeley i Uniwersytetu Stanforda.
Indeks artykułów
Elementami niezbędnymi do ustalenia liniowego modelu programowania, odpowiedniego do sytuacji praktycznej, są:
-Funkcja celu
-Zmienne decyzje
-Ograniczenia
W funkcji celu określasz, co chcesz osiągnąć. Załóżmy na przykład, że chcesz zmaksymalizować zyski z produkcji określonych produktów. Następnie ustala się funkcję „zysku”, zgodnie z ceną, po której sprzedawane są produkty.
W kategoriach matematycznych funkcję tę można wyrazić w skrócie za pomocą notacji sumowania:
Z = ∑kja xja
W tym równaniu kja są współczynnikami i xja są zmiennymi decyzyjnymi.
Zmienne decyzyjne to elementy systemu, nad którymi sprawowano kontrolę, a ich wartościami są dodatnie liczby rzeczywiste. W proponowanym przykładzie zmiennymi decyzyjnymi są ilość każdego produktu, który należy wyprodukować, aby uzyskać maksymalny zysk.
Wreszcie mamy ograniczenia, które są równaniami liniowymi lub nierównościami pod względem zmiennych decyzyjnych. Opisują ograniczenia problemu, które są znane i mogą to być na przykład ilości surowca dostępnego do produkcji..
Możesz mieć M ograniczeń, zaczynając od j = 1 aż do j = M. Matematycznie ograniczenia są trzech typów:
Pierwsze ograniczenie jest typu równania liniowego i oznacza, że wartość Ajot, co jest znane, musi być szanowane.
Pozostałe dwa ograniczenia to nierówności liniowe i oznacza to, że wartości B.jot i Cjot, wiadomo, można je uszanować lub przekroczyć, gdy wyświetlany symbol jest ≥ (większy lub równy) lub respektowany lub nieprzekraczany, jeśli symbol jest ≤ (mniejszy lub równy).
Obszary zastosowań są bardzo zróżnicowane, od administracji biznesowej po odżywianie, ale aby zrozumieć metodę, poniżej zaproponowano prosty model praktycznej sytuacji z dwiema zmiennymi..
Lokalna cukiernia znana jest z dwóch specjalności: ciasta z czarnego lasu i ciasta Sacripantina..
Do jej przygotowania wymagają jaj i cukru. Do czarnego lasu potrzeba 9 jajek i 500 g cukru, a do sacypantyny potrzeba 8 jajek i 800 g cukru. Odpowiednie ceny sprzedaży to 8 i 10 USD.
Problem polega na tym, że ile ciast każdego rodzaju musi upiec ciasto, aby zmaksymalizować swój zysk, wiedząc, że ma 10 kilogramów cukru i 144 jajka?
Zmienne decyzyjne to „x” i „y”, które przyjmują wartości rzeczywiste:
-x: liczba ciastek z czarnego lasu
-oraz: ciastka typu Sacripantina.
Ograniczenia wynikają z faktu, że liczba ciastek jest ilością dodatnią i ilość surowca do ich przygotowania jest ograniczona..
Dlatego w formie matematycznej ograniczenia te przyjmują postać:
Ograniczenia 1 i 2 stanowią warunek nieujemności ujawnione wcześniej, a wszystkie podniesione nierówności są liniowe. W ograniczeniach 3 i 4 podano wartości, których nie wolno przekraczać: 144 jaj i 10 kg cukru.
Wreszcie, funkcją celu jest zysk uzyskany przy produkcji „x” ciastek z czarnego lasu plus „y” ilość saciantyn. Buduje się go mnożąc cenę przez ilość wykonanych ciast i dodając do każdego rodzaju. Jest to funkcja liniowa, którą nazwiemy G (x, y):
G = 8x + 10 lat
Różne metodologie rozwiązań obejmują między innymi metody graficzne, algorytm simplex i metodę punktów wewnętrznych..
Kiedy masz problem z dwiema zmiennymi, taki jak ten w poprzedniej sekcji, wiązania określają region wielokąta na płaszczyźnie xy, połączenie region wykonalny lub region żywotności.
Region ten jest budowany za pomocą linie ograniczające, które są liniami uzyskanymi z nierówności ograniczeń, działającymi tylko ze znakiem równości.
W przypadku piekarni, która chce zoptymalizować zyski, linie ograniczenia są następujące:
Wszystkie punkty w regionie otoczonym tymi liniami są możliwymi rozwiązaniami, więc jest ich nieskończenie wiele. Z wyjątkiem przypadku, w którym obszar wykonalny okazuje się pusty, w którym to przypadku postawiony problem nie ma rozwiązania.
Na szczęście w przypadku problemu z ciastami możliwy region nie jest pusty, mamy go poniżej.
Optymalne rozwiązanie, jeśli istnieje, znajduje się za pomocą funkcji celu. Na przykład, próbując znaleźć maksymalne wzmocnienie G, mamy następujący wiersz, który jest nazywany linia iso-profit:
G = k1x + kdway → y = -k1x / kdwa + G / kdwa
Z tej prostej otrzymujemy wszystkie pary (x, y), które zapewniają dane wzmocnienie G, więc istnieje rodzina linii według wartości G, ale wszystkie o tym samym nachyleniu -k1 / kdwa, więc są to równoległe linie.
Teraz można wykazać, że optymalnym rozwiązaniem problemu liniowego jest zawsze skrajny punkt lub wierzchołek wykonalnego obszaru. Następnie:
Linia rozwiązania jest najbardziej oddalona od początku i ma co najmniej jeden punkt wspólny z możliwym regionem.
Jeśli linia najbliższa początku ma cały odcinek wspólny z możliwym do zrealizowania regionem, mówi się, że istnieją nieskończone rozwiązania. Ten przypadek występuje, gdy nachylenie linii izo-zysku jest równe nachyleniu którejkolwiek z innych linii, które ograniczają region.
W przypadku naszego ciasta kandydującymi wierzchołkami są A, B i C..
Metoda graficzna lub geometryczna ma zastosowanie do dwóch zmiennych. Jednak jest to bardziej skomplikowane, gdy istnieją trzy zmienne i niemożliwe do wykorzystania w przypadku większej liczby zmiennych..
W przypadku problemów z więcej niż dwiema zmiennymi, rozszerzenie metoda simplex, który składa się z szeregu algorytmów do optymalizacji funkcji celu. Do wykonywania obliczeń często używa się macierzy i prostych działań arytmetycznych.
Metodę simplex rozpoczynamy od wybrania możliwego do zrealizowania rozwiązania i sprawdzenia, czy jest ono optymalne. Jeśli tak, to już rozwiązaliśmy problem, ale jeśli tak nie jest, kontynuujemy poszukiwanie rozwiązania bliższego optymalizacji. Jeśli rozwiązanie istnieje, algorytm znajduje je w kilku próbach.
Programowanie liniowe i nieliniowe jest stosowane w wielu dziedzinach, aby podejmować najlepsze decyzje w zakresie redukcji kosztów i zwiększania zysków, które nie zawsze mają charakter pieniężny, ponieważ można je mierzyć w czasie, na przykład, jeśli chcesz zminimalizować niezbędny czas do wykonania szeregu operacji.
Oto kilka pól:
-W marketingu służy do znalezienia najlepszej kombinacji mediów (sieci społecznościowe, telewizja, prasa i inne) w celu zareklamowania określonego produktu.
-Do przydzielania odpowiednich zadań personelowi firmy lub fabryki lub do przydzielania im harmonogramów.
-W doborze najbardziej pożywnej żywności i najniższych kosztach w przemyśle hodowlanym i drobiarskim.
Rozwiąż graficznie model programowania liniowego przedstawiony w poprzednich sekcjach.
Konieczne jest wykreślenie zbioru wartości wyznaczonych przez system więzów określony w zadaniu:
Region wyznaczony przez nierówności 1 i 2 odpowiada pierwszej ćwiartce płaszczyzny kartezjańskiej. Jeśli chodzi o nierówności 3 i 4, zaczynamy od znalezienia linii ograniczeń:
9x + 8y = 144
0,5 x + 0,8y = 10 → 5x + 8y = 100
Regionem wykonalnym jest czworokąt, którego wierzchołki to punkty A, B, C i D..
Minimalny zysk to 0, dlatego linia 8x + 10y = 0 to dolna granica, a linie izo-zysku mają nachylenie -8/10 = - 0,8.
Ta wartość różni się od nachyleń innych linii ograniczających, a ponieważ możliwy obszar jest ograniczony, istnieje unikalne rozwiązanie.
To rozwiązanie odpowiada linii o nachyleniu -0,8 przechodzącej przez dowolny z punktów A, B lub C, których współrzędne to:
A (11; 5,625)
B (0; 12,5)
C (16, 0)
Obliczamy wartość G dla każdego z tych punktów:
-(11; 5,625): G.DO = 8 x 11 + 10 x 5,625 = 144,25
-(0; 12,5): G.b = 8 x 0 + 10 x 12,5 = 125
-(16, 0): G.do = 8 x 16 + 10 x 0 = 128
Największy zysk osiągnięto przy produkcji 11 ciastek z czarnego lasu i 5 625 ciastek sakypantynowych. To rozwiązanie jest zgodne z rozwiązaniem znalezionym w oprogramowaniu.
Sprawdź wynik poprzedniego ćwiczenia, używając funkcji Solver dostępnej w większości arkuszy kalkulacyjnych, takich jak Excel lub LibreOffice Calc, które zawierają algorytm Simplex do optymalizacji w programowaniu liniowym.
Jeszcze bez komentarzy