Автор: Пользователь скрыл имя, 28 Октября 2013 в 14:15, курсовая работа
Целью данной работы является рассмотрение транспортной задачи и метода потенциалов как метода ее решения.
Для реализации данной цели в работе необходимо решить следующие задачи:
- рассмотреть транспортную задачу, общую постановку, цели, задачи;
- изучить основные типы, виды моделей;
- охарактеризовать методы решения транспортной задачи;
- проанализировать метод потенциалов как метод решения транспортной задачи.
Введение 3
Глава 1. Транспортная задача: общая постановка, типы и виды моделей 4
1.1. Общая постановка, цели, задачи 4
1.2. Основные типы, виды моделей 6
Глава 2. Методы решения транспортной задачи 9
2.1. Диагональный метод, или метод северо-западного угла 9
2.2. Метод минимального элемента 10
2.3. Метод наименьшей стоимости 12
2.4. Метод потенциалов как метод решения транспортной задачи 14
Заключение 18
Список литературы
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ВЫСОКИХ ТЕХНОЛОГИЙ
КУРСОВАЯ РАБОТА
ПО ТЕМЕ:
АНАЛИЗ И ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ ЗАДАЧ ТРАНСПОРТНОГО ТИПА
ДИСЦИПЛИНА: СИСТЕМНЫЙ АНАЛИЗ И ПРИНЯТИЕ РЕШЕНИЙ
Выполнил ст-т гр 3-2
______________ Чекина А.Н.
Принял преподаватель
______________ Золотарев А. А
«___»________ 2013 г.
Ростов-на-Дону
2013
СОДЕРЖАНИЕ
Введение
Глава 1. Транспортная задача: общая постановка, типы и виды моделей 4
1.1. Общая постановка, цели, задачи
1.2. Основные типы, виды моделей
Глава 2. Методы решения транспортной
задачи
2.1. Диагональный метод, или метод северо-западного
угла
2.2. Метод минимального элемента
2.3. Метод наименьшей стоимости
2.4. Метод потенциалов как метод решения транспортной задачи 14
Заключение
Список литературы
Приложения
Введение
Актуальность выбранной
Целью данной работы является рассмотрение транспортной задачи и метода потенциалов как метода ее решения.
Для реализации данной цели в работе необходимо решить следующие задачи:
- рассмотреть транспортную
- изучить основные типы, виды моделей;
- охарактеризовать методы
- проанализировать метод
Новизна и практическая значимость
работы обусловлена тем фактом, что
транспортная задача линейного программирования
получила в настоящее время широкое
распространение в
Предметом исследования является транспортная задача. Объектом исследования выступает метод потенциалов.
Под названием «транспортная
Транспортная задача является частным
типом задачи линейного программирования
и формулируется следующим
т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу3.
Пусть хij - количество единиц продукта, поставляемого из пункта Аi в пункт Вj. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:
Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что
Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно потребности. Это условие полного удовлетворения спроса:
Объемы перевозок - неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены:
xij
Транспортная задача сводится, таким образом, к минимизации суммарных затрат при выполнении условий полного удовлетворения спроса и равенства вывозимого количества продукта запасам его в пунктах отправления4.
Определение 1.
Всякое неотрицательное
определяемое матрицей X=(xij)(i 1, …, m; j 1, ..., n), называется планом транспортной задачи.
Определение 2.
План X*=(x*ij)(i 1, …, m; j 1, ..., n), при котором функция
принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
В общей постановке транспортная задача
состоит в отыскании
Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени) 5.
Обозначим количество груза, имеющегося на каждой из баз (запасы), соответственно ,а общее количество имеющегося в наличии груза– :
заказы каждого из потребителей (потребности) обозначим соответственно , а общее количество потребностей – :
Тогда при условии
мы имеем закрытую модель, а при условии
– открытую модель транспортной задачи.
Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза , либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены .
Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.
План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок (приложение 1)
Условие или означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное означает количество груза, перевозимого с базы потребителю : совокупность этих величин образует матрицу (матрицу перевозок).
Таким образом, мы видим, что транспортная
задача является задачей линейного
программирования. Для ее решения
применяют также симплекс-
Для контроля надо проверять, равна ли сумма чисел в заполненных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце — потребности заказчика.
При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного и заканчивается в клетке неизвестного , т. е. идет как бы по диагонали таблицы перевозок (приложение 3).
Заполнение таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным . Первая база может полностью удовлетворить потребность первого заказчика . Полагая , вписываем это значение в клетку и исключаем из рассмотрения первый столбец. На базе остается измененный запас . В оставшейся новой таблице с тремя строками и четырьмя столбцами ; северо-западным углом будет клетка для неизвестного . Первая база с запасом может полностью удовлетворить потребность второго заказчика . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения второй столбец. На базе остается новый остаток (запас) . В оставшейся новой таблице с тремя строками и тремя столбцами северо-западным углом будет клетка для неизвестного . Теперь третий заказчик может принять весь запас с базы . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения первую строку. У заказчика из осталась еще не удовлетворенной потребность .
Теперь переходим к заполнению клетки для неизвестного и т.д.
Через шесть шагов у нас останется одна база с запасом груза (остатком от предыдущего шага) и один пункт с потребностью . Соответственно этому имеется одна свободная клетка, которую и заполняем, положив . План составлен. Базис образован неизвестными . Правильность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам7.
Общий
объем перевозок в тонно-
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел и . Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Информация о работе Анализ и принятие решений на основе задач транспортного типа