Изложенная техника будет работать в пространсве R(n) n=3,4,5,.... Таким образом таким образом Задача 18 может легко поставлена для (x1,x2,x3) Методу изложенному ниже не менее 50 лет, а скорее более
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 5x1+4x2 при следующих условиях-ограничений.6x1+4x2≤24
x1+2x2≤6
-x1+x2≤1
x2≤2
Для построения первого опорного плана систему неравенств приведем
к системе уравнений путем введения дополнительных переменных
(переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5. В 4-м неравенстве смысла (≤) вводим базисную переменную x6.
6x1+4x2+x3 = 24 x1+2x2+x4 = 6 -x1+x2+x5 = 1 x2+x6 = 2
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 6 4 1 0 0 0
1 2 0 1 0 0
-1 1 0 0 1 0
0 1 0 0 0 1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x3, x4, x5, x6 Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,24,6,1,2) Базисное решение называется допустимым, если оно неотрицательно. Базис B x1 x2 x3 x4 x5 x6 x3 24 6 4 1 0 0 0 x4 6 1 2 0 1 0 0 x5 1 -1 1 0 0 1 0 x6 2 0 1 0 0 0 1 F(X0) 0 -5 -4 0 0 0 0
Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (24 : 6 , 6 : 1 , - , - ) = 4 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки.
Получаем новую симплекс-таблицу:Базис B x1 x2 x3 x4 x5 x6 min x3 24 6 4 1 0 0 0 4 x4 6 1 2 0 1 0 0 6 x5 1 -1 1 0 0 1 0 - x6 2 0 1 0 0 0 1 - F(X1) 0 -5 -4 0 0 0 0 4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x1. Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=6. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули. Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (6), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:Получаем новую симплекс-таблицу: Базис B x1 x2 x3 x4 x5 x6 x1 4 1 2/3 1/6 0 0 0 x4 2 0 4/3 -1/6 1 0 0 x5 5 0 5/3 1/6 0 1 0 x6 2 0 1 0 0 0 1 F(X1) 20 0 -2/3 5/6 0 0 0 Итерация №1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (4 : 2/3 , 2 : 4/3 , 5 : 5/3 , 2 : 1 ) = 3/2 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (4/3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 min x1 4 1 2/3 1/6 0 0 0 6 x4 2 0 4/3 -1/6 1 0 0 3/2 x5 5 0 5/3 1/6 0 1 0 3 x6 2 0 1 0 0 0 1 2 F(X2) 20 0 -2/3 5/6 0 0 0 4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x2. Строка, соответствующая переменной x2 в плане 2, получена в результате  деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=11/3. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули. Таким образом, в новом плане 2 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы: B x1 x2 x3 x4 x5 x6
Базис B x1 x2 x3 x4 x5 x6
x1 3 1 0 1/4 -1/2 0 0
x2 3/2 0 1 -1/8 3/4 0 0
x5 5/2 0 0 3/8 -5/4 1 0
x6 1/2 0 0 1/8 -3/4 0 1
F(X2) 21 0 0 3/4 1/2 0 0
1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Базис B x1 x2 x3 x4 x5 x6
x1 3 1 0 1/4 -1/2 0 0
x2 3/2 0 1 -1/8 3/4 0 0
x5 5/2 0 0 3/8 -5/4 1 0
x6 1/2 0 0 1/8 -3/4 0 1
F(X3) 21 0 0 3/4 1/2 0 0
Оптимальный план можно записать так: x1 = 3, x2 = 3/2 F(X) = 5•3 + 4•3/2 = 21
