Рекомендации по поиску решения задач лп

Для удобства использования средства Поиск решения необходимо следовать трем следующим принципам построения моделей линейного программирования.

Во-первых, необходимо масштабировать числа в модели таким образом, чтобы раз­ность между наибольшим и наименьшим числом в таблице не превышала шесть или семь порядков. Пусть, например, в модели одна из переменных решения — это процентная ставка (имеющая значение порядка 5%, т.е. 0,5), а показатель эффективности выражен в долларах, тогда применение средства Поиск решения может привести к неверному ре­зультату, если значение показателя эффективности будет выражаться 8-значным числом ($10 000 000, например). В этом случае разность между наименьшим (0,5) и наибольшим (10 000 000) значениями ячеек модели составит 10 порядков. Из-за этого ошибки округ­ления, возникающие в процессе вычислений, приведут к такой потере точности, что По­иск решения не сможет правильно завершить процесс. В результате будут получены не­оптимальные решения или сообщение о том, что решение не найдено.

В таких случаях нужно изменить масштаб измерения очень больших или очень ма­леньких чисел модели. В приведенном выше примере можно изменить денежные едини­цы, и выражать прибыль в миллионах долларов, а не в долларах. Это не приведет к потере общности и позволит сделать числа модели достаточно небольшими: теперь самое ма­ленькое значение (0,5) отличается от самого большого (10) всего на 3 порядка.

Плохое масштабирование моделей является второй по значимости причиной возник­новения проблем при оптимизации моделей ЛП (первая— пропуск ограничений неот­рицательности).

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

Кроме того, не рекомендуется задавать ограничения непосредственно в диалоговом окне Поиск решения, не привязывая их к ячейкам рабочего листа и используя при этом в качестве правых частей неравенств константы, а не ссылки на ячейки модели. Рассмот­рим еще один пример модели. Предположим, что исходя из определенных соображений Джим решил, что на будущей неделе должно быть произведено не более 80 стульев Captain и не более 60 Mate. Очевидно, что оптимальное решение, полученное средством Поиск решения для исходной модели, не соответствует этим новым ограниче­ниям, поэтому нужно исправить модель, включив в нее дополнительные ограничения, а затем оптимизировать полученную модель, Один из способов осуществления этого по­казан на рис. 19. Обратите внимание на два новых ограничения в верхней части списка Ограничения диалогового окна Поиск решения. Средство Поиск решения корректно оптимизирует данную модель; новое решение показано на рис.

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

Рис. 19. Новые параметры поиска решений для модели

Рис. 20. Оптимальное решение

На основе вышесказанного можно сформулировать следующие правила хорошего стиля моделирования.

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

2. Ячейки правых частей неравенств в табличной модели должны содержать кон­станты, а не формулы (точнее — не формулы, в которые явно или опосредованно входят переменные решения).

Рис. 21.

Рис. 22.

Рис. 23. Исходная модель и ее оптимальное решение

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

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

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

Совет. Чтобы скопировать изображение с экрана монитора в буфер обмена, нужно нажать кла­вишу ≤PrintScreen ≥. Чтобы копировать в буфер обмена изображение, находящееся на переднем плане (например, диалоговое окно), нужно нажать клавиши ≤AIt+PrintScreen ≥. Из буфера обмена рисунок можно вставить в рабочий лист Excel или в другой документ в качестве иллюстрации к документации модели.