Економічні науки/Математичні методи в економіці

Глушик М.М., Телесницька Н.М., Фещин Ю.З.

Львівська комерційна академія

Мінімізація експлуатаційних витрат дилерської мережі

На сучасному етапі розвиток економіки вимагає від виробництва інтенсивного розвитку продуктивних сил і використання досягнень науково-технічного прогресу. При таких умовах вибір оптимальних варіантів планування і управління виробництвом, а заразом і підприємницькою діяльністю, тісно повязаний з ефективним використанням трудових, матеріальних і фінансових ресурсів. Важливим питанням є мінімізація експлуатаційних витрат на створення запасу в дилерській мережі, надійного резерву для торгівлі, яка є найбільш динамічною і швидкими темпами розвивається в Україні. Питання зменшення витрат на забезпечення дилерської мережі продуктами виробництва для продажу, тісно пов’язано з витратами на реалізацію продукції, а заразом і з рентабельністю виробництва і ціною на кінцевий продук [2].

Розглянемо наступну задачу: Виробничо-торгівельна група з випуску продукції, яка користується попитом в N районах, володіє відповідною дилерською мережею з реалізації цієї продукції. Одним із елементів системи управління запасами [1] є витрати, пов’язані з доставкою (постачанням) цієї продукції до споживачів. У зв’язку з цим виникає потреба розробки таких маршрутів доставки (постачання) власної продукції, щоб сумарні витрати на доставку (постачання) були б мінімальними і всі мережеві пункти були б забезпечені цією продукцією. Данному питанню на нинішній день не приділяється особливої уваги.

Авторами пропонується спроба математичного моделювання даної ситуації і її ефективного аналізу.

Дилер (представник дилерскої мережі) повинен забезпечити дилерські пункти продукцією власного виробництва, які знаходяться в N містах (починаючи з пункту виготовлення), відвідати кожний пункт лише один раз і повернутися на фірму (вихідний пункт). Задаються експлуатаційні витрати на перевезення одиниці продукції до мережевих пунктів. Предстаник фірми повинен обрати такий шлях забезпечення дилерської мережі, який забезпечує найменші експлуатаційні витрати.

Для розв’язання данної задачі можна скористувіатися відомою задачею про комівояжера [1].

Реалізацію данного підходу проілюструємо на прикладі.

Приклад: Представник фірми-виробника (в подальшому дилер) повинен повинен забезпечити дилерську мережу продуктами власного виробництва, яка включає пунктів. Дані для розрахунку наводяться в таблиці (табл. 1. для =4).

Таблиця 1

	1	2	3	4
1	-	350	180	110
2	200	-	270	40
3	30	80	-	600
4	500	100	120	-

Задача полягає у тому, щоб мінімізувати функцію мети

де - експлуатаційні витрати на постачання продукції між та ; - пунтами дилерської мережі.

Як відомо [1], таких маршрутів буде маршрутів. Задача полягає у виборі такого маршруту забезпечення транспортної мережі, щоб сумарні експлуатаційні витрати були б мінімальними.

Для спрощення розрахунків можна скоротити на однакову кількість нулів у - вартості проїзду між пунктами. В результаті отримуємо табл. 2. Але потім, при отриманні розв'язку задачі, ми повинні відновити вказані реальні значення . Не дозволені з будь-якої причини маршрути можуть вилучатися з розрахунків виключенням відповідної комірки з таблиці.

Таблиця 2

	1	2	3	4
1	-	35	18	11
2	20	-	27	4
3	3	8	-	60
4	50	10	12	-

Між пунктами може розглядатись лише одна відстань, і тому ми мали б заповнити лише половину табл. 1. Але, з іншого боку, ми розглядаємо задачу, яка повинна охоплювати загальний випадок. Загальний випадок вимагає враховувати наявність різних способів забезпечення по мережі (наприклад, літаком, залізницею, автобусом).

Для розв’язання данної задачі розглянемо метод, який базується на редукції рядків та стовпчиків [1].

Метод редукції рядків та стовпчиків

При розрахунках використовуємо табл. 2. Для оцінки можливої верхньої межі функції мети обираємо довільний маршрут дилера, наприклад (1,3) - (3,2) - (2,4) - (4,1), і отримуємо значення функції мети Очевидно, що оптимальне значення функції мети повинне бути менше за .

