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

У кожному з рядків транспортної таблиці необхідно знайти клітину з мінімальною вартістю позначити його знаком *. Потім те ж потрібно виконати в кожному стовпці. Деякі клітини (відзначені **) мають мінімальні значення як по рядку, так і по стовпці. В такі клітини записується максимально можливі перевезення, виключаючи із розгляду після кожного запису xij, відповідно, рядок або стовпець. Далі в частині матриці, що залишилася, записується максимально можливі перевезення в клоітини, відзначені знаком *. Після цього заповнюються непомічені клітини. Приклад одержання початкового плану приведено в табл. 2-8.

Таблиця 2-8

** * * *
      *
*      

 

Призначимо перевезення в клітини, позначені **.

          Ai
  2 ** 3 * 4 * 5 * 30, 10
  6 *
  9 *
bj 20  

 

Призначимо перевезення в клітини, позначені *.

          ai
  2 ** 3 * 4 * 5 * 30, 10
  6 *  
  9 *
bj 20 30, 20  

 

          ai
  2 ** 3 * 4 * 5 * 30, 10
  6 * 20
  9 *
bj 20 30, 20 25, 5  

 

Призначимо перевезення в клітини, що залишились.

          Ai
  2 ** 3 * 4 * 5 * 30, 10
  6 * 20
  9 *     40, 20
bj 20 30, 20 25, 5  

 

          Ai
  2 ** 3 * 4 * 5 * 30, 10
  6 * 20
  9 *   40, 20, 5
bj 20 30, 20 15 25, 5  

 

          Ai
  2 ** 3 * 4 * 5 * 30, 10
  6 * 20
  9 * 40, 20, 5
bj 20 30, 20 15 25, 5  

 

          ai
  2 ** 3 * 4 * 5 *
  6 *
  9 *
bj  

 

У даному початковому плані 6 базисних кліток, що відповідає числу постачальників і споживачів: 4+3-1=6. Якщо число базисних кліток більше m+n-1, то допущені помилки при складанні початкового плану. Якщо число базисних кліток менше m+n-1, то має місце випадок виродження. Загальна вартість виконання перевезень L=2·20+3·10+6·20+11·20+13·15+15·5=680 грн.

 

Випадок виродження початкового плану.

При вирішенні практичних задач можуть мати місце випадки, коли число базисних клітин менше m+n-1. В цьому випадку має місце випадок виродження. Виродження може статись, якщо призначення чергового перевезення призводить до одночасного виключення рядка і стовпця транспортної таблиці. Для побудови оптимального плану методом потенціалів необхідно збільшити число базисних кліток до m+n-1, уводячи "штучні нульові перевезення". Приклад складання початкового плану у випадку "виродження" наведено в табл. 9-11.

 

Призначимо перевезення x11=20. В цьому випадку потреби пункту b1 будуть повністю покриті за рахунок a1 і з таблиці виключається перший рядок і перший стовпець. Помітимо цю клітину буквою В.

 

        Ai
  2 ** В 20 4 * 5 * 20
  6 *
  9 *
bj 20  

 

Далі призначимо перевезення методом подвійної переваги. Останню заповнену клітину позначимо буквою П.

 

        Ai
  2 ** В 20 4 * 5 * 20
  6 * 20
  9 * П 5 20, 5
bj 20 15 25, 5  

 

В цій таблиці 4 базисних клітини, а повинно бути 3+3-1=5. Для того, щоб довести число базисних клітин до 5 призначаємо штучне нульове перевезення в клітину, що знаходиться на перетині рядка з міткою В та стовпця з міткою П, або стовпця з міткою В та рядка з міткою П:

 

        Ai
  2 ** В 20 4 * 5 * 20
  6 * 20
  9 * П 5 20, 5
bj 20 15 25, 5  

 

6. Знаходження оптимального плану перевезень у транспортній таблиці.

Побудований опорний план перевезень необхідно перевірити на оптимальність. Це можна виконати за допомогою методу потенціалів. Потенціали представляють собою умовну суму, яку вносить кожний з пунктів призначення Ai (потенціал Ui) та кожний з пунктів призначення Bj (потенціал Vj) за перевезення одиниці вантажу деякому перевізнику. Всього потенціалів m+n.

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

Ui + Vj=cij (3)

План перевезень буде оптимальним, якщо для всіх базисних клітин виконується умова (3), а для всіх вільних умова:

Ui + Vjcij (4)

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

1) цикл перерахування будується для вільної клітини, де порушення умови (4) буде максимальним, тобто: Ui + Vjcij = max.

Цикл будується таким чином, щоб всі його вершини, крім початкової (вільної клітини), знаходились в базисних (зайнятих) клітинах. При цьому в кожній вершині виконується поворот на 90º. Цикли перерахування можуть приймати наступні форми:

 

 

2) вільну клітина, що вводиться в план перевезень, помічається знаком „+”. Далі по черзі помічаються всі базисні клітини циклу знаками „–“ та „+” і т.д.

3) клітина, що помічена „–“, яка має найменше значення перевезення X*, повинна бути виключена з базису і стати вільною.

4) обсяги перевезень в клітинах, помічених знаком „+”, збільшується на величину X *, а в клітинах, помічених знаком „–”, зменшується на цю величину.

5) після перерозподілу перевезень і зміни базису будується нова транспортна таблиця (план перевезень), яка знову перевіряється на оптимальність методом потенціалів.

 

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

 








Дата добавления: 2015-12-22; просмотров: 1117;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.011 сек.