Общая постановка задачи математического программирования

В теории безусловного локального экстремума сравнивают частное значение f(x10;x20) функции у=f(xl,x2) в точке (x10;x20) с частными значениями f(xl,x2) этой функции во всех точках (xl,x2), близких к точке (x10;x20). Другими словами, в теории локального безусловного экстремума на независимые переменные x1 и х2 не накладываются никакие дополнительные условия, т.е. не требуется, чтобы переменные xl, и x2, удовлетворяли некоторым дополнительным ограничениям.

Найти локальный максимум (или локальный минимум) функции у=f(xl,x2) при условии, что независимые переменные xl, и x2 удовлетворяют ограничению g(xl,x2)=0 в виде равенства, то есть

f(xl,x2)→max (f(xl,x2)→min) (1.1)

при условии

g(xl,x2)=0 (1.2),

значит решить задачу на условный локальный максимум (минимум). Термин условный здесь появляется в связи с тем, что независимые переменные x1 и х2 удовлетворяют условию (ограничению)(1.2).

Вместо двух терминов (максимум и минимум) используется обобщенный термин экстремум. В задаче, описываемой (1.1), (1.2) на условный экстремум функцию f(xl,x2) принято называть целевой, ибо ее максимизация (или минимизация) часто есть формальное выражение какой-то цели (например, максимизации объема производства при фиксированных затратах). Функцию g называют функцией, задающей ограничение, или функцией связи, или ограничением.

Уравнение (1.2) есть уравнение нулевой линии (точнее множества) уровня функции g(xl,x2), ибо g(xl,x2)=t, где t=0. Поэтому задачу на условный локальный максимум (минимум) можно еще сформулировать так: среди точек нулевой линии уровня функции y=g(xl,x2) найти точку (x10;x20), в которой частное значение f(x10;x20) функции у=f(xl,x2) больше (или меньше) ее частных значений f(xl,x2) в остальных точках (xl,x2) этой линии, близких к точке (x10;x20).

Точка (x10;x20) называется точкой условного локального максимума (минимума) функции f(xl,x2), само частное значение f(x10;x20) - условным локальным максимумом (минимумом) функции f(xl,x2) при наличии ограничения g(xl,x2)=0.

Если значение f(x10;x20) функции f(xl,x2) больше (меньше) значений f(xl,x2) этой функции во всех точках (xl,x2) линии g(xl,x2)=0, то значение f(x10;x20) называется условным глобальным максимумом (минимумом) функции f(xl,x2) при наличии ограничения g(xl,x2)=0, a точка (x10;x20) - точкой условного глобального максимума (минимума) функции f(xl,x2).

Точка условного глобального максимума (минимума) функции f(xl,x2) является точкой условного локального максимума (минимума) этой функции. Обратное, вообще говоря, неверно.

В случае функции f(x1,...,xn) n независимых переменных x1,...,xn задача на условный максимум (минимум) формулируется так:

f(x1,...,xn)→max (f(x1,...,xn)→min) (1.3)

при условиях

g1 = g1(x1,...,xn) = 0

............................... (1.4)

gm = gm(x1,...,xn) = 0.

Если в задаче (1.1) - (1.2) на условный экстремум ограничение (1.2) в виде равенства заменяется на ограничение g(xl,x2)≤0 в виде неравенства, то мы получаем частный случай задачи математического программирования (ЗМП):

f(xl,x2)→max (f(xl,x2)→min) (1.5)

при условии

g(xl,x2) ≤0 (1.6).

Точка (xl,x2), удовлетворяющая ограничениям ЗМП, называется допустимым решением задачи математического программирования. Множество всех допустимых решений задачи математического программирования называется допустимым множеством этой задачи.

Точка (x10;x20) называется оптимальным решением ЗМП, если, во-первых, она есть допустимое решение этой ЗМП и если, во-вторых, на этой точке целевая функция достигает глобального максимума (в случае задачи максимизации) или глобального минимума (в случае задачи минимизации) среди всех точек, удовлетворяющих ограничениям.

Если в ЗМП функции f(x1,...,xn), g1(x1,...,xn), gm(x1,...,xn) линейны, то имеет место задача линейного программирования (ЗЛП), если хотя бы одна из функций нелинейная, имеет место задача нелинейного программирования (3НП).

В случае n-переменных ЗЛП на максимум имеет вид:

(1.7),

здесь m<n.

ЗЛП применяются для решения большого количества практических задач. Многие задачи, адекватно описывающие задачи организации, планирования и управления горным производством, относятся к классу о распределении, смеси или их комбинациям.

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

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