Сборник задач по методам принятия управленческих решений

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 8 Двойственность в линейном программировании Каждой ЗЛП можно поставить в соответствие другую задачу, называемую двойственной (сопряженной) по отношению к исход­ ной. Пару симметричных двойствершых задач можно записать в виде таблицы (табл. 28). Таблица 28 Исходная ЗЛП Двойствеш1ая задача L =• СХ —> min, АХ>В, Х>0 F:=YB max, ГЛ<С, Г>0 Существуют также пары несимметричных двойственных за­ дач. Представление о них дает табл. 29. Таблица 29 Исходная ЗЛП Двойственная задача 1 ) L = CX max, АХ=В, X >0; 2) L = СХ -» min, AX=B,X>Q F = YB —f min, УА>С-, F=YB ^ max, YA<C Правила составления двойственных задач: • Если ограничения исходной задачи имеют вид неравенств, то они должны быть записаны так, чтобы знаки этих неравенств были направлены в одну сторону, причем если знаки неравенств <, то целевая функция должна максимизироваться, если знаки нера­ венств >, то минимизироваться. • Если целевая функция исходной задачи задается на макси­ мум, то целевая функция двойственной - на минимум и наоборот: если Z.- »min, то F —> тах. Если ограничения исходной задачи имеют вид равенств, а целевая функция L-^ max (L —> min), то ограничения двойственной задачи имеют вид неравенств, причем знак неравенства зависит от того, какова целевая функция: «<», если L -4 max, и «>», если L —> min. 60