Nazywa się optymalną wartość funkcji celu. Rozwiązywanie problemów programowania liniowego metodą graficzną

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 rodzaju 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 do tego 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.

KONTROLA PRACY NAD DYSCYPLINĄ:

„METODY OPTYMALNYCH ROZWIĄZAŃ”

Opcja nr 8

1. Decydować metoda graficzna Problem programowania liniowego. Znajdź maksimum i minimum funkcji przy podanych ograniczeniach:

,

.

Rozwiązanie

Należy znaleźć minimalną wartość funkcji celu i maksymalną, w ramach systemu ograniczeń:

9x 1 +3x 2 ≥30, (1)

X 1 + x 2 ≤ 4, (2)

x 1 + x 2 ≤8, (3)

Skonstruujmy obszar rozwiązań dopuszczalnych, tj. Rozwiążmy układ nierówności graficznie. W tym celu konstruujemy każdą linię prostą i definiujemy półpłaszczyznę wyznaczoną przez nierówności (półpłaszczyzny są oznaczone liczbą pierwszą).

Przecięciem półpłaszczyzn będzie obszar, którego współrzędne punktów spełniają nierówności układu więzów problemu. Oznaczmy granice obszaru wielokąta rozwiązania.

Skonstruujmy prostą odpowiadającą wartości funkcji F = 0: F = 2x 1 +3x 2 = 0. Wektor gradientu, złożony ze współczynników funkcji celu, wskazuje kierunek minimalizacji F(X). Początek wektora to punkt (0; 0), koniec to punkt (2; 3). Przesuniemy tę linię równolegle. Ponieważ interesuje nas rozwiązanie minimalne, przesuwamy zatem prostą, aż dotknie ona najpierw wyznaczonego obszaru. Na wykresie ta linia prosta jest oznaczona linią przerywaną.

Prosty
przecina obszar w punkcie C. Ponieważ punkt C powstaje w wyniku przecięcia prostych (4) i (1), to jego współrzędne spełniają równania tych prostych:
.

Po rozwiązaniu układu równań otrzymujemy: x 1 = 3,3333, x 2 = 0.

Jak znaleźć minimalną wartość funkcji celu: .

Rozważmy funkcja docelowa zadania.

Skonstruujmy prostą odpowiadającą wartości funkcji F = 0: F = 2x 1 +3x 2 = 0. Wektor gradientu, złożony ze współczynników funkcji celu, wskazuje kierunek maksymalizacji F(X). Początek wektora to punkt (0; 0), koniec to punkt (2; 3). Przesuniemy tę linię równolegle. Ponieważ interesuje nas rozwiązanie maksymalne, przesuwamy zatem linię prostą aż do ostatniego dotknięcia wyznaczonego obszaru. Na wykresie ta linia prosta jest oznaczona linią przerywaną.

Prosty
przecina obszar w punkcie B. Ponieważ punkt B powstaje w wyniku przecięcia prostych (2) i (3), to jego współrzędne spełniają równania tych prostych:

.

Jak znaleźć maksymalną wartość funkcji celu: .

Odpowiedź:
I
.

2 . Rozwiąż zadanie programowania liniowego metodą simpleksową:

.

Rozwiązanie

Rozwiążmy problem bezpośredniego programowania liniowego metodą sympleksową, korzystając z tabeli sympleksowej.

Wyznaczmy minimalną wartość funkcji celu
pod następującymi warunkami-ograniczeniami:
.

Aby skonstruować pierwszy plan odniesienia, układ nierówności sprowadzamy do układu równań, wprowadzając dodatkowe zmienne.

W pierwszej nierówności znaczenia (≥) wprowadzamy zmienną podstawową X 3 ze znakiem minus. W drugiej nierówności znaczenia (≤) wprowadzamy zmienną podstawową X 4 . W 3. nierówności znaczenia (≤) wprowadzamy zmienną podstawową x 5 .

Wprowadźmy sztuczne zmienne : w pierwszej równości wprowadzamy zmienną X 6 ;

Aby zminimalizować problem, funkcję celu piszemy w następujący sposób: .

Za użycie sztucznych zmiennych wprowadzonych do funkcji celu nakładana jest tzw. kara M, czyli bardzo duża liczba dodatnia, która zwykle nie jest określona.

Powstałą bazę nazywa się sztuczną, a metodę rozwiązania nazywa się metodą sztucznej bazy.

Co więcej, zmienne sztuczne nie są związane z treścią problemu, ale pozwalają na skonstruowanie punktu wyjścia, a proces optymalizacji wymusza na tych zmiennych przyjęcie wartości zerowych i zapewnienie dopuszczalności rozwiązania optymalnego.

Z równań wyrażamy zmienne sztuczne: x 6 = 4-x 1 -x 2 +x 3, które podstawiamy do funkcji celu: lub.

Macierz współczynników
ten układ równań ma postać:
.

Rozwiążmy układ równań dla podstawowych zmiennych: X 6 , X 4 , X 5.

Zakładając, że zmienne wolne są równe 0, otrzymujemy pierwszą planie referencyjnym:

X1 = (0,0,0,2,10,4)

Rozwiązanie podstawowe nazywamy dopuszczalnym, jeżeli jest nieujemne.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6
X 4
X 5

Obecny plan odniesienia nie jest optymalny, ponieważ na linii indeksu znajdują się dodatnie współczynniki. Jako kolumnę wiodącą wybierzemy kolumnę odpowiadającą zmiennej x 2, ponieważ jest to największy współczynnik. Obliczmy wartości D I i spośród nich wybieramy najmniejszy: min(4:1, 2:2, 10:2) = 1.

Dlatego druga linia jest linią wiodącą.

Element rozstrzygający jest równy (2) i znajduje się na przecięciu kolumny wiodącej i wiersza wiodącego.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6
X 4
X 5

Tworzymy kolejną część tabeli simplex. Zamiast zmiennej x 4, plan 1 będzie zawierał zmienną x 2.

Wiersz odpowiadający zmiennej x 2 w planie 1 otrzymuje się poprzez podzielenie wszystkich elementów wiersza x 4 planu 0 przez element rozwiązujący RE = 2. W miejsce elementu rozdzielającego otrzymujemy 1. W pozostałych komórkach kolumny x 2 zapisujemy zera.

Zatem w nowym planie 1 wypełniony jest wiersz x 2 i kolumna x 2. Wszystkie pozostałe elementy nowego planu 1, w tym elementy wiersza indeksowego, określa reguła prostokąta.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6
X 2
X 5
		1 1/2 +1 1/2 M

Obecny plan odniesienia nie jest optymalny, ponieważ w wierszu indeksu znajdują się współczynniki dodatnie. Jako kolumnę wiodącą wybierzemy kolumnę odpowiadającą zmiennej x 1, ponieważ jest to największy współczynnik. Obliczmy wartości D I według wiersza jako iloraz dzielenia: i spośród nich wybieramy najmniejszy: min (3: 1 1 / 2, -, 8: 2) = 2.

Dlatego pierwsza linia jest linią wiodącą.

Element rozstrzygający jest równy (1 1/2) i znajduje się na przecięciu wiodącej kolumny i wiodącego rzędu.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6		1 1 / 2
X 2
X 5
		-1 1 / 2 +1 1 / 2 M

Tworzymy kolejną część tabeli simplex. Zamiast zmiennej x 6, plan 2 będzie zawierał zmienną x 1.

Otrzymujemy nową tabelę simplex:

		X 1	X 2	X 3	X 4	X 5	X 6
X 1
X 2
X 5

Wśród wartości ciągu indeksowego nie ma wartości dodatnich. Dlatego ta tabela określa optymalny plan rozwiązania problemu.

Ostateczna wersja tabeli simplex:

		X 1	X 2	X 3	X 4	X 5	X 6
X 1
X 2
X 5

Ponieważ w rozwiązaniu optymalnym nie ma zmiennych sztucznych (są one równe zeru), rozwiązanie to jest dopuszczalne.

Plan optymalny można zapisać następująco: x 1 = 2, x 2 = 2:.

Odpowiedź:
,
.

3. Firma Three Fat Men dostarcza konserwy mięsne z trzech magazynów zlokalizowanych w różnych częściach miasta do trzech sklepów. Zapasy konserw dostępnych w magazynach, wielkości zamówień sklepowych oraz stawki dostaw (w konwencjonalnych jednostkach pieniężnych) przedstawiono w tabeli transportu.

Znajdź plan transportu zapewniający najniższe koszty pieniężne (wykonaj początkowy plan transportu, stosując metodę „narożnika północno-zachodniego”).

Rozwiązanie

Sprawdźmy warunek konieczny i wystarczający rozwiązywalności problemu:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Warunek równowagi jest spełniony. Zaspokaja równe potrzeby. Dlatego model problemu transportu zamknięte.

Wprowadźmy początkowe dane do tabeli rozkładu.

Wymagania

Stosując metodę narożnika północno-zachodniego, skonstruujemy pierwszy plan odniesienia problemu transportowego.

Plan zaczyna się wypełniać od lewego górnego rogu.

Wymagany element to 4. Dla tego elementu zapasy wynoszą 300, wymagania wynoszą 250. Ponieważ minimum wynosi 250, odejmujemy to: .

			300 - 250 = 50
250 - 250 = 0

Wymagany element wynosi 2. Dla tego elementu zapasy wynoszą 50, wymagania wynoszą 400. Ponieważ minimum wynosi 50, odejmujemy to: .

			50 - 50 = 0
	400 - 50 = 350

Wymagany element to 5. Dla tego elementu zapasy wynoszą 300, wymagania wynoszą 350. Ponieważ minimum wynosi 300, odejmujemy to:

			300 - 300 = 0
	350 - 300 = 50

Element, którego szukasz to 3. Dla tego elementu zapasy wynoszą 200, wymagania wynoszą 50. Ponieważ minimum wynosi 50, odejmujemy to:

			200 - 50 = 150
	50 - 50 = 0

Wymagany element to 6. Dla tego elementu zapasy wynoszą 150, wymagania wynoszą 150. Ponieważ minimum wynosi 150, odejmujemy to:

			150 - 150 = 0
		150 - 150 = 0

Wymagania

Praca laboratoryjna nr 1. Rozwiązywanie problemów programowania liniowego

Cel pracy Zdobycie umiejętności rozwiązywania problemów programowania liniowego z wykorzystaniem metod graficznych, simpleksowych i Excel.

Problem programowania liniowego polega na badaniu sposobów znajdowania maksymalnych lub minimalnych wartości funkcji liniowej w obecności ograniczeń liniowych. Funkcja celu to funkcja, której wartość maksymalna lub minimalna została znaleziona. Zbiór wartości zmiennych, przy którym osiągane są wartości maksymalne lub minimalne, nazywany jest rozwiązaniem optymalnym (planem optymalnym), każdy inny zbiór wartości spełniający ograniczenia nazywany jest rozwiązaniem dopuszczalnym (planem dopuszczalnym).

Metoda rozwiązania geometrycznego I Przyjrzyjmy się problemom programowania liniowego na przykładzie.

Przykład. Znajdź maksymalną wartość funkcji celu L=2X 1 +2X 2 z zachowaniem określonych ograniczeń

Rozwiązanie. Skonstruujmy dziedzinę rozwiązań układu więzów, zamieniając znaki nierówności na dokładne znaki równości:

l 1: 3X 1 -2X 2 +6=0,

l 2: 3X 1 +X 2 -3=0,

l 3:X 1 -3=0.

DZ

2 0 1 3 X 1

(l 1) (l 3)

Prosty l 1 dzieli płaszczyznę X O Na na dwie półpłaszczyzny, z których należy wybrać tę, która spełnia pierwszą nierówność układu (3). Aby to zrobić, weźmy t. O(0; 0) i podstaw go do nierówności. Jeśli to prawda, to należy zacienić półpłaszczyznę od linii prostej, w której znajduje się tzw. O(0; 0). Zrób to samo z liniami prostymi. l 2 i l 3. Dziedziną rozwiązań nierówności (3) jest wielokąt ABCD. Dla każdego punktu na płaszczyźnie funkcja L przyjmuje stałą wartość L=L 1. Zbiór wszystkich bieżących punktów jest linią prostą L=C 1 X 1 +C 2 X 2 (w naszym przypadku L=2X 1 +2X 2), prostopadle do wektora Z(Z 1 ;Z 2) (Z(2; 2)), pochodzące ze źródła. Jeśli ta linia zostanie przesunięta w dodatnim kierunku wektora Z, to funkcja celu L wzrośnie, w przeciwnym razie zmniejszy się. Zatem w naszym przypadku linia prosta przy wyjściu z wielokąta ABCD decyzje będą przechodzić przez tzw W(3; 7.5), a zatem m.in. W funkcja celu przyjmuje wartość maksymalną, tj. L maks. =2ּ3+2ּ7,5=21. Podobnie ustala się, że minimalna wartość, jaką przyjmuje funkcja, wynosi D(1; 0) i L min =2ּ1+2ּ0=2.

Algorytm metody simpleksowej do rozwiązywania problemu programowania liniowego jest następujący.

1. Zadanie ogólne Programowanie liniowe sprowadza się do problemu kanonicznego (więzy zawierają znaki równości) poprzez wprowadzenie tylu zmiennych pomocniczych, ile jest nierówności w układzie więzów.

2. Funkcja celu wyrażana jest za pomocą zmiennych podstawowych i pomocniczych.

3. Kompilowana jest pierwsza tabela simplex. Do podstawy wpisuje się zmienne, w stosunku do których dozwolony jest system ograniczeń (najlepiej jako podstawę przyjąć zmienne pomocnicze). Pierwszy wiersz tabeli zawiera listę wszystkich zmiennych i kolumnę zawierającą terminy dowolne. Współczynniki funkcji celu o przeciwnych znakach zapisano w ostatnim wierszu tabeli.

4. Każda tablica simplex daje rozwiązanie problemu programowania liniowego: zmienne wolne są równe zero, zmienne podstawowe są równe odpowiednio członom wolnym.

5. Kryterium optymalności to brak elementów ujemnych w ostatnim wierszu tabeli dla rozwiązania problemu maksymalnego i elementów dodatnich dla rozwiązania minimalnego.

6. Aby ulepszyć rozwiązanie, należy przejść z jednej tabeli simpleksowej na drugą. Aby to zrobić, znajdź w poprzedniej tabeli kluczową kolumnę, która odpowiada najmniejszemu elementowi ujemnemu w ostatnim wierszu tabeli w problemie maksymalnym i największemu dodatniemu współczynnikowi w problemie minimalnym. Następnie znajduje się kluczowy wiersz odpowiadający minimalnemu stosunkowi wolnych terminów do odpowiednich dodatnich elementów kolumny kluczowej. Na przecięciu kolumny klucza i wiersza klucza znajduje się kluczowy element.

7. Wypełnianie poniższej tabeli simplex rozpoczynamy od wypełnienia podstawy: z podstawy wyprowadzamy zmienną odpowiadającą wierszowi kluczowemu, a w jej miejsce wpisujemy zmienną odpowiadającą kolumnie kluczowej. Elementy poprzedniego ciągu klucza uzyskuje się dzieląc poprzedni element przez klucz. Elementy poprzedniej kolumny klucza stają się zerami, z wyjątkiem elementu klucza, którym jest jeden. Wszystkie pozostałe elementy są obliczane przy użyciu reguły prostokąta:

8. Transformację tabel simpleksowych przeprowadza się aż do uzyskania planu optymalnego.

Przykład. Znajdź maksymalną wartość funkcji
, jeśli zmienne
spełniają system ograniczeń:

Rozwiązanie. 1. Wprowadź nowe zmienne
, za pomocą którego nierówności układu przekształcamy na równania:

Zmieniamy znak współczynników funkcji celu lub zapisujemy go w postaci
. Wypełniamy pierwszą tabelę simplex, w linii zerowej piszemy X 1 ,X 2 i (bezpłatne kursy). W kolumnie zerowej - X 3 ,X 4 ,X 5 i F. Wypełniamy tę tabelę, korzystając z powstałego układu równań i przekształconej funkcji celu.

Sprawdzamy kryterium optymalności, aby znaleźć wartość maksymalną: w ostatniej linii wszystkie współczynniki muszą być dodatnie. Kryterium to nie jest spełnione, zatem przechodzimy do zestawiania drugiej tabeli.

2. Znajdź element rozstrzygający pierwszej tabeli w następujący sposób. Spośród elementów ostatniego rzędu wybieramy największy ujemny współczynnik wielkości (to jest -3) i drugą kolumnę przyjmujemy jako rozdzielczą. Jeśli wszystkie współczynniki kolumny są dodatnie, to
.

Aby wyznaczyć rząd rozdzielczy, dzielimy wolne współczynniki na odpowiednie elementy kolumny rozdzielczej i wybieramy stosunek minimalny, nie bierzemy jednak współczynników ujemnych. Mamy
, druga linia jest zezwalająca. Przecięcie rozdzielającego wiersza i kolumny daje rozstrzygający element - jest to 3.

3. Wypełnij drugą tabelę jednostronną. Zmienne, na przecięciu których otrzymujemy element rozwiązujący, są zamieniane, tj. I . Zastępujemy element rozwiązujący jego odwrotnością, tj. na. Elementy rozwiązującego wiersza i kolumny (z wyjątkiem elementu rozwiązującego) są podzielone na element rozwiązujący. W tym przypadku zmieniamy znak współczynników kolumny rozdzielczości.

Pozostałe elementy drugiej tabeli uzyskujemy stosując regułę prostokąta z elementów pierwszej tabeli. Aby komórka została wypełniona i komórka z elementem rozdzielającym, tworzymy prostokąt. Następnie od elementu wypełnianej komórki odejmujemy iloczyn elementów pozostałych dwóch wierzchołków podzielony przez element rozwiązujący. Pokażmy obliczenia wykorzystując tę ​​regułę do wypełnienia pierwszego wiersza drugiej tabeli:

.

Kontynuujemy wypełnianie tabel według tych zasad, aż do spełnienia kryterium. Do naszego zadania mamy jeszcze dwie tabele.

	X 1	X 4					X 3	X 2
X 3						X 1
X 2						X 2
X 5						X 5

4. Wynik wykonania tego algorytmu zapisuje się następująco. W tabeli końcowej element na przecięciu wiersza
i kolumna B, daje maksymalną wartość funkcji celu. W naszym przypadku
. Wartości zmiennych wiersza są równe wolnym współczynnikom. Dla naszego problemu mamy
.

Istnieją inne sposoby kompilowania i wypełniania tabel jednostronnych. Przykładowo dla etapu 1 wszystkie zmienne i wolne współczynniki zapisywane są w wierszu zerowym tabeli. Po znalezieniu elementu rozwiązującego, stosując te same zasady w poniższej tabeli, zastępujemy zmienną w kolumnie zerowej, ale nie w wierszu. Wszystkie elementy linii zezwalającej dzielimy przez element dopuszczający i zapisujemy je w nowej tabeli. Dla pozostałych elementów kolumny rozdzielczości zapisujemy zera. Następnie wykonujemy określony algorytm z uwzględnieniem tych reguł.

Rozwiązując zadanie programowania liniowego dla minimum, w ostatnim wierszu wybierany jest największy dodatni współczynnik i podany algorytm jest wykonywany do momentu, gdy w ostatnim wierszu nie będzie żadnych dodatnich współczynników.

Rozwiązywanie problemów programowania liniowego za pomocą programu Excel odbywa się w następujący sposób.

Aby rozwiązać problemy z programowaniem liniowym, użyj dodatku Solution Search. Najpierw musisz upewnić się, że ten dodatek jest obecny na karcie Dane w grupie Analiza (dla 2003 r. zobacz Narzędzia). Jeżeli brakuje polecenia Znajdź rozwiązanie lub grupy Analiza, należy pobrać ten dodatek.

Aby to zrobić, kliknij opcję Plik pakietu Microsoft Office (2010), a następnie kliknij przycisk Opcje programu Excel. W wyświetlonym oknie Opcje programu Excel wybierz pole Dodatki po lewej stronie. Po prawej stronie okna należy ustawić wartość pola Kontrola na Dodatki Excel, kliknąć przycisk „Przejdź”, który znajduje się obok tego pola. W oknie Dodatki zaznacz pole wyboru Znajdź rozwiązanie i kliknij OK. Następnie możesz pracować z zainstalowanym dodatkiem Search for Solutions.

Przed wywołaniem funkcji Search for a Solution należy przygotować w arkuszu dane do rozwiązania zadania programowania liniowego (z modelu matematycznego):

1) Określ komórki, w których zostanie umieszczony wynik rozwiązania, w pierwszym wierszu wpisujemy zmienne i funkcję celu. Nie wypełniamy drugiej linii (komórki zmienne) w tych komórkach uzyskany zostanie optymalny wynik. W kolejnym wierszu należy wprowadzić dane dla funkcji celu, a w kolejnym układ ograniczeń (współczynniki dla niewiadomych). Prawa strona wprowadza się ograniczenia (wolne współczynniki), pozostawiając wolną komórkę po zapisaniu współczynników systemu ograniczeń.

2) Wprowadź zależność od komórek zmiennych dla funkcji celu oraz zależność od komórek zmiennych dla lewych części układu więzów w pozostałych wolnych komórkach. Aby wprowadzić wzory zależności, wygodnie jest użyć funkcji matematycznej SUMPRODUCT.

Następnie należy skorzystać z dodatku Wyszukaj rozwiązanie. Na karcie Dane w grupie Analiza wybierz opcję Znajdź rozwiązanie. Pojawi się okno dialogowe Wyszukaj rozwiązanie, które należy wypełnić w następujący sposób:

1) W polu „Optymalizuj funkcję celu” określ komórkę zawierającą funkcję celu (komórka ta musi zawierać wzór na funkcję celu). Wybierz opcję optymalizacji wartości komórki docelowej (maksymalizacja, minimalizacja):

2) W polu „Zmiana komórek zmiennych” wprowadź komórki, które chcesz zmienić. W kolejnym polu „Zgodnie z ograniczeniami” wprowadź określone ograniczenia za pomocą przycisku „Dodaj”. W wyświetlonym oknie wprowadź komórki zawierające formuły układu więzów, wybierz znak ograniczenia i wartość ograniczenia (wolny współczynnik):

3) Zaznacz pole wyboru „Uczyń zmienne nieograniczone nieujemnymi”. Wybierz metodę rozwiązania „Poszukiwanie rozwiązań problemów liniowych metodą simpleksową”. Po kliknięciu przycisku „Znajdź rozwiązanie” rozpoczyna się proces rozwiązywania problemu. W rezultacie pojawia się okno dialogowe „Wyniki wyszukiwania rozwiązania” i początkowa tabela z wypełnionymi komórkami dla wartości zmiennych i optymalnej wartości funkcji celu.

Przykład. Rozwiąż problem programowania liniowego za pomocą dodatku Excel Solution: znajdź maksymalną wartość funkcji
pod ograniczeniami

,

;

,
.

Rozwiązanie. Aby rozwiązać nasz problem, wykonajmy podany algorytm w arkuszu Excela. Wprowadź dane początkowe w formie tabeli

Wprowadzamy zależności dla funkcji celu i układu ograniczeń. Aby to zrobić, wpisz formułę =SUMPRODUCT(A2:B2;A3:B3) w komórce C2. Odpowiednio w komórkach C4 i C5 formuły są następujące: =SUMPRODUCT(A2:B2,A4:B4) i =SUMPRODUCT(A2:B2,A5:B5). W rezultacie otrzymujemy stół.

Uruchom polecenie „Wyszukaj rozwiązanie” i wypełnij okno Wyszukaj rozwiązanie, które pojawi się w następujący sposób. W polu „Optymalizuj funkcję celu” wpisz komórkę C2. Wybierz optymalizację wartości komórki docelowej „Maksymalna”.

W polu „Zmiana komórek zmiennych” wprowadź zmieniające się komórki A2:B2. W polu „Zgodnie z ograniczeniami” wprowadź określone ograniczenia za pomocą przycisku „Dodaj”. Odniesienia do komórki $C$4:$C$5 Odniesienia do ograniczeń =$D$4:$D$5 pomiędzy nimi znak<= затем кнопку «ОК».

Zaznacz pole wyboru „Uczyń zmienne nieograniczone nieujemnymi”. Wybierz metodę rozwiązania „Poszukiwanie rozwiązań problemów liniowych metodą simpleksową”.

Kliknięcie przycisku „Znajdź rozwiązanie” rozpoczyna proces rozwiązywania problemu. W rezultacie pojawia się okno dialogowe „Wyniki wyszukiwania rozwiązania” i oryginalna tabela z wypełnionymi komórkami dla wartości zmiennych i optymalną wartością funkcji celu.

W oknie dialogowym „Wyniki wyszukiwania rozwiązań” zapisz wynik x1=0,75, x2=0,75, F=1,5 - równy maksymalnej wartości funkcji celu.

Zadania do samodzielnej pracy

Ćwiczenie 1. Korzystając z metod graficznych, simpleksowych i narzędzi Excela, znajdź maksymalną i minimalną wartość funkcji F(X) w ramach danego systemu ograniczeń.

1. F(X)=10X 1 +5X 2 2. F(X)=3X 1 -2X 2

3. F(X)=3X 1 +5X 2 4. F(X)=3X 1 +3X 2

5. F(X)=4X 1 -3X 2 6. F(X)=2X 1 -X 2

7. F(X)=-2X 1 +4X 2 8. F(X)=4X 1 -3X 2

9. F(X)=5X 1 +10X 2 10. F(X)=2X 1 +X 2

11. F(X)=X 1 +X 2 12. F(X)=3X 1 +X 2

13. F(X)=4X 1 +5X 2 14. F(X)=3X 1 +2X 2

15. F(X)=-X 1 -X 2 16. F(X)=-3X 1 -5X 2

17. F(X)=2X 1 +3X 2 18. F(X)=4X 1 +3X 2

19. F(X)=-3X 1 -2X 2 20. F(X)=-3X 1 +4X 2

21. F(X)=5X 1 -2X 2 22. F(X)=-2X 1 +3X 3

23. F(X)=2X 1 +3X 2 24. F(X)=4X 1 +3X 2

25. F(X)=-3X 1 -2X 2 26. F(X)=-3X 1 +4X 2

27. F(X)=-2X 1 +4X 2 28. F(X)=4X 1 -3X 2

29. F(X)=-X 1 -X 2 30. F(X)=-3X 1 -5X 2

Pytania kontrolne.

1. Jakie problemy nazywane są problemami programowania liniowego?

2. Podaj przykłady problemów programowania liniowego.

3. Jak rozwiązuje się problem programowania liniowego metodą graficzną?

4. Opisać algorytm metody simpleksowej do rozwiązywania problemów programowania liniowego.

5. Opisać algorytm rozwiązywania problemów programowania liniowego w programie Excel.

Federalna Agencja Edukacji

Państwowa budżetowa instytucja edukacyjna

wyższe wykształcenie zawodowe

„Państwowy Uniwersytet Techniczny w Omsku”

OBLICZENIA I PRACY GRAFICZNE

przez dyscyplinę”TEORIA OPTYMALNEJ KONTROLI »

na temat "METODY OPTYMALIZACYJNE I BADANIA OPERACYJNE »

opcja 7

Zakończony:

student korespondencyjny

Grupa IV roku ZA-419

