Metoda punktów wierzchołkowych 

 

Rozważmy zagadnienie PL w postaci zwyczajnej 

 

.)

.(

.....

2

2

1

1

Min

Max

x

c

x

c

x

c

F

n

n











 

 

Przy warunkach  

i

n

j

j

ij

r

x

a







1

  ,  gdzie  

l

i

...,

,

2

,

1



            (a) 

i

n

j

j

ij

r

x

a







1

  ,  gdzie  

k

l

i

...,

,

1





           (b) 

i

n

j

j

ij

r

x

a







1

  ,  gdzie  

l

k

i

...,

,

1





            (c) 

oraz 

0



j

x

,  gdzie  

n

j

,...,

2

,

1



. 

 

 

Wprowadzając zmienne uzupełniające 

k

n

n

n

x

x

x







...,

,

,

2

1

 

przekształca się postać zwyczajną zagadnienia PL do 

postaci standardowej 

 

k

n

n

n

n

x

x

x

c

x

c

x

c

F



















0

.....

0

.....

1

2

2

1

1

 

.)

.(Min

Max



 

Przy warunkach 

 

i

n

j

j

ij

r

x

a









1

1

  ,  gdzie  

m

i

...,

,

1



 

 

0



j

x

,  gdzie  

k

n

j





,...,

2

,

1

. 

 

 

 

 

Współczynniki 

ij

a  stojące przy zmiennych 

uzupełniających są równe: 

1 gdy nierówności są postaci (a) 

-1 gdy nierówności są postaci (b) 

Często zmienne uzupełniające oznacza się 

k

s

s

s

...,

,

,

2

1

 

nazywając je zmiennymi: 

niedoboru dla warunków (a) 

nadmiaru dla warunków (b) 

 

 

 

  

 

Metoda punktów wierzchołkowych 

Etapy metody punktów wierzchołkowych: 

1) Utworzenie modelu matematycznego. 

2)  Przekształcenie modelu do postaci standardowej. 

3) Określenie rzędu r macierzy współczynników 

ij

a  

postaci standardowej. 

4) Rozwiązanie 



















r

k

n

k

n

 układów równań 

utworzonych poprzez przyjęcie wartości zero dla 

r

k

n





 zmiennych. 

5) Obliczenie wartości funkcji celu w wyznaczonych 

punktach spełniających warunki nieujemności. 

6) Wybór punktu realizującego żądane ekstremum 

funkcji celu.