Метод множителей Лагранжа

Дана задача нелинейного программирования:

.

Предположим, что эта функция и непрерывны вместе со своими первыми производными. Ограничения заданы в виде уравнений, поэтому для решения задачи воспользуемся методом отыскания условного экстремума:

Составляется функция Лагранжа , где - множители Лагранжа. Затем определяются частные производные , , и приравниваются к нулю. Получается система:

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

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

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

,

ден. ед.

Тема 6. Динамическое программирование.

Динамическое программирование – один из разделов оптимального управления, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги).

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

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

В отличие от линейного программирования, в котором симплекс-метод является универсальным методом решения, в динамическом программировании такого универсального метода не существует.

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

Нахождение рациональных затрат при строительстве трубопроводов и транспортных артерий.

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

Y	(север)				В
	13	9	9	10
11	12	12	13	14
	8	14	9	14
13	15	10	10	8
	12	11	16	10
10	13	12	9	12
	14	13	10	14
А				Х (восток)

Решение. Разделим расстояние между пунктами А и В на шаги (отрезки). На каждом шаге можем двигаться либо строго на восток (по оси Х), либо строго на север (по оси У). Тогда путь от А до В представляет ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей. Затраты на содержание каждого из отрезков даны в таблице.

Путь можно рассматривать как управляемую систему, перемещающуюся под влиянием управления из начального состояния А в конечное В.

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

Процедуру условной оптимизации проводим в обратном направлении, т.е. от В к А.

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

Р ассмотрим предпоследний шаг.

Для точки условное управление – по оси Х, а для точки - по оси У. Управление для выбираем как min(13+10,14+14)= =min(23,28)=23, т.е. по оси У.

Условную оптимизацию проводим для всех остальных узловых точек.

Получим , где  - север, - восток. Минимальные затраты составляют 10+13+8+12+9+9+10=71 млн. руб.

О твет: Прокладывать путь целесообразно по схеме: с, с, в, с, в, в, в; при этом затраты будут минимальные – 71 млн. руб.