Автор работы: Пользователь скрыл имя, 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
Таблица 70
S2 (7790 )>S3, из этого следует, что оптимизация прошла успешно
Проверю оптимальность опорного плана. (Таблица 71)
Таблица 71
Работаю с пустыми клетками (Таблица 72)
Таблица 72
Так как существуют ∆C_ij<0, то опорный план неоптимальный.
Перепланировка опорного плана
Выбираю клетку 14 с минимальной разностью -13. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 25. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 73)
Таблица 73
S3 (7020 )>S4, из этого следует, что оптимизация прошла успешно
Проверю оптимальность опорного плана. (Таблица 74)
Таблица 74
Работаю с пустыми клетками (Таблица 75)
Таблица 75
Так как существуют ∆C_ij<0, то опорный план неоптимальный.
Перепланировка опорного плана
Выбираю клетку 13 с минимальной разностью -12. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 25. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 76)
Таблица 76
Проверю оптимальность опорного плана. (Таблица 77)
Таблица 77
Работаю с пустыми клетками (Таблица 78)
Таблица 78
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию.
Минимальные затраты составят: 6515 у.е.
Проверю опорный план (таблица 79) на вырожденность: всего заполненных клеток:
имею заполненных клеток: 8, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.
Таблица 79
Проверю оптимальность опорного плана. (Таблица 80)
Таблица 80
Работаю с пустыми клетками (Таблица 81)
Таблица 81
Так как существуют ∆C_ij<0, то опорный план неоптимальный.
Перепланировка опорного плана
Выбираю клетку 22 с минимальной разностью -4. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 30. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 82)
Таблица 82
S1 (6740 )>S2, из этого следует, что оптимизация прошла успешно
Проверю оптимальность опорного плана. (Таблица 83)
Таблица 83
Работаю с пустыми клетками. (Таблица 84)
Таблица 84
Так как существуют ∆C_ij<0, то опорный план неоптимальный.
Перепланировка опорного плана
Выбираю клетку 14 с минимальной разностью -3. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 25. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 85)
Таблица 85
S2 (6620 )>S3, из этого следует, что оптимизация прошла успешно
Проверю оптимальность опорного плана. (Таблица 85)
Таблица 85
Работаю с пустыми клетками. (Таблица 86)
Таблица 86
Так как существуют ∆C_ij<0, то опорный план неоптимальный.
Перепланировка опорного плана
Выбираю клетку 13 с минимальной разностью -2. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 30. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 87)
Таблица 87
Проверю оптимальность опорного плана. (Таблица 88)
Таблица 88
Работаю с пустыми клетками. (Таблица 89)
Таблица 89
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию .
Минимальные затраты составят:
Проверю опорный план (таблица 90) на вырожденность: всего заполненных клеток:
имею заполненных клеток: 8, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.
Таблица 90
Проверю оптимальность опорного плана. (Таблица 91)
Таблица 91
Работаю с пустыми клетками. (Таблица 92)
Таблица 92
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию .
Минимальные затраты составят:
Транспортые задачи закрытого типа
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 2-й магазин (90), в 4-й магазин (15)
Из 2-го склада необходимо весь груз направить в 2-й магазин
Из 3-го склада необходимо груз направить в 1-й магазин (95), в 3-й магазин (135), в 4-й магазин (10)
Из 4-го склада необходимо весь груз направить в 4-й магазин
Транспортые задачи открытого типа
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 2-й магазин (65), в 3-й магазин (15), в 4-й магазин (25)
Из 2-го склада необходимо весь груз направить в 2-й магазин
Из 3-го склада необходимо груз направить в 1-й магазин (95), в 3-й магазин (120)
Из 4-го склада необходимо весь груз направить в 4-й магазин
На 3-ом складе остался невостребованным груз в количестве 25 ед.
Оптимальный план является вырожденным, так как базисная переменная .
1. Шапкин А. С. Математические методы и модели исследования операций
[Текст] : учебник / А. С. Шапкин, Н. П. Мазаева. – М. : Издательско-торговая
корпорация «Дашков и Ко», 2004. – 400 с., С. 119 – 146.
2. Кремер, Н. Ш. Исследование операций в экономике [Текст] : учебное по-
собие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман;
под ред. Н. Ш. Кремера. – М. : ЮНИТИ, 2003. – 407 с., С. 123 – 153.
3. Кузнецов, Б. Т. Математические методы и модели исследования опера-
ций [Текст] : учебное пособие / Б. Т. Кузнецов. – М. : ЮНИТИ-ДАНА, 2005. –
390 с., С. 103 – 129.
4. Хазанова, Л. Э. Математическое моделирование в экономике [Текст] :
учебное пособие / Л. Э. Хазанова. – М. : Издательство БЕК, 1998. – 141 с., С. 45
– 76.