Вычислительная модель задачи в диалоговом

Окне Поиск решения

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

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

Вычислительная модель задачи в диалоговом - student2.ru

Рис. 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). Получим, что Вычислительная модель задачи в диалоговом - student2.ru , Вычислительная модель задачи в диалоговом - student2.ru , т. е. Вычислительная модель задачи в диалоговом - student2.ru . Таким образом, спрос превышает предложение, и задача стала несбалансированной. В такой ситуации для решения задачи обычно вводят фиктивного поставщика. При использовании надстройки "Поиск решения" в этом нет необходимости, надо только правильно расставить знаки в системе ограничений. Посмотрим, как это можно сделать в рассматриваемой задаче.

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

После модификации математической модели задачи внесем соответствующие изменения в её вычислительную модель. Для этого на рабочем листе в диапазоне 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% от его потребностей. В математической интерпретации это указание запишется как Вычислительная модель задачи в диалоговом - student2.ru . С учетом ранее имеющегося ограничения на потребность ГСМ в Центре3 будем иметь, что Вычислительная модель задачи в диалоговом - student2.ru .

Ограничение Вычислительная модель задачи в диалоговом - student2.ru в разработанной модели имеется, остается добавить ограничение Вычислительная модель задачи в диалоговом - student2.ru . Это можно сделать различными способами, допустим, непосредственно в диалоговом окне Поиск решения ввести 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 тонн, необходимо заблокировать перевозку по данному маршруту. В математической интерпретации это указание запишется в виде ограничения Вычислительная модель задачи в диалоговом - student2.ru . Другим, "искусственным", способом задания блокировки является назначение большой стоимости перевозки блокируемому маршруту, например, Вычислительная модель задачи в диалоговом - student2.ru .

Используем первый способ для блокирования маршрута Хранилище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 – "бедой". Отсюда напрашивается пропорциональное распределение ГСМ относительно масштабов (потребностей) центров, что в нашем понимании и будет являться справедливым решением.

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

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

Вычислительная модель задачи в диалоговом - student2.ru .

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

Вычислительная модель задачи в диалоговом - student2.ru ,

где Вычислительная модель задачи в диалоговом - student2.ru – новое значение спроса в j-м центре;

Вычислительная модель задачи в диалоговом - student2.ru – старое значение спроса в j-м центре.

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

Вычислительная модель задачи в диалоговом - student2.ru .

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

Вычислительная модель задачи в диалоговом - student2.ru ,

где Вычислительная модель задачи в диалоговом - student2.ru – объем недопоставки в j-й центр;

Вычислительная модель задачи в диалоговом - student2.ru – общий объем недостающих ресурсов (объем дефицита).

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

Вычислительная модель задачи в диалоговом - student2.ru .

Выбрав тот или иной способ корректировки потребностей, рассчитаем их новые значения. Все расчеты целесообразно проводить непосредственно на рабочем листе 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

В рассмотренной задаче транспортировка ГСМ осуществлялась в условиях дефицита, т. е. выполнялось условие Вычислительная модель задачи в диалоговом - student2.ru . Наряду с "дефицитной" постановкой задачи возможна и противоположная ей "избыточная" постановка, т. е. когда выполняется условие Вычислительная модель задачи в диалоговом - student2.ru . Исходные данные для такой задачи представлены на рис. 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

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

Решение задачи представлено на рис. 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.

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

Наши рекомендации