Исследование операций / ИСО Учебник
.pdfФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РФ ФГОУ ВПО «СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Е. В. Зандер, В. П. Злодеев, Л. И. Мошкович, А. Р. Семёнова
ИССЛЕДОВАНИЕ
ОПЕРАЦИЙ В ЭКОНОМИКЕ
Учебное пособие
СФУ 2007
УДК 517.8
ББК 65в641 З-27
Рецензенты:
Зандер Е. В.
З-27 Исследование операций в экономике: учеб. пособие / Е. В. Зандер, В. П. Злодеев, Л. И. Мошкович, А. Р. Семёнова. — Сибирский федеральный ун-т. Красноярск: 2007. 202 с.
ISBN
Пособие представляет собой конспект лекций, который излагает основные разделы исследования операций в экономике, изучаемые студентами экономических специальностей вузов и необходимые для принятия управленческих решений в экономических ситуациях с использованием математических методов. Изложены базовые вопросы исследования операций в экономике: методология моделирования, использование линейных моделей в операционном анализе экономических систем, теория двойственности в анализе и принятии решений, моделирование нелинейности в экономических процессах, теория принятия решений в условиях неопределенности и риска, а также специальные задачи исследования операций (теория массового обслуживания, целочисленные задачи, модели транспортного типа и др.).
ISBN
©Сибирский федеральный университет, 2007
©Е. В. Зандер, В. П. Злодеев, Л. И. Мошкович, А. Р. Семёнова, 2007
2
ОГЛАВЛЕНИЕ
ОГЛАВЛЕНИЕ...................................................................................................................... |
|
3 |
РАЗДЕЛ 1. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ: ЛИНЕЙНЫЕ МОДЕЛИ В ЭКОНОМИКЕ...... |
5 |
|
ТЕМА 1.1. ЛИНЕЙНЫЕ МОДЕЛИ В ОПЕРАЦИОННОМ АНАЛИЗЕ ЭКОНОМИЧЕСКИХ СИСТЕМ .. |
5 |
|
Лекция 1.1.1. Основы методологии моделирования........................................................................ |
5 |
|
Лекция 1.1.2. Основные типы линейных моделей в операционном анализе экономики. |
|
|
Постановка задачи и основные определения ЗЛП......................................................................... |
11 |
|
Лекция 1.1.3. Графический метод нахождения решения линейных моделей. Геометрическая |
|
|
интерпретация решения. Метод прямого перебора....................................................................... |
19 |
|
Лекция 1.1.4. Симплексный метод и метод искусственного базиса для нахождения |
|
|
оптимального решения линейных задач исследования операций................................................ |
25 |
|
ТЕМА 1.2. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ОПЕРАЦИОННОМ АНАЛИЗЕ ЭКОНОМИЧЕСКИХ |
|
|
СИСТЕМ.................................................................................................................................................. |
37 |
|
Лекция 1.2.1. Формальная теория двойственности: основные понятия, определения, теоремы. |
|
|
Прямая и двойственная задачи, взаимосвязь их решений, правила построения ........................ |
37 |
|
Лекция 1.2.2. Постоптимальный анализ решения линейных моделей с использованием |
|
|
двойственных оценок: геометрическая интерпретация................................................................. |
46 |
|
Лекция 1.2.3. Постоптимальный анализ решения линейных моделей с использованием |
|
|
двойственных оценок: геометрическая интерпретация (продолжение) ...................................... |
51 |
|
Лекция 1.2.4. Постоптимальный анализ решения линейных моделей с использованием |
|
|
двойственных оценок: аналитический подход............................................................................... |
57 |
|
Лекция 1.2.5. Постоптимальный анализ решения линейных моделей с использованием |
|
|
двойственных оценок: аналитический подход (продолжение)..................................................... |
62 |
|
РАЗДЕЛ 2. НЕЛИНЕЙНЫЕ И СПЕЦИАЛЬНЫЕ МОДЕЛИ ИССЛЕДОВАНИЯ |
|
|
ОПЕРАЦИЙ........................................................................................................................ |
|
71 |
ТЕМА 2.1. НЕЛИНЕЙНОСТЬ В ЭКОНОМИЧЕСКИХ ПРОЦЕССАХ................................................... |
71 |
|
Лекция 2.1.1. Постановка задачи и методы решения для моделей нелинейного |
|
|
программирования............................................................................................................................ |
71 |
|
Лекция 2.1.2. Постановка задачи и методы решения для моделей выпуклого |
|
|
программирования............................................................................................................................ |
76 |
|
Лекция 2.1.3. Динамические модели в исследовании операций. Принцип оптимальности |
|
|
Беллмана для решения динамических задач. Сетевые модели и рекуррентные соотношения |
|
|
как основа методов нахождения решения динамических задач................................................... |
86 |
|
ТЕМА 2.2. СПЕЦИАЛЬНЫЕ МОДЕЛИ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ В ЭКОНОМИКЕ................. |
98 |
|
Лекция 2.2.1. Операционные модели транспортного типа. Методы их решения: нахождение |
|
|
опорного решения транспортной задачи ........................................................................................ |
98 |
|
3
Лекция 2.2.2. Операционные модели транспортного типа Методы их решения: нахождение |
|
оптимального решения транспортной задачи .............................................................................. |
109 |
Лекция 2.2.3. Целочисленные задачи исследования операций. Метод Гомори для нахождения |
|
их решения. Задача о назначениях и венгерский метод.............................................................. |
117 |
Лекция 2.2.4. Теория массового обслуживания: основные понятия, определения, теоремы.. |
128 |
Лекция 2.2.5. Многоканальные СМО: многоканальные и одноканальные системы массового |
|
обслуживания.................................................................................................................................. |
146 |
Лекция 2.2.6. Модели принятия решений в условиях неопределенности и риска ................... |
162 |
СПИСОК ЛИТЕРАТУРЫ.................................................................................................. |
195 |
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ........................................................................................... |
199 |
4
РАЗДЕЛ 1. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ: ЛИНЕЙНЫЕ МОДЕЛИ В ЭКОНОМИКЕ
ТЕМА 1.1. ЛИНЕЙНЫЕ МОДЕЛИ В ОПЕРАЦИОННОМ АНАЛИЗЕ ЭКОНОМИЧЕСКИХ СИСТЕМ
Лекция 1.1.1. Основы методологии моделирования
Использование математических методов для анализа экономических ситуаций предполагает предварительное описание изучаемой экономической системы математическими соотношениями, другими словами, создание математической модели этой системы.
Большинство экономических систем представляются сложными системами. Они характеризуются большим числом параметров, меняющихся во времени. Сложность анализа экономических систем в том, что существенной их составляющей являются люди, принимающие решения на основе разнообразной информации с учетом различных целей. Кроме того, экономическая система непрерывно подвергается множеству случайных, трудно прогнозируемых возмущений как извне (изменение количества и номенклатуры поставок, изменение спроса и т. д.), так и изнутри (появление новых технологий, поломка оборудования, несовпадение реальных сроков с планируемыми
ит. д.).
Вто же время экономико-математическая модель должна быть достаточно простой и обозримой, чтобы ее можно было записать, получить необходимые для записи данные, а если модель расчетная, то поместить полученную информацию в память ЭВМ. Математическая модель всегда «беднее» реальной моделируемой системы, всегда описывает систему лишь приблизительно, выделяя одни свойства системы и пренебрегая другими. Выбор важнейших свойств для учета в модели представляет собой искусство моделирования и определяется умением исследователя операций выделить (исходя из целей анализа) главное из большого количества факторов, цифр и соображений, затрудняющих решение задачи. Исследователю операций не говорят, какие данные необходимо собрать для решения задачи, а также где и как их
5
найти. Часто сбор необходимых данных требует изучения таких факторов, которые на первый взгляд не имеют отношения к предложенной задаче.
Модель создается тогда, когда, по убеждению исследователя, существует некая аналогия между реальной системой и его представлениями. При отсутствии достаточной информации об исследуемых объектах или процессах их изучение начинается с построения простейших моделей. Модели в исследовании операций служат для объединения опытных факторов и нахождения взаимосвязи между параметрами.
Конечная цель разработки математической модели — прогноз результатов проведения операции и выработка рекомендаций по возможным воздействиям на ход ее проведения. При этом необходим четкий анализ сферы и границ применимости полученных результатов. Обычно модели создаются на основе теоретических положений или гипотез, объясняющих полученные в результате наблюдений данные. Модели не следует считать неизменными, их нужно трактовать как инструмент анализа и понимания экономического процесса или системы. Для изучения одного и того же объекта или процесса может быть предложено несколько моделей, соответствующих целям анализа. При создании модели, обосновывающей возможное принятие решения о развитии конкретной ситуации, важное значение имеет количество выделяемого времени. Если требуется срочно выдать результаты, то создание сложной модели нецелесообразно. Во многих случаях модель нужна лишь для грубой оценки влияния отдельных факторов на результат. Подробное теоретическое исследование здесь также нецелесообразно.
Модель должна по возможности обладать «внутренней гибкостью», т. е. допускать возможность использования непредусмотренной новой информации. Сбор и обработка исходной информации являются важной частью исследования операции. К сожалению, при решении большинства практических задач не удается собрать нужный объем данных, необходимый для создания достаточно подробной модели процесса или объекта, охватывающей все аспекты задачи.
При рассмотрении экономико-математической модели оперируют следующими основными понятиями: «критерий оптимальности», «целевая функция», «система ограничений», «уравнения связи», «решение модели».
6
Целевую функцию нельзя отождествлять с критерием оптимальности: различные критерии могут описываться одной и той же целевой функцией.
Целевая функция математически связывает факторы модели (прежде всего переменные, «управляющие»).
Система ограничений определяет границы, сужающие область осуществляемых, приемлемых или допустимых решений, и фиксирует основные свойства моделируемого объекта или процесса. Ограничения устанавливают границы изменения параметров — характеристик объекта.
Уравнения (соотношения) связи являются математической формализацией системы ограничений.
Под критерием оптимальности обычно понимают экономический показатель, содержащий в формализованном виде конкретную цель управления объектом или процессом и выражаемый математически при помощи целевой функции через факторы модели.
Таким образом, критерий оптимальности выражает содержательное, смысловое значение целевой функции. Иногда в качестве критерия оптимальности может выступать одна из интересующих исследователя конечных характеристик объекта.
Решением экономико-математической модели обычно называют набор переменных, удовлетворяющий уравнениям связи. Решения, имеющие экономический смысл, называются допустимыми. Модели, имеющие более одного решения, называются вариантными. Среди допустимых решений вариантной модели находится решение, при котором целевая функция в зависимости от смысла модели имеет наибольшее или наименьшее значение. Такое решение (как и соответствующее значение целевой функции) называется оптимальным.
Применение экономико-математической модели, в особенности оптимизационной, при исследовании операций предполагает не только построение модели, но и получение решения при помощи подходящего метода. Поэтому иногда под моделированием (в более узком смысле) понимают этап нахождения решения. Выбор метода решения зависит от математической формы модели.
7
С точки зрения целей операционного анализа математические модели операций в экономике делятся на оптимизационные (нормативные) и дескриптивные (описательные или экономико-математические модели прямого счета). Важнейший признак дескриптивной модели — отсутствие критерия оптимальности. Решение модели сводится к вычислению выходных характеристик объекта по заданным начальным условиям. Примерами дескриптивных моделей могут быть модели расчета объемов производства по видам продукции, увязки планов производства с ресурсами (балансовые модели), а также модели оперативного учета, получения форм отчетности, анализа влияния факторов, прогнозирования показателей и ряд других. Модели этого типа позволяют решать задачи анализа, предлагающие ответ на вопрос: «Что будет, если…?».
Когда перед исследованием операции стоят задачи синтеза, требующие ответа на вопрос: «При каких значениях управляющих параметров будет достигнуто…?», необходима оптимизационная модель, характерной чертой которой является наличие одной (однокритериальная модель) или нескольких (многокритериальная) целевых функций. В общем виде однокритериальная модель может быть описана следующими соотношениями:
K = f (x1 ,…,xj ,...,xn ;α1,α2 ,…,αl )→extr,
≤
gi = gi (x1 ,…,xj ,...,xn ;α1,α2 ,…,αl ) ≥ 0 ,
=
где K — критерий оптимальности;
f — целевая функция — формализованное описание критерия оптимальности;
gi — уравнения связи, i =1,m;
xj — управляемые переменные, j =1,n;
αk — неуправляемые факторы модели, k =1,l .
Решение модели заключается в нахождении множества значений управляемых переменных
x*т = (x1*,…, xj*,…, xn*) ,
8
обращающих в max или min целевую функцию и удовлетворяющих уравнениям связи.
Учет специфики конкретных операций определяет разнообразные оптимизационные экономико-математические модели. Однако для некоторых часто повторяющихся ситуаций разработаны общие методы построения моделей. Исторически и содержательно наибольший интерес представляют линейные модели, т. е. те модели, в которых целевая функция и уравнения связи являются линейными функциями.
Сфера применимости и предпосылки построения линейных моделей в экономике
Широкое распространение в экономике линейных моделей (или, как еще говорят, линейного программирования) связано, во-первых, с тем, что многие экономические операции с достаточной точностью могут быть описаны линейными моделями; во-вторых, за небольшим исключением только для этих моделей разработаны эффективные методы численного решения при приемлемой для практики размерности задачи.
Примерами использования линейных моделей могут служить модели комплексного использования сырья, транспортная, размещения производства, перспективного планирования, развития экономического комплекса, различных ситуаций оперативного управления и т. д. Широко применяются такие модели и в связи с необходимостью анализа ситуаций, возникающих в экономике из-за большого числа возможных вариантов функционирования конкретного объекта при использовании различных видов сырья, материалов, технологий и других факторов.
Использование линейных моделей опирается на возможность рассмотрения плана (вектора управляемых переменных) в расчлененной форме, составленного из элементарных процессов, которые могут протекать с различной краткостью (интенсивностью). Также предполагается, что приращение критерия оптимальности и невязок условий задачи пропорциональны изменениям соответствующих управляемых переменных. Что, в частности, означает: увеличение выпуска продукции в некоторое число раз требует увеличения потребления объектом всех других продуктов в то же самое число раз.
9
Для многих задач планирования и управления такие допущения выглядят вполне приемлемыми и позволяют получать хорошие результаты.
Вместе с тем необходимо четко представлять границы линейности показателей, включаемых в модель операции. Известно, что существует так называемая условно постоянная часть расходов, не зависящая от количества выпускаемой продукции в определённом диапазоне изменения объемов. При интенсификации процессов могут меняться нормы расходов на единицу выпускаемой продукции тех или иных ингредиентов. Эти и ряд других моментов приводят к нарушению линейности объектов, выделяя тем не менее достаточно обширную сферу применимости линейных моделей в операционном анализе экономических ситуаций.
10