Белорусский государственный университет

(название высшего учебного заведения)

УТВЕРЖДАЮ

Декан экономического факультета

М.М. Ковалев

(подпись) « 25 » июня 2009г.

(дата утверждения) Регистрационный № УД- 86 /р.

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

Учебная программа для специальности:

1-25 01 02 экономика 1-25 01 01 экономическая теория Факультет экономический Кафедра _экономической информатики и математической экономики Курс (курсы) Семестр (семестры) _ Лекции _56 Экзамен 4_ (количество часов) (семестр) Практические (семинарские) занятия 26 Зачет _-- (количество часов) (семестр) КСР Курсовой проект (работа) _--_ Всего аудиторных часов по дисциплине _106_ (количество часов) Всего часов Форма получения по дисциплине _230 высшего образования очная (количество часов) Составил к.э.н., доцент Писарук Н.Н.

2010 г.

Учебная программа составлена на основе Исследование операций: Учеб. программа для высших учебных заведений для специальностей 1-25 01 02 Экономика Утверждена Учебно-методическим объединением вну Республики Беларусь по гуманитарному образованию xx 2010 г. Регистрационный № /тип.

№ ТД-Г.117/тип.

Рассмотрена и рекомендована к утверждению на заседании кафедры экономической информатики и математической экономики 17 июня 2009 г., протокол № Зав. кафедрой М.М. Ковалев Одобрена и рекомендована к утверждению Учебно-методической комиссией экономического факультета Белорусского государственного университета 25 июня 2009 г., протокол № Председатель Е. Э. Васильева

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

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

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

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

Программа курса «Исследование операций» адресована студентам экономических специальностей Республики Беларусь, составлена в соотвестсвии с требованиями общеобразовательного стандарта (106 а/ч – по специальности 1-25 01 02 – «Экономика»).

Учебная программа курса

НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

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

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

задача выпуклого программирования.

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

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

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

КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ

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

СМЕШАННО-ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

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

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

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

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

СЕТЕВАЯ ОПТИМИЗАЦИЯ

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

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

ЗАДАЧИ С НЕОПРЕДЕЛЕННЫМИ ПАРАМЕТРАМИ

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

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

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

УЧЕБНО-МЕТОДИЧЕСКАЯ КАРТА

ВВЕДЕНИЕ

Предмет исследования операций Общая задача исследования операций, неопределенные) факторы. Разделы исследования

НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

Геометрическая интерпретация условий Куна-Таккера.

Решение задач методом множителей Куна-Таккера.

Неоклассическая задача потребления.

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

Связь с условиями Куна-Таккера в дифференцируемом выпуклом случае.

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

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

Примеры приложений.

метод DEA оценки работы сервистных подразделений.

3) Краткосрочный финансовый менеджмент.

4) Марковские процессы принятия решений.

Транспортная задача.

КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ

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

Примеры приложений.

1) Модель Марковица оптимизации портфеля.

Целочисленность и нелинейность.

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

5.2. методом ветвей и границ.

Примеры приложений.

3) Размещение центров обслуживания и модель оптимизации портфеля «индексеый фонд».

4) Задачи теории расписаний.

6.1. Метод динамического программирования Типы графов. Кратчайшие пути.

Задача о максимальном потоке.

Календарное планирование.

Сетевая транспортная задача.

ЗАДАЧИ С НЕОПРЕДЕЛЕННЫМИ

ПАРАМЕТРАМИ

Стохастическое программирование.

оптимизации портфеля «исскуственный опцион».

Понятие о робастной оптимизации.

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

ЛИТЕРАТУРА

1. Вагнер Г. Основы исследования операций (в 3-х томах). — М.: Мир, 1972-1973.

2. Интрилигатор М. Математические методы оптимизации и экономическая теория.М.: Айрис Пресс, 2002.

3. Исследование операций. Т. 1. Методологические основы и математические методы. Т. 2. Модели и применения. Под ред.

Дж. Моудера, С. Элмаграби. — М.: Мир, 1981.

4. Карманов В. Г. Математическое программирование. — М.: Наука, 1975.

Костевич Л. С. Математическое программирование: Информационные технологии оптимальных решений. — Мн. : ООО "Новое знание", 2003.

5. Мину М. Математическое программирование. — М.: Наука, 1990.

6. Писарук Н. Н. Модели и методы смешанно-целочисленного программирования. — Изд-во БГУ, 2010.

7. Сакович В.А. Исследование операций. — Мн.: Вышэйшая школа, 1985.

8. Таха Х. Введение в исследование операций. В 2-х кн. — M.: Мир, 1985.

9. Филлипс Д., А. Гарсиа-Диас. Методы анализа сетей. — М.: Мир, 1984.

10. Birge J.R., F.V. Louveaux. Introduction to stochastic programming. Springer Verlag, New York, 1997.