Общая идея симплексного метода

 

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

.

Для примера: m=5, n=7. Количество крайних точек: 21. каждую из них необходимо найти, посчитать значение целевой функции. Потом все их сравнить.

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

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

Алгоритм решения ЗЛП симплексным методом:

1. Найти начальное опорное решение ЗЛП.

2. Проверить, не является ли оно оптимальным.

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

4. Перейти к пункту 2.

Исходя из алгоритма решения выделим что необходимо знать и уметь при решении задач симплексным методом:

1) уметь строить начальный опорный план ЗЛП;

2) знать признак оптимальности опорного плана;

3) уметь переходить к нехудшему опорному плану.

 

2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом

 

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

Случай 1:

Пусть система ограничений представлена в каноническом виде:

().

Определение 1: Говорят, что ограничение в ЗЛП имеет предпочтительный вид, если при неотицательной правой части () левая часть уравнения содержит переменную с коэффициентом 1, которая в другие уравнения системы входит с коэффициентом, равным 0.

Пример 1:

В данном примере первое и второе уравнения имеют предпочтительный вид, так как в первом есть переменная , коэффициент у которой 1, а в остальные уравнения данная переменная не входит; во втором такая переменная - .

Определение 2: Переменная, входящая в одно из уравнений системы с коэффициентом, равным 1, а в остальные с коэффициентом, равным 0, называется предпочтительно переменной.

В примере 1 в первом уравнении предпочтительная переменная – , во втором –. В третьем уравнении предпочтительных переменных нет.

Определение 3: Говорят, что система уравнений имеет предпочтительный вид, если каждое уравнение системы имеет предпочтительный вид.

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

Пример 2:

Система имеет предпочтительный вид. Предпочтительные переменные (соответственно уравнениям) , и . Следовательно, решение ЗЛП имеет вид: (13, 0, 56, 0, 4).

Случай 2.

Пусть система ограничений ЗЛП представлена в виде:

(),

()

().

Приведем систему к каноническому виду. Для этого прибавим к левым частям неравенств новые неотрицательные переменные.

(),

()

().

Переменные () являются предпочтительными. Случай 2 свелся к случаю 1.

Случай 3.

Пусть система ограничений ЗЛП представлена в виде:

(),

()

().

Система представлена в каноническом виде. однако, в отличие от случая 1, среди уравнений системы нет таких, которые представлены в предпочтительном виде. В этом случае говорят, что есть необходимость решать М-задачу. Для того, чтобы построить М-задачу необходимо прибавить к каждому уравнению системы ограничений дополнительные переменные. Будем их обозначать . будем называть искусственным базисом. Все переменные искусственного базиса – неотрицательны. В целевую функцию они входят с коэффициентом М (бесконечно большое положительное число). Знак коэффициента определяется в зависимости от того, какая ЗЛП решается. Если ЗЛП на максимум, то коэффициент (–М). В противном случае – (+М). Таким образом ЗЛП имеет вид:

при

(),

()

()

().

Переменные () являются предпочтительными. Случай 3 свелся к случаю 1.

Теорема 1: Если в оптимальном плане М-задачи все искусственные переменные будут равны 0, то план является оптимальным для исходной задачи.

Теорема 2: Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных не равна 0, то исходная задача не имеет допустимых планов, т.е. ее условия несовместны.

 

Случай 4.

Пусть система ограничений ЗЛП представлена в виде:

(),

()

().

Приведем систему к каноническому виду. Для этого вычтем из левых частей неравенств новые неотрицательные переменные.

(),

()

().

Переменные () не являются предпочтительными. Случай 4 свелся к случаю 3.

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

Пример 3: Составить начальный опорный план при решении ЗЛП:

при

Решение.

Первое уравнение системы имеет предпочтительный вид (случай 1). Предпочтительная переменная . Второе уравнение не содержит предпочтительной переменной (случай 2). Необходимо добавить одну переменную искусственного базиса . Получим уравнение:

.

В целевую функцию новая переменная войдет с коэффициентом, равным –М.

Третье ограничение имеет вид неравенства ≤ (случай 2). Необходимо добавить дополнительную переменную . Она и будет иметь предпочтительный вид. В целевую функцию она войдет с коэффициентом 0.). Следовательно, вычтем из левой части неравенства и добавим вторую переменную искусственного базиса . Соответственно, в целевую функцию добавятся две новые переменные с коэффициентами 0 и –М соответственно.

Таким образом, ЗЛП будет иметь следующий вид:

при

Базис системы составляют переменные: , , , (представлены в соответствии с уравнениями, предпочтительными переменными которых являются данные переменные). Следовательно, начальный опорный план ЗЛП имеет вид: (0, 23, 0, 0, 0, 34, 0, 17, 6).

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

 

2.6. Признак оптимальности опорного плана. Симплексные таблицы

 

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

Пусть ЗЛП представлена в каноническом виде:

при

С помощью метода Гаусса (см. 1.12) преобразуем систему ограничений и приведем ее к следующему виду:

при

(i= )

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

Составим симплексную таблицу:

БП	СБ	А			…			…		…
		…			…		…
					…			…		…
					…			…		…
…	…	…	…	…	…	…	…	…	…	…	…
					…			…		…
…	…	…	…	…	…	…	…	…	…	…	…
					…			…		…
				…			…		…

В первом столбце (БП) пишутся базисные переменные. Все базисные переменные пишутся В СООТВЕТСТВИИ С УРАВНЕНИЯМИ, ДЛЯ КОТОРЫХ ДАННЫЕ ПЕРЕМЕННЫЕ ЯВЛЯЮТСЯ ПРЕДПОЧТИТЕЛЬНЫМИ.

Во втором столбце (СБ) пишутся коэффициенты для соответственных базисных переменных в целевой функции.

В третьем столбце (А) пишутся свободные члены в уравнениях системы ограничений.

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

В таблице со второй строки четвертого столбца пишутся все коэффициенты соответственных переменных в системе ограничений.

В последней строке пишутся оценки. Оценки считаются по формулам (см. 1.12):

…………………………………….

Оценки для базисных переменных равны 0.

Замечание: Оценки считаются как скалярное произведение соответственного столбца на столбец СБ минус коэффициент в целевой функции для данной переменной.

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

Теорема 1: (признак оптимальности опорного плана при решении задач на максимум) Пусть исходная ЗЛП решается на максимум. Если для некоторого опорного плана в индексной строке симплексной таблицы все оценки () неотрицательны, то такой план будет оптимальным.

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

Пример 1: Составить симплексную таблицу и посчитать оценки для задачи линейного программирования вида:

при

Решение.

Построение начального опорного плана рассмотрено в 2.5.

при

Базис системы составляют переменные: , , , (представлены в соответствии с уравнениями, предпочтительными переменными которых являются данные переменные).

БП	СБ	А
-12				-1			–M	–M
			-1
	–M					-1
			-4		-1
	–M								-1
св. чл		-20
M	-23	-14		-5		-1

=23∙32-17 M+0∙34-6∙M=-23∙M+736;

=-1∙32-13∙M-0∙4-1∙M+12=-14∙M-20;

=32∙1-0∙M+0∙0-0∙M-32=0∙M+0=0 (базисная переменная);

=32∙14-4∙M-0∙1-1∙M-0=-5∙M+448;

=32∙0+1∙M+0∙0-0∙M-0=1∙M+0;

=32∙0-0∙M+0∙12-1∙M+1=-1∙M+1;

=32∙0-0∙M+0∙1-0∙M-0=0∙M+0=0 (базисная переменная);

=32∙0-0∙M+0∙0+1∙M-0=1∙M+0=0;

=32∙0-1∙M+0∙0-0∙M+M=0∙M+0=0 (базисная переменная);

=32∙0-0∙M+0∙0-1∙M+M=0∙M+0=0 (базисная переменная);

Для данного начального опорного плана ответ: Z=-23∙M+736 при (0, 23, 0, 0, 0, 34, 0, 17, 6).

Замечание: Значение Z взято из индексной строки симплексной таблицы (пересечение индексной строки и столбика А). Значение базисных переменных из столбика А.

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

 

2.7. Переход к нехудшему опорному плану.

 

Пусть решается ЗЛП с системой ограничений в предпочтительном виде:

(i= )

Начальный опорный план для такой задачи: . Значение целевой функции: Z= .

Пусть исходная задача решается на максимум (для ЗЛП на минимум все рассуждения аналогичны). Если все оценки () неотрицательны, то план оптимален и задача решена. Предположим, что среди оценок свободных членов есть по крайней мере одна отрицательная. Обозначим ее . Назовем соответственный вектор столбец - разрешающим, а соответственную переменную - перспективной.

Попытаемся заменить некоторую базисную переменную на . При этом все остальные свободные переменные не должны измениться.

Рассмотрим систему ограничений ЗЛП:

(i= )

Преобразуем ее следующим образом:

(i= )

Так как все свободные переменные кроме равны 0, получим:

(i= ) (1).

Отсюда:

(i= ).

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

(i= ).

Отсюда:

(i= ).

Так как базисных переменных не может быть больше m, то при внесении в базис какая-то из базисных переменных будет свободной. Пусть это переменная . Тогда:

→

По условию задачи все - неотрицательны. Тогда и должно быть положительным.

Таким образом, базисный элемент и соответственную строку k следует искать среди строк, которых положительны.

Не ограничивая общности, предположим, что первые s строк имеют >0. Найдем отношение для всех этих строк. Получим последовательность чисел . Среди чисел этой последовательности выберем минимальное:

min = =Θ.

Назовем это отношение наименьшим симплексным отношением. Соответствующий элемент – разрешающим и соответственную строку k – разрешающей. Базисная переменная будет считаться неперспективной.

Вернемся к равенству (1).

(i= ) (1).

Для i=k получим:

.

Отсюда:

= Θ

Тогда:

(i= ).

Новый базис будет состоять из переменных , , …, , , , …, . Соответствующий ему опорный план имеет вид:

Проверим, является ли полученный опорный план "нехудшим". Для этого найдем для нового опорного плана:

,

где – значение целевой функции первоначального опорного плана, - оценка, соответствующая столбцу . Так как <0, а Θ>0, то полученное значение целевой функции >

Алгоритм выбора разрешающего элемента для задач линейного программирования на максимум (минимум) представлен на Рис. 12.

 

2.8. Симплексные преобразования

 

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

Рассмотрим систему ограничений ЗЛП:

(i= )

Рис. 12. Алгоритм выбора разрешающего элемента для задач линейного программирования на максимум (минимум)

Преобразуем ее следующим образом:

(i= )

Выразим из системы базисную переменную :

.

Распишем подробнее:

Отсюда:

Тогда

Подставим данное равенство в другие ограничения системы:

 

Для целевой функции формула представима в виде:

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

Способ 1.

1. Найти разрешающий элемент.

2. С помощью представленных формул преобразовать все уравнения системы ограничений.

3. Посчитать значение целевой функции.

Способ 2.

Алгоритм действий представлен на Рис. 13.

Определение: Шаг симплексного метода, позволяющего перейти от одного опорного плана к другому, называется итерацией.

Пример: Решить симплексным методом ЗЛП:

при

Рис. 13. Алгоритм решения задач линейного программирования на максимум (минимум), используя симплексные преобразования

Решение.

Система ограничений имеет предпочтительный вид. Можно составлять симплексную таблицу:

БП	СБ	А						№ итерации
	-5		-1
	-5		1 \				-1
			5 \
	-1		-5
		-4				-1
							-1
				-5			8 \
	-1						-1
						-5
	-1

В индексной строке последней симплексной таблицы все оценки свободных переменных положительны. Следовательно, план оптимален.

Ответ: Z=72 в (7, 0, 0, 42, 2).

 

2.9. Альтернативный оптимум (признак бесконечности множества опорных планов)

 

Из геометрической иллюстрации ЗЛП следует, что она имеет бесконечно много решений, если линия уравнения проходит через сторону прямоугольника (Рис. 14).

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

 

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

Следствие: Если в индексной строке симплексной таблицы, содержащей оптимальный план, все оценки соответствующие свободным переменным положительны, то найденное решение - единственное.