Funkcja celu- funkcja rzeczywista lub całkowita kilku zmiennych, która podlega optymalizacji (minimalizacji lub maksymalizacji) w celu rozwiązania jakiegoś problemu optymalizacyjnego. Termin używany w programowaniu matematycznym, badaniach operacyjnych, programowaniu liniowym, teorii rozwiązania statystyczne oraz innych dziedzin matematyki, przede wszystkim o charakterze stosowanym, chociaż celem optymalizacji może być także rozwiązanie samego problemu matematycznego. Oprócz funkcja celu W problemie optymalizacji ograniczenia można określić dla zmiennych w postaci układu równości lub nierówności. W przypadek ogólny argumenty funkcji docelowej można określić w dowolnych zestawach.
Przykłady
Funkcje gładkie i układy równań
Zagadnienie rozwiązania dowolnego układu równań
( fa 1 (x 1 , x 2 , … , x M) = 0 fa 2 (x 1 , x 2 , … , x M) = 0 … fa N (x 1 , x 2 , … , x M) = 0 ( \ Displaystyle \ lewo \ ({\ początek (macierz) F_ (1) (x_ (1), x_ (2), \ ldots, x_ (M)) = 0 \\ F_ (2) (x_ (1), x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(macierz) )\Prawidłowy.)
można sformułować jako problem minimalizacji funkcji celu
S = ∑ jot = 1 N fa jot 2 (x 1 , x 2 , … , x M) (1) (\ Displaystyle S = \ suma _ (j = 1) ^ (N) F_ (j) ^ (2) ( x_(1),x_(2),\ldots,x_(M))\qquad (1))
Jeżeli funkcje są gładkie, to problem minimalizacji można rozwiązać metodami gradientowymi.
Dla dowolnej gładkiej funkcji celu pochodne cząstkowe w odniesieniu do wszystkich zmiennych można przyrównać do 0 (\ displaystyle 0). Optimum funkcji celu będzie jednym z rozwiązań takiego układu równań. W przypadku funkcji (1) (\ displaystyle (1)) będzie to układ równań metody najmniejszych kwadratów(MNC). Każde rozwiązanie układu pierwotnego jest rozwiązaniem systemu najmniejszych kwadratów. Jeśli pierwotny system jest niespójny, wówczas system najmniejszych kwadratów, który zawsze ma rozwiązanie, pozwala uzyskać przybliżone rozwiązanie pierwotnego układu. Liczba równań w układzie najmniejszych kwadratów pokrywa się z liczbą niewiadomych, co czasami ułatwia rozwiązanie wspólnych układów początkowych.
Programowanie liniowe
Do innych słynny przykład Funkcja celu jest funkcją liniową, która pojawia się w problemach programowania liniowego. W przeciwieństwie do kwadratowej funkcji celu optymalizacja funkcji liniowej jest możliwa tylko w przypadku istnienia ograniczeń w postaci układu liniowych równości lub nierówności.
Optymalizacja kombinatoryczna
Typowym przykładem kombinatorycznej funkcji celu jest funkcja celu problemu komiwojażera. Funkcja ta jest równa długości cyklu Hamiltona na wykresie. Jest zdefiniowany na zbiorze permutacji n - 1 (\ displaystyle n-1) wierzchołków grafu i jest wyznaczany przez macierz długości krawędzi grafu. Dokładne rozwiązanie takich problemów często sprowadza się do wyliczenia opcji.
Rozdział 1. Opis głównego problemu programowania liniowego
Programowanie liniowe
Programowanie liniowe to gałąź programowania matematycznego badająca metody rozwiązywania problemów ekstremalnych, które charakteryzują się zależność liniowa pomiędzy zmiennymi a testem liniowym. Problematyka tego typu znajduje szerokie zastosowanie w różnych dziedzinach działalności człowieka. Systematyczne badania tego typu problemów rozpoczęły się w latach 1939–1940. w twórczości L.V. Kantorowicz.
Matematyczne problemy programowania liniowego obejmują badania konkretnych sytuacji produkcyjnych i ekonomicznych, które w tej czy innej formie są interpretowane jako problemy optymalnego wykorzystania ograniczonych zasobów.
Zakres problemów rozwiązywanych metodami programowania liniowego jest dość szeroki. Są to na przykład:
problem optymalnego wykorzystania zasobów w planowaniu produkcji;
problem mieszaniny (planowanie składu produktu);
problem znalezienia optymalnej kombinacji różne typy produkty do przechowywania w magazynach (zarządzanie zapasami lub);
zadania transportowe (analiza lokalizacji przedsiębiorstwa, przepływ towarów).
Programowanie liniowe jest najbardziej rozwiniętą i powszechnie stosowaną sekcją programowania matematycznego (dodatkowo obejmuje to: programowanie całkowite, dynamiczne, nieliniowe, parametryczne). Wyjaśnia się to w następujący sposób:
modele matematyczne dużej liczby problemów ekonomicznych są liniowe względem wymaganych zmiennych;
Problem tego typu jest obecnie najczęściej badany. Zaprojektowane dla niego specjalne metody, za pomocą których rozwiązuje się te problemy, oraz odpowiednie programy komputerowe;
wiele problemów programowania liniowego po rozwiązaniu znalazło szerokie zastosowanie;
Niektóre problemy, które w pierwotnym sformułowaniu nie mają charakteru liniowego, po szeregu dodatkowych ograniczeń i założeń mogą stać się liniowe lub sprowadzić do takiej postaci, że można je rozwiązać metodami programowania liniowego.
Ekonomiczny i matematyczny model dowolnego problemu programowania liniowego obejmuje: funkcję celu, optymalna wartość które (maksimum lub minimum) należy znaleźć; ograniczenia w formie systemowej równania liniowe lub nierówności; wymóg nieujemności zmiennych.
W widok ogólny model jest zapisany w następujący sposób:
funkcja celu
(1.1) z ograniczeniami
(1.2) wymagania dotyczące nieujemności
(1.3) gdzie X J– zmienne (nieznane);
- współczynniki problemu programowania liniowego.
Problem polega na znalezieniu optymalnej wartości funkcji (1.1) przy spełnieniu ograniczeń (1.2) i (1.3).
System ograniczeń (1.2) nazywany jest ograniczeniami funkcjonalnymi problemu, a ograniczenia (1.3) nazywane są ograniczeniami bezpośrednimi.
Wektor spełniający ograniczenia (1.2) i (1.3) nazywany jest dopuszczalnym rozwiązaniem (planem) problemu programowania liniowego. Plan, w którym funkcja (1.1) osiąga swoją maksymalną (minimalną) wartość, nazywa się optymalnym.
1.2. Metoda simpleksowa rozwiązywania problemów programowania liniowego
Metodę simpleks opracował i po raz pierwszy zastosował do rozwiązywania problemów w 1947 roku amerykański matematyk J. Danzig.
Dwuwymiarowe problemy programowania liniowego rozwiązywane są graficznie. Dla przypadku N=3 możemy rozważyć trójwymiarowa przestrzeń a funkcja celu osiągnie optymalną wartość w jednym z wierzchołków wielościanu.
Dopuszczalnym rozwiązaniem (dopuszczalnym planem) problemu LP podanym w postaci standardowej jest uporządkowany zbiór liczb (x1, x2, ..., xn) spełniający ograniczenia; jest to punkt w przestrzeni n-wymiarowej.
Zbiór dopuszczalnych rozwiązań tworzy obszar dopuszczalnych rozwiązań (ADS) problemu LP. ODR jest wypukłym wielościanem (wielokątem).
Ogólnie, gdy problem dotyczy N-niewiadomych, można powiedzieć, że obszar rozwiązań dopuszczalnych, określony przez układ warunków granicznych, jest reprezentowany przez wielościan wypukły w przestrzeni n-wymiarowej i osiągana jest optymalna wartość funkcji celu w jednym lub większej liczbie wierzchołków.
Rozwiązaniem podstawowym jest rozwiązanie, w którym wszystkie zmienne wolne są równe zeru.
Rozwiązanie pomocnicze to rozwiązanie podstawowe, które nie jest ujemne. Roztwór nośnika może być niezdegenerowany i zdegenerowany. Rozwiązanie odniesienia nazywa się niezdegenerowanym, jeśli liczba jego niezerowych współrzędnych jest równa rangi układu, w przeciwnym razie jest zdegenerowane.
Dopuszczalne rozwiązanie, w którym funkcja celu osiąga wartość ekstremalną, nazywamy optymalnym i oznaczamy 
.
Bardzo trudno jest rozwiązać te problemy graficznie, gdy liczba zmiennych jest większa niż 3. Istnieje uniwersalny sposób rozwiązywania problemów programowania liniowego, zwany metodą simpleksową.
Metoda simpleksowa jest uniwersalną metodą rozwiązywania problemów LP, która jest procesem iteracyjnym rozpoczynającym się od jednego rozwiązania i w poszukiwaniu najlepszej opcji przesuwa się wzdłuż punktów narożnych obszaru rozwiązań dopuszczalnych, aż do osiągnięcia wartości optymalnej.
Można go wykorzystać do rozwiązania dowolnego problemu programowania liniowego.
Metoda simplex opiera się na idei sekwencyjnego ulepszania powstałego rozwiązania.
Geometryczne znaczenie metody sympleksu polega na sekwencyjnym przejściu od jednego wierzchołka wielościanu więzów do sąsiedniego, w którym funkcja celu przyjmuje najlepszą (a przynajmniej nie najgorszą) wartość, aż do znalezienia rozwiązania optymalnego - wierzchołka, w którym optymalna wartość jest osiągnięta jako funkcja celu (jeśli problem ma ostateczne maksimum).
Zatem mając układ więzów sprowadzony do postaci kanonicznej (wszystkie ograniczenia funkcjonalne mają postać równości), znajdują dowolne podstawowe rozwiązanie tego układu, dbając jedynie o to, aby znaleźć je jak najprościej. Jeżeli pierwsze znalezione rozwiązanie podstawowe okaże się wykonalne, wówczas sprawdza się jego optymalność. Jeśli nie jest to optymalne, wówczas dokonuje się przejścia na inne, koniecznie dopuszczalne, rozwiązanie podstawowe. Metoda simpleks gwarantuje, że dzięki temu nowemu rozwiązaniu funkcja celu, jeśli nie osiągnie maksimum, zbliży się do niego (a przynajmniej nie odsunie się od niego). To samo należy zrobić z nowym wykonalnym rozwiązaniem podstawowym, aż do znalezienia rozwiązania optymalnego.
Proces stosowania metody simpleks polega na realizacji jej trzech głównych elementów:
metoda określania dowolnego początkowego wykonalnego podstawowego rozwiązania problemu;
zasada przejścia do najlepszego (dokładniej, nie gorszego) rozwiązania;
kryterium sprawdzenia optymalności znalezionego rozwiązania.
Metoda simpleksowa składa się z kilku etapów i można ją sformułować w postaci przejrzystego algorytmu (jasnej instrukcji wykonywania kolejnych operacji). Dzięki temu z powodzeniem można go zaprogramować i zaimplementować na komputerze. Problemy z małą liczbą zmiennych i ograniczeń można rozwiązać ręcznie, stosując metodę simplex.
6.1.Wprowadzenie
Optymalizacja. Część 1
Metody optymalizacji pozwalają na wybór najlepsza opcja projekty ze wszystkich możliwe opcje. W ostatnie lata metody te zostały podane wielka uwaga w efekcie opracowano szereg wysoce wydajnych algorytmów, które pozwalają znaleźć optymalną opcję projektowania za pomocą komputera. W tym rozdziale przedstawiono podstawy teorii optymalizacji, zbadano zasady leżące u podstaw konstrukcji algorytmów rozwiązań optymalnych, opisano najbardziej znane algorytmy oraz przeanalizowano ich zalety i wady.
6.2.Podstawy teorii optymalizacji
Termin „optymalizacja” w literaturze odnosi się do procesu lub sekwencji operacji, która pozwala uzyskać dopracowane rozwiązanie. Chociaż ostatecznym celem optymalizacji jest znalezienie najlepszego, czyli „optymalnego” rozwiązania, zwykle trzeba zadowolić się ulepszaniem znanych rozwiązań, a nie ich doskonaleniem. Optymalizacja jest zatem rozumiana raczej jako dążenie do doskonałości, której nie da się osiągnąć.
Rozważając dowolny układ opisany m równaniami z n niewiadomymi, możemy wyróżnić trzy główne typy problemów. Jeśli m=n, problem nazywa się algebraicznym. Ten problem ma zwykle jedno rozwiązanie. Jeśli m>n, to problem jest nadokreślony i z reguły nie ma rozwiązania. Wreszcie dla m
Zanim zaczniemy omawiać zagadnienia optymalizacyjne, wprowadzimy szereg definicji.
Parametry projektowe
Termin ten oznacza niezależne parametry zmienne, które całkowicie i jednoznacznie determinują rozwiązywany problem projektowy. Parametry projektowe to nieznane wielkości, których wartości są obliczane w procesie optymalizacji. Wszelkie wielkości podstawowe lub pochodne, które służą do ilościowego opisu systemu, mogą służyć jako parametry projektowe. Tak, mogłoby być nieznane wartości długość, masa, czas, temperatura. Liczba parametrów projektowych charakteryzuje stopień złożoności danego problemu projektowego. Zwykle liczbę parametrów projektowych oznacza się przez n, a same parametry projektowe przez x z odpowiednimi wskaźnikami. Zatem n parametrów projektowych tego problemu będzie oznaczonych przez
X1, x2, x3,...,xn.
Funkcja celu
Jest to wyrażenie, którego wartość inżynier stara się osiągnąć maksymalnie lub minimalnie. Funkcja celu pozwala ilościowo porównać dwa alternatywne rozwiązania. Z matematycznego punktu widzenia funkcja celu opisuje pewną (n+1)-wymiarową powierzchnię. Jego wartość zależy od parametrów projektowych
M=M(x 1, x 2,...,x n).
Przykładami funkcji celu często spotykanymi w praktyce inżynierskiej są koszt, waga, wytrzymałość, wymiary, wydajność. Jeśli istnieje tylko jeden parametr projektowy, funkcję celu można przedstawić za pomocą krzywej na płaszczyźnie (ryc. 6.1). Jeżeli istnieją dwa parametry projektowe, wówczas funkcja celu zostanie przedstawiona jako powierzchnia w przestrzeni trójwymiarowej (ryc. 6.2). W przypadku trzech lub więcej parametrów projektowych powierzchnie określone przez funkcję celu nazywane są hiperpowierzchniami i nie można ich przedstawić.
małżeństwo w zwykły sposób. W procesie optymalizacji dużą rolę odgrywają właściwości topologiczne powierzchni funkcji celu, od których zależy wybór najefektywniejszego algorytmu.
Funkcja celu w niektórych przypadkach może przybierać najbardziej nieoczekiwane formy. Na przykład nie zawsze da się to wyrazić
Rys. 1. Jednowymiarowa funkcja celu.
Rys. 6.2. Dwuwymiarowa funkcja celu.
zamknięta forma matematyczna, w innych przypadkach może
reprezentują funkcję odcinkowo gładką. Określenie funkcji celu może czasami wymagać tabeli danych technicznych (na przykład tabeli stanu pary wodnej) lub może wymagać eksperymentu. W niektórych przypadkach parametry projektowe przyjmują wyłącznie wartości całkowite. Przykładem może być liczba zębów skrzynia biegów lub liczbę śrub w kołnierzu. Czasami parametry projektowe mają tylko dwa znaczenia – tak lub nie. Parametry jakościowe, takie jak satysfakcja kupującego, który zakupił produkt, niezawodność, estetyka, są trudne do uwzględnienia w procesie optymalizacji, ponieważ prawie niemożliwe jest ich ilościowe scharakteryzowanie. Jednakże niezależnie od postaci, w jakiej zostanie przedstawiona funkcja celu, musi ona być jednoznaczną funkcją parametrów projektowych.
Szereg problemów optymalizacyjnych wymaga wprowadzenia więcej niż jednej funkcji celu. Czasem jedno z nich może okazać się niekompatybilne z drugim. Przykładem jest konstrukcja samolotu, w której wymagana jest jednocześnie maksymalna wytrzymałość, minimalna waga i minimalne koszty. W takich przypadkach projektant musi wprowadzić system priorytetów i przypisać każdej funkcji celu określony bezwymiarowy mnożnik. W efekcie pojawia się „funkcja kompromisowa”, pozwalająca na wykorzystanie w procesie optymalizacji jednej złożonej funkcji celu.
Znalezienie minimum i maksimum
Niektóre algorytmy optymalizacyjne mają na celu znalezienie maksimum, inne - znalezienie minimum. Jednakże niezależnie od rodzaju rozwiązywanego problemu ekstremum można zastosować ten sam algorytm, gdyż problem minimalizacji można łatwo przekształcić w problem poszukiwania maksimum poprzez odwrócenie znaku funkcji celu. Technikę tę pokazano na ryc. 6.3.
Zaprojektuj przestrzeń
Jest to nazwa obszaru zdefiniowanego przez wszystkie n parametrów projektowych. Przestrzeń projektowa nie jest tak duża, jak mogłoby się wydawać, ponieważ zwykle jest ograniczona liczbą
uwarunkowania związane z fizyczną istotą problemu. Ograniczenia mogą być tak silne, że problem nie będzie ich miał
Rys.6.3.Zmiana znaku funkcji celu na przeciwny
zadanie maksymalne zamienia się w zadanie minimalne.
zadowalające rozwiązanie. Ograniczenia dzielą się na dwie grupy: ograniczenia - równość i ograniczenia - nierówność.
Ograniczenia - Równości
Więzy - równości - to zależności pomiędzy parametrami projektowymi, które należy wziąć pod uwagę przy znalezieniu rozwiązania. Odzwierciedlają prawa natury, ekonomii, prawa, panujących gustów i dostępności niezbędne materiały. Liczba ograniczeń - równości może być dowolna. Wyglądają jak
C 1 (x 1 , x 2 ,...,x n)=0,
C 2 (x 1, x 2,...,x n)=0,
..................
Do j (x 1 , x 2 ,...,x n)=0.
Jeśli którąkolwiek z tych zależności uda się rozwiązać w odniesieniu do jednego z parametrów projektowych, wówczas pozwala to na wykluczenie tego parametru z procesu optymalizacji. Zmniejsza to liczbę wymiarów przestrzeni projektowej i upraszcza rozwiązanie problemu.
Ograniczenia - nierówności
Jest to szczególny rodzaj ograniczenia wyrażany przez nierówności. Ogólnie rzecz biorąc, może być ich tyle, ile chcesz i wszystkie mają formę
z 1 r 1 (x 1 , x 2 ,...,x n) Z 1
z 2 r 2 (x 1 , x 2 ,...,x n) Z 2
.......................
z k r k (x 1 , x 2 ,...,x n) Z k
Należy zaznaczyć, że bardzo często, ze względu na ograniczenia, optymalną wartość funkcji celu uzyskuje się nie tam, gdzie jej powierzchnia ma zerowy gradient. Często najlepsze rozwiązanie odpowiada jednej z granic przestrzeni projektowej.
Optimum lokalne
Jest to nazwa punktu w przestrzeni projektowej, w którym znajduje się funkcja celu najwyższa wartość w porównaniu do jego wartości we wszystkich innych punktach w jego bezpośrednim sąsiedztwie.
Ryc. 6.4. Dowolna funkcja celu może mieć kilka
lokalne optima.
Na ryc. Rysunek 6.4 przedstawia jednowymiarową funkcję celu, która ma dwa lokalne optima. Często przestrzeń projektowa zawiera wiele lokalnych optimów i należy uważać, aby nie pomylić pierwszego z optymalnym rozwiązaniem problemu.
Optymalne globalne
Optimum globalne to optymalne rozwiązanie dla całej przestrzeni projektowej. Jest lepsze od wszystkich innych rozwiązań odpowiadających lokalnym optimom i tego właśnie szuka projektant. Możliwe jest, że istnieje kilka równych optim globalnych zlokalizowanych w różne części przestrzeń projektowa. Sposób postawienia problemu optymalizacyjnego najlepiej zilustrować przykładem.
Przykład 6.1
Załóżmy, że trzeba zaprojektować prostokątny kontener o pojemności 1 m przeznaczony do transportu nieopakowanego włókna. Pożądane jest, aby na produkcję takich pojemników zużywano jak najmniej materiału (zakładając stałą grubość ścianek, co oznacza, że powierzchnia powinna być minimalna), ponieważ będzie to tańsze. Aby kontener można było wygodnie podnosić wózkiem widłowym, jego szerokość musi wynosić co najmniej 1,5 m.
Sformułujmy ten problem w formie dogodnej do zastosowania algorytmu optymalizacji.
Parametry projektowe: x 1, x 2, x 3.
Funkcją celu (którą należy zminimalizować) jest pole powierzchni bocznej pojemnika:
A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2.
Ograniczenie - równość:
Objętość = x 1 x 2 x 3 = 1m3.
Wiązanie - nierówność:
Problemy programowania liniowego
Programowanie liniowe (LP) to jedna z gałęzi programowania matematycznego - dyscyplina zajmująca się badaniem problemów ekstremalnych (optymalizacyjnych) i opracowywaniem metod ich rozwiązywania.
Problem z optymalizacją to zadanie matematyczne polegające na znalezieniu optymalnej (tj. maksymalnej lub minimalnej) wartości funkcji celu, przy czym wartości zmiennych muszą należeć do pewnego zakresu wartości akceptowalnych (APV).
Ogólnie rzecz biorąc, sformułowanie ekstremalnego problemu programowania matematycznego polega na wyznaczeniu największego lub najniższa wartość funkcja tzw funkcja docelowa, w warunkach (ograniczeniach), gdzie i mają dane funkcje i mają podane wartości stałe. W tym przypadku ograniczenia w postaci równości i nierówności wyznaczają zbiór (obszar) rozwiązań dopuszczalnych (ADS) i nazywane są parametry projektowe.
W zależności od rodzaju funkcji problemy programowania matematycznego dzieli się na szereg klas (programowanie liniowe, nieliniowe, wypukłe, całkowite, stochastyczne, dynamiczne itp.).
W widok ogólny problem LP ma następującą postać:
, (5.1)
, , (5.2)
, 
, (5.3)
gdzie , , mają stałe wartości.
Funkcja (5.1) nazywana jest funkcją celu; systemy (5.2), (5.3) – system ograniczeń; warunek (5.4) – warunek nieujemności parametrów projektowych.
Zbiór parametrów projektowych spełniających ograniczenia (5.2), (5.3) i (5.4) nazywa się akceptowalne rozwiązanie Lub plan.
Optymalne rozwiązanie Lub optymalnego planu Problem LP nazywany jest rozwiązaniem dopuszczalnym, w którym funkcja celu (5.1) przyjmuje wartość optymalną (maksymalną lub minimalną).
Standardowe zadanie LP jest problemem znalezienia maksymalnej (minimalnej) wartości funkcji celu (5.1) pod warunkiem (5.2) i (5.4), gdzie , , tj. te. ograniczenia jedynie w postaci nierówności (5.2), a wszystkie parametry projektowe spełniają warunek nieujemności, nie ma natomiast warunków w postaci równości:
,
, , (5.5)
.
Zadanie kanoniczne (główne). LP jest problemem znalezienia maksymalnej (minimalnej) wartości funkcji celu (5.1) pod warunkiem (5.3) i (5.4), gdzie , , tj. te. ograniczenia jedynie w postaci równości (5.3), a wszystkie parametry projektowe spełniają warunek nieujemności, nie ma natomiast warunków w postaci nierówności:
,
.
Problem kanoniczny LP można również zapisać w postaci macierzowej i wektorowej.
Postać macierzowa kanonicznego problemu LP ma następującą postać:
Postać wektorowa kanonicznego problemu LP.
Skonstruujmy na płaszczyźnie zbiór dopuszczalnych rozwiązań układu nierówności liniowych i geometrycznie znajdźmy minimalną wartość funkcji celu.
Budujemy linie proste w układzie współrzędnych x 1 x 2
Znajdujemy półpłaszczyzny określone przez układ. Ponieważ nierówności układu są spełnione dla dowolnego punktu odpowiadającej mu półpłaszczyzny, wystarczy sprawdzić je dla dowolnego punktu. Używamy punktu (0;0). Podstawmy jego współrzędne do pierwszej nierówności układu. Ponieważ , to nierówność definiuje półpłaszczyznę niezawierającą punktu (0;0). Podobnie definiujemy pozostałe półpłaszczyzny. Zbiór dopuszczalnych rozwiązań znajdujemy jako część wspólną powstałych półpłaszczyzn - jest to zacieniony obszar.
Konstruujemy wektor i prostopadłą do niego linię poziomu zerowego.
Przesuwając linię prostą (5) w kierunku wektora i widzimy, że maksymalny punkt obszaru będzie w punkcie A przecięcia prostej (3) i prostej (2). Znajdujemy rozwiązanie układu równań:
Oznacza to, że osiągnęliśmy punkt (13;11) i.
Przesuwając linię prostą (5) w kierunku wektora i widzimy, że minimalny punkt obszaru będzie w punkcie B przecięcia prostej (1) i prostej (4). Znajdujemy rozwiązanie układu równań:
Oznacza to, że zdobyliśmy punkt (6;6) i.
2. Firma meblarska produkuje połączone szafki i stoły komputerowe. Ich produkcję ogranicza dostępność surowców (wysokiej jakości płyty, okucia) oraz czas pracy maszyn je przetwarzających. Na każdą szafkę potrzeba 5 m2 desek, na stół - 2 m2. Okucia kosztują 10 dolarów za jedną szafkę i 8 dolarów za jeden stół. Firma może otrzymać od swoich dostawców do 600 m2 desek miesięcznie wraz z akcesoriami o wartości 2000 dolarów. Każda szafa wymaga 7 godzin pracy maszyny, a stół 3 godziny. Miesięcznie możliwe jest wykorzystanie jedynie 840 godzin pracy maszyn.
Ile szafek i stołów komputerowych powinna produkować firma miesięcznie, aby zmaksymalizować zyski, jeśli jedna szafka generuje zysk w wysokości 100 USD, a każde biurko generuje 50 USD?
- 1. Komponuj model matematyczny problem i rozwiązać go metodą simplex.
- 2. Stwórz model matematyczny problemu dualnego, zapisz jego rozwiązanie na podstawie rozwiązania pierwotnego.
- 3. Ustalić stopień niedoboru wykorzystywanych zasobów i uzasadnić opłacalność planu optymalnego.
- 4. Zbadaj możliwości dalszego zwiększania produkcji w zależności od wykorzystania każdego rodzaju surowca.
- 5. Ocenić możliwość wprowadzenia nowego typu produktu - regałów, jeżeli na wytworzenie jednej półki potrzeba 1 m 2 desek i akcesoriów o wartości 5 dolarów, a konieczne jest poświęcenie 0,25 godziny pracy maszyny i zysk ze sprzedaży jedna półka kosztuje 20 dolarów.
- 1. Zbudujmy model matematyczny tego problemu:
Oznaczmy przez x 1 wielkość produkcji szafek i x 2 wielkość produkcji stołów. Stwórzmy system ograniczeń i funkcję celu:
Problem rozwiązujemy metodą simplex. Zapiszmy to w formie kanonicznej:
Zapiszmy dane zadania w formie tabeli:
Tabela 1
Ponieważ Teraz wszystkie delty są większe od zera, to dalszy wzrost wartości funkcji celu f jest już niemożliwy i otrzymaliśmy plan optymalny.
Wstęp
Obecny etap rozwoju człowieka wyróżnia się tym, że epokę energii wypiera epoka informatyki. Następuje intensywne wprowadzanie nowych technologii we wszystkich obszarach działalności człowieka. Istnieje realny problem przejścia do społeczeństwa informacyjnego, dla którego rozwój edukacji powinien stać się priorytetem. Zmienia się także struktura wiedzy w społeczeństwie. Coraz ważniejsze dla praktyczne życie zdobyć podstawową wiedzę, która przyczynia się do twórczego rozwoju jednostki. Ważna jest także konstruktywność zdobywanej wiedzy i umiejętność jej konstruowania zgodnie z celem. W oparciu o wiedzę powstają nowe zasoby informacyjne społeczeństwo. Kształtowanie i zdobywanie nowej wiedzy powinno opierać się na ścisłej metodologii podejścia systemowego, w ramach którego podejście modelowe zajmuje szczególne miejsce. Możliwości podejścia modelowego są niezwykle zróżnicowane, zarówno pod względem stosowanych modeli formalnych, jak i sposobów wdrażania metod modelowania. Modelowanie fizyczne pozwala uzyskać wiarygodne wyniki dla dość prostych układów.
Obecnie nie da się wskazać obszaru działalności człowieka, w którym w takim czy innym stopniu nie znalazłyby zastosowania metody modelowania. Jest to szczególnie prawdziwe w obszarze zarządzania różne systemy, gdzie głównymi procesami jest podejmowanie decyzji na podstawie otrzymanych informacji.
1. Opis problemu
minimalna funkcja celu
Rozwiązać zadanie znalezienia minimum funkcji celu dla układu więzów określonego wielokątem rozwiązania zgodnie z opcją nr 16 zadania. Wielokąt rozwiązania pokazano na rysunku 1:
Rysunek 1 - Wielokąt rozwiązań problemu
Poniżej przedstawiono układ ograniczeń i funkcję celu problemu:
Konieczne jest rozwiązanie problemu za pomocą następujących metod:
Graficzna metoda rozwiązywania problemów LP;
Algebraiczna metoda rozwiązywania problemów LP;
Metoda Simplex rozwiązywania problemów LP;
Metoda znajdowania dopuszczalnego rozwiązania problemów LP;
Rozwiązanie problemu podwójnego LP;
Metoda rozgałęziona i związana rozwiązywania problemów całkowitych LP;
Metoda Gomoriego rozwiązywania problemów liczb całkowitych LP;
Metoda Balaza rozwiązywania problemów logicznych LP.
Porównaj wyniki rozwiązań różne metody wyciągnąć odpowiednie wnioski z pracy.
2. Graficzne rozwiązanie problemu programowania liniowego
Graficzną metodę rozwiązywania problemów programowania liniowego stosuje się w przypadkach, gdy liczba niewiadomych nie przekracza trzech. Wygodny do jakościowego badania właściwości rozwiązań i stosowany w połączeniu z innymi metodami (algebraicznym, rozgałęzionym i związanym itp.). Idea metody opiera się na graficznym rozwiązaniu układu nierówności liniowych.
Ryż. 2 Graficzne rozwiązanie problemu LP
Minimalny punkt
Równanie prostej przechodzącej przez dwa punkty A1 i A2:
AB: (0;1); (3;3)
VS: (3;3); (4;1)
CD: (4;1); (3;0)
EA: (1;0); (0;1)
CF: (0;1); (5;2)
z ograniczeniami:
Rozwiązywanie problemu programowania liniowego metodą sympleksu algebraicznego
Zastosowanie metody algebraicznej do rozwiązania problemu wymaga uogólnienia reprezentacji problemu LP. Pierwotny system ograniczeń, określony w formie nierówności, zostaje przekształcony w zapis standardowy, gdy ograniczenia są określone w formie równości. Transformacja układu więzów do widok standardowy obejmuje następujące kroki:
Przekształć nierówności tak, aby po lewej stronie znajdowały się zmienne i wyrazy wolne, a po prawej 0, tj. Do lewa strona był większy lub równy zero;
Wprowadź dodatkowe zmienne, których liczba jest równa liczbie nierówności w układzie ograniczeń;
Wprowadzając dodatkowe ograniczenia nieujemności dodanych zmiennych, należy zastąpić znaki nierówności ścisłymi znakami równości.
Przy rozwiązywaniu problemu LP metodą algebraiczną dodawany jest warunek: funkcja celu musi dążyć do minimum. Jeśli ten warunek nie jest spełniony, należy odpowiednio przekształcić funkcję celu (pomnożyć przez -1) i rozwiązać problem minimalizacji. Po znalezieniu rozwiązania podstaw wartości zmiennych do oryginalnej funkcji i oblicz jej wartość.
Rozwiązanie problemu metodą algebraiczną uważa się za optymalne, gdy wartości wszystkich zmiennych podstawowych są nieujemne, a współczynniki zmiennych wolnych w równaniu funkcji celu są również nieujemne. Jeżeli te warunki nie są spełnione, należy przekształcić układ nierówności, wyrażając jedne zmienne w kategoriach innych (zmieniając zmienne swobodne i podstawowe), aby osiągnąć spełnienie powyższych ograniczeń. Wartość wszystkich wolnych zmiennych przyjmuje się za równą zero.
Algebraiczna metoda rozwiązywania problemów programowania liniowego jest jedną z najbardziej znanych skuteczne metody podczas ręcznego rozwiązywania problemów na małą skalę, ponieważ nie wymaga dużej liczby obliczeń arytmetycznych. Maszynowa realizacja tej metody jest bardziej skomplikowana niż np. w przypadku metody simplex, ponieważ Algorytm rozwiązania wykorzystujący metodę algebraiczną jest w pewnym stopniu heurystyczny, a skuteczność rozwiązania w dużej mierze zależy od osobistego doświadczenia.
Dowolne zmienne
Św. pas - dodatkowy zestaw
Warunki nieujemności są spełnione, zatem znaleziono optymalne rozwiązanie.
3. Rozwiązywanie zadania programowania liniowego z wykorzystaniem tablicy sympleksowej
Rozwiązanie: Sprowadźmy problem do standardowej formy w celu rozwiązania za pomocą tabeli simplex.
Sprowadźmy wszystkie równania układu do postaci:
Budujemy tabelę simplex:
W górnym rogu każdej komórki tabeli wpisujemy współczynniki z układu równań;
Wybieramy maksymalny element dodatni w wierszu F, z tą różnicą, że będzie to kolumna ogólna;
Aby znaleźć element ogólny, budujemy relację dla wszystkich pozytywnych. 3/3; 9/1;- minimalny stosunek w linii x3. Dlatego - ogólny ciąg znaków i =3 - element ogólny.
Znajdujemy =1/=1/3. Wprowadzamy go do dolnego rogu komórki, w której znajduje się element ogólny;
We wszystkich pustych dolnych rogach linii ogólnej wpisujemy iloczyn wartości w górnym rogu komórki przez;
Wybierz górne rogi linii ogólnej;
We wszystkich dolnych rogach kolumny ogólnej wpisujemy iloczyn wartości w górnym rogu przez - i wybieramy powstałe wartości;
Pozostałe komórki tabeli są wypełniane jako iloczyny odpowiednich wybranych elementów;
Następnie budujemy nową tabelę, w której zamienione są oznaczenia komórek elementów kolumny ogólnej i wiersza (x2 i x3);
Wartości, które wcześniej znajdowały się w dolnym rogu, są zapisywane w górnym rogu poprzedniego ogólnego wiersza i kolumny;
Suma wartości górnych i dolnych rogów tych komórek w poprzedniej tabeli jest zapisana w górnym rogu pozostałych komórek
4. Rozwiązywanie problemu programowania liniowego poprzez znalezienie dopuszczalnego rozwiązania
Niech będzie dany układ liniowych równań algebraicznych:
Możemy założyć, że wszystko jest, w przeciwnym razie pomnożymy odpowiednie równanie przez -1.
Wprowadzamy zmienne pomocnicze:
Wprowadzamy także funkcję pomocniczą
Zminimalizujemy system zgodnie z ograniczeniami (2) i warunkami.
ZASADA ZNAJDOWANIA DOPUSZCZALNEGO ROZWIĄZANIA: Aby znaleźć dopuszczalne rozwiązanie układu (1), minimalizujemy postać (3) w ramach ograniczeń (2), przyjmując xj jako niewiadome wolne i przyjmując xj jako niewiadome podstawowe.
Podczas rozwiązywania problemu metodą sympleksową mogą wystąpić dwa przypadki:
min f=0, wtedy całe i musi być równe zero. A otrzymane wartości xj będą stanowić dopuszczalne rozwiązanie układu (1).
min f>0, tj. oryginalny system nie ma wykonalnego rozwiązania.
System źródłowy:
Wykorzystywany jest warunek zadania z poprzedniego tematu.
Wprowadźmy dodatkowe zmienne:
Znaleziono dopuszczalne rozwiązanie pierwotnego problemu: x1 = 3, x2 = 3, F = -12. Na podstawie otrzymanego rozwiązania wykonalnego znajdziemy optymalne rozwiązanie pierwotnego problemu metodą sympleksową. W tym celu z tabeli uzyskanej powyżej zbudujemy nową tablicę simplex, usuwając wiersz oraz wiersz z funkcją celu zadania pomocniczego:
Analizując skonstruowaną tablicę simplex widzimy, że znaleziono już optymalne rozwiązanie pierwotnego problemu (elementy w wierszu odpowiadającym funkcji celu są ujemne). Zatem wykonalne rozwiązanie znalezione podczas rozwiązywania problemu pomocniczego pokrywa się z optymalnym rozwiązaniem pierwotnego problemu:
6. Zagadnienie programowania liniowego dualnego
Oryginalny układ ograniczeń i funkcję celu problemu przedstawiono na poniższym rysunku.
z ograniczeniami:
Rozwiązanie: Sprowadźmy system ograniczeń do standardowej postaci:
Problem podwójny do tego będzie miał postać:
Rozwiązanie problemu dualnego zostanie przeprowadzone za pomocą prostej metody sympleksowej.
Przekształćmy funkcję celu tak, aby problem minimalizacji został rozwiązany, i napiszmy układ więzów w postaci standardowej do rozwiązania metodą sympleksową.
y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)
y7 = 5 - (-3y1 - y2 + y3 + y4)
Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min
Skonstruujmy początkową tabelę simpleksową do rozwiązania problemu podwójnego LP.
Drugi etap metody simplex
Zatem w trzecim kroku metody sympleksowej znaleziono optymalne rozwiązanie problemu minimalizacji z następującymi wynikami: y2 = -7 /8, y1 = -11/8, Ф = 12. Aby znaleźć wartość funkcję celu problemu podwójnego, znalezione wartości zmiennych podstawowych i wolnych podstawiamy do funkcji maksymalizacji:
Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12
Ponieważ wartość funkcji celu problemów bezpośrednich i podwójnych jest zbieżna, rozwiązanie problemu bezpośredniego zostaje znalezione i wynosi 12.
Fmin = Фmax = -12
7. Rozwiązywanie problemu programowania liniowego liczb całkowitych metodą rozgałęzień
Przekształćmy pierwotny problem w taki sposób, aby warunek liczby całkowitej nie był spełniony przy rozwiązywaniu konwencjonalnymi metodami.
Początkowy wielokąt rozwiązań problemu programowania liczb całkowitych.
Dla przekształconego wielokąta rozwiązań konstruujemy nowy system ograniczenia.
Zapiszmy układ ograniczeń w postaci równości do rozwiązania metodą algebraiczną.
W wyniku rozwiązania uzyskano optymalny plan problemu: x1 = 9/4, x2 = 5/2, F = -41/4. To rozwiązanie nie spełnia warunku całkowitego określonego w zadaniu. Podzielmy wielokąt pierwotnego rozwiązania na dwa obszary, wykluczając z niego obszar 3 Zmodyfikowany wielokąt rozwiązania problemu Stwórzmy nowe systemy ograniczeń dla powstałych obszarów wielokąta rozwiązania. Lewy obszar to czworobok (trapez). Poniżej przedstawiono system ograniczeń dla lewego obszaru wielokąta rozwiązania. System ograniczeń dla lewego obszaru Prawy obszar reprezentuje punkt C. Poniżej przedstawiono system ograniczeń dla właściwego obszaru decyzyjnego. Nowe systemy ograniczeń reprezentują dwa problemy pomocnicze, które należy rozwiązać niezależnie od siebie. Rozwiążmy problem programowania liczb całkowitych dla lewego obszaru wielokąta rozwiązania. W wyniku rozwiązania uzyskano optymalny plan problemu: x1 = 3, x2 = 3, F = -12. Plan ten spełnia warunek, że zmienne w zadaniu są liczbami całkowitymi i można go przyjąć jako optymalny plan odniesienia dla pierwotnego problemu programowania liniowego na liczbach całkowitych. Nie ma sensu szukać odpowiedniego regionu rozwiązania. Poniższy rysunek przedstawia postęp rozwiązywania problemu programowania liniowego liczb całkowitych w postaci drzewa. Postęp w rozwiązywaniu problemu programowania liniowego liczb całkowitych metodą Gomoriego. W wielu zastosowaniach praktycznych dużym zainteresowaniem cieszy się problem programowania liczb całkowitych, w którym podany jest układ nierówności liniowych i postać liniowa Należy znaleźć rozwiązanie całkowite układu (1), który minimalizuje funkcję celu F, a wszystkie współczynniki są liczbami całkowitymi. Jedną z metod rozwiązania problemu programowania liczb całkowitych zaproponował Gomori. Ideą metody jest wykorzystanie metod ciągłego programowania liniowego, w szczególności metody simpleksowej. 1) Metodą sympleksową wyznacza się rozwiązanie problemu (1), (2), dla którego usuwa się wymóg rozwiązania całkowitoliczbowego; jeśli rozwiązanie okaże się liczbą całkowitą, wówczas zostanie znalezione również pożądane rozwiązanie problemu liczb całkowitych; 2) W przeciwnym razie, jeśli jakaś współrzędna nie jest liczbą całkowitą, powstałe rozwiązanie problemu sprawdza się pod kątem możliwości istnienia rozwiązania całkowitego (obecność punktów całkowitych w dopuszczalnym wielościanie): jeśli w dowolnym wierszu z ułamkowym wyrazem wolnym wszystkie pozostałe współczynniki okażą się liczbami całkowitymi, to w dopuszczalnym wielościanie nie ma liczb całkowitych ani punktów i problem programowania liczb całkowitych nie ma rozwiązania; W przeciwnym razie wprowadza się dodatkowe ograniczenie liniowe, które odcina część dopuszczalnego wielościanu, która nie rokuje na znalezienie rozwiązania problemu programowania całkowitego; 3) Aby skonstruować dodatkowe ograniczenie liniowe, wybierz l-ty wiersz z ułamkowym składnikiem wolnym i wpisz dodatkowe ograniczenie gdzie i są odpowiednio częściami ułamkowymi współczynników i są wolne członek. Wprowadźmy zmienną pomocniczą do ograniczenia (3): Wyznaczmy współczynniki i uwzględnijmy w ograniczeniu (4): gdzie i są najbliższymi liczbami całkowitymi od dołu odpowiednio dla i . Gomori udowodnił, że skończona liczba podobnych kroków prowadzi do problemu programowania liniowego, którego rozwiązaniem jest liczba całkowita, a zatem rozwiązanie pożądane. Rozwiązanie: Sprowadźmy układ więzów liniowych i funkcję celu do postaci kanonicznej: Wyznaczmy optymalne rozwiązanie układu więzów liniowych, chwilowo odrzucając warunek całkowity. Używamy do tego metody simplex. Poniżej, kolejno w tabelach, przedstawiono oryginalne rozwiązanie problemu oraz podano przekształcenia oryginalnej tabeli w celu uzyskania optymalnego rozwiązania problemu: Rozwiązywanie problemów logicznych LP metodą Balazsa. Stwórz własną wersję problemu programowania liniowego liczb całkowitych ze zmiennymi boolowskimi, uwzględniając następujące zasady: w zadaniu wykorzystuje się co najmniej 5 zmiennych, co najmniej 4 ograniczenia, współczynniki ograniczeń i funkcję celu dobiera się dowolnie, ale w taki sposób sposób, aby system ograniczeń był kompatybilny. Zadanie polega na rozwiązaniu LCLP ze zmiennymi boolowskimi przy użyciu algorytmu Balazsa i określeniu zmniejszenia złożoności obliczeń w odniesieniu do rozwiązania problemu metodą poszukiwań wyczerpujących. Egzekucja ograniczeń Wartość F Ograniczenie filtrowania: Wyznaczanie redukcji wysiłku obliczeniowego Rozwiązaniem problemu przy użyciu metody wyszukiwania wyczerpującego jest 6*25=192 wyrażeń obliczeniowych. Rozwiązaniem problemu przy użyciu metody Balazsa jest 3*6+(25-3)=47 wyrażeń obliczonych. Całkowite zmniejszenie złożoności obliczeń w odniesieniu do rozwiązania problemu metodą poszukiwań wyczerpujących wynosi: Wniosek Proces projektowania systemów informatycznych wdrażających nowe technologie informatyczne jest stale udoskonalany. Inżynierowie systemów coraz częściej skupiają się na złożonych systemach, co utrudnia korzystanie z modeli fizycznych i zwiększa znaczenie modeli matematycznych i symulacji maszynowej systemów. Symulacja maszyn stała się skutecznym narzędziem do badania i projektowania złożonych systemów. Znaczenie modeli matematycznych stale rośnie ze względu na ich elastyczność, adekwatność do rzeczywistych procesów i niski koszt wdrożenia w oparciu o nowoczesne komputery PC. Coraz większe możliwości daje użytkownik, czyli specjalista od modelowania systemów z wykorzystaniem technologii komputerowej. Zastosowanie modelowania jest szczególnie skuteczne na wczesnych etapach projektowania systemów zautomatyzowanych, kiedy koszt błędnych decyzji jest najbardziej znaczący. Nowoczesne narzędzia obliczeniowe umożliwiły znaczne zwiększenie złożoności modeli stosowanych w badaniu systemów, możliwe stało się budowanie modeli kombinowanych, analitycznych i symulacyjnych, które uwzględniają całą gamę czynników występujących w układach rzeczywistych, tj. , stosowanie modeli bardziej adekwatnych do badanych zjawisk. Literatura: 1. Lyashchenko I.N. Programowanie liniowe i nieliniowe / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. - K.: „Szkoła Wyższa”, 1975, 372 s. 2. Instrukcje metodologiczne dotyczące realizacji projektu kursowego w dyscyplinie „Matematyka stosowana” dla studentów specjalności „Systemy i sieci komputerowe” studiów stacjonarnych i niestacjonarnych / Opracował: I.A. Balakireva, A.V. Skatkov - Sewastopol: Wydawnictwo SevNTU, 2003. - 15 s. 3. Wytyczne do studiowania dyscypliny „Matematyka stosowana”, sekcja „Metody przeszukiwania globalnego i minimalizacji jednowymiarowej” / Comp. A.V. Skatkov, I.A. Balakireva, LA Litvinova - Sewastopol: Wydawnictwo SevGTU, 2000. - 31 s. 4. Wytyczne dotyczące studiowania dyscypliny „Matematyka stosowana” dla studentów specjalności „Systemy i sieci komputerowe” Sekcja „Rozwiązywanie problemów programowania liniowego liczb całkowitych” dla edukacji stacjonarnej i niestacjonarnej / Opracował: I.A. Balakireva, A.V. Skatkov - Sewastopol : Wydawnictwo SevNTU, 2000. - 13 s. 5. Akulich I.L. Programowanie matematyczne na przykładach i problemach: 6. Podręcznik dodatek dla studentów ekonomii. specjalista. uniwersytety.-M.: Wyższe. szkoła, 1986.- 319 s., il. 7. Andronow S.A. Optymalne metody projektowania: Tekst wykładów / SPbSUAP. St. Petersburg, 2001. 169 s.: il. Algorytm rozwiązywania problemów programowania liniowego metodą simplex. Budowa modelu matematycznego problemu programowania liniowego. Rozwiązywanie problemu programowania liniowego w programie Excel. Znalezienie zysku i optymalnego planu produkcji. praca na kursie, dodano 21.03.2012 Rozwiązywanie problemów graficznych. Opracowanie modelu matematycznego. Wyznaczanie maksymalnej wartości funkcji celu. Rozwiązanie metodą simpleksową na sztucznym podłożu problemu kanonicznego programowania liniowego. Sprawdzenie optymalności rozwiązania. test, dodano 04.05.2016 Teoretyczne podstawy programowania liniowego. Problemy programowania liniowego, metody rozwiązywania. Analiza optymalnego rozwiązania. Rozwiązanie problemu programowania liniowego jednoindeksowego. Opis problemu i wprowadzenie danych. Etapy budowy modelu i rozwiązania. praca na kursie, dodano 12.09.2008 Budowa modelu matematycznego. Wybór, uzasadnienie i opis metody rozwiązania zadania bezpośredniego programowania liniowego metodą sympleksową, z wykorzystaniem tablicy sympleksowej. Sformułowanie i rozwiązanie problemu dualnego. Analiza wrażliwości modelu. praca na kursie, dodano 31.10.2014 Budowa modelu matematycznego w celu uzyskania maksymalnego zysku dla przedsiębiorstwa, graficzne rozwiązanie problemu. Rozwiązanie problemu za pomocą dodatku SOLVER. Analiza zmian zasobów zasobów. Wyznaczanie granic zmiany współczynników funkcji celu. praca na kursie, dodano 17.12.2014 Programowanie matematyczne. Programowanie liniowe. Problemy programowania liniowego. Graficzna metoda rozwiązywania problemów programowania liniowego. Ekonomiczne sformułowanie problemu programowania liniowego. Budowa modelu matematycznego. praca na kursie, dodano 13.10.2008 Rozwiązywanie problemu programowania liniowego metodą graficzną, sprawdzanie go w programie MS Excel. Analiza wewnętrznej struktury rozwiązania problemu w programie. Optymalizacja planu produkcji. Rozwiązanie problemu metodą simplex. Wielokanałowy system kolejkowy. test, dodano 05.02.2012 Rozwiązywanie problemu programowania liniowego metodą sympleksową: sformułowanie problemu, konstrukcja modelu ekonomicznego i matematycznego. Rozwiązanie problemu transportowego metodą potencjałową: skonstruowanie wstępnego planu odniesienia, określenie jego optymalnej wartości. test, dodano 11.04.2012 Sformułowanie problemu programowania nieliniowego. Wyznaczanie punktów stacjonarnych i ich rodzajów. Konstrukcja linii poziomu, trójwymiarowy wykres funkcji celu i więzów. Graficzne i analityczne rozwiązanie problemu. Instrukcja obsługi i schemat algorytmu. praca na kursie, dodano 17.12.2012 Analiza rozwiązania problemu programowania liniowego. Metoda simpleksowa wykorzystująca tablice sympleksowe. Modelowanie i rozwiązywanie problemów LP na komputerze. Ekonomiczna interpretacja optymalnego rozwiązania problemu. Matematyczne sformułowanie problemu transportu. Podziel trzeci wiersz przez kluczowy element równy 5, otrzymamy trzeci wiersz nowej tabeli. Kolumny podstawowe odpowiadają kolumnom jednostkowym. Obliczanie innych wartości tabeli: „BP – Plan Podstawowy”: ; „x1”: „x5”: Wartości ciągu indeksowego są nieujemne, dlatego otrzymujemy rozwiązanie optymalne: , ; Odpowiedź: maksymalny zysk ze sprzedaży wytworzonych produktów, równy 160/3 sztuk, zapewnia produkcja wyłącznie wyrobów drugiego rodzaju w ilości 80/9 sztuk. Podano problem programowania nieliniowego. Znajdź maksimum i minimum funkcji celu metodą graficzno-analityczną. Ułóż funkcję Lagrange'a i pokaż, że w punktach ekstremalnych spełnione są warunki wystarczające dla minimum (maksimum). Ponieważ ostatnia cyfra szyfru to 8, wówczas A=2; B=5. Ponieważ przedostatnia cyfra szyfru to 1, wówczas należy wybrać zadanie nr 1. Rozwiązanie: 1) Narysujmy obszar określony przez układ nierówności. Obszar ten to trójkąt ABC o współrzędnych wierzchołków: A(0; 2); B(4; 6) i C(16/3; 14/3). Poziomami funkcji celu są okręgi ze środkiem w punkcie (2; 5). Kwadraty promieni będą wartościami funkcji celu. Następnie z rysunku wynika, że minimalną wartość funkcji celu osiąga się w punkcie H, maksymalną – albo w punkcie A, albo w punkcie C. Wartość funkcji celu w punkcie A: ; Wartość funkcji celu w punkcie C: ; Oznacza to, że największą wartość funkcji osiąga się w punkcie A(0; 2) i wynosi ona 13. Znajdźmy współrzędne punktu H. Aby to zrobić, rozważ system: Prosta jest styczna do okręgu, jeśli równanie ma jednoznaczne rozwiązanie. Równanie kwadratowe ma unikalne rozwiązanie, jeśli wyróżnik wynosi 0. 2) Utwórzmy funkcję Lagrange'a, aby znaleźć rozwiązanie minimalne: Na X 1
=2.5;
X 2
=4.5
otrzymujemy: Układ ma rozwiązanie w punkcie , tj. spełnione są warunki wystarczające dla ekstremum. Utwórzmy funkcję Lagrange'a, aby znaleźć maksymalne rozwiązanie: Warunki wystarczające na ekstremum: Na X 1
=0;
X 2
=2
otrzymujemy: System posiada również rozwiązanie, tj. spełnione są warunki wystarczające dla ekstremum. Odpowiedź: minimum funkcji celu osiąga się, gdy Dwóm przedsiębiorstwom przydzielono środki w wysokości D jednostki. Przy przydzielaniu pierwszego przedsiębiorstwa na rok X jednostek funduszy, które zapewnia dochód k 1
X jednostek oraz w przypadku przydzielenia ich drugiemu przedsiębiorstwu y jednostek funduszy, zapewnia dochód k 1
y jednostki. Stan środków na koniec roku dla pierwszego przedsiębiorstwa jest równy nx i dla drugiego Mój. Jak rozłożyć wszystkie środki na 4 lata, aby łączny dochód był jak największy? Rozwiąż problem stosując metodę programowania dynamicznego. i=8, k=1. A=2200; k1 =6; k2 = 1; n=0,2; m=0,5. Rozwiązanie: Cały okres 4 lat podzielony jest na 4 etapy, z których każdy wynosi jeden rok. Ponumerujmy etapy zaczynając od pierwszego roku. Niech X k i Y k będą środkami przyznanymi odpowiednio przedsiębiorstwom A i B w k-tym etapie. Wtedy suma X k + Y k = a k to suma środków wykorzystanych na k – tym etapie i pozostała część z poprzedniego etapu k – 1. W pierwszym etapie wykorzystywane są wszystkie przyznane środki i a 1 = 2200 jednostek . dochód, jaki uzyskamy na etapie k – przy przydziale jednostek X k i Y k wyniesie 6X k + 1Y k. niech maksymalny dochód uzyskany na ostatnich etapach począwszy od k – tego etapu będzie wynosić f k (a k) jednostek. Zapiszmy funkcjonalne równanie Bellmana wyrażające zasadę optymalności: niezależnie od stanu początkowego i rozwiązania początkowego, kolejne rozwiązanie musi być optymalne ze względu na stan uzyskany w wyniku stanu początkowego: Dla każdego etapu musisz wybrać wartość X k i wartość Yk=ak- Xk. Biorąc to pod uwagę, dochód znajdziemy na k-tym etapie: Równanie funkcjonalne Bellmana będzie wyglądało następująco: Rozważmy wszystkie etapy, zaczynając od ostatniego. (ponieważ maksimum funkcji liniowej osiąga się na końcu odcinka przy x 4 = a 4);
Podobne dokumenty
;
; 
;
; 
.
.
Zadanie nr 2
ó
ó 
Następnie 
; ; 
- minimalna wartość funkcji.
ó 
ó 
ó 
; ; maksimum funkcji celu osiąga się przy 
; .
Zadanie nr 3
