Основы теории оптимизации (стр. 3 )

Пусть имеется n различных пищевых продуктов, содержащих m различных питательных веществ. Обозначим через aij содержание (долю) j-го питательного вещества в i-ом продукте, через bj — суточную потребность организма в j-ом питательном веществе, через ci — стоимость единицы i-го продукта. Требуется составить суточный рацион питания минимальной стоимости, удовлетворяющий потребность во всех питательных веществах. Если обозначить через xi суточное потребление i-го продукта, то эта задача может быть формализована следующим образом. Нужно минимизировать функцию

f(x1, ..., xn) =  n ∑ i = 1 cixi (стоимость рациона)

при условиях

n ∑ i = 1 aijxi ≥ bj, j = 1, ..., m

(рацион должен содержать не менее суточной
потребности в каждом из питательных веществ).

Очевидно, также следует требовать, чтобы

xi ≥ 0, i = 1, ..., n.

В векторных обозначениях задача о рационе может быть записана так: минимизировать функцию

f(x) = (c, x),

где c = (c1, ..., cn) Rn; эту задачу, как обычно, записывают в виде

(c, x) → min,

при ограничениях

Ax ≥ b,

x ≥ Θ.

В них первое неравенство связывает два вектора Ax и b из Rm, а второе – два вектора x и Θ из Rn.

По легенде одним из первых приложений задачи о рационе к реальной жизни была попытка рассчитать оптимальный рацион для американской армии во время второй мировой войны. Результат был неожиданным: солдат в день должен выпивать литр уксуса и съедать килограм бобов (цифры и продукты условные).

1.1.5. Транспортная задача.

Эта задача — классическая задача линейного программирования. К ней сводятся многие оптимизационные задачи. Формулируется она так. На m складах находится груз, который нужно развезти n потребителям. Пусть ai (i = 1, ..., n) — количество груза на i-ом складе, а bj (j = 1, ..., m) — потребность в грузе j-го потребителя, cij — стоимость перевозки единицы груза с i-го склада j-му потребителю. Требуется минимизировать стоимость перевозок. Если обозначить через xij объем перевозок с i-го склада j-му потребителю, то транспортная задача формализуется так:

n ∑ i = 1 m ∑ j = 1 cijxij → min,

n ∑ i = 1 xij = bj, j = 1, ..., m

(все потребители должны быть удовлетворены),

m ∑ j = 1 xij = ai, i = 1, ..., n

(весь груз должен быть доставлен потребителю),

xij ≥ 0

(нельзя перевозить груз от потребителя на склад).

Это были примеры линейных задач условной оптимизации. Приведем один пример нелинейной задачи.

1.1.6. Задачи о распределении ресурсов.

Общий смысл таких задач — распределить ограниченный ресурс между потребителями оптимальным образом. Рассмотрим простейший пример — задачу о режиме работы энергосистемы. Пусть m электростанций питают одну нагрузку мощности p. Обозначим через xj активную мощность, генерируемую j-ой электростанцией. Техническими условиями определяются возможный минимум μj и максимум Mj вырабатываемой j-ой электростанцией мощности. Допустим затраты на генерацию мощности x на j-ой электростанции равны ej(x). Требуется сгенерировать требуемую мощность p при минимальных затратах. В наших обозначениях

f(x) ≝  m ∑ j = 1 ej(xj) → min,

m ∑ j = 1 xj = p,

μj ≤ xj ≤ Mj, j = 1, ..., m.

Если обозначить ∑mj=1ej(xj)через f(x), ∑mj=1xj– p через g(x), а {x Rm: μ ≤ x ≤ M} через Ω, то эта задача переписывается так

f(x)→min, g(x)=0, x Ω.

1.1.7. О классификации задач оптимизации.

Один из классификационных признаков делит оптимизационные задачи на два класса: задачи безусловной оптимизации и задачи условной оптимизации. Первые из них характеризуются тем, что минимум функции f: Rm → R ищется на всем пространстве:

f(x) → min, x Rm.

(2)

В задачах же второго класса поиск минимума идет на некотором собственном подмножестве Ω пространства Rm:

f(x) → min, x Ω.

(3)

Множество Ω часто выделяется ограничениями типа равенств

g0(x) = Θ,

(4)

где g0: Rm → Rk, и/или ограничениями типа неравенств

g1(x) ≤ Θ,

(5)

где g1: Rm → Rl.

Другой классификационный признак задач оптимизации — свойства функций f и множеств Ω. Например задачи (2) и (3) называются линейными (часто говорят о задачах линейного программирования), если функция f — аффинная, а множество Ω — многогранное (множество Ω называется многогранным, если оно выделяется ограничениями вида (4) и (5) с аффинными функциями g0 и g1).

Замечание. Линейная задача безусловной оптимизации (1) имеет решение (причем обязательно неединственное) в том и только том случае, если f(x) ≡ const.

Если функции f, g0 и g1 квадратичные, то говорят о задачах квадратичного программирования или о квадратичных задачах оптимизации (условных или безусловных). Если эти функции выпуклые, то говорят о задачах выпуклого программирования (если множество Ω задается каким-либо другим образом, а не только ограничениями типа (4) и (5), то в задачах выпуклого программирования требуют его выпуклость). Наконец, в общем случае говорят о задачах нелинейного программирования. В таких задачах обычно предполагается гладкость фигурирующих в них функций.

1.2. Краткий обзор методов оптимизации

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

Для решения оптимальных задач применяют в основном следующие методы:

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

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