§ 7.1. общая задача оптимизации. линейное программирование. примеры задач

§ 7.1. общая задача оптимизации. линейное программирование. примеры задач

На практике постоянно встречаются такие ситуации, когда достичь какого-то результата можно не одним, а многими различными способами. В подобной ситуации может оказаться и отдельно взятый человек, например, когда он решает вопрос о распределении своих расходов, и целое предприятие или даже отрасль, если необходимо определить, как использовать имеющиеся в их распоряжении ресурсы, чтобы добиться максимального выхода продукции, и, наконец, народное хозяйство в целом. Естественно, при большом количестве решений выбирается наилучшее. Математически это обычно сводится к нахождению наибольшего или наименьшего значения некоторой функции, т. е. к задаче: найти max (тіп)Дх) при условии, что переменная х ( обычно говорят — точка х) пробегает некоторое данное множество X. Пишут так:

J[x) -» max (min), х Є X. (7.1)

Определенная таким образом задача называется задачей оптимизации. Множество X называется допустимым множеством данной задачи, а функцияДх) — целевой функцией.

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

x = (Х|, х^,х^,

т. е. является точкой «-мерного арифметического пространства R". Соответственно множество X есть подмножество в R".

Очень многое зависит от того, в каком виде задается допустимое

множество X. Во многих случаях X выделяется из R" с помощью системы неравенств (нестрогих):

g (Х,х2, ...,*„)> О . г2(*|.*2>-.*іі)*0 (7.2)

gm(xi,x2, ...,*„)> О

гдеg,g2 gm — какие-то заданные функции в R".

Иначе говоря, X есть множество точек (jc,, х2,хп) G R", удовлетворяющих системе неравенств (7.2).

В этом случае задача оптимизации приобретает следующий вид. Даны функция п переменных f(xx, х2,хп) и система неравенств (7.2). Требуется найти max (min)/при условиях (7.2):

/(jC|, дг2,хп) -> max (min) при условиях (7.2).

Понятно, что следует найти не только само значение max (min)/, но и точку или точки, если их несколько, в которых это значение достигается. Такие точки называются оптимальными решениями. Множество всех оптимальных решений будем называть оптимальным множеством и обозначать X *.

Задачи подобного рода получили название задачи математического программирования (не следует путать математическое программирование с машинным). При этом функцию / называют целевой функцией, а неравенства g, > 0 (;' = 1, 2, т) — ограничениями.

В большинстве случаев в число ограничений входят условия неотрицательности переменных:

х{>0,х2>0,...,хп>0

или части переменных, но это, впрочем, не обязательно.

В зависимости от характера функций/, g,,gm различают разные виды математического программирования Наиболее простой и часто встречающийся случай,— когда эти функции являются линейными, т. е. каждая из них имеет вид

ах +а2х2 + ...+а„хп + Ь.

128

Тогда говорят о задаче линейного программирования. Линейное программирование оформилось как отдельный раздел прикладной математики в 40-50-х гг. XX в., когда выяснилось, что целый ряд задач из сферы планирования и управления может быть сформулирован в виде задач линейного программирования. Для решения таких задач разработаны эффективные методы, с одним из которых (так называемым симплекс-методом) мы будем дальше знакомиться. Подсчитано, что в настоящее время примерно80-85\%всех решаемых на практике задач оптимизации относится к задачам линейного программирования.

В дальнейшем, вместо того,чтобы одновременно рассматривать оба типа задач:/(х) -> max и f [х) -» min, мы будем изучать задачи только какого-нибудь одного типа. Такой подход оправдан тем, что всякая задача на максимум сводится к задаче на минимум (и наоборот) путем умножения целевой функции на -I.

Еще раз напомним, что в задаче оптимизации (7.1) множество X называется допустимым. Соответственно любая точка х Є X называется допустимым решением. Допустимое решение, дающее max (min) /, называется оптимальным решением. Неравенства (7.2) называются ограничениями.

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

1. Задача о банке (пример заимствован из книги Дж. Синки «Управление финансами в коммерческом банке»).

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

Другое дело ценные бумаги, особенно государственные. Их можно в любой момент продать, получив некоторую прибыль или, во всяком случае, без большого убытка. Поэтому существует правило, согласно которому коммерческие банки должны покупать в определенной пропорции ликвидные активы — ценные бумаги, чтобы компенсировать неликвидность кредитов. В нашем примере ликвидное ограничение таково: ценные бумаги должны составлять не менее 30\% средств, размещенных в кредитах и ценных бумагах.

9-3700 129

Пусть х — средства (млн долл.), размещенные в кредитах, у — средства, вложенные в ценные бумаги.

Имеем следующую систему линейных ограничений:

)х+у^