PROGRAMOWANIE LINIOWE: DO CZEGO SŁUŻY, MODELE, OGRANICZENIA, ZASTOSOWANIA - MATEMATYKA - 2025

Programowanie liniowe jest metoda matematyczna jest wykorzystywane do optymalizacji (zwiększania lub zmniejszania odpowiednio) funkcji, której zmienne są ograniczone, jak długo, jak funkcja i ograniczenia są liniowo zależne zmienne.

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.

Rysunek 1. Programowanie liniowe jest szeroko stosowane do optymalizacji zysków. Źródło: Piqsels.

Jednym z najprostszych przypadków jest maksymalizacja funkcji liniowej, która zależy tylko od dwóch zmiennych, zwanych zmiennymi decyzyjnymi. Może mieć postać:

Z = k ₁ x + k ₂ y

Ze stałymi k ₁ i k ₂ . 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 = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

Więzy są również modelowane matematycznie przez układ równań lub nierówności, równie liniowych względem x i y.

Zbiór rozwiązań w tym systemie nazywany jest rozwiązaniami wykonalnymi lub punktami wykonalnymi. 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 Berkeley i Uniwersytetu Stanforda.

Rysunek 2. Matematycy George Dantzig (po lewej) i Leonid Kantorovich (po prawej). Źródło: F. Zapata.

Liniowe modele programowania

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 = ∑k _i x _i

W tym równaniu k _i to współczynniki, a x _i to zmienne decyzyjne.

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.

Rodzaje ograniczeń

Możesz mieć wiele M ograniczeń, zaczynając od j = 1 do j = M. Matematycznie ograniczenia są trzech typów:

1. A _j = ∑ a _ij . x _i
2. B _j ≥ ∑ b _ij . x _i
3. C _j ≤ ∑ c _ij . x _i

Pierwsze ograniczenie jest typu równania liniowego i oznacza, że ​​wartość _Aj , która jest znana, musi być przestrzegana.

Dwa pozostałe ograniczenia to nierówności liniowe i oznacza to, że znane wartości B _j i C _j mogą być przestrzegane lub przekraczane, gdy pojawiający się symbol jest ≥ (większy lub równy) lub jest przestrzegany lub nieprzekraczany, jeśli symbol jest ≤ (mniejszy lub równy).

Przykład modelu

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 poświęconego.

Do jej przygotowania wymagają jaj i cukru. Do czarnego lasu potrzeba 9 jajek i 500 g cukru, a do sacypantyny 8 jajek i 800 g cukru. Odpowiednie ceny sprzedaży to 8 i 10 USD.

Problem w tym, że ile ciast każdego rodzaju musi wypiec piekarnia, aby zmaksymalizować zysk, wiedząc, że ma 10 kilogramów cukru i 144 jajka?

Zmienne decyzje

Zmienne decyzyjne to „x” i „y”, które przyjmują wartości rzeczywiste:

-x: liczba ciastek z czarnego lasu

-y: ciasta typu sacipantine.

Ograniczenia

Ograniczenia wynikają z faktu, że liczba ciastek jest ilością dodatnią, a ilość surowca do ich przygotowania jest ograniczona.

Dlatego w formie matematycznej ograniczenia te przyjmują postać:

1. x ≥ 0
2. i ≥0
3. 9x + 8 lat ≤ 144
4. 0,5 x + 0,8 lat ≤ 10

Więzy 1 i 2 stanowią warunek nieujemności wcześniej ujawniony, 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.

Funkcja celu

Wreszcie funkcją celu jest zysk uzyskany przy produkcji „x” ciastek z czarnego lasu plus „y” ilość sacipantyn. 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

Metody rozwiązania

Różne metodologie rozwiązań obejmują między innymi metody graficzne, algorytm simplex i metodę punktów wewnętrznych.

- Metoda graficzna lub geometryczna

Kiedy masz problem z dwiema zmiennymi, taki jak ten w poprzedniej sekcji, ograniczenia określają region wielokątny na płaszczyźnie xy, zwany regionem wykonalności lub regionem żywotności.

Rysunek 3. Region wykonalny, w którym znajduje się rozwiązanie problemu optymalizacji. Źródło: Wikimedia Commons.

Region ten jest konstruowany przy użyciu linii ograniczeń, 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:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8 lat = 10

Wszystkie punkty w regionie otoczonym tymi liniami są możliwymi rozwiązaniami, więc jest ich nieskończenie wiele. Z wyjątkiem przypadku, gdy 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.

Rysunek 4. Możliwy region problemu z ciastem. Linia o wzmocnieniu 0 przecina początek. Źródło: F. Zapata z Geogebra.

Optymalne rozwiązanie, jeśli istnieje, znajduje się za pomocą funkcji celu. Na przykład, próbując znaleźć maksymalny zysk G, mamy następujący wiersz, który nazywa się linią izo-zysku:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

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 mają to samo nachylenie -k ₁ / k ₂ , więc są równoległe linie.

Optymalne rozwiązanie

Teraz można wykazać, że optymalnym rozwiązaniem problemu liniowego jest zawsze skrajny punkt lub wierzchołek wykonalnego obszaru. Więc:

Jeśli linia najbliższa początku ma cały odcinek wspólny z możliwym do zrealizowania regionem, mówi się, że istnieje nieskończona liczba rozwiązań. Taki przypadek występuje, gdy nachylenie linii izo-zysku jest równe nachyleniu dowolnej innej linii ograniczającej region.

W przypadku naszego ciasta wierzchołkami kandydującymi są A, B i C.

- Metoda simplex Dantziga

Metoda graficzna lub geometryczna ma zastosowanie do dwóch zmiennych. Jest to jednak 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ż dwoma zmiennymi stosuje się metodę simplex, która składa się z szeregu algorytmów optymalizujących funkcje celu. Do wykonywania obliczeń często używa się macierzy i prostych działań arytmetycznych.

Metodę simplex rozpoczynamy od wybrania wykonalnego 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.

Aplikacje

Programowanie liniowe i nieliniowe jest stosowane w wielu dziedzinach w celu podejmowania najlepszych decyzji 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 wykonać szereg 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 przydzielenia odpowiednich zadań personelowi przedsiębiorstwa lub fabryki lub im harmonogramów.

-W doborze najbardziej pożywnej żywności i po najniższych kosztach w przemyśle hodowlanym i drobiarskim.

Rozwiązane ćwiczenia

- Ćwiczenie 1

Rozwiąż graficznie model programowania liniowego przedstawiony w poprzednich sekcjach.

Rozwiązanie

Konieczne jest wykreślenie zbioru wartości określonych przez system ograniczeń określonych w zadaniu:

1. x ≥ 0
2. i ≥0
3. 9x + 8 lat ≤ 144
4. 0,5 x + 0,8 lat ≤ 10

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.

Wartość ta różni się od nachyleń innych linii ograniczających, a ponieważ realny region jest ograniczony, istnieje unikalne rozwiązanie.

Rysunek 5. Rozwiązanie graficzne ćwiczenia 1, pokazujące możliwy do wykonania obszar i punkt rozwiązania C na jednym z wierzchołków wspomnianego obszaru. Źródło: F. Zapata.

To rozwiązanie odpowiada linii nachylenia -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)

Optymalne rozwiązanie

Obliczamy wartość G dla każdego z tych punktów:

- (11; 5,625): G _A = 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 _C = 8 x 16 + 10 x 0 = 128

Największy zysk osiągnięto przy produkcji 11 ciastek z czarnego lasu i 5 625 ciastek sacipantine. To rozwiązanie zgadza się z rozwiązaniem znalezionym przez oprogramowanie.

- Ćwiczenie 2

Sprawdź wynik poprzedniego ćwiczenia, używając funkcji Solver dostępnej w większości arkuszy kalkulacyjnych, takich jak Excel czy LibreOffice Calc, które zawierają algorytm Simplex do optymalizacji w programowaniu liniowym.

Rozwiązanie

Rysunek 6. Szczegóły rozwiązania z ćwiczenia 1 do arkusza kalkulacyjnego Libre Office Calc. Źródło: F. Zapata.

Rysunek 7. Szczegóły rozwiązania z ćwiczenia 1 do arkusza kalkulacyjnego Libre Office Calc. Źródło: F. Zapata.

Bibliografia

1. Znakomity. Programowanie liniowe. Odzyskany z: brilliant.org.
2. Eppen, G. 2000. Badania operacyjne w naukach administracyjnych. 5. Wydanie. Prentice Hall.
3. Haeussler, E. 1992. Matematyka w zarządzaniu i ekonomii. 2nd. Wydanie. Grupo Editorial Iberoamericana.
4. Hiru.eus. Programowanie liniowe. Odzyskany z: hiru.eus.
5. Wikipedia. Programowanie liniowe. Odzyskane z: es. wikipedia.org.