Один із способів розв'язування транспортної задачі ґрунтується на розгляді двоїстої задачі.

Розглянемо транспортну задачу (1.1-1.4). Позначимо змінні двоїстої задачі, які відповідають рівнянням (1.2), через , а для рівнянь (1.3) - через . Оскільки всі обмеження транспортної задачі є рівняннями, то пара спряжених задач є несиметричною і ніякі обмеження на знаки змінних двоїстої задачі та не накладаються.

Для побудови двоїстої задачі поставимо у відповідність обмеженням початкової задачі змінні двоїстої:

(1.9),

(1.10),

Згідно з загальними правилами побудови двоїстих задач маємо:

(1.11)

за умов

(1.12)

Змінні та задачі (1.11), (1.12) двоїстої до транспортної мають назву потенціалів.

Для того, щоб плани відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості:

1) (1.13)

2) (1.14)

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

Перша умова виконується у двох випадках:

а) якщо . Другий співмножник бо за умовою ();

б) якщо , то за умовою транспортної задачі , тоді ().

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

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

1) , ;

2) ,

для всіх , то він є оптимальним планом транспортної задачі.

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

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

1. Визначення типу транспортної задачі (відкрита чи закрита). За необхідності слід звести задачу до закритого типу.

2. Побудова першого опорного плану транспортної задачі одним з відомих методів.

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

4. Перевірка плану транспортної задачі на оптимальність.

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

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

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

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

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

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

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

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

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

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

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

Особливості відкритих транспортних задач з додатковими умовами.

1. Додаткова умова заборони перевезень від певного постачальника до певного споживача. В такому разі в оптимальному плані відповідні клітини обов'язково мають бути вільними ().

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

2. Додаткова умова перевезення за окремими маршрутами строго визначеного обсягу продукції, тобто виконання обов'язкових постачань. В оптимальному плані відкритої транспортної задачі з такою додатковою умовою клітини відповідних фіктивно введених постачальників чи споживачів мають бути вільними.

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

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

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

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

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

2. На практиці часто потрібно визначити оптимальний план перевезень неоднорідної продукції, тобто розв'язати багатопродуктову задачу. Її математична модель має такий вигляд:

;

;

;

,

де - індекс виду продукції, що необхідно перевезти.

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

1.3 Загальна характеристика підприємства ВАТ "Інгулецький гірничо-збагачувальний комбінат"

Аналіз показників ліквідності і платоспроможності ВАТ "ІнГЗК" протягом 2008-2009 рр.

Аналіз даних табл.1.2 свідчить, що всі показники ліквідності за результатами діяльності протягом 2009 року мають тенденцію до збільшення. На ВАТ "ІнГЗК" станом на 31.12.2009р. значення даного коефіцієнту складає 3,806, що перевищує нормативні значення (1,00 - 2,00) та свідчить про високий ступінь ліквідності підприємства. Він показує, яку частину поточних зобов'язань підприємство ВАТ "ІнГЗК"" спроможне погасити, якщо воно реалізує усі свої оборотні активи, в тому числі і матеріальні запаси. Цей коефіцієнт показує, що станом на кінець 2009 р.3,81 гривні оборотних коштів приходиться на кожну гривню поточних зобов'язань. А отже підприємство спроможне своєчасно розрахуватися по зобов'язанням своїми ліквідними активами.

Коефіцієнт швидкої ліквідності у 2009 році збільшився на 0,57 пунктів, і сягнув значення 3,6. Він показує, що 3,6 частини поточних зобов'язань підприємство спроможне погасити за рахунок найбільш ліквідних оборотних коштів - грошових коштів та їх еквівалентів, фінансових інвестицій та кредиторської заборгованості. Цей показник показує платіжні можливості підприємства щодо погашення поточних зобов'язань за умови своєчасного здійснення розрахунків з дебіторами. Даний коефіцієнт перевищує рекомендоване значення, що є позитивним для фінансової діяльності ВАТ "ІнГЗК". Коефіцієнт абсолютної ліквідності станом на 31.12.2009р.0,01 близький до нульового значення, що вказує на дефіцит грошових коштів для покриття короткострокових зобов'язань.

Величина чистого оборотного капіталу станом на 31.12.2009р. складає 4152890 тис. грн., що свідчить про спроможність підприємства сплачувати свої поточні зобов'язання та розширювати подальшу діяльність. Таким чином, в цілому по ВАТ "ІнГЗК" можна говорити про високий рівень ліквідності.

Розділ 2. Застосування моделі транспортної задачі для бюджетування доходів і витрат ВАТ "ІнГЗК"

2.1 Аналіз динаміки доходів та витрат ВАТ "ІнГЗК"

Аналіз фінансових результатів ВАТ "ІнГЗК" за 2008-2009 рр. (тис. грн.)

Аналіз даних таблиці 2.1 свідчить, що за результатами діяльності підприємства протягом 2009 року, чистий прибуток зменшився на - 3789291 тис. грн. або на 80,23 % відносно фінансового результату 2008 року.

Такі зміни сталися через значне зменшення в 2009 році статті "Інші доходи" на - 224926 тис. грн. (або на - 86,91 %), рис.2.1

При цьому спостерігається збільшення таких витрат як витрати на збут, які на кінець 2009 року складають 287532 тис. грн., що більше попереднього періоду на 129628 тис. грн або 82,09 % відносно 2008 року; інші операційні витрати, які збільшилися на 1234007 тис. грн. або на 26,63 % відносно попереднього періоду і на кінець 2009 року складають 586756 тис. грн.

Рис.2.1 Темпи приросту витрат та доходів ВАТ "ІнГЗК" за результатами діяльності в 2009 році.

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

В таблиці 2.2 представлений перелік показників рентабельності та формули їх розрахунку.

Таблиця 2.2

Оцінки пріоритетів направлення використання отриманого доходу за видами видатків ВАТ "ІнГЗК" задана матрицею оцінок експертів. При цьому оцінки 0,1 надається значення як кращий варіант напрямку фінансування витрат, а оцінка 1 - фінансування витрат за рахунок відповідного виду доходу не рекомендується.

Таблиця 2.3

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

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

1. Підрахуємо число зайнятих клітин таблиці, їх 10, а має бути

m+n-1 = 10

Отже, опорний план є невироджених.

2. Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i, v_i. по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij, вважаючи, що u₁ = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких u_i + v_i > c_ij

(1;6): 0 + 0.9 > 0.8, (1;7): 0 + 0.6 > 0

(3;5): - 0.6 + 1 > 0.1, (4;6): - 0.6 + 0.9 > 0.1

Вибираємо максимальну оцінку вільної клітини (1;7): 0

Для цього в перспективну клітку (1;

7) поставимо знак "+", а в інших вершинах багатокутника чергуються знаки "-", "+", "-". Цикл наведено в таблиці.

Із сум коштів х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2,7) = 1331548. Додаємо 1331548 до обсягів коштів, що стоять в плюсових клітинах і віднімаємо 1331548 з Х_ij, що стоять в мінусових клітинах.

В результаті отримаємо новий опорний план.

3. Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i, v_i. по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij, вважаючи, що u₁ = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких u_i + v_i > c_ij

(1;6): 0 + 0.9 > 0.8

(3;4): 0 + 0.7 > 0.6

(3;5): 0 + 1 > 0.1

(3;6): 0 + 0.9 > 0.6

(4;5): 0 + 1 > 0.5

(4;6): 0 + 0.9 > 0.1

Вибираємо максимальну оцінку вільної клітини (3;5): 0.1

Для цього в перспективну клітку (3;5) поставимо знак "+", а в інших вершинах багатокутника чергуються знаки "-", "+", "-". Цикл наведено в таблиці.

Із сум коштів х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3,7) = 138543. Додаємо 138543 до суми коштів, що стоять в плюсових клітинах і віднімаємо 138543 з Х_ij, що стоять в мінусових клітинах.

В результаті отримаємо новий опорний план.

4. Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i, v_i. по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij, вважаючи, що u₁ = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких u_i + v_i > c_ij

(1;6): 0 + 0.9 > 0.8

(4;5): 0 + 1 > 0.5

(4;6): 0 + 0.9 > 0.1

Вибираємо максимальну оцінку вільної клітини (4;6): 0.1

Для цього в перспективну клітку (4;

6) поставимо знак "+", а в інших вершинах багатокутника чергуються знаки "-", "+", "-".

Цикл наведено в таблиці.

Із сум коштів х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (4,7) = 33865.

Додаємо 33865 до суми коштів, що стоять в плюсових клітинах і віднімаємо 33865 з Х_ij, що стоять в мінусових клітинах.

В результаті отримаємо новий опорний план.

4. Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i, v_i. по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij, вважаючи, що u₁ = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких u_i + v_i > c_ij (1;6): 0 + 0.9 > 0.8.

Вибираємо максимальну оцінку вільної клітини (1;6): 0.8

Для цього в перспективну клітку (1;6) поставимо знак "+", а в інших вершинах багатокутника чергуються знаки "-", "+", "-". Цикл наведено в таблиці.

Із коштів сум х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2,6) = 102608. Додаємо 102608 до обсягу сум, що стоять в плюсових клітинах і віднімаємо 102608 з Х_ij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.

3. Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i, v_i. по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij, вважаючи, що u₁ = 0.

Опорний план є оптимальним. Сума експертних оцінок складає:

F (x) = 0.1*2156233 + 0.15*55112 + 0.2*287532 + 0.7*278759 + 0.8*102608 + 0*1503956 + 0.1*5588803 + 0.4*37870 + 0.1*138543 + 0.1*33865 = 1149883.3

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

1. Обсяг чистого доходу від реалізації продукції покриває відповідні витрати наступним чином:

- 100 % собівартість реалізованої продукції (2156233 тис. грн.),

- 100 % адміністративні витрати (55112 тис. грн.),

- 100 % витрати на збут (287532 тис. грн.);

- 4,8 % інших операційних витрати або 278759 тис. грн.;

- 75,2 % інших витрат або 102608 тис. грн.

- 100 % прибутку або 1503956 тис. грн.

2. Інші операційні доходи покривають витрати наступним чином:

- 95,2 % інших операційних витрати або 5588803 тис. грн;

- 21,5 % фінансових витрат або 37870 тис. грн.;

3. Інші фінансові доходи покривають 78,5 % фінансових витрат або 138543 тис. грн.