Переход от одного опорного решения к другому. Метод потенциалов

Теорема (признак оптимальности опорного решения). Если существуют m чисел , , …, и n чисел , , …, такие, что для базисных клеток и для свободных клеток, то план , , будет оптимальным планом транспортной задачи.

Числа называются u_i потенциалами пунктов отправления, числа v_j называются потенциалами пунктов назначения.

Группа равенств для базисных клеток используется как система уравнений для нахождения потенциалов. Данная система имеет m + n неизвестных u_i и v_j (, ). Число уравнений равно m + n -1. Следовательно, чтобы найти ее решение достаточно задать значение одной неизвестной произвольно (например, u ₁=0), а остальные найти из системы.

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

Запишем неравенства в виде: .

Числа называются оценками свободных клеток таблицы ТЗ.

Оценки для свободных клеток ТЗ используются для улучшения опорного решения. С этой целью находят клетку (l, k) таблицы, соответствующую max (, ). Если , то решение оптимальное. Если , то соответствующую клетку вводят в число базисных. Т.к. базисных клеток стало m + n, то по теореме 2 из них можно построить цикл. С помощью цикла улучшают решение. Для этого необходимо расставить в клетках, которые входят в цикл знаки «+» и «–» поочередно, начиная с вновь введенной базисной клетки , в которую ставится знак «+».

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

Сдвигом по циклу на величину Q называется увеличение объемов перевозок во всех клетках цикла, отмеченных знаком «+», на , и уменьшить – во всех клетках цикла, отмеченных знаком «–», на .

Таким образом, клетка выйдет из числа базисных и получаем новое опорное решение.

Пример. На трех базах A ₁, A ₂, A ₃ находится однородный груз в количестве a ₁=30, a ₂=40, a ₃=20 т. Этот груз необходимо развести четырем потребителям B ₁, B ₂, B ₃, B ₄, потребности которых в данном грузе составляют b ₁=20, b ₂=30, b ₃=30, b ₄=10, соответственно. Стоимость перевозок пропорциональна расстоянию и количеству перевозимого груза (С – матрица тарифов). Требуется спланировать перевозки так, чтобы их общая стоимость была минимальной.

.

Решение:

Базы	Потребители
B 1	B 2	B 3	B 4
A 1
A 2
A 3

Начальное решение находится по правилу «северо-западного угла». Заполним исходную таблицу:

Таблица 1

Базы	Потребители	ai
B 1	B 2	B 3	B 4
	Потенциалы	v 1=2	v 2=3	v 3=6	v 4=10
A 1	u 1=0
A 2	u 2= -1					-		+
		20
A 3	u 3= -4					+		-
bj

Число занятых клеток .

Проверим методом потенциалов, является ли полученное опорное решение (план) – оптимальным? В заполненных клетках должно выполняться условие (данные в таблице 1). В свободных клетках должно выполняться условие .

Номера клеток	Свободные	Условие
1-3		Не выполняется
1-4		Не выполняется
2-1		Выполняется
2-4		Не выполняется
3-1		Выполняется
3-2		Выполняется

Условия оптимальности не соблюдаются в клетках 1-3, 1-4, 2-4. Наибольшая разница несовпадения в клетке 2-4, ее принимаем за основание цикла, поставив в нее знак «+». Строим замкнутый цикл, чередуя в точках поворота знаки «+» и «–». Находим в клетках со знаком «–» , – коэффициент поправки. Улучшаем исходный план, прибавляя коэффициент поправки к клеткам со знаком «+» и вычитая его из клеток со знаком «–», строим новую улучшенную таблицу (таблица 2):

Таблица 2

Базы	Потребители	ai
B 1	B 2	B 3	B 4
	Потенциалы	v 1=2	v 2=3	v 3=6	v 4=2
A 1	u 1=0			-		+
	10
A 2	u 2= -1			+		-
A 3	u 3= -4
bj

Число занятых клеток .

Проверим методом потенциалов, является ли полученное новое опорное решение (план) – оптимальным? В заполненных клетках должно выполняться условие (данные в таблице 2). В свободных клетках должно выполняться условие .

Номера клеток	Свободные	Условие
1-3		Не выполняется
1-4		Выполняется
2-1		Выполняется
3-1		Выполняется
3-2		Выполняется
3-4		Выполняется

Условия оптимальности не соблюдаются в клетке 1-3. Принимаем клетку 1-3за основание цикла, поставив в нее знак «+». Строим замкнутый цикл, чередуя в точках поворота знаки «+» и «–». Находим в клетках со знаком «–» , – коэффициент поправки. Улучшаем исходный план, прибавляя коэффициент поправки к клеткам со знаком «+» и вычитая его из клеток со знаком «–», строим новую улучшенную таблицу (таблица 3):

Таблица 3

Базы	Потребители	ai
B 1	B 2	B 3	B 4
	Потенциалы	v 1=2	v 2=3	v 3=2	v 4=2
A 1	u 1=0
A 2	u 2= -1
A 3	u 3= 0
bj

Число занятых клеток .

Проверим методом потенциалов, является ли полученное новое опорное решение (план) – оптимальным? В заполненных клетках должно выполняться условие (данные в таблице 3). В свободных клетках должно выполняться условие .

Номера клеток	Свободные	Условие
1-4		Выполняется
2-1		Выполняется
2-3		Выполняется
3-1		Выполняется
3-2		Выполняется
3-4		Выполняется

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

Ответ: , Z = 170 (д.ед.).

Вопросы для самоконтроля

1. Сформулируйте алгоритм метода северо-западного угла.

2. Сформулируйте признак оптимальности опорного решения

3. Как осуществляется сдвиг по циклу.

Методы решения транспортных задач с неправильным балансом

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

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

Чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного потребителя с запросами , и нулевыми стоимостями перевозок единиц груза =0, .

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

Тогда необходимо ввести фиктивного поставщика с запасами , и нулевыми стоимостями перевозок единиц груза =0, .

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

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

ПН   ПО					Запасы
Потреб- ности

Вопросы для самоконтроля

1. При каком условии вводится фиктивный пункт отправления?

2. При каком условии вводится фиктивный пункт потребления?

3. Что делают, если суммарные запросы потребителей превосходят суммарные запасы поставщиков?

4. Что делают, суммарные запасы поставщиков превосходят суммарные запросы потребителей?

5. Как осуществляется составление первоначального опорного решения для метода минимальной стоимости в транспортной задаче с неправильным балансом?