Декомпозиционный метод решения линейной трехиндексной транспортной задачи | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 5 февраля, печатный экземпляр отправим 9 февраля.

Опубликовать статью в журнале

Библиографическое описание:

Есенков, А. С. Декомпозиционный метод решения линейной трехиндексной транспортной задачи / А. С. Есенков, В. Ю. Леонов, А. П. Тизик. — Текст : непосредственный // Молодой ученый. — 2019. — № 46 (284). — С. 5-9. — URL: https://moluch.ru/archive/284/64103/ (дата обращения: 27.01.2022).



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

Введение. Трехиндексные транспортные задачи подразделяются на планарные (однопродуктовые) [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].

Литература:

  1. Гольтейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М.: Наука: Физматлит, 1969.
  2. Раскин Л. Г., Кирченко И. О. Многоиндексные задачи линейного программирования. М.: Радио,1982.
  3. Криволапов Ю. А. Метод потенциалов для решения трехиндексной транспортной задачи. Деп. Д00821. М.: ВИМИ, 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. Р. 17–31.
  7. Миронов А. А., Цурков В. И. Минимакс в моделях транспортного типа с интегральными ограничениями. I//Изв.РАН. ТиСУ. 2005. № 5. С.69–81.
  8. Миронов А. А., Федорчук В. В.. Цурков В. И. Минимакс в моделях транспортного типа с интегральными ограничениями. II // Изв..РАН. ТиСУ.2005. № 5. С.68–86.
Основные термины (генерируются автоматически): задача, целевая функция, исходная задача, ограничение, транспортная задача, оптимальное решение, оптимальное решение задачи, последовательность псевдорешений, решение, допустимое решение.


Похожие статьи

Декомпозиционный метод решения транспортной задачи...

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

целевая функция, оптимальное решение задачи, ограничение...

Теорема 1. Если объединение оптимальных решений всех задач (1.1), (1.5), (1.6) и (1.2), (1.6), (1.7) - (псевдорешение исходной задачи о назначении) является допустимым решением задачи исходной задачи (1.1) – (1.4), то оно является оптимальным решением задачи (1.1)...

исходная задача, задача, оптимальное решение, ограничение...

Транспортная задачазадача об оптимальном плане перевозок продукта из пункта

целевая функция, оптимальное решение задачи, ограничение, задача, сумма значений

Рис. 1. Оптимальное решение задачи. Решение транспортных задач с применением...

Решение транспортных задач с применением программирования...

Транспортная задача — математическая задача линейного программирования специального вида о поиске оптимального распределения

Решение транспортных задач при помощи САПР MathCAD. Рассмотрим пример транспортной задачи при условии сбалансированности.

целевая функция, оптимальное решение задачи, ограничение...

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

целевая функция, оптимальное решение задачи, ограничение...

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

целевая функция, оптимальное решение задачи, ограничение...

Областью допустимых решений полученной исходной задачи является многоугольникOABEFD. Вточке Е(9,4) этого многоугольника целевая функция принимает максимальное значение. Так как координаты точки Е — целые числа и неизвестные принимают...

целевая функция, оптимальное решение задачи, ограничение...

Транспортная задача — математическая задача линейного программирования об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления с минимальными затратами. Условие этой задачи таково. Решение транспортной задачи с...

Применение метода линейного программирования для решения...

Рис.2. Графическое решение задачи 2. Строим вектор целевой функции , координаты которого равны коэффициентам целевой функции.

В задаче линейного программирования целевая функция и ограничения линейны. транспортная задача, исследование операций, задача...

Оптимизация по условиям Куна — Таккера | Статья в журнале...

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

Похожие статьи

Декомпозиционный метод решения транспортной задачи...

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

целевая функция, оптимальное решение задачи, ограничение...

Теорема 1. Если объединение оптимальных решений всех задач (1.1), (1.5), (1.6) и (1.2), (1.6), (1.7) - (псевдорешение исходной задачи о назначении) является допустимым решением задачи исходной задачи (1.1) – (1.4), то оно является оптимальным решением задачи (1.1)...

исходная задача, задача, оптимальное решение, ограничение...

Транспортная задачазадача об оптимальном плане перевозок продукта из пункта

целевая функция, оптимальное решение задачи, ограничение, задача, сумма значений

Рис. 1. Оптимальное решение задачи. Решение транспортных задач с применением...

Решение транспортных задач с применением программирования...

Транспортная задача — математическая задача линейного программирования специального вида о поиске оптимального распределения

Решение транспортных задач при помощи САПР MathCAD. Рассмотрим пример транспортной задачи при условии сбалансированности.

целевая функция, оптимальное решение задачи, ограничение...

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

целевая функция, оптимальное решение задачи, ограничение...

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

целевая функция, оптимальное решение задачи, ограничение...

Областью допустимых решений полученной исходной задачи является многоугольникOABEFD. Вточке Е(9,4) этого многоугольника целевая функция принимает максимальное значение. Так как координаты точки Е — целые числа и неизвестные принимают...

целевая функция, оптимальное решение задачи, ограничение...

Транспортная задача — математическая задача линейного программирования об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления с минимальными затратами. Условие этой задачи таково. Решение транспортной задачи с...

Применение метода линейного программирования для решения...

Рис.2. Графическое решение задачи 2. Строим вектор целевой функции , координаты которого равны коэффициентам целевой функции.

В задаче линейного программирования целевая функция и ограничения линейны. транспортная задача, исследование операций, задача...

Оптимизация по условиям Куна — Таккера | Статья в журнале...

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

Задать вопрос