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

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

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако, еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канторовичем.

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

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

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

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

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

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

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

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

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

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

Математическую модель задачи запишем следующим образом.

Определить план , который удовлетворяет ограничениям

и обеспечивает максимальное значение целевой функции .

Алгоритм симплексного метода включает следующие этапы.

1. Составление начального опорного плана.

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

,

где базисные переменные,

свободные переменные,

Решим эту систему относительно базисных переменных:

,

а функцию цели перепишем в виде уравнения

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

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

Реализация симплексного метода при решении задач линейного программирования осуществляется с помощью симплексных таблиц. В таблице выписаны соответствующие векторы и . Вектор составлен из свободных членов системы основных ограничений. Среди соответствующих векторов есть т векторов, образующих базис. Их записывают в колонку «Б». Как видим, полагая свободные переменные равными нулю, из таблицы можно получить начальный опорный план задачи.

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

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

Оценки векторов используются для проверки оптимальности плана.

 

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

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

 

3. Определение ключевого столбца и строки.

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

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

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

 

4. Построение нового опорного плана.

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

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

,

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

Затем возвращаемся ко второму этапу алгоритма – проверке нового плана на оптимальность.

 

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

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

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

Б
									4: 2 = 2
									8: 4 = 2
				-1					10: 5 = 2

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

		1,5		0,5
			0,25		0,25
		2,4	-0,2	0,2		0,2

Сравниваем последовательно слева направо полученные частные по столбцам. В первом и втором столбце все частные одинаковы, а в третьем столбце наименьшее частное 1,5 в первой строке, следовательно, эта строка и будет ключевой с ключевым элементом 2.

 

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

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

 

Пример.

Предприятие выпускает три вида продукции: А, В, С, используя при этом три вида ресурсов: . Известны удельные расходы ресурсов, их запасы и прибыль, получаемая от реализации единицы продукции. Указанные данные размещены в таблице.

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

Ресурсы	А	В	С	Запас
Прибыль

Решение. Запишем математическую модель задачи.

Определим план , который удовлетворяет условиям

и обеспечивает максимальное значение целевой функции

.

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

Очевидно, что переменные в этой системе являются базисными, а свободными.

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

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

	Б
		-12	-9	-14					-240	-560

 

Начальный опорный план неоптимальный, так как в индексной строке находятся отрицательные коэффициенты: .

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

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

Формируем следующую симплексную таблицу. Вместо вектора в базис войдет вектор . Первая строка в этой таблице получена в результате деления всех элементов первой строки первой симплексной таблицы на ключевой элемент . На месте ключевого элемента во второй таблице получаем 1. В остальных клетках столбца второй таблицы записываем нули. Столбцы и переносятся во вторую симплексную таблицу без изменения, т.к. они остались в базисе.

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

.

Элементы второй строки определяются аналогично:

Аналогично проводятся расчеты по всем строкам таблицы, включая индексную.

	Б
						-1
								-32

Контроль. Из второй симплексной таблицы можно выписать план рассматриваемой задачи и значение целевой функции на нем .

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

На третьей итерации (третья симплексная таблица) получаем план, который является оптимальным, т.к. все коэффициенты в индексной строке .

	Б

Оптимальный план можно записать так: .

Следовательно, предприятие для получения максимальной прибыли в размере 592 денежных единицы должно из имеющихся ресурсов изготовить и реализовать 40 единиц продукции вида А и 8 единиц продукции вида С, а продукцию вида В совсем не производить. При этом ресурсы и будут использованы полностью, а ресурс останется в количестве 12 единиц.

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

Метод искусственного базиса

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

Если же ограничения задачи заданы в виде неравенств вида или уравнений

и (или) ,

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

Рассмотрим примеры постановок задач такого рода.

Преобразование ограничений, заданных в виде уравнений, рассмотрим на примере:

В систему равенств вводим искусственные переменные с коэффициентами, равными единице, позволяющими образовать искусственный базис:

Здесь .

Целевая функция имеет вид:

при решении задачи на максимум –

при решении задачи на минимум –

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

Преобразование ограничений в виде неравенств вида рассмотрим на примере:

Для получения системы уравнений вводим дополнительные переменные .

Поскольку в этой системе уравнений отсутствует базис, то вводим в нее искусственные переменные с коэффициентами, равными + 1, которые образуют искусственный базис

Целевая функция имеет вид:

при решении задачи на максимум –

при решении задачи на минимум –

.

Здесь .

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

 

Пример. Определить минимальное значение целевой функции

при следующих смешанных условиях-ограничениях:

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

Теперь введем искусственные переменные и в первое и второе уравнения:

Целевая функция запишется в виде:

.

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

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

	Б
				М	М
М
М					-1
	11 М			- М
М
										-
								-	-

Оптимальному плану соответствует точка с координатами и , .

Следует заметить, что эту задачу можно решить с помощью графоаналитического метода.