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

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

по временному признаку (статические модели и модели динамические;

по порядку математических соотношений, соответствующих целевой функции и ограничениям (линейные и нелинейные модели);

по признаку дифференцируемости целевой функции и функциональных ограничений;

по типу управляемых переменных (модели с целочисленными, дискретными, булевыми переменными и переменными непрерывными).

Общую задачу математического программирования можно сформулировать, например, так: определить вектор Х = (х₁; х₂; , х_n)^t, который является решением задачи

Z(X) → min (max);

g_i(X) ≤ (≥) 0, i = 1,2,…,m; (4.1)

h_j(X)=0, j=1,2,….n, где t – индекс транспонирования.

В модели (4.1) первое соотношение представляет собой критериальную функцию, минимизируемую (максимизируемую) в данном случае, а следующие соотношения – ограничения, которые формируют область допустимых решений. Эта область представляет собой множество в n – мерном евклидовом пространстве .

Если функции Z(X), g_i(X),h_j(X) линейны, то модель (4.1) называется линейной, а задача, которую она отражает, - задачей линейного программирования. Линейные целевые функции являются наиболее “простыми” функциями, поэтому анализ моделей линейного программирования в известной мере проще, чем другие модели математического программирования, а методы линейного программирования достаточно глубоко разработаны.

Если хотя бы одна из этих функций не линейна, то модель (4.1) называется нелинейной, а задача, которая представлена в ней, - задачей нелинейного программирования. Методы анализа таких задач называют методами нелинейного программирования.

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

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

F(x) = , (4.2)

а ограничения – линейны.

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

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

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

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

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

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

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

F(x) = F(x₁, x₂,..., x_n) = (4.3)

или

F(x) = F(x₁, x₂,..., x_n) = (4.4)

В случае (4.3) функция F(x) называется аддитивной, а в случае (4.4) – мультипликативной.

Метод динамического программирования применим для анализа многошаговых процессов и является средством анализа многоэкстремальных задач.

Метод прямого перебора.Если известна функциональная связь целевой функции Y и искомой переменной Х, то можно последовательно вычислить значения целевой функции для некоторых значений искомой переменной. Вычисления повторяются до тех пор, пока не будет найден min (max) значения целевой функции:

Y = ƒ(x₁,…, x_i,…,x_n, u₁,…, u_j,…u_m),

x_i = x_0i + Δx_ik (k = 0,1,2,….,l).

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

Классический метод дифференциального исчисления. Если известна функциональная связь целевой функции с искомыми переменными Y = ƒ(x₁,…, x_i,…,x_n, u₁,…, u_j,…u_m), которая обладает непрерывными первыми частными производными, то, определив частные производные по своим искомым переменным, приравняв частные производные от Y по х_i к нулю и решив систему уравнений

= 0,

……………….

= 0,

найдем значения х_ic, дающие стационарные значения целевой функции, среди которых находятся оптимальные.

Метод неопределенных множителей Лагранжа. С помощью этого метода можно определить экстремальные точки функции многих переменных при наличии дополнительных связей между оптимизируемыми параметрами.

Пусть имеется целевая функция Y = ƒ(x₁,..., x_i,..., x_n, u₁,..., u_j,..., u_m), экстремум которой требуется определить, причем существуют дополнительные условия

φ_к(х_1, ,..., x_i,..., x_n, u₁,..., u_j,..., u_m) = 0 (к = 1,2,..., р).

Введя р дополнительных множителей λ₁, λ₂,...,λ_k,..., λ_р, построим новую функцию

L(x₁,..., x_i,..., x_n, u₁,..., u_j,..., u_m, λ₁, λ₂,.., λ_k,.., λ_р) =

= ƒ(x₁,..., x_i,..., x_n, u₁,..., u_j,..., u_m) – *φ_k(x₁,..., x_n, u₁,..., u_m),

где - множитель Лагранжа.

Необходимые условия экстремума состоят в равенстве нулю всех первых частных производных от L по x₁,..., x_i,..., x_n, , λ₁,.., λ_k,.., λ_р:

= 0 (i = 1,2,…, n);

= 0 (k = 1,2, n).

В результате получается n+p уравнений с n+p неизвестными ((x₁,..., x_i,..., x_n), (λ₁,.., λ_k,.., λ_р). Решение этих уравнений относительно переменных х и λ дает возможность определить положение стационарной точки. Использование вспомогательной функции L(x, λ) позволяет заменить задачу с дополнительными условиями задачей без них.

5 ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, её целевой функции и системы ограничений.

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

Методами ЗЛП могут решаться задачи: о наилучшем использовании ресурсов; о выборе оптимальных технологий; о размещении ремонтов специализированного оборудования; транспортная задача (задача развития электрических сетей); о размещении заказа и т.д. В перечисленных задачах может определяться или максимум или минимум целевой функции.

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

Задача формулируется так. Имеется m пунктов производства, в каждом из которых может быть произведено b_i (i = 1,m) электроэнергии и n пунктов потребления электроэнергии, где потребность составляет a_j (j = 1,n) единиц. Известны величины c_ij – затраты на транспортировку на единицу электроэнергии из i – го пункта в j – й пункт потребления. Обозначим через x_ij количество электроэнергии, передаваемого из i – го пункта производства в j – й пункт потребления. Матрица [c_ij] – называется матрицей тарифов, Х = [x_ij] – матрицей транспортировки. С целью удобства построения математической модели матрицы тарифов и транспортировки совмещают в одну, именуемую макетом транспортной задачи (развития сетей).

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

x_ij min (5.1)

при ограничениях: на возможности производителя – весь продукт из пунктов производства может быть транспортирован

≤ b_i (i=1,…,m) (5.2)

на спрос потребителей, который должен быть полностью удовлетворен:

= a_i (j=1,…,n) (5.3)

при условии не отрицательности переменных, исключающем обратные перетоки

≥ 0 (i = 1,..,m; j = 1,..,n) (5.4)

Основные виды записи ЗЛП.

Общей задачей линейного программирования (ОЗЛП) называют задачу, которую математически представляют в виде следующих линейных соотношений:

– целевая функция – W = ∑ C_J X_J → max(min) (5.5)

– ∑ a_ij X_j b_i ( i = 1,…,m₁)

– ограничения – ∑ a_ij X_j b_i ( i = m₁+1,…,m₂) (5.6)

∑ а_ij X_j b_i ( I = m₂+1,…,m)

где –С_j , a_ij, b_i – заданные действительные числа; Х_j ≥ 0 (j = 1,..,n )– искомые неотрицательные переменные параметры, удовлетворяющие условию задачи и ограничениям; Х = (Х₁; ; Х_п)^t – план задачи.

Канонической формой записи ЗЛП называют задачу

min W = ; (5.7)

= b_i, (5.8)

(j = 1,…,n). (5.9)

Каноническая форма записи ЗЛП можно представить в матричной форме и в векторной форме. Введем обозначения

С = [c₁; c₂;…..c_n], A = , X = ,

A₀ = ,

где С – матрица-строка; А – матрица системы уравнений; Х – матрица –столбец переменных; А₀ – матрица-столбец свободных членов.

Каноническая форма задачи с использованием матричной записи примет вид min W = [c₁; c₂;…..c_n] [ ^T;

= , X ≥0

или min W = СХ, АХ = А₀, Х ≥ 0.

Векторная форма записи ЗЛП.

Для столбцов матрицы А введем обозначения:

А₁ = , А₂ = , А₃ = ,…, А_j = ,….,

А_n = .

Тогда задача (5.10) – (5.11) в векторной форме записи примет вид:

min W = cx;

A₁x₁ + A₂x₂ + ……+ A_jx_j + … + A_nx_n = A₀, x ≥ 0,

где cx – скалярное произведение векторов с=(с₁; с₂;…; с_п) и х = (х₁; х₂;…; х_п).

Геометрическая интерпретация задачи линейного планирования

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

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

Пусть дана задача: определить параметры Х₁ ≥ 0, X₂ ≥ 0, обеспечивающие максимум целевой функции и удовлетворяющие условиям ограничений

max Z = c₀ + c₁x₁ + c₂x₂; (5.10)

a₁₁x₁ + a₁₂x₂ ≤ b₁,

a₂₁x₁ + a₂₂x₂ b₂,

………………………. (5.11)

a_m1x₁ + a_m2x₂ ≥ b_m.

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (5.11) задаёт на плоскости х₁Ох₂ некоторую полуплоскость. Полуплоскость – выпуклое множество. Пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (5.10) – (5.11) есть выпуклое множество.

Представим на рис. 5.1 возможные ситуации, когда область допустимых решений (ОДР) задачи линейного планирования (ЗЛП): а) выпуклый многоугольник; б) неограниченная выпуклая многоугольная область; в) единственная точка; г) луч; д) отрезок; е) пустое множество

