Technika optymalizacji

Laboratorium

ĆWICZENIE I

Zadanie programowania liniowego dla ograniczeń mniejszościowych

Metoda prymalna simpleks

Prowadzący ćwiczenie: dr inż. Ewa Szlachcic

1. Metoda programowania liniowego PL – metoda prymarna simpleks

Celem ćwiczenia jest zapoznanie się z podstawową metodą rozwiązywania liniowego zadania
optymalizacji na przykładzie prymarnej metody simpleks.
Metoda ta pozwala na wyliczenie takiego wektora zmiennych decyzyjnych x,
należącego do zbioru rozwiązań dopuszczalnych X, dla którego funkcja celu osiąga
maksimum:

max

)

(

0









x

c

x

x

f

T

przy ograniczeniach:

}

0

;

'

:

{









x

b

x

A

x

X

dim x= nx1, dim c=nx1, dim A’=mxn, dim b = mx1

Na postać kanoniczną składa się funkcja celu

x

c

x

f

T





)

(

, oraz ograniczenia, które

muszą być przekształcone do postaci równościowej:

max

)

(

0



 x

x

f

przy ograniczeniach:

}

0

;

'

:

{









x

b

x

A

x

X

Macierz A o wymiarach mxn tworzą dwie podmacierze A’ o wymiarach odpowiednio
mx(n-m) i podmacierz I (macierz jednostkowa) o wymiarach mxm,
gdzie n – ilość zmiennych włącznie ze zmiennymi sztucznymi ,
m – ilość ograniczeń.





I

A

A

'



Macierz A’ to macierz tworzona przez współczynniki przy zmiennych decyzyjnych w
ograniczeniach mniejszościowych o wymiarze mxn.

1.1.





X

, jedno optymalne rozwiązanie.

funkcja celu:

2

1

0

2

3

max

x

x

x





ograniczenia:























0

3

2

4

2

1

2

1

x

x

x

x

x

postać równościowa:





















3

2

4

4

2

1

3

2

1

x

x

x

x

x

x

Tablica simpleks:





Najpierw wybieramy kolumnę w której jest najmniejsza wartość w naszym przypadku -3.
Następnie szukamy punktu centralnego dzieląc wartości wyrazów z pierwszej kolumny przez

wartości z wybranej kolumny

1

x

(1 i -1) mamy wiec

,

4

1

4 

3

1

3







, wybieramy 4

ponieważ potrzebujemy wartości większej od 0 więc punkt centralny mamy w 1.
Teraz zamieniamy kolumny

1

x

z wierszem

3

x .

Wyliczmy poszczególne wartości:

1

x

2

x

0

x

0 -3 -2

3

x

4

1

1

4

x

3 -1 2

3

x

2

x

0

x

12

1

x

4

x

1

x

2

x

0

x

0

-3 -2

3

x

4

1 1

4

x

3 -1 2

1

x

2

x

0

x

0

-3

-2

3

x

4

1

1

4

x

3 -1 2

3

x

2

x

0

x

1

1

x

4

x

12

1

)

3

(

4

0









1

1

1

)

3

(

)

2

(











W całości tabela wygląda następująco

1

x

2

x

0

x

0 -3 -2

3

x

4

1

1

4

x

3

-1 2

3

x

2

x

0

x

1

x

4

x

7

1

x

2

x

0

x

0 -3 -2

3

x

4

1

1

4

x

3

-1

2

3

x

2

x

0

x

1

x

4

x

3

1

x

2

x

0

x

0 -3 -2

3

x

4

1

1

4

x

3

-1

2

3

x

2

x

0

x

1

x

4

4

x

1

x

2

x

0

x

0 -3 -2

3

x

4

1

1

4

x

3 -1 2

3

x

2

x

0

x

1

x

1

4

x

3

x

2

x

0

x

1

x

4

x

1

1

x

2

x

0

x

0 -3 -2

3

x

4

1

1

4

x

3

-1 2

1

x

2

x

0

x

0

-3 -2

3

x

4

1

1

4

x

3 -1 2

3

x

2

x

0

x

3

1

x

4

x

7

1

)

