WSEI ELEMENTY PROGRAMOWANIA LINIOWEGO, uczelnia WSEI Lublin, UCZELNIA WSEI 2, matma


ELEMENTY PROGRAMOWANIA LINIOWEGO.

1. PODSTAWOWE POJĘCIA I TWIERDZENIA

Programowanie liniowe zajmuje się budową i rozwiązywaniem liniowych modeli decyzyjnych z określonym kryterium optymalności .

Ogólny zapis takiego modelu można przedstawić następująco: wyznaczyć wartość największą albo najmniejszą funkcji :

(1) 0x01 graphic

przy warunkach:

(2) 0x01 graphic

(3) 0x01 graphic
.

Funkcję liniową 0x01 graphic
nazywamy funkcją celu bądź funkcją kryterium.

Zmienne 0x01 graphic
nazywamy zmiennymi decyzyjnymi a wielkości 0x01 graphic
, j = 1, …,n,

0x01 graphic
i = 1,…,m , j = 1,…,n , oraz 0x01 graphic
, 0x01 graphic
nazywamy parametrami modelu.

Warunki (2) nazywamy warunkami ograniczającymi , zaś warunki (3) - warunkami brzegowymi .

Występowanie warunków brzegowych na ogół jest związane z określonym charakterem zagadnień, np. wielkość produkcji pewnego wyroby nie może być ujemna .

DEFINICJA 1. Zbiór wszystkich układów liczb rzeczywistych 0x01 graphic
spełniający warunki (2) i (3) nazywamy zbiorem rozwiązań dopuszczalnych i oznaczamy go symbolem X .

DEFINICJA 2. Rozwiązaniem optymalnym nazywamy te układy 0x01 graphic
,

tzn. te rozwiązania dopuszczalne, dla których funkcja celu osiąga swoją wartość największą ( najmniejszą ) .

Ogólny schemat postępowania przy rozwiązywaniu zadań programowania liniowego jest następujący:

  1. budowa modelu matematycznego postawionego zadania,

  2. rozwiązanie modelu,

  3. weryfikacja i interpretacja otrzymanych wyników.

Opracowane metody rozwiązywania zadań programowania liniowego opierają się na następujących twierdzeniach:

TWIERDZENIE 1.

Zbiór rozwiązań dopuszczalnych zadania programowania liniowego jest zbiorem domkniętym, wypukłym, o skończonej liczbie wierzchołków (niekoniecznie ograniczonym).

TWIERDZENIE 2.

Funkcja liniowa określona na zbiorze domkniętym ograniczonym, wypukłym, o skończonej liczbie wierzchołków osiąga swoją wartość największą ( najmniejszą ) na brzegu tego zbioru .

TWIERDZENIE 3. ( Weierstrassa ) .

Funkcja liniowa określona na domkniętym zbiorze wypukłym, o skończonej liczbie wierzchołków osiąga swoją wartość największą ( najmniejszą ) w wierzchołkach tego zbioru .

TWIERDZENIE 4.

Jeżeli funkcja liniowa określona na zbiorze wypukłym , domkniętym o skończonej liczbie wierzchołków osiąga swoją wartość największą ( najmniejszą ) w dwóch punktach wierzchołkowych, to tę wartość osiąga również na odcinku łączącym te punkty.

Podstawowymi sposobami rozwiązywania zadań programowania liniowego są :

  1. sposób graficzny,

  2. algorytm simpleks,

  3. algorytm transportowy.

Istnieją pewne ogólne zasady budowy modeli zadań programowania matematycznego.

Należą do nich :

  1. określenie wielkości, które będą zmiennymi decyzyjnymi modelu ,

  2. sformułowanie kryterium działalności oraz znalezienia jego matematycznej postaci ,

  3. uwzględniając treść i charakter zadania sformułowanie i zapisanie w postaci nierówności bądź równań warunków ograniczających naszą działalność .

  1. METODA GRAFICZNA ROZWIĄZYWANIA ZADAŃ PROGRAMOWANIA

