Алгоритм решения задач симплексным методом

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

Если целевая функция задачи достигает экстремума в двух угловых точках, то задача имеет бесконечное множество решений. Оптимальным решением является любая выпуклая комбинация этих точек. После нахождения оптимального решения вычислить значение целевой функции на этом решении.

Пусть область допустимых решений изображается многоугольником AВCDECH. Предположим, чтo его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать семь допустимых базисных решений, соответствующих семи угловым точкам многоугольника. Из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем - к оптимальной точке С.

Рис. 1

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

Идея последовательного улучшения решения и является основой универсального метода решения задач линейного программирования - симплексного метода.

Геометрическая интерпретация для понимания логики симплекс-метода имеет смысл только при n = 1,2,3, то есть до третьего измерения включительно.

Реализуется 2 типа геометрических задач:

1) В пространстве представления решений;

2) Представление в пространстве условий.

Рассмотрим примеры основных вариантов решения задачи линейного программирования в графическом виде:

1) Графическое решение существует и оно единственное.

Y=12x1+15x2→max

4x1+3x2 ≤12

2x1+5x2 ≤10

x1≥0, x2≥0

 

Рис. 2

Любые допустимые решения задачи находятся в области AВС – вершины данной фигуры называются экстремальными, крайними точками множества. При этом точки А, В, С являются допустимыми экстремальными точками, а точка D - недопустимым экстремальным решением.

a) 12x1+15x2=0; x1=-(5/4)*x2;

b) 12x1+15x2=1; x1=y/12-(5/4)*x2;

c) 12x1+15x2=15; x2=0,5x1=0,625; x2=0; x1=1,25;

d) 12x1+15x2=30; x2=1; x1=1,25; x2=0; x1=2,5;

Решение: точка B x2=8/7; x1=15/7; Y=300/7.

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

2) Альтернативные оптимизационные  решения (множество оптимальных  решений).

Y=4x1+10x2→max

4x1+3x2 ≤12

2x1+5x2 ≤10

x1≥0, x2≥0

Рис. 3

Для данной задачи все точки - их бесконечное множество, лежат на отрезке [А;В] и являются оптимальными. Данное множество бесконечно оптимальных решений.

3) Неограниченные оптимальные  решения.

Y=-2x1+6x2→max

-x1-x2 ≤-2

-x1+x2 ≤1

x1≥0, x2≥0

Рис. 4

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

 

4) Задача не имеет  решений - система ограничений противоречива.

Y=x1+x2→max

-x1+x2 ≤-1

x1-x2 ≤-1

x1≥0, x2≥0

Рис. 5

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

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

При решении задач линейного программирования, если множество решений является не пустым, то оно выпукло и может быть либо ограниченным, либо неограниченным. Если множество решений является не пустым, то оптимальное значение целевой функции может быть либо конечным, либо неограниченно большим. В случае, когда оптимальное значение целевой функции конечно, оно соответствует экстремальной точке.

 

2.2 Табличный симплекс – метод

 

Для его применения необходимо, чтобы знаки в ограничениях были вида

“ меньше либо равно ”, а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему:

1) Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам;

2) Если в исходной системе ограничений присутствовали знаки “ равно ” или “ больше либо равно ”, то в указанные ограничения добавляются искусственные переменные, которые также вводятся и в целевую функцию со знаками, определяемыми типом оптимума;

3) Формируется симплекс-таблица.

4) Рассчитываются симплекс–разности.

5) Принимается решение об окончании либо продолжении счёта.

6) При необходимости выполняются итерации.

7) На каждой итерации определяется  вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

Из задачи, рассмотренной в пункте 2. «Алгоритм решения задач симплексным методом», составляем исходную симплекс-таблицу (таблица 2.2.1). Для этого записываем целевую функцию и ограничения в таблицу следующей структуры:

Таблица 2.2.1. Исходная симплекс-таблица.

Базисные переменные	Свободные члены	Коэффициенты при базисных и небазисных переменных
		x1	x2*	x3	x4	x5	x6	x7
x5*	15	3	5	2	7	1	0	0
x6	9	4	3	3	5	0	1	0
x7	30	5	6	4	8	0	0	1
Y	0	-40	-50	-30	-20	0	0	0

 

После заполнения исходной симплекс-таблицы начинается подготовка к заполнению второй симплекс-таблицы.

Алгоритм:

1) Проверяем базисные решения  на оптимальность. Просматриваем  знаки коэффициентов последней  строки таблицы, исключая коэффициент  при свободном члене. Наличие отрицательных коэффициентов в последней строке говорит о том, что решение не оптимально.

2) Проверяем задачу на наличие  решения. Если над всеми отрицательными  коэффициентами целевой функции  нет ни одного столбца с  неположительными числами, то задача не имеет решения.

3) Выбираем из небазисных переменных  ту, которая способна при введении  её в базис увеличить значение  целевой функции, т.е. переменную, имеющую  наибольший отрицательный коэффициент  в последней строке, и отмечаем её звездочкой «*» - разрешающий столбец.

4) Определяем, какая из базисных  переменных должна быть выведена  из базиса. Для этого определяем  минимальное частное от деления  соответствующих свободных членов  и положительных коэффициентов  столбца, отмеченного звездочкой. Коэффициент, который находится на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом (в таблице его берут в рамку).

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

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

Таблица 2.2.2. Симплекс-таблица для первой итерации.

Базисные переменные	Свободные члены	Коэффициенты при базисных и небазисных переменных
		x1	x2	x3*	x4	x5	x6	x7
x2	3	3/5	1	2/5	1  2/5	-  1/5	0	0
x6*	0	2  1/5	0	1  4/5	4/5	-  3/5	1	0
x7	12	1  2/5	0	1  3/5	-  2/5	-1  1/5	0	1
Y	150	-10	0	-10	50	10	0	0

 

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

Анализируем таблицу 2.2.2. В строке целевой функции есть отрицательные элементы, т.е. решение не является оптимальным, поэтому переходим к следующей симплекс-таблице. Выводим из базиса x6, вводим в базис x1.

 

Таблица 2.2.3. Симплекс-таблица для второй итерации.

Базисные переменные	Свободные члены	Коэффициенты при базисных и небазисных переменных
		x1	x2	x3	x4	x5	x6	x7
x2	3	1/9	1	0	1  2/9	1/3	-  2/9	0
x3	0	1  2/9	0	1	4/9	-  1/3	5/9	0
x7	12	-  5/9	0	0	-1  1/9	-  2/3	-  8/9	1
Y	150	2  2/9	0	0	54  4/9	2  2/9	5  5/9	0

 

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

Можно выписать ответ. Значения базисных переменных и целевой функции выписываются из столбца свободных членов. Все небазисные переменные равны нулю.

Ответ:

X*=(0;3;0;0;0;0;12);

Y = 150.