Метод последовательной модификации целевой функции, применяемый ранее для классической транспортной задачи, распространяется на случай трех индексов. В итерационном процессе решаются задачи с тремя ограничениями и одной связывающей переменной. Затем рассматриваются три независимые задачи с одним ограничением каждая, где меняются коэффициенты целевой функции для связывающей переменной. Метод строит последовательность псевдорешений с монотонным ростом целевой функции, который сходится к оптимуму. Анализируются вырождения.
Введение. Трехиндексные транспортные задачи подразделяются на планарные (однопродуктовые) [1, 2] и аксиальные (многопродуктовые) [3]. Предметом рассмотрения в данной работе будут вторые. Для известно применение метода потенциалов [3], я также эвристических методов [4]. В [5] предложен декомпозиционный метод решения классической транспортной задачи с m поставщиками и n потребителями. Сначала решаются m+n задач с одним ограничением каждая. Из оптимальных решений m+n задач формируется первое псевдорешение исходной задачи.в дальнейшем термин псевдорешение используется по аналогии с [5]. Оно не допустимо к исходной задаче, а соответствующие целевые функции ограничены сверху исходным оптимумом. Сумма значений целевых функций в оптимальных решениях m+n задач называется значением целевой функции псевдорешения. Далее циклически решаются mn задач с двумя ограничениями каждая. Оптимальное решение задачи с двумя ограничениями представляется как объединение оптимальных решений двух задач с одним ограничением каждая. Таким образом возникает последовательность псевдорешений с монотонно возрастающей целевой функцией. Последовательность значений целевых функции псевдорешений в совокупности ограничена значением целевой функции в оптимальном решении исходной транспортной задачи. Если предел последовательности не равен значению целевой функции исходной задачи (допустимое решение не получено, вырождение), то дополнительные процедуры обеспечивают сходимость к искомому оптимальному решению транспортной задачи. В настоящей работе метод [4] с необходимыми дополнениями рапространяется на трехиндексную транспортную задачу.
1. Постановка задачи иметод решения. Рассматриается известная трехиндексная транспортная задача: имеется m поставщиков (
,
, n потребителей (
,
,...
) и k различных продуктов (С1,C2,...,Сk). Заданы объемы поставок 
продукта Сj поставщиком Аi, объем потребностей
Формальная запись трехиндексной транспортной задачи имеет вид:
(1.1)
, 
(1.2)
, 
(1.3)
, 
(1.4)
, 
(1.5)
Здесь 
, 
— множества номеров производителей, потребителей и продуктов соответственно.
Для разрешимости задачи (1.1) -(1.5) необходимо выполнение условий
, 
(1.6)
, 
(1.7)
, 
(1.8)
Для получения первого псевдорешения решаются 
задач с одним ограничением каждая и с коэффициентами в целевых функциях, равными коэффициентам целевой функции (1.1), деленными на три. Если объединение оптимальных решений всех 
задач с одним ограничением каждая является допустимым решением исходной задачи, то тем самым получено оптимальное решение исходной задачи (1.1) — (1.5). Разумеется, рассчитывать на это не приходится. Значения одних и тех же переменных в различных одномерных задачах могут не совпадать. Заметим, что значение целевой функции любого псевдорешения не превосходит значения целевой функции искомого оптимального решения исходной задачи (1.1) — (1.5). Построим последовательность псевдорешений с монотонно возрастающими значениями целевой функции. Для этого станем циклически решать 
задач с тремя ограничениями каждая. В общем виде задача с тремя ограничениями и одной общей переменной 
имеет вид:
(1.9)
(1.10)
(1.11)
(1.12)
Коэффициенты целевой функции (1.12) с верхними индексами при решении самой первой задачи с тремя ограничениями при 
=1, 
=1 равны коэффициентам целевой функции (1.1), деленным на три. Верхними ограничениями для переменных, входящих в (1.9) — (1.11), служат минимумы из трех правых частей (1.2) — (1.4), в которые эти переменные входят. Задачи вида (1.9) — (1.12) легко решаются подобно [5] сравнением 
c 
+
+
. После решения очередной задачи (1.9) — (1.12) 
представляется в виде 
+
+
. Слагаемые этой суммы выбираются так, чтобы объединение оптимальных решений трех задач с ограничениями (1.9) — (1.11) соответственно совпало с оптимальным решением задачи (1.9) — (1.12).
Если
+ +,
то в задаче (1.9) — (1.12) получил максимально возможное значение и легко можно выписать
, 
, 
Если
=+ +,
то в задаче (1.9) — (1.12) не получает конкретного значения. В качестве решения выступают линейные ограничения с участием 
. В этом случае
, 
, 
Если
+ +,
то в простейшем случае 
и
, 
, 
Однако и в этом случае возможна ситуация, когда
>0. Пусть, например, в ограничении (1.9) 
является конкурентом для и верхним ограничением для является величина меньше, чем 
. Тогда полагая
, 
=--,
имеем =- в ограничении (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) распадается на задач с одним ограничением каждая.
Такая ситуация возможна далеко не в каждой исходной задаче (1.1) — (1.5). Даже в однопродуктовом случае [5] имеют место так называемые вырождения. В данной работе принято простое эффективное правило: если при решении двух задач для некоторой переменной получаются различные значения, необходимо решить задачу, содержащую обе группы ограничений. При этом выявляются более, чем одномерные подзадачи, на которые распадается исходная задача. Если при решении укрупненных задач изменятся коэффициенты в одномерных задачах, то общий итерационный процесс необходимо возобновить. Нижеприведенный пример иллюстрирует этот факт.
2. Пример. Задача содержит три поставщика, три потребителя и три продукта:
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
После 21-го цикла решения задач с тремя ограничениями каждая 27 задач с одним ограничением каждая имеют следующий вид:
Первый продукт:
(2.1)
Здесь и далее для простоты записи некоторые коэффициенты в целевых функциях домножены на число 96000:
(2.2)
(2.3)
(2.4)
(2.5)
(2.6)
Второй продукт:
(2.7)
(2.8)
(2.9)
(2.10)
(2.11)
(2.12)
Третий продукт:
(2.13)
(2.14)
(2.15)
(2.16)
(2.17)
(2.18)
Задачи с ограничениями по загрузке линий:
(2.19)
(2.20)
(2.21)
(2.22)
(2.23)
(2.24)
(2.25)
(2.26)
(2.27)
3. Преодоление вырождений. Ввыписанных задачах с одним ограничением переменная 
имеет два разных значения. В задаче (2.11) 
, а в задаче (2.26) 
задаче (2.3) 
Решая совместно задачи (2.3), (2.11) и (2.26) получаем оптимальное решение 
, 
, 
При этом значения целевых функций в остальных задачах с одним ограничением не изменяются. Вырождение преодолено. Оптимальное решение получено:
,
Заключение. Итак, используется метод понижения размерности [6], который применяется для интересного и малоизученного класса задач оптимизации. В самом деле, на каждом шаге итеративного процесса решается оптимизационная задача с тремя ограничениями. Можно двигаться к распространению на общий многоиндексный случай или осуществлять обобщение на нелинейные постановки по аналогии с [7,8].
Литература:
- Гольтейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М.: Наука: Физматлит, 1969.
- Раскин Л. Г., Кирченко И. О. Многоиндексные задачи линейного программирования. М.: Радио,1982.
- Криволапов Ю. А. Метод потенциалов для решения трехиндексной транспортной задачи. Деп. Д00821. М.: ВИМИ, 1990.
- Афраймович Л. Г. Эвристический метод решения целочисленных декомпозиционных задач // АиТ.2014, № 8. С. 3–18.
- Тизик А. П., Цурков В. И. Метод последовательной модификации функционала для решения транспортной задачи //АиТ. 2012. № 1.С.148–158.
- Tsurkov V. I. Decomposition principle for block-separable systems // Dokl/ AN SSSR. 1979. V.246. № 1. Р. 17–31.
- Миронов А. А., Цурков В. И. Минимакс в моделях транспортного типа с интегральными ограничениями. I//Изв.РАН. ТиСУ. 2005. № 5. С.69–81.
- Миронов А. А., Федорчук В. В.. Цурков В. И. Минимакс в моделях транспортного типа с интегральными ограничениями. II // Изв..РАН. ТиСУ.2005. № 5. С.68–86.