Розрахунок маршруту дилера розбивається на N-2 етапів. У межах кожного етапу алгоритм розрахунків однаковий.

Етап 1

Крок 1.1. Виконуємо редукцію рядків, для чого у табл. 2.2 помічаємо у кожному рядку найменше значення і віднімаємо його від елементів даного рядка. Значення вказуємо у стовпчику (табл. 3).

Таблиця 3

Редукція рядків

	1	2	3	4
1	-	24	7	0	11
2	16	-	23	0	4
3	0	5	-	57	3
4	40	0	2	-	10

Крок 1.2. Виконуємо редукцію стовпчиків, для чого у кожному стовпчику табл. 3 (в якому відсутні нульові елементи) позначаємо найменше значення оцінки шляху (далі - оцінка) і віднімаємо її від елементів даного стовпчика. Значення оцінок вказуємо у стовпчику (табл. 4).

Таблиця 4

Редукція стовпчиків

	1	2	3	4
1	-	24	5	0	11
2	16	-	21	0	4
3	0	5	-	57	3
4	40	0	0	-	10
	0	0	2	0

Розраховуємо найнижчу можливу межу функції мети

Очевидно, що оптимальне значення функції мети , яке ми розраховуємо, повинно розташовуватись у межах або .

Крок 1.3. Визначення одного з кроків оптимального шляху. Якщо у кожному рядку та кожному стовпчику табл. 4 було б лише по одному нулю, то шлях був би замкненим (це обов'язково перевіряється) і нульові комірки визначають оптимальний шлях дилера з оптимальною функцією мети . На цьому розв'язання припиняється. Але у нашій таблиці 4 це не спостерігається, тому продовжуємо розрахунки. З цією метою для даних таблиці 4 визначаємо штрафи а_і , , які показані у стовпчику та рядку табл. 5:

· штраф рядка а_і , який дорівнює найменшому значенню оцінки комірок

-го рядка після першого нуля. Якщо у цьому рядку два або більше нулів, то а_і=0. Штраф а_і визначає додаткові витрати, які виникають, якщо не використовувати одну нульову комірку у рядку;

• штраф стовпчика , який дорівнює найменшому значенню оцінки комірок -го стовпчика після першого нуля. Якщо у цьому стовпчику два або більше нулів, то =0. Штраф визначає додаткові витрати, які виникають, якщо не використовувати одну нульову комірку у стовпчику.

Таблиця 5

Штрафи рядків та стовпчиків

	1	2	3	4		аі
1	-	24	5	0	11	5
2	16	-	21	0	4	16
3	0	5	-	57	3	5
4	40	0	0	-	10	0
	0	0	2	0
	16	5	5	0

За даними табл. 5 розраховуємо для кожної нульової комірки функцію вторинного штрафу і вводимо розраховані дані у табл. 6.

Таблиця 6

Нульові комірки ()	(1,4)	(2,4)	(3,1)	(4,2)	(4,3)
Вторинний штраф	5	16	21	5	5

Найбільше значення вказує, що у маршрут дилера потрібно внести комірку (3,1). Це базова комірка, з якої починається процес гілкування у розрахунках. Але цей вибір може виявитись і помилковим, тому це рішення потрібно перевірити (див. нижче). Обрану комірку (3,1) ми використовуємо для викреслення рядка та стовпчика у табл. 5. У результаті ми отримуємо табл. 7, яку потрібно переробити. Справа у тому, що у будь-якій таблиці дилера (і у скороченій, як у даному випадку) існує одна вимога, яка повинна виконуватись: у будь-якому рядку й у будь-якому стовпчику повинна існувати одна заборонена комірка.

Таблиця 7

Скорочення рядка та колонки

	2	3	4
1	24	5	0
2	-	21	0
4	0	0	-

У даному випадку (табл.7) такої забороненої комірки немає у рядку та у стовпчику (як бачимо, тут повторюються номери викресленої комірки з перестановкою рядка та стовпчика). Тому забороняємо до використання у розрахунках комірку і отримуємо табл. 8, яка використовується для розрахунків на другому етапі.

Таблиця 8

	2	3	4
1	24	-	0
2	-	21	0
4	0	0	-

Етап 2

Крок 2.1. Виконуємо редукцію рядків аналогічно кроку 1.1 етапу 1. Отримуємо дані табл. 8 для рядків.

Таблиця 8а

Редукція та штрафи рядків

	2	3	4
1	24	-	0	0	24
2	-	21	0	0	21
4	0	0	-	0	0

Крок 2.2. Виконуємо редукцію стовпців аналогічно кроку 1.2 етапу 1. Отримуємо дані табл. 8 для стовпчиків.

Таблиця 8б

Редукція та штрафи стовпчиків

	2	3	4
1	24	-	0
2	-	21	0
4	0	0	-
	0	0	0
	24	-	0

Тоді підсумкова таблиця редукції рядків та стовпчиків буде

Таблиця 8с

Редукція та штрафи рядків та стовпчиків

	2	3	4
1	24	-	0	0	24
2	-	21	0	0	21
4	0	0	-	0	0
	0	0	0
	24	0	0	0	24

Якщо б дані та відрізнялися від нуля, то ми повинні були б визначити нову функцію

і врахувати, що оптимальне значення функції мети повинно розташовуватись у межах .

Крок 2.3. Визначаємо ще один із кроків оптимального шляху дилера аналогічно кроку 1.3 етапу 1. Отримуємо штрафи , табл. 2.8с для рядків та стовпчиків. За даними табл. 8с розраховуємо для кожної нульової комірки функцію вторинного штрафу і вводимо розраховані дані у табл.9.

Таблиця 9

Функція вторинного штрафу нульових комірок табл. 8

Нульові комірки ()	(1,4)	(2,4)	(4,2)	(4,3)
Вторинний штраф	24	21	24	21

Ми отримали два найбільших значення штрафу . Обираємо довільно одне з найбільших однакових значень, що розташовується, для конкретності, в комірці (1,4). Це означає, що дилер повинен на своєму шляху використати шлях (1,4). У табл. 8с ми викреслюємо рядок та стовпчик . У результаті ми отримуємо для етапу 3 табл.10.

Етап З

Таблиця 10

N	2	3
2	-	21
4	0	0

У табл. 10 забороняємо використовувати у розрахунках комірку і отримуємо табл. 11.

Таблиця 11

Скорочена матриця оцінок проїзду

N	2	3
2	-	21
4	0	-

У результаті ми отримали скорочену матрицю оцінок проїзду з двома рядками і двома стовпчиками. Далі розрахунки не виконуються, бо табл. 11 вказує маршрут завершення шляху дилера: (2,3) та (4,2).

Таким чином, маршрут дилера (3,1)+(1,4)+(2.3)+(4,2)=(1,4)+(4,2)+(2,3)+(3,1) є безперервним і має оцінку (оцінки - по табл. 2) . При цьому виконується умова або .

Отриманий шлях потрібно перевірити на оптимальність. З цією метою у початковій табл. 2 забороняємо до використання першу базову комірку (3,1) і отримуємо табл. 12.

Таблиця 12

Перевірка розрахунків

N	1	2	3	4
1	-	35	18	11
2	20	-	27	4
3	-	8	-	60
4	50	10	12	-

По табл. 12 виконуємо редукцію рядків і стовпчиків та отримуємо табл. 13, за даними якої розраховуємо . Тому що , отриманий розв'язок є правильним.

Таблиця 13

Перевірка розрахунків

N	1	2	3	4
1	-	24	7	0	11
2	16	-	23	0	4
3	-	0	-	52	8
4	40	0	2	-	10
	16	0	2	0

Тож отриманий шлях є правильним, і з урахуванням даних табл. 1 функція мети .

Якщо у розглянутій задачі про дилера не витримується умова , то треба з самого початку зробити редукцію стовпчиків, а потім - редукцію рядків.

Запропонована методика мінімізації експлуатаційних витрат дилерської мережі може бути запропонована для мережі будь-якої розмірності (дилерських пунктів). Використання сучасних обчислювальних машин при розв’язанні данної задачі, значно полегшить її розв’язання, що в кінцевому випадку призведе до підвищення ефективності виробничої діяльності фірми.

Література

1. М.М. Глушик, Н.М. Телесницька Н.М. Дослідження операцій. – Львів: «Новий світ-2000», 2009. -368 с.

2. Глушик М.М., Телесницкая Н.М. Математические аспекты эффективности производственной деятельности предприятия. Materialy ІV mezinarodni vedecko – prakticka konference «Efektivni nastroje modernich ved – 2008». Dil 5. Ekonomicke vedy: Praha. Publishing House «Education and Science» s.r.o -112 stran