5.Симплексный метод (решение задачи оптимального распределения ресурсов)

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

Рассмотрим основные характеристики, учитываемые при использовании симплексной процедуры вычисления, а именно:

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

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

3.Свойства сходимости. Всегда ли вычислительная процедура, определяемая алгоритмом, обеспечивает сходимость? Если сходимость имеет место, всегда ли она приводит к правильному решению? Исчерпывается ли данная процедура конечным числом итераций? Сколько итераций необходимо выполнить при решении практической задачи, чтобы получить требуемый результат? Является ли сходимость равномерной?

4. Требования к вычислительным процедурам. Насколько сложными и трудоемкими оказываются вычисления? При какой точности вычислений рассматриваемый метод приводит к удовлетворительным результатам?

Симплексный алгоритм

Опишем ход рассуждения симплексного алгоритма в словесной форме.

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

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

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

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

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

Решение задачи распределения ресурсов симплексным методом

максимизировать 4x1 +5x2 + 9x3 + 11x4

при ограничениях

1x1 + 1x2 +1x3 + 1x4 <=15,

7x1 + 5x2 + 3x3 + 2x4 <=120,

3x1 + 5x2 + 10x3 + 15 x4 <=100,

x1>=0, x2>=0, x3>=0, x4>=0.

Обозначим через x0 значение целевой функции и введем в рассмотрение свободные переменные. Получим следующую систему уравнений:

1x0 - 4x1 - 5x2 - 9x3 - 11x4 =0,

1x1 + 1x2 + 1x3 + 1x4 + 1x5 =15,

7x1 + 5x2 + 3x3 + 2x4 +1x6 =120, (1)

3x1 + 5x2 + 10x3 + 15 x4 + 1x7 =100,

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

Задача шага 1 заключается в том, чтобы выбрать первоначальное допустимое решения системы уравнений. Удобнее всего начать с x0=0, x5=15, x6=120, x7=100 при нулевых значениях остальных переменных. Переменные x0, x5, x6, x7

являются базисными переменными или базисом. Остальные переменные называются небазисными переменными.

Интерпритация коэффициентов в нулевой строке.

Каждый коэффициент в строке 0 определяет положительное (если перед ним стоит знак минус) или отрицательное (если перед ним стоит знак плюс) приращение x0 при увеличении на единицу соответствующей небазисной переменной.

Шаг 2 симплексного метода устанавливает следующее легко реализуемое правило, позволяющее определить, какие переменные должны войти в очередной базис.

Симплекс критерий I( максимизация).

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

В соответствии с критерием Iв базис следует ввести переменную x4. Каждое единичное приращение x4 приводит к увеличению значения x0 на 11.

Симплекс критерий II

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

б) Выберем отношение с наименьшим значением - в очередном пробном решении xj приравнивается именно к этому значению

Результаты решения задачи сведем в таблицу:

Базис-ные перемен-ные	Рассматри-ваемое пробное решение	Коэффи-циенты при x4	Значения отношений	Минималь-ное значение	Следующее пробное решение
x x x x	0 15 120 100	-11 1 2 15	- 15 60 6.66	6.66	x4=6.66, x7=0.

Шаг 4 На данном этапе производят процедуру замены базиса.

Система 1 записывается таким образом, чтобы в строке 3 коэффициент при x4 был равен 1, а в строке 0,1,2- нулю.

Для этого разделим обе части уравнения в строке 3 на коэффициент при x4, т.е.на 15:

1x0 - 4x1 - 5x2 - 9x3 - 11x4 =0, (строка0)

1x1 + 1x2 + 1x3 + 1x4 + 1x5 =15, (строка 1)

7x1 + 5x2 + 3x3 + 2x4 +1x6 =120, (строка2)

1/5x1 + 1/3x2 + 2/3x3 + 1 x4 + 1/15x7 =20/3, (строка3)

Обратим в нули коэффициенты при x4 в строках 0,1 и 2, действуя по схеме:

1. умножить строку 3 на 11 и результат прибавить к строке 0;

2. умножить строку 3 на -1 и результат прибавить к строке 1;

3. умножить строку 3 на -2 и результат прибавить к строке 2.

Выполнив указанные действия, получим

1x0 - 9/5x1 - 4/3x2 - 5/3x3 + 11/15 x7 =220/3,

4/5x1 + 2/3x2 + 1/3x3 +1x5 1/15 x7 = 25/3,

33/5x1 + 13/3x2 + 5/3x3 + 1x6 - 2/15x7 =320/3,

1/5x1 + 1/3x2 + 2/3x3 + 1x4 + 1/15x7 =20/3.

Таким образом , вторым пробным базисным решением являются значения:

x0	x5	x6	x4
220/3	25/3	320/3	20/3

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

Согласно критерию I, возможно улучшить решение, введя в базис переменную x1, обеспечивающую наибольшее удельное приращение целевой функции. Сделав выбор, следует перейти к вычислениям предусмотренным шагом 3, используя критерий II (таблица 3).

Базис-ные перемен-ные	Рассматри-ваемое пробное решение	Коэффи-циенты при x1	Значения отношений	Минималь-ное значение	Следующее пробное решение
x0 x5 x6 x4	220/3 25/3 320/3 20/3	9/5 4/5 33/5 1/5	- 125/12 1600/99 100/3	125/12	x1=125/12, x5=0.

Произведем процедуру, позволяющую поменять пробный базис.

Выполним нормировку коэффициента при x1 в строке 1:

1x0 - 9/5x1 - 4/3x2 - 5/3x3 + 11/15 x7 =220/7,

1x1 + 5/6x2 + 5/12x3 +5/4x5 - 1/12 x7 = 125/12,

33/5x1 + 13/3x2 + 5/3x3 + 1x6 - 2/15x7 =320/3,

1/5x1 + 1/3x2 + 2/3x3 + 1x4 + 1/15x7 =3/20.

Исключим x1 из уравнений в строках 0,1 и 3, действуя по схеме:

1.умножить строку 1 на 9/5 и результат сложить со строкой 0;

2.умножить строку 1 на -33/5 и результат сложить со строкой 2;

3.умножить строку 1 на -1/5 и результат сложить со строкой 3.

В результате получим:

1x0 +1/6x2 - 11/ 12x3 + 9/4x5 +7/12 x7 =1105/12,

1x1 + 5/6x2 + 5/12x3 +5/4x5 -1/12 x7 = 125/12,

-7/6x2 - 13/12x3 - 33/4x5+ 1x6 + 5/12x7 =455/12,

1/6x2 +7/12x3 +1x4 - 1/4x5 + 1/12x7 =55/12.

Третье пробное базисное решение можно представить в виде таблицы:

x0	x1	x6	x4
1105/12	125/12	455/12	55/12

Итерация 3 Завершив вторую симплекс- итерацию, снова возвра-щаемся к Шагу 2, с целью проверки решения на оптимальным.

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

Базис-ные перемен-ные	Рассматри-ваемое пробное решение	Коэффи-циенты при x1	Значения отношений	Минималь-ное значение	Следующее пробное решение
x0 x1 x6 x4	1105/12 125/12 455/12 55/12	-11/12 5/12 -13/12 7/12	- 25 - 55/7	55/7	x3=, 55/7, x4=0.

Пронормируем коэффициент при x3 в строке3 путем деления обеих частей соответствующего уравнения на 7/12. Система уравнений примет вид:

1x0 + 1/6x2 - 11/12x3 + 9/4x5 + 7/12 x7 = 1105/12,

x1 + 5/6x2+ 5/12x3 +5/4x5 - 1/12 x7 = 125/12,

-7/6x2 - 13/12x3 - 33/4x5 + 1x6 - 5/12x7 = 455/12,

2/7x2 + 1x3 + 12/7x4 - 3/7x5 + 1/7x7 = 55/7.

Исключим x3 из уравнений в строках 0,1 и 2, действуя по схеме:

1.умножить строку 3 на 11/12 и результат сложить со строкой 0;

2.умножить строку 3 на -5/12 и результат сложить со строкой 1;

3.умножить строку 3 на 13/12 и результат сложить со строкой 2.

В результате получим:

1x0 +3/7x2 +11/ 7x4+ 13/7x5 +5/7 x7 =695/7,

1x1 + 5/7x2 - 5/7x4 + 10/7x5 -1/7 x7 = 50/7,

-6/7x2 - 13/7x4 - 61/7x5+ 1x6 + 4/7x7 =325/7,

2/7x2 + 1x3 + 12/7x4 - 3/7x5 + 1/7x7 =55/7.

Четвертое пробное базисное решение можно представить в виде таблицы со значениями:

x0	x1	x6	x3
695/7	50/7	325/7	55/7

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

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

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