• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Метод подвійної переваги.

1. У кожному рядку знаходиться клітина з найменшою ціною і позначається позначкою.

2. Те ж саме проводиться для кожного стовпчика.

3. Заповнення таблиці починаємо з клітин, відзначених двома позначками.

4. Після цього заповнюються клітини з однією позначкою.

5. У таблиці, що залишилася, застосовується метод мінімальної вартості.

Схема плану :

N=7

План опорний, вироджений Z=4250 (гр. од.)

З трьох викладених методів даний метод, як правило, дає план з меншою загальною вартістю порівняно з іншими методами.

Контрольні запитання

1. Як економічно формулюється транспортна задача?

2. Якою є математична модель ТЗ?

3. Як треба будувати первісний план ТЗ за методом північно-західного кута?

4. Що таке цикл у таблиці ТЗ?

5. Якими є алгоритми методів найменшої вартості та подвійної переваги?

Лекція 6

Транспортна задача

Поліпшення плану

Розв’язування задачі у відкритій моделі

1. Загальний алгоритм розв’язування ТЗ

2. Перетворення виродженого плану у не вироджений

3. Метод потенціалів для оцінки плану

4. Поліпшення плану в циклі перерозподілу постачань. Приклад розв’язування ТЗ

5. Розв’язування ТЗ у відкритій моделі

1. Загальний алгоритм розв’язування транспортної задачі:

а)Побудова початкового опорного плану.

б)Оцінка плану на оптимальність.

в)Поліпшення плану, якщо він не є оптимальним.

г)Оцінка плану і т.д.

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

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

u_i-потенціал постачальника; v_j-потенціал споживача.

u_i+ v_j = c_ij (6.1)

У цій системі невідомих m+n, число рівнянь m+n-1. Отже, система має безліч розв’язків. Досить одержати один розв’язок системи. Для цього можна припустити, що u₁=0 і знайти інші невідомі з відповідних рівнянь.

Для кожної вільної клітини (i; j) обчислюється сума потенціалів постачальника і споживача

d_ij=u_i+v_j

і записується в цю клітину.

Якщо для всіх вільних клітин виконана нерівність

d_ij ≤ c_ij (6.2)

план перевезень оптимальний.

Якщо для деякої клітини

d_ij >c_ij (6.3)

план не є оптимальним і його можна поліпшити.

4. Поліпшення плану досягається перерозподілом постачань за циклом. Цикл повинен містити вершину в клітині з умовою (6.3), а інші вершини – у зайнятих клітинах. Обсяг товару, що перерозподіляється, дорівнює мінімумові з обсягів перевезень, що складаються в клітинах з парними номерами за циклом, початок якого знаходиться в обраній клітині з порушенням (6.2). (Інше пояснення буде в прикладі).

Розглянемо викладене на прикладі. Наступний початковий план отриманий методом мінімальної вартості.

Вартість плану

Z= 1005 гр.од.

Схема плану:

План опорний.

Кількість зайнятих клітин N=7, план не вироджений.

Складемо систему рівнянь для потенціалів

u₁ + v₃ = 3 u₃ + v₂ = 2

u₁ + v₄ = 4 u₄ + v₂ = 3

u₂ + v₁ = 1 u₄ + v₄ = 7

u₃ + v₄ = 2

u₂ + v₄ = 9

Нехай u₁ = 0; тоді одержимо

v₃ = 3; v₄ = 4; u₂ = 5; v₁ = -4; u₄ = 3; v₂ = 0; u₃ = 2

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

План не оптимальний, тому що в клітині (2,3) 8 > 6 і в клітині (3,4) 6 > 4.

Виберемо клітину (3,4) і побудуємо цикл перерозподілу.

75 * 35 40

45 40 85

min (40, 45) = 40. Передача від «-» до «+» 40 од. товару

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

Вартість плану

Z= 925 гр.од. N = 7.

Схема плану:

План опорний, не вироджений і не оптимальний; у клітині (2,3) 8 > 6.

Побудуємо цикл перерозподілу

90 10 80 20

* 10 10

min (90, 10) = 10 – кількість одиниць товару, перерозподілена за циклом.

Новий план перевезень

Вартість плану

Z= 905 гр.од.

План оптимальний, тому що для всіх вільних кліток виконана умова (6.3).

Читайте також:

1. B. Тип, структура, зміст уроку і методика його проведення.
2. D) методу мозкового штурму.
3. Demo 11: Access Methods (методи доступу)
4. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
5. I Метод Шеннона-Фано
6. I. ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ
7. I. Метод єдиної подібності.
8. I. Метод рiвних вiдрiзкiв.
9. II. МЕТОДИЧНІ ВКАЗІВКИ
10. II. УЧЕБНЫЕ И МЕТОДИЧЕСКИЕ ПОСОБИЯ, ПРАКТИКУМЫ
11. IV. КЕРІВНИЦТВО, КОНТРОЛЬ І НАДАННЯ ОРГАНІЗАЦІЙНО-МЕТОДИЧНОЇ ДОПОМОГИ ПРАКТИКАНТАМ.
12. IV. Метод супутних змін.

Переглядів: 630