Исследование операций (стр. 1 )

ФГОУ ВПО «Чувашский государственный университет имени »

Факультет дизайна и компьютерных технологий

Кафедра компьютерных технологий

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

(текст лекций)

Чебоксары 2010

ЛЕКЦИЯ 1

1.Введение.

Исследование операций (ИСО) - применение математических методов для моделирований систем и анализа их характеристик, при выборе наилучшего

способа управления этими системами.

ИСО – как средство решения задач организационного управления можно рассматривать как науку и как искусство .Научность ИСО определяется используемым математическим аппаратом Для того чтобы понять в чем состоит "искусство" исследования операций, лучше всего вспомнить так называемую "проблему …":

Служащие одной из фирм жаловались на слишком долгое время ожидания лифта. Была попытка решить проблему с помощью теории массового обслуживания. Однако это не дало результата. Дальнейшее исследование показало, что претензии сотрудников были необоснованны, т. е. время ожидания было "приемлемым" .Идея, решившая эту проблему оказалась проста – на каждом этаже поставили зеркало и жалобы сразу прекратились.

Люди рассматривали себя в зеркало и время ожидания проходило неза - метно.

Этот пример показывает, что при решении задач ИСО часто приходится сталкиваться с факторами, которые являются существенными, но не подда-

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

1.1 Формулировка задачи организационного управления

При формулировки задачи управления всегда выделяется :

1.  Цель управления ;

2.  Управляемые переменные ;

3.  Неуправляемые переменные ;

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

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

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

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

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

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

2. Задача линейного программирования .

Пример. Фабрика изготавливает два вида красок: В ( для внутренних работ) и Н ( для наружных работ ). Для производства красок используется два исходных продукта - А и В. Максимально возможные затраты этих продуктов составляют 6 и 8 тонн соответственно. Расходы А и В на 1 тонну соответствующих красок приведены ниже в таблице:

Исходный продукт	Расход на 1 тонну красок Н В	Максимально возможный запас, т
А	1	2	6
В	2	1	8

Изучение рынка сбыта показало, что суточный спрос на краску Н никогда не превышает спроса на краску В более чем на 1 тонну. Кроме того, установлено, что спрос на краску В никогда не превышает 2 тонн в сутки. Оптовые цены на краски: Н-3000$ за тонну, для краски В-2000$ за тонну.

Какое количество красок должна выпустить фирма, чтобы получить максимальную прибыль?

2.1 Построение математической модели .

  Переменные .

Так как нужно определить объемы производства, то переменными являются :

x1 – суточное производство краски Н;

x2 – суточное производство краски В.

  Целевая функция ( то есть функция, описывающая цель управления ).

В данном случае это общий доход обеих красок

W = 3 x1+2 x2 ( в тысячах $ ) .

Ограничения :

а) Ограничения на расход исходных продуктов :

x1 + 2 x2 < 6

2 x1 + x2 < 8

В левой части формул расход исходных продуктов за сутки, в правой – их запасы.

б) Ограничения на спрос :

x2 - x1 < 1

x2 < 2

Собрав все неравенства можно записать общую модель производства :

W = 3 x1+2 x2

 

x1 + 2 x2 < 6

2 x1 + x 2 < 8

x2 - x1 < 1

x2 < 2

x1 > 0

x2 > 0

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

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

Если целевая функция и ограничения линейны - линейного программирования .

Лучше всего суть решения задачи линейного программирования, можно понять рассмотрев ее графическое решение. Так можно решить задачи с число переменных равным двум. Нетрудно увидеть, что в рассматриваемом нами примере две переменных x1 и x2 .

2.2 Графическое решение задачи линейного программировавния .

W = 3 x1+2 x2

 

x1 + 2 x2 <

2 x1 + x 2 < 8

-x1 + x2 < 1

x2 < 2 xj > 0 ; j = 1,2 .

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

 

x1 + 2 x2 = 6

2 x1 + x 2 = 8

- x1 + x2 = 1

x2 = 2

Строим соответствующую ему граничную прямую. Каждая из этих прямых делит плоскость x1 О x2 на две полуплоскости.

Пример :

С одной стороны этой прямой x1 + 2 x2 < 6 ( 2 )

С другой x1 + 2 x2 > 6 ( 3 )

Для определения по какую сторону от граничной прямой располагается полуплоскость соответствующая заданному неравенству, достаточно искать какую либо одну точку – например точку О (0,0)

0 + 2*0 < 6

То есть нижняя полуплоскость соответствует неравенству ( 2 )

Полуплоскость, удовлетворяющую исходному неравенству x1 + 2 x2 < 6 отметим штриховкой.

Неравенствам x1>0, x2>0 тоже соответствует полуплоскости расположенные справа от О X2 и сверху от О X1.

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

X2

-x1+x2=1

2

 

 

Z

 

3

X2=2

D

C

E

B

X2

F

A

1

При построении ОДР может встретиться один из четырех случаев :

 

1. Имеет единственное решение.

  Имеет неограниченную область решений.

 

 

  Не имеет решений ( система ограничений не совместна ) .

 

ЛЕКЦИЯ 2

Рассмотрим выражение, соответствующее целевой функции : 2x1+x2 = 8

при фиксированном Z определяет прямую, а при изменении Z – семейство параллельных прямых : ( основная прямая )

Для всех точек, лежащих на 1 прямой Z имеет одно и то же значение. Вектор перепендикулярный этим прямым, показявает направление возрастания параметра Z .

x2

2

-3 3 x1

-2

Нанесем теперь W на рисунок с областью допустимых значений.

Очевидно задача поиска допустимого решения ограничений для которого целевая функция геометрически сводится к определению в ОДР точку, через которую пройдет линия W = Z, соответствующая максимальному значению Z. В нашем случае это точка E. Отметим, что в любом случае решение задачи ЛП или узловая точка или.

В зависимости от вида ОДР и W возможны следующие случаи :

A xопт w

x1 xопт

E A w' B

D w' A

D B xопт

C w'

C x1

w w w

a) б) в) г)

Случаи :

а) минимум достигается в 1 точке А ;

б) минимум достигается в 2-х вершинах А и В, и следовательно, во всех точках отрезка АВ ;

в) в 1 точке А ;

г) в .

2.2 Анализ решения задачи на чувствительность .

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

При анализе решения на чувствительность принято решать 3 задачи:

1) Определить влияние изменения ресурсов на оптимальное решение.

2) Определить, какой из ресурсов в наибольшей степени влияет на изменение целевой функции.

3) Определить как влияет изменение вида целевой функции на полученное решение.

2.3.1 Первая задача анализа на чувствительность .

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

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

связывающие ( активные ) и

несвязывающие ( неактивные )

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

Для решенной нами задачи связывающие ограничения :

x1+2x2 = 6

2x1+x2 = 8

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

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

Анализ влияния ресурсов включает в себя 2 задачи :

1)  Определить предельное увеличение дефицитного ресурса, позволяющее

улучшить найденное оптимальное решение.

2)  Определить предельное оптимальное снижение недифицитного ресурса, на ухудшающее найденного оптимального решения.

Решение любой из этих задач производится "деформацией" области допустимых решений.

Например ( график приведен ниже ), при изучении влияния ресурса А перемещается пример 1. При его увеличении она двигается вправо вверх. Увеличение целевой функции при этом "движении" будет происходить до тех пор, пока прямая не пересечет точку Q .( это произойдет при увеличении ресурса с 6 до 7 ). При дальнейшем увеличении оптимальную точку будут определять прямые (2) и (3) – ресурс В и ограничение спроса.

 

2x1+x2 = 8

 

Q

C D E

B

A

x1+2x2 = 6

 

W

Предельный ресурс А орпеделяется из координат точки Q , которая в свою очередь, получаются из совместного решения уравнений (2) и (3) – ресурс В и ограничение спроса :

2x1+x2 = 8

x2 = 2 , откуда x1=3

Предельный ресурс А:

А: x1+2x2 = 3+2*2=7

В этой точке ограничения 1: x1+2x2=А становится избыточным, так как любой дальнейший рост ресурса не влияет ни на пространство решений, ни на оптимальное решение.

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

Аналогичным образом можно рассчитать предельный ресурс В : Кривую (2) придется передвигать до пересечения некривой (1) с осью x1 .

Координаты этой точки:

x1+2x2 = 6

x2 = 0 , откуда x1 = 6 .

Ресуос В равный 2x1+x2 = 12

Ограничение x2 < 2 фиксируют предельный уровень на краску В. Из рисунка следует, что прямую x2 = 2 можно опускать, не изменяя оптимального решения, до уровня, пока эта прямая не достигнет точки Е( 10/3, 4/3 ). То есть уменьшение спроса на краску В до величины 4/3 не повлияет на оптимальность полученного решения.

Последнее ограничение : -x1+x2 < 1 анализируется подобным образом.

Полные результаты анализа приведены в таблице :

ресурс	тип	Max изменение запроса ресурса (т)	Max изменение дохода от реализации (тыс.$)
1. 2. 3. 4.	Дефицитный Дефицитный Недефицитный Недефицитный	7 - 6 = 1 12 - 8 = 4 -2 - 1 = - 3 4/3 - 2 = -2/3	13-12*(2/3)=1/3 18-12*(2/3)=5*(1/3) 12*(2/3)-12*(2/3)=0 12*(2/3)-12*(2/3)=0

2.3.2 Вторая задача анализа на чувствительность .

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

 

Функция определяет, насколько изменится целевая функция при изменении ресурса на 1 .

ресурс	тип	yi тыс.$ /тону
1. 2. 3. 4.	Дефицитный Дефицитный Недефицитный Недефицитный	y1 =1/3 y2 = 4/3 y3 = 0 y4 = 0

2.3.3. Третья задача анализа на чувствительность .

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

Примерительно к рассмотренному примеру задачу можно переформулировать так : Как влияет на оптимальное решение изменение цен на продукты.

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

а) Каков диаппазон изменения того или иного коэффициента целевой функции, при котором не происходит изменеия оптимального рещения.

б) Как нужно изменить тот или иной коэффициент целевой функции, чтобы какой-то недефицитный ресурс стал дефицитным, или наоборот.