Підвищення ефективності діяльності підприємства ВАТ "Поліпромінвест" на основі використання економіко-математичних методів
Дипломная работа - Экономика
Другие дипломы по предмету Экономика
?лан це такий план, що серед усіх припустимих має найменшу вартість перевезень.
Опорним (базисним) планом транспортної задачі називають любе її допустиме, базисне рішення. Поняття опорного плану має наглядну геометричну інтерпритацію.
Послідовність комунікацій
називають маршрутом, поєднуючим пункти ( рис. 2.2 ).
. . .
.
Рисунок 2.2 Геометрична інтерпритація
Використовуючи маршрут, составленний із комунікацій, можливо виконати перевозку продукції із пункту в пункт , проходячи через пункти .
В процесі этого руху комунікації, що знаходяться на парних місцях, будуть пройдені в зворотньому напрямі.
Будь-яку сукупність значень (i=1,m j=1,n) називають планом перевезень. План, у якому відмінно від нуля не більше m+n-1 (тобто 13 для задачі ВАТ „Житомироблпаливо” та 12 для задачі ЗАТ „Херсоноблпаливо”), а інші рівні нулю, називається опорним.
Для знаходження опорного плану існують різноманітні способи. Наприклад, спосіб „північно-західного кута”, спосіб мінімальної вартості по рядку, спосіб мінімальної вартості по стовпцю та спосіб мінімальної вартості таблиці.
Найпростіший спосіб, так названий спосіб північно-західного кута. Проте цей метод не враховує специфіку матриці транспортних витрат. Таким чином потрібно використовувати метод мінімального елементу (у даному випадку спосіб мінімальної вартості таблиці). Цей метод в порівнянні з методом північно-західного кута дозволяє одразу отримати достатньо економічний план, скорочуючи загальний обсяг інтеграцій по його подальшій оптимізації.
Суть цих методів складається в тому, що базисний план складається послідовно, у декілька кроків. На кожному з цих кроків заповнюється одна клітинка таблиці даних, причому так, що або повністю задовольняються потреби одного із замовників (той, у таблиці якого знаходиться клітинка, що заповнюється), або повністю вивозиться весь запас вугілля з одного із складів (з тої, у рядку якої знаходиться клітинка, що заповнюється).
При методі найменшої вартості на кожному кроці побудови опорного плану першою заповнюється та клітинка частини таблиці, що залишилась, яка має найменший тариф. Якщо така клітинка не єдина, то заповнюється люба з них.
Складемо опорний план по методу північно-західного кута для ЗАТ „Херсоноблпаливо”. Отримаємо таблицю:
Таблиця 2.2 Опорний план по методу північно-західного кута
СкладиВ1В2В3В4В5В6В7В8A11500A23001200A31000700A41001001800A52008001400600
Таким чином загальна вартість перевезень буде коштувати 842 778 гривень. Загальна кількість невідємних клітинок дорівнює 12, тобто задовольняє умовам.
Так як даний план не є оптимальним та не враховує вартість перевезень, спробуємо інший метод потенціалів для побудови опорного плану .
Після того, як за допомогою методу „північно-західного кута” знайдений перший опорний план, потрібно виконати його поліпшення за допомогою методу потенціалів. Поліпшення плану перевезень у цьому методі використовується за допомогою переміщення перевезень із клітини в клітину в транспортній таблиці без порушення балансу заявок і запасів. Переміщення вантажів у таблиці виконується за замкнутим циклом.
Циклом у транспортній таблиці називаються декілька клітин, сполучених замкнутою ламаною лінією, що повертає на 90 в окремих клітинах. Цикл будують так, щоб одна його клітина була у вільній клітині, інші вершини в базисних (заповнених) клітинах. Алгоритм методу показаний на рисунку 2.1.
Рисунок 2.3 Алгоритм методу потенціалів
Метод потенціалів дозволяє автоматично виділити цикли з негативною ціною і визначити їхні ціни.
Существует несколько вариантов цикла :
1.) 2.) 3.)
Рисунок 2.4 Зображення видів циклу
Для цього поставимо у відповідність кожному пункту відправлення (складу) Аi число ?i, а кожному пункту призначення (споживачу) число Вj. Ці числа називаються потенціалами.
У кожному циклі змінюють одну вільну змінну на базисну, тобто заповнюють одну вільну клітину і натомість звільняють одну з базисних клітин. Цикл має парне число вершин. Позначаються знаком „+” ті вершини, у яких у результаті переміщення вантажів перевезення збільшуються, а знаком „-”, вершини, у яких вони зменшуються.
Перенести якусь кількість одиниць вантажу за циклом це значить збільшити перевезення, що стоять у позитивних вершинах циклу, на цю кількість одиниць, а перевезення, що стоять у негативних вершинах, зменшити на цю ж кількість.
При переносі будь-якої одиниці вантажу за циклом рівновага між запасами та заявками не змінюється. Кількість одиниць вантажу, що можна перемістити, визначається мінімальним значенням перевезень, що стоять у негативних вершинах циклу. Якщо перемістити більше число вантажу, то виникнуть негативні перевезення.
Зміна вартості перевезень при переміщенні однієї одиниці вантажу за циклом називають ціною циклу. Визначається ціна циклу як алгебраїчна сума вартостей перевезень, що стоять у вершинах циклу, причому, вартості, що стоять у позитивних вершинах, беруться зі знаком „+”, а в негативних зі знаком „-”. Для поліпшення плану перевезень доцільно переміщати вантажі тільки за тими циклами, ціна яких негативна.
Метод потенціалів дозволяє анатомічно виділити цикли з негативною ціною і визначити їхні ціни. Для цього поставимо у відповідність кожному пункту відправлення (складу) Аi число ?i, а ?/p>