Decomposition algorithm in a nonlinear transport problem with storage

Resumo

Previously, a method was proposed for solving the classical transport problem in an integer formulation, based on the decomposition of the original problem into a sequence of two-dimensional problems with recalculation of the coefficients of the objective functions. The method was then extended to cover additional points of production and consumption. This paper considers the case when transportation costs for additional points are proportional to arbitrary powers of the transportation volume.

Texto integral

Введение. Известные алгоритмы решения транспортных задач основаны на методе улучшения плана в линейном программировании [1, 2]. Однако распространение на более широкие транспортные постановки сопровождается трудностями. В [3] предложен декомпозиционный метод решения классической транспортной задачи. Основой для этого метода являются подходы для оптимизации сетевых задач [4–6]. В [7] эти идеи используются для решения транспортной задачи с дополнительными пунктами производства и потребления (со складами), для которых установлены квадратичные штрафы. В настоящей работе указанные подходы распространяются на нелинейные зависимости.

1. Постановка задачи. Имеется, как и в классической транспортной задаче, m пунктов производства и n пунктов потребления. В каждом i-м пункте производства задан объем производства $a_i, i=\overline{\mathrm{1,}m}$, в каждом j-м – объем потребления $b_j, j=\overline{\mathrm{1,}n}$. Кроме того, существуют еще n дополнительных пунктов производства. Каждый j-й дополнительный пункт производства может поставлять свою продукцию только j-му пункту потребления. Объем производства в дополнительных пунктах производства не ограничен. Имеется также m дополнительных пунктов потребления. Каждому i-му дополнительному пункту потребления продукцию может поставлять только i-й обычный пункт производства. Объем потребления в дополнительных пунктах не ограничен. Указанные промежуточные пункты можно интерпретировать как склады.

Стоимость перевозки из j-го дополнительного пункта производства пропорциональна p_j – степени от объема производства. Стоимость перевозки в i-й дополнительный пункт потребления пропорциональна r_i – степени от объема перевозки. Необходимо минимизировать суммарные затраты на перевозки.

Формальная запись задачи имеет вид

${\displaystyle \sum }_{j=1}^n{x}_{ij}+y_i=a_i, i=\overline{\mathrm{1,}m},$ (1.1)

${\displaystyle \sum }_{i=1}^m{x}_{ij}+w_j=b_j, j=\overline{\mathrm{1,}n},$ (1.2)

${\displaystyle \sum }_{i=1}^m{\displaystyle \sum }_{j=1}^n{c}_{ij}{x}_{ij}+{\displaystyle \sum }_{i=1}^m{d}_i{y}_i^{r_i}+{\displaystyle \sum }_{j=1}^n{e}_j{w}_j^{p_j} \to \min ,$ (1.3)

$x_{ij}\ge \mathrm{0,} y_i\ge \mathrm{0,} w_j\ge \mathrm{0,} c_{ij}\ge \mathrm{0,} d_i, e_j-\text{целые.}$ (1.4)

Здесь x_ij – количество продукта, перевозимого из пункта j в пункт i; y_i – количество продукта, доставляемого в дополнительный j-й пункт потребления; w_j – количество продукта, вывозимого из дополнительного j-го пункта производства. Кроме того, будем считать c_ij четными числами, что не ограничивает общности рассмотрения.

2. Метод решения задачи. 2.1. П е р в ы й  э т а п. Сформируем m + n одномерных задач. Первые m одномерных задач имеют вид ( $i=\overline{\mathrm{1,}m}$ – фиксировано):

${\displaystyle \sum }_{j=1}^n{x}_{ij}+y_i= a_i,$ (2.1)

${\displaystyle \sum }_{j=1}^n{c}_{ij}^1{x}_{ij}+d_i{y}_i^{r_i}\to \text{min},$ (2.2)

$c_{ij}^1=\frac{{\text{c}}_{ij}}{2}, 0\le {\text{x}}_{ij}\le \text{min}\left(a_i,b_j\right), {\text{x}}_{ij},{\text{y}}_i\ge 0-\text{целые.}$ (2.3)

Вторые n оптимизационных задач с одним ограничением запишем как (j фиксировано):

${\displaystyle \sum }_{i=1}^m{x}_{ij}+w_j= b_j,$ (2.4)

${\displaystyle \sum }_{i=1}^m{c}_{ij}^2{x}_{ij}+e_j{w}_j^{p_j}\to \text{min},$ (2.5)

$c_{ij}^2=\frac{{\text{c}}_{ij}}{2}, 0\le {\text{x}}_{ij}\le \text{min}\left(a_i,b_j\right).$ (2.6)

Здесь $x_{ij}, w_j\ge 0$ – целые.

Задачи (2.1)–(2.3) решаются следующим образом. Сравниваем d_i с $c_{i{j}^{*}}^1=\underset{j}{\min }{c}_{ij}^1$ (i фиксировано). Если $d_i>c_{i{j}^{*}}^1$, то полагаем $x_{i{j}^{*}}=\min (a_i, b_{j^{*}})$. При $b_{j^{*}}<a_i$ сравниваем $d_i$ с $c_{i{j}^{**}}^1=\underset{j\ne j^{*}}{\min }{c}_{ij}^1$. Если $d_i>c_{i{j}^{**}}^1$, то полагаем $x_{i{j}^{**}}=\min (a_i-b_{j^{*}}, b_{j^{**}})$ и т.д. Если имеет место неравенство $d_i\le c_{i{j}^{*}}^1$ (сразу или после нескольких назначений линейных переменных), то ищется целочисленный минимум выражения $d_i{y}_i^{r_i}+c_{i{j}^{*}}\left(\min (a_i, b_{j^{*}}\right)-y_i)$.

Обозначим через $y_i^{*}$ оптимальное значение $y_i$. Тогда, очевидно, $x_{i{j}^{*}}=\min (a_i, b_{j^{*}})-y_i^{*}$. Если при этом (2.1) не является равенством, то далее задачи (2.1)–(2.3) решаются как линейные (см., например, [3]). Задачи вида (2.4)–(2.6) решаются вполне аналогичным образом.

Пусть все $m+n$ задач вида (2.1)–(2.3) и (2.4)–(2.6) решены. Если объединение оптимальных решений всех $m+n$ задач является допустимым решением исходной задачи (1.1)–(1.4), то, очевидно, тем самым получено оптимальное решение задачи (1.1)–(1.4). Если оптимальное решение задачи (1.1)–(1.4) не получено, то начинаем итерационный циклический процесс решения $m x n$ оптимизационных задач с двумя ограничениями.

2.2. В т о р о й  э т а п. Первая двумерная задача имеет вид:

${\displaystyle \sum }_{j=1}^n{x}_{1j}+y_1= a_1,$ (2.7)

${\displaystyle \sum }_{i=1}^m{x}_{i1}+w_1= b_1,$ (2.8)

${\displaystyle \sum }_{j=1}^n{c}_{1j}^1{x}_{1j}+{\displaystyle \sum }_{i=1}^m{c}_{i1}^2{x}_{i1}+e_1{w}_1^{p_1}+d_1{y}_1^{r_1}\to \text{min},$ (2.9)

$0\le {\text{x}}_{ij}\le \text{min}\left(a_i,b_j\right).$ (2.10)

Здесь $x_{ij}, y_i\ge \mathrm{0,} w_1\ge 0$ – целые.

