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