Симплекс-метод поиска и анализа оптимального решения линейных моделей

ЦЕЛЬ РАБОТЫ: развить навыки поиска и анализа оптимальных решений линейных моделей на основе симплексного метода.

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ. При поиске оптимального решения линейных моделей можно ограничиться перебором вершин многогранника допустимых решений, отбросив как заведомо неоптимальные все решения, расположенные внутри многогранника (рис. 2).

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

Кроме того, симплекс-метод позволяет учитывать неограниченное количество управляющих переменных, также как и управляемых. На основе данного метода можно решать n-мерные задачи, тогда как графический метод ограничивается решением 2-х, максимум 3-х мерных задач.

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

Каждая расчетная итерация симплексной процедуры фиксируется в симплексной таблице. Симплекс-таблица представляет собой матрицу, которая служит средством перебора допустимых базисных решений задачи линейного программирования (линейной модели). Симплексная таблица образуется из коэффициентов системы уравнений линейной модели, приведенной к каноническому виду:

z₀= p₁x₂+ p₂x₂à max;

или

y₁= - a₁₁x₁- a₁₁x₂+ a₁ > 0;

y₂= - a₂₁x₁- a₂₂x₂+ a₂ > 0;

y₃= a₃₁x₂+ a₃₂x₂- a₃ > 0;

y₄= a₂₄x₂- a₄ > 0;

z₀= 2x₁+ 3x₂max

y₁= - 2x₁- x₂+ 8 > 0

y₂= - x₁- 3x₂+ 18 > 0

y₃=20x₁+50x₂– 200 > 0

y₄=50x₂– 100 > 0

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

В данном примере приведен общий и конкретный вид линейной оптимизационной модели деятельности туристской фирмы, который в общем виде соответствует заданию, выполняемому в практической работе № 1 и 2. Важно отметить, что в данной задаче использован один критерий оптимальности z₀– прибыль организации. Уравнений типа y_r составлено два (y₁ и y₂ соответственно), так как ограничено два вида ресурсов: объем информации, получаемой по Интернету, и количество поездок в посольства и представительства зарубежных стран. Уравнений типа y_l также составлено два (y₃ и y₄ соответственно), поскольку заданы минимальные размеры выручки организации: по обоим видам оказываемых услуг и в том числе по второму виду отдельно.

МЕТОДИКА РЕШЕНИЯ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ СИМПЛЕКСНЫМ МЕТОДОМ

1. Перебор вершин многогранника возможных решений линейных моделей начинают с точки (1) (рис.2,). Эта точка представляет собой начало декартовой системы координат, в нашем примере - это пересечение осей X₁ (х₂=0) и X₂(х₁ =0). Точке (1), как и каждой последующей - (2), (3), (4), (5) - соответствует симплекс-таблица, в которой содержатся характеристики плана (то есть решения линейной модели), соответствующие этим точкам. Точке (1) соответствует симплекс-табл. 1.

Симплекс-таблица 1

-x₂ =0

	-x₁ =0	-x₂ =0			- x₁ = 0 - [xxxxx₂ = О
y ₁= =	a₁₁	a₁₂	a₁	y₁=	2 1
y ₂ =	ax₂₁	a₂₂	a₂	y ₂ =	1 3
yз =	-a₃₁	-a₃₂	- a₃	y ₃ =	-20 -50	-200
y₄ =	-a₄₁	-a₄₂	- a₄	y ₄= z₀=	0 -50	-100
z ₀ =	- p ₁	- p₂		z₀=	-2 -3
	В общем обобщем бщем	виде			Условный числовой пример примерпример

Следует обратить внимание, что верхние управляющие переменные (их может быть любое количество) в симплекс-таблице всегда равны нулю: для точки (1) x₁ =0, x₂ =0 и имеют знак минус. Значения управляемых переменных всегда равны величинам, расположенным в последнем столбце симплексной таблицы: для точки (l) y₁ = 8, у ₂= 18, у₃= -200, у₄= -100, z₀= 0. Все числовые элементы симплекс- таблиц имеют обратные знаки по сравнению с исходным вариантом, кроме значений последнего столбца, где они приводятся с прямыми (исходными) знаками.

Таким образом, все необходимые характеристики плана, соответствующего точке (1), определяются по симплекс-табл. 1.

2. Анализируя план в точке (1), можно сделать вывод, что он не является оптимальным и его можно улучшить. Недостатком плана является отрицательность переменных уз<0, у₄<0. Экономический смысл данного обстоятельства - это невыполнение плана по заданным экономическим показателям. Следовательно, план в точке (1) необходимо улучшить.

3. Изменять план в нашем примере можно лишь, двигаясь по одной
из координатных осей X₁или X₂, выходящих из точки (1) (рис.2,д), то есть за
счет увеличения объема выполняемых услуг 1-го или 2-го
вида. Необходимо выбрать такое направление, при котором будут
увеличиваться у₃ и (или) у₄.

Рис. 2. Геометрическая иллюстрация и характеристики точек (планов) симшекс-процедуры: а - точка (1); б - точка (2); в - точка (3); г - точка (4); д - точка (5).

Улучшить план - это значит изменить в нужном направлении (увеличить или уменьшить) управляемые переменные за счет увеличения управляющих переменных. Уменьшать управляющие переменные нельзя!

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

При этом руководствуются правилом:

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

Анализ знаков коэффициентов симплекс-табл. 1 показывает, что увеличить у₃ или у₄ можно и за счет увеличения управляющей переменной х₁ или х₂. Выберем переменную x₂ и начнем ее увеличивать, то есть двигаться по координатной оси X₂ (x₁=0) (рис.2,а). В нашем примере первой встретится плоскость Y ₄=0. Эта плоскость станет новой координатной осью вместо X₁(x ₂=0) Так определится новое начало декартовой системы координат - точка (2) (рис.2, б).

4. Для точки (2) необходимо построить новую симплекс-таблицу Коэффициенты этой новой таблицы определяются на основе коэффициентов симплекс-табл. 1. Коэффициент симплекс-табл. 1, связывающий управляемую переменную у₄ с управляющей переменной х₂, называется разрешающим элементом. Обозначим его β₄₂=50. Разрешающий элемент находится в разрешающей строке и разрешающем столбце симплекс-табл. 1.

Коэффициенты каждой последующей симплекс-таблицы определяются на основе данных предыдущей симплекс-таблицы определяются на основе данных предыдущей симплекс-таблицы по следующим четырем правилам:

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

В нашем примере

2-е правило – получение новых коэффициентов в разрешающей строке:

В нашем примере

3-е правило – получение новых коэффициентов в разрешающем столбце:

В нашем примере

4-е правило – получение всех остальных коэффициентов новой симплекс-таблицы:

В нашем примере и так далее.

На основе полученных данных строится симплекс-табл.2.

Симплекс-таблица 2

- x _\= 0 - y ₄ = 0

y₁ =		1/80
yг =		3/50
y₃ =	-20	-1	-100
х_г =		-1/50
Zo =	-2	-3/50

Анализ симплекс-табл.2 осуществляется в соответствии с изложенной выше методикой. В нашем примере данный вариант плана не является оптимальным из-за сохраняющейся отрицательности показателей норм прибыли, а также по результирующим экономическим показателям z₀, у₃. Для улучшения этого варианта плана можно увеличивать одну из переменных х₁ или у₄. Выберем переменную x₁ и будем двигаться по оси Y₄=0 до пересечения с плоскостью Y₃= 0, при этом получим точку (3). Этой точке соответствует симплекс-табл.3.

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

Симплекс-таблица 3

	- у ₃ = 0	- у ₄ = 0
y₁ =	1/10	-2/25	-4
y₂ =	1/20	1/100
x₁ =	-1/20	1/20
x₂=		-1/50
z ₀ =	-1/10	1/25

Анализ симплекс-табл.З показывает,; что план в точке (3) допускает перерасход первого вида ресурсов у₁ < 0, что невозможно по условиям заданной модели (рис.2,в). В целях дальнейшей оптимизации из двух управляющих переменных y₃ и у₄ выберем опять y₄. Будем двигаться по оси Y₄=0 (увеличивая переменную x₁) дальше до пересечения с прямой Y₂=0. Расчет коэффициентов симплекс-табл.4 осуществляется по тем же правилам на основе коэффициентов предыдущей симплекс-табл.З. Следующей точкой поиска оптимального варианта плана будет точка (4) (рис.2,г). При этом следует обратить внимание на изменение направления осей. Это вызвано ограничениями, заданными на расход имеющихся ресурсов. Точке (4) соответствует симплекс-табл.4.

Симплекс-таблица 4.

	- y₂ =0	-y₄= 0
y₁ =	-5/4	-25/2
y₃ =	1/16	-1/8	81/8
x₁=	1/80	5/8	5/2
х_г =		1/4	5/2
Z₀=	-1/5	1/2

Анализ симплекс-табл.4 показывает, что данный вариант плана также может быть улучшен из-за сохраняющейся отрицательности одного коэффициента последней строки, то есть нормы прибыли на одном виде услуг. Улучшить план возможно, изменив управляющие переменные у₂ или y₄. Выберем у₂ и будем двигаться по соответствующей оси до пересечения с плоскостью Y ₁=0. Таким образом получим точку (5) как новый альтернативный вариант плана. Этой точке соответствует симплекс-табл.5 (рис.2,д), коэффициенты которой определены на основе коэффициентов симплекс-табл.4. Анализ нового плана показывает, что его улучшить нельзя, так как в последней строке таблицы все коэффициенты положительны. Это означает, что по какой бы оси ни стали двигаться из этой точки, показатель прибыли будет уменьшаться. Следовательно, план в точке (5) оптимален.

Симплекс-таблица 5

- у₂ = 0 - y₁ =0

y₄ =	,20	-15	505/2
yз =		-2
x₁ =	-1/5	13/20	19/40
х₂ =		;1/4	5/2
z₀ =	16/5	1/10	232/5

Управляющие переменные:

Управляемые переменные:

ЗАДАНИЕ К ПРАКТИЧЕСКОЙ РАБОТЕ

На основе методики симплексного метода найти оптимальное решение модели, построенной в практической работе №1, сравнить его с результатами, полученными при решении модели графическим способом. Сделать выводы относительно простоты того и другого метода, а также точности получаемых результатов.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Приведите пример канонической формы линейных моделей.

2. Сформулируйте сущность симплекс-метода поиска и анализа оптимальных решений линейных моделей.

3.Что такое симплексная таблица?

4.Почему нельзя уменьшать управляющие переменные?

5.Как влияет знак коэффициента связи в симплекс-таблице на изменение управляемой переменной, если:

а) управляющая переменная уменьшается, а знак коэффициента

положителен;

б) управляющая переменная уменьшается, а знак коэффициента

отрицателен;

в) управляющая переменная увеличивается, а знак коэффициента

положителен;