Практичне заняття 1. Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда (стр. 10 )

Варіанти:

Навантаження	N1	N2	N3	N4
Час надходження	08.00	10.30	12.00	14.00

N1- номер по списку

N2 – (номер по списку +10000)/2

N3 - номер по списку +5000

N4 - номер по списку - 2000

Кількість надходжень поштового навантаження – 4.

Продуктивність праці одного працівника – 2 тис. листів за годину.

Норматив часу оброблення письмової кореспонденції у вузлі – 3 години.

Практичне заняття 4

Рішення задач поштового зв’язку методами лінійного програмування.

Мета: Вивчення різних способів рішення прикладних транспортних задач поштового зв'язку. Основна увага приділяється машинному способу рішення на ЕОМ, що має найбільший практичний зміст.

Ключові положення

Метод. керівництво: “Застосування методів теорії графів для розв’язування типових задач поштового зв’язку” -, , Одеса 2000.

Навчальний посібник: “Мережі та системи поштового зв’язку” -, , Кріль С. С, Одеса 2008.

, , Беркман зв¢язок. – К.: Техніка, 2003

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

Потрібно знайти таку схему прикріплення пунктів призначення до пунктів відправлення, за якої сумарні витрати на перевезення були б мінімальними.

Якщо позначити через кількість поштового вантажу, перевезеного з

пункту відправлення у пункт призначення, то

обмеження по обсягах пошти в пунктах відправлення можуть бути записані рівняннями:

або більш компактно.

Обмеження по обсягах пошти в пунктах призначення будуть відповідати наступним рівнянням:

або

Цільова функція повинна відповідати мінімуму загальних транспортних витрат на перевезення всієї пошти з пунктів відправлення в пункти призначення:

Інше

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

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

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

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

Заповнені клітки в транспортній таблиці складають групу базисних змінних. Їхня кількість буде дорівнювати:

Таблиця

На початку транспортна таблиця не заповнена, тобто відсутні значення обсягів перевезеного вантажу в клітках таблиці.

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

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

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

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

початкові рішення по методу північно-західного кута. Рішення

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

призначення . Ця заявка може бути задоволена за рахунок запасу з

першого пункту відправлення. Після корегування по стовпцю і по

рядку будемо мати,. Заявка по першому пункту

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

2. Максимально допустиме значення надається першому не викресленому елементу другого стовпця. Виходить, що заявка для другого пункту

призначення може бути задоволена частково за рахунок першого пункту відправлення. Після корегування по стовпцю і по рядку будемо мати . Заявка по другому пункту призначення частково

задоволена, а запас в пункті відправлення рівне нулю.

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

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

елементи стовпця рівні нулю.

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

5. Надається максимальне допустиме значення першому не викресленому елементу четвертого стовпця . Заявка для четвертого пункту призначення виконана частково за рахунок другого пункту відправлення. Після корегування по стовпцю і по рядку будемо мати Викреслюємо другий рядок.

6. Залишається не викресленим один елемент , якому надається максимально-допустиме значення . Заявка для четвертого пункту призначення відповідна цілком за рахунок третього пункту відправлення. Процес заповнення транспортної таблиці базисними елементами закінчений.

Кількість базисних змінних дорівнює необхідному

Отримано початкове базисне рішення, , , ,

, . Інші змінні залишаються вільними та дорівнюють нулю.

Загальні транспортні витрати дорівнюють:

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

Вирішення не є оптимальним, тому що є інші варіанти розподілу перевезень, за якихзменшується.

Таблиця 2

Таблиця З

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

1. З усіх вартостей перевезення одиниці вантажу в транспортній таблиці вибирають найменшу.

2. Розмір заявки відповідного пункту призначення записують у цю клітку.

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

4. Викреслюється стовпець, якщо розмір заявки дорівнює нулю або викреслюється рядок, якщо запас у пункті відправлення дорівнює нулю.

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

Приклад. Для раніше розглянутого прикладу з вихідними даними, зазначеними в табл.2. Знайти початкове вирішення по методу мінімальної вартості.

Рішення 1. Вибираємо клітку з мінімальною вартістю . Значення заявки

пункту призначення запишемо в цю клітку (табл. 4). Одержимо

значення базисної змінної . Запас вантажу, що залишився, при

перевезенні із першого пункту відправлення. Заявка в пункті

призначення виконана цілком. Викреслюємо перший рядок і

другий стовпець.

2. З не викреслених елементів вибираємо кліткуз мінімальною вартістю
. Значення заявки пункту призначення запишемо в цю клітку.

Одержимо базисну змінну. Запас перевезеного вантажу, що залишився

у третьому пункті відправлення, буде дорівнювати . Значення

заявки в першому пункті призначення. Викреслюємо третій рядок

і перший стовпець.

3. З не викреслених елементів виберемо клітку з мінімальною вартістю . Значення заявки пункту призначення запишемо в цю клітку.

Одержимо базисну змінну. Запас, що залишився в другому пункті

відправлення, буде . Значення заявки, що

залишилася, у третьому пункті призначення

Викреслюємо третій стовпець.

4.3алишився не викресленим елемент. Значення заявкизапишемо в

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

, а значення заявки, що залишилася, Розрахунок базисних елементів закінчений. Результати розрахунку занесені в табл. 4. Отримано початкове базисне рішення , ,,

. Інші змінні вільні. Загальні транспортні витрати рівні:

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

Поліпшення початкового рішення

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

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

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

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

Знаходження змінної, що уводиться в базис

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

Другий метод, заснований на принципі оптимальності, називається методом потенціалів. В його основу покладене значення та знак коефіцієнтів при змінних в-рівнянні.

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