Rozdział 14

PROGRAMOWANIE

LINIOWE

Sld.14.2. Programowanie liniowe

Wiele problemów, które chcemy rozwiązywać w

ekonometrii, to zadania

optymalizacji

:

problem

•najkrótszej ścieżki,

•najtańszego drzewa rozpinającego,

•najdłuższego podciągu rosnącego

itd.

W takich przypadkach poszukujemy rozwiązania,

które

1.spełnia pewne ograniczenia (np. ścieżka musi

przechodzić po krawędziach grafu i prowadzić z

s

do

t

,

drzewo musi obejmować wszystkie wierzchołki) oraz

2.jest możliwie najlepsze, według pewnego dobrze

zdefiniowanego

kryterium,

spośród

wszystkich

rozwiązań spełniających te ograniczenia.

Sld.14.3.

Programowanie

liniowe

Programowanie liniowe (ang.

linear programming

)

obejmuje szeroką klasę zagadnień optymalizacyjnych,

w których zarówno ograniczenia, jak i kryterium

optymalizacji są funkcjami liniowymi. Okazuje się, że

można w ten sposób wyrazić ogromną liczbę

problemów.

W problemie programowania liniowego dany jest

zbiór zmiennych, którym chcemy przypisać wartości

rzeczywiste w taki sposób, aby

1. spełnić pewien zbiór równań i/lub nierówności

liniowych zawierających te zmienne,

2. znaleźć optymalną wartości (najmniejszą lub

największą) danej funkcji celu (ang.

objective function

).

Sld.14.4. Przykład 1: maksymalizacja zysku -1

Pewien producent czekolady oferuje dwa wyroby:

-czekoladki

X1

- oraz luksusowe

X2

.

Ile każdego z nich powinien produkować, aby

zmaksymalizować swoje

zyski?

Powiedzmy,

że

produkuje dziennie

x

1

pudełek

X1

, każde w cenie 1 $,

oraz

x

2

pudeł

X2

droższych, po 6 $ za sztukę.

x

1

i x

2

są nieznanymi wartościami, które chcemy

obliczyć. Istnieją ograniczenia:

•Oczywiste

x

1

, x

2

 0

.

•Dzienne zapotrzebowanie na czekoladki

X1

ogranicza się do

200 pudeł i

X2

do 300 pudeł.

•Pracownicy mogą łącznie wyprodukować co

najwyżej 400 pudeł czekoladek dziennie.

Ile wynosi wielkość produkcji obu typów

czekoladek zapewniająca optymalny zysk?

Sld.14.5.

Przykład 1: maksymalizacja zysku

- 2

Sytuację opisujemy za pomocą zadania
programowania liniowego:

funkcja celu

C = max (x

1

+ 6x

2

);

ograniczenia: x

1



200; x

2



300; x

1

+ x

2



400; x

1

,

x

2



0 .

Równanie liniowe zmiennych x

1

i x

2

definiuje linię prostą na

płaszczyźnie dwuwymiarowej (2D), a nierówność liniowa wyznacza
półpłaszczyznę - obszar po jednej stronie prostej. Zbiór wszystkich
rozwiązań dopuszczalnych jest częścią wspólną pięciu pół płaszczyzn.
Jest to wielokąt :

Sld.14.6. Rozwiązywanie zadań

programowania liniowego

Zadania programowania liniowego
(PL) możemy rozwiązywać przy użyciu

metody sympleks

wymyślonej przez George'a Dantziga
w 1947 roku.

Algorytm ten rozpoczyna od

pewnego wierzchołka, może to być
(0,0), po czym wielokrotnie przechodzi
do

sąsiedniego

wierzchołka

(połączonego

krawędzią

obszaru

dopuszczalnego) o lepszej wartości
funkcji celu. W ten sposób wspina się
po wierzchołkach wielokąta, skacząc
od sąsiada do sąsiada i stale
zwiększając zysk na swojej drodze.

 

Sld.14.7. Przykład 2: maksymalizacja zysku –
2.1

Pewien producent czekolady oferuje trzy wyroby:

- czekoladki

X1

; luksusowe

X2

, oraz bardziej ekskluzywny

X3

.

Ile każdego z nich powinien produkować, aby
zmaksymalizować swoje zyski? Produkuje dziennie x

1

pudełek

X1

w cenie 1 $, x

2

pudeł

X2

po 6 $, oraz

X3

po 13 $ za sztukę.

x

1,

x

2

i x

3

chcemy obliczyć. Istnieją ograniczenia :

•

Oczywiste x

1

, x

2

, x

3



0.

•

Dzienne zapotrzebowanie na czekoladki

X1

ogranicza się do

200 pudeł, i

X2

do 300 pudeł.

•

Pracownicy mogą łącznie wyprodukować co najwyżej 400
pudeł czekoladek dziennie.

•

Wyroby

X1

i

X3

wymagają tych samych maszyn pakujących,

przy czym pakowanie

X3

trwa trzy razy dłużej, co narzuca

jeszcze jedno ograniczenie

x

1

+ 3x

3



600.

Ile wynosi wielkość produkcji obu typów czekoladek

zapewniająca optymalny zysk?

Sld.14.8. Przykład 2: maksymalizacja
zysku – 2.2

Przechodzimy z wierzchołka do wierzchołka po krawędziach

wielościanu, stale zwiększając zysk. Rysunek przedstawia jedną z
możliwych

dróg.

Odpowiada

ona

następującemu

ciągowi

wierzchołków i zysków:

A(0, 0, 0)  B(200, 0, 0)  C(200, 200, 0)  D(200, 0, 200)  E(0,

300, 100)

0$ 200 $ 1400 $ 2800 $

3100 $

Sld.14.8. Algorytm sympleks

Algorytm sympleks dla danego zbioru nierówności

liniowych i liniowej funkcji celu znajduje optymalny punkt

dopuszczalny za pomocą następującej strategii:

• niech v - dowolny wierzchołek obszaru dopuszczalnego
• while

istnieje sąsiad v' wierzchołka v o lepszej wartości celu:

• przypisz

v = v‘.

W każdej iteracji algorytm sympleks wykonuje dwa

zadania:

1. Sprawdza, czy bieżący wierzchołek jest optymalny

(jeśli tak, zatrzymuje się ).

2. Określa następny wierzchołek, do którego powinien

się przenieść.

LITERATURA

1.S.Dasgupta. Algorytmy. PWN. Warszawa

2010