Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

О МНОГОКРИТЕРИАЛЬНОЙ ТРАНСПОРТНОЙ ЗАДАЧЕ

Кошкин Б.П. 1 Носков С.И. 1 Оленцевич В.А. 1 Рязанцев А.И. 1
1 ФГБОУ ВО «Иркутский государственный университет путей сообщения»
В данной статье рассматривается специальная задача линейного программирования – транспортная задача, заключающаяся в поиске наиболее экономного плана перевозки однородной, взаимозаменяемой продукции из пунктов производства в пункты потребления. Приводится математическая постановка транспортной задачи в виде замкнутой и открытой моделей, а также способ приведения открытой модели к замкнутой с введением фиктивного пункта производства или фиктивного пункта потребления продукции. Предлагается математическая постановка многокритериальной транспортной задачи с двумя целевыми функциями, заключающейся в одновременной минимизации суммарных затрат на перевозку и максимизации степени важности перевозок. Отмечается метод, который может быть использован как наиболее эффективный для решения такой задачи – многокритериальный симплекс-метод, основанный на построении множества Парето в задаче многокритериального линейного программирования.
векторная оптимизация
многокритериальное линейное программирование
многокритериальный симплекс-метод
транспортная задача
транспортная модель
транспортные перевозки
целевая функция
1. Ашманов С.А. Линейное программирование [Текст] / С.А. Ашманов. – М.: Наука. Главная редакция физико-математической литературы, 1981. – 340 с.
2. Базилевский М.П., Баенхаева А.В., Носков С.И. Моделирование валового регионального продукта Иркутской области на основе применения методики множественного оценивания [Текст] // Фундаментальные исследования. – 2016. – № 10–1. – С. 9–14.
3. Гольштейн Е.Г. Задачи линейного программирования транспортного типа [Текст] / Е.Г. Гольштейн, Д.Б. Юдин. – М.: Наука. Главная редакция физико-математической литературы, 1969. – 384 с.
4. Золотарюк А.В. Математическая модель многокритериальной оптимизации транспортных перевозок [Текст] // Инновационные технологии в науке и образовании. – 2015. – № 1. – С. 317–320.
5. Константинова М.А. К вопросу многокритериальной задачи в транспортной логистике [Текст] // Научное сообщество студентов XXI столетия. Технические науки: сб. ст. по мат. XVIII междунар. студ. науч.-практ. конф. – Новосибирск: «СибАК», 2014. – № 3(18). – С. 49–54.
6. Мунасыпов Н.А. Линейное программирование [Текст]: учебное пособие / Н.А. Мунасыпов. – Оренбург: ООО «Агентство «Пресса», 2015. – 122 с.
7. Носков С.И. Точечная характеризация множества Парето в линейной многокритериальной задаче [Текст] // Современные технологии. Системный анализ. Моделирование. – 2008. – № 1. – С. 99–101.
8. Носков С.И., Баенхаева А.В. Множественное оценивание параметров линейного регрессионного уравнения [Текст] // Современные технологии. Системный анализ. Моделирование. – 2016. – № 3(51). – С. 133–140.
9. Осыкина Ю.А., Чернышова Г.Д. Многокритериальная транспортная задача с разрывной целевой функцией [Текст] // Вестник Воронежского государственного университета. Серия: системный анализ и информационные технологии. – 2008. – № 2. – С. 10–12.
10. Yu L., Zeleny M. The set of all nondominated solutions in linear cases and multycriteria simplex method // J. of Math. Anal. and Applic. – 1975. – Vol. 45, № 2. – P. 430–468.

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

Первая строгая постановка данной задачи принадлежит Хичкоку, а её детальное рассмотрение и разбор – Купмансу. Данциг сформулировал транспортную задачу как задачу линейного программирования и разработал первые методы её решения. Многие литературные источники, посвящённые линейному программированию, так или иначе упоминают, затрагивают транспортную задачу (см., например, [1, 6]). Целиком посвящена классу транспортных задач и методам их решения монография Е.Г. Гольштейна, Д.Б. Юдина [3].

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

Постановка транспортной задачи

Существуют замкнутая и открытая транспортная модель. Формулировка транспортной задачи в виде замкнутой транспортной модели заключается в следующем: имеется m пунктов производства koh01.wmf) и n пунктов потребления koh02.wmf) однородной, взаимозаменяемой продукции. Для каждого пункта производства заданы объёмы производства ai, а для каждого пункта потребления – величины спроса bj в одних и тех же единицах измерения:

koh03.wmf

Расходы, связанные с перевозкой единицы продукта из i-ого пункта в j-ый, заданы величиной cij и известны для каждой пары (i, j). Можно представить эти расходы в виде матрицы размерностью m×n:

koh04.wmf

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

Искомое количество единиц продукта, поставленное из i-ого пункта в j-ый, определяется величиной xij. Количество перевезённой продукции неотрицательно:

koh05.wmf

Можно представить перевезённую продукцию в виде матрицы размерностью m×n:

koh06.wmf

Исходные данные удобнее всего представляются в виде таблицы (таблица).

Исходные данные задачи

 

Пункты потребления

 

B1

B2

 

Пункты производства

A1

c11

c12

c1n

a1

Объём

производства

A2

c21

c22

c2n

a2

Am

cm1

cm2

cmn

am

 

b1

b2

bn

 

Объём потребления

 

Математическая модель транспортной задачи имеет следующий вид.

Минимизируются суммарные расходы на перевозку всей продукции (из всех пунктов производства во все пункты потребления):

koh07.wmf

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

koh08.wmf

koh09.wmf

koh10.wmf

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

koh11.wmf

т.е. объём продукции, имеющейся в пунктах производства, должен совпадать с объёмом продукции, требуемым в пунктах потребления.

Для представления условий задачи в матричном виде требуется ввести в рассмотрение векторы Pij и Р.

Pij – вектор коммуникации, соответствующий коммуникации, которая связывает i-ый пункт производства с j-ым пунктом потребления, и состоящий из (n + m) компонент, из которых i-я и (m + j)-я равны единице, а все остальные – нулю:

koh12.wmf

Р – вектор производства – потребления, состоящий из объёмов производства ai и величин спроса bj:

koh13.wmf

Тогда условия полного вывоза продукции из всех пунктов производства и полного удовлетворения спроса в пунктах потребления в матричной форме будут выглядеть следующим образом:

koh14.wmf

koh15.wmf

В открытой транспортной модели подразумевается, что в пунктах производства может оставаться неотправленный товар:

koh16.wmf

тогда справедливо следующее условие:

koh17.wmf

Либо имеющейся в пунктах производства продукции может быть недостаточно для полного удовлетворения спроса в пунктах потребления:

koh18.wmf

В таком случае справедливо условие

koh19.wmf

Открытую транспортную модель можно привести к замкнутой. Если объём продукции в пунктах производства больше требуемого объёма продукции на пунктах потребления, то вводится фиктивный пункт потребления Bn +1 с объёмом потребления

koh20.wmf

Величина bn +1 определяет суммарный объём нереализованного продукта.

Стоимость перевозок от каждого поставщика в такой фиктивный пункт потребления – нулевая:

koh21.wmf

Если объём продукции в пунктах производства меньше требуемого объёма продукции на пунктах потребления, то вводится фиктивный пункт производства Am +1 с объёмом поставок

koh22.wmf

Стоимость перевозок от фиктивного поставщика в каждый из пунктов потребления нулевая:

koh23.wmf

Постановка многокритериальной транспортной задачи

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

В работе [9] в качестве целевой функции рассматривается минимизация максимального среди всех потребителей числа поставщиков. Несмотря на название («Многокритериальная транспортная задача с разрывной целевой функцией») решается задача при помощи стандартных методов линейного программирования.

В работе [4] в качестве условий рассмотрены: минимизация времени нахождения в пути из пункта производства в пункт потребления продукции, минимизация общей себестоимости перевозки единицы груза, максимизация общего количества перевезённых грузов. Предлагается решать задачу с использованием методов Парето, устанавливая приоритеты критериев, или с использованием интеллектуальных методов нейросетевого прогнозирования. В данном случае определение приоритетов и выделение главного критерия является одним из самых простых методов многокритериального линейного программирования.

В работе [5] минимизировать предлагается расстояние между пунктами назначения перевозки, время транспортировки груза, тарифы перевозки и стоимость перевозки. В качестве решения такой задачи рассматриваются два метода: первый, как и в работе [4], заключается в установлении приоритетов критериев и выделении главного критерия, а второй – в свёртывании критериев и введении одного агрегированного критерия.

Рассмотрим более сложную для решения модификацию транспортной задачи с двумя целевыми функциями. Для этого введём матрицу H размерностью m×n. Элемент hij матрицы H определяет степень важности перевозки продукта из i-ого пункта производства в j-ый пункт потребления. Степень важности перевозки для каждой пары (i, j) может задаваться, например, экспертами:

koh24.wmf

Соответственно, добавляемая целевая функция заключается в максимизации степени важности перевозок:

koh25.wmf

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

koh26.wmf

koh27.wmf

при условиях

koh28.wmf

koh29.wmf

koh30.wmf

или в матричном виде:

koh31.wmf

koh32.wmf

Для открытой модели многокритериальной транспортной задачи справедливо одно из условий (в зависимости от типа открытой модели):

koh33.wmf

либо

koh34.wmf

и также условие неотрицательности количества перевозимой продукции:

koh35.wmf

При приведении открытой транспортной модели к замкнутой важность перевозки из фиктивного пункта производства Am +1 или в фиктивный пункт потребления Bn +1 будет нулевой:

koh36.wmf

koh37.wmf

Решение поставленной задачи может быть найдено при помощи многокритериального симплекс-метода, основанного на построении множества Парето в задаче многокритериального линейного программирования [7, 8, 10].

Заключение

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


Библиографическая ссылка

Кошкин Б.П., Носков С.И., Оленцевич В.А., Рязанцев А.И. О МНОГОКРИТЕРИАЛЬНОЙ ТРАНСПОРТНОЙ ЗАДАЧЕ // Фундаментальные исследования. – 2017. – № 7. – С. 35-38;
URL: https://fundamental-research.ru/ru/article/view?id=41580 (дата обращения: 28.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674