1. На главную
  2. Электронные версии
  3. Известия РАН. Теория и системы управления
  4. № 6, 2019

Известия РАН. Теория и системы управления, 2019, № 6, стр. 57-62

ДЕКОМПОЗИЦИОННЫЙ АЛГОРИТМ ДЛЯ ЛИНЕЙНОЙ ТРЕХИНДЕКСНОЙ ТРАНСПОРТНОЙ ЗАДАЧИ

Л. Ванг a, *, А. П. Тизик b, **, В. И. Цурков c, ***

a Нанкинский ун-т аэронавтики и космонавтики
Нанкин, КНР

b Центральный научно-исследовательский институт связи
Москва, Россия

c Федеральный исследовательский центр “Информатика и управление” РАН
Москва, Россия

* E-mail: wlpmath@nuaa.edu.cn
** E-mail: tizik_ap@mail.ru
*** E-mail: tsur@ccas.ru

Поступила в редакцию 28.06.2019
После доработки 01.07.2019
Принята к публикации 22.07.2019

Полный текст (PDF)

Аннотация

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

Введение. Трехиндексные транспортные задачи подразделяются на планарные (однопродуктовые) [1, 2] и аксиальные (многопродуктовые) [3]. Предметом рассмотрения в данной работе будут вторые. Для них известно применение метода потенциалов [3], а также эвристических методов [4]. В [5] предложен декомпозиционный метод решения классической транспортной задачи с $m$ поставщиками и $n$ потребителями. Сначала решаются $m + n$ задач с одним ограничением каждая. Из оптимальных решений $m + n$ задач формируется первое псевдорешение исходной задачи. В дальнейшем термин псевдорешение используется по аналогии с [5]. Оно не допустимо к исходной задаче, а соответствующие целевые функции ограничены исходным оптимумом. Сумма значений целевых функций в оптимальных решениях $m + n$ задач называется значением целевой функции псевдорешения. Далее циклически решаются $mn$ задач с двумя ограничениями каждая. Оптимальное решение задачи с двумя ограничениями представляется как объединение оптимальных решений двух задач с одним ограничением каждая. Таким образом возникает последовательность псевдорешений с монотонно возрастающей целевой функцией. Последовательность значений целевой функции псевдорешений в совокупности ограничена значением целевой функции в оптимальном решении исходной транспортной задачи. Если предел последовательности не равен значению целевой функции исходной задачи (допустимое решение не получено, вырождение), то дополнительные процедуры обеспечивают сходимость к искомому оптимальному решению транспортной задачи.

В настоящей работе метод [4] с необходимыми дополнениями распространяется на трехиндексную задачу.

1. Постановка задачи и метод решения. Рассматривается известная трехиндексная транспортная задача: имеется $m$ поставщиков $({{A}_{1}},{{A}_{2}},...,{{A}_{m}})$, $n$ потребителей $({{B}_{1}},{{B}_{2}},...,{{B}_{n}})$ и k различных продуктов $({{C}_{1}},{{C}_{2}},...,{{C}_{k}})$. Заданы объемы поставок ${{a}_{{it}}}$ продукта ${{C}_{t}}$ поставщиком Ai, объем потребностей ${{b}_{{jt}}}$ в продуктах Ct у потребителя ${{B}_{j}}$, объемы перевозок ${{c}_{{ij}}}$ от поставщика Ai к потребителю ${{B}_{j}}$. Известны транпортные расходы ${{d}_{{ijt}}}$ на перевозку единицы продукта ${{C}_{t}}$ от поставщика ${{A}_{i}}$ к потребителю ${{B}_{j}}$. Необходимо определить план перевозок с минимальной суммой транспортных расходов.

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

