Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Zadanie programowania liniowego PL dla ograniczeń
mniejszościowych

przy ograniczeniach

:

( )

x

c

x

T

X

x

f

=

∈

max

0

≥

≤

x

b

x

A

dim x=n, dim c=n, dim A =[m x n], dim b

1

=m

1

,

Postać kanoniczna zadania PL

x

c

T

X

x

x =

∈

0

max

{

}

0

,

:

≥

=

=

x

b

Ax

x

X

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Podstawowe definicje

Jeśli dla układu równań liniowych Ax=b spełniony jest warunek rz[A

r

]=rz[A]

to mogą zaistnieć trzy następujące przypadki:

1.

rz[A] = m = n istnieje jedno rozwiązanie układu Ax=b.

2.

rz[A] = n < m istnieje jedno rozwiązanie układu równań, lecz przy tym

(m - n) równań jest zbędnych.

3. rz[A] = m < n istnieje nieskończenie wiele rozwiązań układu Ax=b , jest to

układ nieoznaczony.

Definicja macierzy bazowej B

Macierzą bazową B układu równań Ax = b rz[A] = m, n>m nazywamy nieosobliwą
macierz kwadratową o wymiarach (m*m) utworzoną z liniowo-niezależnych kolumn a

j

macierzy A.

Definicja rozwiązania bazowego

Rozwiązaniem bazowym układu równań Ax=b rz[A]=m, n>m nazywamy wektor

x

b

=B

-1

b utworzony ze zmiennych odpowiadających kolumnom a

j

macierzy bazowej B.

Składowe wektora bazowego x

b

są to zmienne bazowe.

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Rozwiązania bazowe

]

,

[

N

B

A =

m

B

B

=

≠

dim

,

0

det

]

,

[

N

B

x

x

x =

Definicja:

Rozwiązanie bazowe jest rozwiązaniem bazowym dopuszczalnym zadania
programowania liniowego PL

jeśli wektor x

B

jest nieujemny tzn.

Wówczas rozwiązanie bazowe dopuszczalne posiada nie więcej niż m dodatnich x

i

.

Definicja:

Niezdegenerowanym rozwiązaniem bazowym dopuszczalnym zadania PL nazywamy
rozwiązanie dopuszczalne , w którym nie wszystkie składowe x

i

są większe od zera.

0

≥

B

x

B- macierz bazowa nieosobliwa

N- macierz niebazowa

- wektor zmiennych bazowych odpowiadających kolumnom macierz B
- wektor zmiennych niebazowych odpowiadających kolumnom macierz N

N

B

x

x

0

]

0

,

[

1

=

=

=

−

N

B

B

x

b

B

x

x

x

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Extremum zadania programowania liniowego PL

T

B

x

x

]

0

,

[

=

Twierdzenie 5.1

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

Twierdzenie 5.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.:

Definicja:

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.

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Extremum zadania programowania liniowego PL

cd.

1

:

R

X

f

→

n

R

X ⊂

)

(

)

(

v

f

x

f

>

∧

Twierdzenie 5.3

Jeżeli funkcja określona na domkniętym i ograniczonym wypukłym
zbiorze jest ciągła i wypukła, to globalne maksimum 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

∧

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.

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Extremum zadania programowania liniowego PL

cd.

1

,...,

1

,

0

,

1

1

=

=

≥

=

∑

∑

=

=

∧

∧

p

i

i

i

p

i

i

i

p

i

x

X

λ

λ

λ

∧

∧

∧

p

x

x

x

.....

,

2

1

Twierdzenie 5.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ć:

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Pierwsze rozwiązanie bazowe

N

B

x

N

B

b

B

x

1

1

−

−

−

=

N

N

B

B

x

c

N

B

c

b

B

c

x

)

(

1

1

0

−

−

=

−

−

N

N

B

B

B

x

N

B

c

N

B

c

b

B

b

B

c

x

x













−

−













=













−

−

−

−

1

1

1

1

0

Poszukiwanie rozwiązań bazowych
dopuszczalnych

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Pierwsze rozwiązanie bazowe dopuszczalne

N

B

x

N

B

b

B

x

1

1

−

−

−

=

N

N

B

B

x

c

N

B

c

b

B

c

x

)

(

1

1

0

−

−

=

−

−

N

N

B

B

B

x

N

B

c

N

B

c

b

B

b

B

c

x

x













−

−













=













−

−

−

−

1

1

1

1

0

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

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

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Postać początkowej tablicy simpleksowej

N

b

x

c

x

x

B

N

N

−

−

0

0

N

B

b

B

x

c

N

B

c

b

B

c

x

x

B

N

B

B

N

1

1

1

1

0

−

−

−

−

−

−

dla przypadku gdy c

B

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

punkt wierzchołkowy x=0.

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

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

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Polepszanie bazowego rozwiązania dopuszczalnego

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.

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Optymalne rozwiązanie zadania programowania liniowego PL metodą

simpleks

Twierdzenie 5.5

Twierdzenie 5.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

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Pierwsza tablica simpleks-I rozwiązanie bazowe dopuszczalne

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

0

0

0

0

00

0

mk

mj

m

Bm

rk

rj

r

Br

ik

ij

Bi

k

j

k

j

y

y

y

x

y

y

y

x

y

y

y

x

y

y

y

x

x

x

iO

−

−

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

0

0

0

0

00

0

mk

mj

m

Bm

rk

rj

r

Br

ik

ij

Bi

k

j

k

j

y

y

y

x

y

y

y

x

y

y

y

x

y

y

y

x

x

x

iO

−

−

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

0

0

0

0

00

0

mk

mj

m

Bm

rk

rj

r

Br

ik

ij

Bi

k

j

k

j

y

y

y

x

y

y

y

x

y

y

y

x

y

y

y

x

x

x

iO

−

−

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

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

−

−

−

−

−

−

−

−

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Algorytm simpleks (prymalny)

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

=

≥

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

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

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 4

Wydział Elektroniki PWr

EiT III r. subkier. EKA

Schemat reguły przeliczenia współczynników zmiennych 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