Назвіть етапи алгоритму методу потенціалів.

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

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

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

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

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

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

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

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

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

4.4. Побудова циклу і перехід до наступного опорного плану. Вибрана порожня клітина разом з іншими заповненими становить , отже, з цих клітин обов’язково утвориться цикл (теореми та наслідок § 5.2). У межах даного циклу здійснюють перерахування, які приводять до перерозподілу постачань продукції. Кожній вершині циклу приписують певний знак, причому вільній клітинці — знак «+», а всім іншим — за черговістю знаки «–» та «+». У клітин­ках зі знаком «–» вибирають значення q  і переносять його у порожню клітинку. Одночасно це число додають до відповідних чисел, які містяться в клітинках зі знаком «+», та віднімають від чисел, що позначені знаком «–». Якщо значенню q відповідає кілька однакових перевезень, то при відніманні залишаємо у відповідних клітинках нульові величини перевезень у такій кількості, що дає змогу зберегти невиродженість опорного плану.

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

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

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

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

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

 

45. Метод потенціалів. алгоритм

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

Вик-ся лвоїсті змінні: Ui - змінні, які х-ють процес постачання; Vj - х-ють процес споживання.

 Ці змінні наз. потенціалами задачі. Алгоритм розв`язування наступний:

1)Для усіх базисних змінних (не нульових) складається р-ня потенціалів: Хі НЕ=0: Ui + Vj = Cij

2)Одержана с-ма р-нь розв`язується відносно змінних Ui, Vj. С-ма розв`язується тільки в тому випадку, коли різниця між кількостями змінних та р-нь=1. Уцьому випадку одна із змінних довільно дорівнюється нулю,а потім послідовним аналізом кожного р-ня знаходяться ін. змінні.

 Якщо різниця між кількостями > 1, то така с-ма наз. виродженою, і щоб її розв`язати, її необхідно привести до норм. вигляду. Для цього одна із нульових змінних вважається фіктивною базисною, і с-ма доповнюється фіктивним р-ням потенціалів.

3)Складання р-ня потенціалів для вільних змінних і знаходження фактичних оціночних коефіцієнтів Сіj.

 Хі j =0: Ui = Vj = Cij

4)Аналіз одержаного плану на оптимальність С` ij = Cij

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

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

Згідно з побудованим циклом складається послідовність змінних. Потім така послідовність розмічається знаками "+", "-", починаючи з "+".

6)Знаходження нового плану розподілу ресурсів. Для цього знах. величина коригування, яка = мінімальному значенню змінної з позначкою "-".

 /\ = min { Xij }    !дописать!

Усі базисні змінні, які ввійшли до циклу, коригуються на величину /\ з відповідною позначкою, тобто Хі j = Xij + - /\. Змінні, які не ввійшли до циклу, не коригуються.

7)Одержаний новий план необхідно перевірити на оптимальність, починаючи з пункта №1.

 Примітка! Іноді трапляються випадки, коли неможливо побудувати нормальний цикл перерозподілу ресурсів. У цьому випадку дозволяється будувати вироджений цикл, у якому ще одна вершина, крім початкової, проходить через нульову змінну. Причому, знак цієї змінної повинен бути обов`язково "+".

 

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

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

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

До задач динамічного програмування належать такі, що пов’язані з оптимальним розподілом капіталовкладень, розподілом продукції між різними регіонами, визначенням найкоротшого шляху завезення товарів споживачам, задачі щодо заміни устат­кування, оптимального управління запасами тощо.

47.Які ви знаєте методи побудови опорного плану?

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

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

  Ідея методу північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевезень, з лівого верхнього (північно-західного) кута. У клітину записують менше з двох чисел а ₁ та b ₁. Далі переходять до наступної клітини в цьому ж рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнення таблиці у правій нижній клітинці. У такий спосіб значення поставок будуть розташовані по діагоналі таблиці.

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

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

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

 

48.який опорний план наз.невиродженим?

Опорний план транспортної задачі, як зазначалося раніше, має містити не більше ніж (m + n – 1) відмінних від нуля компонент. Якщо їх кількість дорівнює (m + n – 1), то такий опорний план називають невиродженим. Якщо ж кількість додатних компонент менша ніж (m + n – 1), то опорний план є виродженим. Вироджений план може виникати не лише за побудови опорного плану, але і при його перетвореннях у процесі знаходження оптимального плану.

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

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