Методы исследования операций (49886)

Посмотреть архив целиком

МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ


Программа

Программа дисциплины «Методы исследования операций» предназначена для студентов специальности «Экономическая кибернетика».

Цель учебной дисциплины «Методы исследования операций» - вооружить студентов фундаментальными теоретическими знаниями и помочь сформировать практические навыки в вопросах постановки и решения оптимизационных экономических задач методами исследования операций.

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

Основное содержание дисциплины раскрывают такие темы:

I семестр

  1. Методы исследования операций и их использование в организационном управлении.

  2. Общая задача линейного программирования и некоторые методы ее решения.

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

  4. Анализ линейных моделей экономических задач.

  5. Транспортная задача. Постановка, методы решения.

  6. Целочисленные задачи линейного программирования. Некоторые методы их решения и анализа.

II и III семестры

  1. Элементы теории игр.

  2. Блочное программирование.

  3. Параметрическое программирование.

  4. Задачи календарного планирования.

  5. Задачи нелинейного программирования. Некоторые методы их решения.

  6. Динамическое программирование.

  7. Управление запасами.


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

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

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

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

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

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

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

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


Основные особенности исследования операций.


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

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

3. Одной из существенных особенностей исследования операций является стремление найти оптимальное решение поставленной задачи. Однако часто такое решение оказывается недостижимым из-за ограничений, накладываемых имеющимися в наличии ресурсами (денежные средства, машинное время) или уровнем современной науки. Например, для многих комбинаторных задач, в частности задач календарного планирования при числе станков п > 4, оптимальное решение при современном развитии математики оказывается возможным найти лишь простым перебором вариантов. Тогда приходится ограничиваться поиском «достаточно хорошего», или субоптимального решения. Поэтому исследование операций один из его создателей — Т. Саати — определил как «...искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами».

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

Каждое операционное исследование проходит последовательно следующие основные этапы:

  1. постановка задачи,

  2. построение математической модели,

  3. нахождение решения,

  4. проверка и корректировка модели,

  5. реализация найденного решения на практике.

В самом общем случае математическая модель задачи имеет вид:

найти

max Z=F(x, y) (1.1)

при ограничениях

, (1.2)

где Z=F(x, y) – целевая функция (показатель качества или эффективность) системы; х — вектор управляемых переменных; у — вектор неуправляемых переменных; Gi(x, y)— функция потребления i-го ресурса; bi величина i-го ресурса (например, плановый фонд машинного времени группы токарных автоматов в станко-часах).

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

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

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

1. Линейное программирование, если F(x, y), — линейны относительно переменных х.

2. Нелинейное программирование, если F(x, y) или — нелинейны относительно переменных х.

3. Динамическое программирование, если целевая функция F(x, y) имеет специальную структуру, являясь аддитивной или мультипликативной функцией от переменных х.

F(x)=F(x1, x2, …, xn) — аддитивная функция, если F(x1, x2, …, xn)=, и функция F(x1, x2, …, xn) — мультипликативная функция, если F(x1, x2, …, xn)=.

4. Геометрическое программирование, если целевая функция F(x) и ограничения представляют собой функции вида

Математическая модель задачи в этом случае записывается в виде

при условиях ,

,

где I[0]=(m0, m0+1, …, n0); I[k]= (mk, mk+1, …, nk); mk+1=nk+1; m0=1; n0=n.

5. Стохастическое программирование, когда вектор неуправляемых переменных у случаен.

В этом случае математическая модель задачи (1.1—1.2) будет иметь

maxMyE=My{f(x, y)}

при ограничениях

или вероятностных ограничениях

где My — математическое ожидание по у; Р{gi (х) b} — вероятность того, что выполняется условие gi (х) b.

6. Дискретное программирование, если на переменные xj наложено условие дискретности (например, целочисленности): xj целое, j=1,2,…,n1п.

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

По содержательной постановке выделяют следующие типичные классы задач исследования операций:

  1. управления запасами,

  2. распределения ресурсов,

  3. ремонта и замены оборудования,

  4. массового обслуживания,

  5. упорядочения,

  6. сетевого планирования и управления,

  7. выбора маршрута,

  8. комбинированные.

