Линейная оптимизация

Вычислительная математика

(методические указания к выполнениюиндивидуальных заданий)

Линейная оптимизация

1. Введение в линейное программирование

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

Одним из способов исследовать, к каким результатам приведут различные комбинации значений пе­ременных решений, является применение анализа "Что-если". Но мы хотим пойти дальше, и ответить на вопрос, какое решение будет "наилучшим'". При этом хотелось бы избежать бессистемного перебора различных альтернативных решений, при котором есть риск пропустить оптимальное решение. Однако полный перебор сценариев "Что-если" в диапазоне возможных решений для типичных моделей условной оптимизации быстро становится утомительным даже для самых рьяных приверженцев электронных таблиц. Кроме того, вам не удастся воспользоваться таблицами подстановки Excel для автоматиза­ции поиска, поскольку они позволяют изменять не более двух переменных одновременно.

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

Очевидно, что подавляющее большинство комбинаций переменных нас не интересует, поскольку' они нарушают одно или несколько ограничении мо­дели или дают слишком низкую прибыль. Но как выявить эти комбинации? Это трудно сделать с помошью анатиза "Что-если". В этом смысле оптимизационные модели сущест­венно отличаются от простых моделей. Необходимо найти быстрый и эффективный способ просмотра комбинаций переменных для поиска допустимых реше­ний. Для этого можно "перевернуть таблицу", сделав входы модели, используемые для по­строения сценариев "Что-если" (обычно это переменные решения), выходами. Это позво­лит прибегнуть к более эффективным процедурам поиска и избежать полного перебора многих тысяч комбинаций переменных.

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

Существуют эффективные методы поиска решений для моделей оптимизации с ли­нейными ограничениями. Модели с линейными ограничениями называются моделями линейного программирования (ЛП). Однако, прежде чем перейти непосредственно к про­цессу оптимизации моделей, следует уделить внимание представлению моделей ЛП в электронных таблицах. Мы рассмотрим: 1) методику формализации моде­лей ЛП; 2) правила представления моделей ЛП в электронных таблицах, которые упро­стят применение средства Excel Поиск решения; 3) использование средства Поиск реше­ния для оптимизации моделей ЛП.

Поиск по сайту: