Как найти начальный допустимый базис.

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

Ax ≤ b, x ≥ 0, <c, x> → min.

После приведения ее к каноническому виду базисными переменными можно взять дополнительные переменные.

Задача 1.Как найти хотя бы одно допустимое решение.

Запишем СЛУ для задачи ЛП в виде:

Ax = b (или b – Ax = 0) (1)

x ≥ 0 (2)

<c, x> → min (3)

Систему ограничений можно записать подробнее в виде:

b_i - ∑a_ijx_j = 0 (i = 1, …,m).

Можно считать, что все b_i ≥ 0 (если это не так, умножаем соответствующее равенство на -1). Введем новые вспомогательные, «искусственные» переменные (так называемые невязки):

z_i = b_i - ∑a_ijx_j, (i = 1, …,m)

с дополнительными условиями z_i ≥ 0. Очевидно, что для допустимых x все невязки равны 0.

Введем функцию f = ∑z_i и рассмотрим расширенную задачу ЛП:

z_i = b_i - ∑a_ijx_j (или ∑a_ijx_j + z_i =b_i ) (i = 1, …,m) (4)

z_i ≥ 0, x_j ≥ 0, (i = 1, …,m), (j = 1, …,n) (5)

f = ∑z_i → min. (6)

В этой задаче можно взять искусственные переменные за базисные, а исходные – за свободные. Начальный базис (z₁,…, z_m,x₁,…,x_n)=(b₁,…,b_m, 0,…,0) будет допустимым

Так как все z_i ≥ 0, то целевая функция f ≥ 0. Очевидно также,что {все z_i = 0} ó f =0 ó Ax = b.

Вывод: Если в расширенной задаче min f = 0, то существует х ≥ 0: Ax = b. Всякое допустимое решение исходной задачи обращает в нуль все переменные-невязки z_i и дает минимум функции f. Отсюда получаем следующее

Правило:

решаем симплекс-методом расширенную задачу ЛП (4)-(6):

1. Если min f = 0, то в её оптимальном решении все z_i = 0, а найденные x₁, …, x_n – допустимое решение исходной задачи (1)-(3).

2. Если min f = min ∑z_i > 0, то допустимых решений в исходной задаче нет.

Задача 2. Найти допустимое базисноерешение исходной задачи (1)-(3).

В расширенной задаче (z₁,=b₁, …, z_m =b_m ; x₁=0, …, x_n = 0) – исходный допустимый базис (z₁ , …, z_m - базисные переменные). Отправляясь от него, решаем расширенную задачу - находим симплекс-методом ее оптимальное решение (0,…,0; x₁, …, x_n). Оно будет базисным для расширенной задачи, но для исходной – только лишь допустимым.

Если при этом в соответствующем представлении симплекс-таблицы расширенной задачи все z_i являются свободными, то базисными неизвестными окажутся только переменные x_i. Значит, найденное допустимое решение расширенной задачи (точнее, его часть x )будет не только допустимым, но и базисным решением как в расширенной, так и в исходной задаче. Положив z = 0, получим допустимое базисное решение для исходной задачи.

Пусть теперь среди базисных переменных есть переменные z. Как добиться, чтобы все z стали свободными переменными? Надо на каждом шаге симплекс-метода вводить в базис некоторую переменную х_j и выводить z_i , тогда в точке минимума функции f в состав базисных переменных войдут только переменные из числа

x₁, …, x_n. Положив все свободные переменные, в том числе и z₁ , …, z_m равными 0, получим допустимый базис исходной задачи.

Замечание: Может случиться, что min f = min ∑z_i уже достигнут ( и =0), но не все z_i выведены из базиса. Тогда можно продолжить процедуру изменения базиса без изменения значения f до исключения из базиса всех искусственных переменных.

_конец лекции 3