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

2020-06-032021-03-09zzyxelСтудИзба

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

Множители Лагранжа можно рассматривать для ЗЛП только в канонической форме записи.

тогда можно построить функцию Лагранжа

Для оптимального решения

Таким образом двойственные переменные - суть множителя Лагранжа. Тогда функция Лагранжа для двойственной задачи запишется:

Рекомендуемые материалы

Определить величину оборотных средств в производственных запасах по i– тым комплектующим, если годовой объем выпуска изделий, в каждом из которых применяются i– тые комплектующие на сумму 3 д. е., составляет 36000 шт. Договора с предприятиями-поставщ

Экономика предприятия

99 руб.

Определить величину годовых амортизационных отчислений при средней норме амортизации 10%, если стоимость основных средств на 01.01.ХХ составляла 10210 д.е., 01.03.ХХ было введено в действие оборудование стоимостью 2013 д.е., а с 01.09.ХХ выбыло основ

Экономика предприятия

99 руб.

Задачи по кредитам, процентным ставкам

Деньги и кредит

270 руб.

Предприятие планирует выпуск продукции в 1000 шт/год. Для этого необходимо приобрести технологическое оборудование стоимостью 20 тыс. д.е., приборы контроля стоимостью 10 тыс. д.е., вычислительную технику — 5 тыс. д.е. Для создания производственных у

Экономика предприятия

99 руб.

Анализ финансового состояния финансовой организации ПАО АКБ "Авангард" и рекомендации по его улучшению

Экономика финансовых организаций

500 руб.

Определить первоначальную и остаточную стоимость металлорежуще-го станка, если известны следующие данные. Цена станка, использование которого начато три года назад, составляла 4,5 тыс. д.е., доставка и монтаж – 0,5 тыс. д.е. Норма амортизации – 14,2

Экономика предприятия

99 руб.

Рассмотрим задачу линейного программирования в канонической форме записи:

(1)

(2)-(3)

Составим функцию Лагранжа:

. (4)

Теорема. Задача линейного программирования (1)-(3) имеет решение тогда и только тогда, когда такие, что функция Лагранжа достигает мавксимума в точке в области .

Доказательство.

1. Необходимость. Пусть - оптимальное решение задачи(1)-(3).Покажем, что в точке функция Лагранжа (4) достигает максимума в области .

Для доказательства построим двойственную задачу к данной:

(5)

(6)-(7)

Т. к. задача (1)-(3) имеет оптимальное решение, то и задача (5)-(7) имеет оптимальное решение .

Тогда будем иметь:

(8)

По теореме двойственности . (9)

Откуда

Или при , значит, - точка максимума для функции Лагранжа (4).

2. Достаточность. . Требуется доказать, что - оптимальное решение задачи (5)-(7).

Предположим противное.

Пусть существует , для которого (6) не выполняется:

Тогда функция Лагранжа перепишется в виде:

, т. е. .

Следовательно, не является оптимальным решением, что противоречит условию. Тем самым мы показали, что - допустимое решение задачи (5)-(7), и выполняется условие (6):

. (10)

Покажем, что для выполняется соотношение (9). Предположим противное:

. (11)

Пусть существует индекс такой, что (12) (не выполняется (11)).

, что противоречит условию.

Т. е. предположение, что существует индекс неверно. Следовательно, - оптимальное решение, для него верно (10), и это вытекает из теоремы двойственности.

Примечание. (14)

Точка называется седловой точкой.

Выпуклое программирование

Рассмотрим задачу:

(1)

(2)

Функции - выпуклые функции.

Задача (1)-(2) не имеет смысла, если область не ограничена снизу. Во всех остальных случаях она имеет решение.

Теорема 1. Если является аргументом локального минимума:

то или .

Доказательство.

Предположим противное. Пусть в области существует , в котором . Рассмотрим линейную комбинацию

Из определения выпуклости функции следует:

(3)

Выражение (3) является условием выпуклости. Выберем достаточно малым:

Т. о. получили две точки минимума, что противоречит свойству выпуклости функции . Следовательно, предположение о существовании точки было неверным. Поэтому - точка глобального минимума функции .

Теорема Куна-Таккера.

(1)

, (2)

где - выпуклые функции.

Условие Слейтера( необходимо для выполнения теоремы).

Теорема. будет решением задачи (1)-(2)когда существует вектор и такой, что вектор является седловой точкой функции Лагранжа для задачи (1)-(2).

Выясним, можно ли с помощью формализма Лагранжа решить линейную задачу.

Тогда получим ограничение для двойственной задачи

и для прямой задачи

Доказательство.

Пусть существует и .

(4)

Заметим, что (4) является условием седловой точки.

(4’)

1. Требуется доказать, что - точка минимума для задачи (1)-(2). Покажем, что является дополнительным решением для задаи (1)-(2), т. е. что .

Предположим противное. Пусть существует индекс , для которого условие (2) не выполняется, т. е. .

Задавая достаточно большим, получим, что последнее выражение будет неограниченно возрастать, что противоречит условию (4’). Следовательно, предположение о том, что существует индекс , для которого не выполняется условие (2) было неверно. Таким образом, .

Теперь докажем, что - точка минимума функции :

Рассмотрим правое неравенство из (4’):

Тогда , что и требовалось доказать.

2. Необходимо построить множитель Лагранжа, чтобы имела место седловая точка. Причем, дано, что

Рассмотрим два множества:

где - выпуклые функции.

Тогда из построения следует, что и тоже являются выпуклыми множествами.

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