Решение
Так как симплекс-алгоритм разработан для задач ЛП в канонической форме, где требуется минимизировать целевую функцию, то нам требуется перейти от ограничений – неравенств к ограничениям равенствам. Для этого введем добавочные переменные x5, x6, x7 такие, что:
- 5x1 – x2 + 2x3 + х5 = 2
- x1 + x3 + x4 + х6 = 5 (5)
- 3x1 + 5x4 + х7 = 7
х5>= 0, х6>= 0, х7>= 0
Таким образом, мы сформулировали исходную задачу ЛП в канонической форме, т.е. с ограничениями равенствами. Число переменных n = 7 на 4 превышает число уравнений m = 3. Значит, четыре переменных могут быть выбраны в качестве свободных.
Из системы уравнений (5) видно, что в качестве свободных переменных проще всего выбрать x1, x2, x3, х4. Тогда базисные переменные x5, x6, x7 выражаются через свободные так:
5x1 + x2 – 2x3 + 2 = х5
x1 – x3 – x4 + 5 = х6 (6)
3x1 – 5x4 + 7 = х7
Этому набору свободных и базисных переменных соответствует базисное решение: x1 = x2 = x3 = x4 = 0, x5 = 2, x6 = 5, x7 = 7, которое является допустимым (x5 >= 0, x6 >= 0, x7 >= 0) и при этом z = 0. но является ли это решение оптимальным? Нет! Потому что в выражении целевой функции z, которая выражена через свободные переменные x1 и x3, коэффициент при x3 отрицателен. Значит, увеличивая x3, можно уменьшить z.
Попробуем увеличить x3. проследим по уравнениям (6), опасно ли это для других переменных? Для этого выпишем как изменяются базисные переменные при увеличении переменной x3, тогда как переменные x1, x2, x4 остаются равными нулю.
х5 = - 2x3 + 2
х6 = - x3 + 5
х7 = 7
Да, опасно для x5 и x6 – в эти уравнения переменная x3 входит с отрицательным коэффициентом, значит, при увеличении x3 соответствующие переменные x5 и x6 могут стать отрицательными.
Посмотрим, какие из этих переменных x5 или x6 раньше обратится в нуль при увеличении x3. Очевидно, x5: она станет равной нулю при x3 = 1, а величина x6 – только при x3 = 5. Поэтому выбираем переменную x5 и вводим ее в число свободных вместо x3. Чтобы “пере разрешить” систему (5) относительно новых базисных переменных x3, x6, x7 поступим следующим образом. В системе (6) уравнение, соответствующее выбранной переменной x5, разрешим относительно новой базисной переменной x3:
х3 = 5/2 * x1 + 1/2 * x2 – 1/2 * x5 + 1
Это выражение подставим вместо x3 в остальные уравнения системы (6). Итак, мы привели систему (5) к виду:
х3 = 5/2 * x1 + 1/2 * x2 – 1/2 * x5 + 1
х6 = - 3/2 * x1 – 1/2 * x2 – x4 + 1/2 * x5 + 4 (7)
х7 = 3 x1 – 5x4 + 7
со свободными переменными x1, x2, x4, x5 и базисными x3, x6, x7.
Выразим целевую функцию z через новые свободные переменные:
z = 5 x1 – 2x3 = 5x1 – 2(5/2 * x1 + 1/2 * x2 – 1/2 * x5 + 1) = - x2 + x5 - 2 (8)
Этому новому набору свободных и базисных переменных соответствует новое допустимое базисное решение:
x1 = x2 = x4 = x5 = 0, x3 = 1, x6 = 4, x7 = 7.
Значение целевой функции при этом решении равно z = -2. Это уже лучше, чем прежнее значение z = 0. Но является ли это решение оптимальным? Все еще нет, т.к. коэффициент при x2 в выражении (8) отрицателен. Итак, будем увеличивать x2. Посмотрим, для какой из переменных, стоящих в левых частях системы (7), это может быть “опасно”. Для этого выпишем как изменяются базисные переменные при увеличении переменной x2, тогда как остальные свободные переменные x1, x4, x5 остаются равными нулю,
х3 = 1/2x2 + 1
х6 = -1/2 * x2 + 4
х7 = 7
Только для x6 (в первое уравнение x2 входит с положительным коэффициентом, а в третье совсем не входит).
Итак, обменяем местами переменные x2 и x6 – первую выведем из числа свободных, а вторую – введем. Для этого разрешим уравнение, соответствующее переменной x6, системы (7) относительно x2 и подставим его в остальные уравнения системы (7). Получили еще один вид системы (5):
x2 = -3x1 – 2x4 + x5 – 2x6 + 8
х3 = x1 – x4 – x6 + 5
х7 = 3 x1 – 5x4 + 7
Выразим целевую функцию z через новые свободные переменные:
z = -2x2 + x5 – 2= – (–3x1 – 2x4 + x5 – 2x6 + 8) + x5 – 2 = 3x1 + 2x4 + 2x6 – 10 (9)
Новому набору свободных и базисных переменных соответствует новое допустимое базисное решение:
x1 = x4 = x5 = x6 = 0, x2 = 8, x3 = 5, x7 = 7.
Целевая функция z равна –10 для этого решения. Является ли это решение оптимальным? На этот раз – да, т.к. коэффициенты при всех свободных переменных в выражении (9) неотрицательны.
Пример 2.
Имеется задача линейного программирования.
z = 2x1 + x2 max
x1 – x2 <= 10
x1 <= 20
x1 >= 0, x2 >= 0