- •Им. А.Н.Туполева
- •И.П. Ультриванов
- •Учебное пособие для студентов экономического факультета Издательство Казанского
- •Глава 1. Основные понятия моделирования систем
- •Виды и способы математического моделирования систем
- •Экономико-математические модели
- •Адекватность модели
- •1.4. Понятие «черного ящика» в теории управления
- •1.5. Последовательность процесса моделирования
- •Глава 2. Основные свойства систем управления
- •2.1. Понятие системы
- •2.2. Устойчивость динамических систем
- •2.3. Равновесие в экономических системах
- •2.4. Качество процессов регулирования
- •Глава 3. Общие методы оптимизации
- •3.1. Классификация методов получения оптимальных решений
- •3.2. Оптимальные решения
- •3.3. Математическое программирование
- •Глава 4. Задача линейного программирования и ее оптимальное решение
- •4.1. Определение линейности функций
- •4.2. Постановка задачи линейного программирования
- •4.3. Геометрическая интерпретация и графический метод решения задачи линейного программирования
- •4.4. Симплексный метод решения задачи
- •Алгоритм симплекс-метода решения злп. Алгоритм симплекс-метода решения злп продемонстрируем на простом примере.
- •Глава 5. Методы оптимизации в задачах нелинейного программирования
- •5.2. Метод множителей Лагранжа
- •5.3. Методы одномерного поиска минимума функции
- •Эффективность одномерных методов поиска
- •5.4. Методы минимизации без ограничений, использующие производные
- •5.5. Методы минимизации без ограничений, не использующие производные (методы поиска)
3.3. Математическое программирование
Определение и цели. Термин «математическое программирование» (МП) предложен Робертом Дорфманом приблизительно в 1950 г. В общем случае, под МП понимается раздел математики, посвященный теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых некоторыми ограничениями (равенствами и неравенствами). Математическое программирование, которое также называют оптимальным программированием, следует отличать от программирования на ЭВМ.
Большинство практических задач имеет несколько, а иногда и бесконечное множество решений. Целью оптимизации является нахождение наилучшего решения среди многих потенциально возможных в соответствии с некоторым критерием эффективности или качества. Задача, допускающая лишь одно решение, не требует оптимизации. Оптимизация может быть осуществлена при помощи многих стратегий, начиная с весьма сложных аналитических и численных процедур и кончая разумным применением простой арифметики. Существующие в настоящее время многочисленные математические методы оптимизации уже достаточно развиты, что позволяет эффективно использовать возможности современной вычислительной техники. Одним из этих методов является математическое программирование.
Классификация задач математического программирования. Этот метод объединяет:
-
линейное программирование;
-
нелинейное программирование;
-
выпуклое программирование;
-
целочисленное программирование;
-
программирование при наличии неопределенностей.
-
Последние годы в области МП значительные усилия были сконцентрированы на линейном программировании. Задача линейного программирования ― частный случай задачи математического программирования, в которой целевая функция и ограничения линейные. Именно этот класс оптимизационных моделей наиболее широко применяется в экономике. Разработаны специальные пакеты программ для решения задач этого класса. Полученные результаты столь значительны, что достигнутый здесь уровень позволяет решать большинство практических задач.
-
Нелинейное программирование имеет дело с оптимизацией нелинейных функций при линейных и (или) нелинейных ограничениях. Типичными областями его применения являются прогнозирование, планирование промышленного производства, управление товарными ресурсами, контроль качества выпускаемой продукции, учет и планирование капиталовложений и т. д.
Хотя здесь было предложено большое число различных стратегий поиска оптимальных решений, успешное применение нашли лишь немногие алгоритмы. Пока еще не существует общего метода решения нелинейных задач оптимизации, такого, например, как симплексный метод, разработанный для задач линейного программирования. Нелинейное программирование при решении задач включает в себя элементы экспериментирования. Его развитие до сих пор сводилось к предложениям частных алгоритмов, их программированию, проверке результатов применения этих алгоритмов на конкретных задачах и построению лучших алгоритмов на основе приобретенного опыта.
В настоящее время, в связи с развитием информационных технологий и ЭВМ, растет необходимость в методах решения задач нелинейного программирования с более широкой областью применимости.
-
Целочисленное (иногда его называют также дискретным) программирование
изучает экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано, как правило, с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля или принять на работу пять с четвертью человек. Иногда такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Но в ряде случаев такой подход не всегда оправдан, поэтому разработаны и специальные методы решения целочисленных задач, такие, например, как метод отсекающих плоскостей и комбинаторные методы.