22.1. Двойственность в линейном программировании. Виды двойственных задач и составление их математических моделей. Симметричные двойственные задачи

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

Различают симметричные, несимметричные и смешанные двойственные задачи.

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

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

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

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

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

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

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

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

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

< Предыдущая		Следующая >