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

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

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

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

1) Некоторые задачи линейного программирования (финансовые средства, запасы сырья, производственные мощности) можно регулировать. Анализ чувствительности позволяет оценить влияние изменений этих параметров на оптимальное решение. Если обнаруживается, что оптимальное решение (в большинстве задач это прибыль/затраты) может значительно улучшиться за счёт небольших изменений заданных параметров, то целесообразно произвести эти изменения.

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

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

б) к каким последствиям приведёт сокращение объёмов ресурсов.

в) что произойдёт, если ввести в рассмотрение новую управляемую переменную.

 

2.1 Графический метод

Алгоритм графического метода решения задач линейного  программирования состоит из следующих пунктов:

1)  Построить область допустимых решений.

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

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

 

4) Линию уровня переместить до опорной прямой в задаче на max в направлении нормали, в задаче на min в противоположном направлении.

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

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

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

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

Рис. 1

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

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

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

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

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

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

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

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

Y=12x₁+15x₂→max

4x₁+3x₂ ≤12

2x₁+5x₂ ≤10

x₁≥0, x₂≥0

 

Рис. 2

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

a) 12x₁+15x₂=0; x₁=-(5/4)*x₂;

b) 12x₁+15x₂=1; x₁=y/12-(5/4)*x₂;

c) 12x₁+15x₂=15; x₂=0,5x₁=0,625; x₂=0; x₁=1,25;

d) 12x₁+15x₂=30; x₂=1; x₁=1,25; x₂=0; x₁=2,5;

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

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

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

Y=4x₁+10x₂→max

4x₁+3x₂ ≤12

2x₁+5x₂ ≤10

x₁≥0, x₂≥0

Рис. 3

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

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

Y=-2x₁+6x₂→max

-x₁-x₂ ≤-2

-x₁+x₂ ≤1

x₁≥0, x₂≥0

Рис. 4

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

 

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

Y=x₁+x₂→max

-x₁+x₂ ≤-1

x₁-x₂ ≤-1

x₁≥0, x₂≥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