(1.1)
$L(X) = \sum\limits_{i = 1}^m \,\sum\limits_{j = 1}^n \,\sum\limits_{t = 1}^k \,{{d}_{{ijt}}}{{x}_{{ijt}}} \to min,$
(1.2)
$\sum\limits_{j = 1}^n \,{{x}_{{ijt}}} = {{a}_{{it}}},\quad \forall (i,t) \in {{N}_{m}} \times {{N}_{k}},$
(1.3)
$\sum\limits_{i = 1}^m \,{{x}_{{ijt}}} = {{b}_{{jt}}},\quad \forall (j,t) \in {{N}_{n}} \times {{N}_{k}},$
(1.4)
$\sum\limits_{t = 1}^k \,{{x}_{{ijt}}} = {{c}_{{ij}}},\quad \forall (i,j,) \in {{N}_{m}} \times {{N}_{n}},$
(1.5)
${{x}_{{ijt}}} \geqslant 0,\quad \forall (i,j,k) \in {{N}_{m}} \times {{N}_{n}} \times {{N}_{k}}.$

Здесь ${{N}_{m}}$, ${{N}_{n}}$, ${{N}_{k}}$ – множества номеров производителей, потребителей и продуктов, соответственно.

Для разрешимости задачи (1.1)–(1.5) необходимо выполение условий:

(1.6)
$\sum\limits_{i = 1}^m \,{{a}_{{it}}} = \sum\limits_{j = 1}^n \,{{b}_{{jt}}},\quad \forall t \in {{N}_{k}},$
(1.7)
$\sum\limits_{t = 1}^k \,{{a}_{{it}}} = \sum\limits_{j = 1}^n \,{{c}_{{ij}}},\quad \forall i \in {{N}_{m}},$
(1.8)
$\sum\limits_{t = 1}^k \,{{b}_{{ji}}} = \sum\limits_{i = 1}^m \,{{c}_{{ij}}},\quad \forall j \in {{N}_{n}}.$

Для получения первого псевдорешения решаются $(m + n)k + mn$ задач с одним ограничением каждая и с коэффициентами в целевых функциях, равными коэффициентам целевой функции (1.1), деленными на три. Если объединение оптимальных решений всех $(m + n)k + mn$ задач с одним ограничением каждая является допустимым решением исходной задачи, то тем самым получено оптимальное решение исходной задачи (1.1)–(1.5). Разумеется, рассчитывать на это не приходится. Значения одних и тех же переменных в различных одномерных задачах могут не совпадать. Заметим, что значение целевой функции любого псевдорешения не превосходит значения целевой функции искомого оптимального решения задачи (1.1)–(1.5). Построим последовательность псевдорешений с монотонно возрастающими значениями целевой функции. Для этого станем циклически решать mnk задач с тремя ограничениями каждая. В общем виде задача с тремя ограничениями и одной общей переменной ${{x}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}}$ имеет вид:

(1.9)
$\sum\limits_{j = 1}^n \,{{x}_{{{{i}_{0}}j{{t}_{0}}}}} = {{a}_{{{{i}_{0}}{{t}_{0}}}}},$
(1.10)
$\sum\limits_{i = 1}^m \,{{x}_{{i{{j}_{0}}{{t}_{0}}}}} = {{b}_{{{{j}_{0}}{{t}_{0}}}}},$
(1.11)
$\sum\limits_{t = 1}^k \,{{x}_{{{{i}_{0}}{{j}_{0}}t}}} = {{c}_{{{{i}_{0}}{{j}_{0}}}}},$
(1.12)
$\sum\limits_{j = 1,j \ne {{j}_{0}}}^n \,d_{{{{i}_{0}}j{{t}_{0}}}}^{1}{{x}_{{ij{{t}_{0}}}}} + \sum\limits_{i = 1,i \ne {{i}_{0}}}^m \,d_{{i{{j}_{0}}{{t}_{0}}}}^{2}{{x}_{{i{{j}_{0}}{{t}_{0}}}}} + \sum\limits_{t = 1,t \ne {{t}_{0}}}^k \,d_{{{{i}_{0}}{{j}_{0}}t}}^{3}{{x}_{{{{i}_{0}}{{j}_{0}}t}}} + {{d}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}}{{x}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}} \to min.$

