Модель управления на основе решения несимметричных транспортных задач

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. - М.: Наука, Гл. ред. физ.-мат. литературы, 1982. - 256 с.

2. Финаев В.И. Моделирование при проектировании информационно-управляющих систем. - Таганрог: Изд-во ТРТУ, 2002. - 117 с.

3. Финаев В.И., Заргарян Ю.А. Формализация предпочтений экспертов при групповом принятии решений // Известия ЮФУ. Технические науки. - 2012. - № 2 (127). - С. 160-165.

4. Мелихов А.И., Берштейн Л.С., Коровин С.Я. Ситуационные советующие системы с нечеткой логикой. - М.: Наука. Гл. ред. физ.-мат. лит.,1990. - 272 с.

Статью рекомендовал к опубликованию д.т.н., профессор В.Е. Золотовский.

Заргарян Елена Валерьевна - Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет»; e-mail: e.zargaryan@gmail.com; 347928, г. Таганрог, пер. Некрасовский, 44; Тел.: +78634371689; кафедра систем автоматического управления; к.т.н.; доцент.

Zargaryan Elena Valerevna - Federal State-Owned Autonomy Educational Establishment of Higher Vocational Education “Southern Federal University e-mail: e.zargaryan@gmail.com; 44, Nekrasovsky, Taganrog, 347928, Russia; phone: +78634371689; the department of automatic control systems; cand. of eng. sc.; associate professor.

УДК 519.681

О.В. Косенко, И.В. Пушнина

МОДЕЛЬ УПРАВЛЕНИЯ НА ОСНОВЕ РЕШЕНИЯ НЕСИММЕТРИЧНЫХ

ТРАНСПОРТНЫХ ЗАДАЧ

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

Модель; транспортная задача; линейное программирование.

O.V. Kosenko, I.V. Pushnina

MANAGEMENT MODEL ON THE BASIS OF THE SOLUTION OF ASYMMETRICAL TRANSPORT TASKS

One of the most common mathematical programming problems - transportation problem. In solving linear programming problems, especially formulated objectives (criteria) of the control. However, in practice, quite often there are problems such as transport, the formalization of which does not lead to classical triplanarnoy or triaxial scheme. An important class of such problems is the three-index-are unbalanced transportation problems. Since unbalanced transportation prob-

lems are spécial cases of more general symmetric of transport problems, the principal difficulties in solving them usually do not occur. However, the application of the general scheme of the method to asymmetric potential problems is not always justified, since in some cases the consideration of the specific tasks gives bo-a simpler algorithm.

Model; the transportation problem; the linearprogramming.

Одной из наиболее распространённых задач в управлении проектами, является задача распределения ресурсов. В качестве ресурса могут выступать финансы, сырьё, энергия, оборудование, трудовые ресурсы, вычислительные мощности и т. д. Основной проблемой здесь является то, что руководителю проекта, как правило, не известны истинные потребности исполнителей; в ресурсе того или иного вида, т. е. неизвестна точная зависимость их эффективности от полученного ресурса. Следовательно, так как суммарное количество ресурса в большинстве случаев ограничено, то возникает задача распределения ресурса оптимальным образом.

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

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

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

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

Во многих работах по математическому программированию и исследованию операций представлены вопросы решения транспортной задачи в классической постановке. В общей математической форме транспортная задача линейного программирования формулируется следующим образом [2]:

В т пунктах отправления А1, А2,..., Ат сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим аі (і = 1,2,..., т). Данный продукт потребляется в п пунктах В 1В 2,..., Вп ;

объем потребления обозначим Ь. (Ч = 1,2,...,п). Известны расходы на перевозку

единицы продукта из пункта А. в пункт В., которые равны с ч приведенні в маті . ч

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

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

Обозначим количество продукта, перевозимого из пункта А. в пункт В. через х-. Тогда целевая функция задачи имеет вид

т п

f

і=1 ч=1

Ограничения выглядят следующим образом:

1. Полное удовлетворение спроса каждого пункта потребления продуктами из разных пунктов производства:

т ____

X Хч = Ьч, Ч = 1 п.

і=1

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

т ____

X хі. = а., і = 1, т.

і=1

3. Объемы перевозок - неотрицательные числа:

Хч * °.

Необходимым и достаточным условием разрешимости задачи является соблюдение баланса:

т п

X аі = XЬ..

і=1 Ч=1

Транспортная задача сводится, таким образом, к минимизации суммарных затрат (1) при условиях (2)-(4).

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

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

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

2. Наличие груза (автомобилей) и спрос на них не является сбалансированным.

3. Возможность взаимозаменяемости автомобилей различных марок.

4. Размещение автомобилей разных марок на автотранспортном предприятии.

5. Необходимость доставить груз в минимальное время.

Недостатком транспортной задачи является то, что модель перевозок не учитывает неоднородность грузов и транспортных средств. Неоднородность перевозимых грузов и типы автотранспортных средств можно учесть путем рассмотрения многоиндексных транспортных задач. Реализация данных задач обеспечивается решением трипланарной (Т-3Р) и триаксиальной (Т-3А) транспортных задач. Их решение позволяет получить оптимальный план транспортировки разных типов грузов разными типами автотранспортных средств. Системы ограничений транспортного типа и интеграция опорных планов многоиндексных транспортных задач в терминах теории гиперграфов представлены в работе [4].

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

Рассмотрим возможные варианты таких задач.

1. Трехиндексная бипланарная транспортная задача.

Модель задачи имеет следующий вид:

Найти набор {х *ук }, минимизирующий целевую функцию

т п р

Ь

I =1 ]=1 к =1

и удовлетворяющий ограничениям:

п р

X X Хк = а, [ е 1 = í1,2,..., т}

У=1 к =1

т р

XXхф = ъ},уе ] Ч1,2—п}

г=1 к =1

хук > 0,

Задача (6)-(9) называется трехиндексной бипланарной транспортной и обозначается Т-2Р. Необходимым и достаточным условием существования решения задачи Т-2Р является условие баланса

т п

X а = X ъу = Б.

1=1 у=1

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

Найти набор {х *-к}, минимизирующий целевую функцию

г]к

т п р

скх>к

г-1 ]-\ к-1

и удовлетворяющий ограничениям:

т

X хик- ьк , 3е 1 ,к е К; с11)

г-1

Ххзк- сзк,3 е1,к е К;

3-1

х3к > 0,

Задача (10)—(13) называется трехиндексной биаксиальной транспортной и обозначается Т-2А. Необходимым и достаточным условием существования решения задачи Т-2 А является условие баланса

п т

Хь]к - Xек - 5к,к е К.

3-1 г-1

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

Найти набор {х *г/к}, минимизирующий целевую функцию

т п р

и X) - XXX ецкХцк

г-1 /-1 к-1

и удовлетворяющий ограничениям:

р

X Х/к - «г,-, г е 7,3 е 1;

к-1

т п

XX хзк- ек, к е К;

г-1 3-1

хг7к > 0,

Задача (15)-(18) называется трехиндексной аксиально-планарной транспортной и обозначается Т-АР. Необходимым и достаточным условием существования решения задачи Т-АР является условие баланса [5]

т п р

XXаij- Xек - 5.

г -1 3-1 к-1

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

Положим I-(г — 1)п + 3,ге I,]е 1 и преобразуем трехиндексную матрицу {е^ } размера (т X п X р) в двухиндексную матрицу {е1к} размера (тпХ р). Аналогично сформируем {а1к} и {аг},I е{1,2,...,тп}-Ь. Тогда задача Т-АР может быть сформулирована следующим образом:

Найти набор X * = {x *lk ], минимизирующий функцию

mn p

l=1 k=1

и удовлетворяющий ограничениям:

p

S xk = a1 є L;

k =1

mn

S xk = ck,k є K ;

l =1

xlk > 0,(/k)є LXK.

Задача (19)-(22) представляет собой обычную двухиндексную транспортную задачу и может быть решена любым известным методом.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Дюбуа Д., Прад. А. Теория возможностей: Пер. с французского В.Б. Тарасова / Под ред. С.А. Орловского. - М.: Радио и Связь, 1990. - 288 с.

2. Баркалов П.С. Задачи распределения ресурсов в управлении проектами. - М.: Институт проблем управления им. В.А. Трапезникова РАН, 2002.

3. Гудович Д.В. Управление затратами автотранспортного предприятия на основе оптимизации экономических моделей: Дис. ... канд. техн. наук. - Липецк, 2007. - 165 с.

4. Геронимус Б.Л. Экономико-математические методы в планировании на автомобильном транспорте. - М.: Транспорт. 1988. - 160 с.

5. Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования (теория, методы, приложения). - М.: Радио и связь, 1982. - 240 с.

Статью рекомендовал к опубликованию д.т.н., профессор В.Е. Золотовский.

Косенко Олеся Валентиновна - Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет»; e-mail: o_kosenko@mail.ru; 347900, г. Таганрог, 13 переулок, 6; тел.: 88634649741; кафедра систем автоматического управления; ассистент.

Пушнина Инна Валерьевна - e-mail: inna.pushnina@gmail.com; 347900, г. Таганрог, 3-Артил-лерийский, 94; кафедра систем автоматического управления; соискатель.

Kosenko Olesya Valentinovna. - Federal State-Owned Autonomy Educational Establishment of Higher Vocational Education “Southern Federal University”; e-mail: o_kosenko@mail.ru; 6, 13 pereulok, Taganrog, 347900, Russia; phone: 88634649741; the department of automatic control systems; assistant.

Pushnina Inna Valerevna - e-mail: inna.pushnina@gmail.com; 3, Artillery street, Taganrog, 347900, Russia; the department of automatic control systems, the applicant.