- •1.1 Понятие и классификация экономико-математических моделей
- •1.2. Примеры типовых экономико-математических моделей
- •Модуль 2. Сетевые модели в планировании и управлении
- •2.1. Элементы и правила построения сетевой модели
- •2.3. Алгоритм расчета параметров детерминированной сетевой модели
- •2.3. Диаграмма затрат ресурсов и ее оптимизация
- •2.4. Сетевые модели в условиях полной неопределенности
- •2.5. Вопросы для самоконтроля
- •2.6. Тесты. Сетевые модели
- •2.7. Практикум
- •Модуль 3. Экономико-математическая модель межотраслевого баланса «затраты – выпуск»
- •Модель «Затраты–Выпуск». Открытая модель Леонтьева
- •3.2. Замкнутая модель Леонтьева
- •3.3. Динамическая модель Леонтьева
- •3.4. Матричные модели предприятий, фирм
- •3.5. Вопросы для самоконтроля
- •3.6. Тесты. Балансовые модели
- •3.7. Практикум
- •1. Матрица внутрифирменных связей:
- •2. Матрица распределения чистой продукции:
- •3. Матрица затрат ресурсов (фонд заработной платы, материалы, э/энергия, износ оборудования):
- •Модуль 4. Методы и модели линейного программирования
- •4.1. Математическая модель общей задачи линейного программирования
- •4.2. Симплекс - метод решения задач линейного программирования
- •4.3. Двойственность в линейном программировании
- •4.4. Решение задач линейного программирования средствами excel
- •4.5. Вопросы для самоконтроля
- •4.6. Тесты. Линейное программирование
- •4.7. Практикум
- •Модуль 5. Транспортные задачи линейного программирования
- •5.1. Постановка и математическая модель транспортной задачи
- •Математическая модель тз:
- •5.2. Алгоритм решения транспортной задачи методом потенциалов
- •5.3. Транспортная задача с ограничениями на пропускную способность
- •5.4. Метод потенциалов для задачи Td
- •5.5. Вопросы для самоконтроля
- •5.6 Тесты. Транспортные задачи
- •5.7. Практикум
- •Модуль 6. Динамическое программирование
- •6.1. Оптимальное распределение ресурсов
- •6.2. Задача о замене оборудования
- •6.3. Применение динамического программирования в вопросах перспективного планирования.
- •6.4. Выбор оптимальных маршрутов методом динамического программирования
- •6.5. Вопросы для самоконтроля
- •6.6. Тесты. Динамическое программирование
- •6.7. Практикум
- •Задание 4. Выбор оптимальных маршрутов и инцидентных цепей
- •7.1. Постановка и геометрический смысл общей задачи нелинейного программирования
- •7.2. Метод множителей Лагранжа
- •7.3. Градиентные методы
- •7.4. Метод Франка-Вулфа
- •7.5. Метод штрафных функций
- •7.6. Метод наискорейшего спуска
- •7.7. Вопросы для самоконтроля
- •7.8. Практикум
- •Рекомендуемая литература
- •Содержание
- •Математические методы и модели в экономике
- •Издательство
- •625000, Г. Тюмень, ул. Володарского, 38
- •625039, Г. Тюмень, ул. Киевская, 52
7.1. Постановка и геометрический смысл общей задачи нелинейного программирования
В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции
(7.1)
при условии, что ее переменные удовлетворяют соотношениям
, (7.2)
где f и gi – некоторые неизвестные функции n переменных, а bi – заданные числа, а знак () означает, что при различных i ограничения (7.2) могут выражаться со знаком или , или уравнениями. Здесь имеется в виду, что в результате решения задачи будет определена точка , координаты которой удовлетворяют соотношениям (7.2) и такая, что для всякой другой точки , удовлетворяющей условиям (7.2), выполняется в задаче на максимум (минимум) неравенство
Если f и gi – линейные функции, то задача является задачей линейного программирования.
Соотношения (7.2) образуют систему ограничений и включают в себя условия неотрицательности переменных, если такие условия имеются. Условия неотрицательности переменных могут быть заданы и непосредственно.
В евклидовом пространстве Еn система ограничений (7.2) определяет область допустимых решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой.
Если определена область допустимых решений, то нахождение решения задачи (7.1)-(7.2) сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: . Указанная точка может находиться как на границе области допустимых решений, так и внутри нее.
Процесс нахождения решения задачи нелинейного программирования (7.1)-(7.2) с использованием ее геометрической интерпретации включает следующие этапы:
-
Находят область допустимых решений задачи, определяемую соотношениями (7.2) (если она пуста, то задача не имеет решения).
-
Строят гиперповерхность .
-
Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции (7.1) сверху (снизу) на множестве допустимых решений.
-
Находят точку области допустимых решений, через которую проходит гиперповерхность наивысшего (наинизшего) уровня, и определяют в ней значение функции (7.1).
Пример:
Найти максимальное и минимальное значение функции
(7.3)
при условиях
(7.4)
x1≥0, x2 ≥ 0
Решение: Областью допустимых решений исходной задачи является многоугольник ABCDE (рис. 7.1), а линиями уровня – окружности с центром F(4, 3) и радиусом .
Рис.7.1 Геометрическая иллюстрация
Из рисунка. 7.1 видно, что целевая функция принимает минимальное значение в точке F(4, 3), а максимальное значение – в точке С (13, 21/2). Следовательно, Fmin=0 , Fmax=137,25.
7.2. Метод множителей Лагранжа
Рассмотрим частный случай общей задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения, отсутствуют условия неотрицательности переменных и и - функции, непрерывные вместе со своими частными производными
; (7.5)
(7.6)
В курсе математического анализа задачу (7.5) – (7.6) называют задачей на условный экстремум или классической задачей оптимизации.
Чтобы найти решение этой задачи, вводят набор переменных , называемых множителями Лагранжа, составляют функцию Лагранжа
(7.7)
Находят частные производные и и рассматривают систему n+m уравнений
(7.8)
с n+m неизвестными . Всякое решение системы уравнений (7.8) определяет точку , в которой может иметь место экстремум функции . Следовательно, решив систему уравнений (7.8), получают все точки, в которых функция (7.5) может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума.
Таким образом, определение экстремальных точек задачи(7.5) – (7.6) методом множителей Лагранжа включает следующие этапы:
1. Составляют функцию Лагранжа.
2. Находят частные производные от функции Лагранжа по переменным xj и λi и приравнивают их к нулю.
3. Решая систему уравнений (7.8), находят точки, в которых целевая функция задачи может иметь экстремум.
4. Среди точек, подозрительных на экстремум, находят такие, в которых достигается экстремум, и вычисляют значения функции (7.5) в этих точках.