2015-06-04
557
Определим начальное решение по методу Фогеля для транспортной задачи из примера 4.1 (табл.4.4).
Решение.
Разности по строкам будем записывать в правой части табл. 4.4, разности по столбцам — внизу табл.4.4. Максимальную разность будем отмечать кружком. Наименьший тариф в первой строке равен 1. Ближайший к нему равен 3. Разность равна 1. Наименьший тариф во второй строке 4. Ближайшее к нему значение 5. В третьей строке 2 и 3, соответственно. Разности по всем строкам равны 1.
Таблица 4.4
| № | Предложение | Разность по столбцам | |||||||
| 1 | 8 | 1 | 2 | - | - | ||||
| 1 | 5 | 9 | 8 | ||||||
| 9 | 2 | 3 | 6 | ||||||
| Спрос | |||||||||
| Разность по строкам | |||||||||
| - | |||||||||
| - | |||||||||
| - | - |
В первом столбце наименьший тариф c 21= 4. Ближайшее значение с 11 = 7, с 11 – c 21 = 7 – 4 = 3. Во втором столбце наименьшее значение c32 = 3. Ближайшее значение с 22 = 5, с 22 – c32 = 5 – 2 = 3.
|
|
|
Третий столбец: с 13 = 1, с 33 = 3, с 33 – с 13 = 3 -1 = 3.
Четвертый столбец: с 14= 2, с 34 = 6, с 34 – с 14 = 6 – 2 = 4.
Максимальная из всех разностей 4 находится в четвертом столбце.
В этом столбце клетка с наименьшим тарифом с 14 = 2 находится в первой строке. В эту клетку помещаем максимально возможное значение: х14 = min(110,160) = 110. Четвертый потребитель полностью удовлетворил свой спрос, и четвертый столбец вычеркиваем.
Повторяем предыдущие действия без учета вычеркнутых и заполненных клеток.
Первая строка: минимальный тариф с13 = 1. Ближайшее значение
с 11 =7, с 11 – с 13 =7-1 = 6.
Вторая строка: минимальный тариф c21 = 4. Ближайшее значение
с 22 = 5. с 22- с 21 = 5 – 4 = 1.
Третья строка: с32 = 2, с33 = 3, с33 – с32 = 3 – 2 = 1.
Первый столбец: минимальный тариф c21 = 4. Ближайшее значение с11 =7,
с11 – c21=7-4 = 3.
Второй столбец: с32 = 2, с22 = 5, с22 – с32 = 5 – 2 = 3.
Третий столбец: с13 = 1. с33 = 3, с33 — с13 =3 -1 = 3.
Максимальная разность равна 6 и стоит в первой строке. Минимальный тариф в первой строке с13 = 1. В эту клетку помещаем х13 = min(160 -110,190) = 50.
Вычеркиваем первую строку.
Повторяем все действия без учета первой строки и четвертого столбца.
Вторая строка: с21 = 4, с22 = 5, с22 – c21 = 5 – 4 = 1.
Третья строка: с32 = 2, с33 = 3, с33 – с32 = 3 – 2 = 1.
Первый столбец: c21 = 4, с31 = 9, с31 – c21 = 9 – 4 = 5.
Второй столбец: с32 = 2, с22 = 5, с22 – с32= 5 – 2 = 3.
Третий столбец: с33 = 3, с23 = 9, с23 – с33 = 9 – 3 = 6.
Максимальная разность равна 6 и стоит в третьем столбце. Минимальный из оставшихся тарифов в этом столбце с 33 = 3, х 33 =
= min(170, 90 – 50) = 140. Спрос третьего потребителя удовлетворен, третий столбец вычеркиваем.
|
|
|
Вновь составляем разности для невычеркнутых строк и столбцов.
Вторая строка: с21 = 4, с22 = 5, с22 – с21=5 – 4 = 1.
Третья строка: с32 = 2, с31 = 9, с31– с32 = 9 – 2 = 7.
Первый столбец: c21 = 4, с31 =9, с31 – c21 = 9 – 4 = 5.
Второй столбец: с32 = 2, с22 = 5, с22 – с32 = 5 – 2 = 3.
Максимальная разность стоит в третьей строке. Минимальный тариф в этой строке с32 = 2, х 32 = min(170 -140,50) = 30.
Предложение поставщика исчерпано, и третью строку вычеркиваем.
Осталась одна строка транспортной таблицы. Это вторая строка.
В этой строке сначала заполняем клетку с наименьшим тарифом c21=4, х31 =min(140,120) = 120. Оставшееся предложение второго поставщика записываем в единственную свободную клетку х22 = min(140 -120,50 –
– 30) = 20.
Полученный по методу Фогеля план перевозок имеет вид
Затраты на перевозку по этому плану составляют
S 3 = 50*1 + 110*2+120*4+20*5+30*2+140*3=1430.
S 3< S 2< S 1.
Таким образом, для одной и той же транспортной задачи получены различные начальные планы перевозок, построенные с использованием разных методов. При этом затраты на перевозки уставляют соответственно: S 1 =3220, S 2 = 1530, S 3 = 1430. Метод Фогеля наиболее трудоемкий, однако начальный план перевозок, построенный с его использованием, обычно бывает близок к оптимальному плану, а в некоторых случаях является оптимальным планом.
Изложенные методы нахождения начального решения не единственные. В качестве начального решения может быть взят любой набор чисел, удовлетворяющих ограничениям (4.9)–(4.12) (например, полученный по методу "юго-восточного" угла). Читатель может придумать свой собственный метод получения начального решения.