1

(

4

3









3

1

)

1

(

1

2









4

1

4 

1

1

1 

1

1

)

1

(







3

1

)

3

(







Podstawiając do funkcji celu

2

1

0

3

x

x

x





, x

1

=4 i

0

x =12 otrzymujemy.

2

4

3

12

x







2

x

=0

Rozwiązaniem jest punkt x

1

=4,

2

x

=0

Interpretacja graficzna:

Rys. 1

1.2.





X

, nieskończenie wiele rozwiązań na zbiorze ograniczonym – np. odcinek

funkcja celu ma postać:

ograniczenia: 



















1

2

0

8

4

8

2

1

2

1

x

x

x

x

x

postać równościowa:





















1

2

8

4

8

4

2

1

3

2

1

x

x

x

x

x

x

Tablica początkowa simpleksu i otrzymana po przejściu algorytmu:

Rozwiązanie x

1

=1 ; x

2

=0.

W tabeli pojawiło się zero, czyli układ ma nieskończenie wiele rozwiązań, ale na zbiorze
ograniczonym o czym z kolei świadczą wartości dodatnie w kolumnie gdzie występuje zero
(x

2

). Do obliczenia końca zbioru ograniczonego, w tym wypadku drugiego końca odcinka

musimy dokonać ponownych obliczeń.
Sprawdzamy punkty w kolumnie oznaczonej „0”. Przeliczamy metodami Gaussa,
wartości w tablicy simpleksowej. Obliczamy tylko

2

1

, x

x

,czyli współrzędne drugiego punktu.

Rozwiązaniem jest odcinek o początku w punkcie: x

1

=1 ; x

2

=0 i końcu o współrzędnych:

x

1

=1/4; x

2

=3/2

1

x

2

x

0

x

0 -4 -2

3

x

8 8 4

4

x

1 -2 1

2

1

0

2

4

max

x

x

x





2

3

4

1

2

2

1

3

1







Równanie odcinka:













































































































































































2

3

2

3

4

3

4

1

2

3

2

3

4

1

4

1

4

4

2

3

4

1

)

1

(

0

1

2

3

4

1

0

1

)

1

,

0

(

,

)

1

(

^

2

1

2

1

^

x

x

x

x

x

x

Interpretacja graficzna:

Rys. 2

1.3.





X

, nieskończenie wiele rozwiązań na zbiorze nieograniczonym

Np. pół-prosta


funkcja celu ma postać:

ograniczenia:

postać równościowa:



9

3

3

2

1









x

x

x

Tablica początkowa simpleksu i otrzymana po przejściu algorytmu:

Wartość zero otrzymana w kolumnie wartości x

1

świadczy o nieskończonej liczbie rozwiązań,

ale wartości występujące w tej kolumnie w tym przypadku jedna wartośc jest ujemna co
świadczy o nieograniczoności zbioru.

Rozwiązanie x

1

=0 ; x

2

=9.

Półprosta:
rozwiązaniem jest półprosta rozpoczynająca się w

punkcie

x

1

=0 ; x

2

=12.

0

x

1

x

2

x

0

x

0 3 -1

3

x

9 -3 1

0

)

3

(

9

2

1

















t

t

x

t

x

2

1

0

3

max

x

x

x





















0

9

3

2

1

x

x

x

Interpretacja graficzna:

Rys. 3

1.4.





X

zbiór pusty, zadanie PL nie ma rozwiązania.

----------

1.5 Zadanie nieograniczone – funkcja celu może osiągnąć wartość nieskończenie
dużą albo małą. Żadne ograniczenie nie wstrzymuje jej wzrostu.

funkcja celu ma postać:

ograniczenia:

postać równościowa:



5

2

3

2

1









x

x

x

Tablica początkowa simpleksu i otrzymana po przejściu algorytmu:

Algorytm nie napotyka na ograniczenia „ucieka do
nieskończoności”

Interpretacja graficzna:

Rys. 4

0

x

1

x

2

x

0

x

0 1 -2

3

x

5 -2 1















0

5

2

2

1

x

x

x

2

1

0

2

max

x

x

x







1.6 Zadanie teoretyczne

Zakład stolarski produkuje wyłącznie taborety i krzesła.
Wyprodukowanie jednego taboretu wymaga poświęcenia 0,5 godziny pracy tokarki, a krzesła
2 godziny. W procesie produkcyjnym zużywa się drewno
(na 1 szt. taboretu potrzeba 0,15 m3, a 1 szt. krzesła: 0,3 m3), ozdobne gwoździe (2
opakowania na taboret i połowę tego na krzesło)i lakier (który kupowany jest prawie darmo
za wschodnią granicą). Ze względu na restrykcyjne przepisy dotyczące wyrębu drzew,
dostawy drewna są limitowane i wynoszą 18 m3 tygodniowo. Jednocześnie rzemieślnik
wykonujący ozdobne gwoździe może dostarczyć tygodniowo maksymalnie 150 opakowań
tych gwoździ.
Wiadomo również, że maszyny w ciągu tygodnia mogą przepracować najwyżej 100 godzin.
Zyski jednostkowe wynoszą: 30 zł (taboret) i 45 zł (krzesło).
Zmaksymalizuj zyski zakładu.


x1-krzeslo
x2-taboret

funkcja celu ma postać:

ograniczenia:

postać równościowa:





Tablica początkowa simpleksu i otrzymana po przejściu algorytmu:

1

x

2

x

0

x

0 -45 -30

3

x

100 1,5 0,5

4

x

18 0,25 0,15

5

x 150 1 2

2

1

0

30

45

max

x

x

x































0

150

2

18

15

,

0

3

,

0

100

5

,

0

2

2

1

2

1

2

1

x

x

x

x

x

x

x





























150

2

18

15

,

0

3

,

0

100

5

,

0

2

5

2

1

4

2

1

3

2

1

x

x

x

x

x

x

x

x

x

W czwartej iteracji otrzymujemy:

Interpretacja graficzna:

3150

60

30

0

2

1







x

x

x

Rys.5

2. Wnioski:

2.1





X

, jedno optymalne rozwiązanie:

W tym przypadku , wzrost funkcji jest powstrzymany ograniczeniami, którymi są 2 proste.
Maksymalna wartość funkcji celu znajduję się w punkcie o współrzędnych (4, 0). Wartość

optymalna została osiągnięta już w drugiej iteracji.

2.2





X

, nieskończenie wiele rozwiązań na zbiorze ograniczonym – np. odcinek:

Funkcja celu ma nieskończenie wiele rozwiązań, na zbiorze ograniczonym, gdy jest

równoległa do jednego z ograniczeń. Drugie ograniczenie może jedynie ograniczać zbiór. W

maksimum funkcja celu „pokrywa” się z ograniczeniem, dając w konsekwencji nieskończenie

wiele rozwiązań. Maksymalny punkt możemy obliczyć ze wzoru:



































2

3

2

3

4

3

4

1

ˆx

gdzie λ[0, 1].



2.3





X

, nieskończenie wiele rozwiązań na zbiorze nieograniczonym – np. pół prosta:

W tym przypadku jest tylko jedno ograniczenie. Funkcja celu ma nieskończenie wiele

rozwiązań, na zbiorze nieograniczonym, gdy jest równoległa do tego ograniczenia, wartości

optymalne osiągnie, gdy „pokryje się” z funkcją ograniczającą. W tablicy simpleksowej w

jednym ze współczynników funkcji celu występuje ‘0’, jednak nie żadna zmienna nie spełnia

kryteriów wyjścia z bazy. Oznacza to, że zbiór jest nieograniczony. Możemy wyznaczyć

równania parametryczne półprostej, na której znajdują się optymalne rozwiązania:

...

2

,

1

,

0

3

9

ˆ

ˆ

2

1









t

t

x

t

x

2.4 Zadanie nieograniczone:

Zadanie nieograniczone, występuje wtedy, gdy żadna funkcja nie ogranicza wzrostu funkcji
celu. W tym przypadku funkcja celu dąży do nieskończoności, co widać na rys. 4.