Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ПРИМЕР РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ.
Фирма должна отправить некоторое количество кроватей с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице.
|
Склады |
Магазины |
||||
|
B1 |
B2 |
B3 |
B4 |
B5 |
|
|
A1 |
1 |
0 |
3 |
4 |
2 |
|
A2 |
5 |
1 |
2 |
3 |
3 |
|
A3 |
4 |
8 |
1 |
4 |
3 |
Как следует спланировать перевозку, чтобы её стоимость была минимальной?
Построение математической модели
Пусть Хij – количество кроватей, отправляемых со склада i в магазин j. Все Хij ≥ 0, и в силу ограничений на возможности поставки со складов (предложение) и спрос в магазинах они удовлетворяют следующим условиям:
(для предложения)
(для спроса)
Стоимость перевозок равна:
F = 1*Х11+0*Х12+3*Х13+4*Х14+2*Х15+5*Х21+ ... +4*Х34+3*Х35.
Таким образом, имеем следующую математическую модель:
Рассмотренная задача является задачей линейного программирования, но специального вида. Её результат можно обобщить на транспортную задачу общего вида.
Метод наименьшего элемента
Сущность метода в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.
Построим опорный план.
Исходная транспортная таблица:
Построение второй транспортной таблицы
Находим в таблице наименьшую стоимость перевозки – это 0 в клетке A1B2. Записываем в этой клетке значение 12 (наименьшее из сумм по строке и столбцу).
Теперь вычеркиваем второй столбец, уменьшив сумму в первой строке на 12.
Находим следующую наименьшую по стоимости ячейку – их несколько, например, A1B1. Присваиваем ей значение 3, а сумму по столбцу заменяем на 17.
Вычеркиваем первую строку.
Выбираем ячейку A3B3, присваиваем ей значение 5. Вычеркиваем третий столбец. Сумму по третьей строке заменяем на 15.
Выбираем ячейку A2B5, записываем в ней 15, уменьшаем вторую строку на 15 и вычеркиваем пятый столбец.
Выбираем ячейку A3B1, присваиваем ей 15. Уменьшаем первый столбец на 15 и вычеркиваем третью строку.
Ячейке A2B1 присваиваем 2 и вычеркиваем первый столбец. Сумму по второй строке заменяем на 8.
Ячейке A2B4 присваиваем 8 и вычеркиваем четвертый столбец.
Опорный план построен.
Х11 = 3, Х12 = 12, Х21 = 2, Х24 = 8, Х25 = 15, Х31 = 15, Х33 = 5.
Все остальные Хij = 0.
F = 3*1+0*12+5*2+3*8+3*15+5*1 = 147
Найдём теперь оптимальный план для данной задачи.
Для этого воспользуемся методом потенциалов.
PAGE 1