Их математических моделей

Виды двойственных задач и составление

Лекция 4

4. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

Произвольную задачу линейного программирования можно определённым образом сопоставить с другой задачей линейного программирования, называемой двойственной.

Симметричные двойственные задачи

Дана исходная задача

при ограничениях:

Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, для этого:

- каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную y_i;

- составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничений исходной задачи. Функция стремится к минимуму, если в исходной задаче целевая функция стремилась к максимуму, и наоборот;

- составляем систему ограничений. Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи. Знаки неравенств зависят от целевой функции: если она в двойственной задаче стремится к минимуму, то знаки неравенств «», и наоборот;

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

Математическая модель двойственной задачи имеет вид

при ограничениях:

Несимметричные двойственные задачи

Дана исходная задача

при ограничениях:

Задача дана в каноническом виде. Составим математическую модель двойственной задачи.

Для её составления пользуются тем же правилом, что и при составлении симметричной задачи, с учётом следующих особенностей:

- ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства , если максимум, то ;

- переменные y_i – произвольные по знаку

Математическая модель двойственной задачи имеет вид

при ограничениях:

y_i – произвольные по знаку,

Смешанные двойственные задачи

Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач: та переменная, которая соответствует равенству в исходной задаче, может быть произвольного знака в двойственной задаче, а та переменная, которая соответствует неравенству, должна быть в двойственной задаче неотрицательной.

Дата добавления: 2014-01-15