Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

EiT III r. sub-kier. EKA

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

EiT III r. sub-kier. EKA

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

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

EiT III r. sub-kier. EKA

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

EiT III r. sub-kier. EKA

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

EiT III r. sub-kier. EKA

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

EiT III r. sub-kier. EKA

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

=

∀

≥

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 7

Wydział Elektroniki

EiT III r. sub-kier. EKA

Przykład II zadania programowania liniowego

cd.

dualna metoda simpleks

1

-3

1

X

3

-1

1

1

x

1

1

-2

4

X

2

0

1

-5

-x

0

-x

4

-x

5

1

-3

1

X

4

1

-2

2

X

1

-1

1

3

X

2

0

1

-5

-X

0

-x

3

-x

5

[

]

T

T

x

x

x

x

x

x

0

0

1

4

1

1
5

1
4

1
3

1
2

1

1

1

=













=

∧

∧

∧

∧

∧

∧

tablica optymalna I

tablica optymalna II

Rozwiązanie optymalne I
wierzchołek:

Rozwiązanie optymalne II
wierzchołek:

[

]

T

T

x

x

x

x

x

x

0

1

0

3

2

2

5

2

4

2

3

2

2

2

1

2

=













=

∧

∧

∧

∧

∧

∧

5

0

=

∧

x













+

−

=













−

+













=

∧

λ

λ

λ

λ

3

2

3

2

)

1

(

4

1

x

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

EiT III r. sub-kier. EKA

Przykład III – przykład praktyczny

Minimalizacja strat w procesie cięcia dłużyc

3

2

1

0

3

.

0

6

.

0

2

.

0

min

x

x

x

X

x

+

+

=

∈

x













≥

≥

+

+

≥

+

+

=

0

,

2400

7

3

0

1200

0

1

2

:

3

2

1

3

2

1

x

x

x

x

x

x

x

x

X

T

T

x

x

x

x

]

300

,

0

,

600

[

]

,

,

[

3

2

1

=

=

∧

∧

∧

∧

Dane procesu cięcia: Zamówienie na 300 kompletów belek

1 zestaw belek składa się z: 4 belek po 2,5 m i 7 belek po 0,7 m

Minimalizacja strat w wyniku cięcia dłużyc

Wektor zmiennych decyzyjnych:

210

=

∧

o

x

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

EiT III r. sub-kier. EKA

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

EiT III r. sub-kier. EKA

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

EiT III r. sub-kier. EKA

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

I.1 - technika zadania pomocniczego
I.2 - technika pomocniczej funkcji celu

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

EiT III r. sub-kier. EKA

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

EiT III r. sub-kier. EKA

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

EiT III r. sub-kier. EKA

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

=

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

EiT III r. sub-kier. EKA

Ad.I.2 Pomocnicza funkcja celu

Uproszczona wersja I fazy metoda dwufazowej simpleks – uzyskanie

bazowego rozwiązania dopuszczalnego

{

}

m

i

dla

y

y

r

i

i

i

,...,

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 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

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

EiT III r. sub-kier. EKA

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.

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

EiT III r. sub-kier. EKA













>

=

=

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

EiT III r. sub-kier. EKA

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

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

EiT III r. sub-kier. EKA

Przypadki szczególne dla zadania programowania

liniowego

1.

Zadanie programowania liniowego PL posiada jedno rozwiązanie

2.

Zadanie programowania liniowego – nieograniczone

3.

Zadanie programowania liniowego – posiadające nieskończoną liczbę
rozwiązań optymalnych na zbiorze ograniczonym

4.

Zadanie programowania liniowego – posiadające nieskończoną liczbę
rozwiązań optymalnych na zbiorze nieograniczonym

5.

Zadanie programowania liniowego – zbiór rozwiązań dopuszczalnych

jest zbiorem pustym - brak rozwiązania.

Zadania 2,3 i 4 – rozwiązanie II fazy algorytmu PL analogicznie jak w
prymalnej metodzie simpleks.

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki

EiT III r. sub-kier. EKA

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