I. Предмет и задачи исследования операций icon

I. Предмет и задачи исследования операций




Скачати 146.49 Kb.
НазваI. Предмет и задачи исследования операций
Дата06.09.2012
Розмір146.49 Kb.
ТипУчебное пособие

УДК 519.85


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

I. Предмет и задачи исследования операций

1.1 Предмет исследования операций

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

^ Исследование операций - это применение количественных методов обоснования решений во всех областях целенаправленной человеческой деятельности.

Чем сложнее, дороже, масштабнее планируемое мероприятие, тем менее допустимы в нем “волюнтаристские” решения и тем важнее становятся научные методы, позволяющие заранее оценить последствия каждого решения, отбросить недопустимые варианты и рекомендовать наиболее выгодные.

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

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

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

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

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

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

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

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

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

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

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


^ 1.2. Прямые и обратные задачи исследования операций

Задачи исследования операций делятся на два класса: прямые и обратные.

Прямые задачи отвечают на вопрос: что будет, если в заданных условиях будет принято решение хХ?. В частности, чему будет равен, при данном решении х, выбранный показатель эффективности L(х).

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

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

Для решения обратных задач для многих экономических задач используются методы математического программирования. Они позволяют отыскать значения переменных, обеспечивающих экстремум показателя эффективности при наличии ограничений, накладываемых на эти переменные. Слово программирование в данном случае является неудачным переводом слова “program”, которое в рассматриваемом случае означает “планирование”.

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

найти максимум или минимум функции многих переменных

(1.1)

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

(1.2)

(1.3.)

Функция L(х1, х2, ..., хn) называется целевой функцией, она характеризует эффективность исследуемой модели. Ограничения (1.2) и (1.3) определяют область допустимых значений вектора неизвестных переменных

х=/ х1, х2, ..., хn/.

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




Рис. 1.1

К задачам линейного программирования относятся те, у которых целевая функция f(x) линейно зависит от неизвестных х1, х2, ..., хn, а ограничения, налагаемые на эти неизвестные имеют вид линейных равенств или неравенств. В линейном программировании существуют классы задач, структура которых позволяет разработать для их решения более простые специальные методы. Так в линейном программировании появились разделы транспортных задач и задач о назначениях.

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

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

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

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

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


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

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

Пример 1. Фирма “Сатурн” изготавливает два вида продукции П1 и П2, реализация которых с учетом производственных возможностей фирмы неограниченна. Для производства используется ресурсы трех типов: трудовые, материальные, финансовые. Известно количество ресурсов, которое имеется в распоряжении фирмы, а также затраты каждого вида ресурсов для изготовления единицы продукции П1 и П2. Известна также прибыль на единицу каждого вида продукции. Эти данные представлены в таблице 2.1.

Таблица 2.1

Ресурсы

Затраты на

единицу продукции

Наличие




П1

П2

ресурсов

Трудовые

2

8

28

Материальные

1

3

32

Финансовые

12

4

50

Прибыль на единицу продукции

3

5





Необходимо составить план распределения ресурсов.

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

  • какие параметры нужно определить в данной задаче?

  • какой критерий оптимальности планирования необходим для данной задачи? (что характеризует эффективность исследуемой модели?)

  • какие ограничения существуют при решении данной задачи.

Для рассматриваемой задачи планирования неизвестными являются планы выпуска продукции П1 и П2.

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

Естественными являются ограничения на используемые ресурсы, которые не могут превышать их наличия.

После ответа на эти вопросы строится математическая модель.

  1. Переменные (искомые величины) данной задачи обозначим через х1 - план выпуска продукции П1 и х2 - план выпуска продукции П2.

  2. Целевая функция (прибыль) должна быть максимизирована

L = 3x1+5x2  max.

  1. Ограничения на расходуемые ресурсы можно записать следующим образом

1+8х2  28;

х1+3х2  32;

12х1+4х2  50.

Кроме того, естественные ограничения заключаются в том, что планы выпуска продукции П1 и П2 не могут быть отрицательными, т.е. необходимо ввести ограничения на их знак:

х1  0;

х2  0.

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

max L = 3x1+5x2,

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







Данная модель является линейной, потому что входящие в нее функции (целевая функция и ограничения) линейны. Линейность предполагает наличие двух свойств - пропорциональность и аддитивность.

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

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

Пример 2. Фирма “Альтаир” располагает двумя видами станков, из них N1 станков типа 1 и N2 станков типа 2. Станки могут производить три вида продукции: П1; П2; П3, но с разной производительностью. Данные аij производительности станков даны в таблице 2.2.

Каждая единица продукции П1 приносит фирме доход С1, продукции П2 - С2; продукции П3 - С3. Фирма имеет лицензию, согласно которой она должна производить в месяц не более 1 единиц продукции П1; 2 - продукции П2; 3 - продукции П3. Фирма уже получила заказы, согласно которым она должна производить в месяц не менее b1 единиц продукции П1; не менее b2 продукции П2 и не менее b3 продукции П3.

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

Таблица 2.2







Производительность




Наличие

Тип станка




Вид продукции




станков




П1

П2

П3




1

а11

а12

а13

N1

2

a21

a22

a23

N2

Лицензия

1

2

3




Заказы

b1

b2

b3




Прибыль

С1

С2

С3





В этой задаче неизвестными должны выступать не количество продукции каждого вида, а количество станков типов 1 и 2, занятых производством продукции каждого вида. Всего будет шесть неизвестных переменных:

х11, х12, х13,

х21, х22, х23,

где хij - количество станков i-го вида (i=1,2), занятых изготовлением продукции Пj (j=1,3). Запишем сначала ограничения, накладываемые на переменные хij.

Для обеспечения заказа необходимо, чтобы







Для соблюдения плана, определяемого лицензией, необходимо, чтобы







Ограничения, связанные с наличием станков





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

хij  0, i=1,2; j=1,2,3.

Целевая функция должна быть равна суммарному доходу от производства всех видов продукции:




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

Любую задачу линейного программирования можно свести к стандартной (канонической) форме, которая формулируется так: найти неотрицательные значения переменных х1, х2, ..., хn, которые удовлетворяли бы условиям - равенством

(1.4)

где и обращали бы в максимум линейную функцию этих переменных

(1.5)

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



эквивалентна максимизации функции



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

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

Например, при исходном неравенстве

1+7х2  9,

вводится остаточная переменная х3, в результате чего исходное неравенство обращается в равенство

1+7х2 3=9, х30.

Если исходное ограничение определяет расход некоторого ресурса, то переменную х3 следует интерпретировать как остаток, или неиспользованную часть, данного ресурса.

Если исходное ограничение имеет вид другого типа

1+5х2  7,

то вычитая из его левой части избыточную переменную х4, получаем

1+5х24=7, х4  0.

Если в каком-то ограничении правая часть отрицательна, то умножив обе части этого ограничения на -1, всегда можно сделать ее неотрицательной.

Например, равенство 2х1+8х2-3х3=-6 эквивалентно равенству -2х1-8х2+3х3=6.

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

Например, неравенство 2х1-5х2>-3 эквивалентно неравенству -2х1+5х2<3.

Наконец, если какая-то переменная хi не имеет ограничения в знаке, ее можно представить как разность двух неотрицательных переменных

хi=xi-x’’i, где хi0; x’’i0.

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

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

min L = 2x1+5x2,

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

12=10,

-2х1+3х2-8,

1+4х26,

х20, х1 не имеет ограничения в знаке.

Решение. Умножим второе неравенство на -1 и вычтем избыточную переменную х3, получим

1-3х23=8, х30.

Прибавим остаточную переменную к третьему неравенству:

1+4х24=6, х40.

В целевой функции и во всех ограничениях осуществим подстановку х11-x’’1, где x10; x’’10.

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

max (-L)=-2x’1+2x’’1-5x2,

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












Схожі:

I. Предмет и задачи исследования операций iconI. Предмет и задачи исследования операций
Учебное пособие представляет собой конспект лекций для студентов экономических специальностей по одноименной дисциплине. В каждой...
I. Предмет и задачи исследования операций iconI. Предмет и задачи исследования операций
Учебное пособие представляет собой конспект лекций для студентов экономических специальностей по одноименной дисциплине. В каждой...
I. Предмет и задачи исследования операций iconI. Предмет и задачи исследования операций
Учебное пособие представляет собой конспект лекций для студентов экономических специальностей по одноименной дисциплине. В каждой...
I. Предмет и задачи исследования операций iconДегтярев Ю. И. Исследование операций. М.: Высшая школа, 1986. Зайченко Ю. П. Исследование операций
Вентцель Е. С. Исследование операций: Задачи,принципы,методология. М.: Наука, 1980
I. Предмет и задачи исследования операций iconДегтярев Ю. И. Исследование операций. М.: Высшая школа, 1986. Зайченко Ю. П. Исследование операций
Вентцель Е. С. Исследование операций: Задачи, принципы, методология. М.: Наука, 1980
I. Предмет и задачи исследования операций iconКонтрольные вопросы по курсу "Исследование операций и теория игр" Утвержден на заседании кафедры высшей математики и информатики
Формулировка и математические модель задачи линейного программирования (ЛП) как задачи распределения ресурсов
I. Предмет и задачи исследования операций iconЛітература до навчального плану курсу " Математичне програмування "
Вентцель Е. С. Исследование операций: Задачи,принципы,методология. М.: Наука, 1980
I. Предмет и задачи исследования операций iconЛітература до навчального плану курсу " Дослідження операцій "
Вентцель Е. С. Исследование операций: Задачи,принципы,методология. М.: Наука, 1980
I. Предмет и задачи исследования операций iconКонтрольные вопросы по дисциплине «Исследование операций» Математическая модель задачи линейного программирования. Пример
Определение дефицитных и недефицитных ресурсов в задаче лп на основе ее графического решения. Пример
I. Предмет и задачи исследования операций iconКонтрольные вопросы по дисциплине «Исследование операций» Математическая модель задачи линейного программирования. Пример
Определение дефицитных и недефицитных ресурсов в задаче лп на основе ее графического решения. Пример
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи