Software & Systems

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

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

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

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

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

                                                  (1)

где f(x, y) – выпуклая функция пополнения запасов ресурса y для выпуска изделия x; g(x, y) – выпуклая функция расхода ресурса y для выпуска изделия x; Y – множество ресурсов; X – множество изделий; Z – множество производственных планов [1].

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

При линейности выражение (1) имеет следующий вид:

           (2)

С дополнительными ограничениями получаем систему уравнений

                                       (3)

где Di – множество значений спроса на продукцию i в соответствии с заказом diq на продукт i в количестве q.

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

При планировании производства в среднесрочной перспективе смешанная линейная задача определяется целевой функцией

                                             (4)

и дополнительными условиями

                       (5)

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

                        (6)

и дополнительными условиями

         (7)

где N – количество изделий; T – количество интервалов времени; K – количество производственных ресурсов; aik – фиксированное время выпуска продукта i из ресурса k; bik – скорость производства продукта i из ресурса k; Bk – набор продуктов из ресурса k; Ckt – мощность производства ресурса k в период t; dit – независимый спрос на продукцию i в период t; git – количество единиц продукта i, необходимое для производства единицы продукта j; hi – список цен продукта i; Li – количество интервалов времени для продукта i; M – некоторое большое число; Pit – переменные издержки производства продукта i в период t; Si – фиксированная цена продукта i; i=1, …, N и t=1, …, T – переменные решения, определенные для представления объемов производства xit, а также позиции конца периода инвентаризации и установки yit [2, 3].

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

Перед использованием (добавлением, редактированием или удалением) определенного ресурса на сервере Oracle триггер выполняет для данного ресурса следующие действия.

1.   Запуск автономных транзакций. Поскольку приходится читать данные из таблицы, в ответ на изменение которой сработал триггер, во избежание ошибок изменяющейся таблицы во всех случаях следует использовать автономные транзакции. Они дают возможность создать новую транзакцию в пределах текущей, так что можно фиксировать или откатывать ее изменения независимо от родительской транзакции. Автономные транзакции позволяют приостановить текущую транзакцию, начать новую, выполнить ряд действий, зафиксировать их или откатить, не влияя на состояние текущей транзакции. Они предлагают новый метод управления транзакциями в языке PL/SQL и могут использоваться в анонимных блоках верхнего уровня, в локальных, отдельных или входящих в пакеты процедурах и функциях, а также в методах объектных типов и в триггерах БД в целях обеспечения целостности данных.

2.   Выборка и суммирование всех полученных количеств СПК.

3.   Выборка и суммирование всех израсходованных количеств СрК.

4.   Выборка минимально допустимого количества среди ДК.

5.   Отчет по состоянию ресурса: если СПК– –СрК£ДК, триггер запрещает использовать данный ресурс и обязывает заказать дополнительное количество данного ресурса, иначе на уровне интерфейса в графическом виде выводится состояние данного ресурса (общее количество, израсходованное и имеющееся в наличии).

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

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

Алгоритм статистического поиска действует следующим образом: пусть y=(y11, …, y1t, yN1, …, yNt) – вектор переменных модели. Фиксированные yf-сокращения приводят модель целочисленного линейного программирования (6) к модели статистического поиска типа

                   (8)

и к модели с дополнительными условиями

           (9)

Общая идея алгоритмов статистического поиска состоит в генерировании случайной последовательности постановок моделей y(0)®y(1)® … ®y(R), чтобы модель

                               (10)

стала лучшей оптимизацией выражения (8).

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

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

                  (11)

где F(yH) – значение целевой функции очередного решения; F(yC) – значение целевой функции предыдущего решения.

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

,                                             (12)

где  a – параметр падения.

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

Рассмотрим принцип действия алгоритма поиска с запретами для решения смешанных линей-

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

Заметим, что даже если yH приводит к лучшему решению, это не означает, что текущее решение yH обязательно лучше предыдущего. Роль запрещенного листа TLm, содержащего m уже исследованных моделью решений, – исключить возврат к решениям, уже содержащимся в списке запрещенного листа. Использование подобного подхода значительно снижает вероятность попадания в локальные оптимумы. Критерии остановки работы алгоритма различны. В качестве наиболее простого можно предложить достижение заданного числа итераций. Заметим, что, как и для симуляции, поиск с запретами можно остановить после того, как алгоритмом выполнено заданное число шагов.

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

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

Литература

1. Leyffer S., Linderoth J. A practical guide to mixed integer nonlinear programming. Society for industrial and applied mathematics (SIAM), Stockholm, Sweden, 2005.

2. Чаки Ф. Современная теория управления: нелинейные, оптимальные и адаптивные системы. М., 2005. С. 22–130.

3. Thomas Kit. Oracle database architecture: oracle database 9i, 10g, and 11g programming techniques and solutions. NY, USA, 2010, pp. 642–743.