Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






У кожному з рядків транспортної таблиці необхідно знайти клітину з мінімальною вартістю позначити його знаком *. Потім те ж потрібно виконати в кожному стовпці. Деякі клітини (відзначені **) мають мінімальні значення як по рядку, так і по стовпці. В такі клітини записується максимально можливі перевезення, виключаючи із розгляду після кожного запису 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) після перерозподілу перевезень і зміни базису будується нова транспортна таблиця (план перевезень), яка знову перевіряється на оптимальність методом потенціалів.

 

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

 


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

mylektsii.su - Мои Лекции - 2015-2024 год. (0.01 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал