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

 

Исследовать вектор на оптимальность в задаче ЛП.

Вначале нужно проверить, является ли вектор допустимым. Для этого подставляем координаты вектора в ограничения:

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

Построим двойственную задачу:

Поскольку , то из третьего и четвертого ограничений получаем . Но по УДН из условия следует, что должно выполняться равенство в первом ограничении двойственной задачи:

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

Пример решения задачи ЦЛП

 

Решить задачу ЦЛП.

Решаем задачу ЛП симплекс-методом. Оптимальная таблица имеет вид

 

	b
L	-14/3	-4/3	-2/3
	5/3	1/3	2/3
	4/3	2/3	-2/3

 

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

Приписывая это ограничение к симплексной таблице и проводя стандартное преобразование двойственным симплекс-методом, получим:

 

	b
L	-14/3	-4/3	-2/3
	5/3	1/3	2/3
	4/3	2/3	-2/3
	-2/3	-1/3	-2/3

 

	b
L	-4	-1	-1
			-1
		1/2	-3/2

 

Полученная таблица является оптимальной. Соответствующее оптимальное решение является целочисленным. Значение функции на этом решении .

 

 

Пример построения опорного плана методом

Северо-западного угла

 

 

=

 

 

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

 

Пример построения опорного плана методом

Минимальной стоимости

 

		9	57	301
		152	153	8
				=

 

Пример решения транспортной задачи методом

Потенциалов

 

	3	8	2
	7	4	8
				=

 

Опорный план этой задачи найден методом северо-западного угла.

Приписываем к таблице строку для платежей и столбец для платежей . Псевдостоимости записываем в левом углу клетки, а стоимости – в правом.

Из условий в базисных клетках получаем систему уравнений:

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

 

		[-] 20	12 2 [+]
	-1 7	[+] 0	[-] 30		-4
				=

 

 

Стоимость перевозок по плану этой таблицы

 

.

Так как клетка (1,3) имеет отрицательную цену , то план не является оптимальным. Строим для клетки (1,3) цикл. Цена цикла . По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1,2) не стали отрицательными). При этом стоимость плана изменяется на . Для нового плана вычисляем новые значения платежей и псевдостоимостей:

 

	[-] 15	-2 8	[+] 20
	9 7 [+]		[-] 10
				=
		-2

 

Стоимость перевозок по плану этой таблицы

 

.

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

 

		0 8
			5 8
				=

 

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

.