Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

II Zadanie programowania liniowego PL

przy ograniczeniach

:

x

c

T

x 

0

min

0





x

b

x

A

dim x=[n*1], dim c=[n*1]

Macierz A odpowiada za współczynniki w m

ograniczeniach

dim A=[m

x n]

Wektor wyrazów wolnych b odpowiada za prawą stronę
ograniczeń

dim b

=[m*1]

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

Postać kanoniczna II zadania PL

0,

,

A

T









x

b

x

I

x

x

c

x

s

s

,

min

0

0,

,

A

s

s

T













x

x

b

x

I

x

x

c

x

s

,

-

,

-

max

0

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

Optymalne rozwiązanie II zadania PL metodą dualną

simpleks

Twierdzenie:

Twierdzenie:

Rozwiązanie bazowe dopuszczalne układu równań Ax=b

jest rozwiązaniem optymalnym II zadania PL, jeśli są
spełnione warunki:
(i) Warunek dualnej dopuszczalności:

N

oj

R

j

dla

y



0

(ii) Warunek dualnej optymalności





m

i

dla

y

i

,...,

1

0

0





Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

Algorytm dualny simpleks

Krok 1

. (start). Rozpoczynamy algorytm od znalezienia

pierwszej tablicy dualnie dopuszczalnej. Należy sprawdzić
dualną dopuszczalność

rozwiązania: czy Tak - idź do Kroku 2,
Nie – koniec.

Krok 2.

(test optymalności). Czy

dla każdego

?

• Tak - to aktualne rozwiązanie

jest optymalne.

•

Nie - idź do Kroku 3.

Krok 3.

(Wybór zmiennej usuwanej z bazy). Wybierz jako

zmienną usuwaną z bazy taką zmienną

dla której

Typową regułą jest wybór zmiennej dla której:

0

0



i

y

m

i

,...,

1



r

B

x

.

0

0



r

y





m

i

y

y

y

i

io

R

j

r

N

,...,

1

,

0

,

0

0

min









r

B

x

Idż do Kroku 4.

N

oj

R

j

dla

y



0

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

Algorytm dualny simpleks c.d.

Krok 5. (eliminacja). Dokonaj dualną iterację simpleksową metodą
eliminacji

Gauss’a poprzez wprowadzenie do bazy oraz usunięcie

Idź do Kroku 2.

k

x

Krok 4. (wybór zmiennej wprowadzanej do bazy). Wybierz jako
zmienną wchodzącą do bazy taką zmienną

dla której

Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie
jedną z nich.

Idż do Kroku 5.

k

x

).

0

,

(

max

0

0





rj

rj

j

rk

k

y

y

y

y

y

r

B

x

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

Przykład II zadania programowania liniowego – dualna metoda
simpleks







































0

,

3

1

1

6

6

1

2

2

1

:

2

1

2

2

1

1

x

x

x

x

x

x

x

x

X

 

-x

1

-x

2

-x

0

0

1

1

X

3

-6

-1

-2

X

4

-6

-2

-1

X

5

-3

-1

-1

 

-x

1

-x

3

-x

0

-3

½

½

X

2

3

½

-1/2

x

4

-3

-3/2

-1/2

X

5

0

-1/2

-1/2

2

1

0

1

1

min

x

x

X

x







x

 

-x

4

-x

3

-X

0

-4

1/3

1/3

X

2

2

1/3

-2/3

X

1

2

-2/3

1/3

X

5

1

-1/3

-1/3

tablica
początkowa

tablica
pośrednia

tablica
optymalna

tablica dualnie
dopuszczalna

tablica jeszcze nie
optymalna

tablica z rozwiązaniem
optymalnym

N

oj

R

j

dla

y



0

0

20



y

m

i

dla

y

i

,...,

1

0

0







Rozwiązanie
optymalne:





T

T

x

x

x

x

x

x

1

0

0

2

2

5

4

3

2

1





























4

0





x

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

III Zadanie programowania liniowego PL

przy ograniczeniach

:

 

x

c

x

T

f



max

0

2

2

1

1







x

b

x

A

b

x

A

dim x=[n*1], dim c=[n*1]

Macierze A

1

, A

2

odpowiadają za współczynniki w m

1

i m

2

ograniczeniach

dim A

1

=[m

1

* n], dim A

2

=[m

2

* n]

Wektory b

1

, b

2

odpowiadają za prawe strony ograniczeń

dim b

1

=[m

1

*1], dim b

2

=[m

2

*1]

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

Zadanie programowania liniowego dla ograniczeń

mniejszościowych i większościowych

I faza - należy znaleźć pierwsze rozwiązanie bazowe
dopuszczalne poprzez rozwiązanie zadania pomocniczego

II faza - maksymalizacja funkcji celu x

0

dla następnego

rozwiązania bazowego dopuszczalnego wg algorytmu simpleks.

Metoda dwóch faz

Krok 1

. (start). Rozpoczynamy algorytm od znalezienia

pierwszego rozwiązania bazowego dopuszczalnego. Należy
sprawdzić dopuszczalność

rozwiązania: czy Tak - idź do Kroku 2,
Nie – STOP.

m

i

dla

y

i

,...,

1

0

0





Algorytm simpleks (prymalny) – I faza Krok 1 – nie ma możliwości
stworzenia pierwszego rozwiązania bazowego dopuszczalnego

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

I faza metody PL – Nieznane pierwsze rozwiązanie bazowe
dopuszczalne

I.1 - technika zadania pomocniczego

I.2 - technika pomocniczej funkcji celu

Ad. I.1 Rozwiązanie zadania pomocniczego PL z funkcją celu w
postaci funkcji liniowej z

0















0

A

I

A

A

2

t

1

Gdzie I

t

jest macierzą jednostkową

rzędu t.

2

N

2

1

t

t

N

1

b

x

A

b

x

I

x

A







Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

I faza metody PL cd.

Wprowadzamy wektor zmiennych pomocniczych dim
= m- t



x

α

x

2

b

x

I

x

A

b

x

I

x

A

α

t

m

N

2

1

t

t

N

1











Rozwiązanie bazowe dopuszczalne układu równań:

0

,

,

2

1







N

t

x

b

x

b

x



Należy znaleźć inne rozwiązanie bazowe dopuszczalne,
w którym

lub stwierdzić, że takie rozwiązanie nie istnieje.

0





x

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

I faza metody – zadanie pomocnicze PL



0

maxz

,

1x

α



t

t

N

N

0

x

c

x

c

x





,

0



t

t

N

1

x

I

x

A



,

b

1





N

2

x

A

,

2

α

t

m

b

x

I





0

,

,





x

x

x

t

N

Zmienna x

0

zawsze pozostaje zmienną bazową. Rozwiązaniem początkowym

zadania PL I fazy jest

Oraz

N

1

t

N

1

t

0

N

2

2

0

N

2

2

α

N

1

1

t

)x

A

c

(c

b

c

x

),

x

A

1(b

z

,

x

A

b

x

,

x

A

b

x



















0

x

N



Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

Ad.I.2 Pomocnicza funkcja celu

Uproszczona wersja I fazy metody dwufazowej

simpleks – uzyskanie bazowego rozwiązania

dopuszczalnego





m

i

dla

y

y

y

i

i

i

so

,...,

2

,

1

0

,

min

0

0







•Jeśli wektor b w początkowej tablicy simpleksowej ma przynajmniej jedną ujemną
współrzędną, to tablica przedstawia niedopuszczalne rozwiązanie bazowe.

•Początkową niedopuszczalną tablicę simpleksową można przekształcić
wykorzystując algorytm simpleks.

•Cel – uzyskanie nieujemnych wartości zmiennych bazowych

•Należy znaleźć wiersz s, dla którego współczynnik y

io

przyjmuje najmniejszą

wartość

•Wybrany wiersz s będzie stanowił pomocniczą funkcję celu , którą należy
zmaksymalizować.

•Kolejne kroki metody simpleks powinny być prowadzone do uzyskania
dopuszczalnej tablicy simpleks, tzn. takiej dla której spełniony jest warunek
prymalnej dopuszczalności:

m

i

dla

y

i

,...,

2

,

1

0

0





•Koniec I fazy

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

Krok 1. (start- wybór pomocniczej funkcji celu). Rozpoczynamy
algorytm od znalezienia wiersza s , dla którego oraz

Krok 2. (Wybór zmiennej wchodzącej do bazy). Wybierz jako zmienną
wchodzącą do bazy taką zmienną

dla której

Typową regułą jest wybór zmiennej , dla której:

0



sk

y

N

k

R

x 

N

k

R

k

x



,





0

:

min

0







sk

sk

R

j

k

y

y

y

N

k

x

Idż do Kroku 3.

N

sk

R

k

dla

y



0

0

0



s

y





m

i

y

y

s

i

i

i

,...,

2

,

1

,

0

:

min

0

0







Jeśli brak takiego s ( ) to tablica odpowiada
dopuszczalnemu rozwiązaniu bazowemu – należy przejść do II fazy.

m

i

dla

y

i

,...,

2

,

1

0

0





Jeśli jest brak takiej zmiennej ( ) to jest brak
rozwiązania dopuszczalnego. Jest to problem sprzeczny.

Ad.I.2 Pomocnicza funkcja celu

Uproszczona wersja I fazy metody dwufazowej

simpleks

cd.

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.



















0

,

,...,

1

:

min

0

0

ik

i

ik

io

i

rk

r

y

y

m

i

y

y

y

y

Krok 4. (eliminacja Gauss’a). Wyznacz oraz

względem zmiennych

oraz zmiennej

zgodnie z wyprowadzonymi wzorami.

Podstaw

aby otrzymać pierwsze rozwiązanie bazowe dopuszczalne.

Idź do Kroku 1.

Krok ten czasami nazywa się wymianą zmiennej bazowej ( piwotyzacją).

k

x

,

,

N

Bi

R

i

x



}

{

,

k

R

j

x

N

j





0

i

}

{

,

0









Br

N

j

x

k

R

j

x

Krok 3. (wybór zmiennej usuwanej z bazy). Wybierz jako zmienną
usuwaną z bazy taką zmienną

dla której

Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie jedną z
nich.

Taki przypadek zawsze istnieje, ponieważ

Idż do Kroku 5.

,

Br

x

r

B

x

0

0

0





sk

s

y

i

y

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

Przykład III zadania programowania liniowego

metoda dwufazowa simpleks







































0

x

,

6

x

1

x

1

3

2

x

1

x

1

x

1

x

2

:

x

X

2

1

2

2

1

1

 

-x

1

-x

2

x

0

0

-1

-6

x

3

-2

-2

-1

x

4

3

-1

1

x

5

6

1

1

 

-x

5

-x

2

x

0

6

1

-5

x

3

10

2

1

x

4

9

1

2

x

1

6

1

1

2

1

0

X

x

x

6

x

1

x

max







 

-x

5

-x

4

x

0

28,

5

3,5

2,5

X

3

5,5

1,5

-0,5

X

2

4,5

0,5

0,5

X

1

1,5

0,5

-0,5

I faza

II faza cz.1

II faza cz.2

Brak rozwiązania
dopuszczalnego

I rozwiązanie bazowe
dopuszczalne

II rozwiązanie bazowe
dopuszczalne-
rozwiązanie optymalne

6

x

,

0

6

x

1

1

B

0

B

















Rozwiązanie
optymalne:





T

T

x

x

x

x

x

x

0

0

5

,

5

5

,

4

5

,

1

5

4

3

2

1





























5

,

28

0





x

5

,

28

,

5

,

4

5

,

1

2

1

0

















B

B

x

x

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

Kier. EiT ESA III r

.

.

Przypadki szczególne – zbiór rozwiązań
dopuszczalnych jest zbiorem pustym - brak rozwiązania





X

3

2

1

0

2

1

max

x

x

x

X

x









x

























































0

,

2

3

2

2

1

2

2

2

1

:

3

2

3

2

1

3

2

1

x

x

x

x

x

x

x

x

x

x

X

W metodzie dwufazowej simpleks algorytm w I fazie obliczeń nie potrafi
stworzyć pierwszego rozwiązania bazowego dopuszczalnego z powodu braku
rozwiązań dopuszczalnych.

Przykład:

Nie jest spełniony warunek dopuszczalności drugiej tablicy simpleks i jednocześnie druga
tablica wskazuje, że jest brak rozwiązań dopuszczalnych.

-x

1

-x

2

-x

3

x

0

0

-1/2

1

1

x

4

2

-1/2

2

1

x

5

-3

1/2

-2

1

x

6

2

0

1

-1

-x

1

-x

4

-x

3

x

0

x

x

x

x

x

2

x

x

x

x

x

5

-1

0

1

2

x

6

x

x

x

x

0

,

,

,

,

,

1

2

6

5

4

3

2

1

3

4

5











x

x

x

x

x

x

x

x

x