Мастяева И.Н. Исследование операций в экономике

Что мешает нам развиваться и жить. Почему мы бедные

Домой Связной Мастяева И.Н. Исследование операций в экономике

Связной

МИНИСТЕРСТВО ОБРАЗОВАНИЯРОССИЙСКОЙ ФЕДЕРАЦИИ

Московский государственный университет экономики, статистики и информатики

Московский международный институт эконометрики, информатики, финансов и права

И.Н. Мастяева Г.Я. Горбовцов О.Н. Семенихина

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

Москва, 2001

УДК 519.6 ББК 22.18 М - 327

И.Н. Мастяева, Г.Я. Горбовцов, О.Н. Семенихина. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ: Учебное пособие / Московский Государственный Университет Экономики, Статистики и Информатики. М.: МЭСИ, 2001. с.116


Программа курса «Исследование операций в экономике»........................
	Моделирование в экономике.....................................................................
	Теория двойственности в линейном программировании.
Двойственный симплексметод. .................................................................
2.1. Определение и экономический смысл двойственной ЗЛП...........
2.2.Основные положения теории двойственности..................................
2.3.Анализ решения ЗЛП с помощью теории двойственности.............
2.4. Анализ решения ЗЛП на основе отчётов MS EXCEL .....................
2.5. Двойственный симплекс-метод (Р-метод)........................................
	Целочисленные модели исследования операций...................................
	Экономические задачи, сводящиеся к транспортной модели..............
	Нелинейные модели................................................................................
5.1. Методы одномерной оптимизации..................................................
5.2. Методы безусловной оптимизации. ................................................
Литература. ..................................................................................................

Программа курса «Исследование операций в экономике»

Тема 1. Моделирование в экономике. Определение экономикоматематической модели, ее свойства. Классификация моделей по различным признакам.

Тема 2. Теория двойственности в линейном программировании. Двойственный симплекс-метод. Определение и правила постро-

ения двойственных задач, их экономический смысл. Теоремы двойственности. Различные способы отыскания решения двойственной задачи по решению прямой. Экономический анализ линейных моделей на основе теории двойственности. Двойственный симплекс-метод. Р- матрица, псевдоплан, условия перехода от одного псевдоплана к другому. Алгоритм двойственного симплекс-метода.

Тема 3. Целочисленные модели исследования операций.

Примеры задач целочисленного линейного программирования. Метод ветвей и границ решения задачи целочисленного линейного программирования: идея и алгоритм. Постановка задачи коммивояжера. Применение метода ветвей и границ для решения задачи коммивояжера.

Тема 4. Экономические задачи, сводящиеся к транспортным моделям. Транспортная задача (ТЗ) линейного программирования. Математическая модель. Закрытая и открытая модели ТЗ. Опорный план ТЗ. Методы построения первоначальных опорных планов. Метод потенциалов решения ТЗ, его обоснование и алгоритм. ТЗ с запрещенными перевозками. Задача оптимального распределения оборудования. Формирование оптимального штата фирмы. Задача календарного планирования. Задача о назначениях, венгерский метод ее решения. Оптимальное исследование рынка. Оптимальное использование рабочих агентов.

Тема 5. Нелинейные модели исследования операций.

Постановка задачи нелинейного программирования (ЗНП). Одномерная оптимизация. Алгоритм Свенна поиска отрезка, содержащего точку максимума. Метод золотого сечения решения задачи одномерной оптимизации. Безусловная оптимизация. Метод скорейшего подъема (спуска). Условная оптимизация. Метод Зойтендейка.

1. Моделирование в экономике

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

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

По степени агрегирования объектов моделирования различают модели:

Микроэкономические; - одно-, двухсекторные (одно-, двухпродуктовые);

Многосекторные (многопродуктовые); - макроэкономические; - глобальные.

По учету фактора времени различают модели: - статические; - динамические.

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

По цели создания и применения различают модели: - балансовые; - эконометрические;

Оптимизационные; - сетевые;

Систем массового обслуживания; - имитационные (экспертные).

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

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

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

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

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

Модели систем массового обслуживания создаются для минимизации затрат времени на ожидание в очереди и времени простоев каналов обслуживания.

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

По учету фактора неопределенности различают модели:

- детерминированные (с однозначно определенными резуль-

- стохастические (с различными вероятностными результатами). По типу математического аппарата различают модели:

- линейного и нелинейного программирования;

- корреляционно-регрессионные;

Матричные;

Сетевые;

Теории игр;

- теории массового обслуживания и т.д .

Домашнее задание 1.

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

		Распределение
	капиталовложений
			год 2 год 3





Максимальный
капиталовложений

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

2. Совет директоров фирмы изучает предложения по наращиванию производственных мощностей на трех принадлежащих фирме предприятиях. Для расширения всех трех предприятий фирма выделяет средства в объеме 5 млн. руб. Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами суммарных затрат (C) и доходов (R), связанных с реализацией каждого из проектов. Соответствующие данные приведены в таблице, в которую включены также проекты с нулевыми затратами. Это позволяет учесть возможность отказаться от расширения какого-либо предприятия.

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

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

вида ресурсов: материальные и трудовые Возможны четыре варианта расхода ресурсов и получения прибыли (табл.).

Показатели			Варианты



Прибыль, д.е./ед.
Материальные

Трудовые ресурсы

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

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

1) избытка произведенных в прошлом месяце изделий, сохраняющихся для реализации в будущем;

2) производства изделий в течение текущего месяца; 3) избытка производства изделий в более поздние месяцы в счет

невыполненных заказов.

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

В рассматриваемые четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответственно. Требуется составить план, имеющий минимальную стоимость производства и хранения изделий.

5. Известен рыночный спрос на определенное изделие в количестве 180 штук. Это изделие может быть изготовлено двумя

предприятиями по различным технологиям. При производстве x1 изделий первым предприятием его затраты составят (4x1 + x1 2 ) руб., а

при изготовлении x2 изделий вторым предприятием они составят (8x2 + x2 2 ) руб. Определить, сколько изделий, изготовленных по каждой технологии, может предложить концерн, чтобы общие издержки его производства были минимальными.

6. На двух предприятиях холдинга необходимо изготовить 200

изделий некоторой продукции. Затраты, связанные с производством x1 изделий на первом предприятии, равны 4x1 2 руб., а затраты,

обусловленные изготовлением x2 изделий на втором предприятии, составляют (20x2 + 6x2 2 ) руб.

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

7. Для производства двух видов изделий А и В используется три типа технологического оборудования. Известны затраты времени и других ресурсов на производство ед. изделия каждого вида (см. табл.)

	Нормы времени	Огр. по фонду времени
оборудования		Верхний предел	Нижний предел




производство

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

8.Имеется в наличии b = 5 единиц одного ресурса, который в начале планового периода необходимо распределить между тремя предприятиями. Известны аk – количество единиц ресурса, идущего на изготовление единицы продукции k-м предприятием (k = 1,2,3), а2 =а3 =1, а1 =2 и gk (yk ) – доход от выпуска yk единиц продукции k-м предприятием.

g1 (y1 )=1,4y1 – 0,2y1 2 g2 (y2 )=2y2 g3 (y3 )=2y3 – 0,3y3 2

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

9.Требуется разместить n производственных агрегатов на n различных производственных участках. Количество материалов, транспортируемых между агрегатами i и j, равно dij ; удельные затраты на транспортировку материалов с участка p на участок q составляют cqp . Построить модель целочисленного программирования, минимизирующую суммарные затраты на транспортировку.

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

Накладные		Производительность
	производство	(в единицах продукции)
	единицы продукции

Сформулировать задачу целочисленного программирования.

2. Теория двойственности в линейном программировании. Двойственный симплексметод.

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

1. Предмет и задачи исследования операций в экономике. Основные понятия теории исследования операций.

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

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

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

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

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

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

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

Параметры, совокупность которых образует решение, называются элементами решения.

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

Показатель эффективности - количественная мера, позволяющая сравнивать разные решения по эффективности.

2. Понятие о сетевом планировании и управлении. Сетевая модель процесса и ее элементы.

Метод работы с сетевыми графиками – сетевое планирование – базируется на теории графов. В переводе с греческого граф (grafpho – пишу) представляет систему точек, некоторые из них соединены линиями – дугами (или ребрами). Это топологическая (математическая) модель взаимодействующих систем. С помощью графов можно решать не только задачи сетевого планирования, но и другие задачи. Метод сетевого планирования применяется при планировании проведения комплекса взаимосвязанных работ. Он позволяет наглядно представить организационно-технологическую последовательность выполнения работ и установить взаимосвязь между ними. Кроме этого, он позволяет обеспечить координацию операций различной степени сложности и выявить операции, от которых зависит продолжительность всей работы (т.е. организационного мероприятия), а также сосредоточить внимание на своевременном выполнении каждой операции.

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

Основные понятия сетевой модели:

Событие, работа, путь.

Событиями называются результаты выполнения одной или нескольких работ. Они не имеют протяженности во времени.

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

Продолжительность пути определяется суммой продолжительностей составляющих его работ.

3. Построение и упорядочивание сетевого графика.

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

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

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

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

Зависимость (фиктивная работа), не требующая затрат времени изображается пунктирной стрелкой. Фиктивная работа используется в сетевом графике для отражения связей между событиями и работами.

В сетевом графике применяются временные, стоимостные и другие характеристики работ.

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

Стоимость работы – это прямые затраты, необходимые для ее выполнения, зависящие от длительности и условий выполнения этой работы.

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

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

Событие - это факт окончания одной или нескольких работ, необходимый и достаточный для начала одной или нескольких последующих работ. Каждому событию присваивается номер, называемый кодом. Каждая работа определяется двумя событиями: кодом начального события, обозначаемого i и кодом конечного события, обозначаемого буквой j.

События, не имеющие предшествующих работ, называются начальными; события, не имеющие последующих – конечными.

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

2 При построении сети решаются вопросы:

Какие работы (работу) необходимо выполнить, чтобы начать данную работу;

Какие работы целесообразно выполнять параллельно с данной работой;

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

4 Форма графика должна быть простой и зрительно легко воспринимаемой.

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

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

4. Критический путь сетевого графика. Резервы времени. Ранние и поздние сроки событий и работ в сетевом графике.

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

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

Особое значение при составлении сетевого графика имеют два понятия:

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

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

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

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

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

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

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

5. Динамическое программирование. Принцип оптимальности и управления Беллмана.

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

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

Главным недостатком метода является, говоря словами Беллмана, «проклятие размерности» – его сложность катастрофически возрастает с увеличением размерности задачи.

6. Задача о распределении средств между предприятиями.

Можно сказать, что процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную и окончательную. На предварительной стадии для каждого шага определяется УОУ зависящее от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация - также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.

7. Постановка задачи линейного программирования.

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

С точки зрения прогнозирования допустимых интервалов цен (или объемов продаж) в рамках обобщенного непараметрического метода, применение линейного программирования означает:

Критерием является MAX цена очередного продукта из интересуемой группы f.

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

Ограничениями в нашей задаче прогнозирования с использованием обобщенного непараметрического метода, являются:

a) система неравенств (ограничения рациональности поведения потребителя) (см. 4.2. Прогнозирование в рамках обобщенного непараметрического метода);

б) требование неотрицательности управляемых переменных (в нашей задаче прогнозирования мы потребуем, чтобы цены на продукты из группы f не опустились ниже 80% от значений цен в последней временной точке) ;

в) бюджетное ограничение в виде равенства - требование постоянства суммы затрат на покупку продуктов из группы f (с учетом 15% инфляции, например).

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

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

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

Найти минимальное значение функции

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) х1 0, х2 0

Допустим, что система (2.2) при условии (2.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (2.2) и (2.3), как отмечалось выше, определяет полуплоскость с граничными прямыми: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), х1=0, х2=0. Линейная функция (2.1) при фиксированных значениях Z является уравнением прямой линии: С1х1 + С2х2 = const. Построим многоугольник решений системы ограничений (2.2) и график линейной функции (2.1) при Z = 0 (рис. 2.1). Тогда поставленной задаче линейного прграммирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая С1х1 + С2х2 = const опорная и функция Z при этом достигает минимума.

Значения Z = С1х1 + С2х2 возрастают в направлении вектора N =(С1, С2), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора Х. Из рис. 2.1 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А (х1, х2) находим, решая систему уравнений прямых АВ и АЕ.

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

Случай 1. Прямая С1х1 + С2х2 = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.2).

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

9. Симплекс- метод.

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

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

10. Постановка транспортной задачи. Методы определения опорных планов.

Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:

ai – объемы производства i -го поставщика, i = 1, …, m;

вj – спрос j-го потребителя, j= 1,…,n;

сij – стоимость перевозки одной единицы продукции из пункта Ai– i-го поставщика, в пункт Вj – j-го потребителя.

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

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

Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести m·n штук переменных хij, i= 1,…, n, j= 1, …, m, каждая переменная хij обозначает объем перевозок из пункта Ai в пункт Вj. Набор переменных X = {xij} и будет планом, который необходимо найти, исходя из постановки задачи.

Это условие для решения закрытых и открытых транспортных задач (ЗТЗ).

Очевидно, что для разрешимости задачи 1 необходимо, чтобы суммарный спрос не превышал объема производства у поставщиков:

Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной», если же , то задача называется «закрытой» транспортной задачей, и будет иметь вид (2):

– условие сбалансированности.

