Відстані між ВВ та ВО.

2.4. Побудова оптимального плану перевезень вантажів

ІІІ.3. Формування плану - заявки на перевезення вантажів

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

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

Якщо не всі споживачі задоволені і не всі постачальники витратили товари, повернення до п. 1, в іншому випадку задача вирішена.

Результатом складання план-заявки є деяка сукупність обсягів перевезень вантажу х_ij між і-м ВВ та j-м ВО(дод.5,6). Результати складання плану заявки спочатку подаються в матричній формі, а потім – в табличній (табл. ІІІ.3.1, ІІІ.3.2)(3-4ст).

Таблиця ІІІ.3.1

Таблиця ІІІ.3.2

Заявки на перевезення

ІІІ.4. Побудова оптимального плану перевезення вантажу

Розв'язати задачу оптимального обслуговування вантажовідправників та вантажоотримувачів автотранспортом, при якому буде виконаний план перевезень і буде мінімальним пробіг автомобілів, транспртні витрати та вантажооборот.

Задача оптимального обслуговування районів міста автомобільним транспортом розв'­язується як звичайна транспортна задача. Загальний алгоритм вирішення такої задачі за допомогою методу потенціалів наведений на рис.2.1 (показники m та n визначаються загальною кіль­кістю ВВ та ВО), l_ij – відстань між і-м постачальником та j-м споживачем (табл.2.1). Вантажооборот при доставці ij тонн вантажу від i -го постачальника до j -го споживача дорівнює Xij*lij; сумарний вантажооборот визначається як сума окремих величин вантажообороту [2]:

(1)

Вказаний аналітичний вираз є математичним формулюванням функції мети поставленої задачі. Крім того, можна визначити обмеження по вивозу вантажів від кожного ВВ та по розміру завозу -для кожного ВО:

(2)

(3)

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

Вказана задача носить назву транспортної, та відноситься до задач лінійного програмування. Одним з найбільш простих методів вирішення таких задач є метод потенціалів [2,18](див. рис.2.1).

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

Якщо план закріплення ВВ за ВО є оптимальним, то йому відповідає система з (т+п) чисел u_i та v_j, щозадовольняють наступні умови:

- для всіх завантажених клітин: (х_ij >0): u_i + v _j = l_ij (4)

- для всіх незавантажених клітин: (x_ij =0): u_i + v _j ≤ l_ij (5)

Зазначені показники u_i та v _j - називають допоміжними величинами (коефіцієнтами); їх визначають для кожного ВВ та ВО (рядка та стовпчика матриці вантажопотоків) і вказують в окремих графах (табл.ІІІ.4.1); таким коефіцієнтом може бути будь яке ціле число (в т.ч. і від'ємне), а також нуль.

Першим етапом перевірки оптимальності побудованого початкового (опорного) плану є визначення числових значень u_i та v _j. Для цього спочатку задаються нульовим значенням для першого ВО (рядка) або ВВ (стовпчика) (тобто v _j =0 або u_i =0). Аналогічні коефіцієнти для всіх інших ВВ та ВО (рядків та стовпчиків) розраховують послідовно, виходячи з наявних в них завантажених клітин, визначаючи невідоме друге значення з умови (4). Як вже зазначалось вище, оптимальним планом закріплення ВВ за ВО вважається такий план, для всіх незавантажених клітин якого виконується умова (5). Якщо ж серед незавантажених клітин матриці є одна чи декілька таких, для яких: u_i + v _j > l_ij, то така клітина називається потенціальною, а різниця між величиною відстані l_ij та алгебраїчною сумою (u_i + v _j) - величиною потенціалу. Наявність в плані (матриці) хоча б однієї такої клітини вказує на те, що він не є оптимальним, і його необхідно коригувати (змінювати) з метою ліквідації потенціальної клітини шляхом її завантаження [2,18]. При коригуванні плану серед усіх потенціальних клітин (якщо їх декілька) потрібно вибрати клітину із максимальною величиною потенціалу, і поліпшення плану доцільно розпочинати саме з цієї клітини. Її позначають знаком "+" та будують для неї деякий замкнений контур. Всі вершини цього контуру повинні знаходитись лише у завантажених клітинах (окрім тієї, що знаходиться в визначеній потенціальній клітині). Такий контур по суті визначає сукупність завантажених клітин матриці, величини транспортних зв'язків яких будуть змінюватись або перерозподілятись на даному етапі коригування.

Після цього, пересуваючись по контуру, почергово проставляють знаки "+" та "-" по всіх його вершинах(вершина, яка знаходиться у потенціальній клітині, як вже вказувалось, повинна мати знак "+"; крім того, якщо в плані є клітина із умовним завантаженням (нульова), вона в жодному разі не повинна знаходитися у вершині зі знаком "-"). Надалі серед тих вершин (клітин) контуру, які позначені знаком "-", вибирають клітину з мінімальною величиною завантаження (обсягу перевезення х_ij), і цю величину «переміщують» по вершинах контуру(виконують операцію віднімання або додавання згідно наявного знаку).

Отриманий в результаті проведеного коригування поліпшений план наводять в новій матриці вантажопотоків, в яку переносять значення відстаней l_ij, запасів a_і та потреб bj, початкові значення обсягів перевезення x_ij (для тих завантажених клітин, які не входили до складу контуру), а також відкориговані (змінені) значення цих обсягів x_ij. Цей план закріплення ВВ за ВО теж перевіряють на оптимальність(визначають кількість завантажених клітин та, при необхідності, коригують їх число; розраховують величини допоміжних коефіцієнтів, визначають наявність потенціальних клітин), і, якщо він не є оптимальним - знову проводять його коригування [2,18].

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

Таблиця ІІІ.4.1

Матриця вантажопотоків

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

N < m+n-1 N = m+n-1 N > m+n-1

Потенційних клітин немає

Не нашли, что искали? Воспользуйтесь поиском: