Реферат: Применение методов линейного программирования в военном деле. Симплекс-метод

коэффициенты от неизвестных свободных членов отделим чертой, а элемент a₁₁ , заключенный в рамочку, будем называть разрешающим элементом.

Выпишем соответствующую таблицу для коэффициентов уравнений (3.26)

(3.28)

Коэффициент a’₂₁ равен нулю

Из уравнения (3.25) следует, что

(3.29)

На таблице (3.27) соединим элемент a_2j c разрешающим элементом прямой линией. Рассмотрим прямоугольник, диагональю которого является проведенная линия. Эту диагональ будем называть первой диагональю. Второй диагональю является прямая, соединяющая элементы a₂₁ и a_1j , обведенные кружком. Как следует из формулы (3.29), чтобы получить элемент a_2j , нужно из произведения элементов первой диагонали вычесть произведение второй диагонали. Остальные элементы второй строки вычисляются по этому же правилу. Это правило напоминает правило вычисления детерминантов второго порядка, поэтому будем коротко называть его D-правилом.

Переход от таблицы коэффициентов (3.27) к таблице (3.28), совершаемый с помощью D-правила, будем называть симплекс преобразованием или S-преобразованием одной таблицы в другую.

Очевидно, для выполнения S-преобразования с помощью первого уравнения необходимо, чтобы коэффициент a₁₁ ¹0 в противном случае переменная x₁ в первом уравнении будет отсутствовать.

Если теперь возьмем первое уравнение системы (3.22) и третье и проделаем такие же вычисления, то исключим x₁ из третьего уравнения. Продолжая такие же вычисления, исключим x₁ из всех уравнений, кроме первого. Вычисления будем производить в следующем порядке. Сначала запишем таблицу коэффициентов системы (3.22)

(3.30)

Если a₁₁ ¹0, и мы хотим исключить x₁ с помощью первого уравнения, то принимаем элемент a₁₁ за разрешающий и в таблице (3.30) обводим его рамкой. Строка и столбец, в которых находится разрешающий элемент, называются соответственно разрешающей строкой и разрешающим столбцом. В таблице (3.30) это первая строка и первый столбец.

Применяя симплекс преобразование, перейдем к новой таблице. В новой таблице элементы разрешающей строки переписываются без изменений. Все элементы разрешающего столбца, кроме самого разрешающего элемента заменяются нулями.

Остальные элементы новой таблицы вычисляются по D-правилу. Например, для вычисления элемента a’_ij соединяем элемент a_ij на таблице (3.30) с элементом a₁₁ прямой. В результате имеем первую диагональ. Вторая диагональ получается от соединения элементов a_i1 и a_1j , обведенных на таблице кружками. По D-правилу имеем

При выполнении симплекс преобразования диагонали, изображенные на таблице (3.30), на самом деле проводить не нужно: они легко выделяются в уме.

Выполнив S-преобразование над таблицей (3.30), мы получим новую таблицу

(3.31)

Этой таблице соответствует система уравнений:

(3.32)

Система (3.32) эквивалентна первоначальной системе (3.22), но в системе (3.32) переменная x₁ исключена из всех уравнений, кроме первого. Если в таблице (3.31) элемент a’₂₂ ¹0, то, приняв его за разрешающий элемент и проделав над таблицей (3.31) S-преобразование, получим новую таблицу. И в системе уравнений, соответствующей этой таблице, переменная x₂ будет исключена из всех уравнений, кроме второго.

Если в таблице (3.31) a’₂₂ =0, то во втором столбце найдем элемент, не равный нулю, и примем его за разрешающий. Пусть это будет a’₁₂ . Тогда выполняя симплекс преобразование над таблицей (3.31), мы исключим x₂ из всех уравнений, кроме i-того. Продолжая так дальше, мы после n преобразований придем к таблице, имеющей, например, следующий вид.

(3.33)

Таблице (3.33) соответствует система уравнений, эквивалентная первоначальной системе. Эта система уравнений имеет вид:

(3.34)

Можно считать, что система (3.34) решена относительно базисных переменных x₁ , x₂ , …, x_n . Переносить члены, соответствующие свободным переменным, в правую часть для фактического решения системы (3.34) относительно базисных переменных не будем, так как в дальнейшем нас будет интересовать решение, где все свободные переменные равны 0.

Полагая x_n+1 =x_n+2 =…=x_m =0, получим:

Если окажется, что x₁ ³0, x₂ ³0, …, x_m ³0, то совокупность чисел (x₁ , x₂ , …, x_n , 0, 0, …, 0) дает неотрицательное решение системы.