Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Конусом K називається множина точок лінійного векторного простору, що задовольняють умові

Лекція 6

У попередній лекції було встановлено, що допустима область задачі лінійного програмування являє собою опуклу множину із скінченою кількістю крайніх точок. Якщо ця множина обмежена (опуклий многограник), вона являє собою опуклу оболонку опорних планів. При доведенні теореми 5.3 обмеженість допустимої області було враховано вимогою відсутності невід’ємних, крім нульового, розв’язків системи Ax = 0. Ліва частина цієї системи співпадає з лівою частиною непрямих обмежень задачі лінійного програмування. Надалі будемо називати систему Ax = 0 відповідною однорідною системою, маючи на увазі її відповідність основній задачі.

х є K, yÎK Þ l1x + l2yÎ K, " l1, l2 ³ 0.

x2
 
 

 


0 x1

Мал.6.1. Приклад конусу.

На мал.6.1 показаний приклад конусу на площині. Зрозуміло, що конус являє собою окремий випадок опуклої множини.

Множина розв’язків відповідної однорідної системи утворює конус. Дійсно, якщо

Ax = 0 і A y = 0,

То помноживши перше рівняння на l1 ³ 0, а друге на l2 ³ 0 і взявши їх суму, отримуємо

l1 Ax + l2 Ay = 0, або A(l1x + l2y) = 0.

Теорема 6.1 (Про уявлення допустимої області задачі лінійного програмування у загальному випадку). Кожний допустимий розв’зок задачі лінійного програмування є сумою опуклої лінійної комбінації опорних планів і точки з конусу розв’язків відповідної однорідної системи.

Доведення. Доведення цієї теореми майже співпадає з доведенням попередньої. Відміна полягає у тому, що не накладається вимога обмеженості допустимої області. Тому, якщо для поданого допустимого розв’язку x0 стовпчики aj лінійно залежні, то у відповідній нетривіальній лінійній комбінації усі ненульові коефіцієнти можуть мати один і той же знак. При цьому побудований, як і при доведенні теореми 5.3, вектор l = (l1, l2, …, ln) має тільки невід’ємні координати.

Якщо взяти число p, що задовольняє співвідношенню

0 < p < min { x0 j / | lj | },

j N+

то вектор x0 можна записати у формі x0 = (x0 - pl) + pl, де x0 - pl –допустимий розв’язок з меншою кількістю ненульових координат ніж у x0, а pl– точка кунусу розв’язків відповідної однорідної системи. Продовжуючи аналогічно розкладання векторів, яким відповідають лінійно залежні aj, отримуємо

x0 = l~j xj ,+ y,

де y є сумою доданків типу pl, і тому задовольняє системі Ax = 0. Цим і завершується доведення теореми.

Тепер перейдемо до основної теореми, яка і дає обгрунтування аналітичного методу розв’язування задачі лінійного програмування.

Теорема 6.2 (Про існування оптимального опорного плану). Якщо задача лінійного програмування має оптимальний розв’язок, то вона завжди має оптимальний опорний план.

Доведення. Нехай x* - оптимальний розв’язок. З попередньої теореми маємо

x* = lj xj + y,

де lj = 1, lj ³ 0, j = 1, k.

Позначимо x= lj xj. Тоді x* = x+ y. Оскільки x* оптимальний розв’язок, F(x*) £ F(x) "x Î G, де G - допустима область. Звідси прямує, що F(y) ³ 0, бо інакше маємо F(y) < 0 Þ F(x* + ky) < F(x*) для k > 1, що суперечить оптимальності x*.

<== предыдущая лекция | следующая лекция ==>
Эффект Комптона. Изучая рассеяние рентгеновских лучей различными веществами, американский физик А | Тому отримуємо
Поделиться с друзьями:


Дата добавления: 2014-01-13; Просмотров: 382; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.