Поделиться Поделиться

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

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

Як і для класичної транспортної задачі, маємо m постачальників із запасами однорідного вантажу в кількості a1, a2, am та n споживачів, яким даний вантаж треба доставити в обсязі b1, b2, bn. Припустімо, що

m n

виконується умова балансу: 2 at = 2bj. Позначимо через Ху обсяг вантажу, що перевозиться від z'-ro постачальника j-му споживачеві. Відомий також час ty (i = 1, m; j = 1, n), за котрий вантаж перевозиться від z'-ro постачальника j-му споживачеві, й допускається, що він не залежить від 06сягів Перевезень Ху.

Треба скласти такий план перевезень, щоби повністю вивезти запаси всіх постачальників, цілком задовольнити, потреби всіх споживачів, а час доставки вантажу був мінімальний.

Складемо математичну модель розв'язання такої управлінської проблеми. Система обмежень даної задачі не відрізняється від системи обмежень класичної транспортної задачі. Позначимо через T максимальну величину з усіх можливих значень ty, що відповідають ненульо-

вим перевезенням (ху > 0): T = max t".

Критерієм оптимальності плану перевезень є мінімальна тривалість усіх перевезень. Таким чином, математична модель має вигляд:

T = max ty -" min; 2 ху < ai, i = 1, m;

m -

< 2 Ху ^ bj , j = 1, n;

1=1

Ху > 0, i = 1, m; у = 1, n.

Транспортна задача за критерієм часу не належить до задач лінійного програмування, оскільки її цільова функція не лінійна від змінних Ху. Розв'язування даної задачі дозволяється звести до послідовного розв'язання декількох задач лінійного програмування.

Транспортну задачу дозволяється сформулювати та розв'язати за декількома критеріями якості. Такі задачі називаються задачами багатокри-теріальної чи векторної оптимізації. При їх розв'язуванні існує три головні проблеми відносно: а) вибору принципу оптимальності, за яким дозволяється вирішити, через що один розв'язок кращий за інший; б) визначення вагових коефіцієнтів кожного показника якості, за якими вирішується, які показники важливіші, а які - менш важливі, причому сума вагових

n

коефіцієнтів дорівнює одиниці: 2аi = 1 в) нормування чи нормалізація

і=і

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

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

F (X) = {L( X), T (X )}-> min;

m n

L(X) = Т^ЦСуХу ->min;

mn

T(X) = tjXij -> min,

де c j, t j - вартість і час перевезення одиниці вантажу від 7-го постачальника j-му споживачеві.

Через D тут позначено допустиму множину розв'язків, що описується системою

2 Xj < at, i = 1, m;

m -

- Z xij > bj, j =1, n;

Xj > 0, i = 1, m; j = 1, n.

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

F(X) = а, LX)~Lmin + а2 T{X)~Tmin ^ min,

Lmax Lmin Tmax Tmin

де Ашп = тіп ДХІтж = тах ДХX

Ттіп = ІП Т (Х)' Ттах = Т (Х).

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

Висновки

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

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

3. Транспортна задача може бути узагальнена на випадок "некла-сичної" постановки: трьохіндексна транспортна задача, трьохіндексна транспортна задача з різними видами вантажу, чотирьохіндексна транспортна задача тощо.

4. Транспортна задача за критерієм часу виникає при перевезенні термінових вантажів, коли загальна вартість перевезень має другорядне значення, а на перше місце виходить час. Вона не належить до задач лінійного програмування, оскільки її цільова функція не лінійна. Методика розв'язування цих задач базується на розвантажувальних циклах.

5. Багатокритеріальні постановки транспортної задачі є моделями транспортних задач з кількома критеріями якості, наприклад загальна вартість перевезення вантажу та загальний час перевезення. Ця задача зводиться до скалярної транспортної задачі за допомогою згортки критеріїв якості до одного критерію, після чого вона розв'язується стандартними методами.

← Предыдущая страница | Следующая страница →