Автор: Пользователь скрыл имя, 17 Апреля 2012 в 20:51, курсовая работа
Цели работы: изучить методы решения транспортной задачи и их реализацию при решении практической задачи.
Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок”. В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование" здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского.
Введение
Транспортная задача
Математическая модель
Постановка классической транспортной задачи
Способы составления первого допустимого плана перевозок
Способ северо-западного угла
Способ наименьшего элемента в матрице
Способ двойного предпочтения
Способ аппроксимации Фогеля
Решение транспортных задач, имеющих некоторые дополнительные условия
Задача с распределением резерва (спрос не равен предложению)
Запрещение корреспонденции
Обязательная (директивная) корреспонденция
Открытая модель распределительного метода
Признаки наличия альтернативных решений в различных способах распределительного метода
Закрепление потребителей за поставщиками неоднородного взаимозаменяемого продукта
Усложнённая задача перевозки разнородной продукции
Транспортная задача по критерию времени
Заключение
Использованная литература
Расстояния (элементы целевой матрицы) между потребителями и возможными местами добычи песка указаны в правых верхних углах клеток табл. 7 .Сколько в каждой точке нужно добывать песка и как спланировать грузопотоки, чтобы транспортная работа была оптимальной?
Таблица 7
Возможные поставщики песка |
Потребители песка |
Запасы, т | ||||
B1 |
B2 |
B3 |
B4 |
B5 | ||
|
A1 |
2 |
4 |
6 |
3 |
4 |
-- |
A2 |
5 |
3 |
8 |
5 |
4 |
-- |
A3 |
3 |
1 |
4 |
5 |
3 |
-- |
Потребность, т |
300 |
200 |
400 |
250 |
400 |
1550 |
Переносим ограничения спроса по столбцам в клетки с минимальными расстояниями А1В1, А3В2, А3В3, А1В4, А3В5. Таким образом, эти клетки получают загрузку в 300 т, 200 т, 400 т, 250 т и 400 т (табл. 8).
Таблица 8
Возможные поставщики песка |
Потребители песка |
Запасы, т | ||||
B1 |
B2 |
B3 |
B4 |
B5 | ||
|
A1 |
2 300 |
4 |
6 |
3 250 |
4 |
550 |
A2 |
5 |
3 |
8 |
5 |
4 |
-- |
A3 |
3 |
1 200 |
4 400 |
5 |
3 400 |
1000 |
Потребность, т |
300 |
200 |
400 |
250 |
400 |
1550 |
Поскольку загружались клетки с оптимальным значением элемента целевой матрицы, то полученное решение с точки зрения транспортной работы будет оптимальным. При этом добыча песка в точках А1 и А2 должна быть соответственно 550 и 1000 т. В точке А2 добычу вести нерационально.
Открытая модель распределительного метода встречается при решении задач определения оптимального размещения и мощности АТП, закрепления маршрутов за АТП, размещения и ёмкости складов и т.д.
13.5 Признаки наличия альтернативных решений в различных способах распределительного метода
Для задачи, условия которой записаны в табл. 7, пользуясь методом МОДИ, найдем оптимальное решение (табл. 8). Объем грузовой работы при оптимальном решении равен 11 200 т•км.
Однако в этой задаче имеется другое базисное оптимальное решение с точно таким же объёмом грузовой работы, но другим вариантом грузопотоков. Оно получится, если загрузить клетку А1В3, перераспределив загрузку в клетках А1В4 , А3В3 и А3В4, учитывая ограничения по спросу и предложению (табл. 9). Следовательно, имеются два базисных оптимальных решения (табл. 8 и 9).
Переместив 400 т груза из клетки А3В3 в ранее свободную клетку А1В3 и из клетки А1В4 - в клетку А3В4, получим другой вариант оптимального решения (другой базис). При этом от первого перемещения было получено сокращение грузооборота на 400•2 = 800 т•км, от второго - увеличение на 800 т•км, т.е. грузооборот остался прежним, а грузопотоки изменились. Потенциалы и их суммы для всех клеток матрицы одинаковы.
Сохранить неизменными в табл. 10 потенциалы позволило то обстоятельство, что в свободной клетке А1В3 табл. 9 сумма потенциалов равна элементу целевой функции. Это же мы замечаем и для клетки А1В4 в табл. 9.
Таблица 9
Возможные поставщики |
Потенциалы |
Грузопоглощающие точки |
Итого по вывозу, т | |||
B1 |
B2 |
B3 |
B4 | |||
2 |
-2 |
8 |
6 | |||
A1 |
-2 |
16 |
6 |
6 |
4 400 |
400 |
A2 |
4 |
8 |
2 400 |
12 200 |
14 |
600 |
A3 |
3 |
2 200 |
18 |
8 600 |
6 200 |
1000 |
Потребность, т |
200 |
400 |
800 |
600 |
1550 | |
Таблица 10
Возможные поставщики |
Потенциалы |
Грузопоглощающие точки |
Итого по вывозу, т | |||
B1 |
B2 |
B3 |
B4 | |||
2 |
-2 |
8 |
6 | |||
A1 |
-2 |
16 |
6 |
6 400 |
4 |
400 |
A2 |
4 |
8 |
2 400 |
12 200 |
14 |
600 |
A3 |
0 |
2 200 |
18 |
8 600 |
6 200 |
1000 |
Потребность, т |
200 |
400 |
800 |
600 |
1550 | |