Задача (2.7)–(2.10) решается следующим образом. Единственной общей переменной в (2.7) и (2.8) является $x_{11}$. Поэтому решение задачи (2.7)–(2.10) зависит от соотношения между $c_{11}=c_{11}^1+c_{11}^2$ и другими коэффициентами в целевой функции (2.9).

Пусть

$c_{11}<\underset{i,j\ne 1}{\min }\left(c_{1j}^1+c_{i1}^2, c_{1j}^1+e_1,c_{i1}^2+d_1, d_1+e_1\right).$ (2.11)

Тогда, очевидно, что в оптимальном решении задачи (2.7)–(2.10) $x_{11}=\text{min}\left(a_1,b_1\right)$, после чего задача (2.7)–(2.10) распадается на две одномерные, рассмотренные выше.

Определим новые значения $c_{11}^1$ и $c_{11}^2$ следующим образом. Возьмем целочисленные значения $c_{11}^1$ и $c_{11}^2$, подчиняющиеся условиям $c_{11}^1\le d_1,c_{11}^2\le e_1.$ Пусть $c_{11}<\underset{i,j\ne 1}{\min }(c_{1j}^1+$$+c_{i1}^2, c_{1j}^1+e_1,c_{i1}^2+d_1, d_1+e_1)=d_1+e_1$$+c_{i1}^2, c_{1j}^1+e_1,c_{i1}^2+d_1, d_1+e_1)=d_1+e_1$. Очевидно, что тогда $c_{11}^1=d_1,c_{11}^2=e_1$. При новых значениях $c_{11}^1$ и $c_{11}^2$ объединение оптимальных решений соответствующих одномерных задач будет совпадать с оптимальным решением задачи (2.7)–(2.10).

Допустим, что $c_{11}>\underset{i,j\ne 1}{\min }\left(c_{1j}^1+c_{i1}^2, c_{1j}^1+e_1,c_{i1}^2+d_1, d_1+e_1\right)$. Тогда, исключив общую переменную, решаются две одномерные задачи. Далее вычисляются следующие величины:

$\Delta u_0=d_1\left[{\left(y_1^{*}\right)}^{r_1}-{\left(y_1^{*}-1\right)}^{r_1}\right]+e_1\left[{\left(w_1^{*}\right)}^{p_1}-{\left(w_1^{*}-1\right)}^{p_1}\right]$,

$\Delta u_1=d_1\left[{\left(y_1^{*}\right)}^{r_1}-{\left(y_1^{*}-1\right)}^{r_1}\right]+c_{i^{*}1}^2$,

$\Delta u_2=e_1\left[{\left(w_1^{*}\right)}^{p_1}-{\left(w_1^{*}-1\right)}^{p_1}\right]+c_{1j^{*}}^1$,

$\Delta u_3=c_{1j^{*}}^1+c_{i^{*}1}^2$.

Здесь $y_1^{*},w_1^{*}$ – значения переменных $y_1,w_1$ в оптимальных решениях одномерных задач без $x_{11}$, а $c_{1j^{*}}^1, c_{i^{*}1}^2$ – максимальные коэффициенты при положительных значениях переменных $x_{1j}, x_{i1}.$

Если $\underset{0\le k\le 3}{\max }\Delta u_k=\Delta u_3$ и $c_{11}>c_{1j^{*}}^1+ c_{i^{*}1}^2$, то двумерная задача решена. При этом $c_{11}^1\ge c_{1j^{*}}^1$ и $c_{11}^2\ge c_{i^{*}1}^2$. Если $\underset{0\le k\le 3}{\max }\Delta u_k=\Delta u_3$ и $c_{11}=c_{1j^{*}}^1+ c_{i^{*}1}^2$, то, обозначив через $x_{1j^{*}}^{*}$ и $x_{i^{*}1}^{*}$ значения соответствующих переменных в оптимальных решениях одномерных задач, в двумерную задачу запишем ограничения

$x_{1j^{*}}+x_{11}=x_{1j^{*}}^{*}, x_{i^{*}1}+x_{11}=x_{i^{*}1}^1, c_{11}^1=c_{1j^{*}}^1$ и $c_{11}^2=c_{i^{*}1}^2$.

Если $\underset{0\le k\le 3}{\max }\Delta u_k=\Delta u_3$ и $c_{11}<c_{1j^{*}}^1+ c_{i^{*}1}^2$, то $x_{11}$ увеличивается на $\min \left(x_{1j^{*}}, x_{i^{*}1}\right)$ (или до своего максимума). Если при этом $x_{11}$ достигает максимума, то решение двумерной задачи окончено и $c_{11}^1\le c_{1j^{*}}^1, c_{11}^2\le c_{i^{*}1}^2$. В противном случае пересчитываются $\Delta u_k, k=\overline{\mathrm{0,} 3}$, и процесс решения продолжается.

Если $\underset{0\le k\le 3}{\max }\Delta u_k=\Delta u_2$, то при $c_{11}>\Delta u_2$ решение двумерной задачи окончено и $c_{11}^1\ge c_{1j^{*}}^1$, $c_{11}^2\ge e_1\left[{\left(w_1^{*}\right)}^{p_1}-{\left(w_1^{*}-1\right)}^{p_1}\right]$. При $c_{11}=\Delta u_2$ полагаем $c_{11}^1=c_{1j^{*}}^1, c_{11}^2=$$=e_1\left[{\left(w_1^{*}\right)}^{p_1}-{\left(w_1^{*}-1\right)}^{p_1}\right]$. При $c_{11}<\Delta u_2$ увеличивается $x_{11}$, а $w_1$ и $x_{1j^{*}}$ уменьшаются до момента, когда $\Delta u_2$ перестает быть максимумом. Затем пересчитываются все $\Delta u_k$ и процесс решения продолжается.

Если $\underset{0\le k\le 3}{\max }\Delta u_k=\Delta u_1$, то при $c_{11}>\Delta u_1$ решение двумерной задачи окончено и $c_{11}^1\ge d_1\left[{\left(y_1^{*}\right)}^{r_1}-{\left(y_1^{*}-1\right)}^{r_1}\right], c_{11}^2\ge c_{i^{*}1}^2$. При $c_{11}=\Delta u_1 c_{11}^1=d_1\left[{\left(y_1^{*}\right)}^{r_1}-{\left(y_1^{*}-1\right)}^{r_1}\right]$, $c_{11}^2=c_{i^{*}1}^2$. При $c_{11}<\Delta u_1$ все аналогично случаю $c_{11}<\Delta u_2$.

Если $\underset{0\le k\le 3}{\max }\Delta u_k=\Delta u_0$ и $c_{11}<\Delta u_0$, то $y_1^{*}$ и $w_1^{*}$ уменьшаются, а $x_{11}$ увеличивается до потери $\Delta u_0$ статуса максимума. Далее все $\Delta u_k$ пересчитываются и процесс решения продолжается.

Так же, как и в линейном случае [3], имеет место монотонное возрастание суммы значений целевых функций в оптимальных решениях всех $m+n$ одномерных задач в циклическом процессе решения двумерных задач и их разъединения на одномерные задачи. Сумма эта, очевидно, ограничена сверху, процесс – целочисленен, следовательно, за конечное число шагов достигается предел. Точно так же, как и в линейном случае [3], если объединение оптимальных решений одномерных задач (в предельном состоянии) является допустимым решением исходной задачи (1.1)–(1.4), то оно выступает ее оптимальным решением. В противном случае, как и в [3], образуются обобщенные производители и потребители.

