Системы поддержки принятия решения
![]()
|
1.2.Учет ограничений на значения переменныхСущественный вклад в математическую теорию экстремальных задач был внесен Л.В. Канторовичем, впервые сформулировавшим и решившим задачу, позднее получившую название задачи линейного программирования. Математическая постановка этой задачи сводится к поиску переменных, входящих в выражение линейной критериальной функции и, в общем случае, в неограниченное конечное количество дополнительных функций ограничений (тоже линейных), которые в частности могут представлять собой неравенства. Дальнейшее развитие идей Л.В. Канторовича привело к появлению теории математического программирования, расширившей класс используемых функций. Так в некоторых случаях удается решать задачи с нелинейными критериальными функциями (задачи квадратичного программирования, геометрического программирования и т. п.). Отметим, что термин программирование в данном случае используется только как название математического метода и непосредственного отношения к программированию на ЭВМ не имеет. Рассмотрим простейшую задачу математического программирования, у которой имеется линейная целевая функция и линейные ограничения. Такая задача называется задачей линейного программирования. Будем считать, что у этой задачи имеется ![]() ![]() ![]() ![]() Если по смыслу задачи целевая функция должна обращаться в минимум, то для получения выражения (1)) в ней достаточно поменять значения всех коэффициентов ![]() ![]() Набор ограничений может быть записан в виде: ![]() Тогда исходными данными (параметрами задачи) являются наборы коэффициентов ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Оптимальное решение рассматриваемой задачи линейного программирования ![]() ![]() Задача линейного программирования при ![]() ![]() то может быть найдено ее плоскостное решение (рис. 4). Здесь ребра четырехугольника ![]() ![]() ![]() ![]() ![]() Распространенным методом решения задачи линейного программирования является так называемый симплекс – метод. В его основе лежит так называемая симплекс-таблица, которая составляется по определенным правилам исходя из исходных данных задачи (1), 1)). Доказано, что, производя последовательные преобразования этой таблицы по определенным правилам, можно получить оптимальное решение задачи линейного программирования [1]. В основе методов решения нелинейных задач с ограничениями лежит так называемый метод Лагранжа. Наличие ограничения сужает возможности отыскания экстремума. В этом случае, как правило, экстремум функции ![]() ![]() ![]() Рис. 4. Графическая интерпретация метода линейного программирования В отличие от обычной функции ![]() ![]() ![]() ![]() Набор множителей Лагранжа ![]() ![]() При решении таких задач приходится выполнять итеративную процедуру отыскания экстремума, задавая область допустимых значений переменных ![]() ![]() Определив направление возрастания (убывания) целевой функции, построив, например, линии уровня для разных значений ![]() |