4. Графический метод решения задач.

Проиллюстрируем проведенные этапы графическим методом решения задач, заданных в канонической форме при наличии не более двух свободных переменных. Обратимся к системе (3.1) и форме (3.2).

На рис. 4.1 представлен многоугольник решений и линейная форма. Здесь совокупность независимых переменных – это система координат. Линейная форма zв точке 0 даёт одно из допустимых базисных решений. Проведение преобразований – выбор новой пары свободных переменных (вместо,- пара,) – означает переход к новой системе координат. Причём видно, что движение по осивозможно только до значения=2. Так как каждое уравнение в пространстве представляет из себя гиперплоскость (у нас прямая линия), то движемся по осидо встречи с новой гиперплоскостью (прямой), то есть покане станет равной нулю. Точка 0соответствует новому началу координат с осями,.

Новый вид задачи представлен на рис. 4.2 . Здесь целевая функция в точке 0опять даёт одно из допустимых базисных решений. Следующее преобразование системы координат – движение по осидо величины=6 (точка 0) – переход к системе,(рис. 4.3).

Из рис. 4.3 видно, что целевая функция при своём перемещении в направлении вектора достигает точки 0. Допустимое базисное решение в этом случае является и оптимальным (напомним, что линейная форма достигает минимума или максимума только в вершине многогранника решений).

Таким образом, графически (для плоской задачи) симплекс-метод обуславливает переход от одной системы координат к другой, причём заменяемая ось входит в выражение zс отрицательным коэффициентом, то естьzотсекает у неё отрезок в направлении отрицательной полуоси. Процесс происходит до тех пор, пока целевая функция не будет отсекать отрезки у одноимённых по знаку полуосей. Тогда минимум будет достигнут в начале координат.

Рис. 4.1.

Рис. 4.2.

ЗАМЕЧАНИЯ.

Отметим некоторые закономерности, которые могут быть полезны при рассмотрении алгоритма прямого симплекс-метода.

1. Проводя первый этап преобразований системы 3.1, мы увеличиваем до двух, что очевидно из рис. 4.1. Из этого же рисунка видно, что можно было «надеяться» на встречу также с прямыми б) и г), так как в соответствующих им уравнениям коэффициенты приположительны. Однако первой встретилась прямая а), для которой выполняется условие:

(4.1)

2. Предположим, что система (3.3) и функция (3.4) имели бы вид:

(4.2)

(4.3)

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

Рис. 4.4.

5. Прямой алгоритм симплексного метода

1. Рассмотрим прямой алгоритм симплексного метода, в котором используется рассмотренный математический аппарат, имея в виду при этом представ­ление задачи линейного программирования в канони­ческой форме.

Задача линейного программирования может быть представлена в канонической форме следующим об­разом:

с помощью элементарных преобразований,

в результате преобразования в уравнения исходных ограничений, имеющих неравенства вида  («меньше или равно»),

путем введения в уравнения системы некоторых ис­кусственных переменных.

Пусть задача линейного программирования пред­ставлена в канонической форме в следующем виде:

найти

x_j0 (j=1, 2, … , p, p+1, … , p+m) (5.1)

при условиях

(5.2)

c₁x₁ + c₂x₂ + ··· + c_px_p + c_p+1x_p+1 + ··· + c_p+mx_p+m = z  min (5.3)

В такой постановке задачи исходные уравнения сис­темы (5.2) содержат в числе других также m переменных x_p+1, x_p+2, …, x_p+m, при которых коэффициенты образу­ют единичную матрицу, или базис. Отметим, что порядковые номера базисных переменных здесь не играют роли; важно, чтобы каждая из таких переменных входила лишь в одно уравнение, причем с коэффициентом (+1).

В целевую функцию переменная может входить с любым коэффициентом (положительным, отрицательным или нулевым).

Для подготовки задачи к ее решению по прямому алгоритму выразим целевую функцию z через небазис­ные переменные. Для этого значения x_p+1, x_p+2, …, x_p+m, полученные соответственно из первого, второго, …, последнего уравнения системы (5.2), подставим в целе­вую функцию. Затем целевую функцию запишем в виде уравнения, перенеся z (со знаком минус) в одну часть вместе с переменными x_j, а свободный член c₀' (с обратным знаком) — в другую. Будем называть это уравнение целевым уравнением или z-строкой. Тогда задача будет представлена в следующем виде:

x_j0 (j=1, 2, …, p, p+1, …, p+m) (5.1)

удовлетворяющее соотношениям

(5.2)

c'₁x₁ + c'₂x₂ + ·· ·+ c'_px_p + (—z) = —c'₀ (5.3')

Систему уравнений (5.2) — (5.3') будем называть пред­ставленной в полной канонической форме, в которой, кроме базисных переменных x_p+1, x_p+2, …, x_p+m, пере­менную (—z) будем принимать также за базисную. [Учитывая, что базисные переменные принимаются с ко­эффициентами (+1) можно (—z) представить в виде, например, x_z].

Для полной канонической формы базисным решением будет следующее: x₁=0, х₂=0, …, x_р=0, x_p+1=b₁, x_р+2=b₂, …, x_р+m=b_m, z=c'₀, котороё принимается в качестве первоначального решения задачи. Поскольку каноническая форма вытекает из стандартной, а в последней свободные члены сделаны положительными ве­личинами, будем говорить, что задача представлена в допустимой канонической форме.

2. Как только что было установлено, каноническая форма позволяет непосредственно найти соответствую­щее базисное допустимое решение. Каноническую форму можно использовать также для выяснения, будет ли до­пустимое базисное решение минимальным, для чего ко­эффициенты c'_j(j = 1, 2, …, р) целевого уравнения про­веряются на оптимальность. Коэффициенты с'_j будем называть относительными оценками, так как их значе­ния зависят от выбора базисного множества переменных. Отмеченное выше основывается на следующих предло­жениях о критерии оптимальности:

А. Базисное допустимое решение является минималь­ным допустимым решением со значением z=c'₀, если все относительные оценки неотрицательны:

c'_j0 (j = 1, 2, …, р)

Действительно, для канонической формы очевидно, что если все коэффициенты целевого уравнения неотрицательны, то наименьшая величина суммы c'₁x₁ + c'₂x₂ + ··· + c'_px_p + c'_p+1x_p+1 + ··· + c'_p+mx_p+m есть нуль при любом выборе неотрицательных x_j. Следовательно, наименьшая величина разности (z–c'₀) равна нулю и min zc'₀. В частности, для допустимого базисного решения z=c'₀; по­этому min zc'₀, и решение оптимально. Очевидно так­же следующее другое предложение.

Б. Пусть дано минимальное допустимое базисное ре­шение с относительными оценками с'_j0; тогда любое другое допустимое решение (не обязательно базисное) при x_j=0 для всех c'_j>0 также является минимальным решением. Если же это решение обладает тем свойст­вом, что для некоторого j как x_j>0, так и c'_j>0, то оно не может быть минимальным решением.

В. Базисное допустимое решение является минимальным допустимым решением, если c'_j>0 для всех небазисных переменных.

3. В п.1 нами получено первоначальное решение линейной задачи (в общем виде), которое является базис­ным допустимым решением. Теперь перейдем к другому базисному допустимому решению, улучшив последнее.

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

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

В первом столбце таблицы 1 записаны базисные переменные, а так­же базисная переменная (–z). В следующих столбцах пишем коэффициенты при переменных в полной канонической системе. В последнем столбце – свободные члены (компоненты вектора В). В последней строке записаны коэффициенты с_j, из линейной формы (целевой функ­ции).

Первая (исходная) таблица 1 имеет следующий вид:

Таблица 1

Симплекс-таблица (исходная).

Базисн. перем.

x1

…

xj

…

xk

…

xp

xp+1

…

xp+i

…

xp+m

Свободн. члены

xp+1

a11

…

a1j

…

a1k

…

a1p

1

…

0

…

0

b1

xp+2

a21

…

a2j

…

a2k

…

a2p

0

…

0

…

0

b2

…

xp+i

ai1

…

aij

…

aik

…

aip

0

…

1

…

0

bi

…

xp+r

ar1

…

arj

…

ark

…

arp

0

…

0

…

0

br

…

xp+m

am1

…

amj

…

amk

…

amp

0

…

0

…

1

bm

(-z)

c1

…

cj

…

ck

…

cp

0

…

0

…

0

c0

А. Первым шагом в анализе первоначального допус­тимого базисного решения является проверка его на оп­тимальность. Она заключается в отыскании в последней z-строке максимального по модулю отрицательного коэффициента. Столбец c максимальным по модулю отрицательным коэффициентом (пусть это будет с'_k) назовём ключевым, а переменная этого столбца x_k будет новой базисной переменной, которая вводится в базис. В случае если окажется несколько равных по модулю отрицательных коэффициентов, то можно выбрать любой из них.

Если в z-строке отрицательных чисел нет, то получе­но минимальное (оптимальное) решение.

Б. Далее устанавливаем, какая переменная будет выведена из базиса. Для этого составляем отношения свободных членов к соответствующим положительным числам ключевого столбца , …, , …, , …, и выбираем наименьшее из этих отношений, т. е.

(a_ik>0, a_rk>0).

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

Элемент, стоящий на пересечении ключевого столбца и ключевой строки, будем называть ключевым элемен­том.

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

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

В. Переходим к построению следующей таблицы. В этой таблице прежде всего заполняются клетки строки x_r с вводимой переменной х_k. Для этого все элементы ключевой строки делятся на ключевой элемент; таким об­разом, x_r-уравнение разрешается относительно х_k. Полу­чаем следующие элементы строки:

, , …, , …, 1, …,, 0, …,, …, 0, .

С помощью элементарных преобразований системы уравнений можно, как известно, любую переменную исключить из всех уравнений системы, кроме какого-либо одного. В данном случае нам необходимо исключить пе­ременную х_k из всех уравнений (строк), кроме одного (ключевой строки). Чтобы исключить х_k из всех уравне­ний системы, надо, чтобы в клетках ключевого столбца (кроме ключевого элемента а_rk=1) на месте элементов а_1k, а_2k, …, а _r-1;k , а _r+1;k , …, а_mk были нули. Это достигается следующим образом. Пусть мы хотим исключить переменную х_k из i-гo уравнения. Для этого достаточно уравнение с ключевым элементом а_rk=1 умножить на (–а_ik) и прибавить к i-му уравнению. После исключе­ния х_k из всех уравнений система уравнений преобра­зуется в эквивалентную ей систему.

Остальные элементы таблицы (коэффициенты при переменных и свободные члены) будут связаны с коэф­фициентами при переменных и свободными членами ис­ходной системы так называемыми формулами исключе­ния;

(ir, a_rk>0),

(ir, a_rk>0).

Эти формулы легко запомнить, если посмотреть на прямоугольник в таблице 1, в вершины которого по­местить, например, элементы, входящие в формулу ис­ключения (эти элементы выделены в таблице 1). Для того чтобы найти элемент , который будет стоять в клетке новой таблицы на месте элемента a_ij надо из последнего вычесть произведение элементов (a_ik·a_rj), стоящих в вершинах побочной диагонали, и разделить на элемент а_rk, стоящий по главной диагонали. Указан­ное правило относится и к нахождению свободных чле­нов. Преобразованные по формулам исключения элемен­ты записываем в соответствующие клетки новой табли­цы. Для практических расчетов следует иметь в виду следующее:

в новой таблице на месте ключевого элемента пишем 1, а на месте остальных элементов ключевого столбца— нули;

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

если в ключевом столбце окажется нуль, то соответ­ствующую ему строку перепишем в новой таблице без изменения.

Отметим, что для нахождения элементов z-строки ис­пользуем те же формулы исключения.

Г. После того как составлена вторая симплексная таблица, просматриваем в ней z-строку, чтобы выявить, получено ли оптимальное (минимальное) решение с по­мощью критерия оптимальности. Если все элементы этой строки (соответствующие небазисным переменным) ока­жутся положительными или равными нулю, то получено оптимальное решение (, , …, х_k, …, ), для кото­рого имеем min z.

Если в z-строке окажутся отрицательные элементы, то выбираем наименьший из них; соответствующий этой относительной оценке столбец будет ключевым, а пере­менная этого столбца будет базисной переменной, кото­рая и вводится в новый базис.

Затем устанавливаем, какая переменная будет выве­дена из базиса (по правилу, указанному в п. Б). Далее переходим к построению новой симплексной таблицы (по правилу, указанному в п. В), по z-строке которой уста­навливаем, получено ли оптимальное (минимальное) базисное решение, т. е. исследуем на оптимальность до­пустимое базисное решение.

Переход от одной таблицы к другой повторяется до тех пор, пока не будет получено оптимальное решение или не будет выявлено (в случае, если окажется, что относительная оценка ключевого столбца отрицательна, а все его элементы неположительны), что можно пост­роить множество допустимых решений, для которых z не ограничено снизу.

Рассмотренный нами вычислительный процесс с по­мощью прямого алгоритма симплексного метода можно наглядно показать на блок-схеме 1.

Отметим, что если некоторой переменной, не входящей в конечный базис, в z-строке соответствует отно­сительная оценка, равная нулю, то эту переменную мож­но обычным образом ввести в базис и получить новое решение, которое будет также оптимальным. При на­личии двух (или более) оптимальных решений любые их выпуклые комбинации будут оптимальными.

Блок-схема 1

Алгоритм прямого симплекс-метода.