Simplex Method and task 18 advanced development for limited number of x1,x2, ,x(n)

Изложенная техника будет работать в пространсве 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, получена в результате&nbsp
деления всех элементов строки 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