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. Якщо цільова функція досягає екстремального значення в двох сусідніх вершинах многокутника (многогранника) допустимих розв'язків, то вона досягає цього ж значення і в кожній точці ребра (грані-частини), що з'єднує ці точки.


 

А также другие работы, которые могут Вас заинтересовать

60893. Подорожуючи Францією 523.5 KB
  Entendez –vous les coups de fusil? C’ect l’hiver de 1792. La France est en guerre avec l’Autriche. Dans quelques jours l’armeé française quitte la ville, elle va lutter contre l’ennemi.
60897. Лінійні алгортми. Побудова блок – схеми алгоритму 44.5 KB
  Багаторядкове поле редагування Memo. Розв‘язок: c = ; Блок – схема Багаторядкове поле Memo. Компонента Memo знаходиться на закладці Stndrd. Приберіть із багаторядкового поля рерагування слово Memo1.
60898. Моделирование пистолета. Полигональное моделирование 484.5 KB
  Начнём с установки нашего изображения. Зайдите в Material Editor (кнопка M), выберите один материал, зайдите в свиток Map, в Diffuse color выберите карту Bitmap и поставьте это изображение.
60899. Полигональное моделирование. Общие сведения 1.04 MB
  Полигональное моделирование является одним из основных способов моделирования. При полигональном моделировании изменяют форму объекта, непосредственно воздействуя на его составляющие.