14. Задачи нелинейной и дискретной оптимизации. Методы решения.

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

, где Xj- целые j=1,2…p (p<=n). Если р=n то задачу называют полностью целочисленной, если p<n - частично целочисленной.

Задача (модель) нелинейного программирования (НЛП) формулируется так же, как и общая задача оптимального программирования со следующими требованиями к целевой функции (ЦФ) и допустимой области: целевая функция f(x₁, x₂, …, x_n) и (или) одна из функций g_i(x₁, x₂, …, x_n) являются нелинейными:

min (max)f(x₁, x₂, ..., х_n),

g_i(x₁, x₂, ..., x_n){≤, =, ≥}b_i, i = 1, 2, ..., m,

x_j ≥ 0, j = 1, 2, ..., n.

У произвольной задачи НЛП некоторые или все свойства, характерные для задач ЛП, отсутствуют [1]. Вследствие этого задачи НЛП несравнимо сложнее задач ЛП и для них не существует общего универсального метода их решения (аналогично симплексному методу).

Есть целый ряд методов решения задач НЛП, некоторые из них рассмотрены в [1]. В пакете Excel реализован [8] метод множителей Лагранжа, идея которого заключается в преобразовании задачи условной оптимизации в задачу безусловной оптимизации, решение которой производится методами поиска — градиентными методами (метода первого порядка) или методами Ньютона (методы второго порядка). Наиболее распространенными являются градиентные методы. Существующие методы дают возможность находить только локальные оптимумы (помимо случаев, когда задачи обладают соответствующими свойствами выпуклости и вогнутости [1]). Если же есть подозрение, что в допустимой области ЦФ может иметь несколько оптимумов, то эту область следует разбить на ряд областей и в каждой из них определить свои локальные оптимумы, а затем из всех локальных оптимумов выбрать глобальный. В таком практическом подходе задача поиска глобального оптимума сводится к решению ряда задач, в которых ищется свой (локальный) оптимум.

Следует отметить, что в подавляющем большинстве практических задач оптимизации существует только один оптимум [8].

Решение задачи НЛП (реализация модели нелинейной оптимизации) средствами Excel отличается от решения ЗЛП следующим:

назначаются начальные значения искомых переменных так, чтобы ЦФ в начальной точке не была равна нулю,

в диалоговом окне Поиска решения в режиме Параметры не надо вводить «Линейная модель».

В Excel признаком достижения оптимума является величина относительного приращения ЦФ на каждой итерации . Оптимум считается достигнутым, если выполняется условие Δf_k ≤ Δf_зад, где Δf_зад - точность, назначаемая при решении задачи (Параметры).

Примером задачи НЛП является модель оптимального формирования портфеля ценных бумаг (модель Марковица минимального риска).

В этой модели приняты следующие обозначения:

x_j, - доля капитала, потраченная на покупку ценных бумагу j-го вида (весь выделенный капитал принимается за 1);

m_j - средняя ожидаемая доходность j-й ценной бумаги, (m_j называют эффективностью j-и ценной бумаги);

v_j - дисперсия случайной доходности j-й ценной бумаги, ( называют риском j-й ценной бумаги).

В предположении о некоррелированности ценных бумаг (их независимости) модель Марковица имеет вид:

Найти x_j, , минимизирующие риск портфеля ценных бумаг

(1)

при условии, что обеспечивается заданное значение эффективности портфеля m_p, т.е.

(2)

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

(3)

x_j ≥ 0, . (4)

В модели (1)—(4) нелинейной является ЦФ.

Задачи оптимизации, в результате решения которых искомые значения переменных должны быть целыми числами, называются задачами (моделями) целочисленного (дискретного) программирования:

min(max) f (x₁, x₂,...,x_n);

g_i (x₁, х₂,..., х_n){≤, =, ≥}b_i, ;

x_j - целые неотрицательные ∀j∈< n' >.

Если множество индексов <n'>=<n>= {1, 2, ..., n}, то задачу называют полностью целочисленной, если <n'>⊂<n> , то - частично целочисленной.

Существуют различные методы решения задач дискретного программирования (дискретной оптимизации). Наиболее часто используемым методом является метод ветвей и границ. Именно этот метод реализован в программе Поиск решения пакета Excel.

Дискретная оптимизация средствами Excel проводится аналогично решению соответствующих непрерывных задач. Основное отличие заключается во вводе при оформлении диалогового окна Поиск решения требования целочисленности соответствующих переменных (при этом в режиме Параметры устанавливается тип задачи - линейная или нелинейная).

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

Достаточно часто при моделировании экономических процессов используется особый случай дискретности задачи - булевость переменных, т.е. переменные могут принимать значения 0 или 1 . Характерным примером этого случая является задача о назначениях.

Постановка задачи. Имеется n видов работ и m исполнителей этих работ. Известны экономические оценки эффекта C_ij, i = 1, 2, …, n, j = 1, 2, …, m; от назначения i-го исполнителя j-й вид работ. Требуется так распределить исполнителей по видам работ, чтобы суммарный эффект от назначений был максимальным.

ЭММ. Введем необходимые обозначения, пусть

Тогда математически задачу о назначениях можно записать в виде:

(на каждую работу должен быть назначен исполнитель);

(все исполнители должны получить назначение).

(*)

Для реализации этой ЭММ средствами Excel ограничение (*) в рабочей таблице Excel следует записать в виде:

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

Отметим некоторые особые случаи приведенной задачи.

1. Если по той или иной причине некоторое назначение является недопустимым, то соответствующий элемент матрицы (C_ij)_m×n принимается равным (-М), т.е. его значение заведомо меньше любого другого значения. После этого в ходе решения мы сможем избежать данного назначения автоматически.

2. Если матрица (C_ij)_m×n не является квадратной, то по аналогии с открытой транспортной задачей в модели задачи о назначениях следует записать либо ограничение (число исполнителей m больше числа работ n) или (число исполнителей m меньше числа работ n).

Метод приближения непрерывными задачами. В соответствии с ним сначала решается задача линейного программирования без учета целочисленности, а затем в окрестности оптимального решения ищутся целочисленные точки. Методы направленного перебора. Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству Х множества возможных решений Х₀ ставится в соответствие число - "граница" А(Х). При решении задачи минимизации необходимо, чтобы А(Х₁) ≥  А(Х₂), если Х₁  входит в Х₂ или совпадает с Х₂ . Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества Х_С  на два -  Х_1С  и Х_2С  . При этом пересечение Х_1С  и Х_2С  пусто, а их объединение совпадает с   Х_С  . Затем вычисляют границы  А(Х_1С ) и А(Х_2С) и выделяют "ветвь" Х_{С +1}   - то из множеств Х_1С  и Х_2С  , для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа. Для каждой конкретной задачи целочисленного программирования (другими словами, дискретной оптимизации) метод ветвей и границ реализуется по-своему. Есть много модификаций этого метода.