Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Транспортная задача




На трех складах А 1, А 2 и А 3 хранится а 1=100, а 2=200, а 3=60+10 n единиц одного и того же груза, соответственно. Этот груз требуется доставить трем потребителям В 1, В 2 и В 3, заказы которых b 1=190, b 2=120, b 3=10 m единиц груза, соответственно. Стоимости перевозок cij единицы груза с i -го склада j -му потребителю указаны в соответствующих клетках транспортной таблицы:

 

  Потребности Запасы В 1 В 2 В 3
b 1=190 b 2=120 b 3=10 m
А 1 а 1 = 100     m
А 2 а 2 = 200 n    
А 3 а 3 = 60 + 10 n   m + 1  

 

• Сравнивая суммарный запас и суммарную потребность

в грузе, установить, является ли модель транспортной задачи открытой или закрытой. Если модель открытая, то ее необходимо закрыть, добавив фиктивный склад А 4 с запасом а 4= b - а в случае а < b или фиктивного потребителя В 4 с потребностью b 4= a - b в случае а > b и положив соответствующие им тарифы перевозок нулевыми.

• Составить первоначальный план перевозок методом северо-западного угла и методом наименьшей стоимости.

• Методом потенциалов проверить первоначальный план перевозок на оптимальность в смысле суммарной стоимости перевозок, и если это не так, то составить оптимальный план,

обеспечивающий минимальную стоимость перевозок. Найти эту стоимость.

• Решить задачу в MS Excel в режиме «поиск решения». Ответы (значения стоимости перевозок), полученные в результате решений «вручную» и с помощью Excel, должны совпадать. Оптимальные планы перевозок могут не совпадать.

 

Решение

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 100 + 200 + 80 = 380

∑b = 190 + 120 + 20 = 330

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 50 (330—380). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v2 = 2; 0 + v2 = 2; v2 = 2

u3 + v2 = 3; 2 + u3 = 3; u3 = 1

u3 + v1 = 1; 1 + v1 = 1; v1 = 0

u2 + v1 = 2; 0 + u2 = 2; u2 = 2

u2 + v3 = 3; 2 + v3 = 3; v3 = 1

u2 + v4 = 0; 2 + v4 = 0; v4 = -2

  v1=0 v2=2 v3=1 v4=-2
u1=0   2[100]    
u2=2 2[130]   3[20] 0[50]
u3=1 1[60] 3[20]    

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.

Минимальные затраты составят: F(x) = 2*100 + 2*130 + 3*20 + 0*50 + 1*60 + 3*20 = 640

Анализ оптимального плана.

Из 1-го склада необходимо весь груз направить в 2-й магазинИз 2-го склада необходимо груз направить в 1-й магазин (130), в 3-й магазин (20)

Из 3-го склада необходимо груз направить в 1-й магазин (60), в 2-й магазин (20)

На 2-ом складе остался невостребованным груз в количестве 50 ед.

Оптимальный план является вырожденным, так как базисная переменная x24=0.






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных