МУ к практ раб Транспортная логистика

Виключаємо l -й рядок як повністю "використаний":

І т. д. Остаточний варіант:

Число відмічених клітин = число рядків + число стовпців - 1: 6 = 3 + 4 - 1 - вірно.

Вартість перевезення рівна:

2*30 + 1*120 + 2*70 + 5*70 + 3*50 + + 7*130 = 1730.

Ми бачимо, що цей первинний план гірше за первинний план з прикладу 1. Хоча буває і навпаки.

Завдання для самостійного вирішення. Знайти первинний план постачань методом мінімальної вартості.

9

РОЗПОДІЛЬНИЙ МЕТОД РІШЕННЯ ТРАНСПОРТНОЇ ЗАДАЧІ

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

Оцінка клітини (i, j) обчислюється за наступним правилом:

оц³нка i-го рядка + оц³нка j-го стовпця + число в л³вому верхньому кутку кл³тини (i, j).

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

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

Приклад 3. У прикладі 1 був отриманий наступний план постачань. Досліджуємо його на оптимальність.

190 40 120 30

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

Оцінка клітини (1,1) = оцінка 1-го рядка + оцінка 1-го стовпця + число в лівому верхньому кутку клітини (1,1) = оцінка 1-го рядка + 0 + 4 = 0 (так повинно бути для відміченої клітини). Звідси оцінка 1-го рядка = - 4.

Оцінка клітини (2,1) = оцінка 2-го рядка + оцінка 1-го стовпця + число в лівому верхньому кутку клітини (2,1) = оцінка 2-го рядка + 0 + 3 = 0 (так повинно бути для відміченої клітини). Звідси оцінка 2-го рядка = - 3.

Знайдені оцінки стовпців запишемо під таблицею, знайдені оцінки рядків - праворуч від таблиці.

Після цього кроку отримуємо наступну таблицю:

10

0

Тепер потрібно знайти відмічену клітину, для якої відомі оцінка рядка або оцінка стовпця. Наприклад, це клітина (2,2). Для неї відома оцінка рядка. Оцінка клітини (2,2) = оцінка 2-го рядка + оцінка 2-го стовпця + число в лівому верхньому кутку клітини = (- 3) + оцінка 2-го стовпця + 1=0. Звідси оцінка 2-го стовпця = 2.

Після цього кроку отримуємо наступну таблицю:

Для відміченої клітини (2,3) ми знаємо тільки оцінку рядка.

Оцінка клітини (2,3) = оцінка 2-го рядка + оцінка 3-го стовпця + число в лівому верхньому кутку клітини = (- 3) + оцінка 3-го стовпця + 2 = 0. Звідси оцінка 3-го стовпця = 1.

Після цього кроку отримуємо таблицю:

Оцінка клітини (3,3) = оцінка 3-го рядка + оцінка 3-го стовпця + число в лівому верхньому кутку клітини (3,3) = оцінка 3-го рядка + 1 + 3 = 0. Звідси оцінка 3-го рядка = - 4.

11

Після цього кроку отримуємо наступну таблицю:

Оцінка клітини (3,4) = оцінка 3-го рядка + оцінка 4-го стовпця + число в лівому верхньому кутку клітини = (- 4) + оцінка 4-го стовпця + 7 = 0. Звідси оцінка 4-го стовпця = - 3.

Після цього кроку отримуємо наступну таблицю:

Знайдені оцінки усіх рядків і стовпців. Вичислимо оцінки усіх клітин і складемо матрицю оцінок.

Оцінка клітини (1,2) = оцінка 1-го рядка + оцінка 2-го стовпця + число в лівому верхньому кутку клітини (- 4) + 2 + 7 = 5.

Оцінка клітини (1,3) = оцінка 1-го рядка + оцінка 3-го стовпця + + число в лівому верхньому кутку клітини (- 4) + 1 + 2 = - 1.

І т. д.

Отримуємо наступну матрицю оцінок :

Оскільки матриця оцінок містить негативні числа, то наш план постачань є неоптимальним. Проведемо його оптимізацію. Вибираємо клітину з найменшою оцінкою. Це клітина (1,4). Не оцінка рівна - 4. Наше завдання - побудувати цикл перерахунку. Виходячи з клітини (1,4) і рухаючись тільки по відмічених клітинах, треба повернутися в стартову клітину (1,4). При цьому забороняється робити два послідовні кроки в одному рядку або в одному стовпці. Наприклад, підходить цикл

12

(1,4) → (1,1) → (2,1) → (2,3) → (3,3) → (3,4) →(0,4).

Намалюємо цей цикл. Для кожної клітини вказані її індекси і об'єм постачань.

