§ 4. Разделы и классы задач исследования операций.

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

Начнем с характеристики среды (∑) принятия решения.

Если элементы модели (1)не зависят от времени, т.е. процесс принятия решения сводится к мгновенному акту выбора точки из заданного множества, то задача ИО называется статической. В противном случае, т.е. когда принятие решения представляет собой многоэтапный (дискретный) или непрерывный (во времени) процесс, задача ИО называется динамической. Примеры 1-4, 7и 8 относятся к статическим, а примеры 5-6и 9 -к динамическим задачам. Задачи ИО, не содержащие случайных величин и вероятностных явлений, называются детерминированными (см. примеры 1,2,4,5.9).Задачи со случайными факторами с вероятностной оценкой -стохастическими (пример 3,4,6),а задачи принятия решения в условиях неопределенности -конфликтными (примеры 7,8).

В зависимости от количества ЛПР в (1)различают задачи оптимизации (2)и игровые задачи (n ≥ 2,гдеn -число элементов во множествеN).

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

В зависимости от характера конфликта различают, антагонистические (примеры 7,8),неантагонистические (бескоалиционные) и кооперативные игры.

Если в задаче оптимизации все элементы линейны (целевая функция и ограничения), то получаем задачу линейного программирования (примеры 1,2),в противном случае -задачу нелинейного программирования (пример З и пример 4, если функцииR_j, иK_jнелинейные). Если в задаче оптимизации присутствует фактор времени, то она называется задачей оптимального управления (пример 5).Иногда такие задачи называют задачами динамического программирования. Однако это неточное название, так как динамическое программирование -это название метода решения задач оптимального управления.

Часто у ЛПР имеется не одна ,а несколько целей. Математическая модель

<X;f₁,…,f_n;Σ> (5)

такой задачи называется задачей многокритериальной (или векторной) оптимизации. В модели (5)ЛПР выбирает решение хХ так, чтобы получить как можно большие значенияf₁(x),...,f_n(x) критериев.

Есть классы задач ИО, получивших свое название, исходя из их назначения: системы массового обслуживания (пример 6),задачи управления запасами (пример3), задачи сетевого и календарного планирования (пример 9).

Перечисленные классы задач изучаются в разделах ИО с соответствующими названиями.

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

Задача оптимального раскроя материала. Фирма изготовляет изделие, состоящее из р деталей (например комплект постельного белья). Причем в одно изделие эти детали входят в количествахk₁,…,k_r.С этой целью производится раскройmпартий материала. В i-йпартии имеетсяb_iединиц материала. Каждую единицу материала можно раскроить на деталиnспособами. При раскрое единицыi-й партии j-мспособом получается а_ijrдеталейr-го вида.

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

Транспортная задача.Имеетсяnпоставщиков иmпотребителей одного и того же продукта. Известны выпуск продукции у каждого поставщика и потребности в ней каждого потребителя, затраты на перевозки продукции от поставщиков к потребителям.

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

Задача о назначениях на работу.Имеетсяnработ иnисполнителей. Стоимость выполнения работыiисполнителемjравнаc_ij. Нужно распределить исполнителей на работы так, чтобы минимизировать затраты (ФЗП).

Задача о смесях (о рационе).Изmвидов исходных материалов, каждый из которых состоит изnкомпонент, составить смесь, в которой содержание компонент должно быть не меньшеb₁,...,b_n. Известны цены единицы материалов:c₁...c_mи удельный весj-гoкомпонента в единицеi- гoматериала.

Составить смесь, в которой затраты должны быть минимальны.

Задача о рюкзаке.Имеетсяnпредметов. Вес предмета iравенp₁, ценностьc₁(i=l,…,n). Требуется при заданной ценности груза выбрать совокупность предметов минимального веса.

Задача о коммивояжере.Имеетсяnгородов и задано расстояниеc_ijмежду ними (i,j=l....,n). Выезжая из одного (исходного) города, коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в исходный город.

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

Задача о станках.На универсальном станке обрабатываются одинаковые партии изnдеталей. Переход от обработки детали iк обработке детали jтребует переналадки станка, которая занимаетc_ijвремени.

Требуется определить последовательность обработки деталей, при которой общее время переналадок станка при обработке партии деталей минимально.

Задача о распределении капиталовложений. Имеетсяnпроектов, причем для каждого проекта iизвестны ожидаемый эффектγ_jот его реализации и необходимая величина капиталовложений g_j.Общий объем капиталовложений не может превышать заданной величины b.

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

Задача о размещении производства.Планируется выпускmвидов продукции, которые могли бы производиться наnпредприятиях (n>m). Издержки производства и сбыта единицы продукции, плановый объем годового производства продукции и плановая стоимость единицы продукции каждого вида известны.

Требуется из nпредприятий выбрать такиеm, каждое из которых будет производить один вид продукции.