Это условие для решения закрытых транспортных задач (ЗТЗ).

11. Алгоритм решения транспортной задачи.

Применение алгоритма требует соблюдения ряда предпосылок:

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

2. Запас продуктов в каждом пункте производства должен быть известен.

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

4. Общее предложение должно быть равно общему спросу.

Алгоритм решения транспортной задачи состоит из четырех этапов:

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

Этап 2. Проверка полученного распределения ресурсов на оптимальность

Этап 3. Если полученное распределение ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.

Этап 4. Повторная проверка оптимальности полученного распределения ресурсов.

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

12. Модели управления запасами.

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

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

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

детерминированными;

вероятностными.

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

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

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

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

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

процесс пополнения запаса. Может быть мгновенным либо распределенным во времени;

наличие ограничений по оборотным средствам, складской площади т.п.

13. Системы массового обслуживания (СМО) и показатели их эффективности.

Системы массового обслуживания (СМО) представляют собой системы специального вида, реализующие многократное выполнение однотипных задач. Подобные системы играют важную роль во многих областях экономики, финансов, производства и быта. В качестве примеров СМО в финансово-экономической; сфере можно привести банки различных типов (коммерческие, инвестиционные, ипотечные, инновационные, сберегательные), страховые организации, государственные акционерные общества, компании, фирмы, ассоциации, кооперативы, налоговые инспекции, аудиторские службы, различные системы связи (в том числе телефонные станции), погрузочно-разгрузочные комплексы (порты, товарные станции), автозаправочные станции, различные предприятия и организации сферы обслуживания (магазины, справочные бюро, парикмахерские, билетные кассы, пункты по обмену валюты, ремонтные мастерские, больницы). Такие системы, как компьютерные сети, системы сбора, хранения и обработки информации, транспортные системы, автоматизированные производственные участки, поточные линии, различные военные системы, в частности системы противовоздушной или противоракетной обороны, также могут рассматриваться как своеобразные СМО

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

Системы массового обслуживания могут быть одноканальными или многоканальными.

Каждая СМО предназначена для обслуживания (выполнения) некоторого потока заявок (требований), поступающих на вход системы большей частью не регулярно, а случайные моменты времени. Обслуживание заявок, в этом случае, также длится не постоянное, заранее известное время, а случайное время, которое зависит от многиx случайных, порой неизвестных нам, причин. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времени их обслуживания приводит к неравномерной загруженности СМО: в иное время на входе СМО могут скапливаться необслуженные заявки, что приводит к перегрузке СМО, а иногда при свободных каналах на входе СМО заявки не будет, что приводит к недогрузке СМО, т.е. к простаиванию ее каналов. Заявки, скапливающиеся на входе СМО, либо «становятся» в очередь, либо по причине невозможности дальнейшего пребывания в очереди покидают СМО необслуженными.

Показатели эффективности функционирования пары «СМО - потребитель», где под потребителем понимают всю совокупность заявок или некий их источник (например, средний доход, приносимый СМО в единицу времени, и т.п.). Эта группа показателей оказывается полезной в тех случаях, когда некоторый доход, получаемый от обслуживания заявок, и затраты на обслуживание измеряются в одних и тех же единицах. Эти показатели обычно носят вполне конкретный характер и определяются спецификой СМО, обслуживаемых заявок и дисциплиной обслуживания.

14. Уравнения динамики для вероятностных состояний (уравнения Колмогорова). Предельные вероятности состояний.

Формально дифференцируя уравнение Колмогорова-Чепмена по s при s = 0 получаем прямое уравнение Колмогорова:

Формально дифференцируя уравнение Колмогорова - Чепмена по t при t = 0 получаем обратное уравнение Колмогорова

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

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

На рис. показаны граф состояния и переходов, удовлетворяющие поставленному условию: из любого состояния система рано или поздно может перейти в любое другое состояние. Условие не будет выполняться при изменении направления стрелки 4-3 на графе рис, а на противоположное.

Допустим, что поставленное условие выполнено, и, следовательно, предельные вероятности существуют:

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

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

15. Процесс гибели и размножения.

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

Потоками размножения λi(t) будем называть пуассоновские потоки, ведущие к увеличению функции X(t). Соответственно μi(t) – потоки гибели, ведущие к уменьшению функции X(t).

Составим по графу уравнения Колмогорова:

Если поток с конечным числом состояний:

Система уравнений Колмогорова для процесса гибели и размножения с ограниченным числом состояний имеет вид:

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

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

16. Системы массового обслуживания с отказами .

Наиболее простой из рассматриваемых задач в рамках теории массового обслуживания является модель одноканальной СМО с отказами или потерями.

Следует отметить, что в данном случае количество каналов равно 1 (). Этот канал принимает пуассоновский поток заявок, интенсивность которого равняется . Время оказывает влияние на интенсивность:

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

17. Системы массового обслуживания с ожиданием .

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

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

Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):

Канал свободен;

Канал занят, очереди нет;

Канал занят, одна заявка стоит в очереди;

Канал занят, k - 1 заявок стоят в очереди;

Канал занят, т заявок стоят в очереди.

18. Методы принятия решений в условиях конфликта. Матричные игры. Чистые и смешанные стратегии игр.

Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

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

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

Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=), 2 – свою j-ю стратегию (j=), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij<0, то это значит, что игрок 1 платит второму сумму | аij|). На этом игра заканчивается.

Каждая стратегия игрока i=; j = часто называется чистой стратегией.

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

Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x– это набор чисел x = (x1,..., xm) удовлетворяющих соотношениям

xi³ 0 (i= 1,m), =1.

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y– это набор чисел

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

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

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

19. Геометрический метод решения матричной игры.

Решение игр размера 2xn или nx2 допускает наглядную геометрическую интерпретацию. Такие игры можно решать графически.

На плоскости XY по оси абсцисс отложим единичный отрезок A1A2 (рисунок 5.1). Каждой точке отрезка поставим в соответствие некоторую смешанную стратегию U = (u1, u2). Причем расстояние от некоторой промежуточной точки U до правого конца этого отрезка – это вероятность u1 выбора стратегии A1, расстояние до левого конца - вероятность u2 выбора стратегии A2. Точка А1 соответствует чистой стратегии А1, точка А2 – чистой стратегии А2.

В точках А1 и А2 восстановим перпендикуляры и будем откладывать на них выигрыши игроков. На первом перпендикуляре (совпадающем с осью OY) покажем выигрыш игрока А при использовании стратегии А1, на втором – при использовании стратегии A2. Если игрок А применяет стратегию A1, то его выигрыш при стратегии B1 игрока B равен 2, а при стратегии B2 он равен 5. Числам 2 и 5 на оси OY соответствуют точки B1 и B2. Аналогично на втором перпендикуляре найдем точки B"1 и B"2 (выигрыши 6 и 4).

Соединяя между собой точки B1 и B"1, B2 и B"2, получим две прямые, расстояние от которых до оси OX определяет средний выигрыш при любом сочетании соответствующих стратегий.

Например, расстояние от любой точки отрезка B1B"1 до оси OX определяет средний выигрыш игрока A при любом сочетании стратегий A1 и A2 (с вероятностями u1 и u2) и стратегии B1 игрока B.

Ординаты точек, принадлежащих ломаной B1MB"2 определяют минимальный выигрыш игрока A при использовании им любых смешанных стратегий. Эта минимальная величина является наибольшей в точке М, следовательно, этой точке соответствует оптимальная стратегия U* = (,), а ее ордината равна цене игры v.

Координаты точки M найдем, как координаты точки пересечения прямых B1B"1 и B2B"2.

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

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

Прямая B1B"1: = или y = 4x + 2.

Прямая B2B"2: = или y = -x + 5.

Получим систему: y = 4x + 2,

Решим ее: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Таким образом, U = (2/5, 3/5), v = 22/5.

20. Биматричные игры.

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

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

21. Статистические игры. Принципы и критерии принятия решений в условиях полной и частичной неопределенности.

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

неопределенность целей;

неопределенность наших знаний об окружающей обстановке и действующих в данном явлении факторах (неопределенность природы);

неопределенность действий активного или пассивного партнера или противника.

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

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

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

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

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

Другим крайним случаем может быть неопределенность нестохастического вида (по выражению Е.С.Вентцель - "дурная неопределенность"), при которой никаких предположений о стохастической устойчивости не существует. Наконец, можно говорить о промежуточном типе неопределенности, когда решение принимается на основании каких-либо гипотез о законах распределения случайных величин. При этом ЛПР должен иметь в виду опасность несовпадения его результатов с реальными условиями. Эта опасность несовпадения формализуется с помощью коэффициентов риска.

Принятие решений в условиях риска может быть основано на одном из следующих критериев:

критерий ожидаемого значения;

комбинации ожидаемого значения и дисперсии;

известного предельного уровня;

наиболее вероятного события в будущем.

краткий курс

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

П. Конюховский

УЧЕБНОЕ ПОСОБИЕ

Санкт-Петербург

Москва Харьков Минск

Конюховский П. В.

Математические методы исследования операций в экономике

Серия «Краткий курс»

ББК22.183я7+65.529 УДК519.8(075)+658.012.122(075)

Конюховский П. В.

К65 Математические методы исследования операций в экономике - СПб.: Издательство «Питер», 2000. - 208 с. - (Серия «Краткийкурс»).

ISBN 5-8046-0190-3

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

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

ISBN 5-8046-0190-3

Издательство «Питер». 196105, С.-Петербург, Благодатная ул., 67. Лицензия ЛР № 066333 от 23.02.99.

Подписано к печати15.09.99. Формат 60х90/16. Усл. п. л. 13.

Тираж 5000. Заказ 4418.

Отпечатано с фотоформ в АООТ «Типография „Правда”».

119. С.-Петербург, Социалистическая ул., 14.

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

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

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

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

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

Несколько замечаний по используемым в ходе изложения условным обозначениям:

¨ базовые понятия предмета при их первом появлении в тексте выделяются курсивом , а наиболее важные их них (те, которые стоит не забывать и после прочтения!) - жирным шрифтом;

¨ перед фундаментальными определениями стоит символ -;

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

¨ доказательство теоремы завершается символом -.

Начало развития исследования операций как науки традиционно связывают с сороковыми годами двадцатого столетия. Среди первых исследований в данном направлении может быть названа работа Л. В. Канторовича «Математические методы организации и планирования производства», вышедшая в 1939 г. В зарубежной литературе отправной точкой обычно считается вышедшая в 1947 г. работа Дж. Данцига, посвященная решению линейных экстремальных задач.

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

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

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

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

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

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

4. Решение задач, сформулированных на базе построенной математической модели.

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

6. Реализация полученного решения на практике.

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

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

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

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

Частное образовательное учреждение высшего профессионального образования

«Курский институт менеджмента, экономики и бизнеса»

Аспирантура

Рабочая программа дисциплины

Исследование операций в экономике

Специальность: 08.00.05 «Экономика и управление народным хозяйством

(по отраслям и сферам деятельности)»

К. физ. мат..н.,

доцент, профессор МЭБИК

Курск – 2011

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к рабочей программе курса «Исследование операций в экономике»

Программа дисциплины «Исследование операций в экономике» отнесена к блоку факультативных дисциплин основной профессиональной образовательной программы послевузовского профессионального образования специальности 08.00.05 – Экономика и управление народным хозяйством.

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

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

Цель курса «Исследование операций в экономике»: способствовать овладению аспирантом методами исследования операций, вооружить его знаниями, умениями и навыками, позволяющими устанавливать связь между строгими математическими исследованиями, с одной стороны, и практическими задачами принятия решений – с другой.

Задачи курса «Исследование операций в экономике»:

способствовать пониманию основных идей, понятий и методов исследования операций;

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

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

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

В результате изучения дисциплины «Исследование операций в экономике»

аспирант должен знать :

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

методы решения задач целочисленного программирования;

методы решения транспортных задач»;

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

основы динамического программирования;

элементы теории стохастического программирования;

элементы теории игр;

основы теории массового обслуживания;

аспирант должен уметь :

строить математические модели задач линейного, целочисленного, нелинейного, динамического программирования;

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

решать задачи целочисленного программирования;

решать транспортные задачи;

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

решать задачи многошаговой оптимизации методом динамического программирования;

находить решение матричных игр.

ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ КУРСА

«Исследование операций в экономике»

Очная форма обучения

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

	Введение в исследование операций. Основы классической теории оптимизации







Итого
Форма итогового контроля	экзамен

КРАТКОЕ СОДЕРЖАНИЕ

курса «Исследование операций в экономике»

Тема 1. Введение в исследование операций. Основы классической теории оптимизации

Понятие операции. Цель и задачи исследования операций. Примеры задач исследования операций. Место дисциплины исследования операций среди смежных дисциплин. Введение в классическую теорию оптимизации. Основные понятия и определения: задача оптимизации, виды критериев и их свойства, оптимальное решение. Постановка задачи оптимизации. Типы оптимальных решений. Графическое решение. Понятие градиента и его геометрическая интерпретация. Множество допустимых решений. Этапы исследования операций. Классификация методов исследования операций. Типовые постановки задач, их геометрическая интерпретация и методы решения.

Тема 2. Безусловная одномерная оптимизация

