Przypomnijmy, że rozważamy problem

optymalizacji liniowej w postaci

FC:

1

2

1 1

2 2

( ,

,....,

)

.....

MAX(MIN)

n

n n

Z x x

x

c x

c x

c x

=

=

+

+

+

→

O:

WB:

11 1

12 2

1

1

21 1

22 2

2

2

1 1

2 2

.....

.....

.............................

.....

n n

n n

m

m

mn n

m

a x

a x

a x

b

a x

a x

a x

b

a x

a

x

a

x

b

+

+

+

=

+

+

+

≤

+

+

+

≥

0,

1, 2,.....,

j

x

j

n

≥

=

0,

1, 2,.....,

i

b

i

m

≥

=

Jeżeli ograniczenia są równościami to

mówimy o postaci standardowej ZPL i
możemy je zapisać następująco:

1

FC:

MAX(MIN)

n

j j

j

Z

c x

=

=

→

∑

1

O:

n

ij j

i

j

a x

b

=

=

∑

0,

1, 2,.....,

i

b

i

m

≥

=

WB:

0,

1, 2,.....,

j

x

j

n

≥

=

wykorzystując zapis macierzowy ZPL w

postaci standardowej możemy zapisać
następująco:

(

)

Z

=

→

T

FC:

c x

MAX MIN

=

O: Ax b

0,

≥

b

0

≥

WB: x

gdzie:

11

12

1

21

22

2

1

2

n

n

m

m

mn

a

a

a

a

a

a

a

a

a













=













⋯

⋯

⋮

⋮

⋱

⋮

⋯

A

1

2

n

c

c

c

 

 

 

=

 

 

 

⋮

c

1

2

n

x

x

x

 

 

 

=

 

 

 

⋮

x

1

2

n

b

b

b

 

 

 

=

 

 

 

⋮

b

Metoda geometryczna

ZPL może mieć rozwiązania dopuszczalne

lub być zadaniem sprzecznym nie mającym
rozwiązania dopuszczalnego.

Jeżeli ZPL ma rozwiązania dopuszczalne, to

zachodzi jedna z trzech możliwości:

• istnieje jedno rozwiązanie optymalne

• istnieje wiele rozwiązań optymalnych

• brak rozwiązania optymalnego

Problem znajdowania rozwiązania ZPL

metodą geometryczną sprowadza się do:

• wyznaczania półpłaszczyzn

odpowiadających poszczególnym

nierównościom

• znalezienia części wspólnej dla wszystkich

półpłaszczyzn, czyli zbioru rozwiązań

dopuszczalnych (ZRD)

• wyszukania w ZRD rozwiązania

najlepszego dla przyjętej funkcji celu

(rozwiązania optymalnego)

Jeżeli ZRD jest zbiorem pustym lub zbiorem

nieograniczonym w kierunku wzrostu

wartości funkcji celu dla zadania na

maksimum bądź spadku dla zadania na

minimum, to zadanie nie ma rozwiązania

optymalnego.