Лекции по "Экономике организации"

Общая характеристика методов  нулевого порядка.

В этих методах для определения  направления спуска не требуется  вы-числять производные целевой функции. Направление минимизации в данном случае полностью определяется последовательными вычислениями значений функции, и сводятся к построению траектории спуска , вдоль которой целевая функция убывает:

Общая характеристика методов  первого порядка.

Методы первого порядка основаны на свойствах градиента, поэтому они также называются градиентными методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции. 
В градиентных методах, если нет дополнительной информации, то из начальной точки разумно перейти в точку , лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска антиградиент – в точке , получаем итерационный процесс вида 
 
В координатной форме этот процесс записывается следующим образом: 
 
i =1,...,n;k= 0, 1, 2,...

В качестве критерия останова итерационного  процесса используют либо выполнение условия малости приращения аргумента , либо выполнение условия малости градиента , где в качестве нормы берется евклидово расстояние.  
Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий. 
Геометрическая интерпретация метода.

Градиентные методы отличаются друг от друга способами выбора величины шага

Метод конфигураций Хука-Дживса.

Стратегия поиска. Метод представляет собой комбинацию исследующего поиска с циклическим изменением переменных и ускоряющего поиска по образцу. Цель исследующего поиска – выявление локального поведения целевой функции и определение направления ее убывания. Эта информация используется при поиске по образцу вдоль направления убывания целевой функции.  
Исследующий поиск начинается из некоторой начальной точки , называемой старым базисом. В качестве множества направлений поиска выбирается множество координатных направлений. Задается величина шага, которая может быть различной для разных координатных направлений. Фиксируется первое координатное направление и делается шаг в сторону увеличения соответствующей переменной. Если значение исходной функции f(x) в пробной точке меньше значения функции в исходной точке, то шаг считается удачным. В противном случае из исходной точки делается шаг в противоположном направлении с последующей проверкой поведения функции. Если и в этом случае не происходит уменьшения функции, то происходит уменьшение шага и процедура повторяется. Исследующий поиск по данному направлению заканчивается, когда текущая величина шага становится меньше некоторой величины. После перебора всех координат исследующий поиск завершается, полученная точка называется новым базисом. 
Поиск по образцу заключается в движении по направлению от старого базиса к новому. Величина ускоряющего шага задается ускоряющим множи-телем . Успех поиска по образцу определяется с помощью исследующего поиска из полученной точки. Если значение функции в наилучшей точке меньше, чем в точке предыдущего базиса, то поиск по образцу удачен, в противном случае происходит возврат в новый базис, где продолжается исследующий поиск с уменьшенным шагом.  
Обозначим через – координатные направления: 
 
Отметим, что при поиске по направлению меняется только переменная , а остальные переменные остаются зафиксированными.

Алгоритм  метода.  
Шаг 1. Задать начальную точку , число - для остановки алгоритма, начальные значения приращений по координатным приращениям , ускоряющий множитель  
Шаг 2. Провести исследующий поиск по выбранному координатному направлению: 
 
Шаг 3. Проверить условия: 
а) если i < n, то положить i= i+1 и перейти к шагу 2. (продолжить исследующий поиск по оставшимся направлениям); 
б) если i = n, проверить успешность исследующего поиска: 
- если , перейти к шагу 4.  
- если , перейти к шагу 5.  
Шаг 4. Провести поиск по образцу. 
 
В точке провести исследующий поиск, в результате которого получается точка  
Если , то точка становится точкой нового базиса, а - точкой старого базиса. Перейти к шагу 5. . 
Если , то поиск по образцу считается неудачным, точки , аннулируются, точка остается точкой нового базиса, а - точкой старого базиса. Перейти к шагу 2.

Шаг5.Проверить условие окончания счета:

 а) если все , то поиск закончить ;

б) для тех i, для которых , уменьшить величину шага и перейти к шагу 2.

 

 Нелинейные задачи  математического программирования. Локальный и глобальный экстремум,  условия оптимальности, условия  Куна—Таккера. Задачи об условном экстремуме и метод множителей Лагранжа. Методы проектирования. Метод проекции градиента. Метод условного градиента. Методы сведения задач с ограничениями к задачам безусловной оптимизации. Методы внешних и внутренних штрафных функций. Комбинированный метод проектирования и штрафных функций. Метод зеркальных построений. Метод скользящего допуска.

Математические модели в задачах  проектирования реальных объектов или  технологических процессов должны отражать реальные протекающие в  них физические и, как правило, нелинейные процессы. Переменные этих объектов или  процессов связанны между собой  физическими нелинейными законами, такими, как законы сохранения массы  или энергии. Они ограничены предельными  диапазонами, обеспечивающими физическую реализуемость данного объекта  или процесса. В результате, большинство  задач математического программирования, которые встречаются в научно-исследовательских  проектах и в задачах проектирования – это задачи нелинейного программирования

Общая формулировка нелинейных задач:

Найти переменные х₁ , х₂ , …, х_n , удовлетворяющие системе уравнений

Ψ ( х1 , х2 , …, хn ) = bi , i = 1, 2, …, m

(2.24)

и обращающие в максимум ( минимум ) целевую функцию

Z = f ( х1 , х2 , …, хn )

(2.25)

Примером типичной и простой  нелинейной задачи является следующая:  
Данное предприятие для производства какого-то продукта расходует два средства в количестве х₁ и х₂ соответственно. Это факторы производства, например, машины и труд, два различных сырья и т.п., а величины х₁ и х₂ – затраты факторов производства. Факторы производства впредь будем считать взаимозаменяемыми. Если это «труд» и «машины», то можно применять такие методы производства, при которых величина затрат машин в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое).

