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

Допустимый вид системы ограничений:

Какие-то из неизвестных должны быть выражены через остальные неизвестные, причем свободные члены этих выражений неотрицательны.

Пример:

x₁ = -2x₄ + 7x₅ + 5

x₂ = 3x₄ + 6x₅ + 4

x₃ = -x₄ + 2x₅

Допустимый базис:

Все свободные члены в правых частях неотрицательны

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

1. Привести задачу к каноническому виду.

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

x₁ +    a_{1 r+1} x_r+1 + … + a_{1 n} x_n = b₁

x₂ + a_{2 r+1} x_r+1 + … + a_{2 n} x_n = b₂                                                                                                  (1)

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

        x_r + a_{r r+1} x_r+1 + … + a_{r n} x_n = b_r

где x₁, x₂, ….., x_r – базисные переменные, x_r+1, x_r+2, ….., x_n – свободные переменные b_i ≥ 0, I = 1, 2, …, r

3. Исключить из целевой функции базисные переменные с помощью (1) и записать ее в виде

f + c_r+1 x_r+1 + … + c_nx_n = c₀                                                             (2)

Коэффициенты, c_i, i = r + 1, …, n называются оценками соответствующих переменных x_r+1, x_r+2, …, x_n

Из (1), (2) следует, что на допустимом базисном решении

X _баз = (c ₁; c ₂; …; c_r; 0; 0; …; 0) *принадлежит* R ⁿ

целевая функция принимает значение f (x_баз) = c₀

 

После выполнения подготовительного этапа заполняется начальная симплекс-таблица:

Б. н.	С. ч.	X1	…	Xr	Xr+1	…	Xp	…	Xn
X1	b1	1	…	0	a1 r+1	…	a1 p	…	a1 n
…	…	…	…	…	…	…	…	…	…
Xq	bq	0	…	0	aq r+1	…	aq p	…	aq n
…	…	…	…	…	…	…	…	…	…
Xr	br	0	…	1	ar r+1	…	ar p	…	ar n
f	c0	0	…	0	cr+1	…	cp	…	cn

 

Здесь и ниже используются следующие сокращения:

1. Б.н. – базисные неизвестные.

2. С.ч. – свободные члены.

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

а) Если в строке оценок среди чисел c _k (k ≠ 0) имеется хотя бы одна положительная (например c _p), а в соответствующем столбце (разрешающем столбце) хотя бы один положительный элемент, то решение может быть улучшено. Среди указанных положительных элементов столбца в качестве разрешающего элемента a_ip выбирается тот, которому отвечает минимальное отношение b_i / a_ip. Если имеется несколько элементов с подобным свойством, то в качестве разрешающего выбирается любой из них. В таблице таким элементом является a_qp. Далее над таблицей проводятся элементарные преобразования: переменная x_p становится базисной, а x_q – свободной. На новом базисном решении значение целевой функции не увеличивается, и снова анализируется строка оценок.

б) Если в строке оценок нет положительных чисел, то оптимальное решение найдено.

в) Если в строке оценок есть положительное число, а в соответствующем ей столбце нет положительных элементов, то задача ЛП не имеет решения. В задаче о нахождении минимума функции это обозначается так: min f = −∞.

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

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

15. Симплекс-таблица. Строка оценок. Условие оптимальности базисного решения. Условие неограниченности целевой функции. Условие существования альтернативного решения. Примеры.

Строка оценок – последняя строка симплекс-таблицы (коэффициенты целевой функции)

Условие оптимальности базисного решении:

Все коэффициенты при свободных неизвестных в выражении для f неотрицательны

Условие неограниченности целевой функции:

Базисное решение является оптимальным, если все коэффициенты в строке оценок положительны (в задаче на max) или отрицательны (в задаче на min).

Если в задаче на максимум (минимум) в строке оценок есть отрицательный (положительный) элемент, а в соответствующем ей столбце нет положительных элементов, то ЗЛП неразрешима и f_max=+ (f_min=- ).

Условие существования альтернативного решения:

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

После выполнения подготовительного этапа заполняется начальная симплекс-таблица:

Б. н.	С. ч.	X1	…	Xr	Xr+1	…	Xp	…	Xn
X1	b1	1	…	0	a1 r+1	…	a1 p	…	a1 n
…	…	…	…	…	…	…	…	…	…
Xq	bq	0	…	0	aq r+1	…	aq p	…	aq n
…	…	…	…	…	…	…	…	…	…
Xr	br	0	…	1	ar r+1	…	ar p	…	ar n
f	c0	0	…	0	cr+1	…	cp	…	cn

a_{q p}  -> b_i / a_ip -min

Здесь и ниже используются следующие сокращения:

1. Б.н. – базисные неизвестные.

2. С.ч. – свободные члены.

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

а) Если в строке оценок среди чисел c _k (k ≠ 0) имеется хотя бы одна положительная (например c _p), а в соответствующем столбце (разрешающем столбце) хотя бы один положительный элемент, то решение может быть улучшено. Среди указанных положительных элементов столбца в качестве разрешающего элемента a_ip выбирается тот, которому отвечает минимальное отношение b_i / a_ip. Если имеется несколько элементов с подобным свойством, то в качестве разрешающего выбирается любой из них. В таблице таким элементом является a_qp. Далее над таблицей проводятся элементарные преобразования: переменная x_p становится базисной, а x_q – свободной. На новом базисном решении значение целевой функции не увеличивается, и снова анализируется строка оценок.

б) Если в строке оценок нет положительных чисел, то оптимальное решение найдено.

в) Если в строке оценок есть положительное число, а в соответствующем ей столбце нет положительных элементов, то задача ЛП не имеет решения. В задаче о нахождении минимума функции это обозначается так: min f = −∞.

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

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

 

16. Теорема о конечности симплекс-алгоритма (без доказательства).

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

Эту теорему часто называют теоремой о конечности симплекс-алгоритма. И, действительно, в ней утверждается, что если ЗЛП разрешима, то, взяв любой исходный базис и выбирая последовательность разрешающихся элементов подходящим образом, мы всегда придем – после конечного числа шагов – к базисному оптимальному решению.