Міністерство освіти і науки Національний університет «Львівська політехніка» Інститут комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління / Лабораторна робота №1.2 з дисципліни «Математичні методи дослідження операцій» Львів 2018 Лабораторна робота №1.2 Постановка задачі лінійного програмування та її розв’язання методом симплекс-таблиць та методом штучного базису. Мета роботи: вивчення симплекс-методу (табличний та зі штучним базисом) для знаходження розв’язку; робота з програмою SimplexWin для програмного обчислення розв’язку задачі симплекс-методу зі штучним базисом. Теоретичні відомості: 1.1 Симплекс метод Симплекс-метод - це метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку. Досить часто симплекс-метод ще називають методом покращення плану. Симплекс-метод - найбільш загальний алгоритм, що використовується для рішення таких задач. Даний метод був розроблений американським математиком Джорджем Данцігом у 1947 році.  Основна ідея симплекс-метода полягає в тому, що екстремум цільової функції завжди досягається в кутових точках області допустимих рішень. Симплекс-метод реалізує перебір кутових точок області допустимих рішень у напрямі поліпшення значення цільової функції. Основна ідея цього методу наступна. Перш за все, знаходиться яке-небудь допустиме початкове (опорне) рішення, тобто яка-небудь кутова точка області допустимих рішень. Процедура методу дозволяє відповісти на питання, чи є це рішення оптимальним. Якщо "так", то завдання вирішене. Якщо "ні", то виконується перехід до суміжної кутової точки області допустимих рішень, де значення цільової функції поліпшується, тобто до негіршого допустимого рішення. Якщо деяка кутова крапка має декілька суміжних, то обчислювальна процедура методу забезпечує перехід до тієї з них, для якої поліпшення цільової функції буде найбільшим. Процес перебору кутових точок області допустимих рішень повторюється, поки не буде знайдена крапка, якою відповідає екстремум цільової функції. Метод штучного базису Метод штучного базису застосовується в тих випадках коли система обмежень задачі лінійного програмування не містить одиничну матрицю порядку m. Розглянемо задачу лінійного програмування: / / / Отримаємо одиничну матрицю додаванням штучних змінних лише в ті рівняння, які не розв’язані відносно базисних змінних. / Нехай штучну змінну введено у кожне рівняння: / / область допустимих розв’язків задачі розширилась. Задача з даною системою обмежень називається розширеною, або М-задачею Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві Для того, щоб у результаті процедур симплексних перетворень виключалися з базису штучні змінні, потрібно ввести їх у цільову функцію з великими від’ємними коефіцієнтами. Нехай величина М є достатньо великим за модулем числом. Цільова функція для задачі максимізації (мінімізації): / / Якого б малого значення не набувала відповідна коефіцієнту штучна змінна / , значення цільової функції / буде від’ємним для задачі на максимум та додатним для задачі на мінімум і водночас значним за модулем. Тому процедура симплексного методу одразу вилучає відповідні змінні з базису і забезпечує знаходження плану, в якому всі штучні змінні / Якщо в оптимальному плані розширеної задачі існує хоча б одне значення /, то це означає, що початкова задача не має розв’язку, тобто система обмежень несумісна. Для розв’язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му — ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком. Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою. Теорема Якщо в оптимальному плані/розширеної задачі штучні змінні/ то план/ є оптимальним планом початкової задачі. Виконання лабораторної роботи: Індивідуальне завдання: Варіант 70 Цільова функція: