![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Поняття виродженості задач лінійного програмування та спосіб усунення зациклювання у симплекс-методі
В пункті 1.4.1 алгоритм симплекс-методу розглядався у припущенні, що задача невироджена. Нехай тепер дана КЗЛП, для якої Нехай У випадку невиродженої ЗЛП симплекс-метод за скінчену кількість кроків дає можливість одержати оптимальний розв’язок або встановити факт нерозв’язуваності задачі. Це випливає з того, що кожному базисному розв’язку відповідає свій базис. Кількість базисів не перевищує Для вироджених задач лінійного програмування вироджений розв’язок, у якого кількість додатних компонент менше кількості базисних векторів, може бути або початковим, або виникнути у процесі розв’язування задачі. Наприклад, розглянемо задачу
Вектор Поточний базисний розв’язок може стати виродженим у ситуації, коли, користуючись симплекс-методом, неоднозначно визначається вектор, який треба вивести з базису. Тобто мінімальне значення Тоді, вводячи в базис вектор Нехай Припустимо, що для нього існує від’ємна оцінка
Переходимо до нового базису, замінюючи вектором Але, якщо хоча б одне з чисел А повний базисний розв’язок
Тобто, нові значення базисних координат співпадають із старими значеннями, і значення цільової функції після цієї ітерації залишається незмінним. Отже, змінився лише базис: замість базису У зв’язку зі зміною складу базисних змінних зміняться оцінки Оскільки число наборів базисних векторів скінчене, то після деякого числа “холостих” ітерацій приходимо до одного з висновків: а) розв’язок оптимальний; б) задача нерозв’язувана; в) отриманий базисний розв’язок був на попередніх ітераціях. Останній висновок означає, що процес обчислення зациклився, тобто після ряду ітерацій ми повертаємося до вже раніше використаного базису. Тому в алгоритмі симплекс-методу передбачена процедура, що усуває зациклювання. Нехай Якщо Якщо Якщо Гарантується, що знайдеться таке Приклад 1.14.
Приведемо задачу до канонічної форми:
Початковим опорним розв’язком є вектор Таблиця 1.21.
На першій ітерації Оптимальним розв’язком буде вектор Розглянемо геометричну інтерпретацію цього прикладу
Рис.1.4.
Через точку
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-06; просмотров: 1155; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.22.81.151 (0.013 с.) |