Методы решения транспортной задачи (метод потенциалов)

 

Министерство  образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

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

Колледж экономики, управления и права

 

КУРСОВАЯ  РАБОТА

по дисциплине «Математические методы» 

 

Тема:

Методы решения  транспортной задачи (метод потенциалов)

 

 

Автор курсовой работы  __________                Сапин Игорь Александрович_

     (подпись)      Ф.И.О.

 

Шифр специальности 230105.51  Учебная группа           СП-3-1        .

 

Оценка курсовой работы _________

 

Руководитель  курсовой работы ___________               Шинакова С.В.  

.                                          (подпись)      Ф.И.О.

 

                                                              Ростов-на-Дону

2012

 

ОТЗЫВ РУКОВОДИТЕЛЯ О КУРСОВОЙ РАБОТЕ

Студента Сапин Игорь Александрович  _____________________________

(фамилия, имя, отчество)

Тема курсовой работы  Методы решения транспортной задачи___________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

 

 

 

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

 

_______________                   Шинакова С.В.     .

(подпись)         (Ф.И.О.)

 

 

 

 

 

Оглавление

Введение 4

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

1.1 Общая постановка, цели, задачи 5

1.2 Основные  типы, виды моделей 6

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

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

2.2 Метод минимального  элемента 13

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

2.4 Скриншоты  курсового программного продукта 18

2.5 Листинг программы 19

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 48

 

Введение

 

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

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

 

 

 

 

 

 

 

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

1.1 Общая постановка, цели, задачи

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

Транспортная задача является частным типом задачи линейного  программирования и формулируется  следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт В_j, i 1, …, m; j 1, ..., n. Предположим, что

 

,

 

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

Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

 

 

Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это  означает, что

 

, i 1, …, m 

 

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

 

, j 1, …, n 

 

Объемы перевозок - неотрицательные  числа, так как перевозки из пунктов  потребления в пункты производства исключены:

x_ij 0, i 1, ..., m; j 1, ..., n

 

1.2 Основные  типы, виды моделей

 

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

Всякое неотрицательное  решение системы линейных уравнений определяемое матрицей X=(x_ij)(i 1, …, m; j 1, ..., n) и называется планом транспортной задачи.

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

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

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

 

;

 

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

 

,

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

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

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

Условие или означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное означает количество груза, перевозимого с базы потребителю : совокупность этих величин образует матрицу (матрицу перевозок).

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

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

 

 

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

 

 

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

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

 

 

или короче

 

 

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

 

 

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

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

 

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

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

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

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