Из перечисленных выше методов математического программирования наиболее развитым и законченным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций.


Линейное программирование


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

Определение оптимального ассортимента. Имеется р видов ресурсов в количествах а1, а2, ..., аi, ..., аp и q видов изделий. Задана матрица А=||aik||, где аik характеризует нормы расхода i-го ресурса на единицу k-го изделия (k = 1, 2, ..., q).

Эффективность выпуска единицы k-го изделия характеризуется показателем сi, удовлетворяющим условию линейности.

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

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

найти

(1.3)

при ограничениях

(1.4)

Кроме ограничения по ресурсам (1.3), в модель могут быть введены дополнительные ограничения на планируемый выпуск продукции xjxj0, условия комплектности для сборки xi : хj : xk. = bi : bj : bk для всех i, j, k и т. д.

Оптимальное распределение взаимозаменяемых ресурсов. Имеются т видов взаимозаменяемых ресурсов а1, а2, ..., аi, ..., аm используемых при выполнении п различных работ в объеме b1, b2, …, bn.

Заданы числа ij, указывающие, сколько единиц j-й работы можно получить из единицы i-го ресурса, а также сij затраты при изготовлении единицы j-го продукта из i-го ресурса.

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

Данная задача называется общей распределительной задачей.

Количество единиц i-го ресурса, которое выделено для выполнения работ j-то вида, обозначим xij.

Математическая модель задачи такова:

найти

(1.5)

при ограничениях

(1.6)

(1.7)

Ограничение (1.6) означает, что план всех работ должен быть выполнен полностью, а ограничение (1.7) — что ресурсы должны быть израсходованы целиком.


  1. Математическая модель задачи линейного программирования (ЗЛП).

Задачу линейного программирования можно сформулировать так

Найти

(2.1)

при условиях

(2.2)

и

(2.3)

Ограничения (2.3) называют условиями неотрицательности. В данном случае все условия имеют вид неравенств. Иногда они могут быть смешанными, т. е. неравенства и равенства.

Определение 3. Допустимым множеством решений задачи (2.1)—(2.3) называется множество R(х) всех векторов х, удовлетворяющих условиям (2.2) и (2.3).

Очевидно множество R(х) представляет собой выпуклое многогранное множество или выпуклый многогранник.

Отметим, что поскольку minF(х) эквивалентен max[-F(х)], то задачу ЛП всегда можно свести к эквивалентной задаче максимизации.


Стандартная форма задачи линейного программирования

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


Допустимые базисные решения.

Пусть ограничения задачи ЛП заданы в форме уравнений, т.е. задача записана в стандартной форме и содержит m уравнений и n (nm) переменных. Тогда все допустимые крайние точки множества допустимых решений определяются как все однозначные неотрицательные решения системы m уравнений, в которых n-m переменных равны нулю. Однозначные решения такой системы уравнений, получаемые путем приравнивания к нулю (n-m) переменных, называются базисными решениями. Если базисное решение удовлетворяет требованию неотрицательности, оно называется допустимым базисным решением. Переменные, имеющие нулевое значение называются небазисными или свободными переменными, а остальные базисными.


Основные теоремы линейного программирования

В основе методов решения задач линейного программирования лежат следующие теоремы.

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

Теорема 2.1. Если целевая функция принимает максимальное значение в некоторой точке допустимого множества R, то она принимает это значение в крайней точке R (вершине выпуклого многогранника). Если целевая функция принимает максимальное значение более, чем в одной крайней точке, то она принимает это же значение в любой их выпуклой комбинации.

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

Теорема 2.2. Каждое допустимое базисное решение соответствует крайней точке R.

Справедлива также следующая теорема, обратная к теореме 2.2. Теорема 2.3. Если крайняя точка допустимого множества решений R, то соответствующее решение x0является допустимым базисным решением системы ограничений задачи линейного программирования.


Случайные файлы

Файл
130344.rtf
23480-1.rtf
164826.doc
20039.doc
33236.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.