Коэффициенты целевой функции (1.12) с верхними индексами при решении самой первой задачи с тремя ограничениями при ${{i}_{0}} = 1$, ${{j}_{0}} = 1$, ${{t}_{0}} = 1$ равны коэффициентам целевой функции (1.1), деленным на три. Верхними ограничениями для переменных, входящих в (1.9)–(1.11), служат минимумы из трех правых частей (1.2)–(1.4), в которые эти переменные входят. Задачи вида (1.9)–(1.12) легко решаются подобно [5] сравнением ${{d}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}}$ с $mi{{n}_{{j,j \ne {{j}_{0}}}}}d_{{{{i}_{0}}j{{t}_{0}}}}^{1}$ + $mi{{n}_{{i,i \ne {{i}_{0}}}}}d_{{i{{j}_{0}}{{t}_{0}}}}^{2}$ + + ${{\min }_{{t,t \ne {{t}_{0}}}}}d_{{{{i}_{0}}{{j}_{0}}t}}^{3}$. После решения очередной задачи (1.9)–(1.12) ${{d}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}}$ представляется в виде: ${{d}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}}$ = $d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{1} + d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{2} + d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{3}$. Слагаемые этой суммы выбираются так, чтобы объединение оптимальных решений трех задач с ограничениями (1.9)–(1.11) соответственно совпало с оптимальным решением задачи (1.9)–(1.12).

Если

${{d}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}} < \mathop {min}\limits_{j,j \ne {{j}_{0}}} d_{{{{i}_{0}}j{{t}_{0}}}}^{1} + \mathop {min}\limits_{i,i \ne {{i}_{0}}} d_{{i{{j}_{0}}{{t}_{0}}}}^{2} + \mathop {min}\limits_{t,t \ne {{t}_{0}}} d_{{{{i}_{0}}{{j}_{0}}t}}^{3},$
то в задаче (1.9)–(1.12) ${{x}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}}$ получил максимально возможное значение и легко можно выписать
$d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{1} < \mathop {min}\limits_{j,j \ne {{j}_{0}}} d_{{{{i}_{0}}j{{t}_{0}}}}^{1},d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{2} < \mathop {min}\limits_{i,i \ne {{i}_{0}}} d_{{i{{j}_{0}}{{t}_{0}}}}^{2},d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{3} < \mathop {min}\limits_{t,t \ne {{t}_{0}}} d_{{{{i}_{0}}{{j}_{0}}t}}^{3}.$
Если
${{d}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}} = \mathop {min}\limits_{j,j \ne {{j}_{0}}} d_{{{{i}_{0}}j{{t}_{0}}}}^{1} + \mathop {min}\limits_{i,i \ne {{i}_{0}}} d_{{i{{j}_{0}}{{t}_{0}}}}^{2} + \mathop {min}\limits_{t,t \ne {{t}_{0}}} d_{{{{i}_{0}}{{j}_{0}}t}}^{3},$
то в задаче (1.9)–(1.12) ${{x}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}}$ не получает конкретного значения. В качестве решения выступают линейные ограничения с участием ${{x}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}}$. В этом случае

$d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{1} = \mathop {min}\limits_{j,j \ne {{j}_{0}}} d_{{{{i}_{0}}j{{t}_{0}}}}^{1},d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{2} = \mathop {min}\limits_{i,i \ne {{i}_{0}}} d_{{i{{j}_{0}}{{t}_{0}}}}^{2},d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{3} = \mathop {min}\limits_{t,t \ne {{t}_{0}}} d_{{{{i}_{0}}{{j}_{0}}t}}^{3}.$

Если

${{d}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}} > \mathop {min}\limits_{j,j \ne {{j}_{0}}} d_{{{{i}_{0}}j{{t}_{0}}}}^{1} + \mathop {min}\limits_{i,i \ne {{i}_{0}}} d_{{i{{j}_{0}}{{t}_{0}}}}^{2} + \mathop {min}\limits_{t,t \ne {{t}_{0}}} d_{{{{i}_{0}}{{j}_{0}}t}}^{3},$
то в простейшем случае ${{x}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}} = 0$ и

$d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{1} > \mathop {min}\limits_{j,j \ne {{j}_{0}}} d_{{{{i}_{0}}j{{t}_{0}}}}^{1},d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{2} > \mathop {min}\limits_{i,i \ne {{i}_{0}}} d_{{i{{j}_{0}}{{t}_{0}}}}^{2},d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{3} > \mathop {min}\limits_{t,t \ne {{t}_{0}}} d_{{{{i}_{0}}{{j}_{0}}t}}^{3}.$

Однако и в этом случае возможна ситуация, когда ${{x}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}} > 0$. Пусть, например, в ограничении (1.9) ${{x}_{{{{i}_{0}}{{j}_{1}}{{t}_{0}}}}}$ является конкурентом для ${{x}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}}$ и в оптимальном решении ${{x}_{{{{i}_{0}}{{j}_{1}}{{t}_{0}}}}} < {{a}_{{{{i}_{0}}{{t}_{0}}}}}$. Тогда, полагая

$d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{2} = \mathop {min}\limits_{i,i \ne {{i}_{0}}} d_{{i{{j}_{0}}{{t}_{0}}}}^{2},d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{3} = \mathop {min}\limits_{t,t \ne {{t}_{0}}} d_{{{{i}_{0}}{{j}_{0}}t}}^{3},d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{1} = {{d}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}} - d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{2} - d_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}^{3},$
имеем ${{x}_{{{{i}_{0}}{{j}_{0}}{{t}_{0}}}}} = {{a}_{{{{i}_{0}}{{t}_{0}}}}} - {{x}_{{{{i}_{0}}{{j}_{1}}{{t}_{0}}}}}$ в ограничении (1.9) в явном виде, а в ограничениях (1.10) и (1.11) – в форме линейных ограничений с другими переменными. После этого можно переходить к очередной задаче вида (1.9)–(1.12). Если в результате решения последовательности задач вида (1.9)–(1.12) получено допустимое решение задачи (1.1)–(1.5), то тем самым найдено оптимальное решение задачи (1.1)–(1.5).

В этом случае можно сказать, что задача (1.1)–(1.5) распадается на $(m + n)k + mn$ задач с одним ограничением каждая.

Такая ситуация возможна далеко не в каждой исходной задаче (1.1)–(1.5). Даже в однопродуктовом случае [5] имеют место так называемые вырождения. В данной работе принято простое эффективное правило: если при решении двух задач для некоторой переменной получаются различные значения, необходимо решить задачу, содержащую обе группы ограничений. При этом выявляются более чем одномерные подзадачи, на которые распадается исходная задача. Если при решении укрупненных задач изменятся коэффициенты в одномерных задачах, то общий итерационный процесс необходимо возобновить. Нижеприведенный пример иллюстрирует этот факт.

2. Пример. Задача содержит три поставщика, три потребителя и три продукта:

$\begin{gathered} {{x}_{{111}}} + {{x}_{{121}}} + {{x}_{{131}}} = 10,\quad {{x}_{{112}}} + {{x}_{{212}}} + {{x}_{{312}}} = 17,\quad {{x}_{{111}}} + {{x}_{{112}}} + {{x}_{{113}}} = 12, \\ {{x}_{{211}}} + {{x}_{{221}}} + {{x}_{{231}}} = 12,\quad {{x}_{{122}}} + {{x}_{{222}}} + {{x}_{{322}}} = 15,\quad {{x}_{{121}}} + {{x}_{{122}}} + {{x}_{{123}}} = 18, \\ {{x}_{{311}}} + {{x}_{{321}}} + {{x}_{{331}}} = 14,\quad {{x}_{{132}}} + {{x}_{{232}}} + {{x}_{{332}}} = 22,\quad {{x}_{{131}}} + {{x}_{{132}}} + {{x}_{{133}}} = 12, \\ \end{gathered} $
$\begin{gathered} {{x}_{{111}}} + {{x}_{{211}}} + {{x}_{{311}}} = 15,\quad {{x}_{{113}}} + {{x}_{{123}}} + {{x}_{{133}}} = 20,\quad {{x}_{{211}}} + {{x}_{{212}}} + {{x}_{{213}}} = 18, \\ {{x}_{{121}}} + {{x}_{{221}}} + {{x}_{{321}}} = 13,\quad {{x}_{{213}}} + {{x}_{{223}}} + {{x}_{{233}}} = 15,\quad {{x}_{{221}}} + {{x}_{{222}}} + {{x}_{{223}}} = 10, \\ {{x}_{{131}}} + {{x}_{{231}}} + {{x}_{{331}}} = 8,\quad {{x}_{{313}}} + {{x}_{{323}}} + {{x}_{{333}}} = 10,\quad {{x}_{{231}}} + {{x}_{{232}}} + {{x}_{{233}}} = 15, \\ \end{gathered} $
$\begin{gathered} {{x}_{{112}}} + {{x}_{{122}}} + {{x}_{{132}}} = 16,\quad {{x}_{{113}}} + {{x}_{{213}}} + {{x}_{{313}}} = 10,\quad {{x}_{{311}}} + {{x}_{{312}}} + {{x}_{{313}}} = 10, \\ {{x}_{{212}}} + {{x}_{{222}}} + {{x}_{{232}}} = 18,\quad {{x}_{{123}}} + {{x}_{{223}}} + {{x}_{{323}}} = 15,\quad {{x}_{{321}}} + {{x}_{{322}}} + {{x}_{{323}}} = 17, \\ {{x}_{{312}}} + {{x}_{{322}}} + {{x}_{{332}}} = 20,\quad {{x}_{{133}}} + {{x}_{{233}}} + {{x}_{{333}}} = 20,\quad {{x}_{{331}}} + {{x}_{{332}}} + {{x}_{{333}}} = 17, \\ \end{gathered} $
$\begin{gathered} 2{{x}_{{111}}} + 3{{x}_{{121}}} + 4{{x}_{{131}}} + 3{{x}_{{211}}} + 4{{x}_{{221}}} + 5{{x}_{{231}}} + 4{{x}_{{311}}} + 5{{x}_{{321}}} + 6{{x}_{{331}}} + 2{{x}_{{112}}} + 4{{x}_{{122}}} + 6{{x}_{{132}}} + \\ \, + 4{{x}_{{212}}} + 5{{x}_{{222}}} + 7{{x}_{{232}}} + 6{{x}_{{312}}} + 6{{x}_{{322}}} + 8{{x}_{{332}}} + {{x}_{{113}}} + 2{{x}_{{123}}} + 6{{x}_{{133}}} + 7{{x}_{{213}}} + 3{{x}_{{223}}} + 4{{x}_{{233}}} + \\ \, + 8{{x}_{{313}}} + 9{{x}_{{323}}} + 5{{x}_{{333}}}\; \to \;min. \\ \end{gathered} $

После 21-го цикла решения задач с тремя ограничениями 27 задач с одним ограничением каждая имеют следующий вид:

Первый продукт:

