![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Двойственные задачи линейного программирования
Теоретические положения Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряженной по отношению к исходной. Теория двойственности используется для проведения качественных исследований задач линейного программирования. Рассмотрим экономический смысл двойственной задачи. В качестве исходной возьмем задачу, рассмотренную в первой лабораторной работе. Предположим, что некоторая организация решила закупить ресурсы, которыми располагает фирма (см. предыдущую задачу). Необходимо определить оптимальные цены на эти ресурсы. Под оптимальными в данном случае понимают цены, приемлемые как для продавца, так и для покупателя. Очевидно, что покупающая организация заинтересована в том, чтобы затраты Z на все ресурсы в количествах b Z = b С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная от продажи выручка была бы не менее выручки от реализации произведенной продукции. На изготовление единицы продукции первого вида расходуется a a Аналогично можно составить неравенства по другим видам продукции. Экономико-математическая модель и содержательная интерпретация полученной таким образом двойственной задачи приведены в таблице.
Таблица 2
Алгоритм составления двойственной задачи. 1. Составить расширенную матрицу системы A 2. Найти матрицу A 3. Сформулировать двойственную задачу на основе полученной матрицы A
Пример Используя в качестве исходной задачу линейного программирования из лабораторных работ № 1, 2, составить двойственную ей задачу и решить симплексным методом.
Условие исходной задачи
Система ограничений: x 2x x 3x Дополнительные условия задачи: x Линейная функция имеет вид: F=2x 1. Составим расширенную матрицу системы
2. Найдем транспонированную матрицу
A 3. Сформулируем двойственную задачу Z =18 y при ограничениях y 3 y Решение Введем дополнительные неотрицательные переменные y y 3 y Если в качестве основных переменных взять как в исходной задаче дополнительные переменные, то получим базисное решение: (0; 0; 0; 0; -2; -3). Наличие отрицательных компонент в решении свидетельствует о его недопустимости. Поэтому следует выбрать набор основных переменных, дающих допустимое решение. I шаг Основные переменные: y Неосновные переменные: y Выражаем основные переменные через неосновные y y Первое базисное решение Y II шаг Основные переменные: y Неосновные переменные: y После преобразований получим y y Z = 25 – (5/3) y Переменную y
|