Сущность симплекс-метода

Симплекс-метод может быть применен для решения любой задачи линейного программирования, однако в общем случае приходится использовать различные его модификации. Рассмотрим вначале его применение для задачи линейного программирования, удовлетворяющей следующим условиям:

а) на все переменные наложены ограничения неотрицательности, а все остальные ограничения (пусть их m) представляют собой уравнения;

б) свободные члены ограничений неотрицательны;

в) среди векторных коэффициентов имеется полный набор линейно независимых векторов, который представляет собой m единичных столбцов.

Отметим, что задача, удовлетворяющая первому условию, представляет собой задачу линейного программирования в канонической форме. Любая задача линейного программирования в смешанной форме (т.е. в общем виде) может быть к ней приведена (см. раздел 1.4.1).

Что касается двух других условий, то в ряде частных случаев (но отнюдь не всегда) можно добиться их выполнения, умножив или разделив обе части ограничения на одно и то же число. Так, если свободный член в ограничении отрицателен, можно умножить обе части уравнения на -1. Если после этого одного из единичных векторов не хватает, но в соответствующем ограничении присутствует с некоторым положительным коэффициентом переменная, которая в другие ограничения не входит, то обе части этого ограничения можно разделить на данный коэффициент. Например, если одно из ограничений имеет вид -4х₁ - 6х₂ + 2х₃ - 2х₄ = -10, и, например, переменная х₄ в других ограничениях не встречается, то разделив обе части на -2, можно получить 2х₁ + 3х₂ - х₃ + х₄ = 5. В полученном уравнении свободный член неотрицателен, и векторный коэффициент при х₄ является единичным.

Задачу, удовлетворяющую перечисленным условиям, можно записать в общем виде следующим образом (для задачи на максимум):

Разумеется, единичные вектора не обязательно должны стоять при первых m переменных. Однако переменные всегда можно обозначить по-другому, перенумеровать, поэтому запись (14) все-таки можно считать общей.

Опорный план построим следующим образом: базисные переменные (в (14) это первые m переменных) примем равными соответствующим элементам столбца свободных членов, а небазисные - равными нулю. Таким образом, исходный опорный план Х = (b₁, b₂,... b_m, ). Такой план, очевидно, является допустимым, что легко проверить, подставив его в систему ограничений:

b₁ + 0 = b₁

b₂ + 0 = b₂

…

b_m + 0 = b_m

b_1-m ³ 0; 0 ³ 0

Векторные коэффициенты при его ненулевых компонентах b_1-m представляют собой линейно независимые единичные столбцы; т.е. этот план действительно опорный. Далее применение симплекс-метода рассмотрим на примере.