Автор работы: Пользователь скрыл имя, 03 Ноября 2014 в 07:43, курсовая работа
Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).
Для классической транспортной задачи выделяют два типа задач: критерий стоимости(достижение минимума затрат на перевозку) или расстояний и критерий времени(затрачивается минимум времени на перевозку).
Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).
Введение 4
Часть 1. Транспортная модель закрытого типа 10
1.1 Условие задачи 10
1.2. Построение опорных планов транспортной модели 11
1.2.1. Построение опорного плана методом северо-западного угла 11
1.2.2. Построение опорного плана методом минимальной стоимости 15
1.2.3. Построение опорного плана методом Фогеля 18
1.3. Оптимизация транспортной модели открытого типа 24
1.3.1. Метод потенциала на основе опорного плана, построенного методом северо-западного угла 24
1.3.2. Метод потенциала на основе опорного плана, построенного методом минимальной стоимости 32
1.3.3. Метод потенциала на основе опорного плана, построенного методом Фогеля 39
Часть 2. Транспортная модель открытого типа 41
2.1 Условие задачи 41
2.2. Построение опорных планов транспортной моделия 42
2.2.1. Построение опорного плана методом северо-западного угла 42
2.2.2. Построение опорного плана методом минимальной стоимости 46
2.2.3. Построение опорного плана методом Фогеля 50
2.3. Оптимизация транспортной модели закрытого типа 56
2.3.1. Метод потенциала на основе опорного плана, построенного методом северо-западного угла 56
2.3.2. Метод потенциала на основе опорного плана, построенного методом минимальной стоимости 67
2.3.3. Метод потенциала на основе опорного плана, построенного методом Фогеля. 75
ЗАКЛЮЧЕНИЕ 77
Исходные данные транспортной задачи
Проверим необходимое и достаточное условие разрешимости задачи:
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем фиктивного потребителя с предложением, равным 25. Издержки полагаем равными нулю.
Используя метод северо-западного угла, построю первый опорный план транспортной задачи
План начинается заполняться с верхнего левого угла. В ячейку 11 делаю поставку 95, затем закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 45)
Таблица 45
Выбираю ячейку 12 и делаю поставку 10, закрываю
1 строку, т. к. предложение исчерпано. (Таблица
46)
Таблица 46
Выбираю ячейку 22 и делаю поставку 70, закрываю 2 строку, т.к. предложение полностью исчерпано (Таблица 47)
Таблица 47
Выбираю ячейку 32 и делаю поставку 55, закрываю 2 столбец, т.к. потребности полностью удовлетворены. (Таблица 48)
Таблица48
Выбираю ячейку 33 и делаю поставку
135, закрываю 3 столбец, т.к. потребности
полностью удовлетворены. (Таблица 49)
Таблица49
Выбираю ячейку 34 и делаю поставку
50, закрываю 3 строку, т. к. предложение
исчерпано. (Таблица 49)
Таблица 49
Выбираю ячейку 44 и делаю поставку
60. Делаю поставку 25 в ячейку 45. (Таблица
49)
Таблица 50
Матрица перевозок:
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Значение целевой функции для этого опорного плана равно:
Используя метод минимальной стоимости, построю опорный план транспортной задачи.
Выбираю ячейку 21, т. к. данная ячейка содержит наименьшую транспортную издержку 6, и делаю поставку 70. Затем закрываю 2 строку, т.к. предложение полностью исчерпано. (Таблица 50)
Таблица 50
Выбираю ячейку 44, т. к. данная ячейка содержит наименьшую транспортную издержку 7, и делаю поставку 85. Затем закрываю 4 строку, т. к. предложение полностью исчерпано. (Таблица 51)
Таблица 51
Выбираю ячейку 31, т. к. данная ячейка содержит
наименьшую транспортную издержку 10, и
делаю поставку 25. Затем закрываю 1 столбец,
, т.к. потребности полностью удовлетворены.
(Таблица 52)
Таблица 52
Выбираю ячейку 12, т. к. данная ячейка содержит
наименьшую транспортную издержку 12, и
делаю поставку 105. Затем закрываю 1 строку,
т. к. предложение полностью исчерпано.
(Таблица 53)
Таблица 53
Выбираю ячейку 32, т. к. данная ячейка содержит
наименьшую транспортную издержку 19, и
делаю поставку 30. Затем закрываю 2 столбец,
, т.к. потребности полностью удовлетворены.
(Таблица 54)
Таблица 54
Выбираю ячейку 33, т. к. данная ячейка содержит
наименьшую транспортную издержку 22, и
делаю поставку 135. Затем закрываю 3 столбец,
, т.к. потребности полностью удовлетворены.
(Таблица 55)
Таблица 55
Выбираю ячейку 34, т. к. данная ячейка содержит
наименьшую транспортную издержку 27, и
делаю поставку 25. Делаю поставку 25 ячейку
35. (Таблица 56)
Таблица 56
Матрица перевозок:
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Значение целевой функции для этого опорного плана равно:
Используя метод Фогеля, построю опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найду разности между двумя минимальными тарифами, записанными в данной строке или столбце.
Нахожу разности по строкам:
1 строка: минимальная издержка 12, ближайшая к ней 17.
2 строка: минимальная издежка 6, ближайшая к ней 11.
3 строка: минимальная издежка 10, ближайшая к ней 19.
4 строка: минимальная издежка 7, ближайшая к ней 14.
Нахожу разности по столбцам:
1 столбец: минимальная издержка 6, ближайшая к ней 10.
2 столбец: минимальная издержка 11, ближайшая к ней 12
3 столбец: минимальная издержка 17, ближайшая к ней 20.
4 столбец: минимальная издержка 7, ближайшая к ней 21.
14 – максимальная разность, поэтому выбираю 4 столбец и делаю поставку 85 в ячейку 44 с минимальной издержкой 7. Закрываю 4 строку, т.к. предложение исчерпано. (Таблица 57)
Таблица 57
Нахожу разности по строкам:
1 строка: минимальная издержка 12, ближайшая к ней 17.
2 строка: минимальная издежка 6, ближайшая к ней 11.
3 строка: минимальная издежка 10, ближайшая к ней 19.
Нахожу разности по столбцам:
1 столбец: минимальная издержка 6, ближайшая к ней 10.
2 столбец: минимальная издержка 11, ближайшая к ней 12
3 столбец: минимальная издержка 17, ближайшая к ней 20.
4 столбец: минимальная издержка 21, ближайшая к ней 27.
9 – максимальная разность, поэтому выбираю 3 строку и делаю поставку 95 в ячейку 31 с минимальной издержкой 10. Закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 58)
Таблица 58
Нахожу разности по строкам:
1 строка: минимальная издержка 12, ближайшая к ней 17.
2 строка: минимальная издежка 11, ближайшая к ней 20.
3 строка: минимальная издежка 19, ближайшая к ней 22.
Нахожу разности по столбцам:
2 столбец: минимальная издержка 11, ближайшая к ней 12
3 столбец: минимальная издержка 17, ближайшая к ней 20.
4 столбец: минимальная издержка 21, ближайшая к ней 27.
9 – максимальная разность, поэтому выбираю 2 строку и делаю поставку 70 в ячейку 22 с минимальной издержкой 11. Закрываю 2 строку, т.к. предложение исчерпано. (Таблица 59)
Таблица 59
Нахожу разности по строкам:
1 строка: минимальная издержка 12, ближайшая к ней 17.
3 строка: минимальная издежка 19, ближайшая к ней 22.
Нахожу разности по столбцам:
2 столбец: минимальная издержка 12, ближайшая к ней 19
3 столбец: минимальная издержка 17, ближайшая к ней 22.
4 столбец: минимальная издержка 21, ближайшая к ней 27.
7 – максимальная разность, поэтому выбираю 2 столбец и делаю поставку 65 в ячейку 12 с минимальной издержкой 12. Закрываю 2 столбец, т.к. потребности удовлетворены. (Таблица 60)
Таблица 60
Нахожу разности по строкам:
1 строка: минимальная издержка 17, ближайшая к ней 21.
3 строка: минимальная издежка 22, ближайшая к ней 27.
Нахожу разности по столбцам:
3 столбец: минимальная издержка 17, ближайшая к ней 22
4 столбец: минимальная издержка 21, ближайшая к ней 27.
6 – максимальная разность, поэтому выбираю 4 столбец и делаю поставку 25 в ячейку 14 с минимальной издержкой 21. Закрываю 4 столбец, т.к. потребности удовлетворены. (Таблица 61)
Таблица 61
Выбираю ячейку 13 с минимальной транспортной
издержкой 17 и делаю поставку 15. В ячейку
с издержкой 22 делаю поставку 120 и в ячейку
35 делаю поставку 25. (Таблица 62)
Таблица 62
Матрица перевозок:
В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Значение целевой функции для этого опорного плана равно:
Проверю опорный план (таблица 63) на вырожденность: всего заполненных клеток:
имею заполненных клеток: 8, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.
Таблица 63
Проверю оптимальность опорного плана.
Найду предварительные потенциалы и по занятым
клеткам таблицы, в которых , полагая, что.(Таблица
64)
Таблица 64
Работаю с пустыми клетками (Таблица 65)
Таблица 65
Так как существуют ∆C_ij<0, то опорный план неоптимальный.
Перепланировка опорного плана
Выбираю клетку 35 с минимальной разностью -20. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. (Таблица 66)
Таблица 66
Среди отрицательных вершин выбираю наименьшую
поставку 25. Эту поставку прибавляю к поставкам
с положительной вершиной и отнимаю
от поставок с отрицательной вершиной.
Выбранную минимальную поставку зануляю,
а в пустую клетку записываю минимальную
поставку. (Таблица 67)
Таблица 67
S1 (8290 )>S2, из этого следует, что оптимизация прошла успешно
Проверю оптимальность опорного плана. (Таблица 68)
Таблица 68
Работаю с пустыми клетками (Таблица 69)
Таблица 69
Так как существуют ∆C_ij<0, то опорный план неоптимальный.
Перепланировка опорного плана
Выбираю клетку 31 с минимальной разностью -14. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 55. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 70)