Метод искусственного базиса (М-задача)

До сих пор при изложении симплексного метода предполагалось, что система исследуемых уравнений решена относительно базисных переменных, т. е приведена к единичному базису, и все Bi≥ 0.

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

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

Заметим, что в некоторых случаях получение исходного опорного решения не вызывает осложнений и не требует применения специальных приемов. Так, например, система исходных ограничений может оказаться сразу заданной в приведенном к единому базису виде с неотрицательными свободными членами. Иногда исходные ограничения могут выражаться неравенствами вида a_i1 x₁+a_i2x₂+…+a_in x_n≤ a_i0 где а_i0≥ 0.

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

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

Максимизировать линейную функцию

Z=c₁ x₁+с₂ х₂+…+с_k х_k +…c_n x_n

в области решений системы уравнений

a₁₁x₁₁+a₁₂x₁₂+…+a_1nx_n=b₁

a₂₁x₂₁+a₂₂x₂₂+…+a_2nx_n=b₂

_{…………………………………………..}

a_i1x_i1+a_i2x_i2+…+a_inx_n=b_i

_{…………………………………………..}

a_m1x_m1+a_m2x_m2+…+a_mnx_n=b_m

x₁ ≥ 0; x₂ ≥ 0; …; x_n ≥ 0

Среди уравнений системы могут оказаться некоторые линейно зависимые от остальных, т. е. ранг систем может быть меньше, чем m, однако в излагаемом методе нет необходимости в предварительном определении ранга системы и отбрасывании “лишних” уравнений. Будем полагать, что все a_io ≥ 0. Очевидно, этого всегда можно добиться умножением соответствующего уравнения на множитель —1.

a₁₁x₁+a₁₂x₂+…+a_1nx_n+x_n+1= b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n+x_n+2= b₂

………………………………

a_i1x₁+a_i2x₂+…+a_inx_n+x_n+i= b_i

_{……………………………………………….}

a_m1x₁+a_m2x₂+…+a_mnx_n+x_n+m= b_m

получаемую из исходной системы введением m неотрицательных переменных х_n+1 ≥ 0; х_n+2 ≥ 0; …; х_n+m ≥ 0, именуемых искусственными.

Исходная система уравнений приведена к единичному базису { _n+1 , …, _n+m }, называемому искусственным базисом, и имеет неотрицательный столбец свободных членов ( ₀ ≥ 0). Поэтому ей соответствует исходное опорное решение

n m

=(0, 0, …, 0, a₁₀ , …, a_m0 )

Рассмотрим любое допустимое решение = (а₁, а₂,..., а_n, а_n+1, …, а_n+m) исходной системы.

Если в этом решении все искусственные переменные равны нулю (а_n+1= … а_n+m=0), то первые n чисел определяют допустимое решение( =(а_1, а_2, …, а_n ) системы.

Наоборот, если =(а_1, а_2, …, а_n) есть допустимое решение системы, то

=(а_1, а_2, …, а_n , 0, …, 0) есть допустимое решение системы.

По этой причине будем решения =(а_1, а_2, …, а_n) и =(а_1, а_2, …, а_n , 0, …, 0) называть соответствующими.

Составим новую целевую функцию:

T=z – M * _n+i = _k* x_k -M* _n+i

где М — произвольно большое число, и будем максимизировать ее в области допустимых решений исходной системы.

Полученными соотношениями определяется новая задача, которую назовем М-задачей.

Эта задача может решаться симплексным методом. При этом на основании вышеизложенного через конечное число итераций либо будет найдено ее оптимальное решение, либо установлено, что функция Т → ∞.

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

Теорема 1. Если в оптимальном решении М-задачи = (b₁, b₂,..., b_n, b_n+1, …, b_n+m) все искусственные переменные равны нулю (т. е. а_n+i = 0 для всех i), то соответствующее решение =(b_1, b_2, …, b_n) есть оптимальное решение исходной задачи.

Теорема 2. Если имеется оптимальное решение М-задачи, в котором хоть одна из искусственных переменных отлична от нуля, то система ограничений исходной задачи несовместна в области допустимых решений.

Теорема 3. Если М-задача оказалась неразрешимой (Т → ∞), то исходная задача также неразрешима либо по причин несовместности системы (23) в области допустимых решений, либо по причине неограниченности функции z (z_max → ∞).

Рассмотрим практическое применение метода искусственного базиса.

Дана математическая модель задачи:

F (x) = 5x₁ + 6x₂ + 7x₃ + 4x₄ → min

x₁ + x₂ + 4x₄ > = 26

2x₁ + 3x₃ + 5x₄ > = 30

x₁ + 2x₂ + 4x₃ + 6x₄ > = 24

x_j > =0 j = 1÷ 4

Приведем задачу к канонической форме:

F (x) = 5x₁ + 6x₂ + 7x₃ + 4x₄ → min

F (x) = -5x₁ -6x₂ -7x₃ - 4x₄ → max

Введем балансовые переменные х₅, х₆, х₇

x₁ + x₂ + 4x₄ – x₅ = 26

2x₁ + 3x₃ + 5x₄ – x₆ = 30

x₁ + 2x₂ + 4x₃ + 6x₄ – x₇ = 24

Т.к. введенные балансовые переменные имеют знак «-», то принять их за базисные нельзя.Поэтому введем искусственные переменные х₈, х₉, х_10.

x₁ + x₂ + 4x₄ – x₅ + x₈ = 26

2x₁ + 3x₃ + 5x₄ – x₆ + x₉ = 30

x₁ + 2x₂ + 4x₃ + 6x₄ – x₇ + x₁₀ = 24

x_j > =0 j = 1÷ 10

Заполним симплексную таблицу и используя алгоритм модифицированного симплексного метода найдем оптимальное решение.

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

F (x)min = - F(x)max = - (-26) = 26

x = (0, 0, 0, 13/2, 0, 5/2, 15, 0, 0, 0)

Таблица 4. Симплексная таблица

Контрольные вопросы и упражнения

1. Какая задача называется М-задачей?
2. Что называется оптимальным планом задачи с искусственным базисом?
3. Как привести задачу линейного программирования к
4. канонической форме, если неравенства системы
5. ограничений имеют разнородные знаки?
6. Каким образом заполняется симплексная таблица?
7. Как вычисляется строка суммы?
8. С какой целью вводится строка суммы?
9. Каким образом осуществляется переход к следующей итерации?
10. Что происходит с искусственной переменной после выхода из базиса?
11. Как влияет на ход решения задачи наличие искусственной переменной в оптимальном плане?
12. Дайте сравнительную характеристику методов для решения стандартной задачи ЛП и М-задачи.

1. Решить симплексным методом следующие М-задачи линейного программирования:

а) F(x)= -7x₁+3x₂ g max

2x₁+3x₂-4 > _ 12

-x₁+x₂ < _ 7

-2x₁+x₂ < _ 10

x₁ > _ 0, x₂ > _ 0