Книги по разным темам Pages:     | 1 | 2 | 3 | Министерство образования Российской федерации Воронежский государственный университет Специальный курс Исследование операций Часть 1. Математическая модель операции пособие для студентов по специальностям 010100 Воронеж 2003 2 Утверждено научно-методическим советом математического факультета 2 сентября 2002 года Протокол № 2 Составители: Михайлова И.В.

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

Несмотря на колоссальную разницу между задачами, связанными с поиском правильных решений, можно все же указать общую черту, которой все они обладают, - это задачи о рациональных способах организации целенаправленной человеческой деятельности. Изучением таких задач, отысканием методов их решения и занимается наука, получившая название ИССЛЕДОВАНИЕ ОПЕРАЦИЙ (ИСО ). Термин лисследование операций имеет многочисленные синонимы: в Англии более употребительным является выражение лоперационные исследования, американцы часто используют термин наука об управлении и т.

.д Термин лисследование операций возник во время второй мировой войны. Тогда он полностью соответствовал содержанию предмета. Однако зачатки научного мышления, характерного для операционных исследований, появились гораздо раньше: некоторые примитивные модели математического программирования, предложенные экономистами Куинси (1759 г.) и Вальрасом (1874 г.), задача Тейлора о землекопе (1885 г.), результаты, полученные в области динамического программирования Марковым (1856-1922 г.г.), исследования Эрланга по управлению работой автоматических телефонных станций, математический аппарат для решения некоторых задач экономики, предложенный Канторовичем (г.) и т.д. Однако эти исследования оставались долгое время разрозненными, пока не были подхвачены общим потоком разработок, начало которого положили работы, проведенные во время второй мировой войны. Наиболее важным для будущего было то, что многие из специалистов увидели в таких научных разработках военного времени зарождение новой научной дисциплины, а также возможности использования соответствующих научных знаний для многих видов деятельности в мирное время.

Становление ИСО как научной дисциплины относится к 1952 г. и связывается с организацией Американского общества по ИСО.

Под ОПЕРАЦИЕЙ мы будем понимать совокупность действий, мероприятий, объединенных единым замыслом и направленных на достижение определенной ЦЕЛИ. Пока не задана цель, не существует операции. Может быть несколько операций, направленных на достижение некоторой цели, но в данной операции цель единственна. В качестве примера рассмотрим работу некоторого промышленного предприятия.

Цель - выполнение заказа. На достижение этой цели может быть направлено несколько операций: замена оборудования, пополнение запасов сырья и т.д.

з 1. Основные компоненты операции Участники операции (отдельные лица, коллективы, автоматы) могут быть условно разделены на три части: ОПЕРИРУЮЩАЯ СТОРОНА, НЕЙТРАЛЬНЫЕ ЭЛЕМЕНТЫ и ПРОТИВНИК.

Оперирующая сторона (ОС) - совокупность участников операции, которые стремятся в данной операции к достижению поставленной цели.

В качестве примера можно рассмотреть спортивное состязание от лица одной из команд (будем говорить наша команда): цель - выиграть;

ОС - наша команда, наш тренер и наши болельщики; нейтральные элементы - судьи; противник - команда противника, тренер команды противников, болельщики противника.

Члены ОС неодинаково участвуют в проведении операции. Среди них можно выделить ИССЛЕДОВАТЕЛЯ ОПЕРАЦИИ (ИО), который проводит исследование по отысканию наилучших (в определенном смысле) для ОС способов действий. Несмотря на принадлежность ИО к ОС, он занимает в ней особое место в силу следующих причин:

1) как правило, ИО во время исследований располагает меньшей информацией об операции, чем ОС к моменту проведения операции;

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

АКТИВНЫМИ СРЕДСТВАМИ будем называть совокупность материальных, энергетических, денежных и других ресурсов, а также организационных возможностей, используемых ОС для достижения цели.

Результаты проведения операции зависят при данном количестве активных средств от ФАКТОРОВ, которые можно разделить на КОНТРОЛИРУЕМЫЕ (КФ) и НЕКОНТРОЛИРУЕМЫЕ (НКФ).

КФ - способы использования активных средств, способы действий ОС, иными словами СТРАТЕГИИ ОС (СОС), влияющие определенным образом на ход операции в противном случае операция перестает быть, управляемой, а ОС становится пассивным наблюдателем. Значение КФактора обозначим x, а множество возможных значений КФактора - M0, т.е. x M0. Заметим, что M0, вообще говоря, может быть множеством произвольной природы.

НКФ могут быть классифицированы несколькими способами: по причинам появления и по степени информированности ОС о НКФакторам.

Согласно первой классификации, НКФакторы появляются за счет наличия независимо от ОС действующих людей или автоматов, не преследующих цель ОС (НКФ такого типа можно условно назвать СТРАТЕГИЯМИ ПРОТИВНИКА);

за счет влияния метеорологических условий, недостаточной изученности каких-либо процессов (такие факторы условно будем называть ПРИРОДНЫМИ). Так, в сельском хозяйстве НКФактором является метеорологическая обстановка.

Наиболее яркие примеры НКФакторов первого типа дают военные действия испорт.

Вторая возможная классификация приводит к появлению НЕОПРЕДЕЛЕННЫХ ФАКТОРОВ - НФ: ИО известно лишь N множество значений этого фактора; значение НФактора будем обозначать y, т.е. y N, причем N может быть множеством произвольной природы;

СЛУЧАЙНЫХ ФАКТОРОВ - СФ: СФ - это случайная величина Z, значения которой z Z0, а функция распределения вероятностей F F F (множества Z0 и известны ОС и ИО).

Для определения эффективности проведения данной операции вводится функция, называемая КРИТЕРИЕМ ЭФФЕКТИВНОСТИ ОПЕРАЦИИ (КЭО). Другими словами, КЭО операции есть показатель соответствия между результатом предпринимаемых действий и целью операции. Формально КЭО, обозначаемый W, есть отображение прямого произведения M0 N Z0 в множество действительных чисел W : M N Z0 R. Значение функции W x, y, z при фиксированной ( ) ( ) ситуации x, y, z M0 N Z0 позволяет судить, насколько хорошо или ( ) плохо была проведена данная операция в ситуации x, y, z.

( ) Построение МАТЕМАТИЧЕСКОЙ МОДЕЛИ ОПЕРАЦИИ означает построении функции W.

Решение задачи max min в определенном смысле (см. з 4) ( ) функции W является математическим эквивалентом стремления достигнуть поставленную цель.

з 2. ОЦЕНКА ЭФФЕКТИВНОСТИ СТРАТЕГИЙ ОС при отсутствии дополнительной информации о значении НКФакторах 2.1. Рассмотрим сначала самый простой случай: в операции есть только КФ со значениями x M0, СОС есть x M0 и КЭО W = W(x).

Для такой простой модели естественными будут следующие определения.

ОЦЕНКОЙ ЭФФЕКТИВНОСТИ стратегии x назовем W (x) значение КЭО в точке x M0. Стратегию x0 естественно считать ОПТИМАЛЬНОЙ, если W x0 = maxW (x) или W x0 = minW (x).

( ) ( ) xM0 xMЗадачи:

№ 2.1.1. На обувной фабрике можно производить три вида обуви:

мужскую, женскую и детскую. На каждую пару мужской, женской и детской обуви соответственно требуется клея - 20, 20 и 10 г, кожи - 4, 2 и 1 дм2. Стоимость мужской, женской и детской обуви с учетом всех работ соответственно равна 20, 30 и 10 денежных единиц. Запасы клея составляют 3 т, а кожи - 4000 м2. Рассмотреть следующие две операции. В первой операции все имеющиеся ресурсы используются полностью, а во второй последнее требование не является обязательным. В обеих операциях цель состоит в выборе такого производства обуви, при котором стоимость выпущенной продукции является максимальной. Построить модель операции.

А) Найти оптимальные стратегии в обеих операциях и сравнить наилучшие результаты.

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

№ 2.1.2. В приемной в ожидании личной встречи с директором собралось n посетителей. Предварительный опрос позволил выяснить, что рассмотрению вопроса i -го посетителя директор должен уделить время. Директор, зная, что хотя общее (суммарное) время, которое Ti, i = 1,...,n n он уделит всем посетителям, одно и то же, T = T (независимо от i i=очередности их приема), хотел бы так организовать прием, чтобы посетители находились в приемной в целом как можно меньше. Какова должна быть очередность приема № 2.1.3. Имеется начальное количество средств K0, которое нужно m распределять в течение лет между двумя отраслями производства 1 и 2.

i Средства, вложенные в -ю отрасль, приносят доход fi (x), однако уменьшаются при этом до gi (x) < x. По истечении года оставшиеся от Kсредства заново распределяются между отраслями. Новых средств извне не поступает, и в производство вкладываются все оставшиеся в наличии средства; доход не вкладывается, а накапливается отдельно.

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

Решить задачу в случаях:

а) K0 = 10; m = 5; f1(x) = x2; g1(x) = 0,75x; f2(x) = 2x2; g2(x) = 0,3x ;

б) K0 = 2; m = 5; f1(x) = 1- e- x ; g1(x) = 0,75x; f2 (x) = 1- e-2 x; g2(x) = 0,3x.

В общем случае значение КЭО при фиксированной СОС есть функция от значений НКФ. Поэтому предыдущее определение не может быть использовано при оценке качества произвольной стратегии.

Желательно эффективность стратегии характеризовать одним числом.

Есть несколько способов построения оценок эффективности стратегий. Мы рассмотрим тот, который основывается на ПРИНЦИПЕ ГАРАНТИРОВАННОГО РЕЗУЛЬТАТА, а именно, в своих исследованиях ИО ориентируется на наихудшее для ОС значения НКФ.

2.2. Рассмотрим операцию, компоненты которой КФ x M0, СОС x M0, СФ Z с множеством значений Z0 и функцией распределения F F вероятностей. Тогда КЭО W = W x, z.

( ) Пусть ОС разрешает ИО осреднять критерий, что означает фактически переход к другому критерию W (x) = M W x, Z, который F ( ( ) ) F является математическим ожиданием случайной величины W x, Z ( ) F относительно распределения, если математическое ожидание существует. Тогда ОЦЕНКОЙ ЭФФЕКТИВНОСТИ стратегии x называется число W (x) = inf M W x, Z = inf x, z dF(z) ( ( )) F W ( ), FF FF Zесли решается задача на максимуме и, в противном случае W (x) = sup M W x,Z = sup x, z dF (z).

( ( ) ) F W ( ) FF FF ZВ силу закона больших чисел такой переход к осредненному критерию оправдан в случае многократного проведения данной операции при неизменном комплексе условий.

Если же ОС не разрешает осреднять критерий, то единственное, что остается ИО, это оценить эффективность стратегии следующим образом W (x) = inf W (x, z) или W (x) = supW (x, z), zZzZчто крайне неразумно. Фактически мы получаем оценку, которая совсем не учитывает информацию о распределении СФ Z.

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

Задачи:

№ 2.2.1. Межотраслевое объединение ведет строительство автомобильного завода. Предстоит выполнить следующие основные работы:

А. строительство заводских корпусов;

В. завершение разработки модели нового автомобиля;

С. наем рабочей силы;

Е. отладка модели автомобиля.

Очередность выполнения работ задана сетевым графиком (рис. 1).

A C Пусть tA = 2 и tD = 1 - время выполнения работ A и D, а для О D остальных работ времена их выполнения точно неизвестны и B E являются независимыми случайными величинами. При этом tB и tC принимают значения 2, 3, 4 с Рис. вероятностями, а принимает tE значения 1, 2, 3 с вероятностями. Ниже приведена зависимость дополнительной прибыли объединения от времени выполнения всего комплекса работ:

Время выполнения всего 3 4 5 6 комплекса работ Дополнительная прибыль 120 110 100 50 объединения (в тыс.руб.) В распоряжении объединения имеется резерв, ввод которого ускоряет все строительство завода на одну единицу времени, но потребует дополнительных расходов в 20 тыс. руб.

Следует ли использовать резерв, если целью объединения является увеличение по мере возможности чистой дополнительной прибыли (т.е.

дополнительной прибыли за вычетом расходов в случае использования резерва) Составить модель операций. Критерий эффективности записать с помощью матрицы. Осреднить полученный критерий и ответить на вопрос о целесообразности ввода резерва.

№ 2.2.2. Склад имеет форму треугольника G с вершинами Aj, j = 1, 2,3. Грабитель может проникнуть на склад только в точках Aj с вероятностями pj, относительно которых лишь известно, что p/j p p//, j = 1,2,3. Цель операции - наилучшим образом j j установить сторожевую вышку на территории склада, чтобы обнаружить грабителя в момент проникновения на склад. Известно, что вероятность необнаружения грабителя пропорциональна квадрату расстояния до грабителя. Составить модель операции. Найти оценку эффективности произвольной стратегии, если а) p/j = 0, p// = 1, j =1,2,3 ;

j б) p/j = 0, p// =, j = 1,2, ;

j / // // /// / в) p1 = p1 = p2 = p3 =, p2 = p3 = 0.

№ 2.2.3. В автомобильном туннеле скорость движения машин не превосходит 50 км/ч и связана с плотностью потока (количеством машин P на километр дороги) следующим эмпирическим соотношением 60 P =, Z где Z - случайная величина, которая в любой момент определяется соотношением легковых и грузовых машин, проходящих через туннель.

z Известно, что величина равномерно распределена на отрезке ; 1.

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

количества машин, выходящих из туннеля за час.

Составить модель операции. Найти оценку эффективности произвольной стратегии в каждом из следующих предположений:

Pages:     | 1 | 2 | 3 |    Книги по разным темам