Методы оптимальных решений

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

Содержание

1. Методы нелинейной и дискретной оптимизации

2. Задача

3. Задача

4. Задача

5. Задача

Литература

1. Методы нелинейной и дискретной оптимизации

оптимизация нелинейный дискретный программирование

В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции

(1)

при условии

(2)

где - некоторые известные функции n переменных, а - заданные числа.

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

а целевая функция является сепарабельной (суммой n функций ), или квадратической.

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

Рассмотрим частный случай общей задачи нелинейного программирования (1) - (2), предполагая, что система ограничений (2) содержит только уравнения, отсутствуют условия неотрицательности переменных, и - функции, непрерывные вместе со своими частными производными. Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных. Вводят набор переменных , называемых множителями Лагранжа, и составляют функцию Лагранжа

находят частные производные

и рассматривают систему n + m уравнений

(3)

с n + m неизвестными , . Решив систему уравнений (3), получают все точки, в которых функция (1) может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (3), как правило, имеет несколько решений.

Пример. Найти точку условного экстремума функции при ограничениях

Составим функцию Лагранжа:

Продифференцируем ее по переменным . Приравнивая полученные выражения к нулю, получим следующую систему уравнений:

Из второго и третьего уравнений следует, что ; тогда



Решив данную систему, получим:

и

Функция , заданная на выпуклом множестве Х, называется выпуклой, если для любых двух точек из Х и любого выполняется соотношение

. (4)

Функция , заданная на выпуклом множестве Х, называется вогнутой, если для любых двух точек из Х и любо-

го выполняется соотношение

. (5)

Если неравенства (15.4) и (15.5) считать строгими и они выполняются при , то функция является строго выпуклой (строго вогнутой). Выпуклость и вогнутость функций определяется только относительно выпуклых множеств.



Рисунок 1.

Если

- выпуклые (вогнутые) функции на некотором выпуклом множестве , то функция _ также выпуклая (вогнутая) на Х.

Основные свойства выпуклых и вогнутых функций:

1. Множество точек минимума выпуклой функции, заданной на выпуклом множестве, _ выпукло.

2. Пусть _ выпуклая функция, заданная на замкнутом выпуклом множестве . Тогда локальный минимум на Х является и глобальным.

3. Если глобальный минимум достигается в двух различных точках, то он достигается и в любой точке отрезка, соединяющего данные точки.

4. Если _ строго выпуклая функция, то ее глобальный минимум на выпуклом множестве Х достигается в единственной точке.

5. Пусть функция _ выпуклая функция, заданная на выпуклом множестве Х, и, кроме того, она непрерывна вместе со своими частными производными первого порядка во всех внутренних точках Х. Пусть - точка, в которой

Тогда в точке достигается локальный минимум, совпадающий с глобальным минимумом.

6. Множество точек глобальных (следовательно, и локальных) минимумов выпуклой функции , заданной на ограниченном замкнутом выпуклом множестве Х, включает хотя бы одну крайнюю точку; если множество локальных минимумов включает в себя хотя бы одну внутреннюю точку множества Х, то является функцией-константой.

Рассмотрим задачу нелинейного программирования

(6)

(7)

(8)

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

Говорят, что множество допустимых решений задачи (6) - (8) удовлетворяет условию регулярности, или условию Слейтера, если существует по крайней мере одна точка , принадлежащая области допустимых решений такая, что . Задача (6) - (8) называется задачей выпуклого программирования, если функция является вогнутой (выпуклой), а функции - выпуклыми. Функцией Лагранжа задачи выпуклого программирования (6) - (8) называется функция

где - множители Лагранжа.

Точка

называется седловой точкой функции Лагранжа, если

для всех и .



Частным случаем задачи нелинейного программирования является задача квадратичного программирования, в которой ограничения

являются линейными, а функция представляет собой сумму линейной и квадратичной функции (квадратичной формы)

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

Функция представляет собой сумму линейной функции (которая является и выпуклой, и вогнутой) и квадратичной формы. Если последняя является вогнутой (выпуклой), то задачи отыскания максимума (минимума) целевой функции могут быть успешно решены. Вопрос о том, будет ли квадратичная форма вогнутой или выпуклой, зависит от того, является ли она отрицательно-определенной, отрицательно-полуопределенной, положительно-определенной, положительно-полуопределенной или вообще неопределенной.

Задачи оптимизации, в результате решения которых искомые значения переменных должны быть целыми числами, называются задачами дискретного программирования.

Xj - целые неотрицательные.

Существуют различные методы решения дискретной оптимизации. Эти методы делятся на три группы:

- метод отсечения;

- метод дерева решений;

- эвристические (приближенные) методы.

Метод отсечения ориентированы на использования в задачах целочисленного линейного программирования (ЦЛП). Идея отсечения состоит в том, что однократное решение задачи ЦЛП сводится к многократному решению некоторой последовательности задач ЛП. Каждый раз решается новая ЗЛП, полученная из предыдущей дополнением к ней нового ограничения, обладающего двумя свойствами:

- только что полученное нецелочисленное оптимальное решение ЗЛП не удовлетворяет новому ограничению;

- любое целочисленное решение (не только оптимальное) ему удовлетворяет.

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

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

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

2. Задача

Фермер планирует засеять кукурузой и соей 400 га земли. Затраты на сев и уборку кукурузы составят 200 ден. ед./га, сои -100 ден. ед./га. На покрытие расходов, связанных с севом и уборкой урожая, фермер получил кредит в размере 60 тыс. ден. ед. Фермер планирует получить: кукурузы - 30 ц/га, сои - 60 ц/га. Фермер заключил договор на продажу кукурузы по 3 ден. ед./ц и сои по 6 ден. ед./ц. Однако согласно данному договору он обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого - 21 тыс. ц.

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

Решение:

Обозначим через х1 сколько гектаров нужно засеять кукурузы, через х2 - сои. Так как у фермера всего имеется 400 га земли, то первое ограничение задачи имеет вид: х1+ х2 ? 400. Найдем общие затраты на сев и уборку кукурузы и сои: (200х1+100х2) ден. ед. Фермер получил на расходы ссуду в 60 тыс. ден., поэтому следующее ограничение имеет вид: 200х1+100х2 ? 60 000. Найдем, сколько центнеров зерна соберет фермер: (30х1+60х2) ц. Вместимость склада составляет 21 тыс. центнеров, поэтому следующее ограничение имеет вид: 30х1+60х2 ? 21 000. на все переменные наложено ограничение x 1,2 ? 0

Построим экономико-математическую модель задачи:

max f(X) = 90x1+120x2

х1+ х2 ? 400

200х1+100х2 ? 60 000

30х1+60х2 ? 21 000

x1,2 ? 0

Решим задачу графическим методом.

Последнее ограничение означает, что область решений будет лежать в первой четверти декартовой системы координат.

Этап 1. Определим множество решений первого неравенства. Оно состоит из решения уравнения и строгого неравенства. Решением уравнения служат точки прямой x1+x2-400=0. Построим прямую по двум точкам (0;400) и (400;0), которые легко получить в результате последовательного обнуления одной из переменных. На рисунке обозначим ее цифрой I.

Множество решений строгого неравенства -- одна из полуплоскостей, на которую делит плоскость построенная прямая. Какая из них является искомой, можно выяснить при помощи одной контрольной точки. Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости. В качестве такой точки удобно брать начало координат. Подставим координаты (0; 0) в неравенство x1+x2-400<0, получим -400 < 0, т.е. оно выполняется. Следовательно, областью решения неравенства служит нижняя полуплоскость.

Аналогичным образом построим области решения двух других неравенств

200x1+100x2-60 000=0; x1 = 0, x2 = 600

x1 = 300, x2 = 0 (на рисунке прямая II);

200x1+100x2-60 000<0 при x1 = x2 = 0, -60 000<0 выполняется, берется левая полуплоскость.

30x1+60х2-21 000=0 x1 = 0, x2 = 350

x1 = 700, x2 = 0 (на рисунке прямая III);

30x1+60x2-21 000<0

при x1 = x2 = 0, -21 000<0 выполняется, берется нижняя полуплоскость.

Заштрихуем общую область для всех неравенств. Обозначим вершины области латинскими буквами и определим их координаты, решая систему уравнений двух пересекающихся соответствующих прямых. Например, определим координаты точки B, являющейся точкой пересечения первой и третьей прямой:

x1+x2-400=0, x1 = 100; x2 = 300

30x1+60х2 - 21 000=0.

Вычислим значение целевой функции в этой точке:

f(Х)= 90x1+120x2=90•100 + 120•300 = 45000.

Аналогично поступим для других точек, являющихся вершинами области АВСDO, представляющей собой область допустимых решений рассматриваемой ЗЛП. Координаты этих вершин имеют следующие значения: т. А(0;350), т. В(100;300), т.С(200;200), т. D(300;0), т. О(0;0).

Этап 2. Приравняем целевую функцию постоянной величине а: 90x1+120x2 = а.

Это уравнение является множеством точек, в котором целевая функция принимает значение, равное а. Меняя значение а, получим семейство параллельных прямых, каждая из которых называется линией уровня. Пусть а=0, вычислим координаты двух точек, удовлетворяющих соответствующему уравнению90x1+120x2 = 0. В качестве одной из этих точек удобно взять точку О(0;0), а так как при x1 = 4, x2 = -3 то в качестве второй точки возьмем точку G(4;-3).

Через эти две точки проведем линию уровня f(Х)= 90x1+120x2 = 0.

Этап 3. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными функции f(X), т.е. ОN =(90;120) Чтобы построить этот вектор, нужно соединить точку (90;120) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации -- в противоположном направлении.

В нашем случае движение линии уровня будем осуществлять до ее пересечения с точкой В, далее она выходит из области допустимых решений. Следовательно, именно в этой точке достигается максимум целевой функции. Отсюда легко записать решение исходной ЗЛП: max f(Х) =45000 и достигается при x1 = 100, x2=300.

Следовательно, чтобы получить максимальную прибыль, фермер должен засеять 100 га земли кукурузой, 300 га - соей. При этом он получит 45 тыс. ден. ед. при реализации зерна по договору.

Если поставить задачу минимизации функции f(Х) = 90x1+120x2 при тех же ограничениях, линию уровня необходимо смещать параллельно самой себе в направлении, противоположном вектору-градиенту. В нашем случае минимум функции будет в точке О (0;0). Это означает, что фермер не получит ни чего, если не засеет поле зерновыми культурами.

3. Задача

Торговая компания собирается приобрести новый товар - комплекты постельного белья. Ожидаемая потребность - 800 единиц в месяц. Товар можно приобрести у поставщика. Стоимость заказа - 150 руб., годовая стоимость хранения единицы товара -6 руб. Доставка товара осуществляется в течение двух дней. Компания работает 300 дней в году.

Рассчитайте объем заказа, минимизирующий общие годовые расходы компании. Определите:

а) годовые расходы на хранение запасов;

б) период поставок;

в) точку заказа.

Решение. Параметры работы торговой компании: V=800 единиц в месяц, К=150 руб.. h=6 руб., t=2.

Узнаем М=800*12=9600 единиц в год.

1. Найдем оптимальный объем заказываемой партии

, эта формула называется формулой Уилсона.

== 692,82

комплекты постельного белья нужно заказывать в одну партию.



2. Найдем годовые издержки хранения запасов:

Z= 150*9600/693+6*693/2=4156 руб./год.

3. Найдем период доставки:

Т(опт)=Q/М= 693ед/9600ед в год=0,072 года, 0,072*300дней= 21,622 дня.

4. Найдем точку заказа Н=М* t/кол-во дней в году=9600*2/300=64 комплекта постельного белья.

Решение задачи в Excel

Рис. 2.

Рис. 3.



Рис. 4.

Рис. 5.

Ответ:

Объем заказа 693 комплекта постельного белья.

а) годовые расходы на хранение запасов 4156 руб./год;

б) период поставок - 22 дня;

в) точку заказа 64 комплекта постельного белья.

4. Задача

В бухгалтерии организации в определенные дни непосредственно с сотрудниками работают два бухгалтера. Если сотрудник заходит в бухгалтерию для оформления документов (доверенностей, авансовых отчетов и пр.) в тот момент, когда оба бухгалтера заняты обслуживанием ранее обратившихся коллег, то он уходит из бухгалтерии, не ожидая обслуживания. Статистический анализ показал, что среднее число сотрудников, обращающихся в бухгалтерию в течение часа, равно л=8 , а среднее время, которое затрачивает бухгалтер на оформление документа, - Тср.=7.

Оцените основные характеристики работы данной бухгалтерии как СМО с отказами (указание руководства не допускать непроизводительных потерь рабочего времени!). Определите, сколько бухгалтеров должно работать в бухгалтерии в отведенные дни с сотрудниками, чтобы вероятность обслуживания сотрудников была выше 85%.

Решение. Рассчитаем

м=1/Tоб=1/7/60==8,57

затем рассчитаем нагрузку на систему б = л / м = 8/8,57=0,933



Рис. 6.

Расчёты проведем в Excel. Видно, что СМО загружена не сильно: из двух бухгалтеров занято в среднем М=0,76, а из обращающихся в бухгалтерию людей около Р отказов=18% остаются незагруженными.

Из графика на рисунке видно , что минимальное число каналов обслуживания (бухгалтеров), при котором вероятность обслуживания работников будет выше 85% (вероятность отказа ниже 15%), равно n=3.

Рис. 7.

5. Задача

Статистический анализ показал, что случайная величина Х (длительность обслуживания клиента в парикмахерской) следует показательному закону распределения с параметром, а число клиентов, поступающих в единицу времени (случайная величина Y), - закону Пуассона с параметром л=1,9 и м=0,6.

Организуйте датчики псевдослучайных чисел для целей статистического моделирования (использования метода Монте-Карло). Получите средствами MS Excel 15 реализаций случайной величины Х и 15 реализаций случайной величины Y.

Решение. Имитационный эксперимент проведем с использованием MS Excel.

Табличная имитационная модель двухканальной СМО с отказами

На рисунке представлен моделирующий алгоритм (табличная имитационная модель) при числе испытаний N=15.

Для получения случайных чисел с показательным законом распределение Xi=

Случайные числа с равномерным их распределением в интервале от 0 до1 получены с помощью функции =СЛЧИС() Мастер функций (Математические). Эти числа содержатся в ячейках $C$3:$Q$3.

Рис. 8.

Пятнадцать реализаций с.в. длительность интервала ф (в часах) между очередными поступлениями требований $C$4:$Q$4. Для получения, содержимого ячейки С4 использовать функции = (-1/C1)*LN(B3).

Соответственно, кумулятивным образом (строка 6) на временной оси [0, Т] зафиксировано время Тi (i=1,2,…,15) поступления требований (в минутах, с округлением).

Для получения реализаций с.в. длительности обслуживания t (в минутах, с округлением) в соответствующую ячейку электронной таблицы (строки 7 и 9) записывается формула

=60*(-1/6)*LN(СЛЧИС()).

Далее последовательно сравниваются время окончания обслуживания каналами (строки 8 и 10) и время поступлениями требований (строка 6); соответственно, в счётчике отказов (строка 11) фиксируется 0 (требование принято к обслуживанию) или 1(требованию отказано в обслуживании).

В соответствии со счётчиком отказов (в ячейках $C$12:$Q$12) зафиксировано 7 отказов, т.е. статистическая оценка вероятности отказа в данной СМО при N=15 равна (7/15)=0,47.

Литература

1. Федосеев В.В., Гармаш А.Н., Орлова И.В. Экономико-математические методы и прикладные модели: учебник для бакалавров. -3-е изд., перераб. и доп. - М.: Юрайт, 2012.

2. Гармаш А.Н., Орлова И.В. Математические методы в управлении: учебное пособие. - М.: Вузовский учебник, 2012.

3. Ильина М.А., Копылова Ю.Н., Копылова Н.Т. Методы оптимальных решений. Конспект лекций. Учебно-методическое пособие. - Барнаул: Изд-во АлтГТУ, 2012.-112 с.

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

...