(2.1)
$\left\{ \begin{gathered} {{x}_{{111}}} + {{x}_{{121}}} + {{x}_{{131}}} = 10, \hfill \\ 86400{{x}_{{111}}} + 37535{{x}_{{121}}} + 37535{{x}_{{131}}} \to min. \hfill \\ \end{gathered} \right.$

Здесь и далее для простоты записи коэффициенты в целевых функциях домножены на число 96 000:

(2.2)
$\left\{ \begin{gathered} {{x}_{{211}}} + {{x}_{{221}}} + {{x}_{{231}}} = 12, \hfill \\ 107733{{x}_{{211}}} + 107733{{x}_{{221}}} + 107733{{x}_{{231}}} \to min, \hfill \\ \end{gathered} \right.$
(2.3)
$\left\{ \begin{gathered} {{x}_{{311}}} + {{x}_{{321}}} + {{x}_{{331}}} = 14, \hfill \\ 124500{{x}_{{311}}} + 124533{{x}_{{321}}} + 124600{{x}_{{331}}} \to min, \hfill \\ \end{gathered} \right.$
(2.4)
$\left\{ \begin{gathered} {{x}_{{111}}} + {{x}_{{211}}} + {{x}_{{311}}} = 15, \hfill \\ 0.9{{x}_{{111}}} + 44767{{x}_{{221}}} + 44500{{x}_{{311}}} \to min, \hfill \\ \end{gathered} \right.$
(2.5)
$\left\{ \begin{gathered} {{x}_{{121}}} + {{x}_{{221}}} + {{x}_{{321}}} = 13, \hfill \\ 169267{{x}_{{121}}} + 169267{{x}_{{221}}} + 169267{{x}_{{321}}} \to min, \hfill \\ \end{gathered} \right.$
(2.6)
$\left\{ \begin{gathered} {{x}_{{131}}} + {{x}_{{231}}} + {{x}_{{331}}} = 8, \hfill \\ 149800{{x}_{{131}}} + 149967{{x}_{{231}}} + 150000{{x}_{{331}}} \to min. \hfill \\ \end{gathered} \right.$

Второй продукт:

(2.7)
$\left\{ \begin{gathered} {{x}_{{112}}} + {{x}_{{122}}} + {{x}_{{132}}} = 16, \hfill \\ 91335{{x}_{{112}}} + 91335{{x}_{{122}}} + 91335{{x}_{{132}}} \to min, \hfill \\ \end{gathered} \right.$
(2.8)
$\left\{ \begin{gathered} {{x}_{{212}}} + {{x}_{{222}}} + {{x}_{{232}}} = 18, \hfill \\ 161700{{x}_{{212}}} + 161700{{x}_{{222}}} + 161700{{x}_{{232}}} \to min, \hfill \\ \end{gathered} \right.$
(2.9)
$\left\{ \begin{gathered} {{x}_{{312}}} + {{x}_{{322}}} + {{x}_{{332}}} = 20, \hfill \\ 2.5{{x}_{{312}}} + 178700{{x}_{{322}}} + 178700{{x}_{{332}}} \to min, \hfill \\ \end{gathered} \right.$
(2.10)
$\left\{ \begin{gathered} {{x}_{{112}}} + {{x}_{{212}}} + {{x}_{{312}}} = 17, \hfill \\ 86800{{x}_{{112}}} + 86800{{x}_{{212}}} + {{x}_{{312}}} \to min, \hfill \\ \end{gathered} \right.$
(2.11)
$\left\{ \begin{gathered} {{x}_{{122}}} + {{x}_{{222}}} + {{x}_{{322}}} = 16, \hfill \\ 2.202{{x}_{{112}}} + 211300{{x}_{{222}}} + 211100{{x}_{{322}}} \to min, \hfill \\ \end{gathered} \right.$
(2.12)
$\left\{ \begin{gathered} {{x}_{{132}}} + {{x}_{{232}}} + {{x}_{{332}}} = 22, \hfill \\ 3{{x}_{{132}}} + 3{{x}_{{232}}} + 3{{x}_{{332}}} \to min. \hfill \\ \end{gathered} \right.$

Третий продукт:

(2.13)
$\left\{ \begin{gathered} {{x}_{{113}}} + {{x}_{{123}}} + {{x}_{{133}}} = 20, \hfill \\ {{x}_{{113}}} + 16 \cdot 19802{{x}_{{123}}} + 16{{x}_{{133}}} \to min, \hfill \\ \end{gathered} \right.$
(2.14)
$\left\{ \begin{gathered} {{x}_{{213}}} + {{x}_{{223}}} + {{x}_{{233}}} = 15, \hfill \\ 2 \cdot 16{{x}_{{213}}} + 15{{x}_{{223}}} + 16{{x}_{{233}}} \to min, \hfill \\ \end{gathered} \right.$
(2.15)
$\left\{ \begin{gathered} {{x}_{{313}}} + {{x}_{{323}}} + {{x}_{{333}}} = 10, \hfill \\ 3{{x}_{{313}}} + 3{{x}_{{323}}} + 2,5{{x}_{{333}}} \to min, \hfill \\ \end{gathered} \right.$
(2.16)
$\left\{ \begin{gathered} {{x}_{{113}}} + {{x}_{{213}}} + {{x}_{{313}}} = 10, \hfill \\ \frac{1}{{16}}{{x}_{{113}}} + 3{{x}_{{213}}} + 2{{x}_{{313}}} \to min, \hfill \\ \end{gathered} \right.$
(2.17)
$\left\{ \begin{gathered} {{x}_{{123}}} + {{x}_{{223}}} + {{x}_{{323}}} = 15, \hfill \\ 91000{{x}_{{123}}} + 91000{{x}_{{223}}} + 3{{x}_{{323}}} \to min, \hfill \\ \end{gathered} \right.$
(2.18)
$\left\{ \begin{gathered} {{x}_{{133}}} + {{x}_{{233}}} + {{x}_{{333}}} = 20, \hfill \\ {{x}_{{133}}} + 71700{{x}_{{233}}} + 0.5{{x}_{{333}}} \to min. \hfill \\ \end{gathered} \right.$

Задачи с ограничениями по загрузке линий:

(2.19)
$\left\{ \begin{gathered} {{x}_{{111}}} + {{x}_{{112}}} + {{x}_{{113}}} = 12, \hfill \\ 0.2{{x}_{{111}}} + 13865{{x}_{{112}}} + \frac{1}{{16}}{{x}_{{113}}} \to min, \hfill \\ \end{gathered} \right.$
(2.20)
$\left\{ \begin{gathered} {{x}_{{121}}} + {{x}_{{122}}} + {{x}_{{123}}} = 18, \hfill \\ 81198{{x}_{{121}}} + 0.846{{x}_{{122}}} + 81198{{x}_{{123}}} \to min, \hfill \\ \end{gathered} \right.$
(2.21)
$\left\{ \begin{gathered} {{x}_{{131}}} + {{x}_{{132}}} + {{x}_{{133}}} = 16, \hfill \\ 196665{{x}_{{131}}} + 196665{{x}_{{132}}} + 4{{x}_{{133}}} \to min, \hfill \\ \end{gathered} \right.$
(2.22)
$\left\{ \begin{gathered} {{x}_{{211}}} + {{x}_{{212}}} + {{x}_{{213}}} = 18, \hfill \\ 135500{{x}_{{211}}} + 135500{{x}_{{212}}} + 2{{x}_{{213}}} \to min, \hfill \\ \end{gathered} \right.$
(2.23)
$\left\{ \begin{gathered} {{x}_{{221}}} + {{x}_{{222}}} + {{x}_{{223}}} = 10, \hfill \\ 107000{{x}_{{221}}} + 107000{{x}_{{222}}} + 107000{{x}_{{223}}} \to min, \hfill \\ \end{gathered} \right.$
(2.24)
$\left\{ \begin{gathered} {{x}_{{231}}} + {{x}_{{232}}} + {{x}_{{233}}} = 17, \hfill \\ 222300{{x}_{{231}}} + 222300{{x}_{{232}}} + 222300{{x}_{{233}}} \to min, \hfill \\ \end{gathered} \right.$
(2.25)
$\left\{ \begin{gathered} {{x}_{{321}}} + {{x}_{{322}}} + {{x}_{{323}}} = 15, \hfill \\ 186200{{x}_{{311}}} + 186200{{x}_{{322}}} + 3{{x}_{{323}}} \to min, \hfill \\ \end{gathered} \right.$
(2.26)
$\left\{ \begin{gathered} {{x}_{{331}}} + {{x}_{{332}}} + {{x}_{{333}}} = 17, \hfill \\ 301400{{x}_{{331}}} + 301300{{x}_{{332}}} + 2{{x}_{{333}}} \to min. \hfill \\ \end{gathered} \right.$

3. Преодоление вырождений. В выписанных задачах с одним ограничением переменная ${{x}_{{332}}}$ имеет два разных значения. В задаче (2.11) ${{x}_{{322}}} = 15$, а в задаче (2.26) имеем ${{x}_{{321}}} + {{x}_{{322}}} = 15$, в задаче (2.3) ${{x}_{{311}}} = 12$ и ${{x}_{{321}}} = 2$. Решая совместно задачи (2.11), (2.26) и (2.3), получаем оптимальное решение ${{x}_{{322}}}$ = 13, ${{x}_{{321}}} = 2$, ${{x}_{{222}}} = 2$. При этом значения целевых функций остальных задач с одним ограничением не изменяются. Вырождение преодолено, оптимальное решение примера получено:

$\begin{gathered} {{x}_{{111}}} = 0,\quad {{x}_{{121}}} = 8,\quad {{x}_{{131}}} = 2, \\ {{x}_{{211}}} = 3,\quad {{x}_{{221}}} = 3,\quad {{x}_{{231}}} = 3, \\ {{x}_{{311}}} = 12,\quad {{x}_{{321}}} = 2,\quad {{x}_{{331}}} = 0, \\ {{x}_{{112}}} = 2,\quad {{x}_{{122}}} = 0,\quad {{x}_{{132}}} = 14, \\ {{x}_{{212}}} = 15,\quad {{x}_{{222}}} = 2,\quad {{x}_{{232}}} = 1, \\ {{x}_{{312}}} = 0,\quad {{x}_{{322}}} = 13,\quad {{x}_{{332}}} = 7, \\ {{x}_{{113}}} = 10,\quad {{x}_{{123}}} = 10,\quad {{x}_{{133}}} = 0, \\ {{x}_{{213}}} = 0,\quad {{x}_{{223}}} = 5,\quad {{x}_{{233}}} = 10, \\ {{x}_{{313}}} = 0,\quad {{x}_{{323}}} = 0,\quad {{x}_{{333}}} = 10. \\ \end{gathered} $

Заключение. Итак, используется типичный метод понижения размерности [6], который применяется для интересного и малоизученного класса задач оптимизации. В самом деле, на каждом шаге итеративного процесса решается оптимизационная задача с тремя ограничениями. Можно двигаться к распространению на общий случай $l$ индексов или осуществлять обобщение на нелинейные постановки по аналогии с [7, 8].

Список литературы

  1. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука: Физматлит, 1969.

  2. Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. М.: Радио, 1982.

  3. Криволапов Ю.А. Метод потенциалов для решения трехиндексной транспортной задачи. Деп. Д08221. М.: ВИМИ, 1990.

  4. Афраймович Л.Г. Эвристический метод решения целочисленных декомпозиционных задач // АиТ. 2014. № 8. С. 3–18.

  5. Тизик А.П., Цурков В.И. Метод последовательной модификации функционала для решения транспортной задачи // АиТ. 2012. № 1. С. 148–158.

  6. Tsurkov V.I. Decomposition principle for block-separable systems // Dokl. AN SSSR. 1979. V. 246. № 1. P. 17–31.

  7. Миронов А.А., Цурков В.И. Минимакс в моделях транспортного типа с интегральными ограничениями. I // Изв.РАН. ТиСУ. 2003. № 4. С. 69–81.

  8. Миронов А.А., Федорчук В.В., Цурков В.И. Минимакс в моделях транспортного типа с интегральными ограничениями. II // Изв. РАН. ТиСУ. 2005. № 5. С. 68–86.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Известия РАН. Теория и системы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал