Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 11x1+10x2 при следующих условиях-ограничений.
7x1+8x2≤50
6x1+3x2≤35
4x1+x2≤17
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
7x1 + 8x2 + 1x3 + 0x4 + 0x5 = 50
6x1 + 3x2 + 0x3 + 1x4 + 0x5 = 35
4x1 + 1x2 + 0x3 + 0x4 + 1x5 = 17
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3, x4, x5
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,50,35,17)
Базисное решение называется допустимым, если оно неотрицательно.
Базис | B | x1 | x2 | x3 | x4 | x5 |
x3 | ||||||
x4 | ||||||
x5 | ||||||
F(X0) | -11 | -10 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (50: 7, 35: 6, 17: 4) = 41/4
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.
Базис | B | x1 | x2 | x3 | x4 | x5 | min |
x3 | 50/7 | ||||||
x4 | 35/6 | ||||||
x5 | 41/4 | ||||||
F(X1) | -11 | -10 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=4. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B | x1 | x2 | x3 | x4 | x5 |
50-(17 • 7):4 | 7-(4 • 7):4 | 8-(1 • 7):4 | 1-(0 • 7):4 | 0-(0 • 7):4 | 0-(1 • 7):4 |
35-(17 • 6):4 | 6-(4 • 6):4 | 3-(1 • 6):4 | 0-(0 • 6):4 | 1-(0 • 6):4 | 0-(1 • 6):4 |
17: 4 | 4: 4 | 1: 4 | 0: 4 | 0: 4 | 1: 4 |
0-(17 • -11):4 | -11-(4 • -11):4 | -10-(1 • -11):4 | 0-(0 • -11):4 | 0-(0 • -11):4 | 0-(1 • -11):4 |
Получаем новую симплекс-таблицу:
Базис | B | x1 | x2 | x3 | x4 | x5 |
x3 | 81/4 | 25/4 | -7/4 | |||
x4 | 19/2 | 3/2 | -3/2 | |||
x1 | 17/4 | 1/4 | 1/4 | |||
F(X1) | 187/4 | -29/4 | 11/4 |
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (201/4: 61/4, 91/2: 11/2, 41/4: 1/4) = 36/25
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (61/4) и находится на пересечении ведущего столбца и ведущей строки.
Базис | B | x1 | x2 | x3 | x4 | x5 | min |
x3 | 81/4 | 61/4 | -7/4 | 36/25 | |||
x4 | 19/2 | 3/2 | -3/2 | 19/3 | |||
x1 | 17/4 | 1/4 | 1/4 | ||||
F(X2) | 187/4 | -71/4 | 11/4 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 2 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x3 плана 1 на разрешающий элемент РЭ=61/4. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B | x1 | x2 | x3 | x4 | x5 |
201/4: 61/4 | 0: 61/4 | 61/4: 61/4 | 1: 61/4 | 0: 61/4 | -13/4: 61/4 |
91/2-(201/4 • 11/2):61/4 | 0-(0 • 11/2):61/4 | 11/2-(61/4• 11/2):61/4 | 0-(1 • 11/2):61/4 | 1-(0 • 11/2):61/4 | -11/2-(-13/4 • 11/2):61/4 |
41/4-(201/4 •1/4):61/4 | 1-(0 •1/4):61/4 | 1/4-(61/4 •1/4):61/4 | 0-(1 •1/4):61/4 | 0-(0 •1/4):61/4 | 1/4-(-13/4• 1/4):61/4 |
463/4-(201/4 • -71/4):61/4 | 0-(0 • -71/4):61/4 | -71/4-(61/4 • -71/4):61/4 | 0-(1 • -71/4):61/4 | 0-(0 • -71/4):61/4 | 23/4-(-13/4 • -71/4):61/4 |
Получаем новую симплекс-таблицу:
Базис | B | x1 | x2 | x3 | x4 | x5 |
x2 | 81/25 | 4/25 | -7/25 | |||
x4 | 116/25 | -6/25 | -27/25 | |||
x1 | 86/25 | -1/25 | 8/25 | |||
F(X2) | 1756/25 | 29/25 | 18/25 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис | B | x1 | x2 | x3 | x4 | x5 |
x2 | 81/25 | 4/25 | -7/25 | |||
x4 | 116/25 | -6/25 | -27/25 | |||
x1 | 86/25 | -1/25 | 8/25 | |||
F(X3) | 1756/25 | 29/25 | 18/25 |
Оптимальный план можно записать так:
x1 = 311/25, x2 = 36/25
F(X) = 11•311/25 + 10•36/25 = 706/25