Главная » Справочник » Основы организации и управления транспортными системами » Двойственные задачи линейного программирования

Двойственные задачи линейного программирования

Каждой прямой задаче линейного программирования соответствует двойственная задача, решение которой позволяет получить дополнительные параметры оптимизируемого транспортного процесса. Например, в прямой задаче требуется определить объемы транспортной работы различного вида, так, чтобы получить максимальную прибыль, при условии, что расход ресурсов для выполнения транспортных работ, не превышает ограниченных запасов по каждому ресурсу.

В такой задаче неизвестными являются объемы выполненной транспортной работы различного вида, коэффициентами при неизвестных в целевой функции – прибыль, которую приносит каждый вид транспортной работы, коэффициентами при неизвестных в уравнениях системы ограничений – расход ресурсов на выполнение единицы транспортной работы каждого вида, а постоянными в правой части каждого уравнения системы ограничений – размер запаса каждого ресурса.

Решение же двойственной задачи дает ответ на вопрос о том, по какой цене необходимо приобретать ресурсы, чтобы при установленных тарифах на транспортную работу каждого вида минимизировать суммарные затраты на выполнение работ. В такой двойственной задаче неизвестными являются величины стоимости каждого вида ресурсов, коэффициентами при неизвестных в целевой функции – размеры запасов каждого вида ресурсов, коэффициентами при неизвестных в уравнениях системы ограничений – расход ресурсов на выполнение единицы транспортной работы каждого вида, а постоянными в правой части каждого уравнения системы ограничений – величина тарифа за выполнение единицы транспортной работы.

Для формулирования двойственной задачи применяют следующие правила:

каждому ограничению прямой задачи соответствует переменная двойственной задачи, которая называется двойственной объективной оценкой. Число двойственных оценок равно числу ограничений в исходной задаче;
каждой переменной исходной задачи соответствует ограничение двойственной задачи;
коэффициенты при переменных, стоящих в строках системы прямой задачи, становятся коэффициентами при переменных в столбцах системы двойственной задачи, то есть матрицы коэффициентов при переменных и в прямой, и в двойственной задаче получаются друг из друга транспортированием, т.е. заменой строк столбцами с сохранением их порядка;
знаки неравенств меняются на противоположные. Если в прямой задаче содержатся неравенства типа ≥, то в двойственной
наоборот, типа ≤;
свободные члены неравенств системы ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи;
правые части ограничений в двойственной задаче равны коэффициентам целевой функции исходной задачи;
требование минимизации целевой функции прямой задачи заменяется требованием максимизации целевой функции двойственной задачи.

Понятие двойственности широко используется в анализе задач линейного программирования и их экономической интерпретации. В результате решения задачи линейного программирования получаем два описания транспортного процесса: одно математическое (прямая задача), другое экономическое (двойственная задача).

Экономическое описание содержит двойственные оценки каждого вида расходуемых ресурсов или технологических способов, операций технологического процесса.

Двойственная оценка показывает, насколько изменится целевая функция, если количество ресурса изменить на единицу. Они позволяют исследовать устойчивость оптимальной величины критерия при возможных изменениях первоначальных условий – ограничений.

Предыдущая статья Графоаналитический метод решения простейших линейных оптимизационных моделей Следующая статья Единая транспортная система

Статьи по теме