Фэу — факультет экономики и управления. Шпаргалка: Шпаргалка по Исследованию операций в экономике
В учебном пособии представлены модели линейного и целочисленного программирования, классические методы оптимизации, задачи выпуклого и динамического программирования, модели управления запасами и сетевого планирования и управления, элементы теории игр и массового обслуживания. Рассмотрены некоторые вопросы применения ЭВМ для решения задач математического программирования. Приводится большое количество экономических задач с решениями и для самостоятельной работы. Для студентов экономических вузов, экономистов и лиц, занимающихся самообразованием
Раздел I Модели линейного ПРОГРАММИРОВАНИЯ И ЕГО ПРИЛОЖЕНИЯ
Глава 1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Глава 2. ЭЛЕМЕНТЫ ЛИНЕЙНОЙ АЛГЕБРЫ И ГЕОМЕТРИИ ВЫПУКЛЫХ МНОЖЕСТВ 2.1.
Глава 3. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Глава 4. ГЕОМЕТРИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Глава 8. МОДЕЛИ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Раздел II Модели нелинейного ПРОГРАММИРОВАНИЯ
Глава 10. КЛАССИЧЕСКИЕ МЕТОДЫ ОПТИМИЗАЦИИ
Глава 11. МОДЕЛИ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ 11.1.
Глава 12. МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Раздел III Специальные модели ИССЛЕДОВАНИЯ ОПЕРАЦИЙ
Глава 14. МОДЕЛИ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ 14.1.
Глава 15. ЭЛЕМЕНТЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ
Глава 16. МОДЕЛИ УПРАВЛЕНИЯ ЗАПАСАМИ 16.1.
Частное образовательное учреждение высшего профессионального образования
«Курский институт менеджмента, экономики и бизнеса»
Аспирантура
Рабочая программа дисциплины
Исследование операций в экономике
Специальность: 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 г.
КАЛЕНДАРНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ
ПРАКТИЧЕСКИХ ЗАНЯТИЙ
по дисциплине «Исследование операций в экономике»
Типовые постановки задач оптимизации, их геометрическая интерпретация и методы решения. Типы оптимальных решений. Графическое решение. Понятие градиента и его геометрическая интерпретация. Множество допустимых решений. Этапы исследования операций. Классификация методов исследования операций. | ||
Классификация численных методов. Поисковые методы точечного оценивания: метод обратного переменного шага, квадратичной аппроксимации, метод Пауэлла. Методы последовательного сокращения отрезка неопределенности: равномерный поиск, метод локализации оптимума, половинного деления, золотого сечения, Фибоначчи. | ||
Классификация численных методов. Поисковые методы переборного типа: сканирования с равномерным и переменным шагом. Методы на основе пошаговой одномерной оптимизации: поочередного изменения переменных, Гаусса - Зейделя, Хука-Дживса. Симплексные алгоритмы: обычный симплекс-метод, метод Нелдера-Мида. Методы случайного поиска: ненаправленный случайный поиск, метод случайных направлений. Многомерные методы оптимизации с использованием производных: градиентный, наискорейшего спуска (крутого восхождения). | ||
Примеры построения линейных оптимизационных моделей: оптимальная смесь, оптимизация плана производства, распределение ресурсов, загрузка оборудования и др. Геометрическая интерпретация и графический метод решения. Графический анализ устойчивости решения задачи линейного программирования. | ||
Постановка и методы решения транспортной задачи. Закрытая и открытая модель транспортной задачи. Задача о назначениях и выбора кратчайшего пути. Задача коммивояжера. | ||
Основные понятия, классификация и описание игр. Матричные игры и понятие седловой точки. Смешанные стратегии. Решение матричных игр методами линейного программирования и графическим способом. | ||
Постановка и геометрическая интерпретация задачи нелинейного программирования. Графический метод решения для функции двух переменных. Классические методы решения с ограничениями типа равенств: метод исключения, метод множителей Лагранжа. Неклассические методы решения с ограничениями типа неравенств. Необходимые и достаточные условия Куна - Таккера для условного экстремума. | ||
Примеры задач динамического программирования. Принцип оптимальности и уравнение Беллмана. Задача о распределении средств между предприятиями. Общая схема применения метода динамического программирования. Задача о замене оборудования. | ||
Порядок и правила построения сетевых графиков. Упорядочение и оптимизация сетевого графика. Модели управления запасами. Статические детерминированные модели. Управление запасами при случайном спросе и предложении. |
1. Предмет и задачи исследования операций в экономике. Основные понятия теории исследования операций.
Предмет исследования операций - системы организационного управления или организации, которые состоят из большого числа взаимодействующих между собой подразделений не всегда согласующихся между собой и могут быть противоположны.
Цель исследования операций - количественное обоснование принимаемых решений по управлению организациями
Решение, которое оказывается наиболее выгодным для всей организации называется оптимальным, а решение наиболее выгодное одному или нескольким подразделениям будет субоптимальным.
Исследование операций - наука, занимающаяся разработкой и практическим применением методов наиболее оптимального управления организационными системами.
Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.
Цель исследования операций - предварительное количественное обоснование оптимальных решений.
Всякий определенный выбор зависящих от нас параметров называется решением. Оптимальным называются решения, по тем или другим признакам предпочтительные перед другими.
Параметры, совокупность которых образует решение, называются элементами решения.
Множеством допустимых решений называются заданные условия, которые фиксированы и не могут быть нарушены.
Показатель эффективности - количественная мера, позволяющая сравнивать разные решения по эффективности.
2. Понятие о сетевом планировании и управлении. Сетевая модель процесса и ее элементы.
Метод работы с сетевыми графиками – сетевое планирование – базируется на теории графов. В переводе с греческого граф (grafpho – пишу) представляет систему точек, некоторые из них соединены линиями – дугами (или ребрами). Это топологическая (математическая) модель взаимодействующих систем. С помощью графов можно решать не только задачи сетевого планирования, но и другие задачи. Метод сетевого планирования применяется при планировании проведения комплекса взаимосвязанных работ. Он позволяет наглядно представить организационно-технологическую последовательность выполнения работ и установить взаимосвязь между ними. Кроме этого, он позволяет обеспечить координацию операций различной степени сложности и выявить операции, от которых зависит продолжительность всей работы (т.е. организационного мероприятия), а также сосредоточить внимание на своевременном выполнении каждой операции.
Основой сетевого планирования и управления является сетевая модель (СМ), в которой моделируется совокупность взаимосвязанных работ и событий, отображающих процесс достижения определенной цели. Она может быть представлена в виде графика или таблицы.
Основные понятия сетевой модели:
Событие, работа, путь.
Событиями называются результаты выполнения одной или нескольких работ. Они не имеют протяженности во времени.
Путь - это цепочка следующих друг за другом работ, соединяющих начальную и конечную вершины.
Продолжительность пути определяется суммой продолжительностей составляющих его работ.
3. Построение и упорядочивание сетевого графика.
В качестве модели, отражающей технологические и организационные взаимосвязи процесса производства строительно-монтажных работ в системах сетевого планирования и управления (СПУ), используется сетевая модель.
Сетевой моделью называется графическое изображение процессов, выполнение которых приводит к достижению одной или нескольких поставленных целей, с указанием установленных взаимосвязей между этими процессами. Сетевой график представляет собой сетевую модель с расчетными временными параметрами.
Структура сетевого графика, определяющая взаимную зависимость работ и событий, называется его топологией.
Работа - это производственный процесс, требующий затрат времени, труда и материальных ресурсов, который при его выполнении приводит к достижению определенных результатов.
Зависимость (фиктивная работа), не требующая затрат времени изображается пунктирной стрелкой. Фиктивная работа используется в сетевом графике для отражения связей между событиями и работами.
В сетевом графике применяются временные, стоимостные и другие характеристики работ.
Продолжительной работы – время выполнения данной работы в рабочих днях или других единицах времени, одинаковых для всех работ сетевого графика. Продолжительность работ может быть как определенной (детерминированной), так и случайной величиной, задаваемой законом ее распределения.
Стоимость работы – это прямые затраты, необходимые для ее выполнения, зависящие от длительности и условий выполнения этой работы.
Ресурсы характеризуются потребностью в физических единицах, необходимых для выполнения данной работы.
Качество, надежность и другие показатели работ служат дополнительными характеристиками работ.
Событие - это факт окончания одной или нескольких работ, необходимый и достаточный для начала одной или нескольких последующих работ. Каждому событию присваивается номер, называемый кодом. Каждая работа определяется двумя событиями: кодом начального события, обозначаемого i и кодом конечного события, обозначаемого буквой j.
События, не имеющие предшествующих работ, называются начальными; события, не имеющие последующих – конечными.
1 Направление построения сети может иметь различный характер. Сетевой график может строиться от начального события к завершающему и от завершающего к исходному (начальному), а также от любого из событий к исходному или конечному.
2 При построении сети решаются вопросы:
Какие работы (работу) необходимо выполнить, чтобы начать данную работу;
Какие работы целесообразно выполнять параллельно с данной работой;
3 Первоначальный сетевой график строится без учета продолжительности работ, составляющих сеть.
4 Форма графика должна быть простой и зрительно легко воспринимаемой.
5 Между двумя событиями может заключаться только одна работа. При строительстве зданий и сооружений работы могут выполняться последовательно, параллельно или одновременно, часть последовательно, а часть параллельно, в результате чего между отдельными работами складываются различные зависимости.
Нумерация (кодирование) событий производится после окончания построения сети, начиная от исходного события до конечного.
4. Критический путь сетевого графика. Резервы времени. Ранние и поздние сроки событий и работ в сетевом графике.
В сетевом графике между начальным и конечным событиями может быть несколько путей. Путь, имеющий наибольшую продолжительность, называется критическим. Критический путь определяет общую продолжительность работ. Все остальные пути имеют меньшую продолжительность, и поэтому в них выполняемое работы имеют резервы времени.
Критический путь обозначается на сетевом графике утолщенными или двойными линиями (стрелками).
Особое значение при составлении сетевого графика имеют два понятия:
Раннее начало работы - срок, раньше которого нельзя начать данную работу, не нарушив принятой технологической последовательности. Он определяется наиболее долгим путем от исходного события до начала данной работы
Позднее окончание работы - самый поздний срок окончания работы, при котором не увеличивается общая продолжительность работ. Он определяется самым коротким путем от данного события до завершения всех работ.
Раннее окончание - срок, раньше которого нельзя закончить данную работу. Он равен раннему началу плюс продолжительность данной работы
Позднее начало - срок, позже которого нельзя начинать данную работу, не увеличив общую продолжительность строительства. Он равен позднему окончанию минус продолжительность данной работы.
Если событие является окончанием лишь одной работы (т.е. в него направлена только одна стрелка), то раннее окончание этой работы совпадает с ранним началом последующей.
Общий (полный) резерв - это наибольшее время, на которое можно задержать выполнение данной работы, не увеличивая общую продолжительность работ. Он определяется разностью между поздним и ранним началом (или поздним и ранним окончанием - что то же самое).
Частный (свободный) резерв - это наибольшее время, на которое можно задержать выполнение данной работы, не меняя раннего начала последующей. Этот резерв возможен только тогда, когда в событие входят две или более работы (зависимости), т.е. на него направлены две или более стрелки (сплошные или пунктирные). Тогда лишь у одной из этих работ раннее окончание будет совпадать с ранним началом последующей работы, для остальных же это будут разные значения. Эта разница у каждой работы и будет ее частным резервом.
5. Динамическое программирование. Принцип оптимальности и управления Беллмана.
Динамическое программирование – один из наиболее мощных методов оптимизации. С задачами принятия рациональных решений, выбора наилучших вариантов, оптимального управления имеют дело специалисты разного профиля. Среди методов оптимизации динамическое программирование занимает особое положение. Этот метод исключительно привлекателен благодаря простоте и ясности своего основного принципа – принципа оптимальности. Сфера приложения принципа оптимальности чрезвычайно широка, круг задач, к которым он может быть применен, до настоящего времени еще полностью не очерчен. Динамическое программирование с самого начала выступает как средство практического решения задач оптимизации.
Кроме принципа оптимальности, основного приема исследования, большую роль в аппарате динамического программирования играет идея погружения конкретной задачи оптимизации в семейство аналогичных задач. Третьей его особенностью, выделяющей его среди других методов оптимизации, является форма конечного результата. Применение принципа оптимальности и принципа погружения в многошаговых, дискретных процессах приводят к рекуррентно-функцио-нальным уравнениям относительно оптимального значения критерия качества. Полученные уравнения позволяют последовательно выписать оптимальные управления для исходной задачи. Выигрыш здесь состоит в том, что задача вычисления управления для всего процесса разбивается на ряд более простых задач вычисления управления для отдельных этапов процесса.
Главным недостатком метода является, говоря словами Беллмана, «проклятие размерности» – его сложность катастрофически возрастает с увеличением размерности задачи.
6. Задача о распределении средств между предприятиями.
Можно сказать, что процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную и окончательную. На предварительной стадии для каждого шага определяется УОУ зависящее от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация - также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.
КУРСОВОЙ ПРОЕКТ
Исследование операций в экономике
Введение
Графическое решение задач линейного программирования
Решение задач линейного программирования симплекс-методом
Транспортная задача
Задача о назначениях
Задача о ранце
Заключение
Литература
Введение
Успешная реализация достижений научно-технического прогресса в нашей стране тесным образом связана с использованием экономико-математических методов и средств вычислительной техники при решении задач из различных областей человеческой деятельности. Исключительно важное значение приобретает использование указанных методов и средств при решении экономических задач.
Управление и планирование являются наиболее сложными функциями администрации предприятий, менеджеров, руководителей хозяйственных органов и штабов различного уровня. Характер управления и планирования определяет путь достижения цели и оказывает существенное влияние на качество решения поставленной задачи. В современных условиях повышается ответственность за качество принимаемых управленческих решений. Несколько неудачных управленческих решений и предприятие вступает в стадию банкротства.
В настоящее время существует две группы методов принятия управленческих решений:
) логический (когда решение принимается на основании опыта, интуиции и других личностных качеств лица, принимающего решение);
) формально-логический или формализованный (когда решение принимается на основе изучения предварительно-построенной модели). При этом появляется возможность оценить последствия каждого из вариантов и выбрать наилучший по некоторому критерию. В этой группе методов важную роль играют экономико-математические модели.
Образ реальной действительности, в котором отражены характерные для изучаемого явления признаки или черты реального объекта (оригинала), именуют моделью, а сам процесс построения моделей называют моделированием.
Использование цифровых и знаковых символов позволяет создать категорию моделей, которая включает формально-логические и математические модели.
Любое управление в экономике связано с выработкой и принятием управленческих решений, воплощающихся в управленческие воздействия. Субъекты управления стремятся определить последствия определённого решения. Прежде чем осуществлять управляющее воздействие, принимать окончательное решение, желательно проверить его действенность, послед-ствия, результат. При этом фактически используются логические модели процессов управления, мысленные сценарии их протекания. Но возможности даже квалифицированного, опытного специалиста воспроизвести в своём мозгу картину поведения объекта управления под влиянием управляющих воздействий довольно ограничены. Приходится прибегать к помощи математических расчётов, дополняющих мысленные представления, иллюстрирующих ожидаемую картину управляемого процесса в виде цифр, кривых, графиков, таблиц. Использование математических методов при формировании представлений об экономических объектах и процессах в ходе экономического анализа, прогнозирования, планирования называют применением экономико-математических методов.
Наиболее распространённая форма, основной инструмент воплощения экономико-математических методов - это экономико-математическое моделирование. Математическое моделирование опирается на математическое описание моделируемого объекта (процесса) в виде формул, зависимостей с помощью математических символов, знаков.
Экономико-математическая модель представляет собой формализованное описание управляемого экономического объекта (процесса), включающее заранее заданные параметры, показатели и искомые неизвестные величины, характеризующие состояние объекта, его функционирование, объединённые между собой связями в виде математических зависимостей, соотношений, формул. Модель способна быть только аналогом моделируемой системы, отражающим основные, существенные свойства изучаемой управляемой системы, которые наиболее важны с позиций управления.
Благодаря моделированию субъект управления способен в ходе анализа иметь дело не с реальным объектом управления, а с его аналогом в виде модели. Это значительно расширяет возможности поиска лучших способов управления, не нарушая функционирования реального объекта управления в период выработки управленческих решений. Появляется возможность применить вычислительную технику, использовать компьютеры, для которых математический язык моделей является самым удобным. Благодаря компьютерам можно производить многовариантные модельные расчёты, что повышает шансы на отыскание лучших вариантов.
Для того чтобы принять обоснованное решение необходимо получить и обработать огромное количество информации. Ответственные управленческие решения зачастую связаны с судьбами людей, принимающих их, и с большими материальными ценностями. Но сейчас недостаточно указать путь, ведущий к достижению цели. Необходимо из всех возможных путей выбрать наиболее экономный, учитывающий особенности течения и развития управляемого процесса и наилучшим образом соответствующий поставленной задаче.
Процесс управления производственной системой представляет собой процесс принятия решений, что всегда связано с выбором из множества возможных решений, допускаемых обстоятельствами решаемой задачи, то есть имеется множественность имеющихся вариантов. Выбранное решение должно соответствовать некоторому критерию целесообразности. Этим объясняется связь задач принятия управленческих решений с методами теории оптимизации.
В процессе выработки решений приходится формализовать зависимость между отдельными элементами системы, применять математический аппарат, общие кибернетические принципы и закономерности, то есть использовать экономико-математические методы.
Известно, что экономический эффект от рациональных методов управления и планирования, применяемых в широких масштабах и на высоком уровне, способен в ряде случаев повысить эффект от существенного увеличения мощностей. Возникает потребность в новых математических методах, позволяющих анализировать ритм производства, взаимоотношения между людьми и между коллективами.
Математические машины, внедряемые в производство и управление и используемые в научно-исследовательской работе, создают огромные возможности для развития различных отраслей науки, для совершенствования методов планирования и автоматизации производства. Однако без строгих формулировок задач, без формально-математического описания процессов не может быть достигнут необходимый уровень использования техники. Возникают вопросы, связанные с формализацией физических, экономических, технических и других процессов. Формализация задачи - необходимый этап для перевода каждой прикладной экономической задачи на язык математических машин.
Для постановки задачи математического программирования необходимо сформулировать цель управления и указать ограничения на выбор параметров управления, обусловленные особенностями управляемого процесса. Задача математического программирования сводится к выбору системы параметров, обеспечивающей оптимальное (в заданном смысле) качество процесса управления в рамках сформулированных ограничений.
Всё вышесказанное доказывает необходимость применения экономико-математических методов и моделей в управлении для принятия обоснованных управленческих решений.
В данной курсовой работе даётся представление о возможностях практического использования математического программирования и экономико-математических методов при решении конкретных экономических задач.
.Графическое решение задач линейного программирования.
Решить графически задачу 4x1+x2 → max,
при следующих ограничениях:
x1+7x2≤140
x1+10x2≤150
x1+20x2≤100
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F = 4x1+x2 → max.
Построим прямую, отвечающую значению функции F = 0: F = 4x1+x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Область допустимых решений представляет собой многоугольник Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
x1+7x2=140
x1+20x2=100
Решив систему уравнений, получим: x1 = 5.7534, x2 = 3.5616
Откуда найдем максимальное значение целевой функции: (X) = 4*5.7534 + 1*3.5616 = 26.5753
2. Решение задач линейного программирования симплекс - методом.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 5x1 + 5x2 + 11x3+9 при следующих условиях-ограничений.
При вычислениях значение Fc = 9 временно не учитываем. линейный программирование математический экономический x1 + x2 + x3 + x4≤0
x1 + 5x2 + 3x3 + 2x4≤0
x1 + 5x2 + 10x3 + 15x4≤0
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7.
x1 + 1x2 + 1x3 + 1x4 + 1x5 + 0x6 + 0x7 = 0
x1 + 5x2 + 3x3 + 2x4 + 0x5 + 1x6 + 0x7 = 0
x1 + 5x2 + 10x3 + 15x4 + 0x5 + 0x6 + 1x7 = 0
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
11111007532010351015001 Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x5, x6, x7
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,0,0,0) Базисное решение называется допустимым, если оно неотрицательно.
БазисBx1x2x3x4x5x6x7x501111100x607532010x70351015001F(X0)0-5-5-110000
Переходим к основному алгоритму симплекс-метода. Итерация №0. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:(0: 1, 0: 3, 0: 10) = 0 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
БазисBx1x2x3x4x5x6x7minx5011111000x6075320100x703510150010F(X1)0-5-5-1100000
Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:
Bx 1x 2x 3x 4x 5x 6x 70: 11: 11: 11: 11: 11: 10: 10: 10-(0 3):17-(1 3):15-(1 3):13-(1 3):12-(1 3):10-(1 3):11-(0 3):10-(0 3):10-(0 10):13-(1 10):15-(1 10):110-(1 10):115-(1 10):10-(1 10):10-(0 10):11-(0 10):10-(0 -11):1-5-(1 -11):1-5-(1 -11):1-11-(1 -11):10-(1 -11):10-(1 -11):10-(0 -11):10-(0 -11):1
Получаем новую симплекс-таблицу: