Problemy programowania liniowego: metody rozwiązywania i formułowania

Ekonomiści często potrzebują optymalizacji funkcji produkcji, maksymalizacji lub minimalizacji, np. zysku, straty lub innych danych podlegających ograniczeniu liniowemu. Rozumienie problemów programowania liniowego i formułowanie problemów - wymaga to znajomości podstaw matematyki i statystyki. Problem programowania liniowego (LP) polega na określeniu funkcji pozwalającej na uzyskanie optymalnych danych. Jest to jedno z najważniejszych narzędzi w badaniach operacji biznesowych. Jest również szeroko stosowany jako pomoc w podejmowaniu decyzji w wielu dziedzinach: w ekonomii, informatyce, matematyce i innych nowoczesnych studiach praktycznych.

Charakterystyka problemów programowania liniowego

Wyróżniamy następujące cechy LP:

1. Optymalizacja. Podstawą problemów programowania liniowego i formułowania problemów optymalizacyjnych jest maksymalizacja lub minimalizacja pewnej bazy danych, która jest przedmiotem badania. Jest to powszechne w ekonomii, biznesie, reklamie i wielu innych dziedzinach, które wymagają wydajności w celu zachowania zasobów. Dotyczy to kwestii zysku, pozyskiwania zasobów, czasu produkcji i innych ważnych wskaźników ekonomicznych.
2. Liniowość. Jak sama nazwa wskazuje, wszystkie problemy LP mają cechę liniowości. Jest to jednak czasami mylące, ponieważ liniowość odnosi się tylko do zmiennych stopnia 1, wyłączając funkcje potęgowe, pierwiastki kwadratowe i inne związki nieliniowe. Nie oznacza to, że funkcje problemu LP mają tylko jedną zmienną. Traktuje zmienne jako współrzędne punktów na linii prostej, z wyłączeniem wszelkich krzywizn.
3. Funkcja celu. Podstawą problemów programowania liniowego i obiektywnych twierdzeń problemowych są zmienne, które zmieniają się dowolnie, np. czas poświęcony na pracę, wyprodukowane jednostki. Funkcję celu piszemy z dużej litery "Z".
4. Ograniczenia. Wszystkie LP są ograniczone przez zmienne w ramach funkcji. Ograniczenia te przyjmują postać nierówności, np<3", gdzie b może oznaczać jednostki książek napisanych przez autora w miesiącu. Nierówności te określają sposób maksymalizacji/minimalizacji funkcji celu, ponieważ razem definiują obszary podejmowanie decyzji.

Warunki definicji celu to

Przedsiębiorstwa dążą do uzyskania jak największego zwrotu ze swojej działalności, dlatego muszą maksymalnie wykorzystać dostępne im zasoby: ludzkie, materiałowe, sprzętowe, lokalowe i inne. LP są reprezentowane przez jako użyteczny narzędzie pomagające określić najlepsze rozwiązanie w firmie.

Warunki dla problemów programowania liniowego i twierdzenia o problemach są konieczne dla uzyskać maksymalny zysk netto. Aby rozwiązać problem LP musi mieć:

1. Ograniczenia lub ograniczone zasoby, np. ograniczona liczba pracowników, maksymalna liczba klientów lub limit strat produkcyjnych.
2. Cel: maksymalizacja przychodów lub minimalizacja kosztów.
3. Proporcjonalna liniowość. Równania, które generują zmienne decyzyjne muszą być liniowe.
4. Homogeniczność: Właściwości zmiennych rozwiązania i zasobów są takie same. Na przykład godziny pracy człowieka są równie wydajne lub towary wykonane na maszynie są identyczne.
5. Podzielność: produkty i zasoby mogą być przedstawione jako ułamki.
6. Brak negatywności: rozwiązania muszą być dodatnie lub zerowe.

Funkcja celu w wyznaczaniu podstawowego problemu programowania liniowego matematycznie wyraża cel, który ma być osiągnięty przy rozwiązywaniu problemu. Na przykład, maksymalizacja zysków firmy lub minimalizacja kosztów produkcji.

Przedstawia to równanie ze zmiennym rozwiązaniem, gdzie: X 1, X 2, X 3, ..., X n - zmienne decyzyjne; C 1, C 2, C 3, ..., C n są stałymi.

Każde ograniczenie jest wyrażone matematycznie za pomocą dowolnego z tych atrybutów:

1. Mniej lub więcej niż (≤). Gdy istnieje górny limit, np. nadgodziny nie mogą być dłuższe niż 2 godziny dziennie.
2. Równe (=). Określa wiążącą relację, np. zapas końcowy równa się zapasowi początkowemu plus produkcja minus sprzedaż.
3. Większe lub równe (≥). Na przykład, gdy istnieje dolna granica, produkcja danego produktu musi być wyższa niż przewidywany popyt.
4. Ogólne sformułowanie problemu programowania liniowego rozpoczyna się od ustalenia ograniczeń.
5. Każdy problem LP musi mieć jedno lub więcej ograniczeń.
6. Dodatnie zmienne decyzyjne muszą być rozpatrywane w ramach ograniczeń.

Etapy rozwiązywania problemów

Ogólne ujęcie problemu programowania liniowego i jego sformułowanie odnosi się do przełożenia rzeczywistego problemu na postać równań matematycznych, które można rozwiązać.

Etapy wyznaczania problemu programowania liniowego na liczbach całkowitych:

1. Zdefiniuj liczbę, która określa zachowanie funkcji celu dla optymalizacji.
2. Znajdź zbiór ograniczeń i wyraź je jako równania liniowe lub nierówności. W ten sposób zostanie wyznaczona dziedzina w n-wymiarowej przestrzeni optymalizowanych funkcji.
3. Konieczne jest nałożenie na zmienne problemu warunku nieujemności, tzn. wszystkie muszą być dodatnie.
4. Wyrażenie funkcji w postaci równania liniowego.
5. Optymalizuj funkcję graficznie lub matematycznie, gdy matematyczne sformułowanie problemu programowania liniowego jest wykonane.

Metoda graficzna

Metoda graficzna jest stosowana do wykonywania problemów LP w dwóch zmiennych. Metoda ta nie ma zastosowania do rozwiązania problemów, które mają trzy lub więcej rozwiązań zmiennych.

Standardowy problem LP polegający na maksymalizacji niewiadomej problemu, w którym funkcja jest zwiększana, podlega ograniczeniom postaci:

x ≥ 0, y ≥ 0, z ≥ 0 oraz dalsze ograniczenia formujące:

Ax + By + C z +. , ≤ N,

gdzie A, B, C i N są liczbami nieujemnymi.

Nierówność musi być "≤", a nie "=" lub "≥".

Graficzna metoda LP z dwiema niewiadomymi jest następująca:

1. Ustalenie możliwych regionów wykresu.
2. Obliczyć współrzędne kątowe punktów.
3. Zastąp je, aby zobaczyć optymalną wartość. Punkt ten daje rozwiązanie problemu LP.
4. Minimalizuj funkcję i jeśli jej współczynniki są nieujemne, to rozwiązanie istnieje.

Identyfikacja istniejących rozwiązań:

1. Ograniczenie obszaru poprzez dodanie pionowej linii na prawo od najbardziej prawego punktu narożnego oraz poziomej linii powyżej najwyższego punktu narożnego.
2. Obliczyć współrzędne nowych punktów narożnych.
3. Znajdź punkt narożny o optymalnej wartości.
4. Jeśli zachodzi w punkcie początkowym regionu nieograniczonego, to LP ma rozwiązanie w tym punkcie. Jeśli nie, to nie ma optymalnego rozwiązania.

Szkicowanie zbioru rozwiązań

Wybierz punkt odniesienia i zaznacz obszar, który ma być zablokowany.

Narysuj obszar reprezentowany przez nierówność dwóch zmiennych w problemie programowania liniowego. Krótko o przykładzie:

1. Narysuj linię otrzymaną przez zastąpienie nierówności równością.
2. Wybierz punkt kontrolny, (0,0). Dobry wybór, jeśli linia przechodzi przez początek.
3. Jeśli punkt kontrolny spełnia nierówność, to zbiorem rozwiązań jest cały obszar po tej samej stronie prostej co punkt kontrolny. W przeciwnym razie jest po drugiej stronie linii.
4. Region dopuszczalny jest określony przez zbiór nierówności liniowych i jest zbiorem punktów spełniających wszystkie nierówności.
5. Aby ją narysować, określoną zbiorem nierówności liniowych o dwóch zmiennych, wykonaj na tym samym wykresie obszary reprezentowane przez każdą nierówność, pamiętając o zacieniowaniu części płaszczyzny, które nie są potrzebne.

Metoda simpleks dla maksymalizacji

Problem programowania liniowego z modelem matematycznym do maksymalizacji można stwierdzić za pomocą metody simpleks:

1. Przekształć dane w układ równań, wprowadzając zmienne słabe, aby przekształcić ograniczenia w równania, i przepisz funkcję do postaci standardowej.
2. Zapisz oryginalną tabelę.
3. Wybierz kolumnę rozrzutu, liczbę ujemną o najwyższej wartości w dolnym rzędzie, z pominięciem wpisu najbardziej wysuniętego w prawo. Jego kolumna jest podsumowaniem. Jeśli są dwóch kandydatów, wybierz jednego. Jeśli wszystkie liczby w dolnym rzędzie są zerowe lub dodatnie, z wyjątkiem najbardziej prawego wpisu, wszystko jest gotowe i rozwiązanie bazowe maksymalizuje funkcję celu.
4. Wybierz pasek w kolumnie. Oś musi być zawsze liczbą dodatnią. Dla każdego dodatniego wpisu "b" w kolumnie danych sumarycznych oblicz stosunek "a/b", gdzie "a" jest odpowiedzią w tym rzędzie. Wybierz minimum współczynników testowych, wtedy odpowiednia liczba "b" będzie osią.
5. Użyj pręta, aby wyczyścić kolumnę w zwykły sposób, pamiętając, aby dokładnie przestrzegać zaleceń dotyczących formułowania operacji z wierszami, opisanych we wskazówkach dotyczących do metody Gaussa-Jordana, a następnie zamienić kolumnę z etykietą z kolumny.
6. Zmienna oznaczająca początkowo wiersz zestawienia jest zmienną wychodzącą, a zmienna oznaczająca kolumnę jest zmienną przychodzącą.

Aby uzyskać rozwiązanie bazowe odpowiadające dowolnej tabeli w metodzie simpleks, należy ustawić wszystkie zmienne, które nie są wyświetlane jako etykiety wierszy na zero. Wartość wyświetlanej etykiety wiersza (zmiennej aktywnej) jest liczbą w prawej kolumnie wiersza, podzieloną przez liczbę w tym wierszu w kolumnie oznaczonej tą samą zmienną.

Niestandardowe ograniczenia

W celu rozwiązania problemu LP z ograniczeniami w postaci (Ax + By +. , .≥ N) z dodatnim N, odejmujemy od lewej strony dodatkową zmienną (zamiast dodawać słabą zmienną). Rozwiązanie bazowe odpowiadające oryginalnej tabeli nie będzie wykonalne, ponieważ niektóre z aktywnych zmiennych będą ujemne. Dlatego zasady dotyczące początkowego obrotu są inne niż podane powyżej.

Następnie zaznacz wszystkie wiersze, które podają ujemną wartość dla powiązanej zmiennej aktywnej, z wyjątkiem celu. Jeśli zaznaczone są rzędy, należy zacząć od kroku I.

I krok. W pierwszym rzędzie znajdź największą liczbę dodatnią. Użyj współczynników testowych jak w poprzedniej sekcji, aby znaleźć podsumowanie w tej kolumnie, a następnie rozwiń ten zapis. Powtarzać do momentu, gdy nie pozostaną żadne zaznaczone rzędy, a następnie przejść do kroku II.

Etap II wykorzystuje metodę simplex dla standardowego problemu maksymalizacji. Jeżeli po kroku I w lewym dolnym rzędzie występują wartości ujemne, należy zastosować metodę standardowych problemów maksymalizacji.

Przykład gry, którą można rozwiązać metodą simpleksową.

Narzędzie online PHPSimplex

W dzisiejszych czasach narzędzia technologiczne ułatwiają wiele działania życie zawodowe i metody rozwiązywania problemów LP nie są wyjątkiem. Ich zaletą jest to, że, co można uzyskać optymalne rozwiązanie z każdego komputera z dostępem do Internetu.

PHPSimplex to doskonałe narzędzie online do rozwiązywania problemów LP. Ta aplikacja może rozwiązywać problemy bez ograniczeń na liczbę zmiennych i ograniczeń. Dla problemów z dwiema zmiennymi demonstruje rozwiązanie graficzne i w prosty i zrozumiały sposób przedstawia cały proces obliczania optymalnego rozwiązania. Posiada przyjazny interfejs, bliski użytkownikowi, łatwy w obsłudze i intuicyjny, dostępny w kilku językach.

WanerMath: aplikacje bez granic

Warneth dostarcza 2 narzędzia do rozwiązywania problemów programowania liniowego:

1. Graf programowania liniowego (dwie zmienne).
2. Metoda simpleks.

W przeciwieństwie do innych narzędzi, gdzie umieszczane są tylko współczynniki, tutaj uwzględnione są wszystkie funkcje ze zmiennymi. To nie jest bardzo trudne dla początkujących użytkowników, jako że strona profilu ma instrukcja użytkowania. Ponadto strona posiada funkcję "Examples", która automatycznie tworzy problemy, aby użytkownik mógł ocenić jej działanie, np. przy wyznaczaniu problemu programowania liniowego transportu.

JSimplex to kolejne narzędzie online. Pozwala na rozwiązywanie problemów LP bez ograniczania liczby zmiennych. Posiada prosty interfejs zarządzania, który prosi użytkownika o określenie celu i liczby zmiennych. Użytkownik wpisuje współczynniki funkcji celu, ograniczenia i klika "solve. Integracja, obliczenie najlepszej opcji i wyniki każdej zmiennej będą pokazane.

Jak widać, narzędzia te są niezwykle przydatne do łatwej nauki rozwiązywania programowania liniowego.

Prosty przykład LP

Firma produkuje kalkulatory ręczne i naukowe. Prognozy długoterminowe wskazują na spodziewane dzienne zapotrzebowanie na 150 kalkulatorów naukowych i 100 przenośnych. Codziennie zdolność produkcyjna produkcji maksymalnie 250 kalkulatorów naukowych i 200 przenośnych dziennie.

W celu realizacji umowy dostawy należy wyprodukować minimum 250 sztuk kalkulatorów. Sprzedaż jednego powoduje stratę 20 rubli, ale każdy ręczny kalkulator przynosi zysk 50 rubli. Należy dokonać obliczeń, aby zmaksymalizować zysk netto.

Algorytm dla przykładu programowania liniowego:

1. Rozwiązania zmienne. Ponieważ określono optymalną liczbę kalkulatorów, będą one zmiennymi I w tym problemie: x to liczba kalkulatorów naukowych, y to liczba kalkulatorów przenośnych.
2. Ustalenie ograniczeń Ponieważ firma nie może wyprodukować ujemnej liczby kalkulatorów dziennie, naturalnym ograniczeniem byłoby: x ≥ 0, y ≥ 0.
3. Dolna granica: x ≥ 150, y ≥ 100.
4. Ustalić górną granicę dla tych zmiennych ze względu na ograniczenia produkcyjne przedsiębiorstwa: x ≤ 250, y ≤ 200.
5. Wspólne ograniczenie wartości "x" i "y" ze względu na minimalne zamówienie do wysyłki: x + y ≥ 250
6. Optymalizacja funkcji zysku netto: P = -20x + 50y.
7. Rozwiąż problem: maksymalizuj P = -20x + 50y, przy założeniu, że 150 ≤ x ≤ 250; 100 ≤ y ≤ 200; x + y ≥ 250.

Aplikacje

Wśród zastosowań programowania liniowego najczęściej spotykane są:

1. Łączne planowanie sprzedaży i operacji. Celem jest minimalizacja kosztów produkcji w krótkim okresie, np. trzech i sześciu miesięcy, poprzez zaspokojenie oczekiwanego popytu.
2. Planowanie produktu: znalezienie optymalnej kombinacji produktów, biorąc pod uwagę, że wymagają one różnych zasobów i mają różne koszty. Na przykład, znajdź optymalną mieszankę pierwiastków chemicznych dla benzyny, farb, diety ludzkiej i paszy dla zwierząt.
3. Przepływ produkcji: określenie optymalnego przepływu dla produkcji wyrobu, który musi przejść kolejno przez kilka procesów roboczych, gdzie każdy ma swoje koszty i charakterystykę produkcji.
4. Programowanie liniowe problem transportowy stwierdzenie, rozkład jazdy transportu. Metoda służy do zaprogramowania wielu tras danej liczby pojazdów do obsługi klientów lub odbioru materiałów do transportu między różnymi lokalizacjami. Każdy pojazd może mieć inną pojemność i wydajność.
5. Zarządzanie zapasami: określenie optymalnej kombinacji produktów, które będą znajdowały się w magazynie w sieci sprzedaży.
6. Programowanie personelu: opracowanie planu zatrudnienia, który zaspokoi przewidywane zmienne zapotrzebowanie na specjalistów przy minimalnej możliwej liczbie pracowników.
7. Kontrola odpadów: za pomocą programowania liniowego można obliczyć, jak zmniejszyć ilość odpadów do minimum.

Oto niektóre z nich najczęściej spotykany Zastosowania, w których wykorzystuje się programowanie liniowe. W ogólności każdy problem optymalizacyjny spełniający powyższe warunki można rozwiązać za pomocą jego.