![]()
Заглавная страница
Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Обгрунтування симплекс-методу для невироджених задач лінійного програмування
Нехай дана задача лінійного програмування у канонічному виді:
Або у векторній формі
де Припустимо, що задача (1.4.1) має допустимий розв’язок і ранг матриці Якщо Припустимо, що Введемо необхідні означення. Ненульовий допустимий розв’язок Набір векторів Максимальне число лінійно незалежних векторів дорівнює Базисом базисного розв’язку назвемо упорядкований набір з Оскільки невироджений базисний розв’язок містить рівно Приклад 1.7. Нехай обмеження ЗЛП мають вигляд
В цьому прикладі Допустимими розв’язками будуть, наприклад, такі вектори:
Вектори Для Для Для базисного невиродженого розв’язку Теорема 1.4.1. Вектор Доведення. Необхідність. Нехай Тоді Доведемо необхідність від супротивного, а саме, припустимо, що Але тоді
З (1.4.2) отримаємо
За умовою, Достатність. Нехай Нам треба довести, що
За умовою
Помноживши ліву і праву частини рівності (1.4.3) на
Вибираючи
допустимі розв’язки ЗЛП (1.4.1). Крім того, Але тоді З теореми 1.4.1 випливає скінченність числа вершин многогранника допустимих розв’язків будь-якої ЗЛП. Кожній вершині відповідає певна лінійно незалежна підсистема системи векторів Перехід від однієї вершини до іншої — це перехід від одного базисного розв’язку до іншого. Лема 1.4.1. Нехай дано систему
її базис. Замінимо у цьому базисі який-небудь з векторів
за базисом Доведення. Необхідність. Якщо Достатність. Нехай
Зауважимо, що
Тобто, для вектора Знайдемо тепер координати усіх векторів
Нехай
Нехай
Тоді
Так
Для введеного до базису вектора
Формули (1.4.9) також можна отримати із загальних (1.4.10). Дійсно, для
Тоді
Надалі коефіцієнт Тоді При обчисленнях нових координат зручно користуватися таблицями (табл.1.2). Тут у клітинках наведені відповідні координати вектора, до якого відноситься даний стовпець, у старому базисі; вертикальною стрілкою (зверху) відмічено вектор ( Таблиця 1.2.
Щоб отримати Для того, щоб у відповідності з формулами (1.4.10) отримати будь-яку, наприклад, Елементи головної діагоналі перемножуються (причому у ведучій клітинці використовується нове значення 1) і з цього добутку віднімається добуток елементів додаткової діагоналі (причому у відповідній клітинці ведучої строчки знову береться нове значення). Тобто, Приклад 1.8. Нехай
Вектори Базисна матриця, складена з векторів
Координати будь-якого вектора
де
Координати базисних векторів Отже,
Підрахуємо тепер координати векторів
Переконаємося, що заміна у початковому базисі вектора У нашому випадку Тоді координати векторів
Координати базисних векторів відомі.
Проводячи обчислення по таблиці прийдемо до тих же результатів: Таблиця 1.3.
Координати векторів у новому базисі наведені у таблиці 1.4. Таблиця 1.4.
Введемо поняття оцінки вектора. Нехай вектори
Для усіх базисних векторів оцінки дорівнюють нулеві. Дійсно, якщо Нехай дана КЗЛП (1.4.1) і припустимо, що всі її базисні розв’язки невироджені. Надалі назвемо ЗЛП невиродженою, якщо всі її базисні розв’язки невироджені. Теорема 1.4.2. (про можливість поліпшення базисного розв’язку) Якщо для даного невиродженого базисного розв’язку задачі (1.4.1) існує така від’ємна оцінка Доведення. Нехай
Оскільки Координати вектора
де Для того, щоб новий базисний розв’язок
Згідно умов теореми і враховуючи, що Якщо ж Знайдемо тепер значення цільової функції при новому базисному розв’язку:
Додаючи до цієї суми
Або Оскільки Теорема 1.4.2 дає достатні умови того що є кращий, ніж даний, розв’язок задачі, і правило для знаходження відповідного базису. Що можна сказати про існування кращого базисного розв’язку чи про можливість розв’язання задачі, якщо порушуються умови теореми: або всі оцінки Теорема 1.4.3. (критерій оптимальності базисного розв’язку) Якщо для даного базисного розв’язку всі оцінки Доведення. Нехай Візьмемо інший допустимий розв’язок Якщо б інших допустимих розв’язків не було, тоді єдиний допустимий розв’язок Покажемо, що Оскільки
Оскільки
Але
Але ж
Оскільки розклад будь-якого вектора по базису єдиний, то
Підставляючи це в (1.4.12), дістанемо
що і треба було довести. Теорема 1.4.4. (ознака необмеженості цільової функції) Якщо для якого-небудь базисного розв’язку існує хоча б одна оцінка Доведення. Нехай, наприклад, Розглянемо вектор Вектор
Підрахуємо тепер значення цільової функції для побудованого допустимого розв’язку
Оскільки Зауваження. Теореми 1.4.3 та 1.4.4 справедливі і без припущення невиродженості базисних розв’язків. Дійсно, легко бачити по доведенням, що фактично використовувалась не умова Розглянемо тепер випадок, коли умови теореми 1.4.2 не виконані: хоча і є Покажемо, що якщо дана задача невироджена (що ми і припускали), то такого випадку просто не може бути. Дійсно, нехай
Оскільки
Очевидно, що Хоч розв’язок, що відповідає новому базису, і допустимий, він виявляється виродженим, бо принаймні одна з його базисних координат ( Отже, для невироджених ЗЛП можливі лише три випадки: 1. Усі 2. Існує 3. Існують оцінки
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-06; просмотров: 447; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.232.177.219 (0.075 с.) |