Поддержка инженерных решений1. Лекция 1. Основная задача линейного программирования. Цель перехода к основной задаче линейного программирования (цзлп)
 Скачать 1.38 Mb.
|
|
Лекция №1. Основная задача линейного программирования. Цель перехода к основной задаче линейного программирования (ЦЗЛП). Любую задачу линейного программирования можно свести к форме ОЗЛП. ОЗЛП удобно, т. к. позволяет применить общий алгоритм для решения любых задач. ОЗЛП позволяет применяя препарат лин. алгебры заранее (до решения задач) определить имеет ли задача решение. ОЗЛП отличается: 1. Системой ограничений: Все неравенства стали равенством 2. Целевой функцией Пропал свободный член 3. Несколько отличается формулировка. Найти значение Х1, х2, …. Хn которые удовлетворяли бы ограничениям и обращали бы функцию в min. Исходная система ограничений. Введем новую переменную, которая будет меняться также - Переход от задачи линейного программирования к задачи ОЗЛП состоит из следующих этапов: 1. Приведения системы ограничений к форме « ». 2. Введение новых переменных y 1 , y 2 , … y k по числу неравенств. 3. Замена неравенств равенствами вида: И наложение ограничений Пример: Полученная задача запишется следующим образом: Найти такие неотрицательные , которые удовлетворяли бы системе (**) и обращались бы в минимум целевую функцию. Решение ОЗЛП. ОЗЛП не имеет решение если система (*) несовместна (уравнения противоречат друг другу) или система (*) совместна но не в положительной области значений варьируемых параметров (и Х и Y) (отсутствует допустимое решение) или допустимые решения есть, но нет оптимальных. Условия совместности системы (*). Система читается совместной, если значения ранга матрицы системы А и ранга расширенной матрицы системы А’ совпадают. Ранг системы (r s ) показывает число линейно независимых уравнений. Если r s =n, то система уравнений имеет единственное решение. Если при этом m>n (m>r s ), то m-r s – уравнений – линейно зависимы и их можно отбросить. Если r s , а остальные переменные выражают через них (их называют базисными). Свободным переменным можно придавать любые значения, базисные рассчитываются через свободные. Пример: Есть система уравнений В качестве свободных переменных выбраны - бесконечное множество решений – базисные переменные. Решения: 1) 2) Множество решений данной системы уравнений представляет собой точки внутри пространства варьируемых параметров. Каждая точка имеет 4-е координаты. № точки Х1 Х2 Х3 Х4 1 2 3 Если среди полученных решений (точек) нет таких, где все варьируемые параметры неотрицательные то допустимые решения задачи отсутствует. Если допустимые решения есть, то решается задача о поиске оптимального. Геометрическая интерпретация ОЗЛП. Геометрическая интерпретация ОЗЛП возможна в двух случаях: 1. (n-m=2) – на плоскости 2. – в 3-х мерном пространстве. Для каждого ограничения построим прямые. Если области перекрываются – уравнения совместны. Если задача не имеет такой области – решения нет. Для построения области допустимых решений в декартовой системе образуемой свободными переменными строят прямые соответствующие уравнениям из системы (*). Каждая прямая делит плоскость х 1 ох 2 на три подобласти: - на самой прямой соответствующее базисное переменное обращается в 0. По одну сторону от прямой она положительна по другую отрицательна. Положение этих областей зависит от коэффициентов а 11 , а 12 Случай 1. а 11 , а 12 – имеют разные знаки. Случай 2. а 11 , а 12 – имеют один знак. Пример построения ОДР. Пусть основная задача линейного программирования имеет систему ограничений. – в качестве свободных переменных. Для построения графика целевой функции eе необходимо выразить через свободные переменные. с с с с с с с с с с Для полученной ранее ОДР найдем значения х 1 , х 2 обращающие в минимум функцию: Выразим ее через свободные переменные: Из рисунка видно, что в направлении уменьшения целевой функции ее ограничивает т. А – крайняя, наиболее удаленная точка из ОДР. В этой точке функция становится минимальной и т. А является решением задачи оптимизации. Ф(А)=-64,5 Выводы из решения ОЗЛМ. Решения ОЗЛМ имеют следующие особенности: 1. Решение находится на границе ОДР 2. Если функция не ограничено убывает (возрастает) то задача плохо ограничена. 3. В редких случаях задача имеет бесконечное множество решений ( совпадает с границей). 4. В точке решения, по крайней мере n-r s – переменная обращается в 0. Лекция №2. Порядок работы вычислительного алгоритма для решения основной задачи для линейного программирования. (СИМПЛЕКС-МЕТОД). 1. Выделение свободных переменных. 2. Разрешение базисных переменных относительно свободных. 3. Обнуление свободных переменных (в точке решения обнуляются переменные в количестве соответствующем свободным). 4. Вычисление базисных переменных – получение опорной точки. 5. Проверка опорной дочки на допустимость. Если все базисные переменные оказались неотрицательными, то текущее решение (опорная точка) является допустимым. 6. Проверка опорной точки на оптимальность. Целевая функция выражается через свободные переменные и исследуется ее поведение в окрестности опорной точки. Если отклонение от опорной точки ухудшает значение целевой функции, то найденное решение оптимально. 7. Если опорная точка не является допустимой или оптимальной алгоритм повторяют с пункта «1». Применение Excel для решения задач линейного программирования. Процедура «Поиск решения». Элементы диалогового окна «Параметры поиска решения» Установить целевую ячейку Служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу. Равной Служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить число, введите его в поле. Изменяя ячейки Установить целевую ячейку Служит для указания ячеек, значения которых могут изменяться в процессе поиска решения до тех пор, пока наложенные ограничения задачи и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку, не будут выполнены. Предположить Используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки. Ограничения Ограничения Служит для отображения списка текущих ограничений для поставленной задачи. Добавить Служит для отображения диалогового окна Добавить ограничение. Изменить Служит для отображения диалогового окна Изменить ограничение. Удалить Служит для снятия указанного ограничения. Выполнить Служит для запуска поиска решения поставленной задачи. Закрыть Служит для выхода из диалогового окна без решения задачи. При этом сохраняются изменения, выполненные с использованием кнопок Параметры, Добавить, Изменить или Удалить. Параметры Служит для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения. Восстановить Служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используемых по умолчанию. Параметры поиска решения. Изменение способа поиска решения 1. В диалоговом окне Поиск решения нажмите кнопку Параметры. 2. В диалоговом окне Параметры поиска решения задайте один или несколько из следующих параметров. Время поиска и количество итераций 1. В поле Максимальное время введите число секунд, отведенное на время поиска решения задачи. 2. В поле Предельное число итераций введите максимальное допустимое количество итераций. ПРИМЕЧАНИЕ. При достижении границы отведенного временного интервала или при выполнении отведенного числа итераций на экране появляется диалоговое окно Текущее состояние поиска решения. Относительная погрешность В поле Точность введите степень точности. Чем меньше введенное число, тем выше точность результатов. Допустимое отклонение В поле Допустимое отклонение введите значение допустимого отклонения в процентах. Сходимость В поле Сходимость введите значение относительного изменения, при достижении которого в последних пяти итерациях поиск решения прекращается. Чем меньше это значение, тем выше точность результатов. ПРИМЕЧАНИЕ. Для получения дополнительных сведений о других параметрах, нажмите в диалоговом окне кнопку Справка. Нажмите кнопку ОК В диалоговом окне Поиск решения нажмите кнопку Выполнить или Закрыть. Элементы диалогового окна «Параметры поиска решения» Можно изменять условия и варианты поиска решения для линейных и нелинейных задач, а также загружать и сохранять оптимизируемые модели. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач. Максимальное время Служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах), не превышающее 32 767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач. Предельное число итераций Служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести значение, не превышающее 32 767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач. Относительная погрешность Служит для указания точности решений путем использования числа, вводимого в целях определения соответствия значения ограниченной ячейки целевому значению, нижней или верхней границам. Относительная погрешность должна быть задана десятичным значением от 0 (нуля) до 1. Чем больше десятичных знаков в заданном значении, тем выше точность — например, число 0,0001 задает более высокую точность, чем 0,01. Допустимое отклонение Процент, на который целевая ячейка решения, удовлетворяющая целочисленным ограничениям, может отличаться от действительного оптимального значения, но при этом рассматриваться приемлемой. Этот параметр применяется только для задач с целочисленными ограничениями. При большем допуске процесс решения ускоряется. Сходимость Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск решения останавливается. Сходимость применяется только к нелинейным задачам и должна отображаться дробным числом от 0 (нуля) до 1. Если введенное число содержит большее число десятичных знаков, показывается небольшая сходимость — например, 0,0001 является меньшим относительным изменением, чем 0,01. Чем меньше значение сходимости, тем больше времени требуется для поиска решения. Линейная модель Служит для ускорения поиска решения в случае, если все связи модели линейные и требуется найти решение для линейной задачи оптимизации. Неотрицательные значения Устанавливает нижний предел значений всех настраиваемых ячеек равным 0 (нулю), если для таких ячеек нижний предел не был установлен в поле Ограничение диалогового окна Добавление ограничения. Автоматическое масштабирование Служит для включения автоматического масштабирования входных и выходных значений, значительно различающихся по величине, например при максимизации прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей. Показывать результаты итераций Служит для приостановки поиска решения с целью просмотра результатов отдельных итераций. Оценка Служит для указания метода экстраполяции, используемого в целях получения исходных оценок значений базовых переменных в каждом одномерном поиске. Линейная Служит для использования линейной экстраполяции вдоль касательного вектора. Квадратичная Служит для использования квадратичной экстраполяции, которая дает лучшие результаты при решении нелинейных задач. Производные Служит для указания метода численного дифференцирования, используемого в целях вычисления частных производных целевых и ограничивающих функций. Прямые Используется в большинстве задач, где скорость изменения значений ограничения относительно невысока. Центральные Используется для задач, имеющих высокую скорость изменения ограничений. Данный способ требует больше вычислений, однако его применение может быть оправданным, если при поиске решений выдается сообщение о том, что получить более точное решение не удается. Метод Служит для выбора алгоритма, используемого при каждой итерации в целях определения направления поиска. Ньютона Реализация квазиньютоновского метода, в котором обычно запрашивается больше памяти, но выполняется меньше итераций, чем в методе сопряженных градиентов. Сопряженных градиентов Реализация метода сопряженных градиентов, в котором запрашивается меньше памяти, но обычно выполняется больше итераций, чем в методе Ньютона, чтобы достичь определенного уровня точности. Данный метод следует использовать, если задача достаточно велика и необходимо экономить память, а также если переход от итерации к итерации происходит медленно. Загрузить модель Служит для отображения диалогового окна Загрузить модель, в котором можно задать ссылку для загружаемой модели. Сохранить модель Служит для отображения на экране диалогового окна Сохранить модель, в котором можно задать ссылку на область ячеек, предназначенную для хранения модели. Данный вариант предусмотрен только для хранения на листе более одной модели оптимизации — первая модель сохраняется автоматически. Пример решения ЗЛП с помощью Excel. Из 5-ти компонентов составить смесь обладающую максимальной теплотворной способностью. При этом стоимость смеси не должна превышать 5700 у.е. на 100 тонн. Запасы компонентов не должны быть превышены. Исходные данные: Компонент Теплотворная способность Запасы Ценна за тонну Цена за хранение 1 тонны, у.е Стоимость транспортировки, у.е. 1 Ректан 11 750 18 100 12 15 2 11 550 10 90 14 15 3 11 000 50 18 10 10 4 11 000 40 20 35 15 5 10 000 18 15 40 15 Стоимость смеси - не более 5700 Количество смеси – 100 т. Варьируемые параметры х1, х2, …, х5 – масса компонентов смеси. Ограничения: х х х х х х х х х х т затраты: (100+12+15)*х1+(90+14+15)*х2+(18+10+10)*х3+(20+35+15)*х4+(15+40+15)*х5 <5700 Ц. Ф. Ф=11750*х1+11550*х2+11000*х3+11000*х4+10000*х5 ⟶max A B C D E F 1 Варьируемые параметры 2 1 2 3 4 5 3 4 Исходные данные 5 цена Стоимость смеси не более 5700 6 Транспорт 15 15 10 15 15 7 хранение 12 14 10 35 40 8 за вещество 100 90 18 20 15 9 теплотвор н. спос. 11750 11550 110 00 110 00 100 00 10 кол-во на складе 18 10 50 40 18 11 Промежуточные вычисления: 12 стоимость топлива =B3*(B6+B7+B8)+C3*(C6+C7+C8)+D3*(D6+D7+D8 )+E3*(E6+E7+E8)+F3*(F6+F7+F8) 13 Ц.Ф. =B3*B9+C3*C9+D3*D9+E3*E9+F3*+F9 =СУММПРОИЗВ( B3:F3;B9:F9) Нелинейное программирование. Найти оптимальное значение варьируемых параметров {X opt }при котором функция Ф({X opt })=extr и выполняется система ограничений G({X opt }). Для того чтобы задача была нелинейной необходимо чтобы хотя бы одно ограничение или целевая функция имели нелинейный вид. Задачи нелинейного программирования делят на 2 вида: - условная оптимизация (существует система ограничений G), - безусловная оптимизация (отсутствует система ограничений G), Решение безусловных задач проще, поэтому существуют приемы приведения задач условной оптимизации к безусловной форме. Метод штрафных функций. 1. Целевую функцию задачи заменяем другой. 2. Способы решения задач нелинейного программирования. 1. Линеаризация целевой функции и ограничений. 3. 2. Аналитические методы (дифференцирование). 4. 3. Методы поисковой оптимизации (неявный вид функции – функция сотоит из системы уравнений) Методы поисковой оптимизации. Для вычисления используется вычислительная техника. Такие методы называют методами |