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

Базис	В	x1	x2	x3	x4	x5	x6	x7
x2	1.3	0	1	-2.6	0.2	-0.8	-0.2	0.8
x1	0.7	1	0	-1.4	-0.2	-0.2	0.2	0.2
F(X3)	-9.1	0	0	30.2	3.6	5.6	1.4	-5.6+M

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Оптимальный план можно записать так: x₂ = 1.3 x₁ = 0.7 F(X) = -7*1.3 = -9.1

Значит, минимальное значение равно -9.1

Следовательно, двойственная задача линейного программирования будет иметь вид:

F(Y)=+7Y₂+12Y₃+5Y₄ (min)

Ограничения:

1Y1	+	1Y2	-	4Y3	+	0Y4		≥	-2
-4Y1	+	1Y2	+	3Y3	+	1Y4		≥	1.5

Y1	≥	0
Y2	≥	0
Y3	≥	0
Y4	≥	0

Решим двойственную задачу линейного программирования симплексным методом, с использованием симплексной таблицы Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1). Определим минимальное значение целевой функции F(X) = 7x₂+12x₃+5x₄ при следующих условиях-ограничений. -x₁-x₂+4x₃≤2 -4x₁+x₂+3x₃+x₄≥1.5 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x₅. В 2-м неравенстве смысла (≥) вводим базисную переменную x₆ со знаком минус.  -1x₁-1x₂ + 4x₃ + 0x₄ + 1x₅ + 0x₆ = 2 -4x₁ + 1x₂ + 3x₃ + 1x₄ + 0x₅-1x₆ = 1.5 Введем искусственные переменные x: в 2-м равенстве вводим переменную x₇;  -1x₁-1x₂ + 4x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ = 2 -4x₁ + 1x₂ + 3x₃ + 1x₄ + 0x₅-1x₆ + 1x₇ = 1.5 Для постановки задачи на минимум целевую функцию запишем так: F(X) = 7x₂+12x₃+5x₄+Mx₇ → min За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается. Полученный базис называется искусственным, а метод решения называется методом искусственного базиса. Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения. Из уравнений выражаем искусственные переменные: x₇ = 1.5+4x₁-x₂-3x₃-x₄+x₆ которые подставим в целевую функцию: F(X) = 7x₂ + 12x₃ + 5x₄ + M(1.5+4x₁-x₂-3x₃-x₄+x₆) → min или F(X) = (4M)x₁+(7-M)x₂+(12-3M)x₃+(5-M)x₄+(M)x₆+(1.5M) → min Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

-1	-1	4	0	1	0	0
-4	1	3	1	0	-1	1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана. Решим систему уравнений относительно базисных переменных: x₅, x₇ Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,2,0,1.5) Базисное решение называется допустимым, если оно неотрицательно.

Базис	В	x1	x2	x3	x4	x5	x6	x7
x5	2	-1	-1	4	0	1	0	0
x7	1.5	-4	1	3	1	0	-1	1
F(X0)	1.5M	-4M	-7+M	-12+3M	-5+M	0	-M	0

Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. 2. Определение новой базисной переменной. В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент . 3. Определение новой свободной переменной. Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 и из них выберем наименьшее: Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	x6	x7	min
x5	2	-1	-1	4	0	1	0	0	0.5
x7	1.5	-4	1	3	1	0	-1	1	0.5
F(X1)	1.5M	-4M	-7+M	-12+3M	-5+M	0	-M	0	0

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

B	x1	x2	x3	x4	x5	x6	x7
2 / 4 = 0.5	-1 / 4 = -0.25	-1 / 4 = -0.25	4 / 4 = 1	0 / 4 = 0	1 / 4 = 0.25	0 / 4 = 0	0 / 4 = 0

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6	x7
x3	0.5	-0.25	-0.25	1	0	0.25	0	0
x7	0	-3.25	1.75	0	1	-0.75	-1	1
F(X1)	6	-3-3.25M	-10+1.75M	0	-5+M	3-0.75M	-M	0

Итерация №1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. 2. Определение новой базисной переменной. В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент . 3. Определение новой свободной переменной. Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее: Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (1.75) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	x6	x7	min
x3	0.5	-0.25	-0.25	1	0	0.25	0	0	-
x7	0	-3.25	1.75	0	1	-0.75	-1	1	0
F(X2)	6	-3-3.25M	-10+1.75M	0	-5+M	3-0.75M	-M	0	0

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

B	x1	x2	x3	x4	x5	x6	x7
0 / 1.75 = 0	-3.25 / 1.75 = -1.86	1.75 / 1.75 = 1	0 / 1.75 = 0	1 / 1.75 = 0.57	-0.75 / 1.75 = -0.43	-1 / 1.75 = -0.57	1 / 1.75 = 0.57

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6	x7
x3	0.5	-0.71	0	1	0.14	0.14	-0.14	0.14
x2	0	-1.86	1	0	0.57	-0.43	-0.57	0.57
F(X2)	6	-21.57	0	0	0.71	-1.29	-5.71	5.71-M

Итерация №2. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. 2. Определение новой базисной переменной. В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₄, так как это наибольший коэффициент . 3. Определение новой свободной переменной. Вычислим значения D_i по строкам как частное от деления: b_i / a_i4 и из них выберем наименьшее: Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (0.57) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	x6	x7	min
x3	0.5	-0.71	0	1	0.14	0.14	-0.14	0.14	3.5
x2	0	-1.86	1	0	0.57	-0.43	-0.57	0.57	0
F(X3)	6	-21.57	0	0	0.71	-1.29	-5.71	5.71-M	0

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

B	x1	x2	x3	x4	x5	x6	x7
0 / 0.57 = 0	-1.86 / 0.57 = -3.25	1 / 0.57 = 1.75	0 / 0.57 = 0	0.57 / 0.57 = 1	-0.43 / 0.57 = -0.75	-0.57 / 0.57 = -1	0.57 / 0.57 = 1

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6	x7
x3	0.5	-0.25	-0.25	1	0	0.25	0	0
x4	0	-3.25	1.75	0	1	-0.75	-1	1
F(X3)	6	-19.25	-1.25	0	0	-0.75	-5	5-M