При условиях. Метод линейного программирования

Метод линейного программирования

Рассмотрим некоторые частные случаи достаточных условий экстремума, которые могут быть получены из условий Сильвестра (111,14).

Случай двух переменных. Достаточным условием минимума является по­ложительность главных миноров первого и второго порядков, что, принимая во внимание соотношения (111, 13), дает два условия относительно значений вторых производных функции R(x):

*

Достаточным условием максимума в точке является выполнение усло­вия

(111, 17), т. е. положительность четного минора, и одновременное выполнение условия отрицательности первого (нечетного) минора:

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

Подставляя в соотношение (111, 17), которое должно выполняться для экстремальной точки любого типа, значения производных из выражений (в) и (и), получим, что это условие не выполняется. Следовательно, функция R(), определяемая выражением (111,4), в точке с координатами (б) не; имеет экстремума, что и было получено ранее с использованием вращения] осей координат.

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

=; (111,19)

При получении развернутых выражений главных миноров (111,20) (111,21) использовалось свойство симметрии матрицы (111,15), которое дует из определения ее элементов (111, 13), так как для непрерывных функций имеющих непрерывные производные до второго порядка, справедливо равенство:

Достаточным условием минимума для функции трех переменных является; положительность всех трех миноров (111, 19) —(111, 21), т. е.

Достаточным условием максимума служит положительность четных мино­ров (111,20) и отрицательность нечетных миноров (111,19) и (111,21), т. е.

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

Глава 2

Общей задачей ЛП является отыскание наибольшего или наименьшего значения линейной функции на множестве неотрицательных решений линейной системы неравенств или системы: неравенства + уравнения.

В основной задаче ЛП линейная система содержит только уравнения:

Минимизировать (максимизировать):

Общая задача ЛП может быть сведена к равносильной ей основной задаче путём введения добавочных неизвестных, например, дана общая задача

при условиях

.

Здесь показатель качества и ограничения линейны относительно неизвестных. Сведем общую задачу ЛП к равносильной ей основной задаче:

при условиях

;

.

Между общей задачей ЛП и соответствующей ей основной существует связь. Если оптимальное решение (оптимальный план) основной задачи, то – оптимальное решение общей задачи и наоборот. Причем оптимальные значения целевых функций совпадают:

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

Задача ЛП является задачей максимизации, если находяти минимизации, если находят.

В литературе могут также встретиться и другие формы записи общей и основной задач ЛП [1-4]:

1) Максимизировать (минимизировать) функцию цели

переменные которой подчинены следующим условиям:

.

2) Минимизировать

3) Минимизировать при условиях, где

– вектор-строка; - вектор-столбец; – матрица коэффициентов системы ограничений;

– вектор-столбец.

Дата добавления: 2014-01-06