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

Федеральное агентство  по образованию Российской Федерации

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

(ГОУВПО «АмГУ»)

 

Кафедра информационных и управляющих систем

 

 

 

 

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

 

 

 

 

на тему: Транспортная задача

по курсу «Теория принятия решения»

 

 

 

Исполнитель

студент группы 254    __________________  В.А. Артемьев

 

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

к.т.н.     ___________________  С.Г. Самохвалова

 

Нормоконтроль 

к.т.н.     ___________________  С.Г. Самохвалова

 

 

Благовещенск 2005

 

Федеральное агентство по образованию  Российской Федерации

Амурский  Государственный Университет

(ГОУВПО «АмГУ»)

 

Факультет математики и  информатики

Кафедра информационных и управляющих систем

 

 

 

ЗАДАНИЕ

 

 

 

К курсовой работе студента

1. Тема работы: Оптимизация  экономических процессов.

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

Центральный склад обеспечивает доставку товаров в M точек. Существует N маршрутов, каждый из которых позволяет обслужить некоторое подмножество пунктов назначения. Пусть C_ij – стоимость доставки по j-му маршруту. Считая что, каждое транспортное средство может обеспечить доставку не более К заказов, построить план оптимального распределения транспортных средств по маршрутам.

3. Срок сдачи студентами законченной работы: 23.05.2005 г.

4. Дата выдачи задания ________________

 

Руководитель курсовой работы  Самохвалова Светлана Геннадиевна, к.т.н.

Задание принял к исполнению (дата)__________________

 

__________

  (подпись студента)

 

 

РЕФЕРАТ

 

 

Работа 32 с., 4 рисунков, 10 таблиц, 3 источников, 2 приложений

 

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

 

 

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

 

СОДЕРЖАНИЕ

 

 

Введение	5
1. Содержательное и формализованное описание задачи	6
2. Математическая модель задачи	7
3. Выбор метода и  разработка алгоритма решения  задачи	9
3.1 Получение начального базисного решения	10
3.2 Нахождение вводимой переменной. Метод потенциалов	13
3.3 Поиск выводимой переменной. Построение циклов	14
4. Программная реализация	15
5. Экспериментальная проверка и разработка рекомендаций по практическому использованию результатов	16
6. Руководство пользователя	21
Заключение	24
Библиографический список	25
Приложение А. Блок-схема алгоритма решения задачи	26
Приложение Б. Листинг программного модуля	27

 

ВВЕДЕНИЕ

 

 

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

Одной из распространенных задач оптимизации  является задача о минимизации затрат при транспортировке грузов. Данная задача является одной из центральных в экономическом планировании наряду с задачей максимизации доходов при ограниченных ресурсах.

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

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

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

 

 

1 СОДЕРЖАТЕЛЬНОЕ И  ФОРМАЛИЗОВАННОЕ ОПИСАНИЕ ЗАДАЧИ

 

 

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

Для решения поставленной задачи необходимо определить:

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

Вышеперечисленное относится к входной информации.

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

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

 

2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ

 

 

Согласно условиям задачи требуется  построить план оптимального распределения  транспортных средств по маршрутам. Введем следующие обозначения:

• М – количество пунктов назначения;
• N – число маршрутов;
• С_ij – стоимость доставки в j-й пункт по i-му маршруту;
• k_i – емкость транспортного средства;
• Е – потребности пункта назначения;
• X_ij – количество заказов, перевозимое i-м транспортным средством в j-й пункт назначения;
• Z – целевая функция;
• b_j – потребность j-го пункта назначения.

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

Исходя из введенных обозначений, построим целевую функцию:  (1)

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

, где   (2)

Также необходимо, чтобы суммарная  емкость всех транспортных была не меньше потребности j-го пункта назначения:

, где   (3)

Очевидно, что число доставляемых заказов не может быть отрицательным:

, где   (4)

Таким образом, математическая формулировка задачи будет следующей: на множестве допустимых решений системы ограничений (2) - (4) найти такое решение Х=(х₁₁, х₁₂, … , х_mn), при котором значение целевой функции (1) будет минимально.

 

3 ВЫБОР МЕТОДА И РАЗРАБОТКА  АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

 

 

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

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

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

  (5)

Условия (2) и (3) примут вид:

, где  (6)

, где  ; (7)

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

 (8)

Несбалансированную транспортную задачу легко сбалансировать путем введения фиктивного пункта назначения с величиной спроса:

b_M+1 = (k₁ + ... + k_N) - (b₁ + ... + b_M),    (9)

Стоимость доставки до этого  фиктивного пункта любым транспортным средством равна нулю:

С_i,M+1 = 0, где i=1,...,N                 (10)

В результате указанной балансировки условия (2) принимают вид:

, где   (11)

а условие (3):

, где    (13)

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

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

Решение задачи осуществляется поэтапно. Можно выделить основные следующие  шаги решения (см. прил. 1):

1. проверка сбалансированности задачи и при необходимости её балансирование;
2. нахождение начального базисного решения;
3. проверка оптимальности решения и поиск вводимой переменной. В случае оптимальности решения процесс вычисления заканчивается;
4. поиск выводимой переменной, получение нового решения и переход к шагу 3.

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

 

3.1 Получение начального базисного решения

Существует следующие способы  нахождения начального базисного решения:

1. метод «северо-западного» угла (диагональный метод);
2. метод наименьшей стоимости;
3. приближенный метод Фогеля.

Поэтому важно оценить все методы и выбрать наиболее приемлемый, как  с точки зрения качества метода, так и сложности реализации на ЭВМ.

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

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

Приближенный метод Фогеля является эвристическим. Алгоритм состоит из следующих шагов.

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

Шаг 2: Отметить строку или столбец с самым большим штрафом, а если таких несколько, выбрать среди них любую строку или столбец. В отмеченной строке или столбце выбрать переменную с самым коротким расстоянием и придать ей наибольшее возможное значение. Скорректировать величины спроса и предложения и вычеркнуть строку или столбец, соответствующий выполненному ограничению. Если ограничения по строке или столбцу выполняются одновременно, то вычеркнуть либо строку, либо столбец, а оставшемуся столбцу (строке) предписать нулевой спрос (предложение). Строка (или столбец) с нулевым предложением или спросом не используются в дальнейших вычислениях (на шаге 3).