6.2. Zadanie programowania liniowego

W przypadku, gdy funkcje

m

g

g

f

,

,

,

1

K

wstępujące w modelu matematycznym

zadania decyzyjnego, są liniowe oraz ich parametry są nielosowe model nazywamy modelem

programowania liniowego (PL). W ogólnym przypadku model taki możemy zapisać jako

jedno z dwóch zadań postaci:

PL-1. Zadanie na maksymalizację

PL-2. Zadanie na minimalizację

Można także rozważać przypadki, w których w tym samym układzie warunków występują

nierówności i równania. Nie zmniejszając ogólności rozważań, taki układy warunków mogą

Znaleźć wartość największą funkcji

n

n

n

x

c

x

c

x

c

x

x

x

f

+

+

+

=

...

)

,...,

,

(

2

2

1

1

2

1

przy ograniczeniach:











≥

+

+

+

≥

+

+

+

≥

+

+

+

m

n

mn

m

m

n

n

n

n

b

x

a

x

a

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

...

...

...

2

2

1

1

2

2

2

22

1

21

1

1

2

12

1

11

i warunkach brzegowych

0

,

,

,

2

1

≥

n

x

x

x

K

.

Znaleźć wartość największą funkcji

n

n

n

x

c

x

c

x

c

x

x

x

f

+

+

+

=

...

)

,...,

,

(

2

2

1

1

2

1

przy ograniczeniach:











≤

+

+

+

≤

+

+

+

≤

+

+

+

m

n

mn

m

m

n

n

n

n

b

x

a

x

a

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

...

...

...

2

2

1

1

2

2

2

22

1

21

1

1

2

12

1

11

i warunkach brzegowych

0

,

,

,

2

1

≥

n

x

x

x

K

.

być traktowane jako układy nierówności, ponieważ każde równanie można zapisać jako

koniunkcję dwóch nierówności:

b

x

a

x

a

x

a

n

n

=

+

+

+

...

2

2

1

1

⇔







≥

+

+

+

≤

+

+

+

b

x

a

x

a

x

a

b

x

a

x

a

x

a

n

n

n

n

...

...

2

2

1

1

2

2

1

1

.

Zwróćmy także uwagę, że każdą nierówność ze zwrotem „

≥

” można zamienić na

nierówność, w której wystąpi zwrot „

≤

”, mnożąc ją przez liczbę ujemną (np. przez -1).

Oznaczając przez:

n

m

ij

a

×

=

]

[

A

- macierz współczynników układu ograniczeń,

1

]

[

×

=

m

i

b

b

- wektor wyrazów wolnych dla ograniczeń,

1

]

[

×

=

n

j

c

c

- wektor współczynników funkcji celu,

1

]

[

×

=

n

j

x

x

- wektor zmiennych decyzyjnych

zadanie PL tradycyjnie zapisujemy jako:

Zbiór rozwiązań dopuszczalnych

n

R

X

⊂

, wyznaczony przez układ ograniczeń

i warunków brzegowych zadania PL, może być:

a) zbiorem pustym (

∅

=

X

) - mówimy wówczas, że zadanie PL jest sprzeczne;

b) zbiorem niepustym (

∅

≠

X

), który zawiera:

•

jeden element (

{ }

0

x

=

X

) - wówczas zadanie PL nie jest zadaniem decyzyjnym,

ponieważ

nie

dokonujemy

ż

adnego

wyboru

w

zbiorze

rozwiązań

dopuszczalnych;

•

więcej niż jeden element - wówczas zadanie PL jest zadaniem decyzyjnym.

Jeżeli zbiór rozwiązań dopuszczalnych

X

zadania PL zawiera co najmniej dwa

elementy, to jest wypukłym i domkniętym podzbiorem przestrzeni

n

R o skończonej liczbie

punktów wierzchołkowych, czyli jest

wielościanem (gdy jest zbiorem ograniczonym) lub

wielościennym zbiorem wypukłym (gdy jest zbiorem nieograniczonym).

Ponieważ funkcja celu

n

n

n

x

c

x

c

x

c

x

x

x

f

f

+

+

+

=

=

...

)

,...,

,

(

)

(

2

2

1

1

2

1

x

zadania PL jest

liniowa i jeśli zbiór

X

jest wypukłym i domkniętym wielościanem przestrzeni

n

R , to

PL-1:

















≥

≤

→

0

x

b

x

A

x

c

:

max

X

T

lub PL-2:

















≥

≥

→

0

x

b

x

A

x

c

:

min

X

T

korzystając z twierdzenia Weierstrassa, wyznaczamy wartości funkcji f w wierzchołkach

zbioru

X

i wybieramy z nich tę wartość, która jest największą (dla zadania

PL-1.) lub tę,

która jest najmniejszą (dla zadania

PL-2.). Punkt

w

x , czyli wierzchołek zbioru

X

, w którym

ta wartość jest przez funkcję f przyjmowana, nazywamy rozwiązaniem optymalnym i

oznaczamy jako

op

x . Jeśli funkcja celu osiąga swoją wartość optymalną (zgodnie z przyjętym

kryterium) w większej, niż jeden, liczbie wierzchołków, np.

w
s

w

w

x

x

x

,

,

,

2

1

K

, to rozwiązaniem

optymalnym zadania PL jest każda nieujemna i wypukła kombinacja tych wierzchołków,

czyli

w
s

s

w

w

op

x

x

x

x

α

α

α

+

+

+

=

L

2

2

1

1

dla

0

,

,

,

1

2

1

2

1

≥

∧

=

+

+

+

s

s

α

α

α

α

α

α

K

L

.

Jeśli zbiór

X

jest wielościennym zbiorem wypukłym (jest zbiorem nieograniczonym), to

funkcja

n

n

x

c

x

c

x

c

f

+

+

+

=

...

)

(

2

2

1

1

x

może w nim nie osiągać swoich kresów. Wówczas

zadania

PL-1 lub PL-2 mogą mieć nieograniczone rozwiązania optymalne (

∞

+

lub

∞

−

).

Własności zbioru rozwiązań dopuszczalnych oraz liniowość funkcji celu powodują, że

metody rozwiązywania zadań programowania liniowego wykorzystują wiedzę z algebry

liniowej. W szczególności zadania, w których występują dwie zmienne decyzyjne (lub liczba

zmiennych decyzyjnych może być zredukowana do dwóch) można rozwiązać metodą

graficzną. Z tą metodą zapoznać się można np. w pozycjach: [3] s. 11-18 a także [5] s. 18-35,

gdzie jest ona opisana i zilustrowana przykładami. Ogólną algebraiczną metodą

rozwiązywania zadań programowania liniowego o dowolnej liczbie zmiennych decyzyjnych

jest algorytm simpleks opisany w następnym punkcie.