Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

II Zadanie programowania liniowego PL – dla ograniczeń większościowych

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]

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Postać kanoniczna II zadania PL

0,

,

A

T

≥

≥

=

x

b

x

x

c

x

,

min

0

0,

,

A

s

s

T

≥

−

=

+

−

=

x

x

b

x

I

x

x

c

x

s

,

-

,

-

max

0

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

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

∈

≥

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

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

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

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

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Przykład II zadania programowania liniowego – dualna metoda simpleks

















≥

≥

+

+

≥

≥

+

+

+

=

0

,

5

1

1

6

8

1

2

2

1

:

2

1

2

2

1

1

x

x

x

x

x

x

x

x

X

-1

-1

-5

X

5

-1

-2

-6

X

4

-2

-1

-8

X

3

1

1

0

-x

0

-x

2

-x

1

-1/2

-1/2

-1

X

5

-1/2

-3/2

-2

x

4

-1/2

½

4

X

2

½

½

-4

-x

0

-x

3

-x

1

2

1

0

1

1

min

x

x

X

x

+

=

∈

x

-1/3

-1/3

-1/3

X

5

1/3

-2/3

4/3

X

1

-2/3

1/3

10/3

X

2

1/3

1/3

-14/3

-X

0

-x

3

-x

4

tablica początkowa

tablica pośrednia

tablica optymalna

tablica dualnie dopuszczalna

tablica jeszcze nie optymalna

N

oj

R

j

dla

y

∈

≥ 0

0

20

<

y

m

i

dla

y

i

,...,

1

0

0

=

∀

≥

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Przykład II zadania programowania liniowego–dualna metoda simpleks

cd.

]

0

,

1

,

0

,

3

,

2

[

]

,

,

,

,

[

1
5

1
4

1
3

1
2

1

1

1

=

=

∧

x

x

x

x

x

x

1

-3

1

X

4

1

-2

2

X

1

-1

1

3

X

2

0

1

-5

-X

0

-x

3

-x

5

1

-3

1

X

3

-1

1

1

x

1

1

-2

4

X

2

0

1

-5

-x

0

-x

4

-x

5

tablica optymalna I

tablica optymalna II

Rozwiązanie optymalne I
wierzchołek:

Rozwiązanie optymalne II
wierzchołek:

5

0

=

∧

x

]

0

,

0

,

1

,

1

,

1

[

]

,

,

,

,

[

2

5

2

4

2

3

2

2

2

1

2

=

=

∧

x

x

x

x

x

x

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

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]

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Optymalne rozwiązanie zadania programowania liniowego PL metodą

simpleks

Twierdzenie 4.5

Twierdzenie 4.5

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

jest rozwiązaniem optymalnym zadania PL, jeśli są spełnione dwa warunki:

(i) Warunek prymalnej dopuszczalności:

{

}

m

i

dla

y

io

,...,

1

0

∈

≥

(ii) Warunek optymalności

N

j

R

j

dla

y

∈

∀

≥ 0

0

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

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

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

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

=

=

+

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

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

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

I faza metody – zadanie pomocnicze PL

=

0

max z

,

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

=

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Ad.I.2 Pomocnicza funkcja celu

Uproszczona wersja I fazy metoda dwufazowej simpleks – uzyskanie

bazowego rozwiązania dopuszczalnego

•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 pomocniczych.

•Należy znaleźć 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

{

}

m

i

dla

y

y

r

i

i

i

,...,

2

,

1

0

,

min

0

0

=

<

⇒

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

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 metoda dwufazowej simpleks

cd.

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka













>

=

=

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

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

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

1

1

6

x

5

1

-1

3

x

4

-1

-2

-2

x

3

-6

-1

0

x

0

-x

2

-x

1

1

1

6

x

1

2

1

9

x

4

1

2

10

x

3

-5

1

6

x

0

-x

2

-x

5

2

1

0

X

x

x

6

x

1

x

max

+

=

∈

-0,5

0,5

1,5

X

1

0,5

0,5

4,5

X

2

-0,5

1,5

5,5

X

3

2,5

3,5

28,5

x

0

-x

4

-x

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

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

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.

-1

1

0

2

x

6

1

-2

1/2

-3

x

5

1

2

-1/2

2

x

4

1

1

-1/2

0

x

0

-x

3

-x

2

-x

1

x

x

x

x

x

6

2

1

0

-1

x

5

x

x

x

x

x

2

x

x

x

x

x

0

-x

3

-x

4

-x

1

0

,

,

,

1

2

4

3

2

1

3

4

2

≥

−

−

−

=

x

x

x

x

x

x

x

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Teoria dualności dla zadania programowania liniowego PL

x

c

T

x =

0

max

0

≥

≤

x

b

x

A

0

≥

≥

v

c

v

A

T

b

v

v

T

=

0

min

Twierdzenie 7.1 :

Jeśli wektor x jest rozwiązaniem dopuszczalnym dla zadania prymalnego i
wektor v jest rozwiązaniem dopuszczalnym dla zadania dualnego, to wartość
funkcji celu w zadaniu dualnym nie może być mniejsza od wartości funkcji
celu w zadaniu prymalnym.

x

c

b

v

T

T

≥

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Teoria dualności dla zadania PL cd.

∧

∧

v

i

x

∧

∧

=

v

b

x

c

T

T

0

=

v

x

T

Twierdzenie 7.2

Dla pary rozwiązań optymalnych zadania prymalnego i dualnego PL
zachodzi warunek:

Twierdzenie 7.3

Niech (x

r

,x

s

) i ( v

r

, v

s

) będą odpowiednio rozwiązaniami dopuszczalnymi zadania

prymalnego i dualnego, przy czym x

s

i v

s

są wektorami zmiennych dopełniających

do postaci kanonicznej zadania w wektorach rozwiązań.

Wtedy (x

r

,x

s

) i ( v

r

, v

s

) będą odpowiednio rozwiązaniami optymalnymi pary zadań

prymalnego i dualnego, jeśli zachodzi warunek komplementarności zmiennych:

tzn.

0

=

+

r

T

s

s

T

r

v

x

v

x

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Twierdzenie 7.4

Jeśli jedno z pary wzajemnie dualnych zadań programowania liniowego ma
rozwiązanie optymalne, to ma je również zadanie dualne i obydwa zadania mają
identyczne wartości funkcji celu.

Twierdzenie 7.5

Jeśli zadanie dualne jest nieograniczone, to zadanie prymalne jest sprzeczne.

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Przykład I zadanie prymalne

2

1

0

1

2

max

x

x

X

x

+

=

∈

x





















≥

≤

+

≤

+

−

≤

+

=

0

,

21

2

6

0

5

:

2

1

2

1

2

1

x

x

x

x

x

x

x

x

X





















≥

≥

+

+

≥

+

−

=

0

,

,

1

2

2

6

:

3

2

1

3

2

1

3

2

1

v

v

v

v

v

v

v

v

v

x

V

3

2

1

0

21

0

5

min

v

v

v

v

V

v

+

+

=

∈

Przykład II System cięcia dłużyc

3

2

1

0

2

.

0

6

.

0

3

.

0

min

v

v

v

v

+

+

=

0

,

,

1200

2

1

0

2100

0

3

7

3

2

1

3

2

1

3

2

1

≥

≥

+

+

≥

+

+

v

v

v

v

v

v

v

v

v

2

1

0

1

2

max

x

x

X

x

+

=

∈

x





















≥

≤

+

≤

+

≤

+

=

0

,

2

.

0

2

0

6

.

0

1

3

3

.

0

0

7

:

2

1

2

1

2

1

x

x

x

x

x

x

x

x

X

Postać wektora rozwiązań:

[

] [

]

5

4

3

2

1

,

,

,

,

v

v

v

v

v

v

v

v

s

r

=

=

[

] [

]

5

4

3

2

1

,

,

,

,

x

x

x

x

x

x

x

x

s

r

=

=

[

] [

]

0

,

,

0

=

⇒

=

r

s

T

s

r

T

v

v

x

x

v

x

zadanie dualne

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Teoria dualności dla zadania PL

cd.

2

1

0

1

2

max

x

x

X

x

+

=

∈

x





















≥

≤

+

≤

+

−

≤

+

=

0

,

21

2

6

0

5

1

1

:

2

1

2

1

2

1

x

x

x

x

x

x

x

x

X

2

6

21

x

5

1

-1

0

x

4

1

1

5

x

3

-1

-2

0

x

0

x

2

x

1

Zadanie dualne:

I. Rozwiązanie zadania dualnego metodą simpleks

Rozwiązanie optymalne:

a)

Zadanie dualne

b)

Zadanie prymalne

Wartość optymalna funkcji celu:

1/3

1/6

7/2

x

1

4/3

1/6

7/2

x

4

2/3

-1/6

3/2

x

3

-1/3

1/3

7

x

0

x

2

x

5

-1/2

1/4

11/4

x

1

-2

1/2

1/2

x

4

3/2

-1/4

9/4

x

2

1/2

1/4

31/4

x

0

x

3

x

5

[

]

[

]

3

2

1

5

4

5

4

3

2

1

,

,

,

,

,

,

,

,

v

v

v

v

v

v

x

x

x

x

x

x

↑

=

↑

=

∧

∧









↑

=









↑

=

∧

∧

4

1

,

0

,

2

1

,

0

,

0

0

,

2

1

,

0

,

4

9

,

4

11

v

x

4

31

0

0

=

=

∧

∧

v

x