MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Математика\Optimization Toolbox

А.Г.Трифонов. "Постановка задачи оптимизации и численные методы ее решения"
3. Методы условной оптимизации

В оглавление книги \ К следующему разделу \ К предыдущему разделу

3.1. Линейное программирование

Под линейным программированием понимается раздел теории экстремальных задач, в котором изучаются задач и минимизации (или максимизации) линейных функций на множествах, задаваемых системами линейных равенств и неравенств. В общем случае задача линейного программирования формулируется следующим образом. Найти вектор х* (x*1, ..., х*n), определяющий максимум (минимум) линейной форме

f(x) с1x1 + с2x2+...+сnxn

при ограничениях:

a11x1 + … a1nxn b1;

. . . . . . . . . . . . . . . . . . .

am1x1 + … amnxn bm;

am+1x1+… am+1,nxn bm+1;

. . . . . . . . . . . . . . . . . . .

akx1 + … aknxn bm;

ak+1 x1 + … ak+1nxn bm;

am+1x1 + … am+1,nxn bm+1;

. . . . . . . . . . . . . . . . . .

alx1 + … alnxn bl;

xi 0; i 1, …, n.

Каждое из условий-неравенств определяет полупространство, ограниченное гиперплоскостью. Пересечение полупространств образует выпуклый п-мерный многогранник Q. Условия равенства выделяют из n-мерного пространства (п-l) -мерную плоскость, пересечение которой с областью Q дает выпуклый (n-l) -мерный многогранник G. Экстремальное значение линейной формы (если оно существует) достигается в некоторой вершине многогранника. При вырождении оно может достигаться во всех точках ребра или грани многогранника. В силу изложенного для решения задачу линейного программирования теоретически достаточно вычислить значения функции в вершинах многогранника и найти среди этих значений наибольшее или наименьшее. Однако в практических задачах количество вершин области G настолько велико, что просмотр их даже с использованием ЭВМ невозможен. Поэтому разработаны специальные численные методы решения задач линейного программирования, которые ориентируются в основном на две формы записи задач. Каноническая форма задачи линейного программирования:

f(x) с1х1 + ...+ сnxn > max(min);

a11x1 +… a1nxn b1;

. . . . . . . . . . . . . . . . . .

amx1 +… amnxn bm;

xi 0; i 1, …, n.

или в матричной форме:

(с, х) > max(min);

Ax b,

х 0.

Здесь А (аij) - (mхn) - матрица условий. Ее столбцы (a1j, ..., аmj)T , j 1, ..., п, называются векторами условий. Вектор b (b1, ..., bm)T носит название вектора правых частей, а с (с1, …, сn) - вектора коэффициентов линейной формы.

Задача линейного программирования с однотипными условиями

f(x) с1х1 + ...+ сnxn > max(min);

a11x1 +… a1nxn b1;

. . . . . . . . . . . . . . . . . .

amx1 +…amnxn bm;

или в матричной форме:

, х) > max(min);

Ax b,

Любую задачу можно привести к каждой из приведенных форм с помощью приемов, описанных ниже.

Переход к эквивалентной системе неравенств.

Знак неравенства можно поменять на обратный, меняя знаки свободного члена и коэффициентов. Например, ограничение

a11x1 +…a1nxn b1;

можно заменить условием

-a11x1 +…-a1nxn -b1.

Переход от ограничения-неравенства к равенству

Для этого необходимо ввести дополнительную неотрицательную переменную. Так, условие

a1x1 +…anxn b.

эквивалентно двум ограничениям:

-a11x1+…-a1nxn+xn+1 b; xn+1 b1.

Представление ограничения-равенства парой неравенств.

Ограничение

alx1 +… anxn b;

можно представить парой условий:

a11x1 +… a1nxn b1.

a11x1 +…-a1nxn -b1.

Переход к неотрицательным переменным

Если на знак переменной хi не наложено ограничений, можно заменить ее разностью двух неотрицательных переменных:

xi xn+2 - xn+1, xn+1 0; xn+2 0.

Переход от переменных, ограниченных снизу, к неотрицательным переменным

Если переменная ограничена снизу хi bi то, заменив ее по формуле хi уi + bi переходим к задаче с неотрицательной переменной уi 0.

Наиболее употребительным численным методом решения задач линейного программирования является симплекс-метод.

Идея этого метода состоит в следующем. Отыскиваются некоторая вершина многогранника G и все ребра, выходящие из этой вершины. Далее перемещаются вдоль того из ребер, по которому функция убывает (при поиске минимума), и попадают в следующую вершину. Находят выходящие из нее ребра и повторяют процесс. Когда приходят в такую вершину, в которой вдоль всех выходящих из нее ребер функция возрастает, то минимум найден. Отметим, что, выбирая одно ребро, исключают из рассмотрения вершины, лежащие на остальных траекториях. В результате количество рассматриваемых вершин резко сокращается и оказывается посильным для ЭВМ. Симплекс-метод весьма эффективен и широко применяется для решения задач линейного программирования.

В оглавление книги \ К следующему разделу \ К предыдущему разделу


Поиск по сайту:

Система Orphus

Яндекс.Метрика