ОПТИМИЗАЦИОННЫХ ЗАДАЧ ТРАНСПОРТНОГО ТИПА В MICROSOFT EXCEL

КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ

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

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

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

Содержательная постановка задачи. Компанией разрабатывается план обеспечения потребителей горюче-смазочными материалами (ГСМ). Исходные данные о запасах ГСМ в хранилищах, заявках на ГСМ в центрах распределения и стоимости перевозки 1 т ГСМ от хранилищ к центрам распределения представлены в нижеследующей таблице.

Требуется разработать такой план доставки ГСМ от хранилищ к центрам распределения, чтобы общая стоимость перевозок была минимальной.

где т — количество исходных пунктов (в рассматриваемой задаче количество хранилищ);

п — количество пунктов назначения (в рассматриваемой задаче количество центров распределения);

a_i. — количество (объем ) груза в i-м исходном пункте;

b_j. — количество (объем) груза, которое должно быть завезено в j'-й пункт назначения.

Таким образом, она является сбалансированной.

Так как запасы равны потребностям, то все запасы будут вывезены, а все потребности будут удовлетворены. Данные условия можно записать в виде следующих уравнений:

Так как количество перевозимого груза не может принимать отрицательные значения, то в рассматриваемой задаче имеет место условие неотрицательности, т. е.:

Выражения (2)—(4) образуют систему ограничений задачи, целевая функция в которой задается выражением:

Экономическая интерпретация выражения (5) становится очевидной, если его записать в развернутом виде:

Так как с_ij — это стоимость перевозки одной единицы груза с i-гo исходного пункта в j'-й пункт назначения, а х_ij — объем перевозимого груза по данному маршруту, то с_ijх_ij — это стоимость перевозки груза по маршруту «i-й исходный пункт — у'-й пункт назначения». Сложение стоимостей перевозок по всем возможным маршрутам образует стоимость общего плана перевозок.

Объединяя выражения (2)—(6), получаем модель сбалансированной транспортной задачи:

Выражение (7.1) запишется в виде системы следующих уравнений:

Условие неотрицательности (7.3) будет задано 20 неравенствами следующего вида:

Целевая функция (7.4) запишется в виде выражения:

F = 4х₁₁ + 6х₁₂ + ... + 5х₃₁ + ... + 7х₄₅ ->min.

Таким образом, математическая модель рассматриваемой задачи разработана, можно переходить к вычислительной модели задачи.

Вычислительная модель задачи. Форма представления вычислительной модели задачи на рабочем листе может быть самой различной. Для рассматриваемой задачи нами предлагается вычислительная модель, представленная на рис. 1.

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

Логика построения вычислительной модели задачи на рабочем листе достаточно проста и состоит в записи выражений (8)—(11) в MS Excel.

Поскольку диапазон B12:F15 отведен для расчета оптимального плана перевозок, то ячейка В12 соответствует переменной х₁₁, ячейка С12 — переменной х₁₂, ячейка D12 — переменной х₁₃ и т. д. Первое уравнение математической модели задачи (х_п + х₁₂ + х₁₃ + х_и + х₁₅ = 350) может быть записано на рабочем листе следующим образом:

• левая часть уравнения (_х11 + х₁₂ + х₁₃ + х₁₄ + х₁₅) — в ячейке G12 путем ввода формулы =СУММ(В12:F12);

• знак "=" — в ячейке HI2 путем ввода соответствующего символа с клавиатуры;

• правая часть уравнения (350) — в ячейке I12 путем ввода формулы =G3 (в ячейку I12 можно непосредственно ввести число 350, но первый способ является более удобным при последующих изменениях исходных данных задачи).

Подобным образом записываются и другие уравнения. Уравнения (8) записываются в диапазоне G12:I15, а уравнения (9) — в диапазоне B16:F18. Уравнения можно ввести быстро, если воспользоваться маркером заполнения MS Excel.

Условие неотрицательности (10) на рабочем листе задавать не будем, зададим его позже в диалоговом окне Параметры поиска решения.

Для расчета целевой функции отведена ячейка G19. Введем в эту ячейку формулу =CУMMПРОИЗВ(B3:F6;B12:F15), которая соответствует математическому выражению (11).

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

Вычислительная модель задачи в диалоговом окне Поиск решения.Находясь на рабочем листе с разработанной вычислительной моделью, вызовем на выполне­ние надстройку Поиск решения.

Рисунок 2. Вычислительная модель задачи в диалоговом окне «Поиск решения»

В поле Изменяя ячейкивведем ссылку на диапазон ячеек, в которых будут рассчитываться значения искомых переменных, т. е. на диапазон B12:F15.

В поле Ограничениявведем ссылки на диапазоны G12:I15 hB16:F18, которые соответствуют выражениям (8) и (9).

В диалоговом окне Параметры поиска решенияактивизируем флажки Линейная модельи Неотрицательные значения.

Нажмем кнопку Выполнить— получим решение задачи (рис. 3).

Рисунок 3. Вычислительная модель задачи – состояние 2

План перевозок, рассчитанный в ячейках B12:F15, является оптимальным. При данном решении значение целевой функции, рассчитанное в ячейке G19, минимально и равно 4250 у.е.

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

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

При использовании надстройки Поиск решенияв этом нет необходимости, надо только правильно расставить знаки в системе ограничений. Посмотрим, как это можно сделать в рассматриваемой задаче.

С точки зрения экономической интерпретации выражение означает,

что все запасы должны быть вывезены, а выражение потребности должны быть удовлетворены. В ситуации дефицита запасы будут вывезены полностью, т.е. выражение останется без изменений, а вот потребности будут удовлетворены не полностью, т. е. уравнение трансформируется в неравенство Обратим внимание, что используется знак нестрогого не равенства, так как какие-то центры могут быть обеспечены ГСМ в полном объеме, а какие-то нет.

После модификации математической модели задачи внесем соответствующие изменения в ее вычислительную модель. Для этого на рабочем листе в диапазоне B17:F17 поменяем знаки "=" на "<"*, то же самое сделаем и в диалоговом окне Поиск решения. Нажмем кнопку Выполнить— получим решение модифицированной задачи (рис. 4).

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

Обратим внимание, что ячейки диапазона G12:G15 равны ячейкам диапазона 112:115, т. е. все запасы вывезены. Ячейки В16, Е16 и F16 равны соответствующим ячейкам в диапазоне B18:F18, т. е. Центр 1, Центр 4 и Центр 5 удовлетворены ГСМ в полном объеме, а ячейки С16 и D16меньше соответствующих ячеек в диапазоне B18:F18, т. е. в Центр 2 и Центр 3 горюче-смазочные материалы недопоставлены в размере 250 и 50 т соответственно. Ниже представлено, как в данной ситуации осуществить «справедливую» недопоставку ГСМ по всем центрам. Далее рассмотрим еще ряд важных ситуаций, встречающихся на практике.

Допустим, вам поступило указание обеспечить Центр 2 в полном объеме. Для этого необходимо лишь изменить в ячейке С17 знак "<" на знак "=" и ввести дополнительное ограничение С16 = С18 в диалоговом окне Поиск решения.Решение представлено на рис. 5.

Как видно из рис. 5, в Центр 3 горюче-смазочные материалы вообще не доставляются. Допустим, вам поступило указание обеспечить Центр 3 не менее чем на 85 % от его потребностей. В математической интерпретации это указание запишется как b₃> 212,5. С учетом ранее имеющегося ограничения на потребность ГСМ в Центре 3 будем иметь, что 212,5 < b₃< 250.

Рисунок 5. Вычислительная модель задачи – состояние 5

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

Например, в плане на рис. 6 осуществляется перевозка по маршруту Хранилище 2 — Центр 3 в размере 200т, необходимо заблокировать перевозку по данному маршруту. В математической интерпретации это указание запишется в виде ограничения. Другим, «искусственным», способом задания блокировки является назначение большой стоимости перевозки блокируемому маршруту, например с₃₁ = 1000.

Другой распространенной задачей является задача перевозки определенного объе­ма груза по указанному маршруту. Например, между Хранилищем 4 и Центром 1 заключен договор на поставку 300 т ГСМ, а между Хранилищем 1 и Центром 4 — на поставку 100т ГСМ. Решение задачи представлено на рис. 8.

Используем первый способ для блокирования маршрута Хранилище 2 — Центр 3, для чего в диалоговом кне Поиск решениявведем ограничение D13 = 0. Второй способ используем для блокирования маршрута ХранилищеЗ — Центр 1, для чего в ячейку В5 введем какое-нибудь относительно большое число, например 1000.Решение представлено на рис 7.

Другой распространенной задачей является задача перевозки определенного объема груза по указанному маршруту. Например, между Хранилищем 4 и центром 1 заключен договор на поставку 300 т ГСМ, а между Хранилищем 4 и Центром 4 на поставку 100т ГСМ. Решение задачи представлено на рис 8.

Далее рассмотрим схему недопоставки в условиях дефицита, для чего обратимся к модели, представленной на рис. 4. Как видим, недопоставка коснулась только двух центров — Центра 2 и Центра 3, что является по отношению к ним несправедливым решением. Постараемся исправить сложившуюся ситуацию.

Самым простым решением в этом случае будет равномерная недопоставка ГСМ во все пять центров. При дефиците в 400 т (400 = 1750 - 1350) она будет составлять 80 т ГСМ для каждого центра. Однако, как легко заметить, такое решение также будет несправедливым. Например, недопоставка в 80 т для Центра 2 будет лишь неприятностью, а для Центра4 — «бедой». Отсюда напрашивается пропорциональное распределение ГСМ относительно масштабов (потребностей) центров, что в нашем понимании и будет являться справедливым решением.

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

Первый подход состоит в расчете коэффициента обеспеченности

Корректировка потребностей осуществляется в соответствии с формулой

где bf^ew — новое значение спроса в у'-м центре;

bf^d — старое значение спроса в у'-м центре.

Второй подход состоит в следующих, несколько более длинных рассуждениях. Вначале определяется доля каждого центра в общем объеме потребностей:

hi Логичным будет в соответствии с этими долями осуществить и недопоставку:

где объем недопоставки в у'-й центр,

пт

V ^edl = /&/ ^- /,#i — общий объем недостающих ресурсов (объем дефицита).

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

После внесения необходимых изменений на рабочем листе и в диалоговом окне Поиск решения запускаем процедуру поиска. Решение задачи представлено на рис. 9.

В рассмотренной задаче транспортировка ГСМ осуществлялась в условиях дефицита, т. е. выполнялось условие £^Щ </ , b/ . Наряду с «дефицитной» постановкой задачи возможна и противоположная ей «избыточная» постановка, т. е. когда выполняется условие 2_\^ai >/,\bj • Исходные данные для такой задачи представлены на рисунке 10.

В то же время запасы ГСМ будут вывезены из хранилищ не в полном объеме,

т.е. имеет место ограничение У, ^xij - ^ai (знак нестрогого неравенства указывает на

то, что из некоторых хранилищ запасы могут быть вывезены в полном объеме, а из каких-то нет).

Предположим, что поступила следующая информация:

1) Хранилище 3 ликвидируется, поэтому запасы ГСМдолжны быть вывезены из него в полном объеме;

2) мост по дороге от Хранилища 2 к Центру 3 закрыт на реконструкцию, поэто­му необходимо запретить перевозку по указанному маршруту.

Решение задачи представлено на рис. 12

Предположим, что неприкосновенный (неснижаемый) запас в Хранилище 2 со­ставляет 300 т. Тогда при емкости в 400т из него в пределе может быть вывезено 100т ГСМ.

Решение задачи представлено на рис. 13.

Рассмотренные модели, безусловно, не отображают разнообразия всех тех многочисленных ситуаций, которые встречаются в практической деятельности. Тем не менее, их можно рекомендовать в качестве отправных точек для дальнейшего исследования. Направлениями таких исследований могут быть многопродуктовые перевозки, перевозки с промежуточными пунктами, перевозки с учетом грузоподъемности транспортных средств и многие другие