Объем производства (выраженный в  натуральных или стоимостных  единицах) является функцией затрат производства Z = f ( х₁ , х₂ ). Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов (х₁ и х₂) и от цен этих факторов (c₁ и c₂). Совокупные издержки выражаются формулой b = c₁ х₁ + c₂ х₂. Требуется при данных совокупных издержках определить такое количество факторов производства, которое максимизирует объем продукции Z.

Математическая модель этой задачи имеет вид: определить такие переменные х₁ и х₂, удовлетворяющие условиям

c1 х1 + c2 х2 = b

(2.26)

х1 ≥ 0, х2 ≥ 0,

(2.27)

при которых функция

Z = f (х1, х2 )

(2.28)

достигает максимума. Как правило, функция (2.28) может иметь произвольный нелинейный вид.

Использую классические методы оптимизации, следует четко представлять себе различие между локальным экстремумом функции, глобальным экстремумом и условным экстремумом. Понятие условного экстремума вводится для случая, когда число переменных n не меньше 2 (n ≥ 2). Будем полагать, что функция Z = f ( х₁ , х₂ , …, х_n ) = f (X) дважды дифференцируема в точке Х* = (х₁ *, х₂ *, …, х_n* ), (Х* € D(f)) и в некоторой ее окрестности.

Если для всех точек Х этой окрестности f (X*) ≥ f (X) или f (X*) ≤ f (X), то говорят, что функция f (X) имеет экстремум в X* (соответственно максимум или минимум).

Точка X* , в которой все частные производные функции Z = f (Х) равны 0, называется стационарной точкой.

Необходимое условие экстремума.

Если в точке X* функция Z = f (Х) имеет экстремум, то частные производные функции в этой точке равны 0:

f '_x1 (X*) = 0, i = 1, 2, ..., n.

Следовательно, точки экстремума функции Z = f (Х) удовлетворяют системе уравнений:

(2.29)

Для получения достаточных условий  следует определить в стационарной точке знак дифференциала второго  порядка. Дифференциала второго  порядка обозначается d²f (х₁ , х₂ , …, х_n ) f '_x1 (X) найти частную производную по переменной х_j , то получим частную производную второго порядка по переменным х_i , х_j , которая обозначается f ''_{xi, xj} (X). В этом случае

Достаточные условия экстремума. Двух переменных:

• если Δ > 0 и а₁₁ < 0 (а₂₂ < 0), то в точке Х ⁰ функция имеет максимум:  
  если Δ > 0 и а₁₁ > 0 (а₂₂ > 0),то в точке Х ⁰ – минимум (в этих случаях Х ⁰ = Х*);
• если Δ < 0, то экстремума нет;

если Δ = 0, то вопрос об экстремуме остается открытым.

 

 Задачи стохастического  программирования. Стохастические  квазиградиентные методы. Методы стохастической аппроксимации. Методы с операцией усреднения. Методы случайного поиска. Стохастические задачи с ограничениями вероятностной природы. Стохастические разностные методы.

 

 Методы и задачи  дискретного программирования. Задачи  целочисленного линейного программирования. Методы отсечения Гомори. Метод  ветвей и границ. Задача о назначениях.  Венгерский алгоритм.

Постановка задач дискретного  программирования

Под задачей дискретного программирования (дискретной оптимизации) понимается задача математического программирования

F(x0) = min f(x), x є G,

множество допустимых решений которой конечно, т.е. О ≤ |G| = N < ∞, где |G| — число элементов множества G. В силу конечности G все допустимые решения можно пронумеровать: x1, x2, . . . . ., xN, вычислить f(xi), i= 1,2,..., N, и найти наименьшее значение.

Во многих задачах условия дискретности отделены от других условий, т.е. если х = (х1, х2, ... ,хn), то xj є Gj = (х j 1, хj2, ...,хjki), kj > 2. Поэтому N = = =  > 2n, отсюда видно, что с ростом числа переменных объем вычислительной работы резко возрастает.

 

Экономическая и геометрическая интерпретация  задачи целочисленного программирования. Экстремальная задача, переменные которой  принимают лишь целочисленные значения, называется задачей целочисленного программирования.

 

В математической модели задачи целочисленного программирования, как целевая функция, так и функции в системе  ограничений могут быть линейными, нелинейными и смешанными. Ограничимся  случаем, когда целевая функция  и система ограничений задачи являются линейными.

 

Алгоритм Гомори

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

Алгори́тм Го́мори — алгоритм, который используется для решения полностью целочисленных задач линейного программирования. Алгоритм включает в себя:

1. Решение задачи одним из методов группы симплекс-методов или группы методов внутренней точки без учёта требования целочисленности. Если полученное оптимальное решение целочисленно, то задача решена.
2. Составляется дополнительное ограничение для переменной , которая в оптимальном плане имеет максимальное дробное значение, хотя должна быть целой. Тогда величины коэффициентов элементов , вычисляются так:

где — целая часть числа . Тогда дополнительное ограничение формируется следующим образом:

Оно будет целым неотрицательным  при целых неотрицательных  и После составления ограничения оно вводится в систему линейных ограничений и задача решается заново при исходных ограничениях и дополнительном ограничении. Если получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап.

 

Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.

Общая идея метода может быть описана  на примере поиска минимума и максимума  функции  на множестве допустимых значений . Функция и могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

Процедура ветвления состоит в разбиении области допустимых решений на подобласти меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти.

Процедура нахождения оценок заключается в поиске верхних и нижних границ для оптимального значения на подобласти допустимых решений.

В основе метода ветвей и границ лежит  следующая идея (для задачи минимизации): если нижняя граница для подобласти дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти , то может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную ; любой узел дерева поиска, нижняя граница которого больше значения , может быть исключен из дальнейшего рассмотрения.

Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом  функции и достигается на соответствующей  подобласти.