Оптимизация линейной системы общего вида

Размещено на http://www.allbest.ru/

Москва 2008

Оптимизация линейной системы общего вида

1. Назначение разработки, область применения и её ограничения

Программно-методическая разработка по теме «Оптимизация линейной системы общего вида» предназначена для студентов бакалавриата, обучающихся по направлениям «Государственное и муниципальное управление», «Менеджмент», «Экономика и управление промышленным предприятием» и др. Пособие может быть использовано для изучения предметов «Основы математического моделирования социально-экономических процессов», «Экономико-математические методы и модели», «Программные средства решения экономических задач», и т.п. Пособие содержит описание компьютерной технологии моделирования и оптимизации многопродуктовой линейной балансовой экономической системы общего вида, в которой определены ограничения и выбран критерий оптимизации. Цель пособия - поддержка изучения базовых компьютерных технологий моделирования социально-экономических систем на уровне основных понятий теории оптимизации линейных экономических систем и практических методов решения задач линейной оптимизации общего вида в среде электронного табличного процессора EXCEL с применением программы «Поиск решения». Приведено детальное описание комплексной компьютерной модели общей задачи оптимизации и исследования оптимального решения в среде EXCEL, интерфейсы используемых программ EXCEL, схемы размещения исходных данных и промежуточных и окончательных результатов расчетов. Пособие может быть полезным также и для студентов магистратуры, аспирантов, преподавателей и всех, интересующихся применением компьютерных технологий для моделирования социально-экономических процессов и преподавания соответствующих дисциплин.

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

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

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

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

Математическая модель. Исключив из рассмотрения излишки, мы получаем задачу оптимизации, размерность которой значительно меньше размерности канонической задачи. В нашем случае имеем 2 аргумента вместо 7. Это объемы выпуска изделий первого и второго типа. С учетом описанных выше ограничений математическая модель теперь будет иметь вид

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

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

Применив процедуру стандартизации к нашей задаче, получаем

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

Видно, что теперь исходная задача имеет не 7, а 2 аргумента, соответственно двойственная задача имеет 2 функциональных ограничения вместо 7.

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

Двойственная задача в матричной форме будет

Здесь А - матрица удельных затрат, составленная из коэффициентов при аргументах в ограничениях исходной стандартной задачи. В - вектор запасов ресурсов. С - вектор коэффициентов целевой функции, или вектор прибыльностей изделий. Х - вектор аргументов исходной задачи. Y - вектор аргументов ДЗ. Z(X) и W(Y) - целевые функции исходной и двойственной задач оптимизации. Все операции теперь предполагаются матричными. Матричные соотношения в системах ограничений понимаются в смысле Парето (попарно между соответствующими элементами массивов). Заметим, что при необходимости математическую модель можно дополнить. Например, ввести в нее расчет избытков ресурсов и проч. Одновременно укажем, что обе задачи мы полагаем необходимым рассматривать совместно, в комплексе, что и будем учитывать при разработке технологии компьютерного моделирования.

Алгоритм. Не представляя детального алгоритма, отметим, что он включает в себя стандартные шаги - размещение аргументов исходной задачи Х; размещение исходных данных - матрицы удельных затрат А, вектора запасов В и вектора прибыльности С; программирование расчетов левых частей ограничений и целевой функции и применение программы «ПОИСК РЕШЕНИЯ» для вычисления оптимального плана исходной задачи. Затем, используя те же исходные данные, отводим блок ячеек для размещения аргументов двойственной задачи Y, программируем вычисления левых частей ограничений ДЗ и ее целевой функции; настраиваем и применяем «ПОИСК РЕШЕНИЯ».

Компьютерная модель. Общий вид комплексной компьютерной модели стандартной и двойственной задач оптимизации в матричной форме показан на рисунке.

Аргументы стандартной задачи размещены в блоке Х[В8:С8]. Исходные данные: матрица удельных затрат А[B12:C16]; вектор запасов ресурсов C[E12:E16] и вектор удельной прибыльности изделий C[B19:C19]. Для поиска оптимального плана программируется вычисление вектора расходов ресурсов D=AX[D12:D16] по формуле =МУМНОЖ(B12:C16;ТРАНСП(B8:C8)). Формула =МУМНОЖ(B19:C19;ТРАНСП(B8:C8)) вводится в ячейку [D19] для вычисления целевой функции стандартной задачи - прибыли Z(X)=CТX. Заметим, что в рассматриваемой схеме вектор Х, который должен быть вектор-столбцом, размещен в строке. Поэтому в обоих формулах второй сомножитель транспонируется. В блоке [F12:F16] размещена формула расчета величины излишков ресурсов =E12:E16-D12:D16 .

Рис. 1 Компьютерная модель задачи.

Компьютерная модель двойственной задачи строится на базе той же схемы размещения исходных данных. Аргументы ДЗ размещены в блоке Y[G12:G16]. Вектор правых частей ограничений ДЗ F=YTA размещен в блоке [B22:C22] и вычисляется как =МУМНОЖ(ТРАНСП(G12:G16);B12:C16). Для вычисления целевой функции двойственной задачи W(Y)=YTB в ячейку [D19] введена формула =МУМНОЖ(ТРАНСП(G12:G16);E12:E16).

На рисунке 2 показаны настройки программы «ПОИСК РЕШЕНИЯ» и компьютерная модель в режиме просмотра результатов расчетов после решения обеих задач - стандартной задачи оптимизации плана производства изделий и двойственной задачи.

Рис.2. Настройки программы "Поиск решения"

Анализ решения. Целевые функции обеих задач одинаковы, следовательно, обе задачи решены верно и решения оптимальны. Недефицитны второй, четвертый и пятый ресурсы. Увеличение запасов первого ресурса на единицу позволит получить прирост прибыли в размере 4 у.е.; третьего - на 6.

2. Используемые технические и программные средства

Для создания данного электронного продукта использовался персональный компьютер типа Intel Pentium IV c операционной системой Microsoft Windows XP Professional версия 2005 Service Pack 2. Использовался пакет MS-OFFICE с текстовым редактором MS-Word 2003 и MS-Excel 2003.

Размещено на Allbest.ru