Второй критерий оптимальности распределения поставок.

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

Рассмотрим m + n произвольных чисел, поставив в соответствие каждому из пунктов отправления А₁ некоторое число а₁ (i=1, 2...m)
 и каждому из пунктов назначения B_j, некоторое число B_j, (j = 1, 2...n).

Числа а_1, а₂...а_m называются потенциалами пунктов отправления, а числа B_1, B_2...B_N — потенциалами пунктов назначения.

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

    a₁+b_j=c_ij              (27)
система линейных алгебраических уравнений (27) состоит из n+m-1 уравнения с m+n неизвестными. Доказано, что эта система совместна и неопределенна. Ее ранг r = m+n-1. Для определенности считаем а₁ свободной переменной и берем базисное решение системы (27) при а₁ =0.

Установим новый критерий оптимальности решения ТЗ. Рассмотрим свободную клетку с простейшим циклом пересчета (рис. 19).

Алгебраическая сумма стоимостей свободной клетки

Все вершины цикла пересчета свободней клетки (i, j), кроме
самой клетки (i, j), базисные. Согласно (27) для базисных клеток имеем

 

тогда:

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

Согласно (28) и первому критерию оптимальности:

.
откуда следует второй критерий оптимальности:

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

4.4. 5. Решение ТЗ методом потенциалов.

1. Проверяем, является ли ТЗ задачей с правильным балансом.

2. Находим исходное допустимое базисное решение ТЗ методом СЗУ или МНС.

3. Находим потенциалы , решая систему (27). Записываем их в таблицу перевозок.

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

5. Проверяем выполнение второго критерия оптимальности: сравниваем значение стоимости с числом в кружке для всех свободных клеток.

6. Если  для всех свободных клеток, то данное распределение поставок оптимально. Если для одной или нескольких клеток , то переходим к пункту (7).

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

8. Переходим к пунктам 3-7 и повторяем процесс до тех пор, пока не будет выполнен второй критерий оптимальности решения ТЗ для всех свободных клеток.

Пример. Определяем потенциалы  решая систему:

В результате получаем

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

Проверяем выполнение критерия оптимальности. Единственная
клетка, для которой критерий оптимальности не выполнен, - (1, 2):

Определяем для клетки (1, 2) цикл пересчета, находим число
e=min{20, 50, 80}=20 и производим сдвиг по циклу на число e=20. Строим новую таблицу перевозок (табл. 10).

Таблица 9

	Пункт отправления	Пункт назначения	B1	B2	B3	B4	запасы
	A1		5 5	2+ 3	5- 20	6 40	60
	A2		3 3	1 -80	3 +0	7 4	80
	A3		4 40	5 2	4 30	6 5	70
	потребности		40	80	50	40	210

 

Таблица 10

	Пункт отправления	Пункт назначения	B1	B2	B3	B4	запасы
	A1		5 4	2+ 20	5- 4	6 40	60
	A2		3 3	1 60	3 20	7 5	80
	A3		4 40	5 2	4 30	6 6	70
	потребности		40	80	50	40	210

Следующая итерация начинается с определения потенциалов. Для этого имеем систему линейных алгебраических уравнений:

Решая систему получаем

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

Проверяем выполнение критерия оптимальности. Очевидно, что критерий оптимальности выполнен - для всех клеток .

Данное распределение поставок оптимально по критерию стоимости.

Ответ:
.

f_min=2*20+6*40+1*60+3*20+4*40+4*30=680.

 

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

4.5. ТЗ по критерию стоимости с неправильным балансом

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

 

то есть суммарная мощность поставщиков больше суммарной мощности потребителей.

Вводим фиктивный пункт назначения B_n­+1. потребности в грузе
которого составляют

Стоимости перевозок из всех пунктов отправления в фиктивный пункт назначения B_n­+1 полагаем равными нулю: c_1n­+1, c_2n­+1, … c_mn­+1=0.

Получим ТЗ с правильным балансом:

Пример. Найти оптимальное распределение поставок для Т3, заданной таблицей 11.

Таблица 11

Пункт отправления	Пункт назначения	B1	B2	B3	запасы
A1		1	3	2	20
A2		2	1	3	15
потребности		8	10	12	30	35

 

Решить задачу самостоятельно.

Ответ.

, f_min=42.

Из пункта А₂ будет отправлено 5 единиц груза.

Случай 2. Пусть

Вводим фиктивный пункт отправления A_m­+1, запас груза в котором:

,

Стоимости перевозок из фиктивного пунктa отправления A_m­+1 во все пункты назначения полагаем равными нулю: c_1m­+1, c_2m­+1, … c_m­+1n=0.

Получим ТЗ с правильным балансом:

 Пример. Найти оптимальное распределение поставок для ТЗ, заданной таблицей 12.

 

 

таблица 12.

Пункт отправления	Пункт назначения	B1	B2	B3		запасы
A1		3	1	5	2	25
A2		4	6	7	3	25
A3		2	8	4	5	15
потребности		9	20	16	25	70	65

Задачу решить самостоятельно.

Ответ.

, f_min=162.

Потребности пункта B₃ будут не удовлетворены на 5 единиц.

Замечание. При нахождении исходного решения ТЗ с неправильным балансом МНС следует фиктивные пункты учитывать в самую последнюю очередь, то есть выбирать наименьшую стоимость в первую очередь среди стоимостей реальных пунктов.

Внимание к ТЗ обусловлено тем, что задачи подобного типа и многие другие ЗЛП, во-первых, часто встречаются в практических расчётах, и, во-вторых, к ним сводятся многие другие задачи линейного программирования: сетевая задача, задача о назначениях, задача календарного планирования.

 

 

РАЗДЕЛ 3. КОНТРОЛЬНЫЕ ЗАДАНИЯ

⇐ Предыдущая123456Следующая ⇒

Поделиться: