SHPORA.net :: PDA

[ Back ]

Формулировка:

Если все свободные члены уравнений системы не отрицательны, то после симплексных преобразований они останутся неотрицательными.

Изобразим абстрактную часть симплексной таблицы.

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.

Опорность решения сохранилась. Новое решение также оказалось опорным.