Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Двоїстість. Модифікований симплекс-метод
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт
Предмет:
Інші
Група:
ПІ
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
Інститут КНІТ
Кафедра ПЗ
ЗВІТ
До лабораторної роботи № 2
На тему: “ Двоїстість. Модифікований симплекс-метод”
З дисципліни: “Дослідження операцій”
Лектор:
доц. каф. ПЗ
Журавчак Л.М.
Львів – 2010
Тема роботи: Задача лінійного програмування. Розв’язування задачі лінійного програмування двоїстим симплекс-методом.
Мета роботи: Ознайомитись із поняттям двоїстості. Навчитись розв’язувати задачу лінійного програмування двоїстим симплекс-методом.
Теоретичні відомості
Кожній задачі лінійного програмування можна певним чином поставити у відповідність деяку іншу задачу (лінійного програмування), яка називається двоїстою або зв'язаною по відношенню до вихідної або прямої задачі. Дамо визначення двоїстої задачі по відношенню до загальної задачі лінійного програмування, що полягає в знаходженні максимального значення функції. Пряма задача має вигляд:
Тоді двоїста до неї задача запишеться так:
Двоїстий симплекс-метод
В силу теорем двоїстості при розв’язанні прямої задачі, одночасно з її оптимальним розв’язком ми отримуємо оптимальний розв’язок двоїстої задачі або втсановлюємо нерозв’язність обох задач. При цьому для задачі в кононічній формі , де x* i y* - оптимальні розв’язки прямої та двоїстої задачі, а В оптимальний базис. Дана властивість приводить до іншого методу вирішення задачі лінійного програмування, а саме, двоїстого симплекс методу.
Загальні правила побудови двоїстої задачі:
кожному обмеженню вихідної задачі відповідає двоїста змінна;
матриці обмежень взаємно транспоновані;
праві частини системи обмежень однієї задачі є коефіцієнтами при відповідних змінних цільової функції іншої задачі. При цьому максимізація цільової функції замінюється на мінімізацію, і навпаки;
кожному обмеженню-нерівності вихідної задачі відповідає в двоїстій задачі умова невід’ємності відповідної двоїстої змінної, а рівності - довільна двоїста змінна.
Основна теорема двоїстості.
Якщо одна з пари двоїстих задач лінійного програмування має розв’язок, то і інша задача має розв’язок, і при цьому значення цільових функцій цих задач рівні:
(Xопт)=F(Yопт)
Завдання
Розв’язати задачу лінійного програмування двоїстим симплекс-методом.
Код та результати роботи
Висновок
На цій лабораторній роботі я ознайомився із поняттям двоїстості та навчився розв’язувати задачу лінійного програмування, використовуючи двоїстий симплекс-метод; для знаходження оптимального значення цільової функції було використано програмний засіб MathCad.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора