Теорема о симплексных преобразованиях СЛАУ.
Формулировка:
Если все свободные члены уравнений системы не отрицательны, то после симплексных преобразований они останутся неотрицательными.
Изобразим абстрактную часть симплексной таблицы.
Xk Xp
i Aik Aip Aio
q Aqk Aqp Aqo
Пусть разрешающий элемент у нас aqp. Докажем, что при условии положительности всех элементов таблицы, после симплексных преобразований они также сохранят знак. Элементы со штрихом — это элементы полученные в результате симплексных преобразований и стоящие на тех же местах, что и их предшественники без штриха.
aqo’ = aqo/aqp 0;
aik’ = aikaqp – aipaqp/aqp = aik – (aip/aqp)aqk 0; Не понимаю почему.
aqk’ = aqk/aqp 0;
aqo’ = aqo/aqp 0;
Осталось только aio’.
Докажем, что оно тоже 0.
aio’ = aioaqp – aipaqo/aqp = aio – aipaqo/aqp.
aip < 0:
aip = – aip
aio = aio + aip aqo/aqp 0;
aip > 0:
aio’ = aioaqp – aip aqo/aqp = aip (aio/aip – aqo/aqp),
a aqo/aqp — минимально из всех отношений aio/aip, так как aqp мы выбрали в качестве разрешающего.
Следовательно, aio/aip – aqo/aqp > 0.
Следовательно, aio’ 0.
Опорность решения сохранилась. Новое решение также оказалось опорным.