Стартовій клітині (1,4) припишемо знак "+". Рухаючись по циклу, чергуємо знаки. Серед постачань в клітини зі знаком "─" (це клітини (1,1) (2,3) (3,4)) знайдемо мінімальну: min (30, 30, 130) = 30. Після цього в клітинах зі знаком "─" зменшимо постачання на цей мінімум, а в клітинах зі знаком "+" збільшимо на цей мінімум. Клітина (1,4) стає відміченою.

Якщо отримана одна клітина з нульовим постачанням, то вона стає порожньою. У нас таких клітин дві - (1,1) (2,3). Тому порожньою оголосимо тільки одну з них з найбільшим тарифом - клітину (1,1). В клітину буде зроблено нульове постачання, і вона залишиться відміченою. Це робиться для виконання співвідношення :

число відмічених клітин = число рядків + число стовпців - 1.

Отримуємо новий план постачань.

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

Для нового плану знаходимо оцінки рядків і стовпців. Потім отримаємо матрицю оцінок клітин :

План є неоптимальним, оскільки оцінка клітини (2,4) менше нуля. Будуємо 13

для неї цикл перерахунку :(2,4).

min (0, 100) = 0. Клітина (2,3) стає порожньою, а клітина (2,4) відміченої (нульове постачання). Новий план постачань :

Для нового плану знаходимо оцінки рядків і стовпців. Потім отримаємо матрицю оцінок клітин :

План є неоптимальним, оскільки оцінка клітини (3,1) менше нуля. Будуємо для неї цикл перерахунку :(3,1).

min (70, 100) = 70. У клітинах з "+" постачання збільшуються на 70, а в клітинах з "─" постачання зменшуються на 70. Клітина (2,1) стає порожньою.

14

Новий план постачань :

Знаходимо оцінки рядків і стовпців. Отримуємо матрицю оцінок :

Матриця оцінок не містить негативних чисел. Отриманий оптимальний план постачань. Сумарні витрати на перевезення вантажу рівні:

3*30 + 1*120 + 4*70 + 5*70 + 3*150 + 7*30 = 1500.

Нагадаємо, що сумарні витрати на перевезення вантажу для первинного плану були 1690.

Постачальник А1 повинен поставити 30 одиниць вантажу споживачеві В4. Постачальник А2 повинен поставити 120 одиниць вантажу споживачеві В2 і 70 одиниць вантажу споживачеві В4. Постачальник А3 повинен поставити 70 одиниць вантажу споживачеві В1, 150 одиниць вантажу споживачеві В3, і 30 одиниць вантажу споживачеві В4.

Завдання для самостійного вирішення.

Знайти оптимальний план постачань.

15

ВІДКРИТА МОДЕЛЬ

Відкрита модель зводиться до закритої моделі.

Фіктивний споживач

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

Приклад 4.

Сумарна потужність постачальників 40 + 60 + 50 = 150, сумарний попит споживачів 30 + 40 + 60 = 130. Це відкрита модель. Вводимо фіктивного споживача, якому припишемо попит 150 - 130 = 20. Вартість перевезення одиниці вантажу до фіктивного споживача дорівнює нулю. Отримуємо наступну закриту модель.

Завдання для самостійного вирішення. Знайти оптимальний план постачань в прикладі 4.

16

Фіктивний постачальник

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

Приклад 5.

Сумарна потужність постачальників 10 + 40 + 30 = 80, сумарний попит споживачів 20 + 30 + 50 = 100. Модель - відкрита. Вводимо фіктивного постачальника, якому припишемо потужність 100 - 80 = 20. Вартість перевезення одиниці вантажу від фіктивного постачальника до споживачів дорівнює нулю. Отримуємо наступну закриту модель.

Завдання для самостійного вирішення. Знайти оптимальний план постачань в прикладі 5.

17

ТРАНСПОРТНЕ ЗАВДАННЯ В МЕРЕЖЕВІЙ ПОСТАНОВЦІ. ТРАНСПОРТНА МЕРЕЖА

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

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

На план постачань накладаються наступні умови:

1.Усі потужності постачальників мають бути розподілені.

2.Увесь попит споживачів має бути задоволений.

3.До кожної вершини повинна підходити або виходити з неї хоч би одна

стрілка.

4.Число стрілок = число вершин - 1.

5.Стрілки не повинні утворювати замкнутий контур (при цьому неважливо, рухаємося ми по стрілках або проти них).

Особливий випадок транспортного завдання в мережевій постановці проявляється в тому, що при повному використанні потужностей постачальників і повному задоволенні попиту споживачів число стрілок < n - 1, де n - загальне число вершин (у тому числі і нульові). Тоді додатково вводиться потрібна кількість стрілок. При цьому стрілки не повинні утворювати замкнутий контур.

Приклад 6. Задана наступна транспортна мережа:

2

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

У постачальників 1, 4 і 7 є 190, 30 і 250 одиниць вантажу відповідно. Споживачам 2, 3, 5 і 6 вимагається 120, 70, 150 і 130 одиниць вантажу відповідно.

18