Задача 1
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 4x1 + 3x2-3 при следующих условиях-ограничений.
При вычислениях значение Fc = -3 временно не учитываем.
x1 + x2?11
– 5x1 + x2?5
2x1 – x2?4
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (?) вводим базисную переменную x3. В 2-м неравенстве смысла (?) вводим базисную переменную x4. В 3-м неравенстве смысла (?) вводим базисную переменную x5.
1x1 + 1x2 + 1x3 + 0x4 + 0x5 = 11
-5x1 + 1x2 + 0x3 + 1x4 + 0x5 = 5
2x1-1x2 + 0x3 + 0x4 + 1x5 = 4
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных: x3, x4, x5
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,11,5,4)
Базисное решение называется допустимым, если оно неотрицательно.
Базис
B
x1
x2
x3
x4
x5
x3
11
1
1
1
0
0
x4
5
-5
1
0
1
0
x5
4
2
-1
0
0
1
F(X0)
0
-4
-3
0
0
0
Переходим к основному алгоритму симплекс-метода.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi/ai1
и из них выберем наименьшее:
min (11: 1, –, 4: 2 ) = 2
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис
B
x1
x2
x3
x4
x5
min
x3
11
1
1
1
0
0
11
x4
5
-5
1
0
1
0
-
x5
4
2
-1
0
0
1
2
F(X1)
0
-4
-3
0
0
0
0
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=2
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямо