![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм симплекс-методу.
1. Симплекс-метод застосовується до канонічної задачі лінійного програмування, яка має вигляд:
де 2. Знаходиться початковий базисний розв’язок (опорний план)
3. Проводиться аналіз відносних оцінок небазисних змінних: - якщо всі відносні оцінки невід’ємні, то отриманий базисний розв’язок - якщо - якщо
Новий базисний розв’язок буде: Завдяки тому, що кількість вершин скінчена на деякому кроці буде здійснюватись вихід із циклу. Відомо, що симплекс-метод може бути використаний тільки для невироджених задач. Тобто, для задач в яких базисні розв’язки невироджені. Зауваження. Розв’язок вироджений, якщо При розрахунках зручно користуватись симплекс-таблицями. Якщо задача канонічна, то таблиця має вигляд:
Приклад. Нехай задано деяку стандартну задачу лінійного програмування: Зведемо цю задачу до канонічного виду:
Цю задачу тепер можна розв’язати за допомогою симплекс-методу. Побудуємо симплекс-таблицю.
Всі відносні оцінки невід’ємні. Отже, знайдений розв’язок є оптимальним розв’язком канонічної задачі 3. Симплексні перетворення. Відносні оцінки змінних. Критерій оптимальності базисного плану. Ознака необмеженості цільової функції. Алгоритм симплексного методу. Ознака необмеженості цільової функції Наведені у попередньому параграфі міркування складають основу симплекс-методу розв'язування ЗЛП. Перш, ніж сформулювати алгоритм цього методу, доведемо декілька необхідних для його обгрунтування тверджень. Теорема 1.4 (критерій оптимальності базисного розв'язку ЗЛП). Якщо для деякого базисного розв'язку Доведення. Нехай для базисного розв'язку
виконується умова теореми, тобто
Ми повинні довести, що для будь-якого допустимого розв'язку Дійсно, з умови теореми та з допустимості розв'язку
що і доводить теорему. Теорема 1.5 (критерій необмеженості цільової функції ЗЛП на допустимій множині). Якщо для деякого базисного розв'язку min Доведення. Нехай для базисного розв'язку виконується умова теореми де Дійсно, Обчислимо тепер значення цільової функції у точці
Через те, що
|