Исследование операций

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

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

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

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

Пусть в пунктах А₁, А₂,…, А_n находятся склады, на которых хранятся полуфабрикаты в количествах Х₁, Х₂,..., Х_n, соответственно. В пунктах В₁, В₂,…, В_m находятся потребители, к которым необходимо доставить полуфабрикаты в количествах, не меньших, чем Y₁, Y₂,…, Y_m, соответственно. Обозначим черед d_ij стоимость перевозки единицы груза между пунктами А_i и В_j.

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

Обозначим X_ij количество товара, перевозимого из пункта А_i в пункт В_j. Для того, чтобы удовлетворялись запросы потребителей, необходимо выполнение неравенства

X_ij ≥ Y_j

Но со склада i мы не можем вывести полуфабрикатов больше, чем там имеется. Это означает, что искомые величины должны удовлетворять еще одной системе неравенств:

X_{i j} ≤ X_i

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

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

I = d_ij X_ij → min

Теперь задачу о перевозках мы можем сформулировать следующим образом: определить величины X_ij ≥ 0, удовлетворяющие ограничениям и доставляющие функции I минимальное значение.

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

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

Исследование задачи в рассмотренном примере сводилось к четко поставленной задаче оптимизации и не содержало неопределенностей. Однако задачи, не содержащие неопределенности, скорее исключение, чем правило.

В исследованиях операций принято различать три типа неопределенностей: неопределенность целей, неопределенность знаний обстановки («неопределенность природы») и неопределенность действий реального противника или партнера.

Рассмотрим ситуацию с неопределенностью целей.

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

Таким образом, мы сталкиваемся с задачей, когда перед исследователем операций стоит задача выбора способа действия (вектора х), обеспечивающего экстремальное значение функций f₁(x), f₂(x),…, f_n(x) одновременно.

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

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

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

В книге Шенона принцип Парето сформулирован несколько с иных позиций и совсем просто: «С точки зрения характеристик системы существенны лишь некоторые из множества факторов. Действительно, в большинстве систем 20 % факторов определяют 80 % свойств, а остальные 80 % факторов определяют лишь 20% ее свойств. Наша задача – выделить существенные факторы».

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

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

E^н_j2 ≤ E_j2 ≤ E^в_j2

где E_j2 – содержание расчетного j-го компонента в готовом сплаве, %; E^н_j2, E^в_j2 – соответственно нижний и верхний пределы содержания j-го компонента в готовом сплаве, %.

Расчетный состав жидкого расплава записывается соответствующими неравенствами:

E^н_j1 ≤ E_j1 ≤ E^в_j1

где

E^н_j1 = E^н_j2 + ΔE_j; E^в_j1 = E^в_j2 – ΔE_j

ΔE_j – отклонение содержания элемента.

Расчетные уравнения представляют собой систему неравенств и равенств

E^н_j1 ≤ E_ij1 x_i1 ≤ E^в_j1

x_i1 = 1

q ≤ x_i1 ≤ p

где E_ij1 – количество расчетного элемента E_j, усваиваемое жидким металлом из i-й составляющей шихты; 0 ≤ x_i1 ≤ 1 – доля i-й составляющей шихты; р и q – технологические ограничения на x_i; 1, 2, …, m – компоненты шихты.

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

E^н_j0 ≤ E_ij0 x_i0 ≤ E^в_j0

x_i0 k_i =1

q₀ ≤ x_i0 ≤ p₀

где индекс «0» означает «для шихты», а k_i – коэффициент выхода жидкого металла из i-й составляющей шихты.

Если записать E^ср_j0 = (E^н_j0+E^в_j0)/2, то получим

Е_ij = E^ср_j ; x_i =1/k₀

где k₀ – коэффициент выхода жидкого металла из всей шихты, 0 ≤ k₀ ≤ 1.

Таким образом, мы получили систему линейных алгебраических уравнений вида

Σa_ij x_i = b_i,

где a_ij≥0, b_i≥0 ,

i=1,...,m,

j=1,...,n,

m – число компонентов в составляющей шихты,

n – число компонентов шихты.

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

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

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявок и собственно обслуживания. Схематически такой элементарный прибор обслуживания можно представить состоящим из накопителя заявок Н, содержащего l заявок, и канала обслуживания заявок К. В накопитель поступает поток заявок w, а на канал – поток обслуживаний u.

Считают, что поток заявок w, т.е. интервалы времени между моментами появления заявок на входе К образует подмножество неуправляемых переменных, а поток обслуживания u, т.е. интервалы времени между началом и окончанием обслуживания, образуют подмножество управляемых переменных.

Заявки, обслуженные каналом К, и заявки, покинувшие прибор П не обслуженными (например, из-за переполнения накопителя Н), образуют выходной поток у, т.е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.

Процесс функционирования прибора обслуживания П можно представить как процесс изменения состояний его элементов во времени z(t). Переход в новое состояние для П означает изменение числа заявок, которые в нем находятся (в накопителе Н и канале К), т.е. состояние прибора зависит как от состояния накопителя, так и от состояния канала. В практике моделирования используют не отдельные приборы обслуживания П_i, а совокупности, образуемые композицией многих элементарных приборов обслуживания П_i. Такие совокупности и представляют собой математические непрерывно-стохастические схемы.

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