На предприятиях 15 Вопросы к главе 1 25 (стр. 9 из 36)

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

Для решения задач ЛЦП разработаны специальные методы. Метод отсекающих плоскостей разработан Р. Гомори и применяется для решения задач ЛЦП, в которых все переменные целочисленны. Как показала практика, ни один из вариантов метода отсекающих плоскостей не обеспечивает высокой эффективности вычислительных процедур для решения задач большой размерности [14]. Метод ветвей и границ относится к комбинаторным методам и в отличие от методов отсекающих плоскостей непосредственно применим как к полностью, так и к частично целочисленным задачам. Он достаточно эффективен лишь в том случае, когда используемый конкретный алгоритм учитывает специфику решаемой задачи [14].

В таблице 2.4 приведен список оптимизационных задач управления предприятием, которые могут быть решены методами ЛЦП.

Таблица 2.4 – Список оптимизационных задач управления предприятием,

которые могут быть решены методами ЛЦП

№ п/п	Оптимизационные задачи управления предприятием, решаемые методами ЛЦП	ПРИМЕЧАНИЕ
1	Задача распределения производственной программы во времени	Детерминированная, статическая.
2	Задача определения последовательности запуска деталей с учетом переналадки	-||-
3	Некоторые задачи транспортного типа (об оптимальных назначениях, о кратчайшем пути)	-||-
4	Задача о коммивояжере	-||-
5	Задача оптимального раскроя промышленных материалов	-||-
6	Задача о ранце	-||-

Методы динамического программирования (ДП). Динамическое программирование – это поэтапное планирование многошагового процесса, когда на каждом этапе оптимизируется только один шаг, но решение, под воздействием которого система переходит из текущего состояния в новое состояние, должно выбираться с учетом его последствий в будущем и совершенно не обязательно должно давать наибольший эффект на данном этапе. Начало развития методов ДП связано с именем Р. Беллмана. Методы ДП рассмотрены в работах [13, 14, 16, 17].

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

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

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

Это основное правило сформулировано Р. Беллманом в виде такого принципа оптимальности: каково бы ни было предшествующее состояние системы, последующие решения должны выбираться оптимальными относительно состояния, к которому придет система в конце предыдущего шага.

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

Общие свойства динамических моделей сводятся к следующему:

- цель программирования (принцип решений) - максимизация некоторой функции параметров состояния;

- состояние системы в любой момент времени характеризуется небольшим количеством параметров;

- результатом принятия решения является преобразование этих параметров в том же количестве, но с другими числовыми значениями;

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

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

Рисунок 2.2 – Экономико-математические методы решения

оптимизационных задач

Предположим, что в результате условной оптимизации стали известны начальное состояние системы S_o и оптимальное управление Х(Х₁, Х₂,..., Х_n), переводящее систему в состояние S₁, затем - в S₅ и т. д. до получения максимального выигрыша f_n(S). Из этого следует, что в результате безусловной оптимизации определяются оптимальные управления на всех шагах процесса, приводящие к максимально возможному выигрышу Z_max.

Таким образом, динамическое программирование предполагает осуществление пошагового процесса оптимизации дважды:

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

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

Для решения задач динамического программирования существует рекуррентная вычислительная схема, называемая уравнением Беллмана.

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

Таблица 2.5 – Список оптимизационных задач управления предприятием,

которые могут быть решены методами ДП

№ п/п	Оптимизационные задачи управления предприятием, решаемые методами ДП	ПРИМЕЧАНИЕ
1	Задача оптимальной замены оборудования	Динамическая, детерминированная
2	Задача управления запасами предприятия	-||-
3	Задача распределения ограниченных ресурсов	-||-
4	Задача о загрузке транспортных средств	-||-

Методы нелинейного программирования (НП). Нелинейное программирование – раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых и (или) целевая функция (2.1) нелинейная, и (или) система ограничений (2.2) нелинейная. Если в задаче (2.1)-(2.3) x_i ³0 i=1,…n , а функция q – выпуклая и область допустимых решений, определяемая ограничениями (2.2), тоже выпуклая, то для этого случая разработаны эффективные методы решения (выпуклое и квадратическое программирование). Методы НП рассмотрены в работах [1, 13, 14, 17].