Вычислительная модель задачи в диалоговом
Окне Поиск решения
Находясь на рабочем листе с разработанной вычислительной моделью, вызовем на выполнение надстройку "Поиск решения" (рис. 1.3).
В поле Установить целевую ячейку введем ссылку на ячейку, в которой будет рассчитываться значение целевой функции. Такой ячейкой на рабочем листе является ячейка G19, в которой заключена формула расчета стоимости плана перевозок. Так как стоимость плана необходимо минимизировать, то и переключатель Равной необходимо установить в положение минимальному значению (рис. 2.18).
Рис. 2.18
В поле Изменяя ячейки введем ссылку на диапазон ячеек, в которых будут рассчитываться значения искомых переменных, т. е. на диапазон B12:F15.
В поле Ограничения введем ссылки на диапазоны G12:I15 и B16:F18, которые соответствуют выражениям (2.9) и (2.10).
В диалоговом окне Параметры поиска решения активизируем флажки Линейная модель и Неотрицательные значения.
Нажмем кнопку Выполнить – получим решение задачи (рис. 2.19).
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Уравнения (неравенства) | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | лев. часть (вывезено) | знак | прав. часть (запас) | ||
| Хр-ще1 | 50,00 | 50,00 | 0,00 | 0,00 | 250,00 | 350,00 | = | 350,00 | |
| Хр-ще2 | 0,00 | 0,00 | 200,00 | 0,00 | 0,00 | 200,00 | = | 200,00 | |
| Хр-ще3 | 300,00 | 0,00 | 50,00 | 100,00 | 0,00 | 450,00 | = | 450,00 | |
| Хр-ще4 | 0,00 | 350,00 | 0,00 | 0,00 | 0,00 | 350,00 | = | 350,00 | |
| лев. часть (завезено) | 350,00 | 400,00 | 250,00 | 100,00 | 250,00 | ||||
| знак | = | = | = | = | = | ||||
| прав. часть (потребн.) | 350,00 | 400,00 | 250,00 | 100,00 | 250,00 | ||||
| Стоимость перевозки | 4250,00 | ® | min |
Рис. 2.19
План перевозок, рассчитанный в ячейках B12:F15, является оптимальным. При данном решении значение целевой функции, рассчитанное в ячейке G19, является минимальным и равно 4250 у.е.
Построенная модель классической транспортной задачи является платформой, на основе которой могут быть разработаны различные модифицированные модели, учитывающие разнообразные ситуации, возникающие в практической деятельности. Рассмотрим некоторые из них.
Увеличим потребности в ГСМ у первого центра до 500 тонн, а у второго центра до 650 тонн (см. ячейки B7 и C7 на рис. 2.20). Получим, что 
, 
, т. е. 
. Таким образом, спрос превышает предложение, и задача стала несбалансированной. В такой ситуации для решения задачи обычно вводят фиктивного поставщика. При использовании надстройки "Поиск решения" в этом нет необходимости, надо только правильно расставить знаки в системе ограничений. Посмотрим, как это можно сделать в рассматриваемой задаче.
С точки зрения экономической интерпретации выражение 
означает, что все запасы должны быть вывезены, а выражение 
–, что все потребности должны быть удовлетворены. В ситуации дефицита запасы будут вывезены полностью, т. е. выражение останется без изменений, а вот потребности будут удовлетворены не в полном объеме, т.е. уравнение трансформируется в неравенство 
. Обратим внимание, что используется знак нестрогого неравенства, так как какие-то центры могут быть обеспечены ГСМ в полном объеме, а какие-то нет.
После модификации математической модели задачи внесем соответствующие изменения в её вычислительную модель. Для этого на рабочем листе в диапазоне B17:F17 поменяем знаки "=" на "£"*, то же самое сделаем и в диалоговом окне Поиск решения. Нажмем кнопку Выполнить – получим решение модифицированной задачи (рис. 2.20).
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Запасы ГСМ в хр-щах, т | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | |||||
| Хр-ще1 | |||||||||
| Хр-ще2 | |||||||||
| Хр-ще3 | |||||||||
| Хр-ще4 | |||||||||
| Потребн. в ГСМ, т | |||||||||
| Хр-ща ГСМ | Центры распределения | Уравнения (неравенства) | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | лев. часть (вывезено) | знак | прав. часть (запас) | ||
| Хр-ще1 | 100,00 | 0,00 | 0,00 | 0,00 | 250,00 | 350,00 | = | 350,00 | |
| Хр-ще2 | 0,00 | 0,00 | 200,00 | 0,00 | 0,00 | 200,00 | = | 200,00 | |
| Хр-ще3 | 350,00 | 0,00 | 0,00 | 100,00 | 0,00 | 450,00 | = | 450,00 | |
| Хр-ще4 | 50,00 | 300,00 | 0,00 | 0,00 | 0,00 | 350,00 | = | 350,00 | |
| лев. часть (завезено) | 500,00 | 300,00 | 200,00 | 100,00 | 250,00 | ||||
| знак | <= | <= | <= | <= | <= | ||||
| прав. часть (потребн.) | 500,00 | 650,00 | 250,00 | 100,00 | 250,00 | ||||
| Стоимость перевозки | 4000,00 | ® | min |
Рис. 2.20
Обратим внимание, что ячейки диапазона G12:G15 равны ячейкам диапазона I12:I15, т. е. все запасы вывезены. Ячейки B16, E16 и F16 равны соответствующим ячейкам в диапазоне B18:F18, т. е. Центр1, Центр4 и Центр5 удовлетворены ГСМ в полном объеме, а ячейки C16 и D16 меньше соответствующих ячеек в диапазоне B18:F18, т. е. в Центр2 и Центр3 горюче-смазочные материалы недопоставлены в размере 250 и 50 тонн соответственно. Ниже мы рассмотрим, как в данной ситуации осуществить "справедливую" недопоставку ГСМ по всем центрам. А сейчас рассмотрим ещё ряд важных ситуаций, встречающихся на практике.
Важно! После получения решения в соответствии с рис.2.20 создайте копию данного листа (Щелчок правой кнопкой мыши по ярлычку листа–Переместить/скопировать лист… – (переместить в конец) – Создать копию – ОК). Продолжите решение задачи на листе Лист1(2).xls.
Допустим, вам поступило указание обеспечить Центр2 в полном объеме. Для этого необходимо лишь изменить в ячейке C17 знак "£" на знак "=" и ввести дополнительное ограничение С16=С18 в диалоговом окне Поиск решения. Решение представлено на рис. 2.21.
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Уравнения (неравенства) | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | лев. часть (вывезено) | знак | прав. часть (запас) | ||
| Хр-ще1 | 0,00 | 100,00 | 0,00 | 0,00 | 250,00 | 350,00 | = | 350,00 | |
| Хр-ще2 | 0,00 | 200,00 | 0,00 | 0,00 | 0,00 | 200,00 | = | 200,00 | |
| Хр-ще3 | 350,00 | 0,00 | 0,00 | 100,00 | 0,00 | 450,00 | = | 450,00 | |
| Хр-ще4 | 0,00 | 350,00 | 0,00 | 0,00 | 0,00 | 350,00 | = | 350,00 | |
| лев. часть (завезено) | 350,00 | 650,00 | 0,00 | 100,00 | 250,00 | ||||
| знак | <= | = | <= | <= | <= | ||||
| прав. часть (потребн.) | 500,00 | 650,00 | 250,00 | 100,00 | 250,00 | ||||
| Стоимость перевозки | 4850,00 | ® | min |
Рис. 2.21
Как видно из рис. 2.21, в Центр3 горюче-смазочные материалы вообще не доставляются. Допустим, вам поступило указание обеспечить Центр3 не менее чем на 85% от его потребностей. В математической интерпретации это указание запишется как 
. С учетом ранее имеющегося ограничения на потребность ГСМ в Центре3 будем иметь, что 
.
Ограничение 
в разработанной модели имеется, остается добавить ограничение . Это можно сделать различными способами, допустим, непосредственно в диалоговом окне Поиск решения ввести D16 >= 212,5. Решение представлено на рис. 2.22.
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Уравнения (неравенства) | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | лев. часть (вывезено) | знак | прав. часть (запас) | ||
| Хр-ще1 | 0,00 | 100,00 | 0,00 | 0,00 | 250,00 | 350,00 | = | 350,00 | |
| Хр-ще2 | 0,00 | 0,00 | 200,00 | 0,00 | 0,00 | 200,00 | = | 200,00 | |
| Хр-ще3 | 137,50 | 200,00 | 12,50 | 100,00 | 0,00 | 450,00 | = | 450,00 | |
| Хр-ще4 | 0,00 | 350,00 | 0,00 | 0,00 | 0,00 | 350,00 | = | 350,00 | |
| лев. часть (завезено) | 137,50 | 650,00 | 212,50 | 100,00 | 250,00 | ||||
| знак | <= | = | <= | <= | <= | ||||
| прав. часть (потребн.) | 500,00 | 650,00 | 250,00 | 100,00 | 250,00 | ||||
| Стоимость перевозки | 4875,00 | ® | min |
Рис. 2.22
В практической деятельности также встречаются задачи, связанные с блокированием перевозок. Это может быть обусловлено причинами техногенного характера (оползень, сход снега на перевал и т.п.), ремонтно-восстановительными работами (закрытие моста на реконструкцию и т.п.) или, что чаще встречается на практике, коммерческими соображениями.
Например, в плане на рис. 2.22 осуществляется перевозка по маршруту Хранилище2 – Центр3 в размере 200 тонн, необходимо заблокировать перевозку по данному маршруту. В математической интерпретации это указание запишется в виде ограничения 
. Другим, "искусственным", способом задания блокировки является назначение большой стоимости перевозки блокируемому маршруту, например, 
.
Используем первый способ для блокирования маршрута Хранилище2 – Центр3, для чего в диалоговом окне Поиск решения введем ограничение D13 = 0. Второй способ используем для блокирования маршрута Хранилище3 – Центр1, для чего в ячейку B5 введем какое-нибудь относительно большое число, например, 1000. Решение представлено на рис. 2.23.
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Уравнения (неравенства) | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | лев. часть (вывезено) | знак | прав. часть (запас) | ||
| Хр-ще1 | 100,00 | 0,00 | 0,00 | 0,00 | 250,00 | 350,00 | = | 350,00 | |
| Хр-ще2 | 0,00 | 200,00 | 0,00 | 0,00 | 0,00 | 200,00 | = | 200,00 | |
| Хр-ще3 | 0,00 | 100,00 | 250,00 | 100,00 | 0,00 | 450,00 | = | 450,00 | |
| Хр-ще4 | 0,00 | 350,00 | 0,00 | 0,00 | 0,00 | 350,00 | = | 350,00 | |
| лев. часть (завезено) | 100,00 | 650,00 | 250,00 | 100,00 | 250,00 | ||||
| знак | <= | = | <= | <= | <= | ||||
| прав. часть (потребн.) | 500,00 | 650,00 | 250,00 | 100,00 | 250,00 | ||||
| Стоимость перевозки | 5450,00 | ® | min |
Рис. 2.23
Другой распространенной задачей является задача перевозки определенного объема груза по указанному маршруту. Например, между Хранилищем4 и Центром1 заключен договор на поставку 300 т ГСМ, а между Хранилищем1 и Центром4 – на поставку 100 т ГСМ. Решение задачи представлено на рис. 2.24.
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Уравнения (неравенства) | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | лев. часть (вывезено) | знак | прав. часть (запас) | ||
| Хр-ще1 | 0,00 | 162,50 | 0,00 | 100,00 | 87,50 | 350,00 | = | 350,00 | |
| Хр-ще2 | 0,00 | 200,00 | 0,00 | 0,00 | 0,00 | 200,00 | = | 200,00 | |
| Хр-ще3 | 0,00 | 237,50 | 212,50 | 0,00 | 0,00 | 450,00 | = | 450,00 | |
| Хр-ще4 | 300,00 | 50,00 | 0,00 | 0,00 | 0,00 | 350,00 | = | 350,00 | |
| лев. часть (завезено) | 300,00 | 650,00 | 212,50 | 100,00 | 87,50 | ||||
| знак | <= | = | <= | <= | <= | ||||
| прав. часть (потребн.) | 500,00 | 650,00 | 250,00 | 100,00 | 250,00 | ||||
| Стоимость перевозки | 6900,00 | ® | min |
Рис. 2.24
И в заключение рассмотрим схему "справедливой" недопоставки в условиях дефицита, для чего обратимся к модели, представленной на рис. 2.20. Как видим, недопоставка коснулась только двух центров – Центра2 и Центра3, что является по отношению к ним несправедливым решением. Постараемся исправить сложившуюся ситуацию.
Важно!Схему «справедливой» недопоставки рассмотрите на листе Лист1.xls.
Самым простым решением в этом случае является равномерная недопоставка ГСМ во все пять центров. При дефиците в 400 тонн (400 = 1750 – 1350) она будет составлять 80 тонн ГСМ для каждого центра. Однако, как легко заметить, такое решение также будет несправедливым. Например, недопоставка в 80 тонн для Центра2 будет лишь "некоторой неприятностью", а для Центра4 – "бедой". Отсюда напрашивается пропорциональное распределение ГСМ относительно масштабов (потребностей) центров, что в нашем понимании и будет являться справедливым решением.
Существуют различные подходы к пропорциональному распределению ресурсов. Рассмотрим два из них.
Первый подход состоит в расчете коэффициента обеспеченности
.
Корректировка потребностей осуществляется в соответствии с формулой
,
где 
– новое значение спроса в j-м центре;
– старое значение спроса в j-м центре.
Второй подход состоит в следующих, несколько более длинных рассуждениях. Вначале определяется доля каждого центра в общем объеме потребностей
.
Логичным будет в соответствии с этими долями осуществить и недопоставку:
,
где 
– объем недопоставки в j-й центр;
– общий объем недостающих ресурсов (объем дефицита).
Корректировка потребностей осуществляется в соответствии с формулой
.
Выбрав тот или иной способ корректировки потребностей, рассчитаем их новые значения. Все расчеты целесообразно проводить непосредственно на рабочем листе MS Excel. При этом заметим, что задача из несбалансированной вновь превращается в сбалансированную.
После внесения необходимых изменений на рабочем листе и в диалоговом окне Поиск решениязапускаем процедуру поиска. Решение задачи представлено на рис. 2.25.
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Уравнения (неравенства) | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | лев. часть (вывезено) | знак | прав. часть (запас) | ||
| Хр-ще1 | 12,86 | 144,29 | 0,00 | 0,00 | 192,86 | 350,00 | = | 350,00 | |
| Хр-ще2 | 0,00 | 7,14 | 192,86 | 0,00 | 0,00 | 200,00 | = | 200,00 | |
| Хр-ще3 | 372,86 | 0,00 | 0,00 | 77,14 | 0,00 | 450,00 | = | 450,00 | |
| Хр-ще4 | 0,00 | 350,00 | 0,00 | 0,00 | 0,00 | 350,00 | = | 350,00 | |
| лев. часть (завезено) | 385,71 | 501,43 | 192,86 | 77,14 | 192,86 | ||||
| знак | = | = | = | = | = | ||||
| прав. часть (потребн.) | 385,71 | 501,43 | 192,86 | 77,14 | 192,86 | ||||
| Стоимость перевозки | 4554,29 | ® | min |
Рис. 2.25
В рассмотренной задаче транспортировка ГСМ осуществлялась в условиях дефицита, т. е. выполнялось условие 
. Наряду с "дефицитной" постановкой задачи возможна и противоположная ей "избыточная" постановка, т. е. когда выполняется условие 
. Исходные данные для такой задачи представлены на рис. 2.26.
Для решения этой задачи воспользуйтесь файлом Solver2(new).xls. Этот файл полностью (до адреса конкретной ячейки) соответствует примеру, рассмотренному в методических указаниях.
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Запасы ГСМ в хр-щах, т | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | |||||
| Хр-ще1 | |||||||||
| Хр-ще2 | |||||||||
| Хр-ще3 | |||||||||
| Хр-ще4 | |||||||||
| Потребн. в ГСМ, т | |||||||||
Рис. 2.26
Как видим 
, 
, т. е. наблюдается избыток запасов ГСМ – 
. В данной ситуации потребности центров будут удовлетворены в полном объеме, т. е. имеет место ограничение 
(будем считать, что удовлетворение потребностей производится в объеме, не превышающем поданных заявок). В то же время запасы ГСМ будут вывезены из хранилищ не в полном объеме, т. е. имеет место ограничение 
(знак нестрогого неравенства указывает на то, что из некоторых хранилищ запасы могут быть вывезены в полном объеме, а из каких-то не в полном).
Решение задачи представлено на рис. 2.27.
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Уравнения (неравенства) | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | лев. часть (вывезено) | знак | прав. часть (запас) | ||
| Хр-ще1 | 550,00 | 0,00 | 0,00 | 0,00 | 250,00 | 800,00 | <= | 850,00 | |
| Хр-ще2 | 0,00 | 50,00 | 250,00 | 100,00 | 0,00 | 400,00 | <= | 400,00 | |
| Хр-ще3 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | <= | 700,00 | |
| Хр-ще4 | 150,00 | 350,00 | 0,00 | 0,00 | 0,00 | 500,00 | <= | 500,00 | |
| лев. часть (завезено) | 700,00 | 400,00 | 250,00 | 100,00 | 250,00 | ||||
| знак | = | = | = | = | = | ||||
| прав. часть (потребн.) | 700,00 | 400,00 | 250,00 | 100,00 | 250,00 | ||||
| Стоимость перевозки | 4450,00 | ® | min |
Рис. 2.27
Предположим, что поступила следующая информация:
а) Хранилище3 ликвидируется, поэтому запасы ГСМ должны быть вывезены из него в полном объеме;
б) мост по дороге от Хранилища2 к Центру3 закрыт на реконструкцию, поэтому необходимо запретить перевозку по указанному маршруту.
Решение задачи представлено на рис. 2.28.
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Уравнения (неравенства) | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | лев. часть (вывезено) | знак | прав. часть (запас) | ||
| Хр-ще1 | 0,00 | 0,00 | 0,00 | 0,00 | 250,00 | 250,00 | <= | 850,00 | |
| Хр-ще2 | 0,00 | 150,00 | 0,00 | 100,00 | 0,00 | 250,00 | <= | 400,00 | |
| Хр-ще3 | 450,00 | 0,00 | 250,00 | 0,00 | 0,00 | 700,00 | = | 700,00 | |
| Хр-ще4 | 250,00 | 250,00 | 0,00 | 0,00 | 0,00 | 500,00 | <= | 500,00 | |
| лев. часть (завезено) | 700,00 | 400,00 | 250,00 | 100,00 | 250,00 | ||||
| знак | = | = | = | = | = | ||||
| прав. часть (потребн.) | 700,00 | 400,00 | 250,00 | 100,00 | 250,00 | ||||
| Стоимость перевозки | 6300,00 | ® | min |
Рис. 2.28
Предположим, что неприкосновенный (неснижаемый запас) в Хранилище2 составляет 300 тонн. Тогда при емкости в 400 тонн из него в пределе может быть вывезено 100 тонн ГСМ.
Решение задачи представлено на рис. 2.29.
| A | B | C | D | E | F | G | H | I | |
| Хр-ща ГСМ | Центры распределения | Уравнения (неравенства) | |||||||
| Центр1 | Центр2 | Центр3 | Центр4 | Центр5 | лев. часть (вывезено) | знак | прав. часть (запас) | ||
| Хр-ще1 | 150,00 | 0,00 | 0,00 | 0,00 | 250,00 | 400,00 | <= | 850,00 | |
| Хр-ще2 | 0,00 | 0,00 | 0,00 | 100,00 | 0,00 | 100,00 | <= | 400,00 | |
| Хр-ще3 | 450,00 | 0,00 | 250,00 | 0,00 | 0,00 | 700,00 | = | 700,00 | |
| Хр-ще4 | 100,00 | 400,00 | 0,00 | 0,00 | 0,00 | 500,00 | <= | 500,00 | |
| лев. часть (завезено) | 700,00 | 400,00 | 250,00 | 100,00 | 250,00 | ||||
| знак | = | = | = | = | = | ||||
| прав. часть (потребн.) | 700,00 | 400,00 | 250,00 | 100,00 | 250,00 | ||||
| Стоимость перевозки | 6450,00 | ® | min |
Рис. 2.29
Рассмотренные модели, безусловно, не перекрывают разнообразие всех тех многочисленных ситуаций, которые встречаются в практической деятельности. Тем не менее, их можно рекомендовать в качестве отправных точек для дальнейшего исследования. Направлениями таких исследований могут быть многопродуктовые перевозки, перевозки с промежуточными пунктами, перевозки с учетом грузоподъемности транспортных средств и многие другие. Ниже, развивая транспортную тематику, рассматривается известная разновидность задач линейного программирования, получившая название задачи о назначениях.
* В дальнейшем, если специально не оговорено, будет подразумеваться, что искомые переменные могут принимать только неотрицательные значения.
* Здесь и в дальнейшем речь будет идти о русскоязычных версиях Excel. В англоязычных версиях надстройка "Поиск решения" имеет название "Solver".
** Тем читателям, кто раньше не работал с Excel, мы настоятельно рекомендуем первоначально ознакомиться с основными техническими приемами работы с этой программой. Это не займет много времени и значительно ускорит прочтение не только этой книги, но и многих других, посвященных рассмотрению вопросов применения Excel в финансово-экономической практике.
* Некоторые аспекты неформальной теории принятия решений рассмотрены в п. 2.2.
* Изменение знаков на рабочем листе хотя и имеет лишь иллюстративный характер и не влияет на процедуру поиска решения, тем не менее, является очень полезным для понимания сути задачи и позволяет в последующем избежать ошибок при задании новых ограничений.