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

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

Леонов В. Ю., Тизик А. П., Торчинская Э. В. Декомпозиционный метод решения транспортной задачи с квадратичной целевой функцией [Текст] // Проблемы и перспективы экономики и управления: материалы VI Междунар. науч. конф. (г. Санкт-Петербург, декабрь 2017 г.). — СПб.: Свое издательство, 2017. — С. 219-222. — URL https://moluch.ru/conf/econ/archive/263/13466/ (дата обращения: 10.12.2018).



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

1. Введение. В [1] предложен декомпозиционный (как по ограничениям, так и по целевой функции) метод решения классической транспортной задачи. В [2], [3] этот метод был перенесен на различные модификации транспортной задачи с целочисленными переменными и линейной целевой функцией. В настоящей работе рассматривается оптимизационная задача с ограничениями, совпадающими с ограничениями классической транспортной задачи и целевой функцией, квадратично зависящей от объемов перевозки. Такую задачу можно рассматривать как задачу об условном экстремуме и применить к её решению метод множителей Лагранжа. При этом с ростом размерности задачи возрастают и вычислительные трудности, не позволяющие получить решение. В работе предлагается декомпозиционный алгоритм с использованием множителей Лагранжа.

2. Постановка задачи.

При ограничениях

(4)

В оптимальном решении задачи (1)-(4) переменные могут принимать как положительные, так и отрицательные значения. В данной работе, однако, будут рассматриваться задачи, в которых переменные принимают только положительные значения. Соответствующие неравенства, связывающие константы задачи, будут приведены ниже.

3. Метод решения задачи. Задачу (1)−(4) можно рассматривать как задачу на условный экстремум и использовать метод множителей Лагранжа. Этот метод приводит к необходимости решать систему из m + n линейных уравнений общего вида с m + n неизвестными. Поставив себе цель — увеличить размерность решаемых задач, поступим следующим образом. Поделим коэффициенты из (1) на 2 и найдем оптимальные решения с такой целевой функцией отдельно для ограничений первой и второй группы. Очевидно, что сумма значений целевых функций в этих оптимальных решениях будет не превосходить значения целевой функции в оптимальном решении задачи (1) − (4), а значения одних и тех же переменных не обязаны совпадать между собой. Назовем оптимальное решение, удовлетворяющее первой группе ограничений, первым псевдорешением задачи (1) − (4) удовлетворяющее второй группе ограничений — вторым псевдорешением. Решим следующую задачу с двумя ограничениями — первым ограничением из первой группы и первым ограничением из второй группы со следующей целевой функцией:

Задача (5) − (7) решается методом множителей Лагранжа. Легко видеть, что единственная стационарная точка функции Лагранжа в этой задаче является её глобальным минимумом. Заметим, что значение целевой функции в оптимальном решении задачи (5) − (7) не меньше, чем сумма значений целевых функций в оптимальных решениях задач с ограничением (6)

и с ограничением (7)

Предположим, что в оптимальном решении задачи (5)−(7) все переменные положительны. В этом случае, положив

можем записать следующие две задачи, с одним ограничением каждая:

при ограничении (6), и

при ограничении (7) обладающие следующими характеристиками. В оптимальных решениях задач (6), (8) и (7), (9) значения переменных будут совпадать, в пределах своих ограничений, со значениями переменных в оптимальном решении задачи (5) − (7), а сумма значений целевых функций в оптимальных решениях задач (6),(8) и (7),(9) будет равна значению целевой функции в оптимальном решении задачи (5)−(7). Таким образом, можно сформировать новые первое и второе псевдорешения такие, что сумма значений их целевых функций в оптимальных решениях будет больше, чем соответствующая сумма двух предыдущих псевдорешений и, как и прежде, будет не превосходить значения целевой функции любого допустимого решения задачи (1) − (4). Прорешав таким образом циклически все возможные m + n задач с двумя ограничениями, получим возрастающую ограниченную сверху последовательность сумм первых и вторых псевдорешений. При этом любой член этой последовательности не превосходит искомого минимума в задаче (1) − (4). Предел этой последовательности ввиду единственности стационарной точки и того, что она является глобальным минимумом функции Лагранжа в каждой задаче с двумя ограничениями, будет совпадать со значениями целевой функции задачи (1) − (4) в её оптимальном решении, а значения переменных в предельных одномерных задачах будут равняться значениям переменных в оптимальном решении задачи (1)−(4). Выделим класс задач, которые можно решать предложенным методом — при каких соотношениях между константами задачи (1) − (4) в оптимальных решениях задач с двумя ограничениями все переменные будут положительными. В общем случае задача с двумя ограничениями имеет вид:

для всех

Система уравнений для нахождения имеет вид:

Легко видеть, что определитель системы положителен всегда. Предположим для определенности, что , тогда определитель для также будет положительным, а для положительности определителя для необходимо выполнение неравенства (с учетом неравенств (13)):

4. Результаты численного эксперимента. При вычислениях сигналом к окончанию вычислений является наличие двух обстоятельств — сгущение значений сумм целевых функций первого и двух второго псевдорешений в последовательных циклах расчетов и удовлетворение ограничениям задачи с требуемой точностью. Были решены несколько серий задач различной размерности. Стоимостные коэффициенты задавались датчиком равномерных случайных целых 4 чисел в диапазоне от 200 до 400, объемы перевозок также задавались случайным образом в диапазоне от 30 до 90 с неизбежной корректировкой для удовлетворения условиям баланса. Расчеты производились на персональном компьютере с использованием процессора с частотой 3.40GHz. В задачах с 604 пунктами производства и 594 пунктами потребления при расчетах, содержащих до 50 циклов решения задач с двумя ограничениями, на последних циклах приращение сумм целевых функций псевдорешений не превосходило долей единицы, погрешность удовлетворения ограничениями не превосходила 0.02 (при ограничении, равном 30), в остальных ограничениях погрешность не превосходила 0.000001. Время расчета максимально составляло 17 минут. В задачах, содержащих 1208 пунктов производства и 1196 пунктов потребления, для достижения аналогичных результатов потребовалось 120 циклов, максимальное время расчета составило 8 часов 20 минут.

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

Литература:

  1. Тизик А. П., Кузовлев Д. И., Соколов А. А., Метод последовательной модификации функционала для транспортной задачи с дополнительными пунктами производства и потребления. // Вестник ТвГУ, Серия прикладная математика, 2012, № 4, С.91–98.
  2. Кузовлев Д. И., Тизик А. П., Тресков Ю. П. Декомпозиционный метод для решения транспортной задачи с ограниченными пропускными способностями. // Мехатроника, автоматика, управление. 2012, № 1, С. 45–48.
  3. Кузовлев Д. И., Тизик А. П., Тресков Ю. П. Итеративный алгоритм для задачи о назначении. // Технические науки и практика: материалы междунар. заоч.науч. конф. (Чита, апрель 2012 г.) — Чита, Издательство Молодой учёный, 2012., С. 41–43.
Основные термины (генерируются автоматически): целевая функция, оптимальное решение задачи, ограничение, задача, сумма значений, значение переменных, оптимальное решение задач, транспортная задача, предложенный метод, оптимальное решение.

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

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

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

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

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

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

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

Решение интервальной задачи дробно-линейного...

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

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

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

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

Решение транспортной задачи с помощью программного...

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

Интерактивный подход к решению транспортной задачи методом...

Анализ существующих методов решения транспортной...

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

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

Решение многокритериальных задач линейного...

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

Решение транспортных задач с помощью линейного...

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

Метод Гомори в решении целочисленной задачи оптимизации...

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

Обсуждение

Социальные комментарии Cackle

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

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

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

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

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

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

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

Решение интервальной задачи дробно-линейного...

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

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

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

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

Решение транспортной задачи с помощью программного...

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

Интерактивный подход к решению транспортной задачи методом...

Анализ существующих методов решения транспортной...

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

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

Решение многокритериальных задач линейного...

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

Решение транспортных задач с помощью линейного...

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

Метод Гомори в решении целочисленной задачи оптимизации...

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

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