Анализ и принятие решений на основе задач транспортного типа

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ  УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ВЫСОКИХ  ТЕХНОЛОГИЙ

 

 

 

 

 

 

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

 

ПО ТЕМЕ:

АНАЛИЗ  И ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ ЗАДАЧ  ТРАНСПОРТНОГО ТИПА

 

 

ДИСЦИПЛИНА: СИСТЕМНЫЙ АНАЛИЗ И ПРИНЯТИЕ РЕШЕНИЙ

 

 

 

 

 

 

 

 

 

 

Выполнил  ст-т гр 3-2

______________ Чекина  А.Н.

 

Принял преподаватель

______________ Золотарев  А. А

«___»________ 2013 г.

 

 

 

 

 

 

 

 

 

 

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

2013

 

СОДЕРЖАНИЕ

 

Введение                                                                                                                   3

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

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

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

Глава 2. Методы решения транспортной задачи                                                 9

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

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

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

2.4. Метод потенциалов как метод решения транспортной задачи                  14

Заключение                                                                                                             18

Список литературы                                                                                                19

Приложения                                                                                                           20

 

Введение

 

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

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

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

- рассмотреть транспортную задачу, общую постановку, цели, задачи;

- изучить основные типы, виды  моделей;

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

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

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

Предметом исследования является транспортная задача. Объектом исследования выступает  метод потенциалов.

 

Глава 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 Основные типы, виды моделей

 

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

Определение 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)

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

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

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

 

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

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

 

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

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

Теперь переходим к заполнению клетки для неизвестного и т.д.

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

Общий объем перевозок в тонно-километрах для этого плана составит

 

.

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

 

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