Ирина Эланс

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Карачев 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 Представление исходных данных классической транспортной задачи

Пункты отправления	Пункты назначения					Запасы
Пункты отправления	В₁	…	B_j	…	B_n	А₁
A₁	C₁₁ X₁₁	…	C_1j X_1j	…	C_1n X_1n	a₁
…	…	…	…	…	…	…
A_i	C_i1 X_i1	…	C_ij X_ij	…	C_in X_in	a_i
…	…	…	…	…	…	…
A_m	C_m1 X_m1	…	C_mj X_mj	…	C_mn X_mn	a_m
Потребности	b₁	…	b_j	…	b_n

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

, (1.1.5)

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

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

, i 1, ..., m.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Следующий этап состоит из серии итераций:

Первая итерация:

Фиксируем множество всех маршрутов. Поскольку граф - полный, это множество заведомо не пусто. Сопоставим ему число, которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через , то сумму констант приведения матрицы весов обозначим через . Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M₁;

Вторая итерация:

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

Сопоставим множеству следующую матрицу M_1,1: в матрице M₁ заменим на ∞ число в клетке (j, i). Затем в полученной матрице вычеркнем строку i и столбец j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M_1,1.

После этого итерации повторяются вплоть до получения окончательного ответа, причём при каждом таком повторном применении будет фиксироваться очередное ребро графа.

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

Почтовому ведомству США потребовалось определить экономный маршрут доставки почтовых грузов до открытия зимней Олимпиады в Солт-Лейк-Сити по городам: Сиэтл, Чикаго, Нью-Йорк, Мемфис, Хьюстон, Сан-Франциско, Солт-Лейк-Сити, Сент-Луис. Расстояния между городами представлены в виде матрицы:

Таблица 2.1 Исходные данные

l_ij	Сиэтл	Чикаго	Нью-Йорк	Мемфис	Хьюстон	Сан-Франциско	Солт-Лейк-Сити	Сент-Луис
Сиэтл	0	120	-	-	-	50	45	-
Чикаго	120	0	55	35	-	-	80	25
Нью-Йорк	-	55	0	60	-	-	-	-
Мемфис	-	35	60	0	75	-	-	30
Хьюстон	-	-	-	75	0	95	85	30
Сан-Франциско	50	-	-	-	95	0	40	-
Солт-Лейк-Сити	45	80	-	-	85	40	0	75
Сент-Луис	-	25	-	30	30	-	75	0

Постройте маршрут минимальной длины.

Решение

Заменим нули на бесконечности и обозначим города цифрами:

Сиэтл
Чикаго
Нью-Йорк
Мемфис
Хьюстон
Сан-Франциско
Солт-Лейк-Сити
Сент-Луис

Таким образом, исходная таблица примет следующий вид:

Таблица 2.2 Преобразованная матрица

l_ij	1	2	3	4	5	6	7	8
1	∞	120	∞	∞	∞	50	45	∞
2	120	∞	55	35	∞	∞	80	25
3	∞	55	∞	60	∞	∞	∞	∞
4	∞	35	60	∞	75	∞	∞	30
5	∞	∞	∞	75	∞	95	85	30
6	50	∞	∞	∞	95	∞	40	∞
7	45	80	∞	∞	85	40	∞	75
8	∞	25	∞	30	30	∞	75	∞

Инициализация

Выберем произвольный допустимый маршрут, состоящий, например, из звеньев (1, 7), (7, 8), (8, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1).

Вычислим стоимость данного маршрута:

то есть, цена маршрута оптимального маршрута не может превышать значения .

Первая итерация

Выполним редукцию строк; для этого в каждой строке i определим минимальный элемент, и найденное значение c_i вычтем из элементов соответствующей строки:

Таблица 2.3 Редукция строк в первой итерации

l_ij	1	2	3	4	5	6	7	8	c_i
1	∞	75	∞	∞	∞	5	0	∞	45
2	95	∞	30	10	∞	∞	55	0	25
3	∞	0	∞	5	∞	∞	∞	∞	55
4	∞	5	30	∞	45	∞	∞	0	30
5	∞	∞	∞	45	∞	65	55	0	30
6	10	∞	∞	∞	55	∞	0	∞	40
7	5	40	∞	∞	45	0	∞	35	40
8	∞	0	∞	5	5	∞	50	∞	30

В полученной таблице проведём редукцию столбцов. Для этого в каждой строке j определим минимальный элемент, и найденное значение q_i вычтем из элементов соответствующей строки:

Таблица 2.4 Редукция столбцов в первой итерации

l_ij	1	2	3	4	5	6	7	8	c_i
1	∞	75	∞	∞	∞	5	0	∞	45
2	90	∞	0	5	∞	∞	55	0	25
3	∞	0	∞	5	∞	∞	∞	∞	55
4	∞	5	0	∞	40	∞	∞	0	30
5	∞	∞	∞	40	∞	65	55	0	30
6	5	∞	∞	∞	50	∞	0	∞	40
7	0	40	∞	∞	40	0	∞	35	40
8	∞	0	∞	0	0	∞	50	∞	30
q_i	5	0	30	5	5	0	0	0	H=340

Проверка:

Если бы в каждой строке и каждом столбце было ровно по одному элементу, то эти элементы и образовывали бы оптимальный маршрут, и оптимальная стоимость была бы равна H.

` Выберем звено, на котором будет базироваться ветвление.

Таблица 2.5 Редуцированная матрица с ячейками под вторичные штрафы

l_ij	1	2	3	4	5	6	7	8	ci	A_i
1	∞	75	∞	∞	∞	5	0	∞	45	5
2	90	∞	0	5	∞	∞	55	0	25	5
3	∞	0	∞	5	∞	∞	∞	∞	55	5
4	∞	5	0	∞	40	∞	∞	0	30	5
5	∞	∞	∞	40	∞	65	55	0	30	30
6	5	∞	∞	∞	50	∞	0	∞	40	5
7	0	40	∞	∞	40	0	∞	35	40	35
8	∞	0	∞	0	0	∞	50	∞	30	30
q_i	5	0	30	5	5	0	0	0	H=340	-
B_j	5	5	30	5	5	5	50	35	-	-