183600 (596685), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Рисунок 2.2 Геометрична інтерпритація

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

В процесі этого руху комунікації, що знаходяться на парних місцях, будуть пройдені в зворотньому напрямі.

Будь-яку сукупність значень (i=1,m j=1,n) називають планом перевезень. План, у якому відмінно від нуля не більше m+n-1 (тобто 13 для задачі ВАТ „Житомироблпаливо” та 12 для задачі ЗАТ „Херсоноблпаливо”), а інші рівні нулю, називається опорним.

Для знаходження опорного плану існують різноманітні способи. Наприклад, спосіб „північно-західного кута”, спосіб мінімальної вартості по рядку, спосіб мінімальної вартості по стовпцю та спосіб мінімальної вартості таблиці.

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

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

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

Складемо опорний план по методу північно-західного кута для ЗАТ „Херсоноблпаливо”. Отримаємо таблицю:

Таблиця 2.2 Опорний план по методу північно-західного кута

Таким чином загальна вартість перевезень буде коштувати 842 778 гривень. Загальна кількість невід’ємних клітинок дорівнює 12, тобто задовольняє умовам.

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

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

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

Рисунок 2.3 Алгоритм методу потенціалів

Метод потенціалів дозволяє автоматично виділити цикли з негативною ціною і визначити їхні ціни.

Существует несколько вариантов цикла :

1 .) 2.) 3.)

Рисунок 2.4 Зображення видів циклу

Для цього поставимо у відповідність кожному пункту відправлення (складу) А_i число α_i, а кожному пункту призначення (споживачу) – число В_j. Ці числа називаються потенціалами.

У кожному циклі змінюють одну вільну змінну на базисну, тобто заповнюють одну вільну клітину і натомість звільняють одну з базисних клітин. Цикл має парне число вершин. Позначаються знаком „+” ті вершини, у яких у результаті переміщення вантажів перевезення збільшуються, а знаком „-”, вершини, у яких вони зменшуються.

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

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

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

Метод потенціалів дозволяє анатомічно виділити цикли з негативною ціною і визначити їхні ціни. Для цього поставимо у відповідність кожному пункту відправлення (складу) А_i число α_i, а кожному пункту призначення (споживачу В_j) – число β_j. Ці числа називаються потенціалами. Для визначення значень потенціалів складемо для базисних клітин m+n-1 рівнянь з m+n невідомими, тобто

Для отримання рішення потрібно прийняти α₀=0. Далі рівняння розв’язуються методом підстановки. Потім для незаповнених клітин обчислюють псевдо вартість за формулою

Для кожної незаповненої клітини ціна циклу перерахунку дорівнює різниці між вартістю C_ij та псевдо вартістю C’_ij. Наступним кроком алгоритму є перевірка опорного плану на оптимальність. Якщо для небазисних клітин плану (x_ij) , то план є оптимальним і ніякий спосіб поліпшений бути не може.

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

При розв’язанні транспортної задачі може бути отримане вироджене розв’язання, коли кількість базисних змінних менше ніж m+n-1. У цьому випадку одна або декілька базисних клітин залишаться незаповненими, що утрудняє розрахунок потенціалів у розв’язку задачі. Тому для ліквідації вродженості ставлять нуль у незаповнену базисну клітину. Ця клітина вважається заповненою при обчисленнях у циклі.

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

Таблиця 2.3 Розрахунок потенціалів та псевдо вартостей

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

Виконавши необхідні розрахунки отримаємо оптимальний план:

Таблиця 2.4 Опорний план оптимальний

Таким чином загальна вартість вантажних перевезень буде коштувати 510 006 гривень.

Проведемо аналіз транспортних перевезень для ВАТ „Житомироблпаливо”.

Виконавши необхідні розрахунки, отримаємо перший опорний план по методу „північно-західного кута”.

Таблиця 2.5 Опорний план для ВАТ „Житомироблпаливо” по методу північно-західного кута

Таким чином сума вантажний перевезень по методу північно-західного кута буде дорівнювати 647 802 гривень.

Характеристики

Список файлов ВКР