Рис.5.1

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП – непустое множество, например многоугольник АВСДЕ (рис.5.2). Выберем произвольное значение целевой функции Z = Z_o. Получим с₀ + с₁х₁ + с₂х₂ = Z₀. Это уравнение прямой линии. В точках прямой MN целевая функция сохраняет одно и то же постоянное значение Z₀. Считая в равенстве (5.12) Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Рис.5.2

Возникает вопрос: как установить направление возрастания (убывания) целевой функции? Найдём частные производные целевой функции по х₁ и х₂:

Z/ x₁ = c₁, Z/ x₂= c₂. (5.12)

Частные производные (5.12) функции показывают скорость ее возрастания вдоль осей. Следовательно, с₁ и с₂ – скорость возрастания Z соответственно вдоль осей Ох₁ и Ох₂. Вектор G = (с₁;с₂) называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

G= ( Z/ x₁, Z/ x₂).

Вектор – G показывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор G= (с₁;с₂) перпендикулярен к прямым Z = const семейства с₀+с₁х₁+с₂х₂=Z.

Из геометрической интерпретации элементов ЗЛП следует порядок её графического решения.

1. С учетом системы ограничений строим область допустимых решений.

2. Строим вектор G= (с₁;с₂) наискорейшего возрастания целевой функции – вектор градиентного направления.

3. Проводим произвольную линию уровня Z = Z₀ (проще всего провести линию Z = c₀, перпендикулярную к вектору G ).

4. При решении задачи на максимум перемещаем линию уровня Z = Z₀ в направлении вектора G так, чтобы она касалась ОДР в её крайнем положении (крайней точке) (на рис. – до точки Д). В случае решения задачи на минимум линию уровня Z = Z₀ перемещаем в направлении антиградиента (на рис. – до точки В).

5. Определяем оптимальное решение, т.е. значения Х^* = (х₁^*; х₂^*) и экстремальное значение целевой функции Z^* = z( x^*).

Из геометрической интерпретации условий ограничений и целевой функции возможно выявить особенности решения ЗЛП, а именно (см. рис.5.3):

Рис.5.3

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

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

3) – целевая функция не ограничена: линия уровня, сколько бы ее ни перемещали, не может занять соответствующего положения (рис.5.3, в,г);

4) – область допустимых решений состоит из единственной точки, где целевая функция достигает одновременно и максимального, и минимального значений (рис. 5.3, д);

5) – задача не имеет решения: область допустимых решений – пустое множество, т.е. система ограничений несовместна (рис.5.3, е).

При количестве переменных более трех ЗЛП теряет геометрическую наглядность, но идея получения решения (графического) сохраняет смысл и для случая многомерного пространства.

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

Пусть исходная ЗЛП имеет вид

(5.8)

(5.9)

(5.10)

(5.11)

Канонической формой записи ЗЛП называют задачу

(5.12)

(5.13)

(j = 1,…,n). (5.14)

При необходимости задачу максимизации можно заменить задачей минимизации, и наоборот. Для функции одной переменной это утверждение очевидно. В самом деле, если – точка максимума функции , то для функции она является точкой минимума, так как графики функции и – симметричны относительно оси абсцисс (рис.х.3).

Итак, .

То же самое имеет место и в случае функции многих переменных (n):

Преобразуем систему ограничений к каноническому виду. Введем m дополнительных неотрицательных переменных . Для того чтобы неравенства типа ≤ (5.9) преобразовались в равенства, к их левым частям прибавим дополнительные переменные , после чего система неравенств (5.9) примет вид: