УСТОЙЧИВОСТЬ В ЗАДАЧАХ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

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

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

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

  • 1. Во многих практических задачах параметры или входные данные, характеризующие конкретную задачу, определены с некоторой погрешностью, и поэтому важно знать величину погрешности, которая не могла бы повлиять на решение задачи или на значение целевой функции.
  • 2. Решение оптимизационных задач с фиксированным набором входных данных очень часто дает больше информации, чем только оптимальное решение. Это обстоятельство ставит проблему использования полученной дополнительной информации для решения «возмущенных» оптимизационных задач.
  • 3. В ряде практических ситуаций входные данные можно рассматривать как некоторые функции от параметров, характерные для модели, в рамках которой формулируется оптимизационная задача. Тогда возникает проблема распространения решения, т.е. можно ли разбить всю область изменения параметров на множество подобластей, все точки которых приводят к одинаковым решениям исходной задачи.

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

В работе [10] рассматривается устойчивость в линейных дискретных экстремальных задачах как устойчивость в некоторых тра- екторных задачах, которые могут быть сформулированы следующим образом.

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

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

В задачах линейного программирования рассматриваются «возмущения» элементов матрицы ограничений и вектора правых частей, сохраняющие базис, на котором построен оптимальный план исходной задачи [9].

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

Анализ устойчивости оптимального плана может быть произведен по следующим исходным данным:

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

Рассматриваемые в работе задачи оптимального распределения

ресурсов условно можно разделить на три класса.

К первому классу задач относятся задачи планирования выполнения комплекса работ. Постановка этих задач заключается в следующем. Пусть задан комплекс работ, которые необходимо выполнить, используя ограниченный объем многократно используемых ресурсов, определенных вектором b = (bv ..., bm). Последовательность выполнения работ задается ориентированным ациклическим графом. Каждая работа может начать выполняться после того, как выполнены все ее работы-предшественники. Выполняться работа i может только в том случае, если ей выделены ресурсы в количестве, заданном вектором а = (ап, ..., ajm). После окончания выполнения работы i ресурсы в объеме, заданном вектором ар могут быть переданы для выполнения других работ. При этом работы могут допускать прерывание либо прерывание может быть запрещено.

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

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

Необходимо отметить, что данная дискретная оптимизационная задача принадлежит к классу АР-полных задач как для одного, так и для второго критерия оптимальности [9].

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

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

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

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

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

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

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

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

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

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

Внутренними отклонениями являются следующие: сбои и поломки оборудования и инструмента, брак, необеспеченность трудовыми ресурсами и т.д.

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

  • 1) изменение длительности работ;
  • 2) изменение орграфа, задающего последовательность и множество выполняемых работ;
  • 3) изменение объема ресурсов, участвующих в выполнении работ.

Ко второму классу задач, рассматриваемых в книге, относится

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

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

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

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

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

Критериями, по которым организуется обработка поступающих заявок, являются: минимизация необработанного суммарного объема заявок на конец директивного периода; минимизация времени пребывания заявок в системе с момента поступления до начала обработки.

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >