С искусственным базисом М-методом

Date: 2015-10-07; view: 502.

Решение задачи линейного программирования

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

В уравнения, не содержащие базисной переменной, добавляют со знаком «+» неотрицательные переменные , называемые искусственными. Они образуют искусственный базис; чтобы отличать их от прочих переменных, сверху ставят значок « ». Из целевой функции вычитают сумму искусственных переменных, умноженных на сколь угодно большое положительное число М, т.е. рассматривают Такая задача носит название М-задачи.

Справедлива следующая теорема.

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

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

3. если М-задача не имеет решения, то и исходная задача решения не имеет.

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

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

Пример 3. Составить математическую модель и найти решение следующей задачи.

Отдел технического контроля производит закупку нового оборудования — приборов трех типов, предполагая разместить их на площади 24 м². Каждый прибор первого типа занимает 2м², приборы второго и третьего типов — 1 и 3 м² соответственно. Эксплуатационные расходы составляют по 1 ден.ед. для оборудования первого и третьего типов, 4 ден.ед.— для второго типа. За смену приборы каждого типа способны проверить 2, 1 и 3 партии деталей соответственно.

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

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

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

Запишем неравенства системы ограничений в виде уравнений. Правые части неравенств неотрицательны, в левые части введем дополнительные неотрицательные переменные: со знаком «+» в неравенства типа « » и со знаком «–» в неравенство типа « ».

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

В первом уравнении базисной переменной является , во втором — переменная , а в третьем уравнении базисная переменная отсутствует ( входит со знаком «–»). Поэтому в третье уравнение вводим искусственную переменную, которая и будет являться базисной.

Решаем М-задачу:

^.

.

Внесем данные в симплекс-таблицу (табл.5). Базисными являются переменные , , .

Слева и сверху таблицы выпишем коэффициенты при переменных целевой функции. Для целевой функции отведем две строки таблицы: в первую строку запишем слагаемые без множителя М, во вторую строку будем записывать слагаемые с М, который вынесем в качестве общего множителя строки. Вычислим элементы индексной строки по формулам (4.2): d₀= . В первую строку записываем 0, во вторую — (–6). Далее: d₁= . Первое слагаемое вносим в первую, второе — во вторую индексную строку. Остальные элементы индексной строки вычисляются аналогично:

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

Таблица 5.

									‑M
	Баз.	св.
-М			1					-1
			-1	-1	-4
	M	-6	-1	-1
				-1
	х1							-1
					-4			-1
	M
				10/3			‑1/3	1/3
	x3			‑1/3			1/3	2/3
								-1
				‑4/3			4/3	5/3
	х2					2/10	‑1/10	1/10
	x3
						4/10	6/5	9/5

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

План оптимален, . Отбрасывая дополнительные переменные, получим окончательный ответ: X^*=(3;3;5) и .

Пример 4.Cоставить математическую модель и найти решение задачи.

При кормлении животных используются три вида корма А, В и С, в каждом из которых содержатся питательные вещества в количестве 2, 6, 7 г/кг и в количестве 2, 4, 5 г/кг соответственно. Стоимость 1 кг кормов А, В и С составляет 1, 3 и 2 ден.ед. Составить суточный рацион кормления животных, при котором расходы будут минимальны, если ежедневно они должны потреблять 10 кг пищи, получая при этом не менее 28 г питательного вещества и не более 36 г вещества .

Составим математическую модель задачи. Обозначим количество кормов вида А, В и С неизвестными (кг). Тогда математически условие задачи можно записать в виде:

Это общая форма задачи ЛП, запишем ее в виде основной формы. Правые части неравенств и уравнения в системе ограничений неотрицательны, в левые части неравенств введем дополнительные неотрицательные переменные: со знаком «+» в неравенство типа « » и со знаком «–» в неравенство типа « ». Минимизацию функции заменим максимизацией функции .

Исходная задача примет вид:

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

Таким образом приходим к М-задаче:

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

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

Элементы второй симплекс-таблицы находятся обычными преобразованиями, элементы каждой из двух индексных строк находятся по правилу перпендикуляров. Базис во второй симплекс-таблице не содержит искусственной переменной, поэтому из дальнейшего рассмотрения столбец исключаем. Об оптимальности плана судим по второй индексной строке. Она содержит отрицательные элементы, следовательно, план Х₂ не оптимален. Ключевой столбец плана Х₂ соответствует столбцу , ключевой элемент находится в строке , следовательно, искусственная переменная из базиса уходит, и соответствующий ей столбец из рассмотрения исключаем. Переходим к плану .

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

План оптимален, , . Окончательное решение исходной задачи: X^*=(42/5;0;8/5), F(X^*)=58/5.

Таблица 6.

			-1	-3	-2			-М	‑M
	Баз.	св.
-М						-1
-М			1
	W
	M	-38	-3	-7	-8
			2/7	6/7		-1/7		1/7
			4/7	-2/7		5/7
			5/7	1/7		1/7
	W	-8	3/7	9/7		2/7
	M	-6	-5/7	-1/7		-1/7
	x3	8/5
		56/5
		42/5		1/5		1/5
	W	-58/5		6/5		1/5
	M

При кормлении животных необходимо использовать корма вида А и С составит в количестве 42/5 и 8/5 кг, корм вида В вводить в рацион нецелесообразно. При этом минимальная стоимость суточного рациона составит 58/5 денежных единиц.