Аналитический и графический анализ функции. Необходимые и достаточные условия экстремума. Процесс численного нахождения оптимального решения. Начальное приближение. Контроль точности. Классификация численных методов. Поисковые методы точечного оценивания: метод обратного переменного шага, квадратичной аппроксимации, метод Пауэлла. Методы последовательного сокращения отрезка неопределенности: равномерный поиск, метод локализации оптимума, половинного деления, золотого сечения, Фибоначчи. Сравнительный анализ одномерных методов сужения интервала.

Тема 3. Безусловная многомерная оптимизация

Аналитический и графический анализ функции. Общая идея численных методов. Методы оценки точности решения. Классификация численных методов. Поисковые методы переборного типа: сканирования с равномерным и переменным шагом. Методы на основе пошаговой одномерной оптимизации: поочередного изменения переменных, Гаусса - Зейделя, Хука-Дживса. Симплексные алгоритмы: обычный симплекс-метод, метод Нелдера-Мида. Методы случайного поиска: ненаправленный случайный поиск, метод случайных направлений. Многомерные методы оптимизации с использованием производных: градиентный, наискорейшего спуска (крутого восхождения). Сравнительный анализ многомерных методов оптимизации.

Тема 4. Модели и методы линейного программирования

Постановка и особенности задач условной оптимизации. Классификация и характеристика методов решения. Линейное программирование. Примеры построения линейных оптимизационных моделей: оптимальная смесь, оптимизация плана производства, распределение ресурсов, загрузка оборудования и др. Геометрическая интерпретация и графический метод решения. Графический анализ устойчивости решения задачи линейного программированиия. Каноническая форма задачи. Методы решения задач линейного программирования. Теоретическая основа симплекс-метода и алгоритм его реализации. Постановка и решение двойственной задачи линейного программирования. Двойственный симплекс-метод.

Тема 5. Специальные задачи линейного программирования

Целочисленная задача линейного программирования. Методы отсечения. Метод Гомори. Понятие о методе ветвей и границ. Постановка и методы решения транспортной задачи. Закрытая и открытая модель транспортной задачи. Задача о назначениях и выбора кратчайшего пути. Задача коммивояжера. Элементы теории игр. Основные понятия, классификация и описание игр. Матричные игры и понятие седловой точки. Смешанные стратегии. Решение матричных игр методами линейного программирования и графическим способом.

Тема 6. Условная оптимизация. Нелинейное программирование

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

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

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

Тема 8. Специальные модели исследования операций

Модели сетевого планирования и управления. Основные элементы сетевой модели. Порядок и правила построения сетевых графиков. Упорядочение и оптимизация сетевого графика. Модели управления запасами. Статические детерминированные модели. Управление запасами при случайном спросе и предложении.

ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ К ЗАЧЕТУ

по курсу «Исследование операций в экономике

Введение в исследование операций.
Основы классической теории оптимизации

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

2. Общая классификация численных методов классической безусловной оптимизации.

3. Постановки задач безусловной и условной оптимизации.

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

5. Понятие задачи выпуклого программирования. Необходимые и достаточные условия экстремума.

Безусловная одномерная оптимизация

6. Необходимые и достаточные условия экстремума функции одной переменной.

7. Классификация и основные идеи численных методов одномерной оптимизации.

8. Сравнительный анализ численных методов одномерной оптимизации.

Безусловная многомерная оптимизация

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

10. Методы покоординатного поиска экстремума функции нескольких переменных.

11. Симплексные методы поиска экстремума функции нескольких переменных.

12. Градиентные методы оптимизации.

13. Методы случайного поиска экстремума.

14. Методы случайных направлений

15. Сравнительный анализ численных методов многомерной оптимизации.

Условная оптимизация. Нелинейное программирование

16. Постановка задачи и классификация методов статической условной оптимизации.

17. Постановка задачи нелинейного программирования. Классические методы ее решения для системы ограничений в виде равенств.

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

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

Модели и методы линейного программирования

20. Постановка и методы решения задачи линейного программирования. Ее геометрическая и экономическая интерпретации.

21. Каноническая форма задачи линейного программирования. Симплексный метод ее решения.

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

Специальные задачи линейного программирования

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

24. Транспортная задача линейного программирования. Постановка и методы решения.

25. Теория игр. Основные понятия, классификация и описание игр.

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

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

27. Геометрическая и экономическая интерпретации задачи.

Специальные модели исследования операций

28. Сетевые модели планирования и управления.

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

30. Модели управления запасами в детерминированной постановке.

31. Модели управления запасами в стохастической постановке.

ЛИТЕРАТУРА

по курсу «Исследование операций в экономике»

Основная литература

1. , Коробко методы и модели для менеджмента. – СПб: Лань, 2007 г.

