Форум

Тема: Использование методов математического программирования в технических и инженерных приложениях
Копац Э.М., к.т.н., доцент, Копац Т.Л., ст.преподаватель кафедры СКСиТ
Сибирская автомобильно-дорожная академия
Омский государственный институт сервиса

Математическое или оптимальное программирование — область при-кладной математики, объединяющая различные математические методы и дисциплины: линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование и др. Общая задача математического программирования состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений.
Задача математического программирования, рассматривающая методы решения экстремальных задач, в которых результаты (эффективность) возрастают или убывают не пропорционально изменению масштабов ис-пользования ресурсов, масштабов производства состоит в выборе таких неотрицательных значений переменных, подчиненных системе ограничений в форме неравенств, при которых достигается максимум (или минимум) данной функции. Возможны разные случаи: целевая функция нелинейна, а ограничения линейны; целевая функция линейна, а ограничения (хотя бы одно из них) — нелинейны; и целевая функция, и ограничения нелинейны.
Нелинейные задачи сложны, часто их упрощают тем, что приводит к линейным. Такой подход называется методом кусочно-линейных приближений, он применим, однако, лишь к некоторым видам нелинейных задач. Нелинейные задачи в определенных условиях решаются с помощью функции Лагранжа (множители Лагранжа): найдя ее «седловую» точку, тем самым находят и решение задачи. Особенно трудно решаются многоэкстремальные задачи. Для некоторых типов задач выпуклого программирования (вид нелинейного) разработаны эффективные численные методы.
Выпуклое программирование представляет собой совокупность методов решения нелинейных экстремальных задач с выпуклыми функциями. Задача выпуклого программирования состоит в отыскании такого вектора, который доставляет минимум выпуклой функции или максимум вогнутой функции.
Дискретное программирование − раздел оптимального программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область решений конечна.
Квадратичное программирование − раздел выпуклого программиро-вания, в котором целевая функция представляет собой многочлен второй степени, а ограничения линейны. Задачи квадратичного программирования решаются эффективнее всего в тех случаях, когда их удается свести к задачам линейного программирования. Но разработаны и специальные методы их решения.
Линейное программирование — область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными.
Динамическое программирование — раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.
Процессы принятия решений, которые строятся по такому принципу, называются многошаговыми процессами. Математически оптимизационная задача строится с помощью таких соотношений, которые последовательно связаны между собой. Таким образом, можно получить на вычислительной машине результаты решения задачи для любого избранного момента времени и «следовать» дальше. Динамическое программирование применяется не обязательно для задач, связанных с течением времени. Многошаговым может быть и процесс решения вполне статической задачи. Таковы, например, некоторые задачи распределения ресурсов.
Общим для задач динамического программирования является то, что переменные рассматриваются не вместе, а последовательно, одна за другой. Сущность состоит в том, что строится такая вычислительная схема, когда вместо одной задачи со многими переменными строится много задач с малым числом переменных (обычно даже одной) в каждой. Это значительно сокращает объем вычислений. Однако такое преимущество достигается лишь при двух условиях: когда критерий оптимальности аддитивен, т. е. общее оптимальное решение является суммой оптимальных решений каждого шага, и когда будущие результаты не зависят от предыстории того состояния системы, при котором принимается решение. Это вытекает из принципа оптимальности Беллмана, лежащего в основе теории динамического программирования. Из него же вытекает основной прием — нахождение правил доминирования, на основе которого на каждом шаге производится сравнение вариантов будущего развития и заблаговременное отсеивание заведомо бесперспективных вариантов. Когда эти правила обращаются в формулы, однозначно определяющие элементы последовательности один из других, их называют разрешающими правилами. Несмотря на выигрыш в сокращении вычислений, их объем остается очень большим.
Можно выделить два наиболее общих класса задач, к которым в принципе мог бы быть применим этот метод. Первый — задача планирования деятельности экономического объекта (предприятия, отрасли и т. п.) с учетом изменения потребности в производимой продукции во времени. Второй класс задач — оптимальное распределение ресурсов между различными направлениями во времени.
В жизни, на производстве, втехнических, инженерных направлениях возникают проблемы определения наибольшего и наименьшего, наилучшего и наихудшего. Именно в такой форме могут быть поставлены многие задачи, имеющие практическое значение.