Методы решение транспортных задач

Содержание

Введение

Каждый человек в определенный момент времени сталкивается с проблемой: как получить наибольший эффект, обладая ограниченными средствами. Актуальность этой работы состоит в том, что на сегодняшний день множество предприятий занимаются перевозкой продукции для ее дальнейшей реализации. Поэтому большое значение имеет процесс оптимизации грузоперевозок с целью минимизации затрат на доставку грузов. Этим вопросом занимается линейное программирование, точнее такое его направление, как решение транспортной задачи. Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Поскольку методы, изложенные Л.В. Канторовичем, были мало пригодны для ручного счета, а вычислительных машин в то время не существовало, работа Л.В. Канторовича осталась почти не замеченной.

Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов программирования. В 1975 году академик Л.В. Канторович и профессор Т. Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".

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

В пояснительной записке курсового проекта рассмотрены вопросы:

В разделе «Понятие транспортной задачи» Описывается формулировка транспортной задачи и математическая модель транспортной задачи.

В разделе «Инструментальные средства реализации курсового проекта»

Описывает операционную систему, методы решения транспортных задач и Microsoft Excel.

         В разделе «Проектная часть» описывается математическая задача и Microsoft Excel.

         В разделе «Инструкция  пользователя» описывается инструкции по которой нужно работать с программой.

         В разделе «Заключение» описываются выводы из проделанной работы.

        В разделе «Список литературы» описывается список используемой литературы

1. Понятие транспортной задачи

Под названием "транспортная задача" объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача – это задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления. Различают два типа транспортных задач: по критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени). Существует несколько методов для решения подобных задач: симплекс-метод, метод северо-западного угла (диагональный), метод наименьшего элемента, метод потенциалов решения транспортных задач, решение с помощью теории графов.

1.1 Формулировка транспортной задачи

Однородный груз сосредоточен у m поставщиков в объемах [pic 1]. Данный груз необходимо доставить n потребителям в объемах [pic 2]. Известны [pic 3], i=1,2,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.