Курс лекци Русакова по методам оптимизации (1083216), страница 18
Текст из файла (страница 18)
Найти ПодтвердитьMAX и MIN.MAX.найденныерешения, решив двойственнуюзадачулинейногопрограммирования.F = 4x-3yF = -3x-5y --> MAX-5x -4y > -96-2x -6y > -442x -5y > -48-5x -3y > -48-8x -1y < -454x -8y < -24Решить, используя симплекс метод.Задача 3.Задача 4.3x1 + 3x2 + 3x3 → max6x1 + 6x2 + 3x3 → max18x1 + 5x2 + 7x3 ≤25816x1 + 9x2 + 2x3 ≤26414x1 + 13x2 + 8x3 ≤25515x1 + 3x2 + 2x3 ≤31914x1 + x2 + 7x3 ≤2886x1 + 10x2 + 3x3 ≤370105370Вариант № 25.Задача1.РешитьЗадача2.Найтиграфическим способом. Найти ПодтвердитьMAX и MIN.MAX.найденныерешения, решив двойственнуюзадачулинейногопрограммирования.F = -5x-2yF = -4x-6y --> MAX4x -5y > -31-2x -6y > -52-5x -11y > -136-6x -3y > -606x -3y < 39-4x -7y < -60Решить, используя симплекс метод.Задача 3.Задача 4.4x1 + 4x2 + 5x3 → max6x1 + 6x2 + 6x3 → max8x1 + 16x2 + 4x3 ≤27417x1 + 5x2 + 10x3 ≤2763x1 + x2 + 3x3 ≤2688x1 + 19x2 + 11x3 ≤2438x1 + 7x2 + 11x3 ≤36412x1 + 2x2 + 10x3 ≤360170152Вариант № 26.Задача1.РешитьЗадача2.Найтиграфическим способом.
Найти ПодтвердитьMAX и MIN.MAX.найденныерешения, решив двойственнуюзадачулинейногопрограммирования.F = 4x-5yF = -3x-5y --> MAX-3x -7y > -106-3x -7y > -66-6x +1y < -7-8x -3y > -722x -5y < -16-4x +2y > -26Решить, используя симплекс метод.Задача 3.Задача 4.3x1 + 3x2 + 3x3 → max2x1 + 3x2 + 4x3 → max9x1 + 5x2 + x3 ≤2885x1 + 10x2 + 16x3 ≤3102x1 + 9x2 + 16x3 ≤38214x1 + 9x2 + 10x3 ≤26118x1 + 8x2 + 7x3 ≤3503x1 + 8x2 + 10x3 ≤25513092Вариант № 27.Задача1.РешитьЗадача2.Найтиграфическим способом. Найти ПодтвердитьMAX и MIN.MAX.найденныерешения, решив двойственнуюзадачулинейногопрограммирования.F = -2x-7yF = -2x-8y --> MAX2x -6y > -46-3x -6y > -45-4x -5y > -703x -7y > -211x -5y < -19-3x +1y < -1Решить, используя симплекс метод.Задача 3.Задача 4.4x1 + 4x2 + 2x3 → max6x1 + 6x2 + 5x3 → max7x1 + 17x2 + 7x3 ≤36414x1 + 11x2 + 8x3 ≤26511x1 + 7x2 + 4x3 ≤3186x1 + 5x2 + 8x3 ≤27916x1 + 12x2 + 4x3 ≤38712x1 + 8x2 + x3 ≤395135167Вариант № 28.Задача1.РешитьЗадача2.Найтиграфическим способом.
Найти ПодтвердитьMAX и MIN.MAX.найденныерешения, решив двойственнуюзадачулинейногопрограммирования.F = 2x-5yF = -1x-12y --> MAX-1x -5y < -17-3x -5y > -46-3x +1y < -25x -5y > -35-2x -5y > -46-2x -1y > -17Решить, используя симплекс метод.Задача 3.Задача 4.6x1 + 3x2 + 7x3 → max3x1 + 4x2 + 4x3 → max9x1 + 5x2 + 18x3 ≤26118x1 + 18x2 + 17x3 ≤39416x1 + 7x2 + 8x3 ≤3203x1 + 17x2 + 11x3 ≤2576x1 + 5x2 + 18x3 ≤400x1 + 16x2 + 11x3 ≤30614893Вариант № 29.Задача1.РешитьЗадача2.Найтиграфическим способом.
Найти ПодтвердитьMAX и MIN.MAX.найденныерешения, решив двойственнуюзадачулинейногопрограммирования.F = -2x +1yF = -7x-3y --> MAX-2x -6y > -68-1x -6y > -37-4x +1y < -41x -8y < -231x -7y < -13-4x -3y > -52Решить, используя симплекс метод.Задача 3.Задача 4.3x1 + 2x2 + 3x3 → max4x1 + 4x2 + 4x3 → max8x1 + 11x2 + 8x3 ≤3419x1 + 14x2 + 19x3 ≤35818x1 + 11x2 + 17x3 ≤3287x1 + 6x2 + 5x3 ≤25612x1 + 9x2 + 9x3 ≤2864x1 + 4x2 + 2x3 ≤36059148Вариант № 30.Задача1.РешитьЗадача2.Найтиграфическим способом. Найти ПодтвердитьMAX и MIN.MAX.найденныерешения, решив двойственнуюзадачулинейногопрограммирования.F = -1x-2yF = 1x-6y --> MAX-2x -8y > -88-3x -7y > -66-4x +1y < -82x -4y > -161x -7y < -19-4x -4y > -72Решить, используя симплекс метод.Задача 3.Задача 4.4x1 + 2x2 + 3x3 → max4x1 + 6x2 + 3x3 → max5x1 + 4x2 + 15x3 ≤2458x1 + 14x2 + 3x3 ≤2539x1 + 2x2 + 2x3 ≤39711x1 + 16x2 + 3x3 ≤35114x1 + 2x2 + 4x3 ≤33510x1 + 11x2 + 16x3 ≤3081851258.02 Методы одномерной оптимизацииОбщая схема методов поиска минимума на отрезкеПусть функция f ( x) унимодальна на отрезке [a0 , b0 ] .
Необходимонайти точку минимума функции на этом отрезке с заданной точностью ε .Всеметодыодномерногопоискабазируютсянапоследовательномуменьшении интервала, содержащего точку минимума.Возьмем внутри отрезка [a0 , b0 ] две точки x1 и x2 : a0 < x1 < x2 < b0 ,ивычислимзначенияфункциив этихточках.Изсвойстваунимодальности функции можно сделать вывод о том, что минимумрасположен либо на отрезке [a0 , x2 ] , либо на отрезке [ x1 , b0 ] .
Действительно,если f ( x1 ) < f ( x 2 ) , то минимум не может находиться на отрезке [ x2 , b0 ] , аесли f ( x1 ) > f ( x2 ) , то минимум не может находиться на отрезке [a`0 , x1 ] .Если же f ( x1 ) = f ( x2 ) , то минимум находится на интервале [ x1 , x2 ] .Алгоритмзаканчивается,когдадлинаинтервала,содержащегоминимум, становится меньше ε . Различные методы одномерного поискаотличаются выбором точек x1 , x 2 . Об эффективности алгоритмов можносудить по числу вычислений функции, необходимому для достижениязаданной точности.Поиск интервала, содержащего минимум функцииВ рассмотренных методах требуется знать начальный отрезок,содержащий точку минимума.
Поиск отрезка на прямой заключатся в том,что возрастающие по величине шаги осуществляются до тех пор, пока небудет пройдена точка минимума функции, т.е. убывание функции сменитсяна возрастание.Например, интервал может быть выделен с помощью следующегоалгоритма. На первом шаге выбираем начальную точку x0 и определяемнаправление убывания функции.Шаг 1. Если f ( x0 ) > f ( x0 + δ ) , то полагаем: k=1, x1 = x0 + δ , h = δ .Иначе, если f ( x0 ) > f ( x0 − δ ) , то x1 = x0 − δ , h = −δ .Шаг 2.
Удваиваем h и вычисляем xk +1 = xk + h .Шаг 3. Если f ( xk ) > f ( xk +1 ) , то полагаем k = k + 1 и переходим кшагу 2. Иначе – поиск прекращаем, т.к. отрезок [xk −1 , xk +1 ] содержит точкуминимума.Поиск минимума функции n переменных в заданном направленииПусть требуется найти минимум функции n переменных f ( x ) , гдеx = ( x1 , x2 ,..., xn ) , в направлении вектора s . Для этого нужно найти минимумфункции g (λ) = f ( x + λ ⋅ s ) рассмотренными выше методами, λ – величинашага в заданном направлении.Варианты заданийВариант определяется по последней цифре в зачётной книжке.Реализовать методы дихотомии, золотого сечения и Фибоначчи дляпоиска минимума функции на интервале.2551.
f ( x ) = sin( x ) , x ∈ [− π / 2, π / 2] .2. f ( x ) = x 4 − x , x ∈ [0,1].3. f ( x ) = ( x − 2 )2 , x ∈ [− 2,20] .4. f ( x ) = ( x − 15)2 + 5 , x ∈ [2,200] .5. f ( x ) = ( x + 5)4 , x ∈ [− 10,15].6. f ( x ) = e x , x ∈ [0,100].7. f ( x ) = x 2 + 2 x − 4 , x ∈ [ −10,20] .8. f ( x ) = x 3 − x , x ∈ [ 0,1] .9. f ( x ) = x 5 − x 2 , x ∈ [0,1] .10. f ( x ) = − x / e x , x ∈ [ 0,3] .Список литературы1. Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. сангл. — М.: Издательский дом "Вильямc", 2005г.
912 с: ил. — Парал. тит.англ.2. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002.3. Вентцель Е.С. Элементы динамического программирования. —М:Наука, 1964г.4. Акулич И.Л. Математическое программирование в примерах и задачах:Учеб. пособие для студентов эконом. спец. вузов.— М.: Высш. шк., 1986г.319 с.256.