3. Пример. Рассмотрим транспортную задачу с дополнительными пунктами потребления и производства со степенной зависимостью от объема производства и потребления в дополнительных пунктах. Ограничения и целевую функцию запишем следующим образом:

$x_{11}+x_{12}+x_{13}+y_1=10$, $x_{21}+x_{22}+x_{23}+y_2=20$, $x_{31}+x_{32}+x_{33}+y_3=30$,

$x_{11}+x_{21}+x_{31}+w_1=6$, $x_{12}+x_{22}+x_{32}+w_2=22$, $x_{13}+x_{23}+x_{33}+w_3=32$,

$8x_{11}+12x_{12}+18x_{13}+y_1^2+16x_{21}+20x_{22}+18x_{23}+2y_2^3+16x_{31}+18x_{32}+$

$+20x_{33}+3y_3^3+w_1^2+2w_2^3+3w_3^3\to \text{min}$.

3.1. П е р в ы й  э т а п. 3. 1. 1. Первая одномерная задача:

$x_{11}+x_{12}+x_{13}+y_1=10$,

$4x_{11}+6x_{12}+9x_{13}+y_1^2\to \text{min}$.

Здесь $c_{11}^1>d_1$, поэтому ищем целочисленный минимум выражения $y_1^2+4\left(10-y_1\right)$:

$\underset{y_1\ge 0}{\min }\left[y_1^2+4\left(10-y_1\right)\right]$,

$f^{\prime }\left(y_1\right)=2y_1-4=0$,

$y_1=2$,

$x_{11}=\mathrm{6,} x_{12}=2$.

3. 1. 2. Вторая одномерная задача:

$x_{21}+x_{22}+x_{23}+y_2=20$,

$8x_{21}+10x_{22}+9x_{23}+2y_2^3\to \text{min}$.

Здесь $c_{21}^1>d_2$, поэтому вычисляем целочисленный минимум $2y_2^3+8\left(20-y_2\right)$:

$\underset{y_2\ge 0}{\min }\left[2y_2^3+8\left(20-y_2\right)\right]$,

$f^{\prime }\left(y_2\right)=6y_2^2-8=0$,

$y_2=\frac{2}{\sqrt{3}}$.

Целочисленный минимум достигается при $y_2=1$:

$x_{21}=\mathrm{6,} x_{22}=13$.

3. 1. 3. Третья одномерная задача:

$x_{31}+x_{32}+x_{33}+y_3=30$,

$8x_{31}+9x_{32}+10x_{33}+3y_3^3\to \text{min}$.

Здесь $c_{31}^1>d_1$, ищем целочисленный минимум:

$\underset{y_3\ge 0}{\min }\left[3y_3^3+8\left(30-y_3\right)\right]$,

$f^{\prime }\left(y_3\right)=9y_3^2-8=0$,

$y_3=\frac{2\sqrt{2}}{3}$.

Целочисленный минимум достигается при $y_3=1$:

$x_{31}=\mathrm{6,} x_{32}=\mathrm{22,} x_{33}=1$.

3. 1. 4. Четвертая одномерная задача:

$x_{11}+x_{21}+x_{31}+w_1=6$,

$4x_{11}+8x_{21}+8x_{31}+w_1^2\to \text{min}$.

Здесь $c_{11}^2>e_1$, находим минимум выражения $w_1^2+4\left(6-w_1\right)$:

$\underset{w_1\ge 0}{\min }\left[w_1^2+4\left(6-w_1\right)\right]$,

$f^{\prime }\left(w_1\right)=2w_1-4=0$,

$w_1=2$,

$x_{11}=\mathrm{4,} x_{21}=\mathrm{0,} x_{31}=0$.

Далее решать одномерные задачи не имеет смысла, так как, например, в третьей задаче $x_{31}=6$, а в четвертой $x_{31}=0$.

3.2. В т о р о й  э т а п. 3. 2. 1. Первая двумерная задача:

$x_{11}+x_{12}+x_{13}+y_1=10$,

$x_{11}+x_{21}+x_{31}+w_1=6$,

$8x_{11}+6x_{12}+9x_{13}+8x_{21}+8x_{31}+y_1^2+ w_1^2\to \text{min}$.

Здесь $c_{11}>d_1+e_1$, поэтому решаются две одномерные задачи.

3. 2. 1. 1. Первая одномерная задача:

$x_{12}+x_{13}+y_1=10$,

$6x_{12}+9x_{13}+y_1^2\to \text{min}$.

Здесь $c_{12}^1>d_1$, поэтому вычисляем минимум:

$\underset{y_1\ge 0}{\min }\left[y_1^2+6\left(10-y_1\right)\right]$,

$f^{\prime }\left(y_1\right)=2y_1-6=0$,

$y_1=3$,

$x_{12}=\mathrm{7,} x_{13}=0$.

3. 2. 1. 2. Вторая одномерная задача:

$x_{21}+x_{31}+w_1=6$,

$8x_{21}+8x_{31}+w_1^2\to \text{min}$.

Здесь $c_{21}^2>e_1$, ищем минимум:

$\underset{w_1\ge 0}{\min }\left[w_1^2+8\left(6-w_1\right)\right]$,

$f^{\prime }\left(w_1\right)=2w_1-8=0$,

$w_1=4$,

$x_{21}+ x_{31}=2$,

$\Delta u_0=1\left(9-4\right)+1\left(16-9\right)=12$,

$\Delta u_1=5+8=13$,

$\Delta u_2=7+6=13$,

$\Delta u_3=6+8=14$.

Здесь $c_{11}<\Delta u_3$, поэтому $x_{11}=\mathrm{2,} x_{21}=\mathrm{0,} x_{31}=0$, $x_{12}=\mathrm{5,} y_1=\mathrm{3,} w_1=4$:

$\Delta u_0=1\left(9-4\right)+1\left(16-9\right)=12$,

$\Delta u_1=5+0=5$,

$\Delta u_2=7+6=13$,

$\Delta u_3=6+0=6$.

Здесь $c_{11}<\Delta u_2$, поэтому $x_{11}$ увеличивается за счет $x_{12}$ и $w_1$:

$x_{11}=\mathrm{3,} x_{12}=\mathrm{4,} w_1=\mathrm{3,} y_1=3$,

$\Delta u_0=1\left(9-4\right)+1\left(9-4\right)=10$,

$\Delta u_1=5+0=5$,

$\Delta u_2=5+6=11$,

$\Delta u_3=6+0=6$.

Снова $c_{11}<\Delta u_2$, поэтому $x_{11}=\mathrm{4,} x_{12}=\mathrm{3,} w_1=\mathrm{2,} y_1=3$:

$\Delta u_0=5+3=8$,

$\Delta u_1=5+0=5$,

$\Delta u_2=3+6=9$,

$\Delta u_3=6+0=6$.

Снова $c_{11}<\Delta u_2$, поэтому $x_{11}=\mathrm{5,} x_{12}=\mathrm{2,} w_1=\mathrm{1,} y_1=3$:

$\Delta u_0=5+1=6$,

$\Delta u_1=5+0=5$,

$\Delta u_2=1+6=7$,

$\Delta u_3=6+0=6$.

Здесь $c_{11}>\Delta u_2$, поэтому решение второй одномерной задачи окончено.

3. 2. 2. Вторая двумерная задача:

$x_{11}+x_{12}+x_{13}+y_1=10$,

$x_{12}+x_{22}+x_{32}+w_2=22$,

