Постановка задачи

Компания, где Василий нашел вакантное место курьера, имеет два склада, на которых хранится товар, и три магазинчика - конторы, где этот товар реализуется. Задача Васи заключается в строгом выполнении плана, который он получает каждый день. В качестве транспортного средства он использует старый, но выносливый советский велосипед, который не позволяет перевозить всю партию за раз. Поэтому нашему ненасытному другу приходится мотаться туда-сюда. На что он опять копит? Что же он там перевозит? Не ждите от меня ответов на эти вопросы, если б знал - давно бы уже сказал бы.

И тут Василий, изнывая от мучительных болей в ногах и предвидя жесткий выговор со стороны начальства за невыполнение работы в намеченный срок, задумался: можно ли составить с учетом выдаваемого ему плана такой маршрут движения, чтобы на выполнение всего задания уходило минимум времени и сил. Конечно, можно! Этим мы сейчас и займемся.

Составление математической модели

Сначала необходимо проделать подготовительную работу, а именно - определить тарифы на каждом участке будущего оптимального плана перевозок. Поскольку Вася заинтересован в том, чтобы делать свою работу максимально быстро, то в качестве тарифов в данной задаче выступает время, потраченное на перевозку единицы товара из n-го склада в m-ую контору. При помощи карты Минска (CityInfo) с учетом времени на перекур и на подкачку шин, Вася оценил среднее время перевозки товара из каждого склада в каждую контору. В результате была составлена таблица 1.

Данная транспортная задача относится к типу задач с неправильным балансом (47<>50), но нас это не должно смущать. Я вас уверяю, мы ничего не будем решать вручную. Хотелось бы отметить, что в реальной жизни транспортные задачи с правильным балансом встречаются не очень часто. Далее задачу необходимо, как говорится, формализировать, т.е. записать в виде уравнений (формул). Пусть X - количество единиц товара, перевозимых из каждого склада в каждую контору. Тогда X11 - количество единиц товара, перевозимых из первого склада в первую контору, X12 - количество единиц товара, перевозимых из первого склада во вторую контору, и т.д. (такие предложения пишутся простым копированием, если вы не знали.;) Поскольку задача с неправильным балансом, то необходимо ввести также фиктивную контору. Все переменные представлены в таблице 2.

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

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. Теперь открываем рабочее окно "Поиск решения" и записываем все ограничения, показанные на рисунке.

Нажимаем на кнопку "Выполнить" и вместе с Васей радуемся полученным результатам.

Анализ полученных результатов

Оптимальный план перевозок груза выглядит следующим образом: с первого склада нужно переправить 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. Другое приложение оказалось бесплатным, но не умело решать задачи в общем случае (с неправильным балансом). Вот такие пироги (или проги ;).

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