Найти оптимальный план x* и экстремальное значение функции F(x). Построить задачу, двойственную к исходной, решить её и сравнить решения прямой и двойственной задач. Если решение не является целочисленным, получить целочисленное решение путём введения дополнительных ограничений по методу Гомори.
Вариант 18. Условия задачи: F(x) = 3x1 + x2 -6x3 (max)
Для удобства заполнения симплекс-таблицы приведем ограничения к виду «≤», умножив обе части неравенства на «-1».
Приведем ограничения к виду равенств, введя дополнительные переменные со знаком «+», т.к. ограничения вида «≤»:
Матрицы A, Bи CTвыглядят следующим образом: A= ;B = ;СT = ; Если дополнительная переменная со знаком «-», то все коэффициенты перед переменными xi и свободный член bj заносятся с противоположным знаком. Если цель минимизация, то коэффициенты функции цели заносятся без изменения знака.
За базисные переменные принимаем дополнительные переменные x4, x5,x6. А переменные x1, x2,x3 будут являться небазисными. Свободные члены определяют решение задачи.
1 шаг: Производится поиск базисного решения. Т.к. все свободные члены положительны, значит, решение является допустимым. Переходим сразу к шагу 5 для нахождения оптимального решения.
5 шаг: Признаком оптимальности является неотрицательность переменных в F-строке. c1, c2 < 0. Следовательно, решение не является оптимальным. В базис будет включаться та из небазисных переменных, которая находится в столбце с элементом cl, которому соответствует максимальное абсолютное значение.
В данной задаче это элемент c1 = -3< 0.Ведущий столбец x1.
Выбор ведущей строки определяется минимальным симплексным отношением . Следует рассматривать только положительные симплексные отношения. В данной задаче минимальное симплексное отношение получается в строке x5 = 6. Таким образом, ведущая строка x5. Ведущий элемент a21 = 2.
Производим пересчет симплекс-таблицы:
; ; ; ; ;
; ; ; ;
; ; ;
; ; ; ;
Новая симплекс-таблица выглядит следующим образом:
БП СЧ НП x5 x2 x3 x4
x1
x6 3
6
30 -3
10
3
Fmax 18
БП СЧ НП x5 x4 x3 x2
x1
x6
Fmax
БП СЧ НП x6 x4 x3 x2
x1
x5
Fmax
Fmax = .
Оптимальный план: x2 = x1 = x5 =
Выводим условия двойственной задачи:
F(x) = 3x1 + x2 -6x3 (max)
Так как задача максимизации, то условия приводим к виду «≤»:
Матрицы AT, Bи Cвыглядят следующим образом: AT= ;B = ;С = ;
Количество переменных в двойственной задаче равно количеству переменных в прямой, и наоборот.
Тогда ATY ≥ C примет вид:
Функция цели F(y) = BTY = = 39y1 + 12y2 + 24y3 (min) Так как среди ограничений прямой задачи нет равенств и на все переменные наложено условие неотрицательности, то двойственная задача симметрична.
Далее решение производится симплекс-методом.
Вводим дополнительные переменные и приводим ограничения к виду равенств.
Так как цель минимизация, коэффициенты функции цели заносятся в таблицу без изменения знака.
1шаг: Так как не все элементы столбца свободных членов положительны, значит допустимое базисное решение не найдено. Производим поиск допустимого базисного решения, используя шаг 2.
2шаг: Производим пересчет симплекс-таблицы:
Определяем какую небазисную переменную введем в базис и какую базисную переменную выведем из базиса. Для этого выбираем любой из отрицательных элементов столбца свободных членов. Пусть это будет b1= -3 < 0.Просматриваем строку, в которой находится этот элемент, и выбираем любой отрицательный элемент. Пусть это будет a11 = -6 < 0.
Если в строке нет отрицательных элементов, то задача не имеет решения.
Приоритетом в выборе элементов является максимальное абсолютное значение модуля элемента.
Таким образом, ведущим элементом будет являться элемент a11 = -6. Ведущая строка y4, ведущий столбец – y1. Из базиса исключается переменная y4, в базис вводится переменная y1.
Производим пересчет симплекс-таблицы.
Новая симплекс-таблицы выглядит следующим образом:
БП СЧ НП y4 y2 y3 y1
y5
y6
9
-1
-3
-5 Fmin
-1
БП СЧ НП y4 y2 y5 y1
y3
y6
Fmin
Оптимальное решение найдено. Fmin = .
Оптимальный план: y1 = . y3 = . y6 = .
Решения прямой и двойственной задачи совпадают.
Решение задачи без условия целочисленности приведено в пункте 1.
Составим дополнительное ограничение по строке, соответствующей переменной x2, так как у неё наибольшая дробная часть {x2} = . Решение производим по алгоритму Гомори для полностью целочисленной задачи.
x6 + x4 + x3 ≥ или x6 + x4 + x3 ≥
Приведем к виду равенства, введя дополнительную переменную x7 и домножим обе части неравенства на «-1»:
x6 x4 x3 +x7 = -
Расширенная симплекс-таблица выглядит следующим образом:
БП СЧ НП x6 x4 x3 x2
x1
x5
x7
Fmax
БП СЧ НП x7 x4 x3 x2
x1
x5
x6 5
1
0
0
0
-1
5 Fmax 22
Задание 2: Нелинейное программирование
Построить область допустимых значений переменных. Найти максимальное значение функции F(x) без учета ограничений на переменные, используя: а) метод наискорейшего спуска б) метод Ньютона Процесс оптимизации начинать с точки x0. Найти максимальное значение функции F(x) с учетом системы ограничений задачи, используя: а) метод допустимых направлений Зойтендейка б) условия теоремы Куна-Таккера Процесс оптимизации начинать с точки x0.
Так как экстремумом функции будет являться её минимум, градиент будем использовать с противоположным знаком.
1 шаг: Движение осуществляется из x0вдоль в новую точку x1:
Градиент в точке x0равен:
Координаты точки x1определяются выражением:
Величину шага определим из условия:
=
В результате точка x1:
2 шаг: Градиент в точке x1равен:
Координаты точки x2 определяются выражением:
Величину шага определим из условия:
В результате точка x2:
3 шаг: Градиент в точке x2равен:
Координаты точки x3 определяются выражением:
Величину шага определим из условия:
В результате точка x3:
В точке х3 функция достигает значения Fmax = -5,91;
Метод наискорейшего спуска неэффективен при приближении к точке экстремума, поэтому существует погрешность.
б) Так как функция цели квадратичная, экстремум будет найден за один шаг.
H-1= , где detH– определитель матрицы H. detH = 2∙10 - 4∙4 = 20 – 16 = 4.
AdjH – присоединенная к H матрица (транспонированная матрица алгебраических дополнений).
Найдем алгебраические дополнения элементов матрицы H: , тогда:
Тогда AdjH= ; H-1 = ; ;
Fmax = -8,5;
Равенство градиента нулю показывает, что найденная точка является экстремальной, а решение – оптимальным. Исходя из этого, можно построить графики функций и наглядно увидеть, что метод наискорейшего спуска оставляет погрешность и эффективен он только для задач с большим удалением начальной точки от точки максимума.
3) а)
Учитывая, что экстремум функции будет являться её минимумом, будем использовать градиент с противоположным знаком.
Градиент в точке х0 равен:
Выбираем наиболее сильные условия:
Находим значение как в методе наискорейшего спуска. . Данное значение не принадлежит найденному интервалу, поэтому .
Точка х1 равна:
Таким образом, точка попадает на ограничение х2 = 0.
Градиент в точке х1 равен:
Движение в этом направлении выводит за пределы ОДЗП, поэтому очередная точка поиска будет производиться в направлении S1:
Определим интервал изменения параметра α^1 при котором x2 принадлежит области допустимых значений переменных:
=>
Выбираем наиболее сильные условия:
-2 ≤ ≤ 4,2
Находим величину , которая обеспечит максимум функции F(x) в направлении S1:
Для этого в функцию цели подставляем координаты точки x2:
F( ) =
;
Значение = -4,5 не принадлежит найденному интервалу, поэтому принимаем значение равным граничному значению, .
Градиент в точке x2 равен:
Его направление перпендикулярно направлению вектора S1. Следовательно, данная точка является оптимальным решением.
Функция достигает экстремума в точке . Точка экстремума лежит на пересечении ограничивающих прямых и .
Fmin = 0.
б) Составим функцию Лагранжа:
Так как экстремум функции будет являться минимумом, то производная , а производная .
Запишем условия теоремы Куна-Таккера:
БП СЧ НП x1 x2 λ1 λ2 v1
v2
w1
w2 5
7
14
31 -2
-4
-2
5 -4
-10
7
-1 2
-7
0
0 -5
1
0
0
Решение, определяемое последней таблицей, соответствует допустимому базисному решению v1= 5; v2= 7; w1=14; w2=31; x1=x2= λ 1= λ2= 0. Выполняется условие x1∙v1=x2∙v2 = λ1∙w1=λ2∙w2 = 0, поэтому является оптимальным решением задачи.
При этом Fmin= 0.
Список использованной литературы:
1) Полный конспект лекций. Павлова А. В. БГУИР. 2) Математические основы теории систем, алгебраические структуры и матричные методы. Авторы: Ушаков, Хабалов, Дударенко, СПбГУ ИТМО 2005г. 3) Математические основы теории систем: Элементы теории и практикум: Учебное пособие. Ушаков А.В., Хабалов В.В., Дударенко Н.А., Москва, 2007 г.
