Транспортные задачи

 

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ 

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ 

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

им. Н. П. ОГАРЁВА» 

Факультет довузовской подготовки и среднего профессионального  образования 
 
 
 

Курсовая  работа

на  тему:

“Транспортные задачи” 
 
 
 
 

Студента 309 группы                           _________                  _____________             А. И. рап

                                                                                  (подпись)                                          (дата)

Специальность 230105 «Программное обеспечение вычислительной

техники и автоматизированных систем» 

Обозначение курсовой работы        КР-230105-012-2010 

Руководитель  работы

преподаватель                   __________                           _____________                Д. Р. Азз                                

                                                (подпись)                                                              (дата)

                                                                                    

                                                                                        Оценка: 
 
 
 

Саранск 2010

 

Содержание 

Введение . . . . . . . . . . . . . . . . . . . . . . . .  . . .. . .  . . . . . . . . . .  . . . . . . . .3

1 Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  5

2 Методы составления начального опорного плана . . . . . . . . . . . . .11

3 Методы решения транспортной задачи

3.1Диагональный метод, или метод северо-западного угла . . . . . . 12

3.2 Метод наименьшей стоимости . . . .  . . . . . . . . . . . . . . . . . . . . . . 13

3.3 Метод потенциалов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14

4. Транспортная задача с избытком заявок . . . . . . . . . . . . . . . . . . . 22

5. Пример решения транспортной задачи . . . . . . . . . . . . . . . . . . . . .24

Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31

Список использованных источников . . . . . . . . . . . . . . . . . . . . . . . . .32 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

    Каждый  человек ежедневно, не всегда осознавая  это, решает проблему: как получить наибольший эффект, обладая ограниченными  средствами. Наши средства и ресурсы  всегда ограничены. Жизнь была бы менее  интересной, если бы это было не так. Не трудно выиграть сражение, имея армию  в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить  план, или программу действий. Раньше план в таких случаях составлялся  “на глазок” (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование” здесь  и в аналогичных терминах (“линейное  программирование, динамическое программирование”  и т.п.) обязано отчасти историческому  недоразумению, отчасти неточному  переводу с английского. По-русски лучше  было бы употребить слово “планирование”. С программированием для ЭВМ  математическое программирование имеет  лишь то общее, что большинство возникающих  на практике задач математического  программирования слишком громоздки  для ручного счета, решить их можно  только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято  считать 1939г., когда была напечатана брошюра Леонида Витальевича  Канторовича “Математические методы организации и планирования производства”. Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти  не замеченной.

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

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

    Однако  идеи Л.В.Канторовича не встретили  понимания в момент их зарождения, были объявлены ересью, и его работа была прервана. Концепции Леонида  Витальевича вскоре после войны  были переоткрыты на западе. Американский экономист Т.Купманс в течение  многих лет привлекал внимание математиков  к ряду задач, связанных с военной  тематикой. Он активно способствовал  тому, чтобы был организован математический коллектив для разработки этих проблем. В итоге было осознано, что надо научиться решать задачи о нахождении экстремумов линейных функций на многогранниках, задаваемых линейными  неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования. Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны. Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто похожее на разработку начал линейного программирования. Как легко было бы Данцигу и Купмансу проигнорировать эту информацию! Маленькая книжица, изданная ничтожным тиражом, обращенная даже не к экономистам, а к организаторам производства, с минимумом математики, без четко описанных алгоритмов, без доказательств теорем – словом, стоит ли принимать такую книжку во внимание… Но Купманс настаивает на переводе и издании на западе книги Канторовича. Его имя и идеи становятся известны всем. Воздадим должное благородству американского ученого! А самому Леониду Витальевичу – как естественно было бы ему, испытав первые грозные удары ретроградов, остеречься от “грехов” молодости, забыть про всю эту экономику и вернуться к математике. Но Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет, и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А, начиная с 1960 года, Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году.

 

1 Транспортная задача. Общая постановка, цели, задачи. Основные  типы, виды моделей

    Под названием “транспортная задача”  объединяется широкий круг задач  с единой математической моделью. Данные задачи относятся к задачам линейного  программирования и могут быть решены симплексным методом. Однако матрица  системы ограничений транспортной задачи настолько своеобразна, что  для ее решения разработаны специальные  методы. Эти методы, как и симплексный  метод, позволяют найти начальное  опорное решение, а затем, улучшая  его, получить оптимальное решение.

    В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с m баз A1,A2,…,Am n потребителям B1,B2,…,Bn.

    Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

    Обозначим количество груза, имеющегося на каждой из m баз (запасы), соответственно a1,a2,…am, а общее количество имеющегося в наличии груза – a:

     ;                                         (1.1)

    заказы  каждого из потребителей (потребности) обозначим соответственно b1,b2,…,bn, а общее количество потребностей – b:

     ,                                                 (1.2)

    Тогда при условии

                                                                 (1.3)

    мы  имеем закрытую модель, а при условии

                                                                 (1.4)

    – открытую модель транспортной задачи.

    Очевидно, в случае закрытой модели весь имеющийся  в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики  удовлетворены и при этом на некоторых  базах остаются излишки груза (a > b), либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены (a < b).

    Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.

    План  перевозок с указанием запасов  и потребностей удобно записывать в  виде следующей таблицы, называемой таблицей перевозок: