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

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

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

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

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

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

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

— составляем систему ограничений. Коэффициенты систе­мы ограничений образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи. Знаки неравенств меняются на противоположные;

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

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

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

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

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

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

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

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

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

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

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

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

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

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