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