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

ДЕКОМПОЗИЦИОННЫЙ МЕТОД РЕШЕНИЯ ТРЕХИНДЕКСНОЙ ЗАДАЧИ ОБ ЭФФЕКТИВНОЙ СТРЕЛЬБЕ

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

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

^b Математический факультет, Нанкинский ун-т аэронавтики и космонавтики
Нанкин, КНР

^c Лаборатория математического моделирования и высокопроизводительных расчетов авиатранспортных средств
Нанкин, КНР

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

^* E-mail: tsur@ccas.ru

Поступила в редакцию 15.06.2022
После доработки 06.07.2022
Принята к публикации 01.08.2022

EDN: QFUQNN
DOI: 10.31857/S0002338822060026

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

Аннотация

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

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

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

1. Постановка задачи. Имеется $m$ батарей, $n$ целей, $l$ видов снарядов. Задана трехмерная матрица ${{d}_{{jik}}}$ размера $m \times n \times l$. Ее элементы – коэффициенты эффективности выстрела из i-й батареи по j-й цели k-м видом снарядов являются неотрицательными числами:

${{d}_{{jik}}} \geqslant 0.$

Будем искать трехмерную матрицу плана стрельбы, элементы которой ${{x}_{{ijk}}}$ принимают значение единица, если производится выстрел из i-й батареи по j-й цели k-м видом снарядов, и 0, если такого выстрела не производится:

${{x}_{{ijk}}} \in \{ 0,1\} .$

Ограничения задачи об эффективной стрельбе записываются так:

(1.1)

$\sum\limits_{j = 1}^n {{x}_{{ijk}}} = {{a}_{{ik}}},\quad i = \overline {1,m} ,\quad k = \overline {1,k} ,$

где ${{a}_{{ij}}}$ – количество k-го вида снарядов, выпускаемых i-й батареей по всем $n$ целям. Далее имеем

(1.2)

$\sum\limits_{i = 1}^m {{x}_{{ijk}}} = {{b}_{{jk}}},\quad j = \overline {1,n} ,\quad k = \overline {1,l} ,$

где ${{b}_{{jk}}}$ – количество k-го вида снарядов, выпускаемых по j-й цели всеми $m$ батареями. Наконец,

(1.3)

$\sum\limits_{k = 1}^l {{x}_{{ijk}}} = {{c}_{{ij}}},\quad i = \overline {1,m} ,\quad j = \overline {1,n} ,$

где ${{c}_{{ij}}}$ – общее количество выстрелов i-й батареи по j-й цели всеми видами снарядов.

В каждую из $n$ целей должно быть выпущено по одному снаряду каждого из l видов снарядов. Таким образом, условия баланса имеют вид

(1.4)

$\sum\limits_{i = 1}^m \sum\limits_{k = 1}^l {{a}_{{ik}}} = \sum\limits_{j = 1}^n \sum\limits_{k = 1}^l {{b}_{{jk}}} = \sum\limits_{i = 1}^m \sum\limits_{j = 1}^n {{c}_{{ij}}} = nl.$

Необходимо максимизировать суммарную эффективность всех nl выстрелов:

(1.5)

$\sum\limits_{i = 1}^m \sum\limits_{j = 1}^n \sum\limits_{k = 1}^l {{d}_{{ijk}}}{{x}_{{ijk}}} \to \max $

при ограничениях (1.1)–(1.4).

Задача (1.1)–(1.5) является линейной оптимизационной задачей с булевыми переменными и относится к трехиндексным планарным задачам. Она считается NP-трудной.

2. Метод решения задачи. Для начала решим $ml + nl + mn$ задач с одним ограничением каждая. Первые ml задач

(2.1)

$\sum\limits_{j = 1}^n {{d}_{{ijk}}}{{x}_{{ijk}}} \to \max $

при ограничениях (1.1). Вторые nl задач

(2.2)

$\sum\limits_{i = 1}^m {{d}_{{ijk}}}{{x}_{{ijk}}} \to \max $

при ограничениях (1.2). Третьи $mn$ задач

(2.3)

$\sum\limits_{k = 1}^l {{d}_{{ijk}}}{{x}_{{ijk}}} \to \max $

при ограничениях (1.3). Здесь и далее предполагаем, что условия баланса (1.4) соблюдены при составлении задачи. Все $ml + nl + mn$ задач легко решаются простым нахождением наибольших ${{d}_{{ijk}}}$ в количестве, равном правым частям оганичений (2.1)–(2.3).

Если в результате решения вышеупомянутых $ml + nl + mn$ задач значения переменных удовлетворяют ограничениям (1.1)–(1.3), то тем самым решена исходная задача (1.3)–(1.5). Сумма значений целевых функций в оптимальных решениях задач (2.1)–(2.3), деленная на три, будет значением целевой функции в оптимальном решении задачи (1.1)–(1.5). В противном случае будем говорить, что получено первое псевдорешение этой задачи. Заметим, что значение целевой функции первого псевдорешения не меньше значения целевой функции искомого оптимального решения исходной задачи. Построим последовательность псевдорешений с монотонно убывающими значениями целевых функций.

Для получения второго псевдорешения решим следующую задачу с тремя ограничениями:

(2.4)

$\sum\limits_{j = 1}^n {{x}_{{1j1}}} = {{a}_{{11}}},$

(2.5)

$\sum\limits_{i = 1}^m {{x}_{{i11}}} = {{b}_{{11}}},$

(2.6)

$\sum\limits_{k = 1}^l {{x}_{{11k}}} = {{c}_{{11}}},$

(2.7)

${{d}_{{111}}}{{x}_{{111}}} + \sum\limits_{j = 2}^n \frac{1}{3}{{d}_{{1j1}}}{{x}_{{1j1}}} + \sum\limits_{i = 2}^m \frac{1}{3}{{d}_{{i11}}}{{x}_{{i11}}} + \sum\limits_{k = 2}^l \frac{1}{3}{{d}_{{11k}}}{{x}_{{11k}}} \to \max .$

В этой задаче ${{x}_{{111}}}$ – единственная общая переменная в ограничениях (2.4)–(2.6). Очевидно, что в оптимальное решение задачи (2.4)–(2.7) со значением единица войдут ${{a}_{{11}}} - 1$ переменных из (2.4) с наибольшими коэффициентами в целевой функции (2.7), соответственно ${{b}_{{11}}} - 1$ переменных из ограничения (2.5) и c₁₁ – 1 переменных из (2.6). Выберем в целевой функции (2.7) все переменные, входящие в ограничение (2.4), кроме общей переменной, отсортируем по убыванию коэффициенты целевой функции при этих переменных и возьмем коэффициент с номером, равным ${{a}_{{11}}}$. Этот коэффициент обозначим ${{M}_{1}}$. Аналогично через ${{M}_{2}}$ обозначим b₁₁-й коэффициент целевой функции среди переменных, входящих в ограничение (2.5) без общей переменной, а через ${{M}_{3}}$ – ${{c}_{{11}}}$-й коэффициент в целевой функции среди переменных, входящих в (2.6) без общей переменной. Могут иметь место три случая:

(2.8)

${{d}_{{111}}} < {{M}_{1}} + {{M}_{2}} + {{M}_{3}},$

(2.9)

${{d}_{{111}}} = {{M}_{1}} + {{M}_{2}} + {{M}_{3}},$

(2.10)

${{d}_{{111}}} > {{M}_{1}} + {{M}_{2}} + {{M}_{3}}.$

В первом случае (2.8), в оптимальное решение задачи (2.4)–(2.7) войдут дополнительно переменная из (2.4) с коэффициентом ${{M}_{1}}$ в целевой функции, переменная из (2.5) с коэффициентом ${{M}_{2}}$ в целевой функции и переменная из (2.6) с коэффициентом ${{M}_{3}}$ в целевой функции.

Во втором случае (2.9) у задачи (2.4)–(2.7), очевидно, более чем одно оптимальное решение, а значит, имеет место вырождение.

В третьем случае (2.10) к безусловно вошедшим в решение переменным добавляется переменная ${{x}_{{111}}}$.

Решив задачу (2.4)–(2.7), преобразуем ее, сохраняя оптимальное решение, в три независимые задачи, каждая из которых имеет одно из ограничений (2.4)–(2.6). Для этого в первом случае, переписав условие (2.8) как равенство

${{d}_{{111}}} = {{M}_{1}} + {{M}_{2}} + {{M}_{3}} - \delta ,\quad \delta > 0,$

представим целевые функции трех задач с одним из ограничений (2.4)–(2.6) соответственно как

(2.11)

$\left( {{{M}_{1}} - \frac{\delta }{3}} \right){{x}_{{111}}} + \sum\limits_{j = 2}^n \frac{1}{3}{{d}_{{1j1}}}{{x}_{{1j1}}} \to \max ,$

(2.12)

$\left( {{{M}_{2}} - \frac{\delta }{3}} \right){{x}_{{111}}} + \sum\limits_{i = 2}^m \frac{1}{3}{{d}_{{11k}}}{{x}_{{11k}}} \to \max ,$

(2.13)

$\left( {{{M}_{3}} - \frac{\delta }{3}} \right){{x}_{{111}}} + \sum\limits_{k = 2}^l \frac{1}{3}{{d}_{{1j1}}}{{x}_{{1j1}}} \to \max .$

Во втором случае условие (2.9) уже является равенством и коэффициенты целевых функций (2.11)–(2.13) при x₁₁₁ равны ${{M}_{1}}$, ${{M}_{2}}$, ${{M}_{3}}$.

В третьем случае, преобразовав условие (2.10) в равенство

${{d}_{{111}}} = {{M}_{1}} + {{M}_{2}} + {{M}_{3}} + \gamma ,\quad \gamma > 0,$

коэффициенты в целевых функциях (2.11)–(2.13) при x₁₁₁ запишем как ${{M}_{1}} + \gamma {\text{/}}3$, ${{M}_{2}} + \gamma {\text{/}}3$ и ${{M}_{3}} + \gamma {\text{/}}3$.

В итоге получаем второе псевдорешение с уменьшенным значением целевой функции. Заметим, что значение целевой функции каждого псевдорешения не меньше, чем значение целевой функции в искомом оптимальном решении исходной задачи (1.1)–(1.5). Решая циклически все mnl задач с тремя ограничениями, строим последовательность псевдорешений с монотонно убывающей целевой функцией, ограниченной снизу значением целевой функции в оптимальном решении исходной задачи (1.1)–(1.5).

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

4. Пример. Имеются две батареи, три цели и два вида снарядов. Коэффициенты эффективности стрельбы первой и второй батарей даны в табл. 1 и 2 соответственно. Ограничения этой задачи запишем следующим образом:

$\begin{gathered} {{x}_{{111}}} + {{x}_{{121}}} + {{x}_{{131}}} = 2, \\ {{x}_{{112}}} + {{x}_{{122}}} + {{x}_{{132}}} = 1, \\ {{x}_{{211}}} + {{x}_{{221}}} + {{x}_{{231}}} = 1, \\ {{x}_{{212}}} + {{x}_{{222}}} + {{x}_{{232}}} = 2, \\ \end{gathered} $

$\begin{gathered} {{x}_{{111}}} + {{x}_{{211}}} = 1, \\ {{x}_{{121}}} + {{x}_{{221}}} = 1, \\ {{x}_{{131}}} + {{x}_{{231}}} = 1, \\ {{x}_{{112}}} + {{x}_{{212}}} = 1, \\ {{x}_{{122}}} + {{x}_{{222}}} = 1, \\ {{x}_{{132}}} + {{x}_{{232}}} = 1, \\ \end{gathered} $

$\begin{gathered} {{x}_{{132}}} + {{x}_{{232}}} = 1, \\ {{x}_{{121}}} + {{x}_{{122}}} = 1, \\ {{x}_{{131}}} + {{x}_{{132}}} = 1, \\ {{x}_{{211}}} + {{x}_{{212}}} = 1, \\ {{x}_{{221}}} + {{x}_{{222}}} = 1, \\ {{x}_{{231}}} + {{x}_{{232}}} = 1. \\ \end{gathered} $

Таблица 1.

Коэффициенты эффективности стрельбы первой батареи двумя видами снарядов по трем целям

Вид снаряда	Номер цели
	1	2	3
1	3	6	11
2	4	9	12

Таблица 2.

Коэффициенты эффективности стрельбы второй батареи двумя видами снарядов по трем целям

Вид снаряда	Номер цели
	1	2	3
1	10	13	29
2	11	14	19

Целевая функция:

$\begin{gathered} 3{{x}_{{111}}} + 6{{x}_{{121}}} + 11{{x}_{{131}}} + 4{{x}_{{112}}} + 9{{x}_{{122}}} + 12{{x}_{{132}}} + \\ \, + 10{{x}_{{211}}} + 13{{x}_{{221}}} + 29{{x}_{{231}}} + 11{{x}_{{212}}} + 14{{x}_{{222}}} + 19{{x}_{{232}}} \to \max . \\ \end{gathered} $

Первый цикл. Первая задача:

$\begin{gathered} {{x}_{{111}}} + {{x}_{{121}}} + {{x}_{{131}}} = 2, \\ {{x}_{{111}}} + {{x}_{{211}}} = 1, \\ {{x}_{{111}}} + {{x}_{{112}}} = 1, \\ 3{{x}_{{111}}} + 2{{x}_{{121}}} + 11{\text{/}}3{{x}_{{131}}} + 4{\text{/}}3{{x}_{{112}}} + 10{\text{/}}3{{x}_{{211}}} \to \max . \\ \end{gathered} $

В этой задаче в первое ограничение кроме общей переменной входят ${{x}_{{121}}}$ и ${{x}_{{131}}}$. Коэффициенты при них в целевой функции равны 2 и 11/3. Правая часть первого ограничения равна 2, второй по величине коэффициент равен 2, т.е. ${{M}_{1}} = 2$. Во второе ограничение кроме общей переменной входит только ${{x}_{{211}}}$ с коэффициентом 10/3. Правая часть второго ограничения равна 1, таким образом ${{M}_{2}} = 10{\text{/}}3$. Аналогично ${{M}_{3}} = 4{\text{/}}3$. Имеет место соотношение (2.8), отсюда решение первой задачи ${{x}_{{111}}} = 0$, ${{x}_{{121}}} = {{x}_{{131}}} = {{x}_{{112}}} = {{x}_{{211}}} = 1$. Целевые функции (2.11)–(2.13) задач с одним ограничением запишутся так:

$\begin{gathered} {{x}_{{111}}} + 2{{x}_{{121}}} + 11{\text{/}}3{{x}_{{131}}} \to \max , \\ {{x}_{{111}}} + 10{\text{/}}3{{x}_{{211}}} \to \max , \\ {{x}_{{111}}} + 4{\text{/}}3{{x}_{{112}}} \to \max . \\ \end{gathered} $

Коэффициенты здесь и далее округлены.

Вторая задача:

$\begin{gathered} {{x}_{{111}}} + {{x}_{{121}}} + {{x}_{{131}}} = 2, \\ {{x}_{{121}}} + {{x}_{{221}}} = 1, \\ {{x}_{{121}}} + {{x}_{{122}}} = 1, \\ {{x}_{{111}}} + 6{{x}_{{121}}} + 11{\text{/}}3{{x}_{{131}}} + 3{{x}_{{122}}} + 13{\text{/}}3{{x}_{{221}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{121}}} = 0$, ${{x}_{{111}}} = {{x}_{{131}}} = {{x}_{{122}}} = {{x}_{{221}}} = 1$. Целевые функции задач с одним ограничением следующие:

$\begin{gathered} {{x}_{{111}}} + 1{\text{/}}2{{x}_{{121}}} + 11{\text{/}}3{{x}_{{131}}} \to \max , \\ 7{\text{/}}2{{x}_{{121}}} + 13{\text{/}}3{{x}_{{221}}} \to \max , \\ 2{{x}_{{121}}} + 3{{x}_{{122}}} \to \max . \\ \end{gathered} $

Третья задача:

$\begin{gathered} {{x}_{{111}}} + {{x}_{{121}}} + {{x}_{{131}}} = 2, \\ {{x}_{{131}}} + {{x}_{{132}}} = 1, \\ {{x}_{{131}}} + {{x}_{{231}}} = 1, \\ {{x}_{{111}}} + 1{\text{/}}2{{x}_{{121}}} + 11{{x}_{{131}}} + 4{{x}_{{132}}} + 29{\text{/}}3{{x}_{{231}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{131}}} = 0$, ${{x}_{{111}}} = {{x}_{{121}}} = {{x}_{{132}}} = {{x}_{{231}}} = 1$. Целевые функции задач с одним ограничением:

$\begin{gathered} {{x}_{{111}}} + 0.5{{x}_{{121}}} + 0.25{{x}_{{131}}} \to \max , \\ 3.25{{x}_{{131}}} + 4{{x}_{{132}}} \to \max , \\ 7.5{{x}_{{131}}} + 29{\text{/}}3{{x}_{{231}}} \to \max . \\ \end{gathered} $

Четвертая задача:

$\begin{gathered} {{x}_{{112}}} + {{x}_{{122}}} + {{x}_{{132}}} = 1, \\ {{x}_{{111}}} + {{x}_{{112}}} = 1, \\ {{x}_{{112}}} + {{x}_{{212}}} = 1, \\ {{x}_{{111}}} + 4{{x}_{{112}}} + 3{{x}_{{122}}} + 4{{x}_{{132}}} + 11{\text{/}}3{{x}_{{212}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{112}}} = {{x}_{{122}}} = 0$, ${{x}_{{111}}} = {{x}_{{132}}} = {{x}_{{212}}} = 1$. Целевые функции задач с одним ограничением:

$\begin{gathered} 2.25{{x}_{{112}}} + 3{{x}_{{122}}} + 4{{x}_{{132}}} \to \max , \\ {{x}_{{111}}} + 0.25{{x}_{{112}}} \to \max , \\ 1.5{{x}_{{112}}} + 11{\text{/}}3{{x}_{{212}}} \to \max . \\ \end{gathered} $

Пятая задача:

$\begin{gathered} {{x}_{{112}}} + {{x}_{{122}}} + {{x}_{{132}}} = 1, \\ {{x}_{{121}}} + {{x}_{{122}}} = 1, \\ {{x}_{{122}}} + {{x}_{{222}}} = 1, \\ 2.25{{x}_{{112}}} + 9{{x}_{{122}}} + 4{{x}_{{132}}} + 2{{x}_{{121}}} + 14{\text{/}}3{{x}_{{222}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{112}}} = {{x}_{{122}}} = 0$, ${{x}_{{132}}} = {{x}_{{121}}} = {{x}_{{222}}} = 1$. Целевые функции задач с одним ограничением:

$\begin{gathered} 2.25{{x}_{{112}}} + 3{{x}_{{122}}} + 4{{x}_{{132}}} \to \max , \\ 2{{x}_{{121}}} + 1.5{{x}_{{122}}} \to \max , \\ 4.5{{x}_{{122}}} + 14{\text{/}}3{{x}_{{222}}} \to \max . \\ \end{gathered} $

Шестая задача:

$\begin{gathered} {{x}_{{112}}} + {{x}_{{122}}} + {{x}_{{132}}} = 1, \\ {{x}_{{131}}} + {{x}_{{132}}} = 1, \\ {{x}_{{132}}} + {{x}_{{232}}} = 1, \\ 2.25{{x}_{{112}}} + 3{{x}_{{122}}} + 12{{x}_{{132}}} + 3.25{{x}_{{131}}} + 19{\text{/}}3{{x}_{{232}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{112}}} = {{x}_{{132}}} = 0$, ${{x}_{{122}}} = {{x}_{{131}}} = {{x}_{{232}}} = 1$. Целевые функции задач с одним ограничением:

$\begin{gathered} 2.25{{x}_{{112}}} + 3{{x}_{{122}}} + 2.85{{x}_{{132}}} \to \max , \\ 3.25{{x}_{{131}}} + 3{{x}_{{132}}} \to \max , \\ 6.15{{x}_{{132}}} + 19{\text{/}}3{{x}_{{232}}} \to \max . \\ \end{gathered} $

Седьмая задача:

$\begin{gathered} {{x}_{{211}}} + {{x}_{{221}}} + {{x}_{{231}}} = 1, \\ {{x}_{{111}}} + {{x}_{{211}}} = 1, \\ {{x}_{{211}}} + {{x}_{{212}}} = 1, \\ 10{{x}_{{211}}} + 13{\text{/}}3{{x}_{{221}}} + 29{\text{/}}3{{x}_{{231}}} + {{x}_{{111}}} + 11{\text{/}}3{{x}_{{212}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{211}}} = {{x}_{{221}}} = 0$, ${{x}_{{111}}} = {{x}_{{212}}} = {{x}_{{231}}} = 1$. Целевые функции задач с одним ограничением:

$\begin{gathered} 6.5{{x}_{{211}}} + 13{\text{/}}3{{x}_{{221}}} + 29{\text{/}}3{{x}_{{231}}} \to \max , \\ {{x}_{{111}}} + 0.5{{x}_{{211}}} \to \max , \\ 3{{x}_{{211}}} + 11{\text{/}}3{{x}_{{212}}} \to \max . \\ \end{gathered} $

Восьмая задача:

$\begin{gathered} {{x}_{{211}}} + {{x}_{{221}}} + {{x}_{{231}}} = 1, \\ {{x}_{{121}}} + {{x}_{{221}}} = 1, \\ {{x}_{{221}}} + {{x}_{{222}}} = 1, \\ 6.5{{x}_{{211}}} + 13{{x}_{{221}}} + 29{\text{/}}3{{x}_{{231}}} + 3.5{{x}_{{121}}} + 14{\text{/}}3{{x}_{{222}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{211}}} = {{x}_{{221}}} = 0$, ${{x}_{{121}}} = {{x}_{{231}}} = {{x}_{{222}}} = 1$. Целевые функции задач с одним ограничением:

$\begin{gathered} 6.5{{x}_{{211}}} + 9{{x}_{{221}}} + 29{\text{/}}3{{x}_{{231}}} \to \max , \\ 3.5{{x}_{{121}}} + 2{{x}_{{221}}} \to \max , \\ 2{{x}_{{221}}} + 14{\text{/}}3{{x}_{{222}}} \to \max . \\ \end{gathered} $

Девятая задача:

$\begin{gathered} {{x}_{{211}}} + {{x}_{{221}}} + {{x}_{{231}}} = 1, \\ {{x}_{{131}}} + {{x}_{{231}}} = 1, \\ {{x}_{{231}}} + {{x}_{{232}}} = 1, \\ 6.5{{x}_{{211}}} + 9{{x}_{{221}}} + 29{{x}_{{231}}} + 7.5{{x}_{{131}}} + 19{\text{/}}3{{x}_{{232}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{231}}} = 1$, ${{x}_{{131}}} = {{x}_{{211}}} = {{x}_{{221}}} = {{x}_{{232}}} = 0$. Целевые функции задач с одним ограничением:

$\begin{gathered} 6.5{{x}_{{211}}} + 9{{x}_{{221}}} + 11{{x}_{{231}}} \to \max , \\ 7.5{{x}_{{131}}} + 9{{x}_{{231}}} \to \max , \\ 9{{x}_{{231}}} + 19{\text{/}}3{{x}_{{232}}} \to \max . \\ \end{gathered} $

Десятая задача:

$\begin{gathered} {{x}_{{212}}} + {{x}_{{222}}} + {{x}_{{232}}} = 2, \\ {{x}_{{112}}} + {{x}_{{212}}} = 1, \\ {{x}_{{211}}} + {{x}_{{212}}} = 1, \\ 11{{x}_{{212}}} + 14{\text{/}}3{{x}_{{222}}} + 19{\text{/}}3{{x}_{{232}}} + 1.5{{x}_{{112}}} + 3{{x}_{{211}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{212}}} = {{x}_{{232}}} = 1$, ${{x}_{{112}}} = {{x}_{{211}}} = {{x}_{{222}}} = 0$. Целевые функции задач с одним ограничением:

$\begin{gathered} 5{{x}_{{212}}} + 14{\text{/}}3{{x}_{{222}}} + 19{\text{/}}3{{x}_{{232}}} \to \max , \\ 1.5{{x}_{{112}}} + 2{{x}_{{212}}} \to \max , \\ 3{{x}_{{211}}} + 4{{x}_{{212}}} \to \max . \\ \end{gathered} $

Одиннадцатая задача:

$\begin{gathered} {{x}_{{212}}} + {{x}_{{222}}} + {{x}_{{232}}} = 2, \\ {{x}_{{122}}} + {{x}_{{222}}} = 1, \\ {{x}_{{221}}} + {{x}_{{222}}} = 1, \\ 5{{x}_{{212}}} + 14{{x}_{{222}}} + 19{\text{/}}3{{x}_{{232}}} + 4.5{{x}_{{122}}} + 2{{x}_{{221}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{222}}} = {{x}_{{232}}} = 1$, ${{x}_{{212}}} = {{x}_{{122}}} = {{x}_{{221}}} = 0$. Целевые функции задач с одним ограничением:

$\begin{gathered} 5{{x}_{{212}}} + 6.5{{x}_{{222}}} + 19{\text{/}}3{{x}_{{232}}} \to \max , \\ 4.5{{x}_{{122}}} + 4.75{{x}_{{222}}} \to \max , \\ 2{{x}_{{221}}} + 2.75{{x}_{{222}}} \to \max . \\ \end{gathered} $

Двенадцатая задача:

$\begin{gathered} {{x}_{{212}}} + {{x}_{{222}}} + {{x}_{{232}}} = 2, \\ {{x}_{{132}}} + {{x}_{{232}}} = 1, \\ {{x}_{{231}}} + {{x}_{{232}}} = 1, \\ 5{{x}_{{212}}} + 6.5{{x}_{{222}}} + 19{{x}_{{232}}} + 6.15{{x}_{{132}}} + 9{{x}_{{231}}} \to \max . \\ \end{gathered} $

Ее решение: ${{x}_{{212}}} = {{x}_{{222}}} = {{x}_{{132}}} = {{x}_{{231}}} = 1$, ${{x}_{{232}}} = 0$. Целевые функции задач с одним ограничением:

$\begin{gathered} 5{{x}_{{212}}} + 6.5{{x}_{{222}}} + 4.5{{x}_{{232}}} \to \max , \\ 6.15{{x}_{{132}}} + 6.0{{x}_{{232}}} \to \max , \\ 9{{x}_{{231}}} + 8.5{{x}_{{232}}} \to \max . \\ \end{gathered} $

Первый цикл на этом окончен. Допустимое решение при этом еще не получено, так как, например, в шестой задаче ${{x}_{{132}}} = 0$, а в двенадцатой ${{x}_{{132}}} = 1$.

Второй цикл. Выпишем только целевые функции (2.11)–(2.13) для задач с одним ограничением после решения всех 12 задач с тремя ограничениями. После первой задачи имеем

$\begin{gathered} {{x}_{{111}}} + 0.5{{x}_{{121}}} + 0.25{{x}_{{131}}} \to \max , \\ {{x}_{{111}}} + 0.5{{x}_{{211}}} \to \max , \\ {{x}_{{111}}} + 0.25{{x}_{{112}}} \to \max . \\ \end{gathered} $

После второй задачи

$\begin{gathered} {{x}_{{111}}} + {{x}_{{121}}} + 0.25{{x}_{{131}}} \to \max , \\ 3{{x}_{{121}}} + 2{{x}_{{221}}} \to \max , \\ 2{{x}_{{121}}} + 1.5{{x}_{{122}}} \to \max . \\ \end{gathered} $

После третьей задачи

$\begin{gathered} {{x}_{{111}}} + {{x}_{{121}}} + 0.5{{x}_{{131}}} \to \max , \\ 2.5{{x}_{{131}}} + 3{{x}_{{132}}} \to \max , \\ 8{{x}_{{131}}} + 9{{x}_{{231}}} \to \max . \\ \end{gathered} $

После четвертой задачи

$\begin{gathered} 2.5{{x}_{{112}}} + 3{{x}_{{122}}} + 2.85{{x}_{{132}}} \to \max , \\ {{x}_{{111}}} + 0.5{{x}_{{112}}} \to \max , \\ {{x}_{{112}}} + 2{{x}_{{212}}} \to \max . \\ \end{gathered} $

После пятой задачи

$\begin{gathered} 2.5{{x}_{{112}}} + 2.6{{x}_{{122}}} + 2.85{{x}_{{132}}} \to \max , \\ 2{{x}_{{121}}} + 1.8{{x}_{{122}}} \to \max , \\ 4.6{{x}_{{122}}} + 4.75{{x}_{{222}}} \to \max . \\ \end{gathered} $

После шестой задачи

$\begin{gathered} 2.5{{x}_{{112}}} + 2.6{{x}_{{122}}} + 2.8{{x}_{{132}}} \to \max , \\ 2.5{{x}_{{131}}} + 2.7{{x}_{{132}}} \to \max , \\ 6.5{{x}_{{132}}} + 6.0{{x}_{{232}}} \to \max . \\ \end{gathered} $

После седьмой задачи

$\begin{gathered} 7{{x}_{{211}}} + 9{{x}_{{221}}} + 11{{x}_{{231}}} \to \max , \\ {{x}_{{111}}} + 0.5{{x}_{{211}}} \to \max , \\ 2.5{{x}_{{211}}} + 4{{x}_{{212}}} \to \max . \\ \end{gathered} $

После восьмой задачи

$\begin{gathered} 7{{x}_{{211}}} + 7.85{{x}_{{221}}} + 11{{x}_{{231}}} \to \max , \\ 3{{x}_{{121}}} + 2.95{{x}_{{221}}} \to \max , \\ 2.2{{x}_{{221}}} + 2.75{{x}_{{222}}} \to \max . \\ \end{gathered} $

После девятой задачи

$\begin{gathered} 7{{x}_{{211}}} + 7.85{{x}_{{221}}} + 9{{x}_{{231}}} \to \max , \\ 8{{x}_{{131}}} + 8.5{{x}_{{231}}} \to \max , \\ 11.5{{x}_{{231}}} + 8.5{{x}_{{232}}} \to \max . \\ \end{gathered} $

После десятой задачи

$\begin{gathered} 5{{x}_{{212}}} + 6.5{{x}_{{222}}} + 4.5{{x}_{{232}}} \to \max , \\ {{x}_{{112}}} + 2{{x}_{{212}}} \to \max , \\ 2.5{{x}_{{211}}} + 4{{x}_{{212}}} \to \max . \\ \end{gathered} $

После одиннадцатой задачи

$\begin{gathered} 5{{x}_{{212}}} + 6{{x}_{{222}}} + 4.5{{x}_{{232}}} \to \max , \\ 4.6{{x}_{{122}}} + 5{{x}_{{222}}} \to \max , \\ 2.2{{x}_{{221}}} + 3{{x}_{{222}}} \to \max . \\ \end{gathered} $

После двенадцатой задачи

$\begin{gathered} 5{{x}_{{212}}} + 6{{x}_{{222}}} + 4.5{{x}_{{232}}} \to \max , \\ 6.1{{x}_{{132}}} + 4.5{{x}_{{232}}} \to \max , \\ 11.5{{x}_{{231}}} + 10{{x}_{{232}}} \to \max . \\ \end{gathered} $

И хотя предел еще не достигнут, уже получено допустимое, а следовательно, оптимальное решение:

${{x}_{{111}}} = {{x}_{{121}}} = {{x}_{{132}}} = {{x}_{{231}}} = {{x}_{{212}}} = {{x}_{{222}}} = 1.$

Остальные переменные равны нулю. Значение целевой функции: $3 + 6 + 12 + 29 + 11 + 14 = 75$.

Заключение. Итак, представлено применение метода последовательной модификации целевой функции для трехиндексной задачи об эффективной стрельбе. Однако видно, что он дословно распространяется на случай четырех, пяти и так далее индексов. На каждом шаге решаются соответственно задачи с четырьмя, пятью и так далее ограничениями. Важно заметить, что вырождение снимается весьма просто, в отличие от классической транспортной задачи, где приходится дополнительно ставить оптимизационные задачи на сети [5].

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

Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969.
Триус Е.Б. Задачи математического программирования транспортного типа. М.: Сов. радио, 1967.
Михалевич В.С., Сергиенко И.В., Шор Н.З. Исследование методов решения оптимизационных задач и их приложения // Кибернетика. 1981. № 4. С. 89–113.
Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. М.: Радио и связь, 1982.
Тизик А.П., Цурков В.И. Метод последовательной модификации функционала для решения транспортной задачи // АиТ. 2012. № 1. С. 148–158.

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

Инструменты

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

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

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