Simplex Method and task 18 advanced development for several variables (more then 2)

Найти минимальное целое А такое,что для всех неотрицательных х1,х2,х3 
в R^3 имеет место :-

(6x1+5x2+5x3 <A)v(3x1+6x2+4x3>180)v(2x1+x2+2x3>50)v(2x1+3x2+x3>40) = 1
x1 >=0;
x2 >=0;
x3 >=0;
Общая постановка задачи :-

Смотри Википедия Симплекс Метод

Симплекс-метод.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 6x1+5x2+5x3 при следующих условиях-ограничений.
3x1+6x2+4x3≤180
2x1+x2+2x3≤50
2x1+3x2+x3≤40
Для построения первого опорного плана систему неравенств приведем 
к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. 
В 2-м неравенстве смысла (≤) вводим базисную переменную x5. 
В 3-м неравенстве смысла (≤) вводим базисную переменную x6.

3x1+6x2+4x3+x4 = 180
2x1+x2+2x3+x5 = 50
2x1+3x2+x3+x6 = 40

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A =  
3 6 4 1 0 0
2 1 2 0 1 0
2 3 1 0 0 1
 

Базисные переменные это переменные, которые входят только в одно 
уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:

X0 = (0,0,0,180,50,40)

Базисное решение называется допустимым, если оно неотрицательно.
Базис B   x1 x2 x3 x4 x5 x6
x4    180 3  6  4  1  0  0
x5    50  2  1  2  0  1  0
x6    40  2  3  1  0  0  1
F(X0) 0  -6 -5 -5  0  0  0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке 
находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, 
так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (180 : 3 , 50 : 2 , 40 : 2 ) = 20

Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис B  x1 x2 x3 x4 x5 x6 min
x4   180 3  6  4  1  0  0  60
x5   50  2  1  2  0  1  0  25
x6   40  2  3  1  0  0  1  20
F(X1) 0 -6 -5 -5  0  0  0 

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. 
Вместо переменной x6 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена
в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=2.
На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 1, включая элементы индексной строки, 
определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены 
в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), 
А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.




Получаем новую симплекс-таблицу:
Базис B   x1 x2   x3  x4 x5 x6
x4    120 0  3/2 5/2  1  0 -3/2
x5    10  0  -2   1   0  1 -1
x1    20  1 3/2  1/2  0  0  1/2
F(X1) 120 0  4   -2   0  0  3 

 Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной 
строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, 
так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (120 : 3/2 , 10 : 1 , 20 : 1/2 ) = 10 

 Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис B   x1  x2  x3 x4 x5 x6  min
x4    120  0  3/2 5/2 1 0 -3/2 48
x5    10   0  -2  1   0 1 -1   10
x1    20   1  3/2 1/2 0 0 1/2  40
F(X2) 120 0 4 -2 0 0 3 

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. 
Вместо переменной x5 в план 2 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 2, получена 
в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=1. 
На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули.
Таким образом, в новом плане 2 заполнены строка x3 и столбец x3. 
Все остальные элементы нового плана 2, включая элементы индексной строки, 
определяются по правилу прямоугольника.


Получаем новую симплекс-таблицу:
Базис B  x1  x2  x3 x4 x5  x6
x4    95  0 13/2 0  1 -5/2  1
x3    10  0 -2   1  0  1   -1
x1    15  1  5/2 0  0 -1/2  1
F(X2) 140 0  0   0  0  2    1

1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. 
Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис B  x1  x2 x3 x4  x5 x6
x4    95  0 13/2 0  1 -5/2 1
x3    10  0 -2   1  0   1 -1
x1    15  1 5/2  0  0 -1/2 1
F(X3) 140 0  0   0  0   2  1

Оптимальный план можно записать так:
x1 = 15, x2 = 0, x3 = 10
F(X) = 6•15 + 5•0 + 5•10 = 140

Next Sample - Simplex Method and task 18 advanced development for several variables (more then 2)