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

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

КАРАЧЕВСКИЙ ФИЛИАЛ

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

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

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

 

 

 

 

 

Кафедра естественнонаучных дисциплин

 

 

 

 

 

 

 

 

 

 

 

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

по дисциплине

МАТЕМАТИЧЕСКИЕ МЕТОДЫ

на тему «Транспортна задача»

 

 

 

 

 

 

 

Работу выполнил студент____________________________________________

Шифр специальности________ Группа_____Факультет___________________

Специальность_______________________________________________________________________________________________________________________

Курсовая работа защищена с оценкой  _________________________________

Руководитель _____________  ________________________________________

 

 

 

 

Карачев 2010

 

Содержание

 

Введение 3

1. Транспортная задача 5

1.1 Математическая модель задачи 5

  1.2 Классификация транспортных задач 8

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

2. Решение практической  задачи 13

3. Спецификация программного  продукта 22

Заключение 24

Список использованной литературы 25

Приложение. Листинг программы CIRCLE 26

 

Введение

Задача данной курсовой работы - освоить и изучить методику решения транспортных задач.

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

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

Целями курсовой работы являются:

• построить математическую модель задачи;
• рассмотреть классификацию задач данного типа;
• рассмотреть методы решения транспортных задач;
• написать и отладить программу для решения транспортных задач с ограничениями на пропускную способность.

Работа состоит из  введения, трёх глав, и приложения, содержащего исходный код программного продукта.

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

Первый раздел содержит четыре подраздела.

В первом приводится математическая модель классической транспортной задачи, во втором – классификация задач данного типа. Подраздел 3 повествует о различных методах решения данной задачи, и наконец, в четвёртом описывается метод, выбранный для решения практической задачи.

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

Раздел 3 содержит описание работы  программы и её интерфейс.

 

 

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. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

                                             (1.1.1)

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

     (1.1.2)

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

     (1.1.3)

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

x_ij 0, i 1, ..., m; j 1, ..., n        (1.1.4)

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

Определение 1.

Всякое неотрицательное  решение системы линейных уравнений

, j 1, …, n  и  , i 1, …, m,

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

 

Определение 2.

План X*=(x*_ij)(i 1, …, m; j 1, ..., n), при котором функция

 

принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные записываются в виде таблицы 1.1.1

Таблица 1.1.1 Представление исходных данных классической транспортной задачи

Пункты отправления	Пункты назначения					Запасы
	В1	…	Bj	…	Bn	А1
A1	C11 X11	…	C1j X1j	…	C1n X1n	a1
…	…	…	…	…	…	…
Ai	Ci1 Xi1	…	Cij Xij	…	Cin Xin	ai
…	…	…	…	…	…	…
Am	Cm1 Xm1	…	Cmj Xmj	…	Cmn Xmn	am
Потребности	b1	…	bj	…	bn

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

,           (1.1.5)

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

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

, i 1, ..., m.

Введение этого условия  приводит к открытой транспортной модели.

1.2 Виды транспортных задач

Существует следующие  виды транспортных задач:

• Классическая транспортная задача
• Транспортная задача с дополнительными условиями

  Для классической транспортной задачи выделяют два типа:

• На максимум (так называемая транспортная задача по критерию стоимости)
• На минимум (так называемая транспортная задача по критерию времени (или критерию расстояния)).

 

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

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

Рассмотрим некоторые  из них:

Симплекс-метод (метод последовательного улучшения плана)

Алгоритм симплекс-метода следующий:

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

2) Формируется симплекс-таблица.

3) Рассчитываются симплекс-разности.

4) Принимается решение об окончании либо продолжении счёта.

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

 

Метод искусственного базиса

Данный метод решения  применяется при наличии в  ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m , а в задачи минимизации - с положительными m . Таким образом из исходной получается новая m - задача.

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

 

Модифицированный симплекс - метод

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

В процессе работы алгоритма  происходит спонтанное обращение матрицы  ограничений по частям, соответствующим  текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Хорош для ситуаций, когда число переменных n значительно превышает число ограничений m.

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

 

1.4 Методика решения транспортных задач на замкнутые маршруты

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

Рассмотрим данный алгоритм подробнее.

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

Впервые метод  ветвей и границ был предложен  Лендом и Дойгом в 1960 для решения  общей задачи целочисленного линейного  программирования. Интерес к этому  методу и фактически его “второе  рождение” связано с работой  Литтла, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям.