- •Классификация задач оптимизации.
- •При проектировании систем необходимо выполнить комплекс из 8-ми работ
- •Доказательство. Необходимо доказать, что выполняется равенство
- •Пусть дана функция f (х1, х2, …, Хn.) Её градиент:
- •Основная задача.
- •Теорема о крайней точке
- •Доказательство.
- •Пусть задача имеет смешанные ограничения.
- •Получим задачу (2):
- •В симплексную таблицу добавляются 2 столбца-столбцы контрольных сумм. В
- •Предварительный этап:
- •Этап первый
- •Этап второй
- •Этап третий
- •Предназначен для увеличения числа 0 матрицы .
- •Пусть имеется функция
- •Лекция №19.
- •Метод внутриштрафных функций. (Метод барьерных функций)
- •Метод внешних штрафных функций.
Пусть дана функция f (х1, х2, …, Хn.) Её градиент:
f (Х1, Х2, …, Хn.) = f (Х1, Х2, …, Хn.) f(Х1, Х2, …, Хn.)
Х1 , Х2 , …,
,…, f(Х1, Х2, …, Хn.)
Хп .
Вернёмся к задаче f (Х1, Х2, …, Хn.) == Ci Хi max и ограничениям (2).
f (Х1, Х2, …, Хn.) = ( C1, C2, …, Cn).
f (Х1,Х 2) = C1 Х1+ C2Х 2= 0. Откуда Х 2 = - C1 Х1,
C2
Функция возрастает при перемещении основной прямой в направлении градиента функции (см. рис.1).
Если область не ограничена, то задача не имеет оптимального решения.
На геометрической интерпретации основан графический метод решения задачи. Он применяется , когда n=2,3.
Вернёмся к постановке задачи линейного программирования в стандартной форме
f (Х1,Х 2) = C1 Х1+ C2Х 2 max,
11Х1+12Х2+…+1nХn b1;
21Х1+22Х2+…+2nХn b2;
……………………………..
m1Х1+m2Х2+…+mnХn bm;
Х1,Х2,…,Хn 0 ;
Неравенство временно превращается в равенство и вычисляются Х1 и Х 2. Эти точки наносятся на график и строятся соответствующие ограничивающие линии. Получается некая область. Далее перемещают опорную прямую по направлению градиента функции до пересечения этой прямой с самой крайней (верхней) точкой области. Х1 и Х 2 , являющиеся координатами этой точки, и являются оптимальными значениями. Но полученные значения не точны .Чтобы получить точные значения, необходимо приравнять выражения, соответствующие двум прямым, на которых располагается полученная точка. Если прямая совпадает с гранью, то можно взять любую точку, принадлежащую этой грани.
Х2) = C1 Х1 + C2Х2 max, где C1, C2 0
Лекция 5. Основная задача линейного программирования.
Большинство алгоритмов задачи линейного программирования основаны на основной задаче линейного программирования.
Постановка задачи:
(2)
Любая задача линейного программирования, записанная в другой форме отличной от представленной (канонической), может быть сведена к основной задаче линейного программирования: max f(x)=min (-f(x)).
Если в системе ограничений содержится неравенство ( или ), нужно перейти
к (=):
если
Таким образом, эти две задачи эквивалентны, т.е. задача поставлена в стандартной постановке, эквивалентна основной задаче линейного программирования с точностью до размерности. Следовательно, все свойства задачи поставленной в стандартной форме справедливы и для основной задачи линейного программирования.
Вопрос: имеет ли решение эта задача зависит от системы (2). Т.е. совместима система или противоречива.
1.Система совместима, если ранг системы, образованными коэффициентами левой части равны рангу расширенной системы.
В нашей системе ранг - r < m. Если в системе уравнений (2) m=n, то система (если она противоречива) имеет единственное решение. Если это решение положительно х>0, то это решение будет оптимальным.
Поэтому мы будем рассматривать случай, когда число ограничений m<n и будем предполагать, что все уравнения системы ограничений линейно-независимы (ни одно выражение не может быть выражено линейной комбинацией другого).
Если r=m, то система имеет бесконечное множество решений. Если не отрицательных решений нет, то основная задача не имеет допустимого решения, а так же оптимального. Если есть не отрицательные, то нам нужно из этих всех решений найти оптимальное, т.е. то, при котором функция минимальна.
2.Система противоречива.
В системе уравнений m переменных, где m=n-r. Эти переменные через которые выражается m называются свободными переменными, а m переменные называют базисными.
Выразим m переменные через n-r. Пусть это будут первые переменные:
(3)
путем преобразования системы (2).
Набор называют базисом системы. Выразим через свободные переменные, получится:
Если подставить в (3) вместо свободных какие-то другие, то будем получать значение базисных переменных.
В качестве базисных переменных можно выбрать любые n-переменных из свободного числа m-переменных. Общее число базисных решений будет равно числу сочетаний:
Нас интересуют положительные базисные решения, которые называются допустимыми базисными решениями. Может оказаться, что все b=0, то такое решение называется вырожденным.
Нужно найти оптимальное решение, т.о. намечается подход к решению задачи - найти допустимые базисные решения, затем перебрать их и то при котором функция будет минимальна и будет оптимальным. Таким образом, нужно перебрать все допустимые базисные решения.
Геометрическая интерпретация основной задачи линейного программирования.
Число переменных в задачи на 2 или 3 больше числа ограничений, т.е. n-m =2(3)
2-на плоскости, 3-в пространстве.
Рассмотрим когда n-m=2. Выберем в качестве свободных переменных х1,х2. Тогда остальные будут базисные. Тогда можно записать:
Построив график находим x1 и x2-оптимальные.
Лекция 6. СВЯЗЬ МЕЖДУ КРАЙНИМИ ТОЧКАМИ ОДР И ДОПУСТИМЫМИ БАЗИСНЫМИ РЕШЕНИЯМИ