Властивості задачі лінійного програмування

Властивості задачі лінійного програмування

3.1 Форми ЗЛП
3.2 Еквівалентність форм ЗЛП
3.3 Множина допустимих

3.3 Множина допустимих розв’язків ЗЛП (багатогранні множини, багатогранники, вершини, грані)

Гіперплощина

Напівпростори

Напівпростори

Відкриті ніпівпростори:

Нормаль

Самостійно № 2
Довести, що куля є опуклою множиною.

Твердження.
Перетин довільного числа опуклих множин також є опуклою множиною
(Самостійно №3)

Визначення.
Множина, утворена перетином скінченого числа напівпросторів і гіперплощин (якщо цей

1

-1

2

4

4

3

A

C

D

B

F

E

2

-2

2

-1

3

3

Твердження.
Багатогранна множина є опуклою множиною
(Самостійно №4)

Будь-яка багатогранна множина може бути представлена як множина розв’язків системи із

(3)

Визначення вершини

Визначення вершини

Властивості вершин

Міцність множини активних в вершині обмежень

Приклад екзаменаційного завдання

Властивості вершин

Дана ЗЛП:

①

②

③

④

⑤

⑥

НЕ ВЕРШИНА!!!

Властивості вершин

Дана ЗЛП:

①

1

-1

②

③

2

4

4

④

3

A

C

D

B

F

E

①

②

③

④

⑤

⑥

⑤

⑥

Властивості вершин

Дана ЗЛП:

①

②

③

④

⑤

⑥

Властивості вершин

Дана ЗЛП:

①

1

-1

②

③

2

4

4

④

3

A

C

D

B

F

E

①

②

③

④

⑤

⑥

⑤

⑥

Виродженість

Алгоритм знаходження усіх вершин

Самостійно № 5
Запропонувати алгоритм знаходження всіх вершин багатогранної

Приклад екзаменаційного завдання

Теорема.
Будь-яка багатогранна множина має не більш кінцевого числа вершин.
Самостійно №

Cамостійно №
Показати, що визначення вершини співпадає з визначенням грані розмірності 0

Властивість грані

Приклад (1)

Приклад (2)

Приклад (3)

Приклад (4)

Cамостійно №

Cамостійно №

Теорема

Теорема (про представлення багатогранника).