9.4. каноническая форма задачи линейного программирования
9.4. каноническая форма задачи линейного программирования
Задача линейного программирования имеет каноническую форму, если в ее систему ограничений входят только линейные уравнения и условия неотрицательности для всех неизвестных, т.е. в задаче (9.1)—(9.4) 1= М= {1, 2,т), aJ=N= {1, 2,и}.
Задача линейного программирования в канонической форме имеет следующий вид:
/ = XY^(min), (9.7)
л
^OyXj bt, і 1,2,т, (9.8)
xj >0, у = 1,2,...,й. (9.9)
Задачу (9.7)—(9.9) в канонической форме можно записать также в виде
л
±AjX]=B,
Xj>0, у = 1,2,..., и,
где Jj, А2,Aj,Ап — векторы условий, а В — вектор ограничений этой задачи.
Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме.
В самом деле, рассмотрим задачу (9.1)—(9.4). Каждое неизвестное Xj, j є NJ, заменим на разность Zj двух новых неотрица227
тельных неизвестных^., ZjПосле этого в неравенства системы (9.3) введем по новому неизвестному t. (/ є МГ), полагая
Xaiixj + S ау(У] + h = bt> 1 є ML
Ує/ jtNj
Получим задачу линейного программирования в канонической форме:
/' = X 1jxj + Е yjfy ~ Zj)(nto>> (9-Ю) ХаЛ+ S aij(yj-Zj) = bi> ieI> (9-11) + S ayiyj-z^ + t^bi, ieMI, (9.12)
х,> 0, j є /; yy, zj > 0, у є УУ/; f, > 0, / є MI. (9.13)
При этом задача (9.10)—(9.13) будет иметь оптимальное решение тогда и только тогда, когда оптимальное решение было и у исходной задачи (9.1)—(9.4).
Кроме того, зная координаты оптимального решения задачи (9.10)—(9.13): x°,y є /; yf, z-,j є NJ; f°, / є MI, легко найти оптимальное решение исходной задачи, полагая ху. = ху° при j є / и ху = ^-г/ггои;єУУ/.
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы