- •1.4.Двойственность состоит в том, что каждой исходной (прямой) задаче, в которой целевая функция стремится к максимуму (минимуму)
- •2. Лекции
- •Понятие модели
- •Классификация экономико-математических моделей
- •Оптимизационные модели
- •Лекция 2. Примеры содержательных постановок задач линейного программирования
- •Задача об оптимальном использовании ресурсов
- •Транспортная задача линейного программирования
- •Стандартная форма задачи линейного программирования
- •Каноническая форма задачи линейного программирования (злп)
- •Лекция 3. Различные формы задач линейного программирования
- •Переход от стандартной формы задачам линейного программирования (злп) к канонической
- •Лекция 4. Графический метод решения задач линейного программирования
- •Лекция 5. Основные теоремы линейного программирования
- •Геометрическая интерпретация симплекс-метода
- •Основное неравенство теории двойственности
- •Лекция 8. Основные теоремы двойственности
- •Лекция 9. Задачи нелинейного программирования
- •Метод множителей Лагранжа
- •Выпуклое программирование
- •Задача выпуклого программирования
- •Градиентные методы
- •Метод параллельных касательных
- •Метод сопряженных градиентов
- •Метод покоординатного спуска
- •О методах второго порядка
- •О методах прямого поиска
- •Методы одномерной минимизации
- •1. Задачи с ограничениями-равенствами
- •2. Задачи с ограничениями-неравенствами
- •2.1. Метод проекции градиента
- •2.2. Метод приведенного градиента
- •Методы штрафных функций
- •Методы барьерных функций
- •Лекция 14. Практическая реализация методов нелинейного программирования
- •Построение начального приближения
- •Практическая реализация методов нелинейного программирования
- •3. Практические и лабораторные занятия
- •4. Самостоятельная работа студента
- •Задача об оптимальном использовании ресурсов
- •Транспортная задача линейного программирования
- •Стандартная форма задачи линейного программирования
- •Основное неравенство теории двойственности
- •Экономический смысл первой (основной) теоремы двойственности
Классификация экономико-математических моделей
Экономико-математические модели можно классифицировать по ряду признаков, относящихся к особенностям моделируемого объекта:
цели моделирования;
используемый инструментарий, т.е. модели макро- и микроэкономические, теоретические и прикладные, оптимизационные и равновесные, статические и динамические и т.д.
Макроэкономические модели рассматривают экономику как единое целое.
Микроэкономические модели описывают взаимодействие структурных и функциональных составляющих экономики либо поведение одной такой составляющей в рыночной среде.
Равновесные модели описывают такие состояния экономики, когда результирующая всех сил, стремящаяся вы вести ее из данного состояния, равна нулю.
Оптимизационные модели присутствуют в основном на микроуровне: максимизация прибыли, минимизация затрат.
Статические модели описывают некоторый объект в определенный (фиксированный) момент времени.
Динамические модели включают взаимосвязи переменных во времени. Динамические модели обычно используют аппарат теории дифференциальных игр и разностных уравнений.
Детерминированные модели предполагают жесткие функциональные связи между переменными моделями.
Стохастические модели допускают случайные воздействия на исследуемые показатели и используют инструментарий теории вероятностей и математической статистики.
Эконометрические модели строятся на основе изучения и анализа эмпирических данных.
Одними из наиболее распространенных моделей являются оптимизационные.
Оптимизационные модели
Математические методы оптимизации, соответствующие алгоритмы и компьютерные программы можно рассматривать как эффективный элемент наукоемких технологий, разработка которых в различных областях в настоящее время особенно актуальна. Оптимизационные методы используются в исследовании операций и системном анализе, в планировании производственной деятельности, в проектировании различных объектов, в военном деле и т.д.
Недостаточность классической теории оптимизации вылилась во второй трети XX в. при необходимости решать задачи с ограничениями в виде неравенств, особенно при большом числе переменных. Последнее обстоятельство (большая размерность задач) преодолено разработкой численных методов решения систем алгебраических уравнений соответствующих компьютерных программ.
Задачи с ограничениями в виде неравенств, в которых равенство нулю частных производных вообще не является даже необходимым условием экстремума, потребовали работки новой теории оптимизации — теории математического программирования. Эта теория дает совокупность методов решения задач поиска экстремума функций многих переменных (целевая функция) при наличии ограничений (равенств или неравенств) на искомые неизвестные. Как правило, это численные (итерационные) годы. Их практическая реализация осуществляется в соответствующих алгоритмах и компьютерных программах.
Классические задачи на безусловный экстремум (при отсутствии ограничений вообще) или при наличии только ограничений-равенств также могут решаться методами математического программирования (как частный случай). Отсюда следует теоретическая и практическая значимость этих методов.
Наиболее известными и простыми являются методы линейного программирования, используемые в научных исследованиях и практической деятельности значительно чаще, чем методы нелинейного программирования. Но нелинейное программирование— это бурно развивающийся раздел современной теории оптимизации, созданный практически в последние 30-40 лет. Сравнительно редкое практическое применение методов нелинейного программирования объясняется именно этим обстоятельством (а не отсутствием реальных практических задач), так как необходимо значительное время для освоения новых теорий широким кругом практиков и реализации новых методов в конкретных алгоритмах и компьютерных программах. Более того, реализация методов нелинейного программирования для решения задач большой размерности требует мощных компьютеров, которые получили широкое распространение в нашей стране только в последние 10-15 лет.
Почти одновременно с линейным программированием (конец 40-х - начало 50-х годов прошлого века) был разработан метод динамического программирования. В «компьютерную эпоху» он получил широкое применение в самых различных областях практики. Этот мощный метод оптимизации далеко не универсальный. Известны безуспешные попытки его применения без должного анализа особенностей конкретной задачи оптимизации.
Отличительные признаки оптимизационных моделей:
наличие одного или нескольких критериев оптимальности (критерий оптимальности — это признак, по которому одно (или множество) решений задачи признается наилучшим); наиболее типичными критериями в экономических оптимизационных задачах являются: максимум дохода или прибыли, минимум издержек, минимальное время для выполнения задания и другие;
система ограничений, формируемая исходя из содержательной постановки задачи и представляющая собой систему уравнений или неравенств.
Математически эти задачи относятся к задачам на условный экстремум. Постановка таких задач, представленных в общем виде, выглядит следующим образом:
• найти условный максимум (или минимум) функции
Y = f (x1x2...xn) → max (min), (1)
• при условии, что независимые переменные удовлетворяют ограничениям:
G (x1 ,x2...xn) = 0. (2)
Функцию G называют функцией, задающей ограничения. Если в задаче на условный экстремум ограничения в виде системы уравнений G (x1, x2,..., хn) = 0 заменить на ограничения в виде неравенств и добавить требования (ограничения) неотрицательности переменных x1 ≥0, x2 ≥0,... хn≥0, то получим задачу математического программирования, в которой необходимо:
• найти максимум (или минимум) функции
f (x1,x2...xn) →max(min) (3)
• при условии, что независимые переменные удовлетворяют системам ограничений:
g1(x1,x2...xn) ≤ 0
……………… (4)
gn(x1,x2...xn) ≤ 0
x1≥0,x2≥0,...,xn≥0 (5)
В задаче математического программирования функцию f (xb x2..., хn) также называют целевой функцией; систему неравенств (4) — специальными ограничениями задачи математического программирования, а неравенства (5) — общими ограничениями задачи линейного программирования.
Задача линейного программирования — частный случай задачи математического программирования, в которой целевая функция и ограничения линейные.
Именно этот класс оптимизационных моделей наиболее широко применяется в экономике. Разработаны специальные пакеты программ линейного программирования для решения этого класса задач.
Вопросы для самоконтроля:
1.Сущность и классификация оптимизационных задач и методов.
2.Условия существования экстремумов.
Рекомендуемая литература:
1.Акулич И.Л. Математическое программирование в примерах и задачах. — М.: Высш. шк., 1986.
2.Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. М.: Наука, 1984.
