Нахождение минимальных затрат при распределении товаров среди магазинов методами решения транспортной задачи

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

1.2 Методы составления опорного плана транспортной задачи

1.2.1 Метод северо-западного угла

1.2.2 Метод наименьшей стоимости

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

1.2.4 Метод аппроксимации Фогеля

Глава 2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

2.1 Постановка зад

ачи

2.2 Нахождение первоначального плана методом северо-западного угла

2.3 Нахождение первоначального плана методом наименьшей стоимости

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

2.5 Метод аппроксимации Фогеля

2.6 Применение возможностей электронных таблиц при решении транспортной задачи

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ И ИСТОЧНИКОВ

ВВЕДЕНИЕ

Транспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального по стоимости) плана распределения и перемещения ресурсов от производителей к потребителям.

Существует множество методов для решения данной задачи. Выбрав один из методов можно быстро рассчитать оптимальный план распределения, что значительно сократит затраты на доставку товаров по точкам, в отличии от метода "наугад", когда приходится гадать куда и сколько распределить товаров.

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

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

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

ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решений, в том числе и в финансовой математике. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов. В развитие и совершенствование этих систем вложен труд и талант многих математиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики.

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

· рационального использования сырья и материалов; задачи оптимального раскроя;

· оптимизации производственной программы предприятий;

· оптимального размещения и концентрации производства;

· составления оптимального плана перевозок, работы транспорта;

· управления производственными запасами;

· и многие другие, принадлежащие сфере оптимального планирования.

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

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

· обеспечить всех потребителей ресурсами;

· распределить все произведенные ресурсы;

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

От каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения.

1.2 Методы составления опорного плана транспортной задачи

1.2.1 Метод северо-западного угла

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

1.2.2 Метод наименьшей стоимости

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

Алгоритм:

· Из таблицы тарифов выбирают наименьшую стоимость. И в клетку, которая ей соответствует, вписывают меньшее из чисел.

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

· Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п.1, в противном случае задача решена.

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

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

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

Опорный план должен быть не вырожденным (r=m+n-1 – невырожденный план)

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

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

2. Находим потенциалы поставщика и потребителя, пользуясь первым условием оптимальности плана Ui + Vj < Cij

3. Проверяем второе условие оптимальности плана для свободных клеток

 Скачать реферат