Метод оптимальных решений

 

Симплекс-метод.

 

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

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

2x₁ + x₂≤30

2x₁ + 2x₂≤40

x₁ + 2x₂≤36

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

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

2x₁ + 1x₂ + 1x₃ + 0x₄ + 0x₅ = 30

2x₁ + 2x₂ + 0x₃ + 1x₄ + 0x₅ = 40

1x₁ + 2x₂ + 0x₃ + 0x₄ + 1x₅ = 36

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

 

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

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

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

x₃, x₄, x₅,

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

X1 = (0,0,30,40,36)

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

 

Базис	B	x1	x2	x3	x4	x5
x3	30	2	1	1	0	0
x4	40	2	2	0	1	0
x5	36	1	2	0	0	1
F(X0)	0	-3	-2	0	0	0

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

Итерация  №0.

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

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

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

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

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

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

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

min (30 : 2 , 40 : 2 , 36 : 1 ) = 15

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

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

 

Базис	B	x1	x2	x3	x4	x5	min
x3	30	2	1	1	0	0	15
x4	40	2	2	0	1	0	20
x5	36	1	2	0	0	1	36
F(X1)	0	-3	-2	0	0	0	0

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

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

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

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

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

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

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

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

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

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

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

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

 

B	x 1	x 2	x 3	x 4	x 5
30 : 2	2 : 2	1 : 2	1 : 2	0 : 2	0 : 2
40-(30 • 2):2	2-(2 • 2):2	2-(1 • 2):2	0-(1 • 2):2	1-(0 • 2):2	0-(0 • 2):2
36-(30 • 1):2	1-(2 • 1):2	2-(1 • 1):2	0-(1 • 1):2	0-(0 • 1):2	1-(0 • 1):2
0-(30 • -3):2	-3-(2 • -3):2	-2-(1 • -3):2	0-(1 • -3):2	0-(0 • -3):2	0-(0 • -3):2

 

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

 

Базис	B	x1	x2	x3	x4	x5
x1	15	1	1/2	1/2	0	0
x4	10	0	1	-1	1	0
x5	21	0	3/2	-1/2	0	1
F(X1)	45	0	-1/2	3/2	0	0

Итерация  №1.

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

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

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

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

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

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

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

min (15 : ¹/₂ , 10 : 1 , 21 : 1¹/₂ ) = 10

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

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

 

Базис	B	x1	x2	x3	x4	x5	min
x1	15	1	1/2	1/2	0	0	30
x4	10	0	1	-1	1	0	10
x5	21	0	11/2	-1/2	0	1	14
F(X2)	45	0	-1/2	11/2	0	0	0

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

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

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

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

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

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

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

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

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

 

B	x 1	x 2	x 3	x 4	x 5
15-(10 • 1/2):1	1-(0 • 1/2):1	1/2-(1 • 1/2):1	1/2-(-1 • 1/2):1	0-(1 • 1/2):1	0-(0 • 1/2):1
10 : 1	0 : 1	1 : 1	-1 : 1	1 : 1	0 : 1
21-(10 • 11/2):1	0-(0 • 11/2):1	11/2-(1 • 11/2):1	-1/2-(-1 • 11/2):1	0-(1 • 11/2):1	1-(0 • 11/2):1
45-(10 • -1/2):1	0-(0 • -1/2):1	-1/2-(1 • -1/2):1	11/2-(-1 • -1/2):1	0-(1 • -1/2):1	0-(0 • -1/2):1

 

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

 

Базис	B	x1	x2	x3	x4	x5
x1	10	1	0	1	-1/2	0
x2	10	0	1	-1	1	0
x5	6	0	0	1	-3/2	1
F(X2)	50	0	0	1	1/2	0

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

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

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

 

Базис	B	x1	x2	x3	x4	x5
x1	10	1	0	1	-1/2	0
x2	10	0	1	-1	1	0
x5	6	0	0	1	-3/2	1
F(X3)	50	0	0	1	1/2	0

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

x₁ = 10

x₂ = 10

F(X) = 3•10 + 2•10 = 50

Анализ  оптимального плана.

В оптимальный план вошла дополнительная переменная x₅. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 6