Линейное программирование. Методы нелинейной оптимизации
Линейные математические модели, формы и графическое решение задач линейного программирования. Сущность симплекс-метода решения задач и метода искусственного базиса, теория двойственности и оптимизации. Нелинейное программирование и условный экстремум.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 26.04.2014 |
| Размер файла | 1,5 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Пример:
Предприятие может работать по двум технологиям. При этом используются два типа ресурсов. Запасы ресурсов составляют 12 тонн и 4 литра соответственно. За 1 час работы по первой технологии расходуется 2 тонны первого ресурса и 1 литр второго, а за 1 час работы по второй технологии - 1 тонна первого ресурса. 1 час работы по первой технологии приносит доход 8 тыс. руб., а по второй - 3 тыс. руб. Суммарное время работы по технологиям должно составлять 6-часовую смену. Определить время работы по каждой технологии так, чтобы суммарный доход был наибольшим.
· Математическая модель
[час] - время работы по каждой технологии
· Построим двойственную задачу.
· Проверим, является ли оптимальным решение .
Для этого запишем соотношения дополняющей не жесткости . Подставим в эти соотношения компоненты решения
Решая данную систему уравнений, получим . Подставим в ограничения двойственной задачи. Первое ограничение не выполняется:
Мы получили, что найденное нами решение не является допустимым для двойственной задачи. Поэтому можно сделать вывод, что решение не является оптимальным решением исходной задачи.
· Предположим, что нам известно оптимальное решение прямой задачи , тогда найдем :
Таким образом, мы получили оптимальное решение двойственной задачи .
5.3 Анализ чувствительности оптимального решения к изменению свободных членов ограничений
Пусть исходная задача дана в канонической форме:
1.
Тогда двойственная к ней будет иметь вид:
2.
Конечно, оптимальное решение зависит от исходных параметров, поэтому его можно рассматривать как неявно заданную функцию исходных параметров .
Изучим влияние пока только одного параметра - вектора на оптимальное решение .
Пусть правые части ограничений (ресурсы) меняются, получая малые приращения:
- возмущенный вектор правых частей ограничений.
- (малые) приращения ресурсов.
Тогда задача с новым вектором правых частей ограничений (возмущенная задача) I' и двойственная к ней II' запишутся в виде
Лемма: пусть - невырожденное оптимальное решение задачи I и - базисная матрица этого плана .
Если выполняется условие , то:
· оптимальным решением возмущенной задачи является вектор
, .
· оптимальное решение двойственной задачи не меняется .
Доказательство:
Пусть - оптимальное решение, - его базисная матрица. Значит, существует и обратная матрица , базисные компоненты оптимального плана -, выполняется признак оптимальности .
Покажем, что вектор - оптимальное решение возмущенной задачи.
Сначала покажем, что это допустимое решение, то есть для него должны выполняться ограничения.
Подставляя в левую часть, получим
,
то есть ограничение выполняется.
Итак, - допустимое решение задачи.
Покажем, что это оптимальное решение. Проверим признак оптимальности. Оценки свободных переменных возмущенной задачи совпадают с оценками свободных переменных исходной задачи , так как в формулах их расчета не участвуют свободные члены ограничений, а остальные параметры обеих задач совпадают
Значит, признак оптимальности выполняется и это есть оптимальное решение возмущенной задачи.
Первая часть леммы доказана.
Справедливость второй части следует из того, что формулы расчета оптимальных решений задач, двойственных задач также совпадают.
Лемма доказана.
Область устойчивости двойственных оценок по отношению к изменению свободных членов ограничений - множество правых частей ограничений, при которых решение двойственной задачи не меняется.
Теорема 3 (теорема об оценках, теорема о чувствительности): компоненты оптимального решения двойственной задачи являются оценками влияния свободных членов ограничений на оптимальное значение целевой функции.
Доказательство:
Рассмотрим оптимальное значение критерия как функцию от правых частей ограничений
По первой теореме двойственности критерии на оптимальных решениях прямой и двойственной задач равны
Будем рассматривать малые приращения правых частей ограничений, лежащие в области устойчивости двойственных оценок , тогда по доказанной выше лемме решение двойственной задачи не меняется и в правой части ( ) bi - переменные, а yi - константы.
Возьмем производную по bi от левой и правой части ( ), получим
Теорема доказана.
Экономическая интерпретация третьей теоремы двойственности
Если соотношение выполняется, то .
То есть если ресурс изменился на 1 , то .
Из соотношения следует, что компонента оптимального решения двойственной задачи показывает, на сколько изменится оптимальное значение критерия при увеличении ресурса на 1.
Двойственные переменные называют также двойственными оценками, модельными ценами, теневыми ценами.
Разлагая функцию оптимального значения критерия в ряд по формуле Тейлора в окрестности , получим
В области устойчивости двойственных оценок приращение критерия может быть получено по формуле
Пример:
Для задачи из раздела 5.2 о работе предприятия по двум технологиям, определим, как изменится оптимальное решение при изменении объемов используемых ресурсов
Математическая модель задачи:
Найдем оптимальное решение этой задачи методом искусственного базиса.
Для этого строим расширенную задачу:
Решение в симплекс-таблицах:
Ранее было найдено оптимальное решение двойственной задачи:
Найти оптимальное решение данной задачи, если вектор ресурсов изменился:
,
Базисная матрица оптимального плана
Обратную к ней возьмем из оптимальной симплекс-таблицы под единичной матрицей исходной симплекс-таблицы.
Проверим, что эти матрицы взаимно обратные:
Базисные компоненты решения измененной задачи
неотрицательны, значит по лемме 3 это базисные компоненты оптимального плана измененной задачи
В новых условиях по первой технологии следует работать 5 часов, по второй - 3 часа. Останется неиспользованной одна тонна первого ресурса.
Приращение оптимального значения критерия
Доход на новом оптимальном плане
Построение областей устойчивости двойственных оценок
Интервал устойчивости двойственных оценок к изменению компоненты вектора ограничений - такой интервал изменения этой компоненты, внутри которого решение двойственной задачи не меняется.
Для рассмотренной задачи найдем интервал устойчивости двойственных оценок к изменению запаса второго ресурса:
Получили интервал устойчивости в приращениях
,
А непосредственно интервал устойчивости
Это означает, что при уменьшении запасов второго ресурса до нуля или увеличении до 6 оценки всех ресурсов сохранят свои значения , а приращение критерия можно найти по формуле
Построим область устойчивости двойственных оценок к изменению всех ресурсов.
Напомним, что область устойчивости двойственных оценок к изменению правых частей ограничений - множество значений правых частей ограничений, при которых двойственные оценки не меняются.
Область устойчивости определяется условиями
Подставляем сюда
Для приращений ресурсов получаем систему неравенств
Неравенства (1) и определяют область устойчивости в трехмерном пространстве приращений ресурсов.
Если меняется только один ресурс, область устойчивости обращается в интервал устойчивости двойственных оценок к изменению этого ресурса.
Пусть меняется только второй ресурс:
- интервал устойчивости двойственных оценок к изменению второго ресурса.
Пусть меняется только третий ресурс:
- интервал устойчивости двойственных оценок к изменению третьего ресурса.
Построим область устойчивости двойственных оценок к одновременному изменению второго и третьего ресурсов:
Из графика видно, что область устойчивости (в приращениях ресурсов) высекает на осях координат интервалы устойчивости. При изменении приращений ресурсов внутри этой области сохраняется неизменным (устойчивым) решение двойственной задачи , сохраняется базис оптимального плана , а компоненты (базисные) оптимального плана меняются по формулам .
Найдем новое оптимальное решение при конкретных изменениях ресурсов внутри области устойчивости.
Пусть
Тогда приращение оптимального значения критерия
Базисные компоненты оптимального решения
,
а полный вектор нового оптимального решения
Экономическая интерпретация полученного решения:
При уменьшении запасов второго ресурса (катализатора) на 2 литра и одновременном увеличении длительности рабочей смены на 3 часа, по первой технологии следует работать 2 часа, по второй - 7 часов, при этом максимально возможный доход составит 37 тысяч рублей. Тонна первого ресурса останется неиспользованной.
5.4 Определение оптимального решения двойственной задачи из оптимальной симплекс-таблицы прямой
Пусть исходная задача дана в канонической форме
Оптимальное решение получено симплекс-методом, - базисная матрица оптимального решения.
Оптимальное решение двойственной задачи (по первой теореме двойственности)
,
элементы строки оценок в оптимальной симплекс-таблице прямой задачи вычисляются по формулам
Памятуя о том, что ограничение двойственной задачи, соответствующее переменной прямой задачи, имеет вид
,
,
выводим важное свойство оценок :
Оценка переменной в симплекс-таблице равна разнице левой и правой части соответствующего ограничения двойственной задачи.
Из соотношения легко найти компоненты оптимального решения двойственной задачи.
Действительно, пусть - единичный вектор с единицей в i-ой строке. В исходной симплекс-таблице всегда есть такие вектора.
Оценка переменной согласно (6) запишется
,
Откуда
Таким образом, для определения компоненты оптимального решения двойственной задачи следует в исходной симплекс-таблице выбрать единичный столбец с единицей в i-ой строке. Тогда компонента равна оценке переменной из оптимальной симплекс-таблицы плюс коэффициент критерия этой переменной
Пример:
Найдем оптимальное решение двойственной задачи к задаче раздела 5.2 о работе предприятия по двум технологиям.
Воспроизведем для наглядности решение симплекс-методом
Единичная матрица в исходной симплекс таблице расположена в столбцах 3, 4, 5.
Оптимальное решение двойственной задачи будет находиться в строке оценок оптимальной симплекс-таблицы под единичной матрицей исходной симплекс-таблицы:
5.5 Двойственный симплексный метод
Рассмотрим базисное недопустимое решение .
Пусть все оценки на этом решении неотрицательные . Такое базисное решение называется псевдо-планом или псевдо-оптимальным решением. У него значение критерия лучше, чем у оптимального, но оно является недопустимым.
Для этого решения
,
А это означает, что псевдо-план исходной задачи соответствует опорному плану двойственной задачи: . При этом каждому псевдо-плану исходной задачи соответствует угловая точка двойственной.
Двойственная задача может быть решена симплекс-методом.
Двойственный симплекс-метод решения прямой задачи использует соответствующее решение двойственной задачи, но операции выполняются в симплекс-таблице исходной задачи. Перемещение происходит от одного псевдо-плана к другому с приближением к области. Когда очередное базисное решение станет допустимым, будет получено оптимальное решение.
Если симплексный метод - метод последовательного улучшения плана (улучшаются планы ), то двойственный симплекс-метод - метод последовательного улучшения оценок (улучшаются решения двойственной задачи - двойственные оценки ).
Условия применимости двойственного симплекс-метода:
· в матрице условий задачи, записанной в канонической форме, должна быть единичная подматрица, при этом правые части ограничений не обязаны быть положительными.
· все оценки должны быть неотрицательны, если задача на максимум, и неположительны, если задача на минимум.
Итерации в двойственном симплекс-методе выполняются по следующим правилам:
· определяется переменная , выводимая из списка базисных. Она определяется по отрицательной компоненте . Если их несколько, то лучше брать максимальную по модулю.
· определяется свободная переменная , вводимая в список базисных. При этом разрешающий столбец определяется по минимальному по модулю отношению оценок свободных переменных к отрицательным коэффициентам разрешающей строки.
Это правило гарантирует, что новое базисное решение будет псевдо-планом.
· далее выполняются операции однократного замещения (как и в симплекс-методе) с разрешающим элементом .
· процесс повторяется до тех пор, пока очередное базисное решение не станет допустимым.
Замечание: если в разрешающей строке нет отрицательных элементов, то область допустимых решений пуста.
Пример:
1. Содержательное описание.
Целлюлозно-бумажный комбинат (ЦБК) на берегу озера Байкал может работать по двум технологическим режимам. По первому режиму в течение смены расходуется 100 м3 древесины, производится 50 тонн целлюлозы, 60 центнеров лигнитов (вещества, используемые в химической промышленности) и сбрасывается в озеро 10 кг отравляющих веществ. По второму режиму в течение смены расходуется 120 м3 древесины, производится 75 тонн целлюлозы, 30 центнеров лигнитов, сбрасывается в озеро 25 кг отравляющих веществ. Годовой план производства составляет 15000 тонн целлюлозы, 1200 тонн лигнитов. Предельные годовые нормы выброса отравляющих веществ составляют 5 тонн. Определить годовой план работы ЦБК, требующий минимального расхода древесины.
2. Математическая модель.
· Управляемые параметры.
[см] - время работы (в сменах) по первой технологии;
[см] - время работы (в сменах) по второй технологии;
- годовой план работы.
2.2 Ограничения:
- годовое производство целлюлозы в тоннах должно быть не меньше плана;
- годовое производство лигнитов в центнерах должно быть не меньше плана;
- годовой выброс отравляющих веществ в килограммах не должен превосходить предельно-допустимых норм выброса.
- время работы по каждой из технологий неотрицательно
3. Формулировка цели.
- годовой расход древесины должен быть минимален
Получили следующую задачу линейного программирования
Приведем ее к каноническому виду
- очевидное базисное решение, но оно не является допустимым.
Обеспечим условия применения двойственного симплекс-метода. Сменим знаки левых и правых частей первых двух уравнений
Занесем данные в симплекс-таблицу. Видим, что оценки переменных в последней строке первой симплекс-таблицы не положительны, то есть базисное решение является псевдо-планом, условия применимости двойственного симплекс-метода выполняются.
- псевдо-план.
На первой итерации выбирается первая разрешающая строка (-15000<0) и второй разрешающий столбец (120/75<100/50). Выполняются операции однократного замещения. Получаем следующее приближение к области.
На второй итерации разрешающая строка вторая (-6000,0), разрешающий столбец первый (20/40=0.5< 8/5:2/5=4).
Следующее решение
- допустимое базисное, значит оптимальное.
Экономическая интерпретация полученного решения: для обеспечения минимального расхода древесины нужно работать 150 смен по первой технологии, 100 смен по второй технологии, при этом расход древесины будет составлять 27000 м3. Производство целлюлозы и лигнитов совпадает с плановым (так как x3=x4=0), выброс отравляющих веществ на 1000 кг меньше предельно-допустимых норм выброса.
Построим двойственную задачу. Для применения правил построения двойственных задач необходимо согласовать знаки неравенств с типом критерия:
Введем переменные двойственной задачи:
- оценка полезности 1 тонны целлюлозы;
- оценка полезности 1 центнера лигнитов;
- оценка «полезности» 1 кг отравляющих веществ. Значение у3 на оптимальном плане будет показывать, на сколько изменится критерий при увеличении b3 на единицу (с -5000 до -4999). В терминах исходной задачи - это приращение расхода древесины от ужесточения (уменьшения) предельно допустимых норм выброса отравляющих веществ на один килограмм.
Тогда двойственная задача запишется в виде
Найдем оптимальное решение двойственной задачи из оптимальной симплекс-таблицы прямой задачи:
Казалось бы, полученное решение опровергает теорию получения оптимального решения двойственной задачи из оптимальной симплекс-таблицы прямой. Полученное решение даже недопустимое - нарушаются условия не отрицательности.
Действительно, - это не оптимальное решение задачи, двойственной к задаче. Вектор - это оптимальное решение задачи, двойственной к задаче. Именно эта задача представлена в исходной симплекс-таблице.
Хотя задачи эквивалентны, имеют совпадающие области допустимых решений, но формы представления задач разные и двойственные к ним задачи будут отличаться не только формой, но и значением оптимальных решений. Однако оптимальные решения этих задач легко могут быть получены друг из друга.
Построим двойственную задачу к задаче:
После замены переменных:
Таким образом, если из симплекс-таблицы получено оптимальное решение задачи, двойственной к задаче, то решение двойственной к задаче может быть получено сменой знаков компонент решения:
Экономический смысл двойственных переменных
показывает, что при увеличении плана выпуска целлюлозы на 1 тонну расход древесины возрастет на 1.4 м3.
показывает, что при увеличении плана выпуска лигнитов на 1 центнер расход древесины возрастет на 0.5 м3.
показывает, что при уменьшении годовых предельно допустимых норм выброса отравляющих веществ на 1 килограмм расход древесины не изменится. Действительно, на оптимальном решении ограничение по выбросу отравляющих веществ не активное, выброс (4000) не достигает предельной нормы (5000), поэтому уменьшение нормы не только на 1, но и на величину в пределах 1000 килограммов не повлияет на оптимальный план работы комбината.
Полученные оценки влияния рассмотренных параметров на оптимальное значение критерия справедливы в области устойчивости двойственных оценок.
6. Послеоптимизационный анализ задачи линейного программирования
Пусть исходная задача решена, получено ее оптимальное решение и оптимальное решение двойственной к ней задачи:
Представляет интерес то, как меняются характеристики оптимального решения при изменении условий планирования. Исследованием этих вопросов и занимается послеоптимизационный (постоптимизационный) анализ.
Послеоптимизационный анализ предполагает решение следующих задач:
· Анализ чувствительности оптимального решения к изменению правых частей ограничений (запасов ресурсов);
· Анализ чувствительности оптимального решения к изменению коэффициентов критерия (цен);
· Анализ чувствительности оптимального решения к изменению технологических коэффициентов;
· Добавление новых переменных;
· Добавление нового ограничения.
Пусть исходная задача дана в канонической форме
Двойственная к ней будет иметь вид
Первый вид анализа - анализ чувствительности оптимального решения к изменению правых частей ограничений уже рассмотрен в разделе 5.3. Он является основой для понимания смысла двойственных переменных.
Рассмотрим другие виды анализа.
6.1 Добавление нового ограничения
Пусть в математической модели задачи появилось новое ограничение
Возможны две ситуации:
· Если прежнее оптимальное решение удовлетворяет новому ограничению, то это решение оптимальное и для измененной задачи:
· Если прежнее оптимальное решение не удовлетворяет новому ограничению , то в таком случае прежнее оптимальное решение является базисным недопустимым решением и является псевдо-планом. Поэтому решение новой задачи может быть получено двойственным симплексным методом.
Для этого требуется новое ограничение привести к виду уравнения.
Включим новое ограничение в оптимальную симплекс-таблицу. Но прежде исключим из этого уравнения базисные переменные, чтобы в симплекс-таблице столбцы при базисных переменных были единичными.
Пример:
В задаче о работе ЦБК учтем ограничения на кислотные выбросы в атмосферу. Известно, что по первой технологии за 1 смену выбрасывается 1 кг кислотных выбросов, по второй - 3 кг. При этом предельно допустимые годовые нормы выброса составляют 360 кг.
В математической модели появится новое ограничение
,
а вся система ограничений примет вид
Проверим, удовлетворяет ли прежнее оптимальное решение новому ограничению:
Ограничение не выполняется.
Преобразуем его к виду уравнения, введя балансовую переменную x6
Заменим в этом уравнении базисные переменные x1, x2 их значениями через свободные из оптимальной симплекс-таблицы
Уравнение примет вид
Включаем его в оптимальную симплекс-таблицу и решаем далее двойственным симплекс-методом
На следующей итерации получаем новое оптимальное решение
В новых условиях комбинат должен работать 240 смен по первой технологии, 40 смен по второй. Расход древесины возрастет до 28800 м3.
6.2 Добавление новой переменной
Пусть в математической модели (1-3) появилась новая переменная
В задаче объемного планирования это означает возможность производить новый вид продукции с известными затратами ресурсов и известным доходом от единицы продукции. Сохранится ли прежнее оптимальное решение? Если нет, то, как найти новое оптимальное решение?
Если в исходной задаче появляется новая переменная, то в двойственной задаче появляется новое ограничение
Вектор - прежнее оптимальное решение с нулевой n+1-ой компонентой является допустимым решением новой задачи. Если выполняется условие, то вектор - прежний вектор оптимальных двойственных оценок - допустимое решение двойственной к задачи. Соотношения дополняющей нежесткости для этих двух решений пополнились условием
и выполняются за счет . Значит, решение - оптимальное для новой задачи.
Этому выводу можно дать экономическое обоснование. Выполнение условия означает, что затраты на единицу новой продукции превышают доход. Значит, такую продукцию производить не выгодно, , прежнее оптимальное решение не меняется.
Если ограничение не выполняется, затраты на единицу новой продукции меньше дохода, , то такую продукцию следует производить, объем производства нужно увеличивать.
Для получения нового оптимального решения следует дополнить прежнюю оптимальную симплекс-таблицу новым столбцом
,
а оценку переменной найти как разность левой и провой части ограничения двойственной задачи
В полученной симплекс-таблице признак оптимальности не выполняется (), переменную нужно вводить в список базисных и далее решать задачу симплекс-методом.
Пример:
Предположим, что у ЦБК появилась возможность работать по третьей технологии с расходом за смену 103 кубометра древесины, производительностью в смену 60 тонн целлюлозы, 40 центнеров лигнитов и 20 килограммов отравляющих веществ.
, .
Обозначив - время работы по третьей технологии, ищем решение в виде для новой математической модели
Новая переменная порождает в двойственной задаче новое ограничение
Проверим, удовлетворяет ли этому ограничению вектор оптимальных двойственных оценок исходной задачи:
Ограничение не выполняется, суммарная оценка полезности произведенной за смену продукции (104 м3) превышает затраты (103м3), значит прежнее решение не является оптимальным.
Для определения нового оптимального решения включим в прежнюю оптимальную симплекс таблицу столбец с переменной .
В исходную симплекс-таблицу новый вектор условий войдет в виде
, так как менялись знаки в первых двух уравнениях (см. раздел 5.5). В оптимальной симплекс-таблице он преобразуется к виду
Оценка переменной определится как разность левой и правой части ограничения двойственной задачи
Оценка положительна, что нарушает условие оптимальности опорного плана. Решаем далее симплекс-методом
На следующей итерации получим оптимальное решение новой задачи
,
Комбинат должен работать 75 смен по первой технологии, 187.5 смен по третьей дополнительной технологии. При этом расход древесины будет наименьшим и составит 26812.5 кубометров.
6.3 Изменение коэффициентов критерия
Влияние изменения коэффициентов критерия на оптимальное решение задачи хорошо видно на графике в пространстве двух управляемых параметров. Оптимальное решение не меняется, если вектор коэффициентов критерия (градиент функции) меняется в конусе градиентов активных ограничений.
Если меняется только коэффициент (пусть это цена второго вида продукции), то
· при оптимальное решение переходит в другую угловую точку области допустимых решений.
· при оптимальное решение также меняется.
· при оптимальное решение остается неизменным.
Как найти оптимальное решение задачи с измененными коэффициентами критерия, используя оптимальную симплекс-таблицу исходной задачи?
Пусть, для простоты, меняется только один коэффициент критерия. Будем отдельно рассматривать два случая:
· Меняется коэффициент критерия при свободной переменной оптимального плана
· Меняется коэффициент критерия при базисной переменной оптимального плана:
Симплекс-таблица оптимального плана . Имеет вид
Изменение коэффициента критерия при свободной переменной
Пусть меняется коэффициент критерия при свободной переменной :
Оценки в симплекс-таблице вычисляются по известной формуле
Если меняется коэффициент при свободной переменной, то вектор коэффициентов при базисных переменных не меняется. Поэтому в симплекс-таблице меняется только одна оценка - при переменной
Для оптимальности решения она должна оставаться неотрицательной (в задаче максимизации).
Поэтому прежнее решение остается оптимальным, если .
Если , то тогда , прежнее решение не оптимальное и нужно выполнить несколько итераций симплекс-метода для получения нового оптимального решения.
Пример:
В плане работы ЦБК, работающем по трем технологиям с затратами древесины по третьей технологии 110 м3 в смену, определить в каких пределах может меняться расход древесины по третьей технологии, чтобы при этом прежнее решение оставалось оптимальным.
Симплекс-таблица для оптимального решения этой задачи имеет вид
Таким образом, мы пришли к выводу, что оптимальное решение сохраняется, если расход древесины не менее 104 м3.
Найдем оптимальное решение, лежащее вне этого интервала.
Пусть расход древесины удалось уменьшить до
Выполняя одну итерацию симплекс-метода, получим новое оптимальное решение
Изменение коэффициента критерия при базисной переменной
Пусть меняется коэффициент критерия при базисной переменной :
Так как переменная - базисная переменная, то меняется вектор коэффициентов при базисных переменных , в симплекс-таблице меняется крайний левый столбец. Это повлечет изменение большинства оценок свободных переменных. Новые оценки вычисляются следующим образом:
Из этой системы неравенств находим интервал - интервал неизменности (устойчивости) оптимального решения.
Пример:
Пусть в плане работы ЦБК по двум технологиям меняется расход древесины во время работы по второй технологии. В каких пределах можно изменять расход, чтобы прежнее решение оставалось оптимальным?
Получили, что прежнее решение остается оптимальным, если расход древесины по второй технологии меняется в пределах от 50 до 150 кубометров в смену.
6.4 Изменение технологических коэффициентов
Рассмотрим влияние на оптимальное решение изменения матрицы технологических коэффициентов
Пусть меняется один технологический коэффициент
Так же, как в предыдущем разделе следует рассмотреть два случая
Изменение технологических коэффициентов при базисной переменной
Изменение коэффициента при базисной переменной меняет базисную матрицу оптимального плана. Меняется и матрица, обратная к базисной, которая используется в расчете основных характеристик оптимального решения как прямой, так и двойственной задач.
Вычислительные затраты на пересчет матрицы, обратной к базисной, сопоставимы с затратами на повторное решение задачи симплекс-методом, поэтому не существует более эффективного способа получения оптимального решения измененной задачи.
Изменение технологических коэффициентов при свободной переменной
Пусть меняются технологический коэффициент при свободной переменной .
Такое изменение технологического коэффициента не меняет базисную матрицу.
В оптимальной симплекс-таблице изменится только один столбец при переменной . Его следует вычислить по формуле
Посмотрим, как изменится оценка свободной переменной :
Полученное неравенство является условием сохранения прежнего оптимального решения для задачи максимизации.
Пример:
Пусть в плане работы ЦБК по трем технологиям c затратами древесины 100, 120, 110 м3 меняются объемы производства целлюлозы за смену работы по третьей технологии.
В первой симплекс-таблице
.
Оптимальная симплекс-таблица до изменения
В этой таблице следует пересчитать оценку :
Таким образом, если производство целлюлозы за смену по третьей технологии будет уменьшаться до нуля или увеличиваться до 64.286 м3, оптимальный план останется прежним , третья технология не будет использоваться.
Если производительность третьей технологии превысит 64.286 м3, она будет использоваться, оптимальное решение изменится. Новое оптимальное решение можно будет найти, изменив в оптимальной симплекс-таблице столбец 3 и продолжив решение симплекс-методом.
7. Классическая теория оптимизации
Задача математического программирования
называется задачей нелинейного программирования, если функция цели или хотя бы одна из функций ограничений не линейна.
Точка называется точкой локального экстремума, если существует - окрестность этой точки , для которой ,.
Точка называется точкой глобального экстремума, если для любого .
Функция называется унимодальной (одноэкстремальной), если у этой функции имеется только один локальный экстремум. В противном случае она называется многоэкстремальной.
В классической теории оптимизации рассматриваются экстремальные задачи без ограничений, то есть область D совпадает со всем n-мерным пространством вещественных чисел .
Рассмотрим задачу безусловной оптимизации
В случае достаточной дифференцируемости функции можно сформулировать необходимые и достаточные условия локального экстремума.
7.1 Необходимые условия оптимальности
Для функции одной переменной справедлива следующая теорема.
Теорема 1: для того, чтобы функция одной переменной имела в точке локальный экстремум, необходимо, чтобы производная функции в этой точке была равна нулю.
Аналогичная теорема справедлива для функции многих переменных.
Теорема 2: для того, чтобы функция имела в точке локальный экстремум, необходимо, чтобы все ее частные производные в этой точке обращались в ноль
Другими словами, вектор градиента функции в этой точке должен быть нулевым.
Такие точки называются стационарными точками функции.
7.2 Достаточные условия оптимальности
Для функции одной переменной достаточные условия задаются следующей теоремой.
Теорема 3: если в точке первая производная функции равна нулю, а вторая производная , то функция в точке имеет локальный минимум, если , то функция в точке имеет локальный максимум.
Если вторая производная функции в точке равна нулю, то необходимо исследовать производные высших порядков в соответствии со следующей теоремой.
Теорема 4: если функция одной переменной имеет в точке производные до порядка равными нулю и производная , то тогда, если четно, то точка является точкой минимума, если ,точкой максимума - если .
Если нечетно, то точка - точка перегиба.
Для обобщения теоремы 3 на случай функции многих переменных рассмотрим матрицу вторых производных функции и ее свойства.
Матрицей Гессе (Гессианом) называется матрица вторых производных функции:
Для анализа поведения функции в точке потребуются некоторые свойства квадратичных функций.
Рассмотрим квадратичную функцию (форму):
Числовая матрица называется матрицей квадратичной формы. Можно считать, что эта матрица симметрична.
Квадратичная форма называется положительно определенной, если для и отрицательно определенной, если для .
Симметричная матрица A называется положительно определенной, если построенная по ней квадратичная форма положительно определена.
Симметричная матрица называется отрицательно определенной, если построенная по ней квадратичная форма отрицательно определена.
Проверить положительную или отрицательную определенность числовой матрицы можно по следующим признакам.
Признаки:
1. Критерий Сильвестра: матрица является положительно определенной, если все ее миноры больше ноля.
Матрица является отрицательно определенной, если знаки угловых миноров чередуются.
Или: если все угловые миноры удовлетворяют неравенству .
2. Для того чтобы матрица была положительно определенной, необходимо, чтобы все ее собственные числа были больше нуля.
Собственные числа - корни многочлена . Этот определитель есть многочлен относительно .
.
Для того чтобы матрица была отрицательно определенной, необходимо, чтобы все ее собственные числа были меньше нуля.
Достаточное условие оптимальности задается следующей теоремой.
Теорема 5: если в стационарной точке (т.е. ) матрица Гессе положительно определена, то эта точка - точка локального минимума, если матрица Гессе отрицательно определена, то эта точка - точка локального максимума.
Доказательство:
Пусть - стационарная точка, , возьмем окрестность точки . Тогда по теореме Тейлора
По условию теоремы , а матрица Гессе в точке положительно определена, то есть квадратичная форма >0 в точке , а в силу непрерывности вторых частных производных и в точке .
Значит точка - точка локального минимума.
Пример: Продукция трех видов производится в объеме и реализуется по цене соответственно. Определить объемы производства, обеспечивающие наибольший доход.
Определим стационарные точки функции :
Решением этой системы линейных алгебраических уравнений является вектор
Проверим достаточное условие оптимальности. Вычислим матрицу Гессе в полученной стационарной точке.
Угловые миноры матрицы имеют чередующиеся знаки
,
значит, матрица Гессе отрицательно определена и точка - точка локального максимума. При полученных объемах производства будет достигнут наибольший доход .
Проверим отрицательную определенность матрицы вторым способом. Найдем собственные числа матрицы Гессе
Так как все собственные числа матрицы , то матрица отрицательно определена и - локальный максимум.
8. Нелинейное программирование
8.1 Задачи на условный экстремум. Метод множителей Лагранжа
Задача на условный экстремум ставится как задача определения управляемых параметров , на которых достигается экстремум (максимум или минимум) при ограничениях, заданных уравнениями.
Задачу на условный экстремум можно свести к задаче на безусловный экстремум для специальным образом построенной функции.
Каждому ограничению поставим в соответствие переменную .
Построим функцию Лагранжа:
Если ограничения выполняются, то функция Лагранжа превращается в исходную функцию.
Точки локальных экстремумов задачи будут точками локальных экстремумов функции Лагранжа.
Теорема 6 (необходимое условие экстремума): если - точка локального экстремума и в окрестности этой точки функции непрерывно дифференцируемы, то в этой точке выполняются условия
Условия (10) означают, что градиент функции Лагранжа равен нулю .
Для формулировки достаточных условий оптимальности рассмотрим
окаймляющую матрицу Гессе:
Теорема 7 (достаточное условие экстремума):
· Стационарная точка функции Лагранжа является точкой локального минимума, если в окаймляющей матрице Гессе, вычисленной в стационарной точке, все угловые миноры, начиная с порядка имеют знаки, определяемые множителем .
· Стационарная точка функции Лагранжа является точкой локального максимума, если все угловые миноры окаймляющей матрицы Гессе, начиная с порядка образуют знакопеременный ряд, в котором знак первого члена определяется множителем .
Достаточное условие оптимальности можно сформулировать также в другой форме: если рассмотреть определитель, построенный из окаймляющей матрицы Гессе, то стационарная точка функции Лагранжа является точкой максимума, если все действительных корней многочлена меньше ноля. Если же корни больше нуля, стационарная точка функции Лагранжа является точкой минимума.
Пример: Предприятие выпускает два вида продукции в объемах . Они реализуются по ценам соответственно. По плану предприятие должно выпустить ровно 50 единиц продукции. Определить план производства, обеспечивающий наибольший доход.
Здесь функция ограничений
Построим функцию Лагранжа
Вычитая из второго уравнения первое, получим
Проверим достаточное условие оптимальности:
Угловые миноры матрицы, начиная с порядка 2m+1=3 должны иметь чередующиеся знаки, знак первого из них (положителен). Все эти условия выполняются:
Полученное решение - точка локального максимума.
Экономическая интерпретация множителей Лагранжа
Множитель Лагранжа - это двойственная переменная. Как и в линейном программировании, она показывает, на сколько изменится критерий при изменении правой части ограничений на единицу.
В рассмотренном примере
Следует ожидать, что при увеличении суммарного объема производимой продукции с 50 до 51 доход уменьшится на 6.66.
Проверим этот вывод. Пусть в нашей задаче критерий остался прежним, поменялась правая часть ограничения
Тогда условия стационарности выглядят следующим образом:
Стационарная точка
Приращение критерия
Для проверки достаточного условия оптимальности найдем корни многочлена, построенного из окаймляющей матрицы Гессе:
Корень отрицательный, значит это точка максимума функции.
Приращение функции -7.33 оказалось больше по модулю, чем ожидаемое приращение -6.66. Это объясняется нелинейностью целевой функции и тем, что производная
отражает приращение функции только при бесконечно малом приращении аргумента.
8.2 Задачи выпуклого программирования
Пусть исходная задача имеет вид:
Задача называется задачей выпуклого программирования, если выполняются следующие условия:
1. - вогнутая функция, то есть для
2. область допустимых решений выпуклая
3. область регулярная, то есть существует по крайней мере одна внутренняя точка Можно построить функцию Лагранжа:
Теорема 8: точка является оптимальным решением задачи выпуклого программирования тогда и только тогда, когда существует вектор такой, что для функции Лагранжа выполняются условия:
1.
2. условия дополняющей не жесткости:
3.
Условия называются условиями Куна - Таккера.
В общем случае система уравнений и неравенств слишком сложна для аналитического решения. Однако в задачах квадратичного программирования есть способы решения этой системы условий, сводящиеся к нахождению опорных решений систем линейных алгебраических уравнений.
Геометрический смысл условий Куна-Таккера:
Если все , , то условия дополняющей не жесткости запишутся в виде
то есть градиент функции в оптимальной точке является линейной комбинацией с положительными коэффициентами градиентов и активным ограничениям. Иными словами, градиент критерия лежит в геометрическом конусе градиентов ограничений.
Литература
1. Таха Х.А. Введение в исследование операций. - М.: Издательский дом «Вильямс», 2005.
2. Исследование операций в экономике / под редакцией Кремера Н.Ш.- М.: Банки и биржи, 2009.
3. Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. Математические основы и прикладные задачи. - М.: Либроком, 2010.
4. Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. Конечные методы. - М.: Либроком, 2010.
5. Рузанов А.И. Математические оптимизационные модели в экономических исследованиях. - Н.Новгород: изд. ННГУ, 2006.
6. Палий И.А. Линейное программирование. - М.: Эксмо, 2008.
7. Ермольев Ю.М., Ляшко И.И., Михалевич В.С., Тюптя В.И. Математические методы исследования операций. - Киев: Высшая школа, 1979.
8. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. - М.: Вш, 1980.
9. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск: ВШ. 2001.
10. Калихман И.Л. Сборник задач по математическому программированию. - М.: ВШ, 1975.
11. Акулич И.Л. Математическое программирование в примерах и задачах: Учебное пособие для студентов экономических специальностей вузов. - М.: ВШ, 1986.
12. Сборник задач и упражнений по высшей математике. Математическое программирование.- А.В. Кузнецов, В.А. Сакович, Н.И. Холод, Л.Т. Дежурко, Р.А. Рутковский, Н.М. Слукин / под редакцией А.В. Кузнецова - Минск: ВШ. 1995.
13. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. - Минск: ВШ. 2001.
14. Диалоговая система решения и анализа задач линейного программирования. Методические указания для проведения лабораторных работ по курсу Системный анализ. - Н. Новгород: изд. ННГУ, 1993.
Теория двойственности в задачах линейного программирования. - Н. Новгород: изд. ННГУ, 1999.
Размещено на Allbest.ru
...Подобные документы
Задачи оптимизации. Ограничения на допустимое множество. Классическая задача оптимизации. Функция Лагранжа. Линейное программирование: формулировка задач и их графическое решение. Алгебраический метод решения задач. Симплекс-метод, симплекс-таблица.
реферат [478,6 K], добавлен 29.09.2008Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа [263,5 K], добавлен 27.03.2011Оптимизационные исследования задач линейного и нелинейного программирования при заданных математических моделях. Решение задач линейного программирования и использование геометрической интерпретации и табличного симплекс-метода, транспортная задача.
курсовая работа [408,7 K], добавлен 13.06.2019Изучение экстремальных задач и поиск их решений. Выбор метода решения и приведения задачи к каноническому виду и к задаче линейного программирования. Метод искусственного базиса. Модифицированный симплекс-метод. Написание программы на языке С++Builder 6.
курсовая работа [343,0 K], добавлен 28.11.2010Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса.
курсовая работа [142,9 K], добавлен 24.10.2012Понятие теории оптимизации экономических задач. Сущность симплекс-метода, двойственности в линейном программировании. Элементы теории игр и принятия решений, решение транспортной задачи. Особенности сетевого планирования и матричное задание графов.
курс лекций [255,1 K], добавлен 14.07.2011Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
реферат [157,5 K], добавлен 21.08.2008Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.
курсовая работа [4,0 M], добавлен 05.03.2012Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа [88,9 K], добавлен 11.02.2011Определение с помощью симплекс-метода плана выпуска продукции для получения максимальной прибыли, чтобы сырьё II вида было израсходовано полностью. Решение задач линейного программирования средствами табличного процессора Excel, составление алгоритма.
курсовая работа [53,2 K], добавлен 30.09.2013Характеристика основных методов линейного программирования с n- переменными, в частности, графического и симплекс-метода. Способы решения задачи по определению оптимальной структуры товарооборота, обеспечивающей торговому предприятию максимум прибыли.
курсовая работа [678,7 K], добавлен 03.04.2011Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
контрольная работа [59,8 K], добавлен 30.10.2014Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
курсовая работа [57,1 K], добавлен 04.05.2010Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Обзор алгоритмов методов решения задач линейного программирования. Разработка алгоритма табличного симплекс-метода. Составление плана производства, при котором будет достигнута максимальная прибыль при продажах. Построение математической модели задачи.
курсовая работа [266,4 K], добавлен 21.11.2013Методы определения оптимального плана производства (приобретения) продукции с учетом ограниченного обеспечения ресурсами различного вида. Технология поиска оптимального решения задач линейного программирования (ЗЛП) с помощью итоговой симплекс-таблицы.
лабораторная работа [42,8 K], добавлен 11.03.2011Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа [1,7 M], добавлен 05.01.2015Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015
