Алгоритм симплексного метода

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

Алгоритм симплексного метода.

1) Математическая модель задачи должна быть канонической. Если она не каноническая. То ее надо привести к каноническому виду.

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

 

ni	Aj	n1	n2	…	nm	nm+1	…	nn	L(x)
		x1	x2		xm	xm+1		xn	bi
n1	x1	1	0		0	h1,m+1		h1,n	f1
n2	x2	0	1		0	h2,m+1		h2,n	f2
…	…	…	…	…	…	…	…	…	…
nm	xm	0	0		1	hm,m+1		hm,n	f3
		0	0	…	0		10

 

Индексная строка для переменных находится по формуле

 и по формуле

 для свободного члена.

Возможны следующие случаи при решении задачи на максимум:

- если все оценки  то найденное решение оптимальное;

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

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

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

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

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

3) Заполняем симплексную таблицу 2-го шага:

- переписываем ключевую строчку, разделив ее на ключевой элемент;

- заполняем базисные столбцы;

- остальные коэффициенты таблицы находим по правилу «прямоугольника».

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

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

,

где , ,  – элементы первого шага.

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

 

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

Расход ресурсов за один месяц и общий ресурс при каждом способе производства даны в таблице:

Производственные ресурсы	Расход ресурсов за 1 месяц при работе		Общий ресурс
	1-ым сп.	2-ым сп.
сырье	1	2	4
оборудование	1	1	3
электроэнергия	2	1	8

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

Решение.

Составим математическую модель:  – время работы предприятия 1-ым способом;  – время работы предприятия 2-ым способом.

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

Приведем задачу к каноническому виду:

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

Составляем симплексную таблицу 1-го шага.

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

Ключевым моментом является 2.

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

Вводим в столбец базисной переменной . Составляем симплексную таблицу 2-го шага.

 

ni	Aj	3	4	0	0	0	L (x)
		X1	X2	X3	X4	X5	bi
4	X2	½	1	½	0	0	2
0	X4	½	0	-1/2	1	0	1
0	X5	3/2	0	-1/2	1	1	6
		-1	0	2	0	0	8

 

Получим  В индексной строке имеется одна отрицательная оценка. Полученное решение можно улучшить. Ключевым элементом является ½. Составляем симплексную таблицу 3-го шага.

 

ni	Aj	3	4	0	0	0	L (x)
		X1	X2	X3	X4	X5	bi
4	X2	0	1	1	-1	0	2
3	X1	1	0	-1	2	0	1
0	X5	0	0	1	-3	1	6
		0	0	1	2	0	10

Все оценки свободных переменных  следовательно, найденное опорное решение является оптимальным:

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

Транспортная  задача

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

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

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

Если , то задача называется закрытой (ЗТЗ).

Если , то задача называется открытой (ОТЗ).

Обозначим через  количество груза, перевозимого из пункта  в пункт .

Рассмотрим ЗТЗ. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения.

 

 

			…
			…
			…
...	…	…	…	…
			…

Математическая модель закрытой транспортной задачи имеет вид:

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

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

Для решения транспортной задачи разработан специальный метод, имеющий этапы:

-  нахождение исходного опорного решения;

-  проверка этого решения на оптимальность;

-  переход от одного опорного решения к другому.

Нахождение  исходного  опорного  решения

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

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

В этом случае недостающие их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми.

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

Пример 3. На складах , ,  имеются запасы продукции в количествах 90; 400; 110 т соответственно. Потребители , ,  должны получить эту продукцию в количествах 140; 300; 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (усл. ед.)

 

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

т,

т,

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

 

			5

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

Стоимость перевозки при исходном опорном решении составляет:

 усл. ед.

Метод  потенциалов

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

Числа  и  называют потенциальными.В распределительную таблицу добавляют строчку  и столбец . Потенциалы  и  находят из равенства + = , справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например , тогда остальные потенциалы определяются однозначно. Так, если известен потенциал , то ; если известен потенциал , то . Обозначим . Эту оценку называют оценкой свободных клеток. Если , то опорное решение является оптимальным. Если хотя бы одна из оценок , то опорное решение не является оптимальным и его можно опорного решения к другому.

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

 

				5   100

.

Для занятых клеток составляем систему уравнений:

.

Отсюда , , , , .

Найденные значения потенциалов заносим в таблицу. Вычислим оценки свободных клеток:

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

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

Для свободной клетки с  строится цикл, все вершины которого кроме одной находится в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла становится (+), затем поочередно проставляют знаком (–) и (+). У вершин со знаком (–) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+) и отнимают от грузов у вершин со знаком (–). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение.

		–	–	+
		–
			–	–

 

 

Новое опорное решение

		–	–	+
		+		–
			–	8 –

 

Произведем перераспределение грузов. Получим новое решение. Проверим его на оптимальность.

 

		–	–
				5 70
			–	8 –

 

 

 

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

Стоимость транспортных расходов равна:  усл. ед.

По сравнению с исходными опорным решением транспортные расходы уменьшились на  усл. ед.

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

В целевой функции фиктивный поставщик или потребитель не учитывается.