Zadanie programowania liniowego część II

Wydział Elektroniki
Kier. Automatyka i Robotyka
Studia II st.

dr inż. Ewa Szlachcic

Zakład Sterowania i Optymalizacji

Instytut Informatyki, Automatyki i Robotyki

Politechnika Wrocławska

TEORIA I METODY
OPTYMALIZACJI

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Extremum zadania programowania liniowego PL

Twierdzenie 4.1

Zbiór wszystkich rozwiązań dopuszczalnych zadania programowania liniowego PL jest
zbiorem wypukłym.

Definicja 4.5

Punkt x należący do wypukłego zbioru jest punktem wierzchołkowym zbioru
X, jeśli nie może być wyrażony jako kombinacja liniowa innych punktów zbioru X.

n

R

X ⊂

Dowód:

1. Zakłada się, że wektor x jest bazowym rozwiązaniem dopuszczalnym. Pokazać, że x
jest punktem wierzchołkowym zbioru X

2. Zakłada się, że wektor x jest punktem wierzchołkowym zbioru rozwiązań
dopuszczalnych zadania programowania liniowego. Pokazać, że wektor x jest bazowym
rozwiązaniem dopuszczalnym.

Twierdzenie 4.2

Rozwiązanie dopuszczalne x zadania programowania liniowego PL jest punktem
wierzchołkowym zbioru rozwiązań dopuszczalnych X wtedy i tylko wtedy gdy
odpowiada mu bazowe rozwiązanie dopuszczalne tzn.:

T

B

x

x

]

0

,

[

=

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Extremum zadania programowania liniowego PL cd.

1

:

R

X

f

→

Twierdzenie 4.3

Jeżeli funkcja , określona na domkniętym i ograniczonym wypukłym
zbiorze , jest ciągła i wklęsła, to globalne minimum funkcji f(x) występuje w
punkcie ekstremalnym (bądź punktach) zbioru X.

Dowód: Zaprzeczamy tezie:

- dowolne globalne minimum

v – dowolny punkt ekstremalny zbioru X.

Zbiór X jest zbiorem zwartym, funkcja f(x) jest ciągła – więc istnieje punkt

∧

x

- punkty ekstremalne zbioru X .

k

i

v

i

,...,

1

, =

Każdy punkt , który nie jest punktem ekstremalnym, może być wyrażony jako
kombinacja wypukła punktów v

i

X

x ∈

1

;

,...,

1

,

0

,

1

1

=

=

≥

=

∑

∑

=

=

∧

k

i

k

i

i

i

i

i

k

i

v

x

µ

µ

µ

Funkcja f(x) jest wypukła więc zachodzi dla dowolnego punktu zachodzi:

X

x ∈

∧

)

(

max

)

(

)

(

)

(

1

1

i

i

k

i

k

i

i

i

i

i

v

f

v

f

v

f

x

f

≥

≥

=

∑

∑

=

=

∧

µ

µ

ckd.

n

R

X ⊂

)

(

)

(

v

f

x

f

<

∧

∧

x

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Extremum zadania programowania liniowego PL

cd.

∧

∧

∧

p

x

x

x

.....

,

2

1

Twierdzenie 4.4

1.

Funkcja celu zadania PL przyjmuje wartość maksymalną w punkcie
wierzchołkowym zbioru rozwiązań dopuszczalnych zadania PL.

2. Jeśli funkcja celu zadania PL przyjmuje wartość maksymalną w więcej niż jednym

punkcie wierzchołkowym, to ma tą samą wartość dla każdej kombinacji wypukłej
tych punktów.

Dla p dopuszczalnych bazowych rozwiązań optymalnych, tzn.

Zbiór rozwiązań optymalnych przyjmuje postać:

1

,...,

1

,

0

,

1

1

=

=

≥

=

∑

∑

=

=

∧

∧

p

i

i

i

p

i

i

i

p

i

x

X

λ

λ

λ

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Wprowadzone oznaczenia:

























≡













≡

−

−

0

10

00

1

1

0

m

B

y

y

y

b

B

b

B

c

y

M





























≡

















−

≡

−

−

mj

j

j

j

j

j

B

j

y

y

y

a

B

c

a

B

c

y

M

1

0

1

1

N

j

R

j

a

∈

,

oraz

gdzie oznaczają kolumny macierzy N.

∑

∈

−

=

R

j

j

j

x

y

y

x

0

00

0

∑

∈

=

−

=

N

R

j

j

ij

i

Bi

m

i

dla

x

y

y

x

,...,

1

,

0

Funkcja celu x

0

M funkcji ograniczeń

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Postać początkowej tablicy simpleksowej

N

B

b

B

x

c

N

B

c

b

B

c

x

x

B

N

B

B

N

1

1

1

1

0

−

−

−

−

−

−

].

