- •Факультет информационных технологий и управления
- •1 Математическое описание линейных систем
- •1.1 Дифференциальное уравнение системы.Характеристическое уравнение и его корни
- •1.2 Разложение передаточной функции на сумму простых слагаемых. Вычисление импульсной переходной характеристики ω(t) спомощью обратного преобразования Лапласа и переходной характеристикиh(t)
- •1.3 Построение лачх и лфчх
- •1.4 Уравнение состояния в нормальной форме,схема моделирования
- •1.5 Уравнение состояния в канонической форме,
- •1.6 Решение уравнения состояния в нормальной и канонической формах
- •1.7 Проверка: одинаково ли значение коэффициента усиления по передаточной функции, переходной характеристике,моделям в пространстве состояний, аналитической записи импульсной переходной характеристики
- •2 Линейное программирование
- •2.1 Математическая модель задачи. Нахождение оптимального плана х* и экстремального значения функции
- •2.2 Построение и решение задачи, двойственной к исходной. Сравнение решения прямой и двойственной задач
- •2.3 Получение целочисленного решения путем введения дополнительных ограничений по методу Гомори
- •3.2.2 Метод Ньютона-Рафсона
- •3.3 Нахождение экстремального значения функцииF(X) с учетом системы ограничений задачи
- •3.3.1 Метод допустимых направлений Зойтендейка
- •3.3.2 Метод линейных комбинаций
- •3.3.3 Условия теоремы Куна-Таккера
- •4 Тексты программ в среде matlab
- •4.1 Математическое описание линейных систем
- •4.2 Линейное программирование
- •4.3 Нелинейное программирование
2.2 Построение и решение задачи, двойственной к исходной. Сравнение решения прямой и двойственной задач
Рассмотрим соотношение прямой и двойственной задач:
(2.2)
Число переменных двойственной задачи совпадает с числом ограничений прямой задачи.
Исходная задача:
F(x)=-1x1-5x2-3x3 (max)при следующих ограничениях:
Так как требуется найти максимум целевой функции, то неравенства в системе ограничений должны быть вида <. Второе неравенство ограничений прямой задачи умножим на (-1):
тогда
, ,
Двойственная задача будет иметь 4 переменные, так как прямая содержит 4 ограничения. В соответствии с (2.2) запишем двойственную задачу в виде:
,
Тогда условие пример следующий вид:
,
следовательно:
.
Так как в прямой задаче есть ограничение равенство, то на у1, соответствующая переменная двойственной задачи, не накладывается условие неотрицательности.
Введем дополнительные переменные:
Составим симплекс-таблицу:
Таблица 2.5
БП |
Своб. члены |
НП | |||
y1 |
y2 |
y3 |
y4 | ||
y5 |
1 |
5 |
-5 |
0 |
4 |
y6 |
5 |
-4 |
0 |
5 |
-5 |
y7 |
3 |
1 |
5 |
4 |
-2 |
F |
0 |
-3 |
9 |
-42 |
9 |
Таблица 2.6
БП |
Своб. члены |
НП | |||
Y1 |
Y2 |
Y3 |
Y7 | ||
Y5 |
-5 |
7 |
5 |
8 |
2 |
Y6 |
25/2 |
-13/2 |
-25/2 |
-5 |
-5/2 |
Y4 |
3/2 |
-1/2 |
-5/2 |
-2 |
-½ |
F |
-27/2 |
3/2 |
63/2 |
-24 |
9/2 |
Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный член (-5). Ведущая строка - X5. В строке X5так же найдем максимальный по модулю отрицательный свободный член (2). Столбец X7 - ведущий.Так как в строке с отрицательным свободным членом нет отрицательных элементов, то система ограничений не совместна и задача не имеет решения Запишем соответствие между переменными прямой и двойственной задач:
Исходные переменные Дополнительные переменные
прямой задачи прямой задачи
x1 x2 x3 R x4 x5 x6
(2.3)
y5 y6 y7 y1 y2 y3 y4
Дополнительные переменные Исходные переменные
двойственной задачи двойственной задачи
Соответствие не означает равенство. Оптимальное решение прямой задачи определяется коэффициентами F-строки. Переменные прямой задачи приравниваются к коэффициентамприсоответствующим им небазисных переменных в F-строке оптимальной симплекс-таблицы двойственной задачи.
2.3 Получение целочисленного решения путем введения дополнительных ограничений по методу Гомори
При решении задачи не было получено решения, т.к. система ограничений не совместна.
3 Нелинейное программирование
3.1 Построение ОДЗП, выбор начальной точки поиска
Целевая функция имеет вид:
Построим ОДЗП:
Пусть x1=3, тогдаx2=5
Пусть x1=0, тогдаx2=-4
Пусть x1=3, тогдаx2=5
Пусть x1=0, тогдаx2=6
Рисунок 3.1 - ОДЗП
Внутри области допустимых значений выбираем точку x0, которая в дальнейшем будет являться начальной в процессе поиска экстремума:
x0=(1;3).
3.2 Нахождение экстремального значения функцииF(x) без учета ограничений на переменные
3.2.1 Метод наискорейшего спуска
В методе наискорейшего спуска (подъема) очередная точка при поиске максимума функции вычисляется по формуле:
где направление движения задается вектором антиградиента функцииF(x), вычисленном в точке, а величина шага перемещения определяется числовым параметром.
Найдем градиент :
.
На первом шаге движение осуществляется из точки вдоль вектора
-в новую точку:
Величина шагана любом шаге выбирается из условия обеспечения экстремума функции в рассматриваемом направлении. Подставляя координаты точкив функцию, получим:
Из условия:
;
найдем :
;
В результате после первого шага координаты очередной точки получаются равными:
Вычисляем
.
На втором шаге движение осуществляется в направлении вектора
-:
Подставив полученные выражения для x12 и x22 в функцию цели и преобразовав получаем
;
Из условия:
;
найдем :
;
Тогда:
В результате после второго шага координаты очередной точки получаются равными:
Вычисляем :
На третьем шаге движение осуществляется в направлении вектора
-:
;
Из условия:
;
найдем :
;
В результате после третьего шага координаты очередной точки получаются равными:
После проведения четвертой итерации получаем точку
На четвертой итерации закончим вычисления, значение функции цели:
Рисунок 3.2 – Графическая интерпретация метода наискорейшего спуска
Как видим из графической интерпретации, происходит приближение к экстремальному значению функции без учета ограничений.