Симплекс-метод.
Copyright © Semestr.RU

Решим прямую задачу линейного программирования  симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 3x1+2x2 при следующих условиях-ограничений.
x1+2x2≤6
x1+x2≤5
2x1+2x2≤10
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5. 
1x1 + 2x2 + 1x3 + 0x4 + 0x5 = 6
1x1 + 1x2 + 0x3 + 1x4 + 0x5 = 5
2x1 + 2x2 + 0x3 + 0x4 + 1x5 = 10
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

Базис	В	x1	x2	x3	x4	x5	
x3	6	1	2	1	0	0	
x4	5	1	1	0	1	0	
x5	10	2	2	0	0	1	
F(X0)	0	-3	-2	0	0	0	

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

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

Базис	В	x1	x2	x3	x4	x5	min	
x3	6	1	2	1	0	0	6	
x4	5	1	1	0	1	0	5	
x5	10	2	2	0	0	1	5	
F(X1)	0	-3	-2	0	0	0	0	

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

B	x1	x2	x3	x4	x5	
						
5 / 1 = 5	1 / 1 = 1	1 / 1 = 1	0 / 1 = 0	1 / 1 = 1	0 / 1 = 0	

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

Базис	В	x1	x2	x3	x4	x5	
x3	1	0	1	1	-1	0	
x1	5	1	1	0	1	0	
x5	0	0	0	0	-2	1	
F(X1)	15	0	1	0	3	0	

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

Базис	В	x1	x2	x3	x4	x5	
x3	1	0	1	1	-1	0	
x1	5	1	1	0	1	0	
x5	0	0	0	0	-2	1	
F(X2)	15	0	1	0	3	0	

Оптимальный план можно записать так: 
x1 = 5
x3 = 1
F(X) = 3*5 = 15

Анализ оптимальной симплекс-таблицы.
В оптимальный план вошла дополнительная переменная x3. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 1.
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 1> 0 в столбце x2 означает, что использование x2 - не выгодно.
Значение 3 в столбце x4 означает, что теневая цена (двойственная оценка) равна 3.

Решение было получено и оформлено с помощью сервиса:
Симплекс-метод
Вместе с этой задачей решают также:
Графический метод решения задач линейного программирования
Двойственный симплекс-метод
Двойственная задача линейного программирования
Метод Гомори
Транспортная задача
Copyright © Semestr.RU