Если линия уровня целевой функции параллельна прямой (или гиперплоскости), соответствующей связывающему ограничению, то могут возникнуть альтернативные оптимальные планы X*. В этом случае целевая функция принимает одно и тоже оптимальное значение в некоторой совокупности точек пространства решений.
Пример. Определим максимальное значение целевой функции F(X) = 2x1 + 4x2 при следующих условиях-ограничений.
x1 + 2x2<=5
x1 + x2<=4
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (<=) вводим базисную переменную x3. В 2-м неравенстве смысла (<=) вводим базисную переменную x4.
1x1 + 2x2 + 1x3 + 0x4 = 5
1x1 + 1x2 + 0x3 + 1x4 = 4
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных:
x3, x4,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,5,4)
Базисное решение называется допустимым, если оно неотрицательно.
| Базис
| B
| x1
| x2
| x3
| x4
|
| x3
|
|
|
|
|
|
| x4
|
|
|
|
|
|
| F(X0)
|
| -2
| -4
|
|
|
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (5: 2, 4: 1) = 21/2
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
| Базис
| B
| x1
| x2
| x3
| x4
| min
|
| x3
|
|
|
|
|
| |
| x4
|
|
|
|
|
|
|
| F(X1)
|
| -2
| -4
|
|
|
|
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x3 в план 1 войдет переменная x2 .
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=2
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
| B
| x 1
| x 2
| x 3
| x 4
|
| 5: 2
| 1: 2
| 2: 2
| 1: 2
| 0: 2
|
| 4-(5 • 1):2
| 1-(1 • 1):2
| 1-(2 • 1):2
| 0-(1 • 1):2
| 1-(0 • 1):2
|
| 0-(5 • -4):2
| -2-(1 • -4):2
| -4-(2 • -4):2
| 0-(1 • -4):2
| 0-(0 • -4):2
|
Получаем новую симплекс-таблицу:
| Базис
| B
| x1
| x2
| x3
| x4
|
| x2
| 21/2
| 1/2
|
| 1/2
|
|
| x4
| 11/2
| 1/2
|
| -1/2
|
|
| F(X1)
|
|
|
|
|
|
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис
| B
| x1
| x2
| x3
| x4
|
| x2
| 21/2
| 1/2
|
| 1/2
|
|
| x4
| 11/2
| 1/2
|
| -1/2
|
|
| F(X2)
|
|
|
|
|
|
Оптимальный план можно записать так:
x2 = 21/2
F(X) = 4•21/2 = 10
Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x4. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 11/2
В индексной строке в 1-ом столбце нулевое значение. В столбце, содержащем этот нуль, имеется хотя бы один положительный элемент. Следовательно, задача имеет множество оптимальных планов.
Покажем это на примере. Свободную переменную, соответствующую указанному столбцу, вносим в базис (вместо x2), выполнив соответствующие этапы алгоритма.
После преобразований получаем новую таблицу:
| Базис
| B
| x1
| x2
| x3
| x4
|
| x1
|
|
|
|
|
|
| x4
| -1
|
| -1
| -1
|
|
| F(X)
|
|
|
|
|
|
В результате получен второй оптимальный план с другим набором базисных переменных.
