апвр. Математическое программирование. Решение задачи линейного программирования 23 1 Описание постановки задачи 23 2 Формулировка экономикоматематической модели 24 3 Нахождение численного решения Поиска решений
![]()
|
титульник Содержание1. Нелинейное программирование 4 1.1 Постановка задачи нелинейного программирования 4 1.2 Критерии оптимальности в задачах с ограничениями 4 1.2.1 Задачи с ограничениями в виде равенств 5 1.2.2 Множители Лагранжа 6 1.3 Условия Куна-Таккера 11 1.3.1 Условия Куна–Таккера и задача Куна–Таккера 12 1.3.2 Интерпретация условий Куна – Таккера 14 1.3.3 Теоремы Куна–Таккера 16 Теорема 1. Необходимость условий Куна–Таккера 17 Теорема 2. Достаточность условий Куна–Таккера 20 2. Решение задачи линейного программирования 23 2.1 Описание постановки задачи 23 2.2 Формулировка экономико-математической модели 24 2.3 Нахождение численного решения «Поиска решений» 25 Заключение 30 Список литературы 31 Введение Современный этап развития человечества отличается тем, что на смену века энергетики приходит век информатики. Происходит интенсивное внедрение новых технологий во все сферы человеческой деятельности. Встает реальная проблема перехода в информационное общество, для которого приоритетным должно стать развитие образования. Изменяется и структура знаний в обществе. Все большее значение для практической жизни приобретают фундаментальные знания, способствующие творческому развитию личности. Важна и конструктивность приобретаемых знаний, умение их структурировать в соответствии с поставленной целью. На базе знаний формируются новые информационные ресурсы общества. Формирование и получение новых знаний должно базироваться на строгой методологии системного подхода, в рамках которого отдельное место занимает модельный подход. Возможности модельного подхода крайне многообразны как по используемым формальным моделям, так и по способам реализации методов моделирования. Физическое моделирование позволяет получить достоверные результаты для достаточно простых систем. В настоящее время нельзя назвать область человеческой деятельности, в которой в той или иной степени не использовались бы методы моделирования. Особенно это относится к сфере управления различными системами, где основными являются процессы принятия решений на основе получаемой информации. 1. Нелинейное программирование1.1 Постановка задачи нелинейного программированияВ задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной х=( ![]() ![]() а переменные ![]() ![]() ![]() Иногда в формулировке задачи ограничения (1) имеют противоположные знаки неравенств. Учитывая, однако, что если ![]() ![]() ![]() ![]() ![]() 1.2 Критерии оптимальности в задачах с ограничениямиРяд инженерных задач связан с оптимизацией при наличии некоторого количества ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой проводится поиск оптимума. На первый взгляд может показаться, что уменьшение размеров допустимой области должно упростить процедуру поиска оптимума. Между тем, напротив, процесс оптимизации становится более сложным, поскольку установленные выше критерии оптимальности нельзя использовать при наличии ограничений. При этом может нарушаться даже основное условие, в соответствии с которым оптимум должен достигаться в стационарной точке, характеризующейся нулевым градиентом. Например, безусловный минимум функции ![]() ![]() ![]() 1.2.1 Задачи с ограничениями в виде равенствРассмотрим общую задачу оптимизации, содержащую несколько ограничений в виде равенств: Минимизировать ![]() при ограничениях ![]() Эта задача в принципе может быть решена как задача безусловной оптимизации, полученная путем исключения из целевой функции k независимых переменных с помощью заданных равенств. Наличие ограничений в виде равенств фактически позволяет уменьшить размерность исходной задачи с n до n-k. В качестве иллюстрации рассмотрим следующий пример. Пример 1. Минимизировать ![]() при ограничении ![]() Исключив переменную ![]() ![]() min ![]() Метод исключения переменных применим лишь в тех случаях, когда уравнения, представляющие ограничения, можно разрешить относительно некоторого конкретного набора независимых переменных. При наличии большого числа ограничений в виде равенств, процесс исключения переменных становится весьма трудоемкой процедурой. Кроме того, возможны ситуации, когда уравнение не удается разрешить относительно переменной. В частности, если в примере 1 ограничение ![]() ![]() 1.2.2 Множители ЛагранжаС помощью метода множителей Лагранжа по существу устанавливаются необходимые условия, позволяющие идентифицировать точки оптимума в задачах оптимизации с ограничениями в виде равенств. При этом задача с ограничениями преобразуется в эквивалентную задачу безусловной оптимизации, в которой фигурируют некоторые неизвестные параметры, называемые множителями Лагранжа. Рассмотрим задачу минимизации функции n переменных с учетом одного ограничения в виде равенства: Минимизировать ![]() при ограничениях ![]() В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации: минимизировать L (x, u)=f(x) – u*h(x) (5) Функция L (х; u) называется функцией Лагранжа, u – неизвестная постоянная, которая носит название множителя Лагранжа. На знак u никаких требований не накладывается. Пусть при заданном значении u=u0 безусловный минимум функции L (x, u) по х достигается в точке ![]() ![]() ![]() ![]() Разумеется, необходимо подобрать значение u=u° таким образом, чтобы координата точки безусловного минимума х° удовлетворяла равенству (4). Это можно сделать, если, рассматривая u как переменную, найти безусловный минимум функции (5) в виде функции u, а затем выбрать значение u, при котором выполняется равенство (4). Проиллюстрируем это на конкретном примере. Пример 2 Минимизировать ![]() при ограничении ![]() Соответствующая задача безусловной оптимизации записывается в следующем виде: минимизировать L (x, u)= ![]() ![]() Решение. Приравняв две компоненты градиента L к нулю, получим ![]() ![]() Для того чтобы проверить, соответствует ли стационарная точка х° минимуму, вычислим элементы матрицы Гессе функции L (х; u), рассматриваемой как функция х, ![]() которая оказывается положительно определенной. Это означает, что L (х, u) – выпуклая функция х. Следовательно, координаты ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() При решении задачи из примера 2 мы рассматривали L (х; u) как функцию двух переменных ![]() ![]() ![]() в виде явных функций u получить нельзя, то значения х и u находятся путем решения следующей системы, состоящей из n+1 уравнений с n+1 неизвестными: ![]() ![]() Для нахождения всех возможных решений данной системы можно использовать численные методы поиска (например, метод Ньютона). Для каждого из решений ( ![]() Метод множителей Лагранжа можно распространить на случай, когда задача имеет несколько ограничений в виде равенств. Рассмотрим общую задачу, в которой требуется Минимизировать f(x) при ограничениях ![]() Функция Лагранжа принимает следующий вид: L (x, u)=f(x)- ![]() Здесь ![]() ![]() ![]() ………. ![]() Если найти решение приведенной выше системы в виде функций вектора u оказывается затруднительным, то можно расширить систему путем включения в нее ограничений в виде равенств ![]() ![]() ![]() Решение расширенной системы, состоящей из n+К уравнений с n+К неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция х, подобно тому, как это было проделано в случае задачи с одним ограничением. Для некоторых задач расширенная система n+К уравнений с n+K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что такие задачи на практике встречаются достаточно редко. 1.3 Условия Куна-ТаккераВ предыдущем разделе было установлено, что множители Лагранжа можно использовать при построении критериев оптимальности для задач оптимизации с ограничениями в виде равенств. Кун и Таккер обобщили этот подход на случай общей задачи нелинейного программирования с ограничениями, как в виде равенств, так и в виде неравенств. Рассмотрим следующую общую задачу нелинейного программирования: минимизировать ![]() при ограничениях ![]() ![]() Определение: Ограничение в виде неравенства ![]() ![]() ![]() ![]() Если существует возможность обнаружить ограничения, которые неактивны в точке оптимума, до непосредственного решения задачи, то эти ограничения можно исключить из модели и тем самым уменьшить ее размеры. Основная трудность заключается при этом в идентификации неактивных ограничений, предшествующей решению задачи. Кун и Таккер построили необходимые и достаточные условия оптимальности для задач нелинейного программирования, исходя из предположения о дифференцируемости функций ![]() 1.3.1 Условия Куна–Таккера и задача Куна–ТаккераНайти векторы ![]() ![]() ![]() ![]() ![]() ![]() Прежде всего проиллюстрируем условия Куна – Таккера на примере. Пример 3 Минимизировать ![]() при ограничениях ![]() Решение. Записав данную задачу в виде задачи нелинейного программирования (0) – (2), получим ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Уравнение (3), входящее в состав условий Куна–Таккера, принимает следующий вид: ![]() откуда ![]() Неравенства (4) и уравнения (5) задачи Куна – Таккера в данном случае записываются в виде ![]() ![]() ![]() Уравнения (5.16), известные как условие дополняющей нежесткости, принимают вид ![]() ![]() Заметим, что на переменные ![]() ![]() ![]() Таким образом, этой задачи условия Куна–Танкера записываются в следующем виде: ![]() 1.3.2 Интерпретация условий Куна – ТаккераДля того чтобы интерпретировать условия Куна – Таккера, рассмотрим задачу нелинейного программирования с ограничениями в виде равенств: минимизировать ![]() ![]() Запишем условия Куна–Таккера ![]() ![]() Далее рассмотрим функцию Лагранжа для задачи нелинейного программирования с ограничениями в виде равенств ![]() Для этой функции условия оптимальности первого порядка записываются в виде ![]() Нетрудно видеть, что условия Куна-Таккера (8) и (9) совпадают с условиями оптимальности первого порядка для задачи Лагранжа. Рассмотрим задачу нелинейного программирования с ограничениями в виде неравенств: минимизировать ![]() ![]() ![]() Запишем условия Куна–Таккера ![]() Соответствующая функция Лагранжа имеет вид ![]() Условия оптимальности первого порядка записываются как ![]() Заметим, что ![]() ![]() ![]() ![]() ![]() ![]() ![]() Если предположить, что ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Для того чтобы определить знак ![]() ![]() ![]() ![]() ![]() ![]() ![]() 1.3.3 Теоремы Куна–ТаккераВ предыдущем разделе построены условия Куна–Таккера для задач условной оптимизации. С помощью метода множителей Лагранжа получено интуитивное представление о том, что условия Куна – Танкера тесно связаны с необходимыми условиями оптимальности. В данном разделе рассматриваются строгие формулировки необходимых и достаточных условий оптимальности решения задачи нелинейного программирования. Теорема 1. Необходимость условий Куна–ТаккераРассмотрим задачу нелинейного программирования (0) – (2). Пусть ![]() ![]() ![]() ![]() ![]() Условие, согласно которому ![]() 1. Все ограничения в виде равенств и неравенств содержат линейные функции. 2. Все ограничения в виде неравенств содержат вогнутые функции, все ограничения-равенства – линейные функции, а также существует, по крайней мере, одна допустимая точка х, которая расположена во внутренней части области, определяемой ограничениями-неравенствами. Другими словами, существует такая точка х, что ![]() Если условие линейной независимости в точке оптимума не выполняется, то задача Куна–Таккера может не иметь решения. Пример 4 Минимизировать ![]() при ограничениях ![]() Решение. Изображена область допустимых решений сформулированной выше нелинейной задачи. Ясно, что оптимальное решение этой задачи есть ![]() ![]() Допустимая область в задаче 4. Так как ![]() Легко видеть, что векторы ![]() ![]() Запишем условия Куна–Таккера и проверим, выполняются ли они в точке (1, 0). Условия (3), (6) и (7) принимают следующий вид; ![]() ![]() ![]() ![]() ![]() ![]() При ![]() ![]() ![]() Заметим, что нарушение условия линейной независимости не обязательно означает, что точка Куна–Таккера не существует. Для того чтобы подтвердить это, заменим целевую функцию из этого примера функцией ![]() ![]() Нетрудно проверить, что точка ![]() Теорема о необходимости условий Куна–Таккера позволяет идентифицировать неоптимальные точки. Другими словами, теорему 1 можно использовать для доказательства того, что заданная допустимая точка, удовлетворяющая условию линейной независимости, не является оптимальной, если она не удовлетворяет условиям Куна–Таккера. С другой стороны, если в этой точке условия Куна–Таккера выполняются, то нет гарантии, что найдено оптимальное решение нелинейной задачи. В качестве примера рассмотрим следующую задачу нелинейного программирования. Следующая теорема устанавливает условия, при выполнении которых точка Куна–Таккера автоматически соответствует оптимальному решению задачи нелинейного программирования. Теорема 2. Достаточность условий Куна–ТаккераРассмотрим задачу нелинейного программирования (0) – (2). Пусть целевая функция ![]() ![]() ![]() ![]() Если условия теоремы 2 выполняются, то нахождение точки Куна–Таккера обеспечивает получение оптимального решения задачи нелинейного программирования. Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример: Минимизировать ![]() при ограничениях ![]() С помощью теоремы 2 докажем, что решение ![]() ![]() Так как матрица ![]() ![]() ![]() ![]() ![]() Поскольку матрица ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Точка ![]() ![]() Положив ![]() ![]() ![]() ![]() ![]() ![]() ![]() 2. Решение задачи линейного программирования2.1 Описание постановки задачиПредприятие производит для автомобилей ВАЗ запасные части типа А и В. Норма расхода ресурсов для производства каждого вида запасных частей, а также отведенные лимиты ресурсов приведены в таблице. Производственная мощность позволяет выпускать максимум 3500 деталей типа А. Табл. 1. Исходные данные
нелинейный р максимальный доход Определить, сколько деталей каждого вида следует производить, чтобы обеспечить максимальный доход от продажи за неделю через Simplex-метод и «Поиск решений» используя средства Microsoft Excel. 2.2 Формулировка экономико-математической моделиДля решения данной задачи составим экономико-математическую модель, используя исходные данные, приведенные в табл. 1. Обозначим x1; x2 – нормы расхода ресурсов на производство детали. Для их изготовления потребуется: 4х1+3х2 – трудозатраты 2х1+6х2 - листовой материал 5 х1+2 х2 - полимерные материал Так как использование норм расхода ресурсов на производство детали не должно превышать лимит ресурсов то связь выразится следующей системой неравенств: ![]() По смыслу задачи ![]() ![]() Необходимо найти сколько деталей каждого вида следует производить, чтобы обеспечить максимальный доход от продажи за неделю удовлетворяющий системе (1) и условию (2) при котором функция (3) принимает максимальное решение. 2.3 Нахождение численного решения «Поиска решений»В MS Excel составляем таблицу с исходными данными: ![]() В ячейки D2; D3; D4 вводим соответственно: =СУММПРОИЗВ (B2:C2;$B$6:$C$6) =СУММПРОИЗВ (B3:C3;$B$6:$C$6) =СУММПРОИЗВ (B4:C4;$B$6:$C$6) Затем заходим на вкладку Данные и выбираем «Поиск решений»; в появившемся окне последовательно выбираем изменяемые ячейки: ![]() И добавляем необходимые нам ограничения: ![]() ![]() В параметрах поиска решений выбираем «Линейная модель»: ![]() Систему неравенств: ![]() Приводим к каноническому виду: ![]() ![]() ![]() ![]() В MS Excel заполняем: 1. Simplex-таблицу: ![]() ![]() 2. Simplex-таблица: ![]() ![]() 3. Simplex-таблица: ![]() ![]() Так как в последней строке ![]() Результат: F(x)=21634,61 X1=807 X2=980,7 Данный результат почти идентичен результату, полученному при нахождение численного решения «Поиска решений», что подтверждает правильность решения данной задачи линейного программирования. ЗаключениеПроцесс проектирования информационных систем, реализующих новую информационную технологию, непрерывно совершенствуется. В центре внимания инженеров-системотехников оказываются все более сложные системы, что затрудняет использование физических моделей и повышает значимость математических моделей и машинного моделирования систем. Машинное моделирование стало эффективным инструментом исследования и проектирования сложных систем. Актуальность математических моделей непрерывно возрастает из-за их гибкости, адекватности реальным процессам, невысокой стоимости реализации на базе современных ПЭВМ. Все большие возможности предоставляются пользователю, т.е. специалисту по моделированию систем средствами вычислительной техники. Особенно эффективно применение моделирования на ранних этапах проектирования автоматизированных систем, когда цена ошибочных решений наиболее значительна. Современные вычислительные средства позволили существенно увеличить сложность используемых моделей при изучении систем, появилась возможность построения комбинированных, аналитико-имитационных моделей, учитывающих все многообразие факторов, имеющих место в реальных системах, т.е. использованию моделей, более адекватных исследуемым явлениям. Список литературы |