$6x_{11}+12x_{12}+9x_{13}+10x_{22}+9x_{32}+y_1^2+ 2w_2^3\to \text{min}$.

Имеем $c_{12}=12>d_1+e_2=3$, поэтому сначала $x_{12}$ исключается и решаются две одномерные задачи.

3. 2. 2. 1. Первая одномерная задача:

$x_{11}+x_{13}+y_1=10$,

$6x_{11}+9x_{13}+y_1^2\to \text{min}$.

Здесь $c_{11}^1>d_1$, поэтому находим минимум:

$y_1^3+6\left(10-y_1\right)$,

$f^{\prime }\left(y_1\right)=3y_1^2-6=0$,

$y_1^2=2$,

$y_1=\sqrt{2}$.

Целочисленный минимум достигается при $y_1=1$. При этом $x_{11}=\mathrm{6,} x_{13}=3$.

3. 2. 2. 2. Вторая одномерная задача:

$x_{22}+x_{32}+w_2=22$,

$10x_{22}+9x_{32}+2w_2^3\to \text{min}$.

Имеем $c_{32}>e_2$, поэтому отыскиваем целочисленный минимум:

$2w_2^3+9\left(22-w_2\right)$,

$f^{\prime }\left(w_2\right)=6w_2^2-9=0$,

$w_2^2=1.5$,

$w_2=\sqrt{1.5}$.

Целочисленный минимум достигается при $w_2=1$. При этом $x_{32}=\mathrm{21,} x_{22}=0$:

$\Delta u_0=1\left(1-0\right)+2\left(1-0\right)=3$,

$\Delta u_1=1\left(1-0\right)+9=10$,

$\Delta u_2=2\left(1-0\right)+9=11$,

$\Delta u_3=9+9=18$.

Здесь $12=c_{12}<\Delta u_3=18$, поэтому $x_{12}=\min \left(\mathrm{21,} 3\right)=3$. Имеем $x_{12}=\mathrm{3,} x_{11}=\mathrm{6,} x_{13}=\mathrm{0,}$ $y_1=\mathrm{1,} x_{22}=\mathrm{0,} x_{32}=\mathrm{18,} w_2=1$ $y_1=\mathrm{1,} x_{22}=\mathrm{0,} x_{32}=\mathrm{18,} w_2=1$:

$\Delta u_0=3$,

$\Delta u_1=1+9=10$,

$\Delta u_2=2+6=8$,

$\Delta u_3=9+6=15$.

Здесь $12=c_{12}<\Delta u_3=15$, поэтому $x_{12}$ увеличивается на $\min \left(\mathrm{9,} 6\right)=6; x_{12}=9$. Имеем $x_{12}=\mathrm{9,} x_{11}=\mathrm{0,} x_{13}=\mathrm{0,}$ $x_{12}=\mathrm{9,} x_{11}=\mathrm{0,} x_{13}=\mathrm{0,}$$y_1=\mathrm{1,} x_{22}=\mathrm{0,} x_{32}=\mathrm{12,} w_2=1$:

$\Delta u_0=3$,

$\Delta u_1=1\left(1-0\right)+9=10$,

$\Delta u_2=2+0=2$,

$\Delta u_3=0+9=9$.

Здесь $12=c_{12}>\Delta u_1=10$. Решение двумерной задачи окончено. При этом $c_{12}^1=\mathrm{3,} c_{12}^2=9$.

3. 2. 3. Третья двумерная задача:

$x_{11}+x_{12}+x_{13}+y_1=10$,

$x_{13}+x_{23}+x_{33}+w_3=32$,

$6x_{11}+3x_{12}+18x_{13}+9x_{23}+10x_{33}+y_1^3+ 3w_3^3\to \text{min}$.

Здесь $c_{13}>d_1+e_3$, поэтому решаются две одномерные задачи.

3. 2. 3. 1. Первая одномерная задача:

$x_{11}+x_{12}+y_1=10$,

$6x_{11}+3x_{12}+y_1^3\to \text{min}$.

Здесь $c_{12}>d_1$, поэтому находим минимум:

$y_1^3+3\left(10-y_1\right)$,

$f^{\prime }\left(y_1\right)=3y_1^2-3=0$,

$y_1=1$.

Тогда $x_{12}=9$. Первая одномерная задача решена.

3. 2. 3. 2. Вторая одномерная задача:

$x_{23}+x_{33}+w_3=32$,

$9x_{23}+10x_{33}+3w_3^3\to \text{min}$.

Здесь $c_{23}>e_3$, поэтому вычисляем минимум:

$3w_3^3+9\left(30-w_3\right)$,

$f^{\prime }\left(w_3\right)=9w_3^2-9=0$,

$w_3=1$,

$x_{23}=\mathrm{20,} x_{33}=11$,

$\Delta u_0=1\left(1-0\right)+3\left(1-0\right)=4$,

$\Delta u_1=1\left(1-0\right)+10=11$,

$\Delta u_2=3\left(1-0\right)+3=6$,

$\Delta u_3=6+11=17$.

Здесь $18=c_{13}>\Delta u_3=17$, поэтому двумерная задача решена: $c_{13}^1=\mathrm{7,} c_{13}^2=11$.

3. 2. 4. Четвертая двумерная задача:

$x_{21}+x_{22}+x_{23}+y_2=20$,

$x_{11}+x_{21}+x_{31}+w_1=6$,

$0x_{11}+16x_{21}+10x_{22}+9x_{23}+8x_{31}+2y_2^3+ w_1^3\to \text{min}$.

Здесь $16=c_{21}>d_2+e_1=3$, поэтому решаются две одномерные задачи.

3. 2. 4. 1. Первая одномерная задача:

$x_{22}+x_{23}+y_2=20$,

$10x_{22}+9x_{23}+2y_2^3\to \text{min}$.

Здесь $c_{23}>d_2$, поэтому ищем минимум:

$2y_2^3+9\left(20-y_2\right)$,

$f^{\prime }\left(y_2\right)=6y_2^2-9=0$,

$y_2^2=1.5$,

$y_2=\sqrt{1.5}$.

Целочисленный минимум достигается при $y_2=\mathrm{1,} x_{23}=\mathrm{19,} x_{22}=0$.

3. 2. 4. 2. Вторая одномерная задача:

$x_{11}+x_{31}+w_1=6$,

$0x_{11}+8x_{31}+w_1^3\to \text{min}$.

Здесь $0=c_{11}^2<e_1=1$, поэтому $x_{11}=\mathrm{6,} x_{31}=\mathrm{0,} w_1=0:$:

$\Delta u_0=2\left(1-0\right)+0=2$,

$\Delta u_1=2\left(1-0\right)+0=2$,

$\Delta u_2=0+9=9$,

$\Delta u_3=0+9=9$.

Здесь $16=c_{21}>\Delta u_3=9$, поэтому двумерная задача решена:

$x_{21}=\mathrm{0,} x_{22}=\mathrm{0,} x_{23}=\mathrm{19,} y_2=\mathrm{1,} x_{11}=\mathrm{6,} x_{31}=0$,

$w_1=\mathrm{0,} c_{21}^1=\mathrm{12,} c_{21}^2=4$.

3. 2. 5. Пятая двумерная задача:

$x_{21}+x_{22}+x_{23}+y_2=20$,

$x_{12}+x_{22}+x_{32}+w_2=22$,

$12x_{21}+20x_{22}+9x_{23}+9x_{12}+9x_{32}+2y_2^3+ 2w_2^3\to \text{min}$.

Здесь $c_{22}>d_2+e_2$, поэтому решаются две одномерные задачи.

3. 2. 5. 1. Первая одномерная задача:

$x_{21}+x_{23}+y_2=20$,

$12x_{21}+9x_{23}+2y_2^3\to \text{min}$.

Здесь $c_{23}^1>d_2$, поэтому отыскиваем минимум:

$2y_2^3+9\left(20-y_2\right)$,

$f^{\prime }\left(y_2\right)=6y_2^2-9=0$,

$y_2^2=1.5$,

$y_2=\sqrt{1.5}$.

Целочисленный минимум достигается при $y_2=1$:

$x_{23}=\mathrm{19,} x_{21}= 0$.

3. 2. 5. 2. Вторая одномерная задача:

$x_{12}+x_{32}+w_2=22$,

$9x_{12}+9x_{32}+2w_2^3\to \text{min}$.

Здесь $c_{12}=c_{32}>e_2$, поэтому находим минимум:

$2w_2^3+9\left(10-w_2\right)$,

$f^{\prime }\left(w_2\right)=6w_2^2-9=0$,

$w_2^2=1.5$,

$w_2=\sqrt{1.5}$.

Целочисленный минимум достигается при $w_2=1:$:

$x_{12}=\mathrm{10,} x_{32}=11$,

$\Delta u_0=2\left(1-0\right)+2\left(1-0\right)=4$,

$\Delta u_1=2\left(1-0\right)+9=11$,

$\Delta u_2=2\left(1-0\right)+9=11$,

$\Delta u_3=9+9=18$.

Здесь $20=c_{22}>\Delta u_3=18$, поэтому пятая двумерная задача решена:

$x_{21}=\mathrm{0,} x_{22}=\mathrm{0,} x_{23}=\mathrm{19,} y_2=\mathrm{1,} x_{12}=\mathrm{10,} x_{32}=1$,

$w_2=\mathrm{1,} c_{22}^1=\mathrm{10,} c_{22}^2=10$.

3. 2. 6. Шестая двумерная задача:

$x_{21}+x_{22}+x_{23}+y_2=20$,

$x_{13}+x_{23}+x_{33}+w_3=32$,

$12x_{21}+10x_{22}+18x_{23}+11x_{13}+10x_{33}+2y_2^3+ 3w_3^3\to \text{min}$.

Здесь $18=c_{23}>d_2+e_3=5$, поэтому решаются две одномерные задачи.

3. 2. 6. 1. Первая одномерная задача:

$x_{21}+x_{22}+y_2=20$,

$12x_{21}+10x_{22}+2y_2^3\to \text{min}$.

Здесь $c_{22}^1>d_2$, поэтому отыскиваем минимум:

$2y_2^3+10\left(20-y_2\right)$,

$f^{\prime }\left(y_2\right)=6y_2^2-10=0$,

$y_2^2=\frac{5}{3}$,

$y_2=\sqrt{\frac{5}{3}}$.

Целочисленный минимум достигается при $y_2=1$:

$x_{22}=\mathrm{19,} x_{21}=0$.

3. 2. 6. 2. Вторая одномерная задача:

$x_{13}+x_{33}+w_3=32$,

$11x_{13}+10x_{33}+3w_3^3\to \text{min}$.

Здесь $c_{32}^2>e_3$, поэтому ищем минимум:

$3w_3^3+10\left(30-w_3\right)$,

$f^{\prime }\left(w_3\right)=9w_3^2-10=0$,

$w_3^2=\frac{10}{9}$,

$w_3=\sqrt{\frac{10}{9}}$.

Целочисленный минимум достигается при $w_3=1:$

$x_{33}=\mathrm{30,} x_{13}=1$,

$∆u_0=2\left(1-0\right)+3\left(1-0\right)=5$,

$∆u_1=2\left(1-0\right)+11=13$,

$∆u_2=3\left(1-0\right)+10=13$,

$∆u_3=10+11=21$.

Здесь $c_{23}<∆u_3$, следовательно $x_{23}=\mathrm{1,} x_{22}=\mathrm{18,} x_{13}=\mathrm{0,} x_{33}=30:$:

$∆u_0=5$,

$∆u_1=2\left(1-0\right)+10=12$,

$∆u_2=3\left(1-0\right)+10=13$,

$∆u_3=10+10=20$.

Снова $c_{23}<∆u_3$, следовательно $x_{23}=\mathrm{19,} x_{22}=\mathrm{0,} x_{13}=\mathrm{0,} x_{33}=12$. Здесь $x_{23}$ достигло максимума, поэтому шестая двумерная задача решена:

$x_{21}=\mathrm{0,} x_{22}=\mathrm{0,} x_{23}=\mathrm{19,} y_2=\mathrm{1,} x_{13}=\mathrm{0,} x_{33}=12$,

$w_3=\mathrm{1,} c_{23}^1=\mathrm{9,} c_{23}^2=9$.

3. 2. 7. Седьмая двумерная задача:

$x_{31}+x_{32}+x_{33}+y_3=30$,

$x_{11}+x_{21}+x_{31}+w_1=6$,

$16x_{31}+9x_{32}+10x_{33}+0x_{11}+4x_{21}+3y_3^3+ w_1^3\to \text{min}$.

Здесь $16=c_{31}>d_3+e_1=4$, поэтому решаются две одномерные задачи.

3. 2. 7. 1. Первая одномерная задача:

$x_{32}+x_{33}+y_3=30$,

$9x_{32}+10x_{33}+3y_3^3\to \text{min}$.

Здесь $c_{32}>d_3$, поэтому вычисляем минимум:

$3y_3^3+9\left(30-y_3\right)$,

$f^{\prime }\left(y_3\right)=9y_3^2-9=0$,

$y_3=1$,

$x_{32}=\mathrm{22,} x_{33}=7$.

3. 2. 7. 2. Вторая одномерная задача:

$x_{11}+x_{21}+w_1=6$,

$0x_{11}+4x_{21}+w_1^3\to \text{min}$.

Здесь, очевидно, $x_{11}=\mathrm{6,} x_{21}=\mathrm{0,} w_1=0:$

$∆u_0=3\left(1-0\right)+0=3$,

$∆u_1=3\left(1-0\right)+0=3$,

$∆u_2=0+10=10$,

$∆u_3=10+0=10$.

Здесь $c_{32}>∆u_3$, следовательно двумерная задача решена:

$x_{11}=\mathrm{6,} x_{21}=\mathrm{0,} x_{31}=\mathrm{0,} x_{32}=\mathrm{22,} x_{33}=\mathrm{7,} y_3=1$,

$w_1=\mathrm{0,} c_{31}^1=\mathrm{11,} c_{31}^2=5$.

3. 2. 8. Восьмая двумерная задача:

$x_{31}+x_{32}+x_{33}+y_3=30$,

$x_{12}+x_{22}+x_{32}+w_2=22$,

$11x_{31}+18x_{32}+10x_{33}+9x_{12}+10x_{22}+3y_3^3+2w_2^3\to \text{min}$.

Здесь $18=c_{32}>d_3+e_2=5$, поэтому решаются две одномерные задачи.

3. 2. 8. 1. Первая одномерная задача:

$x_{31}+x_{33}+y_3=30$,

$11x_{31}+10x_{33}+3y_3^3\to \text{min}$.

Здесь $c_{33}^1>d_3$, поэтому находим минимум:

$3y_3^3+10\left(30-y_3\right)$,

$f^{\prime }\left(y_3\right)=9y_3^2-10=0$,

$y_3^2=\frac{10}{9}$,

$y_3=\sqrt{\frac{10}{9}}$.

Целочисленный минимум достигается при $y_3=1$:

$x_{33}=\mathrm{29,} x_{31}=0$.

3. 2. 8. 2. Вторая одномерная задача:

$x_{12}+x_{22}+w_2=22$,

$9x_{12}+10x_{22}+2w_2^3\to \text{min}$.

Здесь $c_{12}>e_2$, поэтому отыскиваем минимум:

$2w_2^3+9\left(10-w_2\right)$,

$f^{\prime }\left(w_2\right)=6w_2^2-9=0$,

$w_2^2=\frac{3}{2}$,

$w_2=\sqrt{\frac{3}{2}}$.

Целочисленный минимум достигается при $w_2=1$:

$x_{12}=\mathrm{10,} x_{22}=11$,

$∆u_0=3\left(1-0\right)+2\left(1-0\right)=5$,

$∆u_1=3\left(1-0\right)+10=13$,

$∆u_2=2\left(1-0\right)+10=12$,

$∆u_3=10+10=20$.

Здесь $c_{32}<∆u_3$, поэтому $x_{32}=\mathrm{11,} x_{33}=\mathrm{18,} x_{12}=\mathrm{10,} x_{22}=\mathrm{0,}{x}_{31}=\mathrm{0,} y_3=\mathrm{1,} w_2=1$:

 $∆u_0=5$,

 $∆u_1=3+9=12$,

 $∆u_2=2+10=12$,

 $∆u_3=9+10=19$.

Здесь $c_{32}<∆u_3$, поэтому $x_{32}=\mathrm{21,} x_{33}=\mathrm{8,} x_{12}=\mathrm{0,} x_{22}=\mathrm{0,} x_{31}=\mathrm{0,} y_3=\mathrm{1,} w_2=1$:

$∆u_0=5$,

$∆u_1=3+0=3$ 3,

$∆u_2=2+8=10$,

$∆u_3=8+0=8$.

Здесь $c_{32}>∆u_3$, поэтому восьмая двумерная задача решена:

$c_{32}^1=\mathrm{9.5,} c_{32}^2=8.5$.

3. 2. 9. Девятая двумерная задача:

$x_{31}+x_{32}+x_{33}+y_3=30$,

$x_{13}+x_{23}+x_{33}+w_3=32$,

$11x_{31}+9.5x_{32}+20x_{33}+11x_{13}+9x_{23}+3y_3^3+3w_3^3\to \text{min}$.

Здесь $c_{33}>d_3+e_3$, поэтому решаются две одномерные задачи.

3. 2. 9. 1. Первая одномерная задача:

$x_{31}+x_{32}+y_3=30$,

$11x_{31}+9.5x_{32}+3y_3^3\to \text{min}$.

Здесь $c_{32}^1>d_3$, поэтому вычисляем минимум:

$3y_3^3+9.5\left(22-y_3\right)$,

$f^{\prime }\left(y_3\right)=9y_3^2-9.5=0$,

$y_3^2=\frac{9.5}{9}$,

$y_3=\sqrt{\frac{9.5}{9}}$.

Целочисленный минимум достигается при $y_3=1$:

$x_{32}=\mathrm{22,} x_{31}=7$.

3. 2. 9. 2. Вторая одномерная задача:

$x_{13}+x_{23}+w_3=32$,

$11x_{13}+9x_{23}+3w_3^3\to \text{min}$.

Здесь $c_{23}^2>e_3$, поэтому находим минимум:

$3w_3^3+9\left(20-w_3\right)$,

$f^{\prime }\left(w_3\right)=9w_3^2-9=0$,

$w_3=1$,

$x_{13}=\mathrm{10,} x_{23}=20$,

$\Delta u_0=3\left(1-0\right)+3\left(1-0\right)=6$,

$\Delta u_1=3\left(1-0\right)+11=14$,

$\Delta u_2=3\left(1-0\right)+11=14$,

$\Delta u_3=11+11=22$.

Здесь $c_{33}<\Delta u_3$, поэтому $x_{33}=\mathrm{7,} x_{32}=\mathrm{22,} x_{23}=\mathrm{20,} x_{13}=\mathrm{4,} y_3=\mathrm{1,} w_3=\mathrm{1,}{x}_{31}=0$:

$\Delta u_0=6$,

$\Delta u_1=3+9=12$,

$\Delta u_2=3+9.5=12.5$,

$\Delta u_3=9+9.5=18.5$.

Здесь $c_{33}>\Delta u_3$, поэтому $c_{33}^1=\mathrm{10,} c_{33}^2=10$. Решение девятой двумерной задачи окончено.

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

3.3. Р е ш е н и е  и с х о д н о й  з а д а ч и. Рассматривается как объединение решений одномерных задач:

$x_{11}+x_{12}+x_{13}+y_1=10$,

$3.6x_{11}+4x_{12}+6x_{13}+y_1^2\to \text{min}$,

$x_{11}=\mathrm{4,} x_{12}=\mathrm{4,} y_1=2$,

$x_{11}+x_{21}+x_{31}+w_1=6$,

$4.4x_{11}+4.5x_{21}+5x_{31}+w_1^2\to \text{min}$,

$x_{11}=\mathrm{4,} w_1=2$,

$x_{21}+x_{22}+x_{23}+y_2=20$,

$11x_{21}+10x_{22}+8x_{23}+2y_2^3\to \text{min}$,

$x_{23}=\mathrm{19,} y_2=1$,

$x_{12}+x_{22}+x_{32}+w_2=22$,

$8x_{12}+10x_{22}+8x_{32}+w_2^3\to \text{min}$,

$x_{12}=\mathrm{4,} w_2=\mathrm{1,} x_{32}=17$,

$x_{31}+x_{32}+x_{33}+y_3=30$,

$11x_{31}+10x_{32}+10x_{33}+3y_3^3\to \text{min}$,

$x_{32}=\mathrm{17,} x_{33}=\mathrm{12,} y_3=1$,

$x_{13}+x_{23}+x_{33}+w_3=32$,

$12x_{13}+10x_{23}+10x_{33}+3w_3^3\to \text{min}$,

$x_{23}=\mathrm{19,} x_{33}=\mathrm{12,} w_3=1$.

4. Численные расчеты. Была осуществлена программная реализация предложенного метода. Проведен счет с различным количеством ограничений (до 300). Время счета было пропорционально $n^{4.6}$.

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

1) при $y_i=\mathrm{0,} 1\le i\le m$ и $w_j=\mathrm{0,} 1\le j\le n$ соответствующие слагаемые равны нулю,

2) при $y_i>\mathrm{0,} 1\le i\le m$ и $w_j>\mathrm{0,} 1\le j\le n$ все соответствующие слагаемые положительны,

3) первые производные всех нелинейных слагаемых целевой функции являются строго возрастающими функциями.

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

$x_{11}+x_{12}+y_1=24$, $x_{21}+x_{22}+y_2=16$,

$x_{11}+x_{21}+w_1=18$, $x_{12}+x_{22}+w_2=22$,

$24x_{11}+20x_{12}+22x_{21}+28x_{22}+2\left(e^{0.4y_1}-1\right)+3\left(e^{0.5y_2}-1\right)+$

