Одной из самых распространенных проблем во всех областях экономики
является транспортировка груза или товара с минимальными материальными
и временными затратами. Так как огромное количество возможных вариантов
перевозок затрудняет получение самого экономичного плана эмпирическим
или экспертным путем, то появилась необходимость разработки специальной
теории, позволяющей быстро решать подобные задачи с помощью алгоритмизации.
Применение математических методов в планировании перевозок дает
большой экономический эффект. В этом нам и предстоит сейчас убедиться
при помощи нашего знакомого Васи, который как раз устроился работать
курьером.
Постановка задачи
Компания, где Василий нашел вакантное место курьера, имеет два
склада, на которых хранится товар, и три магазинчика - конторы,
где этот товар реализуется. Задача Васи заключается в строгом выполнении
плана, который он получает каждый день. В качестве транспортного
средства он использует старый, но выносливый советский велосипед,
который не позволяет перевозить всю партию за раз. Поэтому нашему
ненасытному другу приходится мотаться туда-сюда. На что он опять
копит? Что же он там перевозит? Не ждите от меня ответов на эти
вопросы, если б знал - давно бы уже сказал бы.
И тут Василий, изнывая от мучительных болей в ногах и предвидя
жесткий выговор со стороны начальства за невыполнение работы в намеченный
срок, задумался: можно ли составить с учетом выдаваемого ему плана
такой маршрут движения, чтобы на выполнение всего задания уходило
минимум времени и сил. Конечно, можно! Этим мы сейчас и займемся.
Составление математической модели
Сначала необходимо проделать подготовительную работу, а именно
- определить тарифы на каждом участке будущего оптимального плана
перевозок. Поскольку Вася заинтересован в том, чтобы делать свою
работу максимально быстро, то в качестве тарифов в данной задаче
выступает время, потраченное на перевозку единицы товара из n-го
склада в m-ую контору. При помощи карты Минска (CityInfo) с учетом
времени на перекур и на подкачку шин, Вася оценил среднее время
перевозки товара из каждого склада в каждую контору. В результате
была составлена таблица 1.
Таблица
1. Время на перевозку |
Склад\Контора |
Контора
№1 |
Контора
№2 |
Контора
№3 |
Есть
на складах |
Склад
№1 |
5 |
20 |
8 |
20 |
Склад
№2 |
10 |
15 |
12 |
30 |
Потребность |
15 |
12 |
20 |
47/50 |
Данная транспортная задача относится к типу задач с неправильным
балансом (47<>50), но нас это не должно смущать. Я вас уверяю,
мы ничего не будем решать вручную. Хотелось бы отметить, что в реальной
жизни транспортные задачи с правильным балансом встречаются не очень
часто. Далее задачу необходимо, как говорится, формализировать,
т.е. записать в виде уравнений (формул). Пусть X - количество единиц
товара, перевозимых из каждого склада в каждую контору. Тогда X11
- количество единиц товара, перевозимых из первого склада в первую
контору, X12 - количество единиц товара, перевозимых из первого
склада во вторую контору, и т.д. (такие предложения пишутся простым
копированием, если вы не знали.;) Поскольку задача с неправильным
балансом, то необходимо ввести также фиктивную контору. Все переменные
представлены в таблице 2.
Таблица
2. Количество перевозимых товаров |
Склад\Контора |
Контора
№1 |
Контора
№2 |
Контора
№3 |
Фиктивная |
Есть
на складах |
Склад
№1 |
X11 |
X12 |
X13 |
X14 |
20 |
Склад
№2 |
X21 |
X22 |
X23 |
X24 |
30 |
Потребность |
15 |
12 |
20 |
3 |
50/50 |
Теперь все готово для составления системы уравнений и целевой функции,
определяющей время выполнения плана перевозок и направленной на
минимум. По смыслу ясно, что количество единиц товара, привезенных
с каждого склада в контору, в сумме должно равняться потребности
этой конторы. Т.е.
X11+ X21=15
X12+ X22=12
X13+ X23=20
X14+ X24=3
Аналогично получаем следующие условия:
X11+X12+X13+X14=20
X21+X22+X23+X24=30
Целевая функция, как я уже говорил, определяет время выполнения
намеченного плана транспортировки товара. Поэтому:
E=5* X11 + 20* X12 + 8* X13 + 10* X21 + 15* X22 + 12* X23 ->min
Тарифы на доставку товара в виртуальную контору принимаются равными
нулю, поэтому слагаемое "0*X14+0*X24" в записи формулы для целевой
функции можно опустить. Теперь приступим непосредственно к решению
поставленной задачи. Согласитесь, проделанные до сих пор операции
не вызывают больших трудностей.
Выбор метода решения
А найти решение нам поможет мощный табличный процессор Microsoft
Excel, широко используемый не только как удобное средство для хранения
разнообразных данных и многофункциональный инструмент, позволяющий
выполнять над ними многочисленные математические операции, но и
как орудие для решения несложных оптимизационных задач. Последним,
в частности, и занимается программная надстройка "Поиск решения".
Если она у вас не установлена, то проделайте следующие действия:
"Сервис" > "Надстройки", потом поставьте галочку около пункта
"Поиск решения". Для поиска ответа остается только занести шесть
ограничений и целевую функцию в Excel. Я не буду докучать читателю
((с) Джонатан Свифт, "Путешествия Гулливера";) подробным описанием
того, как следует вводить данные в ячейки таблицы или как нужно
составлять ограничения в "Поиск решения". Этот титанический труд
был проделан в первой статье по оптимизации в среде Excel, опубликованной
в 21-м номере. Отмечу, что хоть задача про изготовление баннеров
и задача про перевозки принадлежат к различным типам задач, для
нахождения ответа на которые разработано множество "своих" методов,
все-таки обе задачи являются задачами линейного программирования.
Поэтому их можно решать и общим для всех задач линейного программирования
способом - симплекс-методом. Конечно, для решения транспортных задач
вручную намного предпочтительнее использовать специально разработанные
для этих целей алгоритмы. Но в конкретном случае мы переложим наше
бремя на плечи машины. Ей-то какая разница, выполнять 10 или 100
итераций. Если мы собираемся использовать тот же самый подход, что
и при решении задачи об изготовлении баннеров, то алгоритм поиска
оптимального ответа в данном примере почти не будет отличаться от
алгоритма, описанного в предыдущей статье. Различия будут заключаться
лишь в подготовительных работах, которые мы, сами того не зная,
уже проделали выше.
Итак, в ячейки строки с целевой функцией запишем коэффициенты перед
переменными, входящими в целевую функцию. Так же поступим и cо всеми
ограничениями в виде равенств (в столбце "L" записывается правая
часть уравнений). В столбце с решением "J" в каждую ячейку введем
формулу вида "=СУММПРОИЗВ(Bn:Gn;B2:G2)", где n изменяется от 3 до
9. Теперь открываем рабочее окно "Поиск решения" и записываем все
ограничения, показанные на рисунке.
![](task2/2005370101.gif)
Нажимаем на кнопку "Выполнить" и вместе с Васей радуемся полученным
результатам.
Анализ полученных результатов
Оптимальный план перевозок груза выглядит следующим образом: с
первого склада нужно переправить 15 ед. груза в первую контору и
5 ед. груза в третью контору, а со второго - 12 ед. груза во вторую
и 15 ед. груза в третью конторы. На все это Вася будет тратить 475
минут (7 часов и 55 минут). Это оптимальный вариант. Сравним его
с любым другим возможным. Допустим, что Вася решил делать все наобум
и выбирал маршрут случайным образом. Пусть план следующий: (X11,
X12, X13, X21, X22, X23)=(0, 0, 20, 15, 12, 0). Тогда целевая функция
будет равна 490 минут (за смену Вася не управится). С одной стороны,
это не много, с другой, если бы в качестве тарифов выступало не
время, а деньги, то экономия была бы существенной. Да и если вспомнить
фразеологизм "Время - деньги", то всякие сомнения по поводу рациональности
использования оптимизации в управлении и финансах отпадают. Ведь
выгода заключается не в том, что Васе приходится быстрее крутить
педали, а в том, что при помощи математической модели находится
наилучший вариант протекания реального процесса.
В качестве следствия можно отметить, что если предстоит решать
задачу с правильным балансом, то из всех рассуждений необходимо
просто исключить переменные X14 и X24.
Конечно, существует много программ, которые специализируются именно
на исследовании транспортных задач. Но с Excel'ем как-то проще ((с)
Реклама про "Биосистему"). Иногда время и деньги, потраченные на
поиски нужной программы в интернете, сравнимы с выгодой, полученной
в ходе оптимизации. На одной web-странице программу, работающую
с транспортными задачами, предлагалось приобрести за $100. Другое
приложение оказалось бесплатным, но не умело решать задачи в общем
случае (с неправильным балансом). Вот такие пироги (или проги ;).
В современном обществе методы оптимизации применяются повсеместно,
принося существенную экономическую выгоду и предупреждая финансовые
крахи. Они позволяют принимать разнообразные управленческие решения
в условиях риска и неопределенности. Правда, уже при помощи более
мощных программных комплексов, работающих на основе генетических
алгоритмов, нечеткой логики и нейронных сетей.