 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Математическая модель
Определим переменные xij — количество груза, перевозимого из i-го склада в j-й магазин (
). Математическая модель транспортной задачи имеет вид:
Z = 4x11 +2x12 +5x13 ++ x21 +3x22 +3x23 +5x31 +4x32 +2x33 → min.
x11 + x12 + x13 + x14 = 50
x21 + x22 + x23 + x24 = 30
x31 + x32 + x33 + x34 = 50
x11 + x21 + x31 = 25
x12 + x22 + x32 = 30
x13 + x23 + x33 = 35
x14 + x24 + x34 = 40
хij 
0, i = 
, j = 
.
1. Нахождение опорного плана методом северо-западного угла
Построим для нахождения начального опорного планатаблицу.
Таблица 1
Нахождение начального опорного плана может осуществляться различными способами. Наиболее простым способом является метод северо-западного угла.
Определим величину элемента x 11 = min { 
, 
} = min {50, 25} = 25. Занесем эту величину в первую клетку таблицы (1). Она показывает, что первый поставщик поставляет первому потребителю 25 единиц груза.
Так как потребность первого потребителя полностью удовлетворена, закрываем первый столбец и переходим в следующую клетку (1, 2) первой строки. Оставшийся запас первого поставщика равен 25 = 50 – 25 единицам, а потребность второго потребителя равна 30 единицам. Следовательно, от первого поставщика он может получить 25 единиц, т.е. x 12 = min {25, 30} = 25.
Так как запас первого поставщика исчерпан, закроем первую строку и перейдем на следующую строку в клетку (2, 2), соответствующую второму поставщику. Его запас равен 40, а оставшаяся потребность второго потребителя равна 5. Следовательно, x 22 = min {40, 5} = 5.
Теперь потребность первого потребителя полностью удовлетворена. Поэтому закрываем второй столбец и переходим в следующую клетку второй строки. Оставшийся запас второго поставщика равен 25, а потребность третьего потребителя равна 35. Следовательно,полагаем x 23 = min {25, 35} = 25. Закрываем вторую строку и переходим на следующую строку. Третьему потребителю требуется еще 10 единиц. Их ему может поставить третий поставщик, т.е. x 33 = min {50, 10} = 10.
Таблица 2
Оставшиеся 40 единиц получает четвертый потребитель: x 34 = min {40, 40} = 40. Нахождение опорного плана перевозок завершено (см. таблицу 2). Полученный план содержит 6 ненулевых элементов. Ранг матрицы задачи также равен 6 = 3+ 4–1. Поэтому найденный опорный план является невырожденным.
Из самого способа его построения вытекает сбалансированность плана перевозок по поставщикам и потребителям. Однако во избежание ошибок рекомендуется проверить балансы путем суммирования поставок по строкам и столбцам.
Определим затраты на перевозки на построенном опорном плане (значение целевой функции).
Z = 25·4 + 25·2 + 5·3 + 25·3 + 10·2 = 260.
Замечание. Возможна ситуация, когда на каком-то шаге одновременно исчерпывается запас у текущего поставщика и полностью удовлетворяется потребность текущего потребителя. Тогда нужно закрыть либо текущую строку, либо текущий столбец, а в следующую незанятую клетку записать 0 (нулевую поставку). В этом случае после окончания работы метода будет получен вырожденный опорный план.
2. Нахождение оптимального плана методом потенциалов
Поиск по сайту: