Складання опорного плану

2.3 Складання опорного плану

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

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

Послідовність комунікацій

називають маршрутом, поєднуючим пункти  ( рис. 2.2 ).

   . . .

   .  

Рисунок 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 гривень.

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

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

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

Кінцевий опорний план для ВАТ „Житомироблпаливо” матиме вигляд:

Таблиця 2.7 Опорний план для ВАТ „Житомироблпаливо”

Таким чином загальна сума вартості вантажних перевезень дорівнює 428 889 гривень.

Похожие работы

Підвищення ефективності роботи підприємства на основі застосування економіко-математичних методів (на прикладі ВАТ "Дніпрополімермаш")

Скачать

155152

18

31

... і над плановим. Відомо, що собівартість є одним з головних джерел резервів підвищення ефективності роботи підприємства. Звідси сформуємо мету і задачі даної роботи. Метою даної роботи є підвищення ефективності роботи підприємства ВАТ «Дніпрополімермаш» шляхом управління собівартістю продукції. Відповідно, для досягнення поставленої мети необхідно вирішити наступні задачі: 1.   Проаналізувати ...

Фінансовий потенціал розвитку підприємства

Скачать

64259

5

1

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

Комплексна оцінка фінансового стану підприємства та шляхи його вдосконалення

Скачать

160613

15

0

... ЗАТ «Черкасивторресурси» необхідно проаналізувати можливість ефективного використання наявного майна та вдало розпоряджатися ним.   2.3 Прогнозна оцінка платоспроможності та фінансової стійкості підприємства Прогнозування фінансового стану підприємства є невід’ємним елементом його управлінням. Визначаючі фінансовий стан як складну систему, що є об’єктом прогнозування, нами пропонується ...

Інформаційна система аналізу діяльності підприємства для фінансового забезпечення інвестиційної діяльності

Скачать

159558

15

6

... »; 5)         підсистема «Розрахунок чистого дисконтованого доходу»; 6)         підсистема «Розрахунок індексу доходності проекту». Рис. 3.2. Структура інформаційної системи «Аналіз діяльності підприємства для фінансового забезпечення інвестиційних проектів» Далі приймається рішення щодо впровадження чи відхилення інвестиційного проекту. Усі ...