Алгоритм решения задач симплексным методом

 

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

Анализируем таблицу 2.2.2. В строке целевой функции есть отрицательные элементы, т.е. решение не является оптимальным, поэтому переходим к следующей симплекс-таблице. Выводим из базиса x₆, вводим в базис x₁.

 

Таблица 2.2.3. Симплекс-таблица для второй итерации.

Базисные переменные	Свободные члены	Коэффициенты  при базисных и небазисных переменных
		x1	x2	x3	x4	x5	x6	x7
x2	3	1/9	1	0	1  2/9	1/3	-  2/9	0
x3	0	1  2/9	0	1	4/9	-  1/3	5/9	0
x7	12	-  5/9	0	0	-1  1/9	-  2/3	-  8/9	1
Y	150	2  2/9	0	0	54  4/9	2  2/9	5  5/9	0

 

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

Можно выписать ответ. Значения базисных переменных и целевой функции выписываются из столбца свободных членов. Все небазисные переменные равны нулю.

Ответ:

x₁ = 0; x₂ = 3; x₃ = 0; x₄ = 0; x₅ = 0; x₆ = 0; x₇ = 12;

Y = 150.

Анализ решения задачи показывает, что предприятие будет выпускать только изделия второго вида.

При этом расход времени  на создание изделия на оборудовании каждого вида будет равен:

О₁ = 15;

О₂ = 9;

О₃ = 18.

Ответ: x = (0;3;0;0); Y=150.

 

 

2.3 Модифицированный симплекс-метод

 

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

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

В улучшенном симплекс-методе реализуется та же основная идея, что  и в обычном симплекс-методе, но здесь на каждой итерации пересчитывается  не вся матрица A^-1, обратная матрице ограничений A, а лишь та часть, которая относится к текущему базису A_x.

Особенности:

1) Данный метод используется при m намного меньше n.

2) Для вычислений всех оценок достаточно знать начальный вектор и вектор цен.

3) Для предотвращения зацикливания в модифицированном методе удобно применять правило Бленда³.

Правило Бленда можно сформулировать следующим образом:

a) Из переменных, вводимых в базу, нужно выбрать переменную с наименьшим номером.

b) Из переменных, выводимых из базы, нужно выбрать переменную с наименьшим номером.

4) Наличие двух таблиц - основной и вспомогательной, порядке их заполнения и некоторой специфичности расчётных формул.

Преимущества модифицированного симплексного метода:

• простота;
• эффективность вычислительной процедуры;
• меньшее количество вычислительных операций;
• меньший объем памяти ЭВМ;

Недостаток модифицированного симплекс-метода:

• накопление ошибок в связи с вычислением обратной матрицы.

 

Рассмотрим алгоритм решения задачи данным методом:

 

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

 

F(x)= -5x₁ + х₂ - 2х₃ → max.

-x₁ - 5x₂ + 3х₃ = 4

2x₁ + 5x₂ - 3х₃ ≥2

2х₁ + 4х₂ ≤ -4

 

Шаг №0. Сведем задачу ЛП к нахождению минимума.

-x₁ - 5x₂ + 3х₃ = 4

2x₁ + 5x₂ - 3х₃ ≥2

2х₁ + 4х₂ ≤ -4

-F(x)= 5x₁ - х₂ + 2х₃ → min.

Если сразу задана функция минимизации (min), то Шаг №0 пропускаем.

Приводим из системы  неравенств в систему уравнений, вводя дополнительные переменные:

-x₁ - 5x₂ + 3х₃ = 4

2x₁ + 5x₂ - 3х₃ - х₄ = 2

2х₁ + 4х₂ + х₅= -4

-F(x)= 5x₁ - х₂ + 2х₃ → min.

 

 

 

 

В матричной форме:

* Матрица А     -1 -5 3 0 0

                             2 5 -3 -1 0

                             2 4 0 0 1

 

* Матрица В      4

                            2

                           -4

 

или B^T = (4; 2; -4).

Тогда задачу ЛП можно  записать следующим образом:

A x X = B                                                                                                         (2.3.1)

X ≥ 0, X = (x₁, x₂, x₃, x₄, x₅)                                                                                        (2.3.2)

F(x) = Z = C * X → min                                                                                   (2.3.3)

Базисные переменные: x₁, x₂, x₃

Небазисные переменные: x₄, x₅

Преобразуем матрицу А, выделяя  единичную матрицу I:

-1/3 -5/3 1 0 0

-1 0 0 1 0

2 4 0 0 1

 

Шаг №1.

В начале первого цикла нам известны обратная матрица A^-1 (единичная матрица), базисное решение xb = A^-1 * b:

