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

Двоїстий симплекс-метод В силу теорем двоїстості при розв’язанні прямої задачі, одночасно з її оптимальним розв’язком ми отримуємо оптимальний розв’язок двоїстої задачі або втсановлюємо нерозв’язність обох задач. При цьому для задачі в кононічній формі
, де x* i y* - оптимальні розв’язки прямої та двоїстої задачі, а В оптимальний базис. Дана властивість приводить до іншого методу вирішення задачі лінійного програмування, а саме, двоїстого симплекс методу. Загальні правила побудови двоїстої задачі: кожному обмеженню вихідної задачі відповідає двоїста змінна; матриці обмежень взаємно транспоновані; праві частини системи обмежень однієї задачі є коефіцієнтами при відповідних змінних цільової функції іншої задачі. При цьому максимізація цільової функції замінюється на мінімізацію, і навпаки; кожному обмеженню-нерівності вихідної задачі відповідає в двоїстій задачі умова невід’ємності відповідної двоїстої змінної, а рівності - довільна двоїста змінна. Основна теорема двоїстості. Якщо одна з пари двоїстих задач лінійного програмування має розв’язок, то і інша задача має розв’язок, і при цьому значення цільових функцій цих задач рівні: (Xопт)=F(Yопт) Завдання Розв’язати задачу лінійного програмування двоїстим симплекс-методом.
Код та результати роботи
Висновок На цій лабораторній роботі я ознайомився із поняттям двоїстості та навчився розв’язувати задачу лінійного програмування, використовуючи двоїстий симплекс-метод; для знаходження оптимального значення цільової функції було використано програмний засіб MathCad.