Теорию и методы решения задачи оптимизации изучает математическое программирование.
Выбор наилучшего решения (плана) – называется программированием. Наука, занимающаяся разработкой теории и методов выбора наилучших вариантов решения (плана) из множества возможных, получила название математическое программирование. Частью математического программирования является ли- нейное программирование
Математическое программирование — это область математики, разрабатывающая теорию, численные методы решения многомерных задач с ограничениями. В отличие от классической математики, математическое программирование занимается математическими методами решения задач нахождения наилучших вариантов из всех возможных.
По критерию размерности допустимого множества, методы оптимизации делят на методы одномерной оптимизации и методы многомерной оптимизации.
По виду целевой функции и допустимого множества, задачи оптимизации и методы их решения можно разделить на следующие классы:
· Задачи оптимизации, в которых целевая функция f(->x) и ограничения gi (->x), i= 1, …, m являются линейными функциями, разрешаются так называемыми методами линейного программирования.
· В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:
· если f(->x) и gi (->x) — выпуклые функции, то такую задачу называют задачей выпуклого программирования;
· если X ( принадлежит Z, то имеют дело с задачей целочисленного (дискретного) программирования.
Задачи линейного программирования решаются с применением алгоритмов симплексного и распределительного методов
В задачах линейного программирования через систему линейных уравнений и неравенств, с достаточной точностью воспроизводятся экономические процессы, ха- рактеризующиеся множеством взаимодействующих факторов. Линейные уравнения или неравенства - называются ограничениями и в совокупности составляют матема- тическую модель.
Наиболее универсальным методом решения задач линейного программирова- ния является симплексный метод. Алгоритм метода базируется на последовательном улучшении некоторого первоначального плана, когда за определенное число итера- ций (циклически повторяющихся вычислений симплексных таблиц) получается оп- тимальное решение. После каждой итерации значение целевой функции должно улучшаться. Процесс повторяется до тех пор, пока не будет получен оптимальный план. Симплексный метод имеет геометрическую интерпретацию
Каждой прямой задаче линейного программирования соответствует двой- ственная (обратная) по отношению к ней. Искомой величиной двойственной задачи является двойственная оценка, т.е. двойственная задача обеспечивает расчет двой- ственных оценок.
Распределительный метод является частным случаем задач линейного програм- мирования. Изначально он был создан для оптимизации организации грузоперевозок и поэтому называется транспортной задачей (ТЗ). Транспортная задача может быть решена с помощью универсального симплекс-метода. Однако применение симплекс- метода к транспортным задачам не рекомендуется, т.к. он оказывается слишком гро- моздким.
В динамических моделях рассматривается поведение системы на нескольких временных интервалах, а поиск решения производится один раз, оптимизируя поведение модели на всех временных интервалах сразу. Динамические модели являются более реалистическими и более адекватно описывают многие производственные ситуации.
Нелинейное программирование — разделматематического программирования, изучающий методы решения экстремальных задач с нелинейнойцелевой функцией и (или) областью допустимых решений, определенной нелинейными ограничениями. Вэкономике это соответствует тому, что результаты (эффективность) возрастают или убываютнепропорционально изменению масштабов использования ресурсов (или, что то же самое, масштабовпроизводства) — например, из-за деления издержек производства на предприятиях на переменные и условно-постоянные, из-за насыщения спроса на товары, когда каждую следующую единицу продать труднее, чемпредыдущую, из-за влияния экстерналий
Выпуклое программирование [convex programming] — разделнелинейного программирования, совокупность методов решения нелинейных экстремальных задач свыпуклыми целевыми функциями (они минимизируются) и выпуклыми системами ограничений. (См. Выпуклость, Вогнутость).
Общая задача В.п. состоит в отыскании такого вектора x (т.е. такой точки выпуклого допустимогомножества), который доставляет минимум выпуклой функции f(x) или максимум вогнутой функции y(x) (рис. В.4). Для второго случая (выпуклая область допустимых значений и максимум вогнутой функции) ряд авторовпредпочитают термин «вогнутое программирование». Выпуклость (вогнутость) важна тем, что гарантируетнахождение оптимального решения задачи, так как соответственно локальные и глобальный экстремумыздесь обязательно совпадают. Критериями оптимальности в первом случае могут быть, например, издержкипри различных сочетаниях факторов производства, во втором случае — величина прибыли при этихсочетаниях. Как видим, есть большое сходство между задачами выпуклого (вогнутого) и линейногопрограммирования (последнее можно рассматривать как частный случай первого). Но нелинейностьзависимостей делает задачу намного сложнее.
Задачи комбинаторной оптимизации можно решить с помощью методов дискретного программирования. Одними из основных методов решения задач дискретного программирования являются метод отсечения[1], метод ветвей и границ[2] и динамическое программирование
Целочисленным (иногда его называют также дискретным) программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано, как правило с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля и т.д. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение. Поэтому разработаны специальные методы решения целочисленных задач.