LINIOWEGO

Jest to sposób otrzymania rozwiązania zadania programowania liniowego w przypadku, gdy w modelu występują tylko dwie zmienne decyzyjne, bądź dany model można sprowadzić do zadania o dwóch zmiennych decyzyjnych.

Idea metody graficznej jest następująca :

  1. wyznaczamy zbiór rozwiązań dopuszczalnych rozwiązując graficznie układ nierówności bądź równań ,

  2. znajdujemy rozwiązanie optymalne, które zgodnie z twierdzeniem 3 i 4 , znajdować się będzie w którymś z wierzchołków , bądź na brzegu zbioru rozwiązań dopuszczalnych.

PRZYKŁAD 1.

Pewien zakład produkuje dwa wyroby A i B . Do produkcji tych wyrobów potrzebne są surowce 0x01 graphic
. Nakłady surowców potrzebne do wyprodukowania jednostki każdego z wyrobów , zasoby surowców i zyski jednostkowe z sprzedaży tych wyrobów podane są w poniższej tabeli:

0x08 graphic
wyroby

surowce

A

B

0x08 graphic
zasoby

surowców

0x01 graphic

3

1

18

0x01 graphic

2

4

40

0x01 graphic

3

2

24

zyski jednostkowe

2

3

Należy ustalić plan produkcji zapewniający maksymalny zysk .

ROZWIĄZANIE

Zmiennymi decyzyjnymi w tym przypadku będą:

0x01 graphic
- planowana liczba jednostek wyrobu A,

0x01 graphic
- planowana liczba jednostek wyrobu B , 0x01 graphic
.

Funkcja celu : zysk 0x01 graphic
.

Warunki ograniczające :

0x01 graphic

Warunki brzegowe : 0x01 graphic
.

Zbiorem rozwiązań dopuszczalnych tego modelu jest zbiór punktów 0x01 graphic
płaszczyzny spełniających warunki 0x01 graphic
oraz warunki brzegowe . Zauważmy , że na płaszczyźnie każdy

z tych warunków określa odpowiednią półpłaszczyznę . Wobec tego znalezienie zbioru rozwiązań dopuszczalnych sprowadza się do graficznego rozwiązania układu

nierówności ( * ) . Punkty będące wierzchołkami tego zbioru (wielokąta) wyznaczamy rozwiązując układy równań:

0x01 graphic
; 0x01 graphic

oraz znajdując punkt przecięcia prostej 0x01 graphic
z osią 0Y i prostej 0x01 graphic
z osią 0X.

y Wierzchołki tego wielokąta to punkty:

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
D(0,10) C(2,9) 0x01 graphic

0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic
B(4,6)

0x08 graphic
0x08 graphic

0x08 graphic

0x08 graphic
X

A(6,0)

0x08 graphic
O(0,0) x

Rysunek 1.

Zapiszemy w tabeli wartości funkcji celu dla poszczególnych punktów wierzchołkowych:

Punkt

Współrzędne

Wartość funkcji celu

0x01 graphic

x

y

0x08 graphic
0

A

B

C

D

0

6

4

2

0

0

0

6

9

10

0

0x01 graphic

0x01 graphic

0x01 graphic

20x01 graphic

Jak widać, funkcja celu osiąga wartość największą równą 31 w punkcie C ( 2,9 ) .

Zatem optymalny program produkcyjny jest następujący:

należy wyprodukować 2 jednostki wyrobu A oraz 9 jednostek wyroby B .

PRZYKŁAD 2.

Gospodarstwo rolne prowadzi hodowlę drobiu, stosując dwa produkty paszowe A i B . Dla właściwej hodowli zwierzęta powinny otrzymywać (na dobę) odpowiednie ilości potrzebnych składników odżywczych (witaminy,proteiny, itp.), które są podane w poniższej tabelce.

Przyjmują, że koszt jednostki produktu A jest równy 20 zł , a że koszt jednostki produktu B jest równy 40 zł, podać jaka struktura żywienia zapewni najmniejszy dobowy koszt hodowli.

Składniki

odżywcze

Zawartość składników

w produkcie

Minimalna

ilość

składnika

A

B

0x01 graphic

36

6

108

0x01 graphic

3

12

36

0x01 graphic

20

10

100

ROZWIĄZANIE

Zmiennymi decyzyjnymi w tym przypadku będą:

0x01 graphic
- planowana liczba jednostek paszy A,

0x01 graphic
- planowana liczba jednostek paszy B .

Funkcja celu : dobowy koszt hodowli: 0x01 graphic
.

Warunki ograniczające :

0x01 graphic

Warunki brzegowe : 0x01 graphic
.

Zbiorem rozwiązań dopuszczalnych tego modelu jest zbiór punktów 0x01 graphic
płaszczyzny spełniających warunki 0x01 graphic
oraz warunki brzegowe . Zauważmy , że na płaszczyźnie każdy

z tych warunków określa odpowiednią półpłaszczyznę . Wobec tego znalezienie zbioru rozwiązań dopuszczalnych sprowadza się do graficznego rozwiązania układu

nierówności ( * ) . Punkty będące wierzchołkami tego zbioru (wielokąta) wyznaczamy rozwiązując układy równań:

0x01 graphic
; 0x01 graphic
,

oraz znajdując punkt przecięcia prostej 0x01 graphic
z osią 0Y i prostej 0x01 graphic
z osią 0X.

Wierzchołki tego zbioru: 0x01 graphic
.

0x08 graphic

Zapiszemy w tabeli wartości funkcji celu dla poszczególnych punktów wierzchołkowych:

Punkt

Współrzędne

Wartość funkcji celu

0x01 graphic

x

y

0x08 graphic

A

B

C

D

12

4

2

0

0

2

6

18

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

Jak widać, funkcja celu osiąga wartość najmniejszą równą 160 w punkcie 0x01 graphic
.

Zatem najmniejszy dobowy koszt hodowli zapewni kupno 4 jednostek paszy A oraz 2 jednostek paszy B.

Opracował: dr Franciszek Bogowski

5



Wyszukiwarka

Podobne podstrony:
CIĄGI, uczelnia WSEI Lublin, UCZELNIA WSEI 2, matma
Ekonometria modele, uczelnia, Programowanie Liniowe
instrukacja do programów profilaktycznych, ^v^ UCZELNIA ^v^, ^v^ Pedagogika, promocja zdrowia z arte
1.Opis programu CorelDRAW, ^v^ UCZELNIA ^v^, ^v^ Pedagogika, promocja zdrowia z arteterapią i socjot
Dobór naddatków na obróbkę elementu odlewanego - Projekt, Uczelnia, Technologia budowy maszyn
Modułowy program nauczania, uczelnia, Pakiet edukacyjny
Elementy rachunku macierzowego, uczelnia
Wstęp-ADM-Zaoczna-program i zasady2005, Uczelnia, Licencjat
Karta programowa czysta, Uczelnia, Obróbka Ubytkowa, Materiały pomocnicze
Elementy rachunku wyrównawczego, uczelnia, BL, Geodezja, zagadnienia z geodezji
Opracowanie Programowanie liniowe metoda sympleks
BO WYK2 Program liniowe optymalizacja
programowanie liniowe teoria
PL (programowanie liniowe), semestr 8, Matematyka, Teoria i praktyka decyzji ekonomicznych
konspekt cw 3 1 programowanie liniowe
programowanie liniowe zadanie 1 wmzghak5ktjjzelzmpatqlx6iahqoqrauoxjgtq WMZGHAK5KTJJZELZMPATQLX6IA

więcej podobnych podstron