WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 11 |

–Q(u3) –(u2) u –(u2) –Q(u3) u –(u1) –Q(u1) u uРис. 3.14 Поиск оптимума методом проектирования вектора-градиента при наличии ограничений типа неравенств 3.5.2 Метод ажурной строчки Этот метод заключается в зигзагообразном движении вдоль границы. Идея этого метода при использовании его в задачах с ограничениями типа неравенств, а также равенств заключается в следующем.

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

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

= Вычисляется градиент функции (u) и осуществляется возврат в до = пустимую область. Следующий шаг делается опять по градиенту целевой функции Q (u) и т.д.

Рис. 3.15 Поиск оптимума методом ажурной строчки Сложность метода заключается в выборе алгоритма уменьшения шага и правила остановки. Это зависит от опыта и способностей программиста и определяется его творчеством.

3.6 ГЛОБАЛЬНЫЙ ЭКСТРЕМУМ Исследуемая функция может иметь несколько экстремумов. Если для всех значений независимых переменных выполняется условие Q (uопт) Q (u), u U, то экстремум в точке uопт называется глобальным, другие экстремумы называются локальными.

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

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

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

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

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

3.7 ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ П р и м е р 3.2 Найти максимум функции Q(u1, u2) = -2u1 + 2u1, u2- u2 при условии 1(u1, u2) = -2u1 + 5u2 - 30 0, 2(u1, u2) = 4u1 + 5u2 - 60 0, 3(u1, u2) = 4u1 - 5u2 - 20 0, 4(u1, u2) = -u1 0, 5(u1, u2) = -u2 методом наискорейшего спуска.

В качестве начального приближения выбирается точка u0(1, 0), для которой условия принимают следующие значения 1 (u0) = –32, 2 (u0) = –56, 3 (u0) = –16, 4 (u0) = –1, 5 (u0) = 0, т.е. выполняются.

Для нахождения направления спуска u1= (u1, u2) необходимо найти частные производные функции Q (u1, u2) в точке u0:

Q(u1, u2) Q(u1, u2) = -4u1 + 2u2, u0 = -4;

u1 uQ(u1, u2) Q(u1, u2) = +2u1 - 2u2, u0 = 2, u2 uи решить следующую задачу линейного программирования.

Q Q Найти минимум функции F = U1 + U2 для нашего u1 uслучая F = –4u1 + 2u2 при условиях –u2 0 (так как 5 (u0) = 0), u1 1, u2 1.

Решение этой задачи дает, что u1 = 1, u2 = 0, minF = –4.

Новое приближение u1 определяется как u1 = u0 + tu1, где min F t – величина шага, определяемая из соотношения t = min(t', t"), где t =, t" – наименьшее поло2[Bu1, u] t'>0, t">жительное число среди отношений (u0), =1, 2, 3, 4, 5.

n ui aj i=В – матрица, состоящая из коэффициентов функции Q (u1, u2): b11 = –2, b12 = 1, b21 = 1, b22 = –1; aj – коэффициент функций ().

Таким образом, имеем, что 2(u0) 56 3(u0)= 4 = 4, t = –1 < 0, t = min = ; 2 u u a2 j a3 j j j j =1 j = отсюда t = 4.

Координаты точки u2: u1 = 1+ 4 = 5, u1 = 0. Значения условий для этой точки:1(u1)= -40, 2(u1)= -40, 3(u1)= 0, 4(u1)= -5, 5(u1)= 0.

Для нахождения очередного направления спуска u2 = (u1, u2) необходимо решить следующую задачу линейного программирования: найти минимум функции F = –20 u1 + 10u2 при условиях 4u1 – 5u0, –u2 0, u1 1, u2 1.

4 Решение этой задачи дает u1 = 1, u2 = -, при этом min F = -.

5 Величина шага t: t = - < 0, t = min(20; 5) = 5, следовательно новое приближение u2 = u1 + t u2, или 2 u1 = 10, u2 = 4.

Значение условий для точки u2:

1(u2)= -30, 2(u2)= 0, 3(u2)= 0, 4(u2)= -10, 5(u2)= -4.

Для определения следующего направления решается задача линейного программирования: найти минимум F = –32u1 + 12u2 при условиях 4u1 + 5u2 0, 4u1 – 5u2 0, u1 1, u2 1.

Решением этой задачи будет u1 = 0, u2 = 0, min F = 0. Следовательно u2 = (10,4) является оптимальным решением min Q (u1, u2) = –136.

П р и м е р 3.2 Найти максимальное значение функции Q(u1, u2) = -u1 - u2 при условиях: (u1-7)2+(u2-7)2 18, u1 0, u2 0 методом штрафных функций.

На рис. 3.16 представлена область допустимых решений и линии уровня, определяемые целевой функцией Q (u1, u2). Этими линиями являются окружность с центром в точке (0, 0). Точка касания одной из этих окружностей с областью допустимых решений и является точкой максимального движения целевой функции.

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

При этом координаты последующей точки находят по формуле (uk)+ di g(uk).

0; Q uk +1 = max uk + j j u x j j =2 Положим u0 = (6,7), = 0,1, g(u1,u2) = 18 -(u1-7) -(u2-7) и определим частные производные от целевой и штрафной функций Q g Q g = -2u1, = -2u1 +14; = -2u2, = -2u2 +14.

u1 u1 u2 u u uE u uu u u 0 u 1 3 5 7 9 Рис. 3.16 Допускаемая область и линии уровня целевой функции I итерация. Так как точка u0 = (6,7) принадлежит области допустимых решений задачи, то второе слагаемое в квадратных скобках формулы для определения последующей точки равно нулю. Следовательно координаты точки u1 вычисляются по формулам:

Q(u0) = max{0; 6 + 0,1(- 2)6}= 4,8;

1 u1 = max u1 + 0;

u Q(u0) = max{0; 7 + 0,1(- 2)7 }= 5,6.

u1 = max u2 + 0;

u Для определения принадлежности этой точки области допустимых решений задачи необходимо найти g(u1) = 11,2, так как g(u1) > 0, то u1 принадлежит области допустимых решений. В этой точке Q (u1) = –54,4.

II итерация. Находим:

u1 = max{0; 4,8 + 0,1(- 2)4,8}= 3,84;

u2 = max{0; 5,6 + 0,1(- 2)5,6}= 4,48;

g(u2)= 1,664 > 0; Q(u2)= -34,816.

III итерация. Находим:

u1 = max{0; 3,84 + 0,1(- 2)3,84}= 3,072;

u2 = max{0; 4,48 + 0,1(- 2)4,48}= 3,584;

g(u3) -9,096.

IV итерация. Найденная точка u3 не принадлежит области допустимых решений задачи. Следовательно Q (u3)+ g(u3) = max{0; 2,4576 + 0,7856 };

4 u1 = max 0; u1 + u1 u Q (u3)+ g(u3) = max{0; 2,8672 + 0,6832 }.

4 u2 = max 0; u2 + u2 u Здесь возникает вопрос о выборе числа. Наиболее целесообразно взять его так, чтобы точка u4 не слишком далеко удалялась от границы области допустимых решений и вместе с тем принадлежала этой области. Этим требованием удовлетворяет = 1,9 и следовательно:

u1 = max{0; 2,4576 +1,90,7856} 3,95;

u2 = max{0; 2,8672 + 1,90,6832} 4,165;

g(u4) 0,66 > 0; Q(u4) -32,95.

V итерация. Находим u1 = max{0; 3,95 + 0,1(- 2)3,953}= 3,16;

u2 = max{0; 4,165 + 0,1(- 2)4,165}= 3,33;

g(u5) -10,2 < 0.

VI итерация. Находим u1 = max{0; 3,16 + 0,1[(- 2) 3,16 +1,9 ((- 2) 3,16 +14)]} 3,987;

u2 = max{0; 3,33 + 0,1[(- 2) 3,33 +1,9 ((- 2) 3,33 +14)]} 4,06;

g(u6) 0,272 > 0; Q(u6) -32,37.

VII итерация.

7 u1 3,189; u2 3,247; g(u7) -10,61 < 0.

VIII итерация.

8 u1 3,999; u2 4,024; g(u8) 0,137 > 0; Q(u8) -32,185.

IX итерация.

9 u1 = 3,201; u2 = 3,219; g(u9) -10,728 < 0.

Х итерация.

u1 = 4,004; u10 = 4,012; g(u10)= 0,096 > 0; Q(u10)= -32,128.

XI итерация.

u1 = 3,203; u11 = 3,21; g(u11)= -10,781 < 0.

XII итерация.

u1 = 4,005; u12 4,008; g(u12)= 0,079; Q(u12)= -32,104.

Сравнивая значения целевой функции, найденные в точках, полученных после Х и ХII итераций, видно, что они с точностью до 0,1 совпадают. Это говорит о близости точки, найденной на последней итерации, к точке максимального значения целевой функции. Эта точка u12 находится вблизи границы области допустимых решений и ее можно считать приемлемым решением задачи. При необходимости можно уточнить дальнейшими шагами найденное решение.

4 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Линейное программирование является составной частью задач математического программирования, в которых критерий оптимальности задается в виде линейной функции от входящих в него переменных, кроме того, на эти переменные накладываются некоторые ограничения в форме линейных равенств и неравенств.

4.1 КРАТКИЙ ИСТОРИЧЕСКИЙ ОЧЕРК Математические исследования отдельных экономических проблем, математическая формализация статистического материала проводилась еще в XIX веке. Так, при математическом анализе процесса расширенного воспроизводства использовались преимущественно алгебраические соотношения. Потребности планируемой управляемой экономики, характерной для ХХ века, привели к необходимости располагать конкретными экономическими показателями и характеристиками. Это привело к созданию системы межотраслевого баланса, послужившего толчком в разработке и исследовании математических моделей экономических систем и ситуаций.

В 1936 году появилась первая публикация американского экономиста и статистика В.В. Леонтьева о межотраслевой модели производства и распределении продукции США, которая вошла в литературу под названием метода анализа экономики "затраты – выпуск".

В 1938 году русский математик Л.В. Канторович, изучая практическую задачу выбора наилучшей производственной программы загрузки лущильных станков, отметил, что эта задача на максимум при ограничениях в виде линейных неравенств весьма своеобразна и не поддается решению известными средствами классического анализа. Эта задача не является случайной, как стало ясно, а является типичным представителем нового, не исследованного класса задач, к которым приводят различные вопросы нахождения наилучшего производственного плана. В 1939 году появилась работа Л.В. Канторовича "Математические методы организации и планирования производства", открывшая новый этап в развитии экономико-математических методов – методов линейного программирования, которые долгое время почти не разрабатывались и в практику не внедрялись.





Термин "линейное программирование" появился впервые только в 1951 году в работах Дж. Б. Данцига и Т. Купманса (США). В эти же годы Дж. Б. Дансингом разработан эффективный метод решения задач линейного программирования – симплекс метод.

Наиболее эффективно линейное программирование развивалось в СССР и США в 1955 – 65 годах, именно в этот период оно было одним из наиболее "модных" разделов прикладной математики. В настоящее время линейное программирование стало важным инструментом современной теоретической и прикладной математики.

4.2 ТИПИЧНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Задача об оптимальном выпуске продукции Эта задача возникает при составлении планов выпуска продукции предприятием и поэтому имеет важное практическое значение.

Предприятие выпускает n наименований продукции. Затраты -го вида ресурсов ( = 1, m ) на производство единицы продукции j-го вида ( j = 1, n) составляют аj ; полный объем имеющихся ресурсов – b ( = 1, m ); прибыль, получаемая предприятием при изготовлении и реализации единицы -го вида продукта – с ; а и А – задаваемая нижняя и верхняя границы по объему выпуска -го вида продукции.

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

Таким образом, задача математически заключается в следующем: найти такой план выпуска проn дукции U = (u1,..., un), чтобы выполнялись технологические ограничения u bi, = 1, m, и ограничеaij j j=ния на объемы отдельных видов выпускаемой продукции aj uj Aj, j = 1, n и при этом достигалась бы n максимальная общая прибыль от производства и реализации продукции – max ui.

ci j=Задача оптимизации межотраслевых потоков Каждая из n отраслей хозяйства производит только свой один специфический вид продукции, используемый в дальнейшем в производстве во всех n отраслях (в частности, в нулевом количестве). Если yi – объем производства в -й отрасли, u – объем продукта -го вида для внепроизводственного потребления, аj – коэффициенты прямых затрат продукции j-го вида на производство в -й отрасли единицы продукции -го вида, N – максимально возможный объем производства в -й отрасли, d – требуемое для внепроизведенного потребления количество продукции -го вида, С – стоимость единицы продукции го вида, то задача ставится следующим образом.

Требуется найти такие объемы производства y и такой план выпуска конечной продукции u ( = 1, n), при котором максимизируется общая стоимость произведенного конечного продукта – n max u при выполнении ограничений на объем производства 0 y N, = 1, n; на выпуск конечного C =n продукта u d, = 1, n; технологических ограничений на выпуск продукции y x + u, = 1, n.

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

Имеется m пунктов производства с объемами производства в единицу времени а, = 1, m и n пунктов потребления b, = 1, n, естественно, что потребление не должно превышать возможностей произm n водства, затраты на перевозку единицы продукции из -го пункта производства в j-й пункт a b =1 =потребления составляют Сj, а количество перевезенного продукта uj.

Требуется составить такой план перевозок, при котором суммарные затраты на них были бы миниm n мальны min uij при условиях, что в каждый пункт потребления завозится требуемое количество Cij i=1 j=m продукта bj, j = 1, n, из каждого пункта производства вывозится не более произведенного количеuj =n ства продукта a, = 1, m и перевозимый объем продукта не может быть отрицательным uj =uj 0, = 1, m, j = 1, n.

Задача о выборе производственной программы Эта задача была одной из первых практических задач линейного программирования, решенная в 1939 году известным русским математиком Л.В. Канторовичем.

На m предприятиях нужно произвести n продуктов в заданном ассортименте l1, l2,..., ln. Если uij, = 1, m, j = 1, n – рабочее время -го предприятия, отводимое под j-й продукт, аij – производительность го предприятия в единицу времени по выпуску j-го продукта, то задача о выборе производственной программы для случая, когда продукция дефицитна, производственные мощности ограничены и должны использоваться максимально полно, ставится следующим образом.

Требуется составить программу работы предприятий – указать время uj, отведенное на производство каждого вида продукции на данном предприятии таким образом, чтобы получить максимальный суммарный объем продукции в заданном ассортименте в единицу времени, т.е. необходимо найти uj из условий, что время не может быть отрицательным uj > 0, сумма всех временных долей не превосходит полn ного времени работы предприятия 1, количество ассортиментных наборов продуктов максимально uj j =m y j, max Z = max,min где yj = uj – aj l j =количество j-го продукта, произведенного на всех предприятиях.

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 11 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.