МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" Інститут КНІТ Кафедра ПЗ ЗВІТ До лабораторної роботи № 1 На тему: “Розв’язування задачі лінійного програмування симплекс-методом” З дисципліни: “Дослідження операцій” Лектор: доц. каф. ПЗ Журавчак Л.М. Львів – 2010 Тема роботи: Задача лінійного програмування. Розв’язування задачі лінійного програмування симплекс-методом. Мета роботи: Ознайомитись із задачею лінійного програмування. Навчитись розв’язувати задачу лінійного програмування симплекс-методом. Теоретичні відомості Постановка задачі лінійного програмування Методи лінійного програмування - чисельні методи вирішення оптимізаційних задач, що зводяться до формальних моделей лінійного програмування. Як відомо, будь-яке завдання лінійного програмування може бути приведене до канонічної моделі мінімізації лінійної цільової функції з лінійними обмеженнями типу рівності. Оскільки число змінних в завданні лінійного програмування більше числа обмежень (
), то можна отримати рішення, прирівнявши нулю (
) змінних, які називаються вільними. Решта m змінних, які називаються базисними, можна легко визначити з системи обмежень звичайними методами лінійної алгебри. Якщо рішення існує, то воно називається базисним. Якщо задача лінійного програмування має оптимальні рішення, то хоча б один із них є базисним. Приведені міркування означають, що при пошуку оптимального рішення задачі лінійного програмування досить обмежитися перебором базисних допустимих рішень. Те, що не всі базисні рішення є допустимими, істотно проблеми не міняє, оскільки щоб оцінити допустимість базисного рішення, його необхідно отримати. В загальному постановка задачі має вигляд: Нехай маємо деякі змінні
і функцію цих змінних
, яка називається цільовою функцією. Потрібно найти екстремум (максимум чи мінімум) цільової функції
при умові, що змінні
належать деякій області
:
В залежності від виду функції
і області G розрізняють розділи математичного програмування: квадратичне програмування, випукле і ін. Лінійне програмування характеризується тим, що функція
і лінійною функцією змінних
і область G визначається системою лінійних рівнянь чи нерівностей. Симплекс-метод розв’язання задачі лінійного програмування Симплекс-метод застосовується до рішення будь-якої задачі лінійного програмування. Симплекс метод в порівнянні з графічним методом забезпечує більш раціональне рішення задачі. Розпочинаючи з будь-якої вершини багатокутника, твореного обмеженнями, переходять до розрахунку тільки тієї вершини, в якій значення лінійної форми буде більшим, чим в попередніх. Решту варіантів не обчислюють. Тоді при кінцевому числі кроків може бути найдений оптимальний план. Таким чином, виконується впорядкований перебір вершин, при яких відбувається постійне збільшення лінійної форми. Тому симплекс-метод також називають методом послідовного покращення оптимального плану. Рішення задачі симплекс-методом включає в себе два етапи. Спочатку потрібно найти вершину багатокутника обмежень, координати якої визначають початковий опорний план. Потім послідовно переходимо від однієї вершини багатокутника до іншої, яка сусідня попередній. Так як прилеглих вершин багато, то кожний раз вибирається така вершина, при переході до якої забезпечується найбільший приріст лінійної форми. На кожному кроці процесу покращення плану виконується перевірка на оптимальність. Очевидно, що план буде оптимальний, якщо серед вершин, які прилягають до даної, немає такої, при переході до якої відбувається ріст лінійної функції. Зазвичай, симплекс-метод реалізується у вигляді симплекс-таблиць. У першому стовпчику цієї таблиці зазначають вектори, які входять в базис. У другому – коефіцієнти цільової функції, які відповідають векторам, що входять в базис. Третій стовпчик – компоненти опорного плану. Головною перевагою симплекс-методу є його універсальність, будь-яку задачу лінійного програмування можна з легкістю вирішити як за допомогою програмного забезпечення так і вручну. Якщо обчислення і створення симплекс-таблиць пишеться вручну, то єдиною трудністю може стати обчислення: якщо велика кількість обмежень через неуважність можна отримати хибне рішення. Завдання Знайти розв’язок задачі лінійного програмування симплекс-методом, використовуючи програмний засіб MathCad. Цільова функція та обмеження:
Код та результати роботи
Висновок