1 0 0

0 1 0

0 0 1      и xb = (4; 2; -4).

 

Шаг №2.

Образуем для каждой небазисной переменной характеристическую разность d_j, используя уравнение:

d_j = c_j - s_j x P_j,                                                                                                   (2.3.4)

где s - двойственные переменные, которые можно найти следующим  образом:

s_j = c_x * A^-1,                                                                                               (2.3.5)

где c_x - вектор коэффициентов целевой функции при базисных переменных.

c_x = (-5; 1; -2);

s_j = c_x x A^-1 = (-5; 1; -2);

d_j = (-5; 1; -2) - (-5; 1; -2) = (0; 0; 0).

 

Шаг №3.

Предполагая, что используется стандартное правило выбора вводимого  столбца, находим: s = min d_j.

s = -5, индекс столбца  p = 1.

 

Шаг №4.

Если s ≥ 0 - процедура  останавливается. Текущее базисное решение является оптимальным.

 

Шаг №5.

Если s ≤ 0, вычисляем преобразованный  столбец P:

P_-p = A^-1 x P_p;                                                                                                    (2.3.6)

P_-1 = (-1/3; -1; 2);

P_-p = (a_1s,a_2s,...,a_ms).

Если все a_is ≤ 0 - процедура останавливается: оптимум неограничен.

 

Шаг №6.

В противном случае находим  выводимую из базиса переменную:

xb_r / a_rs = min (a_is ≥ 0)                                                                                      (2.3.7)

 

Шаг №7. Строим матрицу и трансформируем ее с ведущим элементом a_rs.

 

2.4 Алгоритм метода искусственного  базиса

Для того, чтобы воспользоваться стандартной процедурой симплекс-метода на первом этапе, необходимо выполнить замену. Ввести искусственную целевую функцию F′ = -F.

Представление исходной системы неравенств ограничений  в виде системы равенств:

a_i1*x₁ + … + a_ij*x_j = b_i                                                                                      (2.4.1)

Ввод искусственных  или вспомогательных неизвестных Z_i по числу уравнений в системе переменные Z_i образуют опорный план:

Z_i = b_i - (a_i1*x₁ + … + a_ij*x_j)                                                                             (2.4.2)

Формирование искусственной целевой функции, выраженной через искусственные переменные:

F = Z₁ + Z₂ + … + Z_m → min                                                                            (2.4.3)

Используем симплекс-метод для минимизации целевой функции, при этом возможны 2 пути:

* F_min > 0

В этом случае система уравнений, исходная система ограничений не имеет неотрицательных решений, а это значит, что и исходная задача ЛП с такой системой ограничений не имеет решений

* F_min = 0

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

На этом первый этап закончен и приступаем к оптимизации имеющегося плана.

 

 

2.5 Двойственный симплекс-метод

Непосредственное приложение теории двойственности к вычислительным алгоритмам линейного программирования позволило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода последовательного уточнения оценок. Впервые он был предложен Лемке в 1954 г.

Теорема двойственности подсказывает, что симплекс-метод, примененный  к двойственной задаче, может дать решение и прямой задачи (если обе  задачи ЛП имеют допустимые векторы).

Идея двойственного  симплекс-метода состоит в том, что, переходя от одной двойственно допустимой  базы к другой, нужно получить такую базу, для которой q_i0 ≥ 0 (i = 1, 2, …, s).

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

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

Пусть дана задача линейного  программирования, в которой единичными являются m производственных векторов Pj (P1, P2, … , Pm).

Y = c₁x₁ + c₂x₁+ … + c_nx_n → max                                                                    (2.5.1)

x₁P₁ + x₂P₂ +… + x_mP_m + x_m+1P_m+1 + x_nP_n = b                                                  (2.5.2)

x_j ≥ 0 (j = 1, …, n)                                                                                             (2.5.3)

Где  P₁ = [1, 0, 0, …, 0, 0]

P₂ = [0, 1, 0, …, 0, 0]

…

P_m = [0, 0, 0, …, 0, 1]

P_m+1 = [a₁₁, a₂₁, …, a_m1]

…

P_n = [a_1n, a_2n, …, a_mn]

Среди b_i есть отрицательные.

В данном случае X = (b₁,b₂,…,b_m,0,0) - решение системы (2). Однако оно не является решением (1)-(3), т.к. b_i может быть отрицательным числом.

Поскольку P₁, … ,P_m - единичные, каждый из P_j (j от 1 до m) можно представить виде линейной комбинации данных векторов, причем коэффициенты разложения P_j по P₁,…,P_m - некоторые числа y_ij (i от 1 до m; j от 1 до n), так что можно найти D_j: