Математические модели операций.

Под исследованием операции (ИО) понимается применение мат. методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Осн. задача ИО – сравнение между собой различных вариантов решений и выбор наилучшего из них. Операция – совок-ть действий, направленных на достижение некот. цели. Это управляемое мероприятие. Наличие цели подразумевает существование участников, преследующих эту цель, для обозначения кот. Существует понятие оперирующая сторона. ОС – совок-ть лиц, стремящихся в данной операции к поставленной цели. В ОС выделяют исследователя операции (ИО). ИО преследует ту же цель, что и ОС, но, как правило, сам не принимает решения по выбору способов действия, а дает лишь рекомендации для принятия решения. Выбор, зависящий от параметров, наз. решением (стратегией). Для достижения поставленной цели ОС должна обладать активными средствами. Действия, направленные на достижение поставленной цели, предст. соб. способы использования активных средств (некот. запас ресурсов), наз. стратегиями. В зав от информированности ИО об усл-я: 1) Фиксированные факторы – факторы, точное зн-е кот известны ИО; 2) Случайные – сл вел, з-ны распределения, кот точно известны ИО; 3)неопред – сл вел отн-но кот ИО известна лишь обл возмож зн-й. Ход выполнения опер-и можно описать некот набором фазовых переменных. Степень соотношения хода выполнения операции поставл цели выполняется критерием эффективности. W явл ф-й фазовых перем контр и неконтр факторов. Матем. модель операции = { W(критерий эффективности), X, Y }, x≤ X, X=X() (X- прос-во стратегий, Y -мн-во некотрол. факторов).Модели: 1) динамические (присут пар-р t); 2) статические. Переход от динамической модели к статической наз нормализацией. В случае статич.модели w =F(x, y) – ф-я контр. и неконтр. факторов. Матем.объект, состоящий из {F(x, y), X, Y} наз. статич. или нормальной формой матем.модели. Общ приемов построения не сущ. 1)сформулировать цель; 2) определить активные ср-ва; 3) x – управляющие переменные; 4) построить пр-во стратегий; 5) неконтрол факторы y; 6) построить критерий эффективности w=F(x, y). Для сравнения стратегий удобно иметь оценки. Оценка, ставящая кажд. стратегии некот. действит. число, т.е. явл-ся ф-ей переменной х, наз. оценкой эффективности стратегии. Оценки эфф-ти опред-ся видом неконтролируемых факторов. 1) Отсутсвие неконтролируемого фактора или он явл-ся фиксированным. y=y⁰. w=F(x, y⁰) w явл. ф-ей одной переменной и выступает в роли оценки эффективности одной стратегии. f(x)=F(x, y⁰) Стратег. х₁ лучше стратег. х₂, если ее оценка эфф-ти больше оценки эфф-ти второй стр.: f₀(x₁)> f₀(x₂). Стратегия x⁰ наз. оптимальной стратегией, если ее оценка эфф-ти не больше оценки эфф-ти любой др. стратег.: f₀(x⁰)≥ f₀(x) " x Î X. 2) Случайный неконтролируемый фактор y. x^*- фиксир. w=F(x^*, y). В данной ситуации в роли оценки эфф-ти выступает мат. ожидание критерия эфф-ти по y. Пусть y имеет дискретный закон распред.

f_c(x)=M_yF(x, y) – оценка в среднем. x⁰ – оптимальная в среднем, если ее оценка в среднем не меньше всех остальных стратег. f_c(x⁰)≥ f_c(x) " x Î X 3) Неопределенные неконтрол. факторы.Известно лишь мн-во возможных знач-ий Y. Критерий эфф-ти примет значения:

Оценка эфф-ти Î [A, B]. В кач-ве оценки эфф-ти выбирают гарантированную оценку эфф-ти: .Гарантирующей оптимальной стратегией наз. x⁰, если вып-ся: " x Î X. " x Î X. Стратегии ф-ции Оптимальная гарантир-я стратегия ф-ции: Величину F_Г(X) на пространстве значений: наз max-м гарантированным результатом. Многокритериальные задачи исследования операций. Пусть w₁, w₂, …, w_m – частные критерии; w₀=f(w₁, w₂, …, w_m) w₀ –общий вид общего критерия; w₁, w₂, …, w_m – частн. критерии; f – некот. произвольная ф-ция Свертки критериев эффективности. Свертки: 1)суммирование с весовыми коэф-ми. (экономич. способ) , где l_i – некот. весовые коэф-ты, l_i≥ 0, i=1, …, m; (условие нормировки, необязат.) 2)переход от качествен. критериев к количествен. и обратно.Критерии, принимающие только два значения 0 и 1, наз. качественными.

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

, где w_i^* - пороговые знач-я частн. критериев.

Если все частн. критерии достигают порогов. значений, то исход операции удовлетворителен. 3)логические способы сверток для качествен. критериев: а) отрицание w₀=1-w₁ (m=1) б) конъюнкция (логич. умножение) в) дизъюнкция (логич. сложение) 4) обощенные логические способы сверток для количествен. критериев.а) противоположная цель w₀= - w₁ (m=1) б) оценка по наихудшему знач-ю частных критериев в) оценка по наилучшему значению Оптимальность по Парето. Часто бывает, что ОС затрудняется в выборе весовых коэф-тов и способе свертки. В такой ситуации вводят понятие оптимальности в терминах всех частн. критериев (вектор-критерий). Это т.н. оптимальность по Парето. Пусть (w₁(х), w₂(х), …, w_m(х)) отсутствует y. Т. х₀ наз. эффективной (оптимальной по Парето) стратегией, а вектор (w₁⁰(х), w₂⁰(х), …, w_m⁰(х)) – эффективн.значением вектора критериев, если не существ. такой т. хÎ Х (из прос-ва стратегий), что: w_i(x)≥ w_i(x⁰), i=1, …, m, причем для хотя бы одного номера это определение строгое: w_i(x)≥ w_i(x⁰). Эффективн. знач-е вектора частн. критериев наз. паретовской точкой.

Лемма.

Пусть т. х⁰ – эффективн.т., причем w_i(x⁰)> 0, i=1, …m, тогда , что для т. х⁰ явл-ся т-кой max.

Док-во: введем переменные и ;

;

Оценим знач-е частн. критерия на произвольн. стратегии. Т.к. х⁰ – эффективн. т. для данного критерия, то для " стратегии $ хотя бы один номер, для кот. вып-ся строгое соотношение

w₀(x) " xÎ X $ i₁ w_i1(x⁰)> w_i1(x)

Поэтому w₀(x) ≤ l_i1

w₀(х) ≤ w₀(х⁰) Þ х⁰ т. max

Т.о. оптимальные по Парето стратегии могут получаться как обычн. точки max общего критерия. Как правило эффект. точек для вектора критериев оказывается много. Мн-во эффект. значений вектора критериев наз. мн-вом Парето.

Различные типы задач исследования операций и методы их решения.

В кажд. разделе классификация проводится по виду критерия эффек-ти и прос-ва стратегий. Если крит. эф-ти и прос-во стратегий задаются линейн. соотношениями, то получ. линейное программ-е (ЛП). Если хотя бы один из этих объектов определен нелинейн. соотношением, то получ. нелин. программ-е (НП). Основн. метод поиска оптим. реш-ий в ЛП явл. симплекс-метод. Если по содержательному смыслу решение ЗЛП должно быть целыми числами, то получ. целочисленное программ-е (ЦП). Если крит. эф-ти и прос-во страт. обладают св-вом выпуклости, то получаем выпукл. прогамм-е (ВП). Если в ЗНП явно присутствует параметр времени, то получ. задачу динамич. программ-я (ДП). КвП – квадратическое программ-е. Наиб. известными явл. задачи массового обслуживания, задачи теории надежности, зад. управления запасами. Все они решаются вероятностно-стохастическими методами. Если мы используем гарантиован. оценки эф-ти, то получ. maxmin- ные или minmax -ные задачи (по своей сути это ЗНП), если неопределенность связана с др. участниками, то получ. т.н. игровые задачи (теория игр). Несмотря на многообразие задач ИО решение " задачи содержит 4 основных этапа: 1) неформальное содержательное описание проблемы и возможность способов действий на языке той области, в кот. возникла эта проблема; 2)составление мат. модели операции и формальн. представление задачи; 3)анализ поставлен.задачи мат. методами и нахожд-е в том или ином смысле наилуч. реш-я; 4)содержательн.смысловая интерпретация полученного реш-я и реализация его на практике.