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