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

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

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

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

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

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

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

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

на  тему:

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

Студента 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).

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

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

    Очевидно, переменные xij должны удовлетворять условиям: 

    Система (2.1) содержит m+n уравнений с mn неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (2.1) могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (2.1) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.

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

    где символы  и означают суммирование по соответствующему индексу. Так, например,

    При этом легко заметить, что под символами  такого суммирования объединяются только свободные неизвестные (здесь i ≥ 2,j ≥ 2).

    В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные x12,x13,…,x1n с помощью вертикальных уравнений, мы получаем уравнение

    или короче

                                                         (2.2)

    где символ означает сумму всех свободных неизвестных. Аналогично, исключив из первого вертикального уравнения базисные неизвестные x21,x31,…xm1 с помощью горизонтальных уравнений, мы получаем уравнение

                                               (2.2’)

    Так как для закрытой модели транспортной задачи a=b, то полученные нами уравнения (2.2) и (2.2’) одинаковы и, исключив из одного из них неизвестное x11, мы получим уравнение-тождество 0=0, которое из системы вычеркивается.

    Итак, преобразование системы (2.1) свелось  к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (2.2). Остальные уравнения остаются неизменными. Система приняла вид

    В системе (2.3) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного x11 [она входит в первое уравнение системы (2.3)]. В системе (2.3) имеется m+n-1 уравнений, выделенный базис содержит m+n-1 неизвестных, а, следовательно, и ранг системы (2.1) r=m+n-1.

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

    Совокупность  тарифов cij также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу: 
 

    Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных xij:

                                         (2.4)

    Требуется в области допустимых решений  системы уравнений (2.1) и (2.1.1) найти  решение, минимизирующее линейную функцию (2.4).

    Таким образом, мы видим, что транспортная задача является задачей линейного  программирования. Для ее решения  применяют также симплекс-метод, но в силу специфики задачи здесь  можно обойтись без симплекс-таблиц. Решение можно получить путем  некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен m+n-1 то среди всех mn неизвестных xij выделяется m+n-1 базисных неизвестных, а остальные (m-1)*(n-1) неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем m+n-1 заполненных и (m-1)*(n-1) пустых клеток.

    Для контроля надо проверять, равна ли сумма  чисел в заполненных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце — потребности заказчика [этим подтверждается, что данный план является решением системы (2.1)].

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

    Замечание 2. Под величинами cij, очевидно, не обязательно подразумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, xij выражены в тоннах, а cij в километрах, то величина S, определяемая формулой (2.4), является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.

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

Как и  в общем случае, решение транспортной задачи начинается с отыскания первого  опорного плана (исходного базиса). Мы рассмотрим два наиболее распространенных метода построения такого базиса. Суть обоих этих методов состоит в том, что базисный план составляется последовательно, в несколько шагов (точнее, m+n-1 шагов). На каждом из этих шагов заполняется одна клетка, притом так, что, либо полностью удовлетворяется один из заказчиков (тот, в столбце которого находится заполняемая клетка), либо полностью вывозится весь запас груза с одной из баз (с той, в строке которой находится заполняемая клетка).

    В первом случае мы можем исключить  столбец, содержащий заполненную на этом шаге клетку, и считать, что  задача свелась к заполнению таблицы  с числом столбцов, на единицу меньшим, чем было перед этим шагом, но с  тем же количеством строк и  с соответственно измененным запасом груза на одной из баз (на той базе, которой был удовлетворен заказчик на данном шаге).

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

    Начиная с первоначально данной таблицы  и повторив m+n-2 раз описанный шаг, мы придем к “таблице”, состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потребность последнего заказчика. В результате, совершив m+n-1 шагов, мы и получим искомый опорный план.

    Замечание. Может случиться, что уже на некотором (но не на последнем!) шаге потребность  очередного заказчика окажется равной запасу груза на очередной базе. Тогда после заполнения очередной клетки объем таблицы как бы одновременно уменьшается на одни столбец и на одну строку. Но и при этом мы должны считать, что уменьшение объема таблицы происходит либо на один столбец, а на базе сохраняется “остаток” равный нулю, либо на одну строку, а у заказчика еще осталась неудовлетворенная “потребность” в количестве нуля единиц груза, которая и удовлетворяется на одном из следующих шагов. Этот нуль (“запас” или “потребностью” – безразлично) надо записать в очередную заполняемую клетку на одном из последующих шагов. Так как при этом оказывается равной нулю одна из базисных неизвестных, то мы имеем дело с вырожденным случаем. Различие методов отыскания первого опорного плана состоит в различии способов набора заполняемой клетки.

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

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

    При этом методе на каждом шаге построения первого опорного плана заполняется  левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного x11 и заканчивается в клетке неизвестного xmn, т. е. идет как бы по диагонали таблицы перевозок.

    Пример.