Pełna nazwa: Kuzhelev S.A.

Sprawdzony:

Devyaterikova M. V.

Omsk – 2012
^

Zadanie 1. Graficzna metoda rozwiązywania problemów programowania liniowego.

7) 7X 1 + 6X 2 → maks 20X 1 + 6X 2 ≤ 15 16X 1 − 2X 2 ≤ 18 8X 1 + 4X 2 ≤ 20 13X 1 + 3X 2 ≤ 4 X 1 , X 2 ≥ 0.

Krok 1: Konstruowanie obszaru wykonalnego

Warunki nieujemności zmiennych i kwadratów ograniczają zakres ich dopuszczalnych wartości do pierwszej ćwiartki. Każde z pozostałych czterech ograniczeń nierówności modelu odpowiada pewnej półpłaszczyźnie. Przecięcie tych półpłaszczyzn z pierwszą ćwiartką tworzy zbiór możliwych rozwiązań problemu.

Pierwsze ograniczenie modelu ma postać . Zastępując w nim znak ≤ znakiem =, otrzymujemy równanie . Na ryc. 1.1 wyznacza linię prostą (1), która dzieli płaszczyznę na dwie półpłaszczyzny, w tym przypadku nad linią i pod nią. Aby wybrać, który z nich spełnia nierówność , podstaw do niego współrzędne dowolnego punktu nie leżącego na danej linii (na przykład początek X 1 = 0, X 2 = 0). Ponieważ otrzymaliśmy prawidłowe wyrażenie (20 0 + 6 0 = 0 ≤15), to półpłaszczyzna zawierająca początek współrzędnych (oznaczona strzałką) spełnia nierówność. W przeciwnym razie kolejny półpłatowiec.

Podobnie postępujemy z pozostałymi ograniczeniami problemu. Przecięcie wszystkich skonstruowanych półpłaszczyzn z formami pierwszej ćwiartki ABCD(patrz ryc. 1). To jest możliwy obszar problemu.

Krok 2. Rysowanie linii poziomu Linia poziomu Funkcja celu to zbiór punktów na płaszczyźnie, w których funkcja celu przyjmuje wartość stałą. Taki zbiór jest dany równaniem F ( X) = konst. Połóżmy np. konst = 0 i narysuj linię na poziomie F ( X) = 0, tj. w naszym przypadku linia prosta 7 X 1 + 6X 2 = 0.

Linia ta przechodzi przez początek układu współrzędnych i jest prostopadła do wektora. Wektor ten jest gradientem funkcji celu w punkcie (0,0). Gradient funkcji jest wektorem wartości pochodnych cząstkowych danej funkcji w danym punkcie. W przypadku problemu LP pochodne cząstkowe funkcji celu są równe współczynnikom CI, J = 1 , ..., N.

Gradient pokazuje kierunek najszybszego wzrostu funkcji. Przesuwanie linii poziomu funkcji celu F ( X) = konst. prostopadle do kierunku gradientu, znajdujemy ostatni punkt, w którym przecina się on z obszarem. W naszym przypadku jest to punkt D, który będzie punktem maksymalnym funkcji celu (patrz rys. 2)

Leży na przecięciu prostych (2) i (3) (patrz rys. 1) i określa rozwiązanie optymalne.

^ Należy pamiętać, że jeśli chcemy znaleźć minimalną wartość funkcji celu, linię poziomu przesuwamy w kierunku przeciwnym do kierunku gradientu.

^ Krok 3. Wyznaczenie współrzędnych punktu maksymalnego (minimalnego) i optymalnej wartości funkcji celu

Aby znaleźć współrzędne punktu C, należy rozwiązać układ składający się z odpowiednich równań bezpośrednich (w tym przypadku równań 2 i 3):

16X 1 − 2X 2 ≤ 18

8X 1 + 4X 2 ≤ 20

Otrzymujemy rozwiązanie optymalne = 1,33.

^ Optymalna wartość funkcji celu F * = F (X*) = 7 * 0 + 6 * 1,33 = 7,8