Курсовая работа: Моделювання бюджету доходів та витрат методом транспортної задачі

(1.11)

за умов

(1.12)

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

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

1) (1.13)

2) (1.14)

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

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

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

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

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

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

1) , ;

2) ,

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

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

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

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

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

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

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

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

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

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

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

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

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