§ 5. Приближенное решение задач с сепарабельными функциями

Изложим теперь общую идею приближенного решения задач с сепарабельными функциями. В математике известны методы, позволяющие заменить любую непрерывную функцию ломаной. Воспользуемся одним из этих методов и построим приближенную задачу к задаче (2.9)-(2.10), проводя кусочно-линейную аппроксимацию функций g_ij (x_j) и f_j (x_j). Далее будет показано, как определяется оптимальное решение полученной приближенной задачи.

На примере функции одной переменной покажем, как проводится такая аппроксимация. Рассмотрим некоторую непрерывную функцию, определенную для всех x из интервала c₁≤x≤c₂ (рис. 2.4). Выберем на этом интервале r + 1 точку x_k таким образом, чтобы x₀ = c₁, x₁<x²<...<x_k<... <x_r = c₂. Этим точкам будут соответствовать значения функции y_k (x_k). Соединим попарно точки x_ky_k и x_k+1y_k+1 при всех k = 0, ..., r - 1 отрезками прямых. В результате получится кусочно-линейная функция , которая аппроксимирует функцию y(x). Такая аппроксимация может быть сделана со сколь угодно большой точностью путем выбора соответствующего разбиения интервала c₁≤x≤c₂.

Рис. 2.4

Найдем аналитический вид функции . Если x лежит в интервале x_k≤x≤x_k+1, то для можно написать

(2.18)

Любое значение x в интервале x_k≤x≤x_k+1 можно представить в виде x = λx_k+1 + (1-λ)x_k, где 0≤λ≤1.

Обозначим λ = λ_k+1, 1-λ = λ_k. Тогда имеем

где λ_k + λ_k+1 = 1, λ_k ≥ 0, λ_k+1 ≥0.

Обобщая эти выражения таким образом, чтобы с их помощью определить любое x из c₁≤x≤c₂ и любую соответствующую функцию , можем написать:

(2.20)

где

Если условиться, что отличными от нуля для каждых x_k и y_k являются лишь не более двух соседних λ_k, то функция (2.20) является аналитическим выражением кусочно-линейной функции, пример которой изображен на рис. 2.4.

Воспользуемся таким методом аппроксимации для построения функций, приближенных к g_ij(x_j) и f_j(x_j). Будем считать, что в задаче (2.9)-(2.10) непрерывны все функции g_ij (x_j) и f_j (x_j). Выберем на интервале c_1j≤x_j≤c_2j, который может пробегать переменная x_j (j = 1, 2, ..., n), r_j + 1 точку x_kj и, используя описанный выше метод аппроксимации, построим кусочно-линейные функции и . Если интервал, который пробегает переменная x_j, точно не известен, то предварительно необходимо грубо оценить, в каких пределах меняется x_j, и производить разбиение этого расширенного интервала d_1j<x_j<d_2j, где d_1j<c_1j и d_2j>c_2j. В результате мы получим задачу, приближенную к задаче (2.9)-(2.10):

(2.21)

найти максимум (минимум)

Все функции и в соответствии с (2.20) можно записать в виде

(2.22)

(2.23)

где f_kj = f_j (x_kj) и g_kij = g_ij (x_kj) - фиксированные числа,

причем для данного j не более двух соседних λ_kj могут быть положительными. Отметим, что при построении функций и используется одно и то же разбиение интервала c_1j<x_j<c_2j, на котором точки x_kj по условию выбираются так, чтобы обеспечить удовлетворительную точность аппроксимации всех функций f_j (x_j) и g_ij (x_j).

Подстановка выражений (2.22) и (2.23) в (2.21) позволяет получить форму записи приближенной задачи, отличающуюся от (2.21) тем, что вместо переменных x_j используются переменные λ_kj

(2.24)

найти минимум (максимум) Таким образом, задача с сепарабельными функциями сведена к задаче линейного программирования. Далее можно искать решение этой задачи с помощью симплексного метода. Причем если функции f_j (x_j) выпуклые (вогнутые) и g_ij (x_j) обладают свойствами, при которых множество допустимых решений выпукло, то при решении приближенной задачи как задачи линейного программирования получается оптимальное решение даже в том случае, когда при построении базиса не учитывается требование того, чтобы при каждом j не более двух соседних λ_kj были положительны. Доказательство этого положения можно найти в более подробных курсах нелинейного программирования [8].

Следует, однако, иметь в виду то обстоятельство, что задача вида (2.9) - (2.10) даже небольшой размерности может свестись к задаче (2.24) очень большой размерности. Поэтому может оказаться выгодным вначале решать задачу при довольно грубом разбиении интервала изменения переменных, а затем уточнять результат, используя более мелкое разбиение в окрестности полученного грубого решения. При этом если некоторая переменная x_j входит в задачу линейно, т. е. g_ij (x_j) = a_ijx_j и f_j (x_j) = c_jx_j, то нет необходимости выражать x_j через λ_kj, а можно просто использовать x_j как переменную. Это обстоятельство позволяет уменьшить размерность задачи.

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

