Читать курсовая по математике: "Нахождение минимальных затрат при распределении товаров среди магазинов методами решения транспо" Страница 2

(Назад) (Cкачать работу)

1.1 Транспортная задача Транспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального по стоимости) плана распределения и перемещения ресурсов от производителей к потребителям. Проблема оптимизации стоимости перевозок актуальна и на сегодняшний день, так как позволяет фирмам и предприятиям существенно сократить расходы на транспорт. Правильная организация перевозок позволяет устранить встречные и дублирующие перевозки, сократить количество дальних перевозок и т. д. При решении транспортной задачи необходимо:

обеспечить всех потребителей ресурсами; распределить все произведенные ресурсы; переместить ресурсы от производителей к потребителям с наименьшими затратами.

От каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения. 1.2 Методы составления опорного плана транспортной задачи 1.2.1 Метод северо-западного угла

На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из или полностью удовлетворяется потребность . 1.2.2 Метод наименьшей стоимости

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую. И в клетку, которая ей соответствует, помещают меньшее из чисел ai или bj . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены. Либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Алгоритм:

Из таблицы тарифов выбирают наименьшую стоимость. И в клетку, которая ей соответствует, вписывают меньшее из чисел. Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п.1, в противном случае задача решена.

1.2.3 Метод потенциалов

Наиболее простым методом ТЗ является метод потенциалов. Потенциалами называются условные числа Ui ,Vj , приписанные определённым образом каждому поставщику и потребителю.

Теорема(условия оптимального плана): Сумма потенциалов поставщика и потребителя равна тарифной ставке для занятых клеток; сумма потенциалов поставщика и потребителя не превышает тарифную ставку для свободных клеток Опорный план должен быть не вырожденным (r=m+n-1 – невырожденный план)

Алгоритм решения:

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

Похожие работы