Нелинейное программирование

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

Нелинейность «встраивается» в модели программирования и в других случаях, например:

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

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

3. Выручка от реализации продукции. Спрос на продукцию компании может существенно зависеть от цен реализации: чем ниже цена продукта, тем больше объем реализации, несмотря на аналогичное снижение цен, производимое конкурентами. Следовательно, выручка от реализации продукции не изменяется пропорционально цене, и это обстоятельство должно быть отражено в целевой функции многопродуктовой модели с помощью нелинейного слагаемого. Для иллюстрации примем, что х(р) есть объем реализации, зависящий от цены р; тогда выручка от реализации равна рх(р). Пусть на представляющем для нас интерес интервале изменения р функция объема реализации от цены линейна, т. е. имеет вид х (р) = ap + b.Тогда слагаемые в целевой функции, относящиеся к выручке от реализации, являются квадратичными относительно управляющей переменной р и имеют вид (ар² + bр).

Пока не существует универсального метода решения задач нелинейного программирования. Задачи легко описываются системой уравнений, но методы решений крайне громоздки, фактически почти всегда для решения используется ЭВМ.

Сетевые задачи

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

Пусть имеются пункты производства A₁, А₂, … А_n с объемами производства в единицу времени (месяц, квартал), равными соответственно а₁, а₂,... а_n, и пункты потребления B₁, В₂,... В_n с объемами потребления, равными b₁, b₂,... b_n соответственно. Будем предполагать, что производство и потребление сбалансированы — сумма объемов производства равна сумме объемов потребления.

Предполагаются известными величины С_ij — затраты по перевозке единицы продукта из i-го пункта производства в j-й пункт потребления. Требуется найти такой план перевозок, при котором были бы удовлетворены потребности в пунктах В₁, В₂... В_n и при этом суммарные затраты на перевозку были бы минимальны. Обозначая через х_ij количество продукта, перевозимое из i-го

пункта производства в j-й пункт потребления, приходим к следующей математической формулировке задачи.

Транспортная задача решается симплекс методом [8, с.46], [4, с.124].