Метод Фогеля

Метод Фогеля

Правила ввода данных

Поиск

Процесс

Сообщение

Данный метод состоит в следующем:

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

В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом. Если существует несколько одинаковых по величине максимальных штрафов в матрице, то в соответствующих строках или столбцах выбирается одна не вычеркнутая клетка с минимальным тарифом. Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП
Симплексный метод решения ЗЛП
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных
Задачи динамического программирования

Как правило, опорный план, получаемый с помощью метода Фогеля, является сразу оптимальным (как в примере №2), но иногда приходиться применять и метод потенциалов для его улучшения (пример №1).

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

Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 78 + 94 + 29 + 86 = 287
∑ b = 49 + 60 + 78 + 50 + 50 = 287
Занесем исходные данные в распределительную таблицу.

1. Используя метод Фогеля, построим первый опорный план транспортной задачи.
1. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Первый минимальный элемент строки N=1 равен 5. Второй минимальный элемент строки N=1 равен 7. Разность равна 2.
Первый минимальный элемент строки N=2 равен 6. Второй минимальный элемент строки N=2 равен 29. Разность равна 23.
Первый минимальный элемент строки N=3 равен 11. Второй минимальный элемент строки N=3 равен 19. Разность равна 8.
Первый минимальный элемент строки N=4 равен 13. Второй минимальный элемент строки N=4 равен 28. Разность равна 15.
Первый минимальный элемент столбца N=1 равен 9. Второй минимальный элемент столбца N=1 равен 30. Разность равна 21.
Первый минимальный элемент столбца N=2 равен 5. Второй минимальный элемент столбца N=2 равен 20. Разность равна 15.
Первый минимальный элемент столбца N=3 равен 6. Второй минимальный элемент столбца N=3 равен 7. Разность равна 1.
Первый минимальный элемент столбца N=4 равен 10. Второй минимальный элемент столбца N=4 равен 25. Разность равна 15.
Первый минимальный элемент столбца N=5 равен 18. Второй минимальный элемент столбца N=5 равен 19. Разность равна 1.
Вычислив все эти разности, видим, что наибольшая из них соответствует строке (2). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (3).

	1	2	3	4	5	Запасы	Разности по строкам
1	9	5	7	10	18	78	2
2	36	29	6	38	40	94	23
3	41	20	11	25	19	29	8
4	30	28	13	39	50	86	15
Потребности	49	60	78	50	50	0	0
Разности по столбцам	21	15	1	15	1	0

Первый минимальный элемент строки N=1 равен 5. Второй минимальный элемент строки N=1 равен 9. Разность равна 4.
Первый минимальный элемент строки N=2 равен 29. Второй минимальный элемент строки N=2 равен 36. Разность равна 7.
Первый минимальный элемент строки N=3 равен 19. Второй минимальный элемент строки N=3 равен 20. Разность равна 1.
Первый минимальный элемент строки N=4 равен 28. Второй минимальный элемент строки N=4 равен 30. Разность равна 2.
Первый минимальный элемент столбца N=1 равен 9. Второй минимальный элемент столбца N=1 равен 30. Разность равна 21.
Первый минимальный элемент столбца N=2 равен 5. Второй минимальный элемент столбца N=2 равен 20. Разность равна 15.
Первый минимальный элемент столбца N=4 равен 10. Второй минимальный элемент столбца N=4 равен 25. Разность равна 15.
Первый минимальный элемент столбца N=5 равен 18. Второй минимальный элемент столбца N=5 равен 19. Разность равна 1.
Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (1). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (1).

	1	2	3	4	5	Запасы	Разности по строкам
1	9	5	7	10	18	78	4
2	36	29	6	38	40	16	7
3	41	20	11	25	19	29	1
4	30	28	13	39	50	86	2
Потребности	49	60	0	50	50	0	0
Разности по столбцам	21	15	-	15	1	0

Первый минимальный элемент строки N=1 равен 5. Второй минимальный элемент строки N=1 равен 10. Разность равна 5.
Первый минимальный элемент строки N=2 равен 29. Второй минимальный элемент строки N=2 равен 38. Разность равна 9.
Первый минимальный элемент строки N=3 равен 19. Второй минимальный элемент строки N=3 равен 20. Разность равна 1.
Первый минимальный элемент строки N=4 равен 28. Второй минимальный элемент строки N=4 равен 39. Разность равна 11.
Первый минимальный элемент столбца N=2 равен 5. Второй минимальный элемент столбца N=2 равен 20. Разность равна 15.
Первый минимальный элемент столбца N=4 равен 10. Второй минимальный элемент столбца N=4 равен 25. Разность равна 15.
Первый минимальный элемент столбца N=5 равен 18. Второй минимальный элемент столбца N=5 равен 19. Разность равна 1.
Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (4). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (4).

	1	2	3	4	5	Запасы	Разности по строкам
1	9	5	7	10	18	29	5
2	36	29	6	38	40	16	9
3	41	20	11	25	19	29	1
4	30	28	13	39	50	86	11
Потребности	0	60	0	50	50	0	0
Разности по столбцам	-	15	-	15	1	0

Читать далее
4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

	v₁=7	v₂=5	v₃=-16	v₄=10	v₅=18
u₁=0	9	5[23]	7	10[50]	18[5]
u₂=22	36	29	6[78]	38	40[16]
u₃=1	41	20	11	25	19[29]
u₄=23	30[49]	28[37]	13	39	50

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j <= c_ij.
Минимальные затраты составят: F( x) = 5*23 + 10*50 + 18*5 + 6*78 + 40*16 + 19*29 + 30*49 + 28*37 = 4870

Пример №2
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	Запасы
1	5	2	1	8	10
2	2	1	2	3	10
3	4	8	1	4	20
Потребности	14	15	5	6

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 10 + 10 + 20 = 40
∑b = 14 + 15 + 5 + 6 = 40
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	5	2	1	8	10
2	2	1	2	3	10
3	4	8	1	4	20
Потребности	14	15	5	6

Этап I. Поиск первого опорного плана.
1. Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Данный метод состоит в следующем:
1. на каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;
2. находят максимальную разность и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.
Находим разности по строкам.
Для строки N=1 первый минимальный элемент min¹₁= 1, второй минимальный элемент min²₁= 2. Их разность равна d = min²₁- min¹₁= 1.
Для строки N=2 первый минимальный элемент min¹₂= 1, второй минимальный элемент min²₂= 2. Их разность равна d = min²₂- min¹₂= 1.
Для строки N=3 первый минимальный элемент min¹₃= 1, второй минимальный элемент min²₃= 4. Их разность равна d = min²₃- min¹₃= 3.
Находим разности по столбцам.
Для столбца N=1 первый минимальный элемент min¹₁= 2. второй минимальный элемент min²₁4. Их разность d = min²₁- min¹₁= 2.
Для столбца N=2 первый минимальный элемент min¹₂= 1. второй минимальный элемент min²₂2. Их разность d = min²₂- min¹₂= 1.
Для столбца N=3 первый минимальный элемент min¹₃= 1. второй минимальный элемент min²₃1. Их разность d = min²₃- min¹₃= 0.
Для столбца N=4 первый минимальный элемент min¹₄= 3. второй минимальный элемент min²₄4. Их разность d = min²₄- min¹₄= 1.
Вычислив все эти разности, видим, что наибольшая из них соответствует строке (3). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (3) и столбца (3).

Искомый элемент равен 1
Для этого элемента запасы равны 20, потребности 5. Поскольку минимальным является 5, то вычитаем его.
x₃₃= min(20,5) = 5.

0	x	0	0
0	x	x	0
0	0	x	20 - 5 = 15
x	5 - 5 = 0	x	x

Находим разности по строкам.
Для строки N=1 первый минимальный элемент min¹₁= 2, второй минимальный элемент min²₁= 5. Их разность равна d = min²₁- min¹₁= 3.
Для строки N=2 первый минимальный элемент min¹₂= 1, второй минимальный элемент min²₂= 2. Их разность равна d = min²₂- min¹₂= 1.
Для строки N=3 первый минимальный элемент min¹₃= 4, второй минимальный элемент min²₃= 4. Их разность равна d = min²₃- min¹₃= 0.
Находим разности по столбцам.
Для столбца N=1 первый минимальный элемент min¹₁= 2. второй минимальный элемент min²₁4. Их разность d = min²₁- min¹₁= 2.
Для столбца N=2 первый минимальный элемент min¹₂= 1. второй минимальный элемент min²₂2. Их разность d = min²₂- min¹₂= 1.
Для столбца N=4 первый минимальный элемент min¹₄= 3. второй минимальный элемент min²₄4. Их разность d = min²₄- min¹₄= 1.
Вычислив все эти разности, видим, что наибольшая из них соответствует строке (1). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (2).

Искомый элемент равен 2
Для этого элемента запасы равны 10, потребности 15. Поскольку минимальным является 10, то вычитаем его.
x₁₂= min(10,15) = 10.

x	0	0	x	10 - 10 = 0
0	x	x	x	x
0	0	x	0	0
0	15 - 10 = 5	x	0	0

Находим разности по строкам.
Для строки N=2 первый минимальный элемент min¹₂= 1, второй минимальный элемент min²₂= 2. Их разность равна d = min²₂- min¹₂= 1.
Для строки N=3 первый минимальный элемент min¹₃= 4, второй минимальный элемент min²₃= 4. Их разность равна d = min²₃- min¹₃= 0.
Находим разности по столбцам.
Для столбца N=1 первый минимальный элемент min¹₁= 2. второй минимальный элемент min²₁4. Их разность d = min²₁- min¹₁= 2.
Для столбца N=2 первый минимальный элемент min¹₂= 1. второй минимальный элемент min²₂8. Их разность d = min²₂- min¹₂= 7.
Для столбца N=4 первый минимальный элемент min¹₄= 3. второй минимальный элемент min²₄4. Их разность d = min²₄- min¹₄= 1.
Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (2). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (2).

