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

6

ГЛАВА 1. О нелинейном программировании.

1.1.История развития нелинейного программирования.

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

Термин "математическое программирование" предложен Робертом Дорфманом приблизительно в 1950 г.; теперь он объединяет линейное программирование, целочисленное программирование, выпуклое программирование, нелинейное программирование и программирование при наличии неопределённости. Нелинейное программирование имеет дело с оптимизацией нелинейных функций при линейных и (или) нелинейных ограничениях. Типичными областями его применения являются прогнозирование, планирование промышленного производства, управление товарными ресурсами, контроль качества выпускаемой продукции, планирования обслуживания и ремонта, проектирование технологических линий (процессов), учет и планирование капиталовложений. Пока еще не существует общего метода решения нелинейных задач оптимизации, такого, как, например, симплексный алгоритм, разработанный для задач линейного программирования. Нелинейное программирование при решении задач включает в себя элементы экспериментирования. Его развитие до сих пор сводилось к предложениям частных алгоритмов, программированию их, проверке результатов применения этих алгоритмов в конкретных  задачах, представляющих практический интерес, и построению лучших алгоритмов на основе приобретенного опыта. Оно подобно айсбергу, огромная подводная часть которого скрыта еще от пытливых глаз.

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

1.2.Классификация методов нелинейного программирования.

Большинство практических задач имеет несколько (а некоторые, возможно, даже бесконечное число) решений. Целью оптимизации является нахождение наилучшего решения среди многих потенциально возможных в соответствии с некоторым критерием эффективности или качества. Задача, допускающая лишь одно решение, не требует оптимизации. Оптимизация может быть осуществлена при помощи многих стратегий, начиная с весьма сложных аналитических и численных математических процедур и заканчивая  разумным применением простой арифметики. Предполагая, что подлежащая оптимизации задача должным образом  определена (не обязательно математически), можно классифицировать общие методы оптимизации следующим образом:

1.      Аналитические методы, использующие классические методы дифференциального и вариационного исчислений, Эти методы заключаются в определении экстремума функции f(x) путем нахождения тех значений х, которые обращают в нуль производные f(x) по х. В случае поиска экстремума  f(x) при наличии ограничений применяются такие методы, как метод множителей Лагранжа и метод ограниченных вариаций. При использовании аналитических методов задача оптимизации должна быть сформулирована  математически с тем, чтобы можно было обращаться со всеми фигурирующими в ней функциями и переменными при помощи известных правил. Ограничением является то, что для решения больших существенно нелинейных задач аналитические методы зачастую оказываются непригодными.

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

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

4.      Экспериментальные методы. Экстремум функции можно иногда найти, экспериментируя непосредственно с реальными переменными вместо того, чтобы исследовать соответствующую математическую модель. Результаты одного эксперимента используются для планирования следующего эксперимента, позволяющие получить улучшенные результаты.

5.      Методы исследования различных вариантов. Эти методы основаны на анализе нескольких возможных решений  одной и той же задачи с целью выбора наилучшего. Таким образом, "наилучшее" решение, полученное меетодом исследования различных вариантов, будет скорее всего субоптимальным.

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

1.3.Общая постановка задачи нелинейного программирования.

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

1.      Переменные принимают лишь целочисленные значения (целочисленное нелинейное программирование).

2.      Ограничения включают как параметр время, при этом используется дифференциальные уравнения (оптимальное управление, динамическая оптимизация).

Пусть непрерывная функция  f(x) представляет собой целевую функцию, h1(x), …,hm(x) задают ограничения в виде равенств, а gm+1(x), …,gp(x) – ограничения в виде неравенств, где х = [х1, …,хn]Т – вектор – столбец компонент х1, …,хn в n-мерном евклидовом пространстве.

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

Формально задача нелинейного программирования может быть сформулирована следующим образом:

минимизировать f(x), хЕn ,                                              (1.1)

при m линейных и (или) нелинейных ограничениях  в виде равенств

hi(x)=0,    i=1, …, m,                                                           (1.2)

при (p-m) линейных и (или) нелинейных ограничениях  в виде неравенств

gi(x)0,    i=m+1, …, p.                                                       (1.3)

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

Иногда встречается другое представление выражений (1.1) – (1.3):

минимизировать {f(x)|xR} ,                                             (1.4)

где  R – область значений переменной х , для которой выполнены условия (2) и (3), например

              R={x|hi(x),   gi(x)0 для всех i}.                                      (1.5)

              Знак неравенства в выражении gi(x)0 может быть изменён на обратный путем умножения на –1, что не изменит математической постановки задачи.