0

,...,

0

[

=

x

N

b

x

c

x

x

B

N

N

−

−

0

0

dla przypadku gdy c

B

=0 tzn. pierwsze rozwiązanie bazowe dopuszczalne odpowiada za

punkt wierzchołkowy x

0

=

B

c

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Polepszanie rozwiązania bazowego dopuszczalnego

∑

∈

=

−

=

N

R

j

j

ij

i

Bi

m

i

dla

x

y

y

x

,...,

1

,

0

∑

∈

−

=

N

R

j

j

j

x

y

y

x

0

00

0

0

,

0

0

0

≤

↑

↑

≥

k

k

j

y

gdy

x

również

to

x

gdy

zatem

x

zawsze

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Polepszanie bazowego rozwiązania dopuszczalnego – metoda eliminacji
Gauss’a.

0

,

0

0

>

∈

=

<

ik

N

j

y

oraz

R

k

k

j

pewnego

dla

y

).

0

,

/

(

min

0

,...,

1

>

=

=

ik

ik

i

m

i

rk

y

y

y

θ

{ }

Br

rk

j

k

R

j

rk

rj

rk

r

k

x

y

x

y

y

y

y

x

N

1

0

−

−

=

∑

−

∈

{ }

Br

rk

ik

j

k

R

j

rk

rj

ik

ij

rk

r

ik

i

B

x

y

y

x

y

y

y

y

y

y

y

y

x

N

i

+













−

−













−

=

∑

−

∈

0

0

Gdy mamy nie-zdegenerowane rozwiązanie bazowe dopuszczalne takie, że

dla przynajmniej jednego i wówczas można z niego otrzymać lepsze bazowe
rozwiązanie dopuszczalne przez wymianę jednej z kolumn macierzy B na
kolumnę macierzy N.

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Polepszona tablica simpleks odpowiada za następne rozwiązanie bazowe

dopuszczalne o większej wartości funkcji celu.

...

/

1

...

/

...

/

...

...

...

/

)

/

(

...

)

/

(

...

...

...

/

...

)

/

(

...

)

/

(

...

...

...

0

0

0

0

0

0

0

0

00

0

rk

rk

rj

rk

r

k

rk

ik

rk

rj

ik

ij

rk

r

ik

i

Bi

rk

k

rk

rj

k

j

rk

r

k

Br

j

y

y

y

y

y

x

y

y

y

y

y

y

y

y

y

y

x

y

y

y

y

y

y

y

y

y

y

x

x

x

−

−

−

−

−

−

−

−

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

Algorytm simpleks dla ograniczeń mniejszościowych

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.

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 wchodzącej do bazy). Wybierz jako zmienną wchodzącą do

bazy taką zmienną

dla której

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

0

0

≥

j

y

N

R

j ∈

N

k

R

k

x

∈

,

.

0

0

<

k

y

{

}

0

,

0

0

0

min

≤

=

∈

j

j

R

j

k

y

y

y

N

k

x

Idż do kroku 4.

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 simpleks (prymalny) c.d.

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

względem zmiennych

oraz zmiennej

zgodnie z wyprowadzonym wzorem.

Podstaw

aby otrzymać nowe rozwiązanie bazowe dopuszczalne.

Idź do kroku 2.

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 4. (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.

Idż do kroku 5.

,

Br

x

).

0

,

/

(

min

0

,...,

1

>

=

=

ik

ik

i

m

i

rk

y

y

y

θ

r

B

x

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Schemat reguły przeliczenia współczynników w tablicy simpleks

wg metody eliminacji Gauss’a

p - element centralny (główny)

q – dowolny element w wierszu centralnym (głównym)

r – dowolny element w kolumnie centralnej (głównej)

s – dowolny pozostały element

























−

−

⇒













p

p

r

p

p

p

rq

s

q

s

r

q

1

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Zadanie programowania liniowego PL dla ograniczeń mniejszościowych

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

2

6

21

x

5

1

-1

0

x

4

1

1

5

x

3

-1

-2

0

x

0

x

2

x

1

Przykład:

Założenia:

1. Zbiór X rozwiązań dopuszczalnych

2. algorytm simpleks startuje z bazowego dopuszczalnego rozwiązania oraz w
trakcie jego realizacji nie występuje degeneracja

I. Zadanie programowania liniowego PL posiada jedno rozwiązanie

Rozwiązanie bazowe optymalne:

Wartość optymalna funkcji celu:

4

31

]

0

,

4

1

,

0

,

4

9

,

4

11

[

]

.

,

,

,

[

0

5

4

3

2

1

=

=

=

∧

x

x

x

x

x

x

x

T

T

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

0

≠

X