3179027796

Elementy Badań Operacyjnych

2. Program liniowy

Programem liniowym (PL) nazywamy zadanie o następującej postaci:

c_lx_l+c₂x₂-\—I-c_Nx_N —> max funkcja celu (funkcja kryterium) ct_nx_x + a_l2x₂ +... + a_lNx_N < Z>, a_2ix, + a₂₂x₂ +...+a_2Nx_N < b₂

>    warunki ograniczające    (1)

a_Mlx_l + a_M2x₂ +... + a_mx_N < b_KI I x,, x₂, • • •, x_N > 0 warunki brzegowe lub

c_lx_l+c₂x₂+---+c_Nx_N —> min funkcja celu (funkcja kryterium) a_nx₂ + a_l2x₂ +... + a_lNx_N > b_x a_2lx_l+a₂₂x₂+... + a_2Nx_N >b₂

>    warunki ograniczające    (2)

^aMl^Xl + ^aM₂X₂ + • • • + d_mX_M > by J

x,,x₂,-",x_A, > 0 warunki brzegowe

Program liniowy (1) nazywamy standardowym zadaniem maksymalizacji a program (2) standardowym zadaniem minimalizacji.

W programie tym występują pewne wielkości dane — parametry: aj, b„ Cj (i = 1,2 j = \,2,...,N) oraz wielkości, które należy ustalić — zmienne decyzyjne: Xj (j = 1,2

Elementami każdego programu liniowego są: warunki ograniczające, warunki brzegowe i funkcja celu. Warunki ograniczające to układ równań lub nierówności opisujących warunki działania. W konkretnych sytuacjach decyzyjnych nierówności w warunkach ograniczających mogą oczywiście mieć przeciwny zwrot, mogą to także być równości. W warunkach brzegowych zakłada się, że zmienne decyzyjne, które są pewnymi wielkościami ekonomicznymi będą liczbami nieujemnymi. Funkcja celu umożliwia wybór optymalnego przy istniejących ograniczeniach wariantu planu; może być maksymalizowana lub minimalizowana.

Zbiór wartości zmiennych decyzyjnych spełniający warunki ograniczające i warunki brzegowe nazywamy rozwiązaniem dopuszczalnym PL. Rozwiązań dopuszczalnych jest zwykle wiele. Spośród nich wybiera się takie, dla którego (których) funkcja celu przyjmuje wartość ekstremalną (w zależności od sytuacji maksymalną lub minimalną). Jest to rozwiązanie optymalne.

Standardowy program liniowy może być odpowiednio także zapisany w notacji macierzowej :

c^Tx —> max    c^Tx —> min

Ax < b    Ax > b    (3)

x > 0    x > 0

gdzie: A jest macierzą współczynników stojących po lewej stronie układu warunków ograniczających (o wymiarach MxN), b jest wektorem (kolumnowym, o wymiarach Mxl) wyrazów wolnych układu warunków ograniczających, c^T jest wektorem wierszowym (o wymiarach 1 xN) współczynników funkcji celu i x jest wektorem zmiennych decyzyjnych (o wymiarach

Nx 1).

Antoni Goryl, Anna Walkosz: Programowanie liniowe strona 4

Wyszukiwarka

Podobne podstrony:
predykcji. 5. Wybrane elementy badań operacyjnych - programowanie liniowe: Sformułowanie zadania
Elementy Badań OperacyjnychElementy badań operacyjnych - programowanie liniowe 1.
Elementy Badań Operacyjnych Zatem, rozwiązanie programu liniowego polega na wyznaczeniu optymalnych
Statystyka z elementami badań operacyjnych BADANIA OPERACYJNE - programowanie
Elementy Badań Operacyjnych X = 200, x2 = 600, lub *i = 400, x2 = 200. Przy takich strukturach produ
Elementy Badań Operacyjnych Jak łatwo sprawdzić, posługując się np. metodą geometryczną, rozwiązanie
Elementy Badań Operacyjnych są wartości X2* = 300,4; x^* = 149,7, a F(xi*, X2*, *3*) = 36-0 + 54-300
Elementy Badań Operacyjnych gdzie, powtórzmy raz jeszcze, poszczególne parametry oznaczają: ci]—
Elementy Badań Operacyjnych F(x„...,x5) = 8x, +2x2 +12*3 +6x4 + 0x5 -> min 5x, +4x2 + 2x3 +x4 >
Elementy Badań Operacyjnych funkcji celu PP, jeżeli wyraz wolny w /-tym ograniczeniu wzrośnie o 1. Z
Elementy Badań Operacyjnych Tablica 4 Mieszanka Zawartość składnika w 1 kg mieszanki Cena 1 kg
Elementy Badań Operacyjnych Tablica 5 Stop % zawartość pierwiastka w stopie Cena 1 tony stopu
Elementy Badań Operacyjnych Do produkcji żeliwa należy zatem użyć 200 ton stopu S2 i 1100 ton stopu
Elementy Badań Operacyjnych Model zagadnienia transportowego zamkniętego ma postać: M N J ,J Jciixu
Elementy Badań Operacyjnych 1. Wprowadzenie Sprawność zarządzania przedsięwzięciami i firmami jest
Elementy Badań Operacyjnych Funkcja celu: Model OZT M N =m n OZT sprowadzone do ZZT M
Elementy Badań Operacyjnych Jest to konieczne, zanim rozwiązanie zostanie zastosowane w praktyce. Ch
Elementy Badań Operacyjnych Uj — minimalna ilość j-tego wyrobu jaką trzeba wyprodukować, v, —

więcej podobnych podstron