Таблица 10. Затраты времени на выпуск единицы продукции (по типам машин и видам продукции), машино-ч/шт.

Определим максимальное значение целевой функции F(X) = 10x1+8x2+9x3+12x4 при следующих условиях-ограничений.
4x1+2x2+x4≤800
2x1+2x3+x4≤700
2x1+2x2+2x3≤740
2x1+2x2+x3+x4≤770
2x2+2x3+2x4≤760
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных
В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7. В 4-м неравенстве смысла (≤) вводим базисную переменную x8. В 5-м неравенстве смысла (≤) вводим базисную переменную x9.
4x1+2x2+x4+x5 = 800
2x1+2x3+x4+x6 = 700
2x1+2x2+2x3+x7 = 740
2x1+2x2+x3+x4+x8 = 770
2x2+2x3+2x4+x9 = 760
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
4 2 0 1 1 0 0 0 0
2 0 2 1 0 1 0 0 0
2 2 2 0 0 0 1 0 0
2 2 1 1 0 0 0 1 0
0 2 2 2 0 0 0 0 1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.Решим систему уравнений относительно базисных переменных: x5, x6, x7,
x8, x9
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,0,800,700,740,770,760)Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x5 800 4 2 0 1 1 0 0 0 0
x6 700 2 0 2 1 0 1 0 0 0
x7 740 2 2 2 0 0 0 1 0 0
x8 770 2 2 1 1 0 0 0 1 0
x9 760 0 2 2 2 0 0 0 0 1
F(X0) 0 -10 -8 -9 -12 0 0 0 0 0
Переходим к основному алгоритму симплекс-метода.1. Проверка критерия оптимальности.Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.2. Определение новой базисной переменной.В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.3. Определение новой свободной переменной.Вычислим значения Di по строкам как частное от деления: bi / ai4и из них выберем наименьшее:min (800 : 1 , 700 : 1 , - , 770 : 1 , 760 : 2 ) = 380Следовательно, 5-ая строка является ведущей.Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9 min
x5 800 4 2 0 1 1 0 0 0 0 800
x6 700 2 0 2 1 0 1 0 0 0 700
x7 740 2 2 2 0 0 0 1 0 0 -
x8 770 2 2 1 1 0 0 0 1 0 770
x9 760 0 2 2 2 0 0 0 0 1 380
F(X1) 0 -10 -8 -9 -12 0 0 0 0 0
4 . Пересчет симплекс-таблицы.Формируем следующую часть симплексной таблицы. Вместо переменной x9 в план 1 войдет переменная x4.Строка, соответствующая переменной x4 в плане 1, получена в результате деления всех элементов строки x9 плана 0 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x4 записываем нули.Таким образом, в новом плане 1 заполнены строка x4 и столбец x4. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.НЭ = СЭ - (А*В)/РЭСТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6 x7 x8 x9
800-(760 • 1):2 4-(0 • 1):2 2-(2 • 1):2 0-(2 • 1):2 1-(2 • 1):2 1-(0 • 1):2 0-(0 • 1):2 0-(0 • 1):2 0-(0 • 1):2 0-(1 • 1):2
700-(760 • 1):2 2-(0 • 1):2 0-(2 • 1):2 2-(2 • 1):2 1-(2 • 1):2 0-(0 • 1):2 1-(0 • 1):2 0-(0 • 1):2 0-(0 • 1):2 0-(1 • 1):2
740-(760 • 0):2 2-(0 • 0):2 2-(2 • 0):2 2-(2 • 0):2 0-(2 • 0):2 0-(0 • 0):2 0-(0 • 0):2 1-(0 • 0):2 0-(0 • 0):2 0-(1 • 0):2
770-(760 • 1):2 2-(0 • 1):2 2-(2 • 1):2 1-(2 • 1):2 1-(2 • 1):2 0-(0 • 1):2 0-(0 • 1):2 0-(0 • 1):2 1-(0 • 1):2 0-(1 • 1):2
760 : 2 0 : 2 2 : 2 2 : 2 2 : 2 0 : 2 0 : 2 0 : 2 0 : 2 1 : 2
0-(760 • -12):2 -10-(0 • -12):2 -8-(2 • -12):2 -9-(2 • -12):2 -12-(2 • -12):2 0-(0 • -12):2 0-(0 • -12):2 0-(0 • -12):2 0-(0 • -12):2 0-(1 • -12):2
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x5 420 4 1 -1 0 1 0 0 0 -1/2
x6 320 2 -1 1 0 0 1 0 0 -1/2
x7 740 2 2 2 0 0 0 1 0 0
x8 390 2 1 0 0 0 0 0 1 -1/2
x4 380 0 1 1 1 0 0 0 0 1/2
F(X1) 4560 -10 4 3 0 0 0 0 0 6
Итерация №1.1