Искомый элемент равен 1
x₂₂= min(10,5) = 5.

0	0	0	0
0	x	0	10 - 5 = 5
x	x	x	x
5 - 5 = 0	x	0	0

Находим разности по строкам.
Для строки N=2 первый минимальный элемент min¹₂= 2, второй минимальный элемент min²₂= 3. Их разность равна d = min²₂- min¹₂= 1.
Для строки N=3 первый минимальный элемент min¹₃= 4, второй минимальный элемент min²₃= 4. Их разность равна d = min²₃- min¹₃= 0.
Находим разности по столбцам.
Для столбца N=1 первый минимальный элемент min¹₁= 2. второй минимальный элемент min²₁4. Их разность d = min²₁- min¹₁= 2.
Для столбца N=4 первый минимальный элемент min¹₄= 3. второй минимальный элемент min²₄4. Их разность d = min²₄- min¹₄= 1.
Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (1). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (1).

Искомый элемент равен 2
x₂₁= min(5,14) = 5.

0	0	0	0	0
0	x	0	x	5 - 5 = 0
0	x	x	x	x
14 - 5 = 9	x	0	0	0

Находим разности по строкам.
Для строки N=3 первый минимальный элемент min¹₃= 4, второй минимальный элемент min²₃= 4. Их разность равна d = min²₃- min¹₃= 0.
Находим разности по столбцам.
Для столбца N=1 первый минимальный элемент min¹₁= 4. второй минимальный элемент min²₁4. Их разность d = min²₁- min¹₁= 0.
Для столбца N=4 первый минимальный элемент min¹₄= 4. второй минимальный элемент min²₄4. Их разность d = min²₄- min¹₄= 0.
Вычислив все эти разности, видим, что наибольшая из них соответствует строке (3). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (3) и столбца (1).

Искомый элемент равен 4
x₃₁= min(15,9) = 9.

0	0	0	0	0
0	x	0	0	0
0	x	0	0	15 - 9 = 6
9 - 9 = 0	x	x	x	x

Находим разности по строкам.
Для строки N=3 первый минимальный элемент min¹₃= 4, второй минимальный элемент min²₃= 4. Их разность равна d = min²₃- min¹₃= 0.
Находим разности по столбцам.
Для столбца N=4 первый минимальный элемент min¹₄= 4. второй минимальный элемент min²₄4. Их разность d = min²₄- min¹₄= 0.
Вычислив все эти разности, видим, что наибольшая из них соответствует строке (3). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (3) и столбца (4).

Искомый элемент равен 4
x₃₄= min(6,6) = 6.

0	0	0	0
0	0	0	x
0	0	0	6 - 6 = 0
x	x	6 - 6 = 0	x

	1	2	3	4	Запасы
1	5	2[10]	1	8	10
2	2[5]	1[5]	2	3	10
3	4[9]	8	1[5]	4[6]	20
Потребности	14	15	5	6

Сведем все вычисления в одну таблицу.

	1	2	3	4	Запасы	d₁	d₂	d₃	d₄
1	5	2[10]	1	8	10	1	3	-	-
2	2[5]	1[5]	2	3	10	1	1	1	1
3	4[9]	8	1[5]	4[6]	20	3	0	0	0
Потребности	14	15	5	6
d₁	2	1	0	1
d₂	2	1	-	1
d₃	2	7	-	1
d₄	2	-	-	1

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*10 + 2*5 + 1*5 + 4*9 + 1*5 + 4*6 = 100

Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалыu_i, v_j. по занятым клеткам таблицы, в которых u_i+ v_j= c_ij, полагая, что u₁= 0.
u₁+ v₂= 2; 0 + v₂= 2; v₂= 2
u₂+ v₂= 1; 2 + u₂= 1; u₂= -1
u₂+ v₁= 2; -1 + v₁= 2; v₁= 3
u₃+ v₁= 4; 3 + u₃= 4; u₃= 1
u₃+ v₃= 1; 1 + v₃= 1; v₃= 0
u₃+ v₄= 4; 1 + v₄= 4; v₄= 3

	v₁=3	v₂=2	v₃=0	v₄=3
u₁=0	5	2[10]	1	8
u₂=-1	2[5]	1[5]	2	3
u₃=1	4[9]	8	1[5]	4[6]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j <= c_ij.
Минимальные затраты составят: F(x) = 2*10 + 2*5 + 1*5 + 4*9 + 1*5 + 4*6 = 100
Анализ оптимального плана.
Из первого склада необходимо весь груз направить в второй магазин
Из 2-го склада необходимо груз направить в 1-й магазин (5), в 2-й магазин (5)
Из третьего склада необходимо груз направить в 1-й магазин (9), в третий магазин (5), в 4-й магазин (6).

Потребности