- •Содержание
- •Глава 1. Постановка транспортных задач 6
- •Глава 2. Определение оптимального плана транспортных задач 28
- •Введение
- •Глава 1.Постановка транспортных задач
- •1.1.Однопродуктовая транспортная модель
- •1.2.Многопродуктовая транспортная модель
- •1.3.Модель производства с запасами
- •1.4. Методы построения опорного плана
- •1.4.1. Метод северо-западного угла
- •1.4.2.Метод минимальной стоимости
- •1.4.3.Метод двойного предпочтения
- •1.4.4.Приближенный метод Фогеля
- •Глава 2.Определение оптимального плана транспортных задач
- •2.1.Решение транспортной задачи методом моди
- •2.2.Дельта-метод решения транспортной задачи
- •2.3.Решение задач закрепления потребителей за поставщиками и клиентуры за автотранспортными предприятиями с учетом дополнительных требований
- •2.3.1.Ограничения в поставках
- •2.3.2.Несбалансированное наличие и потребности
- •2.3.3.Задача закрепления при учете взаимозаменяемости автомобилей
- •2.3.4.Задача на минимизацию времени доставки груза
- •Глава 3.Задача о назначениях
- •3.1.Постановка задачи о назначениях
- •3.2.Венгерский метод решения задачи о назначениях
- •3.3.Применение задачи о назначениях к решению экономических проблем
- •Глава 4.Оптимальное планирование грузооборота
- •4.1.Транспортная сеть и характеристика перевозимых грузов
- •Объёмы потребления грузов
- •Объёмы производства песка
- •4.2.Оптимальное планирование грузоперевозок
- •4.3.Маршрутизация перевозок грузов при помашинных отправках
- •4.4.Составление кольцевых и маятниковых маршрутов
- •Глава 5.Оптимальное планирование работы автобусного парка
- •5.1.Постановка задачи
- •5.2.Двойственная задача линейного программирования
- •5.3. Примеры формулировок двойственных задач
- •5.4. Симметричная и несимметричная двойственные пары. Основы теории двойственности
- •Основная теорема теории двойственности
- •5.5. Условия равновесия в симметричной паре. Экономическая интерпретация
- •5.6.Решение задачи оптимального планирования работы автопарка
- •Глава 6.Область применения сетевых транспортных задач
- •6.1.Примеры применения модели о кратчайшем пути
- •6.2.Алгоритмы нахождения кратчайшего пути
- •6.2.1.Алгоритм для сетей без циклов
- •6.2.2.Алгоритм для сетей с циклами
- •6.2.3.Алгоритм Флойда
- •6.3.Алгоритм нахождения максимального потока в сети
- •6.4.Представление сетевых задач как задач линейного программирования
- •Глава 7.Применение сетевых моделей в транспортировке грузов
- •7.1. Определение кратчайших расстояний между пунктами транспортной сети
- •7.2. Решение задачи коммивояжера методом "ветвей и границ"
- •7.3. Определение развозочных маршрутов для перевозки мелких партий грузов
- •7.3.1. Нахождение кратчайшей связывающей все пункты сети и набор пунктов в маршруты
- •7.3.2. Определение очередности объезда пунктов маршрута
- •Матрица кратчайших расстояний 2-го маршрута
- •7.4. Определение развозочных маршрутов для мелких партий грузов методом Кларка Райта
- •Список литературы
1.2.Многопродуктовая транспортная модель
Фирма производит автомобили четырех различных марок, которые для простоты будем обозначать как М1, М2, М3,М4. Завод в Детройте выпускает автомобили марок М1, М2, М4. В Новом Орлеане производятся только автомобили марок М1, М2. Завод в Лос-Анджелесе выпускает автомобили марок М3, М4. В таблице 6 указаны объем выпуска разных заводов и величина спроса в центрах распределения для автомобилей каждой марки.
Таблица 6
|
Марка |
Всего |
|||
М1 |
М2 |
М3 |
М4 |
||
Завод |
|||||
Лос-Анджелес |
‑ |
‑ |
700 |
300 |
1000 |
Детройт |
500 |
600 |
‑ |
400 |
1500 |
Новый-Орлеан |
800 |
400 |
‑ |
‑ |
1200 |
Центр распределения |
|||||
Денвер |
700 |
500 |
500 |
600 |
2300 |
Майами |
600 |
500 |
200 |
100 |
1400 |
В целях упрощения вычислений предположим, что стоимость перевозки автомобиля любой марки на одну милю по-прежнему равна 8 центам. Для того чтобы учесть многопродуктовый характер задачи, изменим транспортную модель следующим образом. Вместо того, чтобы рассматривать каждый завод как один исходный пункт, разобьем его на несколько пунктов в соответствии с числом марок автомобилей, выпускаемых этим заводом. Аналогично поступим и с пунктами назначения, т.е. будем считать, что каждый из них состоит их четырех станций, соответствующих четырем маркам автомобилей.
Рис. 1.2. Многопродуктовая транспортная модель
В результате получим семь исходных пунктов и восемь пунктов назначения. Модель изображена на рис. 1.2 и в виде транспортной таблицы (см. табл. 7). Заметим, что некоторые маршруты недопустимы, поскольку в данной постановке задачи автомобили различных марок не могут заменять друг друга. Например, нельзя осуществлять перевозки из пункта производства автомобилей марки М1 в пункт доставки автомобилей марки М4. На рис 1.2 запрещенным маршрутам соответствует отсутствие дуги. Этим маршрутам в табл. 7 приписана очень высокая стоимость перевозки M>>1 («>>» - много больше). Если внимательно изучить таблицу, то можно заметить, что на самом деле задачу не обязательно описывать одной моделью.
Таблица 7
|
Денвер
|
М айами |
|
||||||
|
М1 |
М2 |
М3 |
М4 |
М1 |
М2 |
М3 |
М4 |
|
М3 |
М |
М |
80 |
М |
М |
М |
215 |
М |
700 |
М4 |
М |
М |
М |
80 |
М |
М |
М |
215 |
300 |
М1 |
100 |
М |
М |
М |
108 |
М |
М |
М |
500 |
М2 |
М |
100 |
М |
М |
М |
108 |
М |
М |
600 |
М4 |
М |
М |
М |
100 |
М |
М |
М |
108 |
400 |
М1 |
102 |
М |
М |
М |
68 |
М |
М |
М |
800 |
М2 |
М |
102 |
М |
М |
М |
68 |
М |
М |
400 |
|
700 |
500 |
500 |
600 |
600 |
500 |
200 |
100 |
|
В силу независимости поставок можно было бы представить задачу по каждой марке автомобилей в виде отдельной таблицы перевозок, но только существенно меньшего размера. Табл. 7 можно разбить на четыре самостоятельные транспортные таблицы (табл. 8-11).
Рассмотрение этих четырех транспортных моделей дает решение, совпадающее с оптимальным решением задачи, соответствующей табл. 7.
С вычислительной точки зрения небольшие подзадачи (см. табл. 8-11) решить существенно быстрее, чем одну сложную задачу, представленную в табл. 7. Если бы между марками существовала связь (например, одну из них можно бы было заменять другой), то в общем случае исходную модель не удалось бы разбить на отдельные задачи.
Таблица 8 Марка М1
|
Таблица 9 Марка М2
|
|||||||||||||||||||||||||||||||||
Таблица 10 Марка М3
|
Таблица 11 Марка М4
|