Классификация методов оптимизации

Вопрос 1. Классификация методов оптимизации. Общая запись задач оптимизации задаѐт большое разнообразие их классов. От класса задачи зависит подбор метода (эффективность еѐ решения). Классификацию задач определяют: целевая функция и допустимая область (задаѐтся системой неравенств и равенств или более сложным алгоритмом). Методы оптимизации классифицируют в соответствии с задачами оптимизации: Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом. Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции. Существующие в настоящее время методы поиска можно разбить на три большие группы: o детерминированные; o случайные (стохастические); o комбинированные. По критерию размерности допустимого множества, методы оптимизации делят на методы одномерной оптимизации и методы многомерной оптимизации. 28 По виду целевой функции и допустимого множества, задачи оптимизации и методы их решения можно разделить на следующие классы: Задачи оптимизации, в которых целевая функция и ограничения являются линейными функциями, разрешаются так называемыми методами линейного программирования (именно им мы уделим более пристальное внимание далее). f x j g x , i 1,...,m В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи: если и – выпуклые функции, то такую задачу называют задачей выпуклого программирования; f x j g x , i 1,...,m если , то имеют дело с задачей целочисленного (дискретного) программирования. X Z По требованиям к гладкости и наличию у целевой функции частных производных, их также можно разделить на: прямые методы, требующие только вычислений целевой функции в точках приближений; методы первого порядка: требуют вычисления первых частных производных функции; методы второго порядка: требуют вычисления вторых частных производных, то есть гессиана целевой функции. Помимо того, оптимизационные методы делятся на следующие группы: аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера); численные методы; графические методы. В зависимости от природы множества X задачи математического программирования классифицируются как: задачи дискретного программирования (или комбинаторной оптимизации) – если X конечно или счѐтно; задачи целочисленного программирования – если X является подмножеством множества целых чисел; задачей нелинейного программирования, если ограничения или целевая функция содержат нелинейные функции и X является подмножеством конечномерного векторного пространства. Если же все ограничения и целевая функция содержат лишь линейные функции, то это – задача линейного программирования. 29 Кроме того, разделами математического программирования являются параметрическое программирование, динамическое программирование и стохастическое программирование. Математическое программирование используется при решении оптимизационных задач исследования операций. Способ нахождения экстремума полностью определяется классом задачи. Но перед тем, как получить математическую модель, нужно выполнить 4 этапа моделирования: Определение границ системы оптимизации. Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается. Выбор управляемых переменных. «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные) Определение ограничений на управляемые переменные. … (равенства и\или неравенства). Выбор числового критерия оптимизации. Создаѐм целевую функцию. Вопрос 2. Постановка задачи линейного программирования и свойства ее решений. Линейное программирование – раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений. Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда – необходимость разработки новых методов. Формы записи задачи линейного программирования: Общей задачей линейного программирования называют задачу (1) n j j j 1 max min Z c x 30 при ограничениях (2) n ij j i 1 j 1a x b i 1,...,m (3) n ij j i 1 2 j 1a x b i m 1,...,m (4) n ij j i 2 j 1a x b i m 1,...,m (5) j 1 x 0 j 1,n – произвольные (6) j x i j n1,...,n где – заданные действительные числа; (1) – целевая функция; (1) – (6) –ограничения; – план задачи. j ij i c,a,b1n x x;...;x Пусть ЗЛП представлена в следующей записи: (7) max Z cx (8) 11 22 nn 0 AxAx... AxA (9) 1 2 n x0, x0,..., x0 Чтобы задача (7) – (8) имела решение, системе еѐ ограничений (8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай вообще невозможен. При система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть . В этом случае система векторов содержит базис – максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные переменных будут свободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов . Этому базису соответствуют базисные r n r n j x 0 j 1,n r n1 2 n A,A,...,Arn Cn r 1 2 m A,A,...,A31 переменные , а свободными будут переменные . 1 2 mx,x,...,xm 1 m 2 n x,x,...,x Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом). Теорема. Если система векторов содержит m линейно независимых векторов , то допустимый план 1 2 n A,A,...,A1 2 m A,A,...,A (10) 1 2 m n m x x ;x ;...;x ;0;0;...;0 является крайней точкой многогранника планов. Теорема. Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией. Графический способ решения ЗЛП. Геометрическая интерпретация экономических задач дает возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования более сложных свойств. ЗЛП с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства ОЗЛП, приводит к идее ее решения, делает геометрически наглядными способы решения и пути их практической реализации. Пусть дана задача (11) 11 2 2 max Z cxcx (12) 11 1 12 2 1 21 1 22 2 2 m1 1 m2 2 m a x a x b a x a x b ............................. a x a x b (13) 1 2 x0, x0 32 Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (12), (13) задает на плоскости некоторую полуплоскость. Полуплоскость – выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (11) – (13) есть выпуклое множество. 12 xOx Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП – непустое множество, например многоугольник . 123456 AAAAAA Рис. 1 Выберем произвольное значение целевой функции . Получим . Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (11) параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения). 0 Z Z11 2 2 0 cxcxZ0 ZZ Найдѐм частные производные целевой функции по и : 1 x2 x , (14) 1 1 Z c x . (15) 2 2 Z c x Частная производная (14) (так же как и (15)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, и – скорости возрастания соответственно вдоль осей и . Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции: 1 c2 cZ 1 Ox2 Ox12 c c,c 1 2 Z Z c , x x 33 Вектор указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. c Вектор перпендикулярен к прямым семейства . 12 c c,cZ const 11 2 2 cxcxZ Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения. 1. С учетом системы ограничений строим область допустимых решений . 2. Строим вектор наискорейшего возрастания целевой функции – вектор градиентного направления. 12 c c,c 3. Проводим произвольную линию уровня . 0 Z Z 4. При решении задачи на максимум перемещаем линию уровня в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точке). В случае решения задачи на минимум линию уровня перемещают в антиградиентном направлении. 0 Z Zc 0 Z Z 5. Определяем оптимальный план и экстремальное значение целевой функции . 1 2 x x,xZ z x Симплексный метод решение ЗЛП. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит: 1) умение находить начальный опорный план; 2) наличие признака оптимальности опорного плана; 3) умение переходить к нехудшему опорному плану. Пусть ЗЛП представлена системой ограничений в каноническом виде: . n ij j i i j 1a x b , b 0 i 1,...,m Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства – с коэффициентом, равным нулю. i b0 Пусть система ограничений имеет вид 34 n ij j i i j 1a x b , b 0 i 1,...,m Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные . Получим систему, эквивалентную исходной: n 1 x0 i 1,...,m , n ij j i i j 1a x b , b 0 i 1,...,m которая имеет предпочтительный вид . 0 1 2 m n m x 0;0;...;0;b ;b ;...;b В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю . n 1 c0 i 1,...,m Пусть далее система ограничений имеет вид . n ij j i i j 1a x b , b 0 i 1,...,m Сведѐм еѐ к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему n 1 x0 i 1,...,m . n ij j n 1 i i j 1a x x b , b 0 i 1,...,m Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть (при ) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные . В целевую функцию n 1 xi b0 0 1 2 m n x 0;...;0; b ; b ;...; b i 35 переменные , вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом – М для задачи на максимум, где М – большое положительное число. Полученная задача называется М- задачей, соответствующей исходной. Она всегда имеет предпочтительный вид. i Пусть исходная ЗЛП имеет вид , (16) n j j j 1 max min Z c x , (17) n ij j i i j 1a x b , b 0 i 1,...,m , (18) j x0 j 1,...,n причѐм ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так: (19) n m j j i j 1 t 1 max min Z c x M (20) n ij j i i j 1a x b , i 1,...,m (21) j i x 0 j 1,n , 0, i 1,...,m Задача (19) – (21) имеет предпочтительный план. Еѐ начальный опорный план имеет вид 0 1 2 m n x 0;0;...;0;b ;b ;...;b Если некоторые из уравнений (17) имеют предпочтительный вид, то в них не следует вводить искусственные переменные. Теорема. Если в оптимальном плане (22) 12 n12m x x;x;...;x; ; ;...; М-задачи (19) – (21) все искусственные переменные , то план является оптимальным планом исходной задачи (16) – (18). i 0 i 1,...,m 12 n x x;x;...;x36 Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М – задачу, которая имеет начальный опорный план 0 1 2 m n x 0;0;...;0;b ;b ;...;b Решение исходной задачи симплексным методом путем введения искусственных переменных называется симплексным методом с искусственным базисом. i Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные , то его первые n компоненты дают оптимальный план исходной задачи. i 0 Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны. Признаки оптимальности. Теорема. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки неотрицательны, то такой план оптимален. i j 1,n Теорема. Если исходная задача решается на минимум и для некоторого опорного плана все оценки не положительны, то такой план оптимален. i j 1,n Рассмотрим классические примеры ЗЛП. Задача о смесях. В различных отраслях народного хозяйства возникает проблема составления таких рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего определенными свойствами. К этой группе задач относятся задачи о выборе диеты, составлении кормового рациона в животноводстве, шихт в металлургии, горючих и смазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве и т. д. Высокий уровень затрат на исходные сырьевые материалы и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными свойствами при наименьших затратах на исходные сырьевые материалы. Пример. Для откорма животных используется три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 800 г. жиров, 700 г. белков и 900 г. углеводов. Содержание в 1 кг. 37 каждого вида комбикорма жиров, белков и углеводов (граммы) приведено в таблице 1: Таблица 1. Содержание жиров, белков и углеводов (граммы) в 1 кг. каждого вида комбикорма Содержание в 1 кг. Комбикорм А В С Жиры 320 240 300 Белки 170 130 110 Углеводы 380 440 450 Стоимость 1 кг 31 23 20