Практическое занятие № 7 Оптимизация задач транспортного типа

7.1. Цель занятия

Целью занятия является ознакомление с возможностями применения современных технологических инструментов мониторинга и оптимизации для решения актуальных задач транспортной логистики. Предлагается использовать стандартный математический аппарат пакета MS Office, который хорошо знаком студентам и имеет широкое распространение среди современных пользователей компьютеров. Табличный процессор MS Excel позволяет решать транспортные задачи разной степени сложности, разного экономического смысла и содержания не требуя от пользователя специальных знаний из области математического программирования.

На практическом занятии с помощью инструментального средства «Поиск решения» табличного процессора MS Excel моделируются задачи:

- оптимальной маршрутизации доставки грузов,

- оптимизации движения материальных потоков к потребителям строго по графику в установленное время;

- задачи оптимального распределения работ, которые необходимо выполнить коллективу бригады;

- задачи оптимизации распределения капитала между различными объектами инвестиций.

Практическое занятие знакомит студентов с возможностями, которые открывает применение инструментария «Поиск решения» для оперативного решения актуальных задач транспортной логистики, для анализа полученных по разным критериям оптимизации результатов, для мониторинга тенденций в любой логистической схеме. Кроме того, студенты получают практические навыки работы с данным инструментарием, овладевают технологией подготовки и реализации оптимизационных задач в среде MS Excel.

7.2. Оптимизация транспортных перевозок

В разных экономических моделях в качестве оптимального принимается план действий (производства, транспортировки, маршрутизации, распределения работ и инвестиций и т.п.), который обеспечивает искомый оптимальный результат при соблюдении заданных условий. В моделях транспортных задач, образующих наиболее широкий класс задач линейного программирования, реализуется поиск оптимального (в соответствии с тем или иным критерием) плана перевозок грузов из пунктов отправления в заданные пункты получения.

Различают два типа транспортных задач: по критерию стоимости и по критерии времени. На практике в большинстве случаев критерий стоимости является главным, определяющим эффективность плана перевозок. Однако, если в задаче речь идет о перевозках скоропортящихся продуктов, или о подвозе грузов в места техногенных или природных катастроф, о подвозе боеприпасов к местам боевых действий, то доминирующим фактором становится не стоимость перевозок, а время, в течение которого все перевозки будут завершены.

Общая постановка транспортной задачи по критерию стоимости такова.

В m пунктах отправления находятся а₁, а₂, .., а_m единиц однородного груза (ресурсы), которые должны быть доставлены в n заданных пунктов назначения (потребления), соответственно, в количестве b₁, b₂,…,b_n единиц (потребность). Стоимость перевозок (тарифы) единицы груза из i-го пункта отправления в j-й пункт назначения равняется С_ij, а соответствующее количество единиц перевезенного груза равно x_ij (i = 1, 2, 3… m; j = 1, 2, 3,… n). Необходимо составить такой план перевозок, при котором их общая стоимость была бы минимальной, т.е. необходимо определить, сколько единиц груза должно быть отправлено с любого i -го пункта отправления в какой-либо j-й пункт назначения так, чтобы максимально удовлетворить потребности, и чтобы суммарные затраты на перевозку были минимальными.

Матрицы, образованные значениями переменных x_ij и коэффициентами С_ij называют соответственно планом перевозок и матрицей транспортных затрат

, ,

Задача 1. Имеются поставщики продукции, продукция которых хранится на трех складах. Ее нужно доставить потребителям в три магазина. Даны объемы потребностей для каждого магазина b_i , и объемы запасов на каждом складе a_j, а также матрица тарифов перевозок C_ij. Нужно составить такой план перевозок, который минимизировал бы суммарные транспортные расходы и обеспечивал вывоз с каждого склада продукции и удовлетворение потребностей каждого магазина. Зоны данных для построения модели оптимизации транспортных перевозок (табл. 7.1)

Таблица 7.1 - Зоны данных для оптимизации транспортных перевозок

	Магазин 1	Магазин 2	Магазин 3
Потребители bi	220	170	110	Поставщики aj
Стоимость перевозок (Сij)
Склад 1	3	1	2	180
Склад 2	2	1	4	205
Склад 3	3	6	5	160
Ограничения	220	170	110

Математическая модель оптимизации транспортных перевозок

Целевая функция: С = ∑ ∑ x_ij * c_ij→ min

Ограничения: ∑ x_ij = bi ; ∑ x_ij = aj, i, j = 1, 2, 3;

x_ij – целые; x_ij > 0

Технология подготовки решения задачи в программной среде Excel

1. Запускаем Excel. В ячейки Рабочего листа (см. рис.7.1) заносим: в диапазон клеток B9:D12 – исходные данные C_ij - стоимость перевозки единицы груза между заданными пунктами;

Ограничения по поставкам – диапазон клеток Е3:Е 5 и ограничения по потребностям - В14: D14.

2. Выделяем ячейки искомой матрицы перевозок - В3:D5 – зона искомых переменных x_ij, которым первоначально присваиваем нулевые значения.

3. Ячейка Е13 – зона целевой функции С, заносим туда функцию Excel: =СУММПРОИЗВ($B$3:$D$5;$B$9:$D$11)

4. B16: D16 и G3:G5 – зоны расчетных ограничений, заносим туда соответственно формулы Excel

→ G3 = СУММПРОИЗВ($B$3:$D$3;$B$9:$D$9)

→ G4 = СУММПРОИЗВ($B$4:$D$4;$B$10:$D$10)

→ G5 = СУММПРОИЗВ($B$5:$D$5;$B$11:$D$11)

→ В16 = СУММПРОИЗВ($B$3:$В$3;$B$9:$В$11)

→ С16 = СУММПРОИЗВ($С$3:$С$5;$С$9:$С$11)

→ D16 = СУММПРОИЗВ($D$3:$D$5;$D$9:$D$11)

Картина расположения на всех указанных выше зон на Рабочем листе MS Excel: зоны искомых переменных – матрица объемов транспортных перевозок, зоны ограничений, зоны исходных данных – матрица стоимости перевозки единицы продукции, зоны целевой функции имеет вид (см. Рис.7.1)

Рисунок 7.1. Исходные данные для оптимизации на Рабочем листе Excel

После внесения на Рабочий лист Excel всех необходимых данных, устанавливаем курсор на клетке Е13 и задаем команду Сервис – Поиск решения. Заполняем диалоговое окно «Поиск решения» (см. Рис.7.2) следующими данными:

Рисунок 7.2. Диалоговое окно для задания параметров оптимизации

Нажав кнопку «Выполнить» получаем решение (см. Рис.7.3) - элементы матрицы перевозок груза, которые расположены в ячейках В3: D5 и расчетное значение целевой функции – 945 грн.

Рисунок 7.3. Результат оптимизации транспортных перевозок расчетов