Задачи принятия решений

Экономический факультет

Кафедра экономической информатики

                                 В.С. Громницкий

Методы оптимизации

Курс лекций

 

 

Записано и оформлено выпускницей экономического факультета
Андреевой Екатериной Павловной

 

 

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

Нижний Новгород

2010

 

УДК 65.012.122 (075,8)

ББК Ув6я73

Г 87

 

 

Г87 Громницкий В.С. Методы оптимизации. Курс лекций: Учебное пособие – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2010. – 104 с.

 

 

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

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

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

 

 

Рецензент: доцент, к.э.н. Пчелинцев Александр Дмитриевич

 

ББК Ув6я73

 

 

© Громницкий В.С., 2010

            © Нижегородский государственный

                      университет им. Н.И. Лобачевского, 2010

Содержание

Введение. 4

Задачи принятия решений. 5

Математическое моделирование. 7

Часть I. Линейное программирование.. 9

Глава 1. Линейные математические модели в экономических исследованиях.. 9

1.1. Экономические задачи. 9

1.2. Общий вид математической модели задачи линейного программирования. 11

1.3. Различные формы задач линейного программирования. 12

1.4. Графическое решение задач. 17

Глава 2. Математические свойства задачи линейного программирования. 20

2.1. Свойства области допустимых решений. 20

2.2. Базисные и опорные решения. 22

Глава 3. Симплекс-метод решения задачи линейного программирования. 24

3.1. Идея симплекс-метода. 24

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

3.3. Симплекс-метод в уравнениях. 26

3.4. Симплекс-метод в таблицах. 29

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

3.6. Предупреждение зацикливания симплекс-метода. 34

Глава 4. Метод искусственного базиса.. 35

4.1. Построение начального опорного плана. 35

4.2. Решение задачи линейного программирования методом искусственного базиса. 38

Глава 5. Теория двойственности в задачах линейного программирования. 40

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

5.2. Математические свойства пары взаимно двойственных задач. 43

5.3. Анализ чувствительности оптимального решения к изменению свободных членов ограничений. 51

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

5.5. Двойственный симплексный метод. 61

Глава 6. Послеоптимизационный анализ задачи линейного программирования. 66

6.1. Добавление нового ограничения. 67

6.2. Добавление новой переменной. 69

6.3. Изменение коэффициентов критерия. 71

6.4. Изменение технологических коэффициентов. 74

Часть II. Методы нелинейной оптимизации.. 77

Глава 7. Классическая теория оптимизации.. 77

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

7.2. Достаточные условия оптимальности. 78

Глава 8. Нелинейное программирование. 81

8.1. Задачи на условный экстремум. Метод множителей Лагранжа. 81

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

8.3. Задачи квадратичного программирования. 86

Задания к лабораторным работам.. 91

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

Лабораторная работа 2. Симплекс-метод. Варианты разрешимости задачи линейного программирования. 91

Лабораторная работа 3. Теория двойственности в задачах линейного программирования. 92

Лабораторная работа 4. Послеоптимизационный анализ задач линейного программирования. 92

Перечень задач к лабораторным работам 3 и 4. 94

Литература.. 109

Введение

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

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

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

Система – совокупность взаимосвязанных элементов. Она описывается некоторыми параметрами, среди которых выделяют исходные (), управляемые
(A, B, C…) и выходные (). Задача анализа системы ставится как задача принятия решений, то есть задача выбора таких управляемых параметров, которые обеспечивают наилучшие показатели деятельности системы. Цели функционирования системы могут быть разные и обычно формулируются постановщиком задачи, лицом принимающим решения.

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

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

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

 

Задачи принятия решений

Исследование операций включает в себя целый ряд научных дисциплин, отличающихся целями и методами принимаемых решений:

·

(1)     (2)

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

 

 где   

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

· Линейное программирование.  Задача линейного программирования – это задача математического программирования (1–2), в которой целевая функция и функции ограничений линейные. Для таких задач разработаны точные методы решений.

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

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

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

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

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

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

· Задачи динамического программирования – задачи, в которых применяются пошаговые методы решения.

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

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

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

· Теория управления запасами изучает задачи определения объемов поставки  и сроков хранения продукции.

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

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

· Имитационное моделирование – моделирование систем с помощью электронной вычислительной техники.

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