РОСЖЕЛДОР
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
«Ростовский государственный университет путей сообщения»
(ФГБОУ ВПО РГУПС)
Линденбаум М.Д.
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ НА ТРАНСПОРТЕ
Оптимизация транспортной системы и динамическое распределение ресурствов
Методические указания
Ростов-на-Дону
Лабораторная работа
Оптимизация транспортной системы
В регионе работают пять комбинатов по производству однотипной продукции и четыре потребителя этой продукции. Определить оптимальный план прикрепления комбинатов к потребителям, доставляющий минимум приведенных транспортных издержек. Данные об объемах выпуска продукции комбинатами, потребностях потребителей, а также транспортных издержках на перевозку единицы продукции приводятся в таблице 1.
На направлениях A 3® B 2 и A 4® B 4 существуют ограничения пропускной способности в количествах q 3,2 = 10 и q 4,4 = 15 соответственно.
Проверить имеет ли задача правильный баланс, если нет, то привести ее к правильному балансу одним из способов, описанных в п. 1.3., в соответствии с вариантом задания (см. таблицу № 2). Преобразовать транспортную таблицу с учётом ограничений методом, изложенным в п. 1.3. Решить задачу методом потенциалов (п. 1.1.) или с помощью Microsoft Excel (п. 1.4.), проанализировать результаты, сделать выводы.
Таблица1
Исходные данные
Комбинаты | Потребители | Объемы поставок | |||
B 1 | B 2 | В 3 | B 4 | ||
A 1 | 8 | 10+ S 1 | 14 | 13 | |
A 2 | 10+ S 1 | 25 | 20 | 15 | |
A 3 | 10 | (10) 3 | 13 | 18 | |
A 4 | 40 | 30 | 18 | (15) 2 | |
A 5 | 9 | 15 | 8 | 25 | 30+10 × S 2 |
Объемы потребности | 80+10 × S 2 |
S 1 – предпоследняя цифра шифра; S 2 – последняя цифра шифра.
Таблица 2
S 1+ S 2 = 1, 4, 7, 10,13,16,19 | Вводится фиктивный пункт отправления Аn+ 1, cn+ 1 ,j = 0, 1 £ j £ m | ||
S 1+ S 2 = 2, 5, 8, 11, 14, 17 | Вводится коэффициент пропорциональногоуменьшения заявок d | ||
S 1+ S 2 = 3, 6, 9, 12, 15, 18 | Вводится фиктивный пункт отправления Аn+ 1, cn+ 1, j – потери от недопоставки единицы продукта | ||
c 6,1 | c 6,2 | c 6,3 | c 6,4 |
35 | 44 | 16 | 28 |
Оптимальное распределение ресурсов
Для развития двух направлений транспортной сети A 3® B 2 и A 4® B 4 выделены средства в количестве
K 0=12+ F
(F - число букв в фамилии). В течении четырех месяцев (m =4) распределить выделенные средства так, чтобы суммарный прирост пропускной способности был максимальным. Известно, что рост пропускной способности от вложения Xi единиц средств в первое направление (A 3® B 2) равен
f (Xi) = a×Xi,
а от вложения Y i единиц средств во второе направление (A4®B4) –
g (Yi) = b×Y i.
Остаток средств в конце месяца для первого направления равен
j(Xi) = a ×Xi,
а для второго направления
y(Yi) = b ×Yi.
Решить задачу методом динамического программирования (п. 2.2.), проанализировать результаты, сделать выводы. Варианты заданий приведены в таблице. Варианты заданий выбираются из таблицы 3 по числу из двух последних цифр шифра.
Таблица 3
Вари- ант | a | b | a | b | Вари- ант | a | b | a | b |
1,9 | 0,6 | 0,50 | 0,90 | 1,8 | 0,8 | 0,30 | 0,85 | ||
0,7 | 1,8 | 0,85 | 0,45 | 0,5 | 1,1 | 0,80 | 0,30 | ||
1,1 | 0,4 | 0,40 | 0,90 | 1,7 | 0,7 | 0,50 | 0,95 | ||
0,8 | 1,9 | 0,90 | 0,50 | 0,7 | 1,9 | 0,95 | 0,35 | ||
2,0 | 1,0 | 0,35 | 0,80 | 1,1 | 0,5 | 0,50 | 0,85 | ||
0,4 | 1,1 | 0,95 | 0,35 | 0,6 | 1,4 | 0,95 | 0,35 | ||
2,2 | 0,9 | 0,40 | 0,90 | 1,6 | 0,7 | 0,45 | 0,90 | ||
0,5 | 1,3 | 0,85 | 0,35 | 0,7 | 2,0 | 0,95 | |||
1,3 | 0,6 | 0,40 | 0,90 | 1,5 | 0,9 | 0,50 | 0,95 | ||
0,9 | 1,9 | 0,85 | 0,30 | 0,9 | 1,8 | 0,85 | 0,35 | ||
2,1 | 0,7 | 0,35 | 0,95 | 2,1 | 0,9 | 0,50 | 0,95 | ||
0,6 | 1,8 | 0,85 | 0,35 | 0,7 | 1,6 | 0,95 | 0,35 | ||
2,0 | 0,9 | 0,40 | 0,80 | 1,5 | 0,8 | 0,30 | 0,95 | ||
0,6 | 1,9 | 0,90 | 0,35 | 0,8 | 2,1 | 0,90 | 0,40 | ||
2,0 | 0,8 | 0,50 | 0,95 | 1,6 | 0,7 | 0,50 | 0,85 | ||
0,8 | 1,8 | 0,85 | 0,40 | 0,8 | 1,5 | 0,90 | 0,50 | ||
1,2 | 0,7 | 0,35 | 0,90 | 1,4 | 0,6 | 0,50 | 0,90 | ||
0,6 | 1,1 | 0,95 | 0,45 | 0,8 | 1,7 | 0,90 | 0,30 | ||
1,8 | 0,8 | 0,55 | 0,95 | 1,6 | 0,8 | 0,45 | 0,85 | ||
1,0 | 1,9 | 0,80 | 0,30 | 0,8 | 1,8 | 0,85 | 0,35 | ||
1,5 | 0,7 | 0,35 | 0,90 | 2,1 | 1,0 | 0,50 | 0,90 | ||
0,5 | 1,2 | 0,95 | 0,55 | 0,9 | 2,0 | 0,90 | 0,50 | ||
1,5 | 0,6 | 0,40 | 0,90 | 1,9 | 0,9 | 0,35 | 0,90 | ||
0,6 | 1,2 | 0,90 | 0,50 | 0,6 | 1,6 | 0,95 | 0,40 | ||
1,7 | 0,8 | 0,35 | 0,95 | 1,6 | 0,9 | 0,50 | 0,95 | ||
0,8 | 2,0 | 0,85 | 0,25 | 0,9 | 1,8 | 0,85 | 0,45 | ||
2,2 | 1,0 | 0,40 | 0,95 | 1,7 | 0,6 | 0,30 | 0,95 | ||
0,7 | 1,3 | 0,95 | 0,30 | 1,1 | 2,1 | 0,90 | 0,35 | ||
1,6 | 0,6 | 0,35 | 0,90 | 1,3 | 0,6 | 0,45 | 0,90 | ||
0,9 | 1,7 | 0,95 | 0,40 | 1,0 | 2,2 | 0,90 | 0,35 | ||
1,4 | 0,8 | 0,50 | 0,90 | 1,7 | 0,8 | 0,40 | 0,90 | ||
0,9 | 1,6 | 0,85 | 0,35 | 0,7 | 1,3 | 0,95 | 0,50 | ||
2,0 | 0,7 | 0,35 | 0,85 | 1,8 | 0,9 | 0,40 | 0,90 | ||
0,9 | 1,7 | 0,85 | 0,30 | 0,8 | 1,6 | 0,95 | 0,50 | ||
1,8 | 0,7 | 0,40 | 0,90 | 1,5 | 0,7 | 0,35 | 0,80 | ||
0,7 | 1,5 | 0,95 | 0,50 | 0,9 | 2,2 | 0,85 | 0,30 | ||
1,3 | 0,5 | 0,40 | 0,80 | 1,9 | 0,8 | 0,40 | 0,95 | ||
0,7 | 1,7 | 0,90 | 0,40 | 0,7 | 1,4 | 0,85 | 0,50 | ||
1,4 | 0,6 | 0,30 | 0,90 | 2,1 | 0,8 | 0,45 | 0,95 | ||
0,6 | 1,7 | 0,85 | 0,45 | 0,8 | 1,5 | 0,85 | 0,45 | ||
2,2 | 0,8 | 0,40 | 0,85 | 1,3 | 0,7 | 0,35 | 0,85 | ||
0,6 | 1,5 | 0,85 | 0,30 | 0,7 | 1,2 | 0,85 | 0,45 | ||
1,4 | 0,7 | 0,25 | 0,90 | 1,1 | 0,6 | 0,40 | 0,85 | ||
1,1 | 2,2 | 0,95 | 0,55 | 0,6 | 1,3 | 0,95 | 0,50 | ||
1,9 | 0,7 | 0,40 | 0,85 | 1,2 | 0,6 | 0,35 | 0,85 | ||
0,8 | 1,4 | 0,95 | 0,45 | 1,0 | 2,0 | 0,95 | 0,30 | ||
1,9 | 1,0 | 0,40 | 0,90 | 1,8 | 0,6 | 0,45 | 0,90 | ||
1,0 | 2,1 | 0,90 | 0,45 | 0,7 | 1,4 | 0,80 | 0,40 | ||
1,2 | 0,5 | 0,25 | 0,90 | 1,7 | 0,9 | 0,35 | 0,90 | ||
0,9 | 1,5 | 0,90 | 0,35 | 0,9 | 2,1 | 0,90 | 0,45 |
ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ
1. Проверить имеет ли задача правильный баланс, если нет, то привести ее к правильному балансу.
2. Решить транспортную задачу на ЭВМ. Вначале задача решается без учета ограничений пропускной способности, затем с учетом пропускной способности на направлениях A 3® B 2 и A 4® B 4(q 3,2=10, q 4,4=15). Проанализировать результаты, сделать выводы.
3. Решить задачу оптимального распределения ресурсов методом динамического программирования.
4. Решить третий раз на ЭВМ транспортную задачу с увеличенными пропускными способностями на направлениях A 3® B 2 и A 4® B 4:
q 3,2*= q 3,2+ f (х сумм), q 4,4*= q 4,4+ g (у сумм).
Проанализировать результаты, сделать выводы.
5. Рассчитать срок окупаемости капиталовложений в развитие направлений A 3® B 2 и A 4® B 4
T 0 = 1000 K 0/(W - W *),
где W - общие транспортные издержки до увеличения пропускных способностей; W * - общие транспортные издержки после увеличения пропускных способностей.
7. Сделать общие выводы по работе.
СОДЕРЖАНИЕ ОТЧЁТА
Отчёт должен содержать цель работы, номер варианта (последние две цифры шифра). В отчёте должны быть представлены исходная таблица, преобразованная таблица, приведенная к балансному условию по заданной стратегии и с учётом ограничений по пропускной способности направлений A 3® B 2 и A 4® B 4. В таблицах следует привести оптимальный план перевозок и выводы о недопоставках. Следует привести исходные данные и решение динамической задачи распределения ресурсов на увеличение пропускной способности направлений A 3® B 2 и A 4® B 4, проверку полученного решения. После увеличения пропускной способности привести исходную и преобразованную таблицы с оптимальным планом перевозок и выводами о недопоставках. Привести расчёт срока окупаемости капиталовложений и вывод о их целесообразности.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к лабораторной работе №1
1. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
1.1. Общее решение
Постановка задачи
Имеется n – пунктов отправления: A1, A2,…, Ai,…, An, в которых имеются однотипные продукты в количествах: a1, a2,…, ai,…, an, и m-пунктов назначения B1, B2,…, Bj,…, Bm с потребностями в продуктах (заявками) в количествах b1, b2,…, bj,…, bm. Все пункты отправления и пункты назначения связаны между собой транспортной сетью. Транспортные издержки задаются в виде матрицы
где ci,j – затраты на перевозку единицы продукта из пункта Ai в пункт Bj.
Задача относится к линейному программированию, так как линейна целевая функция W и линейны все ограничения области допустимых решений (ОДР).
Решением задачи является оптимальный план перевозок в виде матрицы
где хi,j – объём перевозки из пункта Ai в пункт Bj.