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 є / и ху = ^-г/ггои;єУУ/.