Билеты на государственный аттестационный экзамен по специальности Информационные Системы

Задача линейного и нелинейного программирования

Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.

Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.

 Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи: рационального использования сырья и материалов; задачи оптимизации раскроя; оптимизации производственной программы предприятий; оптимального размещения и концентрации производства; составления оптимального плана перевозок, работы транспорта; управления производственными запасами; и многие другие, принадлежащие сфере оптимального планирования. Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций. В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов.

Линейное программирование тесно связано с другими методами математического программирования (например, нелинейного программирования, где целевая функция нелинейна).

Современные методы линейного программирования достаточно надежно решают задачи общего вида с несколькими тысячами ограничений и десятками тысяч переменных. Для решения сверхбольших задач используются уже, как правило, специализированные методы.

Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1 , X2 , Xn , удовлетворяющих ограничениям в виде равенств:

A_{1 1}X₁ + A_{1 2}X₂ + … + A_{1 n}X_n = B₁;

A_{2 1}X₁ + A_{2 2}X₂ + … + A_{2 n}X_n = B₂;

……………………………………

A_{m 1}X₁ + A_{m 2}X₂ + … + A_{m n}X_n = Bm;

Xj ≥ 0, j=1,…,n

и обращающих в максимум линейную функцию этих переменных:

E = C₁X₁ + C₂X₂ + … + C_nX_n Þ max

При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия:

Bj ≥ 0, j=1,…,n

Приведение к стандартной форме необходимо, так как большинство методов решения задач линейного программирования разработано именно для стандартной формы. Для приведения к стандартной форме задачи линейного программирования может потребоваться выполнить следующие действия: - перейти от минимизации целевой функции к ее максимизации; - изменить знаки правых частей ограничений; - перейти от ограничений-неравенств к равенствам; - избавиться от переменных, не имеющих ограничений на знак.

Задача нелинейного  программирования В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции f(x1,x2,…,xn) при условии, что ее переменные удовлетворяют соотношениям

где f и gi – некоторые известные функции n переменных, а bi – заданные числа. Когда целевая (производственная) функция и ограничения нелинейные и для поиска точки экстремума нельзя или очень сложно использовать аналитические методы решения, тогда для решения задач оптимизации применяются методы нелинейного программирования. Как правило, при решении задач методами нелинейного программирования используются численные методы с применением ЭВМ. В основном методы нелинейного программирования могут быть охарактеризованы как многошаговые методы или методы последующего улучшения исходного решения. В этих задачах обычно заранее нельзя сказать, какое число шагов гарантирует нахождение оптимального значения с заданной степенью точности. Кроме того, в задачах нелинейного программирования выбор величины шага представляет серьезную проблему, от успешного решения которой во многом зависит эффективность применения того или иного метода. Разнообразие методов решения задач нелинейного программирования как раз и объясняется стремлением найти оптимальное решение за наименьшее число шагов.

Большинство методов нелинейного программирования используют идею движения в n-мерном пространстве в направлении оптимума.

вектора U^k на величину DU^k, называемую шагом, т.е.

U^k+1=U^k+DU^k                                                                                                                                                   (1) 

В ряде методов шаг, т.е. его величина и направление определяется как некоторая функция состояния U^k

DU^k=f(U^k)                                                                                                                                                   (2) 

Следовательно, согласно (1) новое состояние U^k, получаемое в результате выполнения шага (2) может рассматриваться как функция исходного состояния U^k

U^k+1=U^k+f(U^k)                                                                                                                                                   (3) 

В некоторых методах DU^k обусловлен не только состоянием U^k, но и рядом предшествующих состояний

  DU^K=f(U^k) ,U^k-1...,U^k-2                                                                                                                                                  (4)

  U^k+1=U^k+f(U^k),U^k-1...,U^k-2                                                                                                                                                   (5) 

Естественно, что алгоритмы поиска типа (5) являются более общими и принципиально могут обеспечить более высокую сходимость к оптимуму, т.к. используют больший объем информации о характере поведения оптимальной функции.

В настоящее время для решения подобных задач разработано значительное число методов, однако нельзя отдать предпочтение какому-либо одному. Выбор метода определяется сложностью объекта и решаемой задачей оптимизации.

Методы нелинейного программирования в соответствии со способом определения шага поиска R(U) можно отнести к одному из 3-х типов:

1.Безградиентные методы

2.Градиентные методы

3.Методы случайного поиска.

Все эти методы можно назвать прямыми итеративными методами.

Задачи оптимизации (экстремальные задачи)

называются задачами нелинейного программирования (сокращенно задачами НЛП), если среди функций f, g₁...g_m, h₁..., h_k имеется хотя бы одна нелинейная функция. Записи (1)-(3) и (4)-(5) являются стандартными постановками задач минимума и максимума (обратите внимание на знаки неравенств в (2) и (5)).

Задачи НЛП, как и любые другие задачи оптимизации, являются математическими моделями некоторых практических задач принятия решения.