- •1 Математическое описание линейных систем
- •1.1 Дифференциальное уравнение системы. Характеристическое уравнение и его корни
- •1.2 Разложение передаточной функции на сумму простых слагаемых. Вычисление импульсной переходной характеристики ω(t) с помощью обратного преобразования Лапласа и переходной характеристики h(t)
- •1.3 Построение лачх и лфчх
- •1.4 Уравнение состояния в нормальной форме,схема моделирования
- •1.5 Уравнение состояния в канонической форме,
- •1.6 Решение уравнения состояния в нормальной и канонической формах
- •2 Линейное программирование
- •2.1 Математическая модель задачи. Нахождение оптимального плана х* и экстремального значения функции
- •2.2 Построение и решение задачи, двойственной к исходной. Сравнение решения прямой и двойственной задач
- •2.3 Получение целочисленного решения путем введения дополнительных ограничений по методу Гомори
- •3 Нелинейное программирование
- •3.1 Построение одзп, выбор начальной точки поиска
- •3.2 Нахождение экстремального значения функции f(X) без учета ограничений на переменные
- •3.2.1 Метод наискорейшего спуска
- •3.2.2 Метод Ньютона-Рафсона
- •3.3 Нахождение экстремального значения функции f(X) с учетом системы ограничений задачи
- •23.3.1 Метод допустимых направлений Зойтендейка
- •3.3.2 Метод линейных комбинаций
- •3.3.3 Условия теоремы Куна-Таккера
- •4 Тексты программ в среде matlab
- •4.1 Математическое описание линейных систем
- •4.2 Линейное программирование
- •4.3 Нелинейное программирование
3.3.2 Метод линейных комбинаций
Вычислим градиент функции F(x):
На следующем этапе вычислим значение градиента в точке x0:
;
Суть метода линейных комбинаций заключается в линеаризации функции F(x) и замене ее линейной функцией в соответствии с выражением:
Решаем задачу линейного программирования при следующих ограничениях:
Процедура решения задачи иллюстрируется последовательностью симплекс таблиц:
Таблица 3.1
.БП |
Своб. члены |
НП |
|
x1 |
x2 |
||
x3 |
2 |
-1 |
2 |
x4 |
550 |
49 |
10 |
w0 |
0 |
55 |
22 |
Решение задачи:
Произведем корректировку найденного решения в соответствии с выражением:
Найдем значение , которое максимизирует F(x1):
Т.к. то примем .
Вычислим координаты точки x1 и значения вектора градиента в этой точке:
Линеаризуем функцию F(x) относительно точки x1 и заменим ее линейной функцией w(x1):
Решаем задачу линейного программирования при следующих ограничениях:
Процедура решения задачи иллюстрируется последовательностью симплекс таблиц:
Т аблица 3.2
Базисные переменные |
Свободные члены |
Небазисные переменные |
|
x1 |
x2 |
||
x 3 |
2 |
-1 |
2 |
x4 |
550 |
49 |
10 |
w0 |
0 |
6 |
-7 |
Таблица 3.3
Базисные переменные |
Свободные члены |
Небазисные переменные |
|
x1 |
x3 |
||
x2 |
1 |
0 |
1/2 |
x4 |
540 |
49 |
-5 |
w0 |
7 |
6 |
7/2 |
Решение задачи:
Произведем корректировку найденного решения:
Найдем значение , которое минимизирует F(x2):
Вычислим координаты точки x2 , значения вектора градиента и значение функции цели в этой точке:
следовательно, x2 является точкой экстремума.
Рисунок 3.4 - Графическая интерпретация метода линейных комбинаций
3.3.3 Условия теоремы Куна-Таккера
Составляем функцию Лагранжа:
здесь – левые части ограничений, приведенных к нулевой правой части; – неопределенные множители Лагранжа.
Т.к. функция имеет минимум по x и максимум по λ, то
;
Частные производные функции Лагранжа определяются выражениями:
Для того, чтобы вышеуказанные выражения имели вид равенств, введем в них дополнительные переменные:
Решение этой системы из четырех алгебраических уравнений, содержащих восемь неизвестных, можно найти с помощью симплекс-процедуры. На первом шаге в базис включаются все введенные дополнительные переменные, тогда первая симплекс-таблица соответствует таблице 3.4. Строка для функции цели отсутствует. Процедура решения иллюстрируется симплекс-таблицами (таблицы 3.4-3.5).
Проведем симплекс – преобразования и найдем допустимое базисное решение.
Т аблица 3.4
БП |
Своб. члены |
НП |
|||
х1 |
х2 |
|
|
||
v1 |
6 |
-14 |
-7 |
1 |
-49 |
v2 |
-7 |
-7 |
-8 |
-2 |
-10 |
w1 |
2 |
-1 |
2 |
0 |
0 |
w2 |
550 |
49 |
10 |
0 |
0 |
Таблица 3.5
БП |
Своб. члены |
НП |
|||
х1 |
v2 |
|
|
||
v1 |
97/8 |
161/8 |
-7/8 |
11/4 |
-161/4 |
x2 |
7/8 |
7/8 |
-1/8 |
1/4 |
5/4 |
w1 |
1/4 |
-11/4 |
2/8 |
-1/2 |
-5/4 |
w2 |
2165/4 |
161/4 |
5/4 |
-5/4 |
-25/2 |
Т.к. в столбце свободных членов нету отрицательных элементов, то полученое решение является допустимым.
Следовательно, координаты точки экстремума x*:
;
Значение функции цели в этой точке: