Решение ручным способом

Определим минимальное значение целевой функции F(X) = - 6x₁ - 8x₂ при следующих условиях-ограничений.

2x₁ + 5x₂≤20

12x₁ + 6x₂≤72

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≤) вводим базисную переменную x₄.

2x₁ + 5x₂ + 1x₃ + 0x₄ = 20

12x₁ + 6x₂ + 0x₃ + 1x₄ = 72

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

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Решим систему уравнений относительно базисных переменных:

x₃, x₄,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,20,72)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4
x3
x4
F(X0)

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (20: 5, 72: 6) = 4

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	min
x3
x4
F(X1)

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 1 войдет переменная x₂ .

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₃ плана 0 на разрешающий элемент РЭ=5

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₂ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂ .

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4
20: 5	2: 5	5: 5	1: 5	0: 5
72-(20 • 6):5	12-(2 • 6):5	6-(5 • 6):5	0-(1 • 6):5	1-(0 • 6):5
0-(20 • 8):5	6-(2 • 8):5	8-(5 • 8):5	0-(1 • 8):5	0-(0 • 8):5

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4
x2		2/5		1/5
x4		93/5		-11/5
F(X1)	-32	24/5		-13/5

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:

min (4: ²/₅, 48: 9³/₅) = 5

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (9³/₅) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	min
x2		2/5		1/5
x4		93/5		-11/5
F(X2)	-32	24/5		-13/5

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 2 войдет переменная x₁ .

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₄ плана 1 на разрешающий элемент РЭ=9³/₅

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₁ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁ .

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4
4-(48 • 2/5):93/5	2/5-(93/5 • 2/5):93/5	1-(0 • 2/5):93/5	1/5-(-11/5 • 2/5):93/5	0-(1 • 2/5):93/5
48: 93/5	93/5: 93/5	0: 93/5	-11/5: 93/5	1: 93/5
-32-(48 • 24/5):93/5	24/5-(93/5 • 24/5):93/5	0-(0 • 24/5):93/5	-13/5-(-11/5 • 24/5):93/5	0-(1 • 24/5):93/5

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4
x2				1/4	-1/24
x1				-1/8	5/48
F(X2)	-46			-11/4	-7/24

1. Проверка критерия оптимальности.

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

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4
x2				1/4	-1/24
x1				-1/8	5/48
F(X3)	-46			-11/4	-7/24

Оптимальный план можно записать так:

x₂ = 2

x₁ = 5

F(X) = -8•2 + -6•5 = -46