Методы оптимизации Курс лекций



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

Государственное образовательное учреждение

высшего профессионального образования

«Нижегородский государственный университет им. Н.И. Лобачевского»

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

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

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

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

Курс лекций

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

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

2010

УДК 65.012.122 (075.8)

ББК Ув6я73

Г 87

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

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

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

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

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

ББК Ув6я73

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

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

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

Содержание

Введение

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

В материальном моделировании можно выделить три группы методов: пространственное, физическое и аналоговое

Пространственное  моделирование изучает геометрические свойства объекта (макеты, карты, глобус).

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

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

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

Методы идеального моделирования можно разбить на две группы: формализованное (знаковое) и неформализованное (интуитивное) моделирование.

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

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

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

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

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

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

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

  1. Задача объемного планирования
    1. Содержательное описание

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

  1. Математическая модель

2.1.Исходные параметры

– количество видов продукции

– количество типов ресурсов

– запасы ресурсов каждого вида

– нормы расходаi-го ресурса на единицуj-ой продукции

– доход от единицыj-ой продукции

2.2.Управляемые параметры (варьируемые параметры)

– объемы производства каждого вида продукции

– вектор управляемых параметров (решение, допустимое решение – план)

2.3.Ограничения модели

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

Пусть –  расходi-го ресурса на произвольном плане .

  1. Формулировка цели принятия решений

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

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

,

на котором достигается наибольшее значение критерия

при условии

  1. Задача о диете
    1. Содержательное описание

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

  1. Математическая модель

2.1.Исходные параметры

– количество видов продукта

– количество контролируемых питательных веществ

– нормы потребления каждого питательного вещества (нижние границы)

– содержаниеi-го питательного вещества в единицеj-го продукта

– цена каждого продукта

2.2.Управляемые параметры (варьируемые параметры)

– объем закупок каждого продукта

– вектор управляемых параметров (решение, план закупок или рацион)

2.3.Ограничения модели

Пусть– содержаниеi-го питательного вещества в произвольном рационе .

Нужно выбрать наилучшее решение.

  1. Формулировка цели принятия решений

Сформулируем критерий оптимальности. Пусть – стоимость произвольного рациона . Требуется найти рацион наименьшей стоимости

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

,

на котором достигается наименьшее значение критерия

при условии

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

В общем виде задача линейного программирования ставится следующим образом:

Найти набор управляемых параметров

,

на  котором достигается наибольшее (наименьшее) значение показателя эффективности

при выполнении ограничений

и на некоторые переменные накладываются условия неотрицательности

Функция (7) называется целевой функцией или критерием оптимальности, или линейной формой.

Вектор управляемых параметровназывается решением. Решение называется допустимым, если оно удовлетворяет ограничениям (8–11). Допустимое решение называется планом.

Решение  называется оптимальным, если на нем достигается наибольшее значение критерия оптимальности:

– оптимальное решение, если

– оптимальное решение, если для любого

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

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

В зависимости от вида ограничений различают следующие формы задач:

Задача в канонической форме – задача ЛП, в которой все ограничения (8) – (10) есть равенства (p =q = 0) и все переменные неотрицательные (r =n).

Общий метод решения задачи ЛП разработан именно для задачи в каноническом виде.

Матричный вид задачи в канонической форме:

() = (*) →

=

=   – вектор коэффициентов критерия

=

=– матрица условий (технологических коэффициентов)

= ( )

=   – вектор условий

=    – вектор ограничений

() = (*)

+  + …+ =

,

Для неё разработан метод решения, который называется симплексным.

Задача в симметричной форме – задача ЛП, в которой все ограничения (8) - (10) есть неравенства (p =q =m) и все переменные неотрицательные (r =n).

Матричный вид задачи в симметричной форме:

Симметричная форма допускает графическое решение (иллюстрацию).

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

эквивалентной формы к другой.

  1. Сведение задачи минимизации к задаче максимизации:

Преобразование сводится к смене знака критерия.

() ~ (())

() = (())

  1. Переход от ограничений-неравенств к уравнению:

+ =

Переменные  - дополнительные или балансовые, так как обеспечивают баланс правой и левой частей.

- =

  1. Переход от переменных произвольного знака к неотрицательным переменным:

=  -

  1. Переход от переменных, ограниченных снизу, к неотрицательным:

= +

  1. Переход от уравнений к неравенствам: