Допустимое решение в задаче линейного программирования

При решении задачи ЛП табличным симплекс-методом предполагалось, что в начале первого шага известно какое-либо допустимое решение, то есть все базисные переменные положительны. Однако, в общем случае, задача ЛП, приведенная к исходному виду

xk+1 = bk+1 – (nk+1,1 x1 + nk+1,2 x2 + nk+1,3 x3 +…+ nk+1,j xj +…+ nk+1,k xk) xk+2 = bk+2 – (nk+2,1 x1 + nk+2,2 x2 + nk+2,3 x3 +…+ nk+2,j xj +…+ nk+2,k xk) ……………………………………………………………………..… xk+m= bk+m – (nk+m,1 x1 + nk+m,2 x2 + nk+m,3 x3 +…+ nk+m,j xj +…+ nk+m,k xk)

(3.23)

 

L (x)= g0 - (r1 x 1 + r2 x 2 +...+ r jxj +...+ r kxk)

(3.24)

x_n ³ 0 (n = 1, …, k+m)

(найти такие x_n, которые удовлетворяют (3.23) и обращают в минимум целевую функцию L (x)).

Столбец свободных членов наряду с положительными, содержит и отрицательные значения свободных членов b _k+i. Это означает, что одна или несколько базисных переменных в начальном решении принимают отрицательные значения, то есть начальное решение не является допустимым, так как оно не удовлетворяет условию неотрицательности переменных x ₁, x ₂,..., x_n. В этом случае необходимо перед применением симплексного метода найти допустимое решение задачи. Изобразим исходную симплекс-таблицу, соответствующую (3.23):

Таблица 3.4

СП БП	СЧ	x 1	x 2	…	xj	…	xk
L (x)	g0	r1	r2	…	r l	…	r k
xk +1	b k +1	n k +1,1	n k +1,2	…	n k +1, l	…	n k +1, k
xk +2	b k +2	n k +2,1	n k +2,2	…	n k +2, l	…	n k +2, k
…	…	…	…	…	…	…	…
xk + s	b k+s	n k+s ,1	n k + s,2	…	n k+s,l	…	n k+s,k
…	…	…	…	…	…	…	…
xk + m	b k+m	n k+m ,1	n k + m,2	…	n k+m,l	…	n k+m,k

 

Пусть среди свободных членов b _k+i есть отрицательные b _k+i < 0; 1 ≤ i ≤ m, тогда начальное решение не является допустимым. Заметим в таблице 3.4 строки с отрицательными свободными членами. Если среди них есть строка, в которой кроме свободного члена все остальные элементы неотрицательные, то система (3.23) будет несовместна. Это положение справедливо на всех этапах решения задачи линейного программирования.

Допустим, что система (2.23) совместна. Тогда в таблице 3.4, если она содержит отрицательные свободные члены, в соответствующих строках обязательно найдутся отрицательные элементы ν _pq < 0. Пусть такой строкой будет s -я строка, где ν_k+s,l < 0. Вспоминая алгоритм преобразований Жордана, позволяющий получать системы уравнений, равносильные исходной (3.23), можно легко понять, что выбирая элемент ν_k+s,l в качестве ведущего после осуществления первого жорданова преобразования в s -й строке получим положительный элемент.

(3.25)

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

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

Определим условия, при которых обеспечивается последовательное уменьшение количества отрицательных элементов в столбце свободных членов при выполнении преобразования Жордана с ведущим элементом ν _{k + s,l} . Свободные члены, кроме выбранного b _k+s, преоб­разуются в этом случае по формуле

(3.26)

 

Из выражения (3.26) легко получить условия сохранения в произольной k+i -й строке таблицы (k +1 ≠ k + s) знака свободного члена при выполнении одного преобразования Жордана с ведущим элементом ν _{k + s,l} . В самом деле отношение всегда.

Рассмотрим отношение .

1. При b_k+i ³ 0 и ν_k+i,l < 0 - ,

то есть в круглых скобках выражения (3.26) будет стоять отрицательная величина, а ее произведение на отрицательное ν _{k + i,l} даст в результате b’ _{k + i} > 0. То есть в этом случае свободный член в k+i -й строке новой таблицы останется положительным.

2. При b_k+i ³ 0 и ν_k+i,l > 0 - и b’_k+i ³ 0

лишь при условии

³ > 0

то есть элемент ν _{k + s,l} можно выбирать ведущим только тогда, когда он будет знаменателем наименьшего из всех положительных отношений элементов столбца свободных членов к соответствующим элементам ведущего l-го столбца.

3. b _k+i < 0. Если при этом ν_k+i,l > 0, то b’_k+i < 0.

4. b _k+i < 0. Если при этом ν_k+i,l < 0, то > , а значит и b’_k+i < 0. Таким образом, во всех этих случаях знак свободного члена k+i -й строки, в новой таблице изменяться не будет, а изменится только знак b _k+s.

Однако, приписывая отношению знак «+», видим, что оно будет наименьшим среди положительных отношений, а значит, b’_k+i новой таблицы только тогда будет равняться нулю, (даже при ν_k+i,l > 0, когда и b_k+i = 0, то есть, когда ведущий элемент взят в строке с нулевым свободным членом. При этом остальные элементы, отличные от нуля, сохраняют, как следует из анализа выражения (3.26), свой знак.

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

В самом деле, в этом случае в столбце свободных членов на один отрицательный элемент становится меньше, но, к сожалению, не всегда именно отношение , где и b_k+s ≤ 0 и ν_k+s,l < 0 будет наименьшим среди положительных отношений в l -м столбце. Обычно всегда находится положительный элемент ν_k+r,l с соответствующим положительным b_k+r, для которого справедливо < , и именно для него отношение является минимальным положительным.

Рассмотрим этот случай, то есть, < причем ν_k+r > 0 и, соответственно, ν _k+r,l > 0. Положим в выражении (3.26) i=r при этом получаем b’_r< 0, то есть свободный член в k+r -й строке из положительного стал отрицательным. И чем больше будет таких отношений < для r = 1, 2, …, m; r ≠ s, где b_л+к > 0 и ν_k+r,l > 0, тем больше будет появляться отрицательных элементов в столбце свободных членов, если будет выполняться жорданово преоб­разование с ведущим элементом ν_k+s,l.

Поэтому необходимо перейти к новой таблице, взяв в качестве ведущего элемента ν_k+r,l > 0, для которого отношение будет минимальным , надеясь получить в этой таблице столбец, отрицательный элемент которого будет знаменателем наименьшего положительного отношения, числителем в котором - соответствующий элемент столбца свободных членов.

В новой таблице число отрицательных свободных членов в этом случае останется тем же самым, что вытекает из анализа (3.26), и элемент b’ _{k + r} сохранит положительный знак.

Выполнив конечное число таких преобразований симплекс-таблицы можем иметь лишь два результата:

1) убеждаемся в противоречивости условий задачи;

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