Возьмем за основу линейную задачу, решенную ранее (см. гл. I, § 5, п. 3). В этой задаче мы предполагали все a_ij и c_j заданными числами, что очень грубо отражает действительное положение, складывающееся на практике. Обычно в производстве всегда имеется возможность появления брака, т. е. расходования ресурсов без выпуска изделий. Процент брака может не быть постоянной величиной; например, он может увеличиваться о ростом интенсивности производства.

Допустим, что специальные исследования, проведенные на данном предприятии, показали, что зависимости себестоимости от объема производства изделий в первом приближении могут считаться линейными функциями, т. е. C_j = c_j⁰ + c_j¹x_j (все c_j⁰≥0, c_j¹≥0, j = 1, 2), и из-за наличия брака расход ресурсов на изготовление изделий также в первом приближении линейно зависит от объема производства этих изделий (все в расчете на тысячу штук);

Подставляя C_j и a_ij в условия линейной задачи, приходим к следующей нелинейной задаче;

найти

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

или в сокращенной записи;

найти

(2.25)

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

Сравнивая задачи (2.25) и (2.9)-(2.10), нетрудно видеть, что в нашем примере

и

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

Проверим, обладают ли функции f_j (x_j) и g_ij (x_j) задачи (2.25) свойствами выпуклости или вогнутости. В данном случае достаточно убедиться в том, что любая из функций f_j (x_j) и g_ij (x_j) обладает этим свойством. Возьмем, например, функцию f₁ (x₁) = (P₁ - c⁰₁)x₁ - c¹₁x²₁ и составим для нее неравенство (2.4). Для этого выберем две произвольные точки x₁₁ и x₁₂ и определим при любом 0≤λ≤1 значение функции

и сумму

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

так как все сомножители λ, (1-λ) и (x₁₂ - x₁₁)² неотрицательные числа. Функция f₁ (x₁) - вогнутая, поскольку

Совершенно аналогично доказывается выпуклость функции g_ij (x_j). Итак, задача (2.25) является задачей выпуклого программирования. Перейдем к приближенному решению этой задачи.

Прежде всего определим максимальные значения переменных x₁ и x₂. Для этого сначала в ограничениях положим x₂ = 0, решим три получившихся квадратных уравнения относительно x₁ и выберем из этих решений минимальное: I

Знак "-" перед корнем в решениях не учитываем, так как по условию x₁≥0. Аналогично имеем

Обозначим эти значения следующим образом: (x₁)_max = α и (x₂)_max = β. Таким образом, переменные x₁ и x₂ могут изменяться в интервалах 0≤x₁≤α, 0≤x₂≤β. Разобьем первый из этих интервалов, например, на пять одинаковых отрезков точками x₀₁ = 0, x₁₁, x₂₁, x₃₁, x₄₁, x₅₁ = α и второй - точками x₀₂ = 0, x₁₂, x₂₂, x₃₂, x₄₂, x₅₂ = β. Соответственно координаты точек внутри интервалов есть

Не представляет труда непосредственно убедиться в том, что любое значение x₁ из интервала (0, α) может быть получено с помощью выражения

где все

То же самое можно сказать и о x₂. Тогда кусочно-линейные функции и f_j (x_j) запишутся в следующем виде:

(2.26)

Функции и - линейные функции переменных λ_kj, так как все выражения в скобках - заданные постоянные числа. Таким Образом, от нелинейной задачи 2.25) путем линейной аппроксимации мы перешли к следующей линейной задаче:

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

(2.27)

Далее линейная задача (2.27) может решаться симплексным методом, причем без учета ограничительных условий на выбор λ_kj, так как мы показали, что задача (2.25) является задачей выпуклого программирования.

Проиллюстрируем решение этой задачи на конкретном примере. Используем те же численные условия, что и в лисиной задаче, и дополнительно будем считать, что все a'_ij = 1 и c'_j = 0,1.

При этих условиях задача имеет вид:

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

Решая квадратные уравнения

находим (x₁)_max≥min (6, 2; 4,9; 5,8} = 4,9.

Аналогично имеем (x₂)_max≥min {4, 2; 7; 5,8} = 4,2. Для удобства расчетов примем, что оба переменных изменяются в интервале (0;5), который и разобьем на 5 отрезков единичной длины, т. е. имеем:

Запишем функции и :

и аналогично

Подставляя эти линейные функции в условия задачи (2.27), мы приходим к задаче линейного программирования вида (2.24) с тремя ограничениями и тринадцатью неизвестными (с учетом искусственных переменных), которая далее может решаться с помощью стандартной процедуры симплексного метода, описанной в § 5 гл. I. Оптимальное решение находится после того, как получены значения λ_kj:

При этом значение функции цели есть