2. Исследование операций в экономике: Учебное пособие для вузов / Под ред. . - М.: ЮНИТИ, 20с. - Гриф МО РФ

3. Стронгин операций. Курс лекций. –М: Интуит, 2006 г.

Дополнительная литература

1. Вентцель операций.- М.: Высшая школа, 2001.

2. , Загоруйко операций: Учеб. для вузов/ Под ред. , Изд-во МГТУ им. , 200с.

3. Исследование операций в экономике /, ; Под ред. проф..- М.: ЮНИТИ, 200c.

4. Конюховский методы исследования операций в экономике.- СПб: Питер, 2000.-208 с.

5. , Костевич к решению задач по математическому программированию.- Мн.: Выш. шк., 2001.

6. , Летова оптимизации в примерах и задачах: Учеб. пособие.- М.: Высш. шк., 200с.

7. , Волоценко программирование. –М: Высшая школа, 1990 г.

8. Таха Х. Введение в исследование операций. –М: Мир, 1985 г.

9. исследование операций в задачах, алгоритмах, программах. –М: Радио и связь, 1984 г.

10. , Шахдинаров и модели управления фирмой. –СПб: Питер, 2001 г.

КАЛЕНДАРНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ

ПРАКТИЧЕСКИХ ЗАНЯТИЙ

по дисциплине «Исследование операций в экономике»

	Тема практического занятия
	Типовые постановки задач оптимизации, их геометрическая интерпретация и методы решения. Типы оптимальных решений. Графическое решение. Понятие градиента и его геометрическая интерпретация. Множество допустимых решений. Этапы исследования операций. Классификация методов исследования операций.
	Классификация численных методов. Поисковые методы точечного оценивания: метод обратного переменного шага, квадратичной аппроксимации, метод Пауэлла. Методы последовательного сокращения отрезка неопределенности: равномерный поиск, метод локализации оптимума, половинного деления, золотого сечения, Фибоначчи.
	Классификация численных методов. Поисковые методы переборного типа: сканирования с равномерным и переменным шагом. Методы на основе пошаговой одномерной оптимизации: поочередного изменения переменных, Гаусса - Зейделя, Хука-Дживса. Симплексные алгоритмы: обычный симплекс-метод, метод Нелдера-Мида. Методы случайного поиска: ненаправленный случайный поиск, метод случайных направлений. Многомерные методы оптимизации с использованием производных: градиентный, наискорейшего спуска (крутого восхождения).
	Примеры построения линейных оптимизационных моделей: оптимальная смесь, оптимизация плана производства, распределение ресурсов, загрузка оборудования и др. Геометрическая интерпретация и графический метод решения. Графический анализ устойчивости решения задачи линейного программирования.
	Постановка и методы решения транспортной задачи. Закрытая и открытая модель транспортной задачи. Задача о назначениях и выбора кратчайшего пути. Задача коммивояжера.
	Основные понятия, классификация и описание игр. Матричные игры и понятие седловой точки. Смешанные стратегии. Решение матричных игр методами линейного программирования и графическим способом.
	Постановка и геометрическая интерпретация задачи нелинейного программирования. Графический метод решения для функции двух переменных. Классические методы решения с ограничениями типа равенств: метод исключения, метод множителей Лагранжа. Неклассические методы решения с ограничениями типа неравенств. Необходимые и достаточные условия Куна - Таккера для условного экстремума.
	Примеры задач динамического программирования. Принцип оптимальности и уравнение Беллмана. Задача о распределении средств между предприятиями. Общая схема применения метода динамического программирования. Задача о замене оборудования.
	Порядок и правила построения сетевых графиков. Упорядочение и оптимизация сетевого графика. Модели управления запасами. Статические детерминированные модели. Управление запасами при случайном спросе и предложении.

Биткойн задумывался разработчиками как «электронный кэш», однако криптовалюта не оправдала надежд. В качестве средства накопления она не состоялась, а расплачиваться BTC за товары и услуги слишком неудобно. К таким заключениям пришел управляющий Банка Англии Марк Карни во время встречи со студентами Лондонского университета Риджентс.

Глава Банка Англии Марк Карни пополнил список скептиков, которые выступают против криптовалют. На встрече со студентами Лондонского университета Риджентс управляющий банка признал биткойн провальным проектом. «С точки зрения традиционных денег биткойн провалился. Его нельзя использовать как средство накопления из-за постоянных колебаний. И никто не пользуется им как средством обмена», - цитирует Reuters Карни.

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

Предприятие 1

Предприятие 2

Предприятие 3

1. Регистрация предприятия

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

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