28481

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

Доклад

Математика и математический анализ

Основні властивості розв’язків задач лінійного програмування. Множина розв'язків нерівності заповнює суцільно одну із півплощин на які ділить площину гранична пряма аі1 x1 ai2 Х2= b Леми 1 та 2 дозволяють сформулювати:Властивість 1. Сукупність допустимих розв'язків задачі ] 2 заповнює опуклий многокутник або є порожньою множиною. Оптимальним розв’язком задачі ] 2називається такий її допустимий план на якому цільова функція 1 досягає екстремального найбільшого або найменшого значення.

Украинкский

2013-08-20

19.37 KB

2 чел.

9.22.Основні властивості розв’язків задач лінійного програмування.

Множина розв'язків нерівності заповнює суцільно одну із півплощин, на які ділить площину гранична пряма аі1 x1 +ai2 Х2= b

Леми  1 та 2 дозволяють сформулювати:Властивість 1. Сукупність допустимих розв'язків задачі (])—(2) заповнює опуклий многокутник або є порожньою множиною.Означення. Оптимальним розв’язком задачі (])—(2)називається такий її допустимий план, на якому цільова функція (1) досягає екстремального (найбільшого або найменшого) значення.Властивість 2. Якщо задача (1)—(2) має єдиний розв"язок, то він знаходиться в одній із вершин многокутника допустимих розв'язків.

При доведенні властивості 2 суттєво використовується те, що многокутник допустимих розв"язків обмежений.Нехай многокутник — необмежена множина, наприклад, яка зображена на мал.1.Проведемо пряму x1 + х2 =?. Тоділдляозрізаного   многокутника справедлива    властивість 2. Для визначеності нехай цільова функція (1) максимізується. Якщо максимум досягається у вершині А1 або В1, то збільшення r приводить до збільшення цільової функції і в граничному переході отримано zmax = . Аналогічно розглядається випадок z min = - Зауваження. Властивості 1 і 2 залишаються в силі і для випадку п > 2. При цьому многокутник допустимих розв'язків стає опуклим м н о г о г р а н н и к о м    д о п у с т и м и х    р о з в ' я з к і в. Гранична пряма — площиною (n = 3) або гіперплощиною (n > 3), півплощина — півпростором, вершина многокутника — вершиною многогранника.Властивість 3. Якщо цільова функція досягає екстремального значення в двох сусідніх вершинах многокутника (многогранника) допустимих розв'язків, то вона досягає цього ж значення і в кожній точці ребра (грані-частини), що з'єднує ці точки.