$+ 4\left(e^{0.6w_1}-1\right)+5\left(e^{0.3w_2}-1\right)\to \text{min}$.

5.1. П е р в ы й  э т а п. 5. 1. 1. Первая одномерная задача:

$x_{11}+x_{12}+y_1=24$,

$12x_{11}+10x_{12}+2\left(e^{0.4y_1}-1\right)\to \text{min}$,

${\left[2\left(e^{0.4y_1}-1\right)+10\left(24-y_1\right)\right]}^{\text{'}}=0.8e^{0.4y_1}-10=0$,

$e^{0.4y_1}=12.5$,

$0.4y_1=\ln \left(12.5\right)=2.5257$,

$y_1=6.314$.

Целочисленный минимум достигается при $y_1=6:$:

$x_{12}=\mathrm{18,} x_{11}=0$.

5. 1. 2. Вторая одномерная задача:

$x_{21}+x_{22}+y_2=16$,

$11x_{21}+14x_{22}+3\left(e^{0.5y_2}-1\right)\to \text{min}$,

${\left[3\left(e^{0.5y_2}-1\right)+11\left(16-y_2\right)\right]}^{\text{'}}=1.5e^{0.5y_2}-11=0$,

$e^{0.5y_2}=7.3333$,

$0.5y_2=\ln \left(7.3333\right)=1.9924$,

$y_2=3.9849$.

Целочисленный минимум достигается при $y_2=4$:

$x_{21}=\mathrm{12,} x_{22}=0$.

5. 1. 3. Третья одномерная задача:

$x_{11}+x_{21}+w_1=18$,

$12x_{11}+11x_{21}+4\left(e^{0.6w_1}-1\right)\to \text{min}$,

${\left[4\left(e^{0.6w_1}-1\right)+11\left(18-w_1\right)\right]}^{\text{'}}=2.4e^{0.6w_1}-11=0$,

$e^{0.6w_1}=4.5833$,

$0.6w_1=\ln \left(4.5833\right)=1.5224$,

$w_1=2.5374$.

Целочисленный минимум достигается при $w_1=3$:

$x_{21}=\mathrm{15,} x_{11}=0$.

Четвертую одномерную задачу решать не имеет смысла, так как во второй задаче $x_{21}=12$, а в третьей $x_{21}=15$.

5.2. В т о р о й  э т а п. 5. 2. 1. Первая двумерная задача:

$x_{11}+x_{12}+y_1=24$,

$x_{11}+x_{21}+w_1=18$,

$24x_{11}+10x_{12}+11x_{21}+2\left(e^{0.4y_1}-1\right)+4\left(e^{0.6w_1}-1\right)\to \text{min}$.

Здесь $24=c_{11}>2\left(e^{0.4}-1\right)+4\left(e^{0.6}-1\right)$, поэтому решаются две одномерные задачи.

5.2.1.1. Первая одномерная задача:

$x_{12}+y_1=24$,

$10x_{12}+2\left(e^{0.4y_1}-1\right)\to \text{min}$,

${\left[2\left(e^{0.4y_1}-1\right)+10\left(24-y_1\right)\right]}^{\text{'}}=0.8e^{0.4y_1}-10=0$,

$e^{0.4y_1}=12.5$,

$0.4y_1=\ln \left(12.5\right)=2.5257$,

$y_1=6.314$.

Целочисленный минимум достигается при $y_1=6$:

$x_{12}=18$.

5. 2. 1. 2. Вторая одномерная задача:

$x_{21}+w_1=18$,

$11x_{21}+4\left(e^{0.6w_1}-1\right)\to \text{min}$,

${\left[4\left(e^{0.6w_1}-1\right)+11\left(18-w_1\right)\right]}^{\text{'}}=2.4e^{0.6w_1}-11=0$,

$e^{0.6w_1}=4.5833$,

$0.6w_1=\ln \left(4.5833\right)=1.5224$,

$w_1=2.537$.

Целочисленный минимум достигается при $w_1=3$:

$x_{21}=15$,

$\Delta u_0=2\left(e^{0.4\cdot 6}-e^{0.4\cdot 5}\right)+4\left(e^{0.6\cdot 3}-e^{0.6\cdot 2}\right)\approx 18.19$,

$\Delta u_1=2\left(e^{0.4\cdot 6}-e^{0.4\cdot 5}\right)+11\approx 18.27$,

$\Delta u_2=4\left(e^{0.6\cdot 3}-e^{0.6\cdot 2}\right)+10\approx 20.92$,

$\Delta u_3=10+11=21$.

Здесь $c_{11}>\Delta u_3$, поэтому $x_{11}=\mathrm{0,} x_{12}=\mathrm{18,} y_1=\mathrm{6,} x_{21}=\mathrm{15,} w_1=\mathrm{3,} c_{11}^1=\mathrm{12,} c_{11}^2=12$.

5. 2. 2. Вторая двумерная задача:

$x_{11}+x_{12}+y_1=24$,

$x_{12}+x_{22}+w_2=22$,

$20x_{12}+12x_{11}+14x_{22}+2\left(e^{0.4y_1}-1\right)+5\left(e^{0.3w_2}-1\right)\to \text{min}$.

Здесь $20=c_{12}>2\left(e^{0.4}-1\right)+5\left(e^{0.3}-1\right)$, поэтому решаются две одномерные задачи.

5. 2. 2. 1. Первая одномерная задача:

$x_{11}+y_1=24$,

$12x_{11}+2\left(e^{0.4y_1}-1\right)\to \text{min}$,

${\left[2\left(e^{0.4y_1}-1\right)+12\left(24-y_1\right)\right]}^{\text{'}}=0.8e^{0.4y_1}-12=0$,

$e^{0.4y_1}=15$,

$0.4y_1=\ln \left(15\right)=2.7081$,

$y_1=6.77$.

Целочисленный минимум достигается при $y_1=7$:

$x_{11}=17$.

5. 2. 2. 2. Вторая одномерная задача:

$x_{22}+w_2=22$,

$14x_{22}+5\left(e^{0.3w_2}-1\right)\to \text{min}$,

${\left[5\left(e^{0.3w_2}-1\right)+14\left(22-w_2\right)\right]}^{\text{'}}=1.5e^{0.3w_2}-14=0$,

$e^{0.3w_2}=9.333$,

$0.3w_2=\ln \left(9.333\right)=2.234$,

$w_2=7.445$.

Целочисленный минимум достигается при $w_2=7$:

$x_{22}=15$,

$\Delta u_0=2\left(e^{0.4\cdot 7}-e^{0.4\cdot 6}\right)+5\left(e^{0.3\cdot 7}-e^{0.3\cdot 6}\right)\approx 23.87$,

$\Delta u_1=2\left(e^{0.4\cdot 7}-e^{0.4\cdot 6}\right)+14\approx 25.12$,

$\Delta u_2=5\left(e^{0.3\cdot 7}-e^{0.3\cdot 6}\right)+12\approx 24.75$,

$\Delta u_3=12+14=26$.

Здесь $c_{12}<\Delta u_3$, поэтому

$x_{12}=\mathrm{15,} x_{22}=\mathrm{0,} x_{11}=\mathrm{2,} y_1=\mathrm{7,} w_2=6$,

$\Delta u_0\approx 23.87$,

$\Delta u_1=11.12+0 =11.12$,

$\Delta u_2=12.75+12 =24.75$,

$\Delta u_3=12+0=12$.

Здесь $c_{12}<\Delta u_2$, отсюда

$w_2=\mathrm{6,} x_{12}=\mathrm{16,} x_{22}=\mathrm{0,} x_{11}=\mathrm{1,} y_1=7$,

$\Delta u_0=11.12+7.7765=18.8965$,

$\Delta u_1=11.12$,

$\Delta u_2=7.7765+12 =19.7765$,

$\Delta u_3=12+0=12$.

Решение второй двумерной задачи окончено. Здесь $c_{12}>\Delta u_3$, поэтому

$w_2=\mathrm{6,} x_{12}=\mathrm{16,} x_{22}=\mathrm{0,} x_{11}=\mathrm{1,} y_1=\mathrm{7,} c_{12}^1=\mathrm{12,} c_{12}^2=10$.

5. 2. 3. Третья двумерная задача:

$x_{21}+x_{22}+y_2=16$,

$x_{11}+x_{21}+w_1=18$,

$22x_{21}+12x_{11}+14x_{22}+3\left(e^{0.5y_2}-1\right)+4\left(e^{0.6w_1}-1\right)\to \text{min}$.

Здесь $22=c_{21}>3\left(e^{0.5}-1\right)+4\left(e^{0.6}-1\right)$, поэтому решаются две одномерные задачи.

5. 2. 3. 1. Первая одномерная задача:

$x_{22}+y_2=16$,

$14x_{22}+3\left(e^{0.5y_2}-1\right)\to \text{min}$,

${\left[3\left(e^{0.5y_2}-1\right)+14\left(16-y_2\right)\right]}^{\text{'}}=1.5e^{0.5y_2}-14=0$,

$e^{0.5y_2}=9.3333$,

$0.5y_2=\ln \left(9.3333\right)=2.2336$,

$y_2=4.467$.

Целочисленный минимум достигается при $y_2=4$:

$x_{22}=12$.

5. 2. 3. 2. Вторая одномерная задача:

$x_{11}+w_1=18$,

$12x_{11}+4\left(e^{0.6w_1}-1\right)\to \text{min}$,

${\left[4\left(e^{0.6w_1}-1\right)+12\left(18-w_1\right)\right]}^{\text{'}}=2.4e^{0.6w_1}-12=0$,

$e^{0.6w_1}=5$,

$0.6w_1=\ln 5=1.6094$,

$w_1=2.682$.

Целочисленный минимум достигается при $w_1=3$:

$x_{11}=15$,

$\Delta u_0=3\left(e^{0.5\cdot 4}-e^{0.5\cdot 3}\right)+4\left(e^{0.6\cdot 3}-e^{0.6\cdot 2}\right)=19.48$,

$\Delta u_1=3\left(e^{0.5\cdot 4}-e^{0.5\cdot 3}\right)+12=20.6487$,

$\Delta u_2=4\left(e^{0.6\cdot 3}-e^{0.6\cdot 2}\right)+14=24.834$,

$\Delta u_3=14+12=26$.

Здесь $c_{21}<\Delta u_3$, поэтому

$x_{21}=\mathrm{12,} x_{22}=\mathrm{0,} x_{11}=\mathrm{3,} w_1=\mathrm{3,} y_2=4$,

$\Delta u_0=19.48$,

$\Delta u_1=20.6487$,

$\Delta u_2=10.83+0 =10.83$,

$\Delta u_3=0+12=12$.

Здесь $c_{21}>\Delta u_1$, поэтому решение двумерной задачи окончено:

$c_{21}^1=\mathrm{10,} c_{21}^2=12$.

5. 2. 4. Четвертая двумерная задача:

$x_{21}+x_{22}+y_2=16$,

$x_{12}+x_{22}+w_2=22$,

$10x_{21}+28x_{22}+10x_{12}+3\left(e^{0.5y_2}-1\right)+5\left(e^{0.3w_2}-1\right)\to \text{min}$.

Здесь $28=c_{22}>3\left(e^{0.5}-1\right)+5\left(e^{0.3}-1\right)$, поэтому решаются две одномерные задачи.

5. 2. 4. 1. Первая одномерная задача:

$x_{21}+y_2=16$,

$10x_{21}+3\left(e^{0.5y_2}-1\right)\to \text{min}$,

${\left[3\left(e^{0.5y_2}-1\right)+10\left(16-y_2\right)\right]}^{\text{'}}=1.5e^{0.5y_2}-10=0$,

$1.5e^{0.5y_2}=10$,

$e^{0.5y_2}=6.6666$,

$0.5y_2=\ln \left(6.6666 \right)=1.897$,

$y_2=3.79$.

Целочисленный минимум достигается при $y_2=4$:

$x_{21}=\mathrm{12,} x_{22}=0$.

5. 2. 4. 2. Вторая одномерная задача:

$x_{12}+w_2=22$,

$10x_{12}+5\left(e^{0.3w_2}-1\right)\to \text{min}$,

${\left[5\left(e^{0.3w_2}-1\right)+10\left(22-w_2\right)\right]}^{\text{'}}=15e^{0.3w_2}-10=0$,

$e^{0.3w_2}=6.6666$,

$0.3w_2=\ln \left(6.6666\right)=1.897$,

$w_2=6.3237$.

Целочисленный минимум достигается при $w_2=6$:

$x_{12}=16$,

$\Delta u_0=3\left(e^{0.5\cdot 4}-e^{0.5\cdot 3}\right)+5\left(e^{0.3\cdot 6}-e^{0.3\cdot 5}\right)=16.4252$,

$\Delta u_1=8.6487+10=18.6487$,

$x_{12}+w_2=22$,

$\Delta u_3=10+10=20$.

Здесь $c_{22}>\Delta u_3$, поэтому решение четвертой двумерной задачи окончено:

$y_2=\mathrm{4,} x_{21}=\mathrm{12,} x_{22}=\mathrm{0,} w_2=\mathrm{6,} x_{12}=\mathrm{16,} c_{22}^1=\mathrm{14,} c_{22}^2=14$.

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

5. 2. 5. Итоговый набор одномерных задач имеет следующий вид:

$x_{11}+x_{12}+y_1=24$,

$10x_{11}+10x_{12}+2\left(e^{0.4y_1}-1\right)\to \text{min}$.

Решение: $y_1=\mathrm{6,} x_{11}+x_{12}=18$;

$x_{21}+x_{22}+y_2=16$,

$8x_{21}+13x_{22}+3\left(e^{0.5y_2}-1\right)\to \text{min}$.

Решение: $y_2=\mathrm{3,} x_{21}=\mathrm{13,} x_{22}=0$;

$x_{11}+x_{21}+w_1=18$,

$14x_{11}+14x_{21}+4\left(e^{0.6w_1}-1\right)\to \text{min}$.

Решение: $w_1=\mathrm{3,} x_{11}+x_{21}=15$;

$x_{12}+x_{22}+w_2=22$,

$10x_{12}+15x_{22}+5\left(e^{0.3w_2}-1\right)\to \text{min}$.

Решение: $w_2=\mathrm{6,} x_{12}=16$.

Из этого набора решений легко формируется итоговый результат:

$x_{11}=\mathrm{2,} x_{12}=\mathrm{16,} x_{21}=\mathrm{13,} x_{22}=\mathrm{0,} {\text{y}}_1=\mathrm{6,} y_2=\mathrm{3,}{w}_1=\mathrm{3,} w_2=6$.

Заключение. Декомпозиционный подход оказался применим для еще одного класса задач. Намечается путь к рассмотрению двух индексов в данной постановке.