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

дом. Пусть задача линейного программирования задана в канони­ ческом виде: найти L= L(x,,Xj,...,x „) = qx,+C2X2+... + c',|Ji:„ —> min при условиях йцХ, + +... + = bf +«22^2+... + а2„Х„ ^ ^ X, >0, Xj >0, ..., х„ >0, где foj>0, i = l,m, т<п. Пусть среди столбцов А,, А,, ..., А„ нет единичных. Перейдем к новой задаче. Она получается путем вве­ дения в ка>вдое ограничение искусственной переменной. Искусст­ венные переменные вводятся в ограничения-равенства, чтобы по­ лучить начальный опорный план. Каждая искусственная переменная вводится в левую часть только одного из уравнений-ограничений с коэффициентом еди­ ница (+1). Кроме того, каждая искусственная переменная добавля­ ется в целевую функцию с коэффициентом +М, если решается за­ дача на минимум, и с коэффициентом -М, если решается задача на максимум. Здесь М >0, М - некоторое достаточно большое число. После введения искусственных переменных задача принимает вид: L[x^ •••,'•^,1»-^п+Р .•> = с,Х| -ь CjX, -I-.. + + Мл-,^1 +... + min при условиях ацХ, + + - + а,„х„ + = fc,; Й2,.Х| -ьа,2-^2 + - + = Ь,-, х,>0, j = l, {п + тХ [а„,Л + а„2^2 + - + = Ь,„, 54