Линейное программирование
Задача 1 (16.88) Минимизировать функцию f(x) на всей числовой оси методом Ньютона. Критерием достижения требуемой точности считать выполнение неравенства . Решение: Найдем первую и вторую производные исходной функции: Выберем начальное приближение . И осуществим вычисления по формуле Результаты запишем в таблице |
n | | | | | 0 | 0 | 2 | 1 | | 1 | -0,2 | 1,91 | -0,1649 | | 2 | -0,175697 | 1,908525 | -0,0032 | | 3 | -0,17520305 | 1,908524 | -0,0000013 | | |
n=1 n=2 n=3 n=4 Далее мы заканчиваем вычисления, потому что данная точность достигнута. В результате мы получаем: и . Осуществим проверку при помощи встроенной функции Minimize: , Ответ: и Задача 2 (16.115) Выписать матрицу Q квадратичной функции f(x), найти ее градиент в точке и убедиться в выпуклости f(x) в . , Решение: Запишем исходную функцию в следующем виде: , где Тогда матрица Q примет вид: Найдем градиент в точке по формуле , где r - вектор-столбец и равен : Подставляя в полученную матрицу , мы получаем следующее значение градиента в данной точке: Теперь убедимся в выпуклости f(x) в . Для того, чтобы исходная функция была выпуклой в , достаточно, чтобы матрица Q была положительно определена. Для этого найдем угловые миноры матрицы Q и если они будут больше нуля, то функция f(x) будет выпуклой в . , Так как , ,то функция f(x) выпукла в . Проверка в Mathcad: Проверка на выпуклость и нахождение градиента в точке x0 Ответ: градиент равен и функция f(x) будет выпуклой в . Задача 3 (16.136) Минимизировать квадратичную функцию методом наискорейшего спуска, заканчивая вычисления при , . Решение: Тогда производные исходной функции будут иметь вид: Выберем начальное приближение . Тогда Для нахождения точки минимума функции найдем нули ее производной: Зная , мы определим следующим образом: И так далее по выше описанной цепочке. Реализуем решение данной задачи в математическом пакете Mathcad. Функция имеет вид: Тогда коэффициенты будут равны Возьмем следующие начальное приближение и : Далее пишем программу В результате получаем искомое решение и функцию : Ответ: и Задача 4 (16.155) Минимизировать функцию f(x) методом сопряженных направлений, заканчивая вычисления при , . Решение: Тогда частные производные исходной функции будут иметь вид: Решение будем искать по следующему алгоритму: Шаг 1. Выбрав начальное приближение , Для нахождения точки минимума функции используем метод перебора: =>> , откуда Шаг 2. Для нахождения точки минимума функции используем метод перебора: =>> , откуда Шаг 3. Для нахождения точки минимума функции используем метод перебора: =>> , откуда Шаг 4. следовательно требуемая точность достигнута и Ответ: Задача 5 (16.193) Решить задачу линейного программирования графическим методом. Решение: Изобразим на плоскости наш многоугольник ABCDE (красного цвета) и одну из линий уровня (розового цвета). Линии AB соответствует уравнение , BC соответствует , CD соответствует , DE соответствует и EA соответствует Направление убывания функции указывает вектор . Совершая параллельный перенос линии уровня вдоль направления , находим ее крайнее положение. В этом положении прямая проходит через вершину многоугольника ABCDE. Поэтому целевая функция принимает минимальное значение в точке , причем Ответ: и Задача 6 (16.205) Решить задачу линейного программирования в каноническом виде графическим методом. Решение: Матрица системы будет иметь следующий вид: Ранг этой матрицы равен . Тогда число свободных переменных равно , поэтому для решения задачи можно использовать графический метод. Решив систему ограничений - равенств относительно базисных переменных , , получим: Исключая с помощью полученной системы переменные , из выражения для целевой функции, получаем: С учетом условия неотрицательности , , и последних равенств получаем следующую задачу: Изобразим на плоскости наш многоугольник ABCDEJ (красного цвета) и одну из линий уровня (розового цвета). Линии AB соответствует уравнение , BC соответствует , CD соответствует , DE соответствует , EJ соответствует и JA соответствует . Направление убывания функции указывает вектор . Совершая параллельный перенос линии уровня вдоль направления , мы видим, что целевая функция содержит сторону AB многоугольника ABCDEJ. Таким образом, все точки отрезка AB являются точками минимума функции . Так как концы A и B имеют координаты и соответственно, то найдем отсюда координаты и : Тогда любая точка минимума представима в виде где . Минимальное значение целевой функции Ответ: бесконечное множество решений , где и . Задача 7 (16.216) Решить задачу линейного программирования симплекс - методом, находя начальную угловую точку методом искусственного базиса. Решение: Матрица системы имеет вид . Ее ранг равен 3. Введем дополнительные переменные и запишем условие вспомогательной задачи линейного программирования для рассматриваемого случая: Считая дополнительные переменные базисными, запишем симплекс таблицу этой задачи, соответствующую угловой точке : |
| | | | | | | | 3 | -2 | 3 | 2 | 9 | | | 1 | 2 | -1 | 1 | 0 | | | -1 | -1 | 2 | 1 | 6 | | | -3 | 1 | -4 | -4 | -15 | | |
Произведем преобразования исходной симплекс-таблицы симплекс-методом следующим образом: 1) смотрим на нижнюю строку - выбираем тот столбец, в котором нижний элемент отрицательный, если таких столбцов несколько, то выбираем любой (в нашем случае выбираем первый столбец ); 2) далее смотрим на последний и выбранный столбцы - сравниваем отношения элементов последнего и выбранного столбцов (в выбранном столбце берем только положительные числа), и выбираем тот элемент выбранного столбца, где отношение элементов будет наименьшим (в нашем случае 9/3 и 0/1, так как второе отношение наименьшее, следовательно, опорным элементом будет 1); 3) меняем местами переменные и , остальные переменные оставляем на своих местах; 4) на место опорного элемента ставим отношение 1/(опорный элемент); 5) на остальных местах разрешающей строки записываем соответствующие элементы исходной таблицы, деленные на опорный элемент; 6) на свободные места разрешающего столбца ставим со знаком минус соответствующие элементы исходной таблицы, деленные на опорный элемент; 7) оставшиеся свободные места в новой симплекс-таблице заполняем построчно следующим образом: из строки элементов исходной таблицы вычитаем произведение ее элемента из разрешающего столбца на уже заполненную разрешающую строку новой таблицы. Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц: |
| | | | | | | | -3 | -8 | 6 | -1 | 9 | | | 1 | 2 | -1 | 1 | 0 | | | 1 | 1 | 1 | 2 | 6 | | | 3 | 7 | -7 | -1 | -15 | | |
|
| | | | | | | | -2 | -6 | 5 | 1 | 9 | | | 1 | 2 | -1 | 1 | 0 | | | -1 | -3 | 3 | -2 | 6 | | | 4 | 9 | -8 | 1 | -15 | | |
|
| | | | | | | | -2/5 | -6/5 | 1/5 | 1/5 | 9/5 | | | 3/5 | 4/5 | 1/5 | 6/5 | 9/5 | | | 1/5 | 3/5 | -3/5 | -13/5 | 3/5 | | | 4/5 | -3/5 | 8/5 | 13/5 | -3/5 | | |
|
| | | | | | | | 0 | 2 | -1 | -5 | 3 | | | 1/3 | -4/3 | 1 | 14/3 | 1 | | | 1/3 | 5/3 | -1 | -13/3 | 1 | | | 1 | 1 | 1 | 0 | 0 | | |
В нижней строке последней симплекс-таблицы нет отрицательных элементов, следовательно, минимум вспомогательной целевой функции достигнут и есть угловая точка допустимого множества исходной задачи линейного программирования, тогда
Страницы: 1, 2
|