Комплект индивидуальных заданий для выполнения практических работ

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(x)=29x1+32x2+53x3 при следующих условиях-ограничений:
2x1+3x2+5x3≤35;3x1+5x2+10x3≤52;x1+9x2+x3≤27;x1≥0; x2≥0; x3≥0
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.
2x1+3x2+5x3+x4 = 35
3x1+5x2+10x3+x5 = 52
x1+9x2+x3+x6 = 27
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A=2351003510010191001
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,35,52,27)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6
x4 35 2 3 5 1 0 0
x5 52 3 5 10 0 1 0
x6 27 1 9 1 0 0 1
F(X0) 0 -29 -32 -53 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3 . Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (35 : 5 , 52 : 10 , 27 : 1 ) = 51/5
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (10) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 min
x4 35 2 3 5 1 0 0 7
x5 52 3 5 10 0 1 0 26/5
x6 27 1 9 1 0 0 1 27
F(X1) 0 -29 -32 -53 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=10. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А∙В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (10), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6
35-(52 • 5):10 2-(3 • 5):10 3-(5 • 5):10 5-(10 • 5):10 1-(0 • 5):10 0-(1 • 5):10 0-(0 • 5):10
52 : 10 3 : 10 5 : 10 10 : 10 0 : 10 1 : 10 0 : 10
27-(52 • 1):10 1-(3 • 1):10 9-(5 • 1):10 1-(10 • 1):10 0-(0 • 1):10 0-(1 • 1):10 1-(0 • 1):10
0-(52 • -53):10 -29-(3 • -53):10 -32-(5 • -53):10 -53-(10 • -53):10 0-(0 • -53):10 0-(1 • -53):10 0-(0 • -53):10
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6
x4 9 1/2 1/2 0 1 -1/2 0
x3 26/5 3/10 1/2 1 0 1/10 0
x6 109/5 7/10 17/2 0 0 -1/10 1
F(X1) 1378/5 -131/10 -11/2 0 0 53/10 0
Итерация №1.
1