11767

Транспортна задача лінійного проґрамування

Практическая работа

Математика и математический анализ

Транспортна задача лінійного проґрамування. Математична та змістовна постановка транспортної задачі. Методи знаходженння початкового опорного плану транспортної задачі. Метод потенціалів. Розв’язування транспортних задач з ускладненнями в постановці....

Украинкский

2013-04-11

656.5 KB

66 чел.

  1.  Транспортна задача лінійного проґрамування.
  2.  Математична та змістовна постановка транспортної задачі.
  3.  Методи знаходженння початкового (опорного) плану транспортної задачі.
  4.  Метод потенціалів.
  5.  Розв’язування транспортних задач з ускладненнями в постановці.
  6.  Транспортна модель з проміжними пунктами
  7.  Інтерпретація методу потенціалів як симплекс-методу.
  8.  Метод диференційних рент.
  9.  Задача про призначення.
    1.  Математична та змістовна постановка транспортної задачі

Змістовно транспортна задача формулюється наступним чином.  Необхідно перевезти однорідний продукт з пунктів зберігання (комор) в пункти споживання таким чином, щоб загальна вартість перевезень була мінімальною. Наявно m пунктів зберігання A1,...,Am та n пунктів споживання B1,...,Bn. Запас продукту в кожному i-му пункті зберігання  Ai становить аі, а потреби в кожному j-му пункті споживання Bj  рівні bj. Вартість перевезення одиниці продукту з кожного i-го пункту зберігання в кожний j-й пункт споживання також відома і становить сij. Якщо сумарні потреби рівні сумарним запасам продукту в коморах —  — то транспортна задача є задачею закритого типу, формальна математична модель якої виглядає наступним чином:

, , , ,  .

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

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

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

  1.  Закрита транспортна задача завжди має припустимий розв’язок.

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

2. Ранґ матриці системи обмежень-рівностей закритої невиродженої транспортної задачі .

Матриця коефіцієнтів обмежень транспортної задачі за умови приведення задачі до класичного вигляду задачі лінійного програмування з впорядкуванням змінних  в загальному випадку має вигляд:

 

Доведемо, що ранг матриці А рівний .

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

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

......................................................................................

......................................................................................

.

Звідси .

Для інших  з -го до до -го отримаємо

..........................................................................................

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

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

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

  1.  Знаходження початкового опорного плану транспортної задачі (початкового базового розв’язку).
  2.  Покрокове покращення плану перевезень до моменту досягнення оптимального.
    1.  Методи знаходженння початкового (опорного) плану транспортної задачі

Для знаходження початкового опорного плану транспортної задачі використовується один з трьох методів: метод північно-західного кута; метод мінімального елемента;  еврістичний метод Фойґеля.

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

            Bj

Ai

B1

...

Bn

Запаси

A1

c11

      x11

...

c1n

         x1n  

a1

...

...

...

...

...

Am

cm1

        xm1

cmn

      xmn

am

Потреби

b1

...

bn

Метод північно-західного кута.

При знаходженні розв’язку задачі за допомогою методу північно-західного кута заповнення клітинок значеннями перевезень починається від верхнього лівого (“північно-західного”) кута таблиці; надалі рух та заповнення відповідних клітинок відбувається зліва направо до моменту вичерпання запасу відповідного пункту; якщо запас вичерпаний, опускаємося на клітинку вниз і продовжуємо рух до моменту вичерпання всіх запасів.

Метод мінімального елемента.

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

Еврістичний метод Фойґеля.

На кожній ітерації методу Фойґеля для кожного стовпчика та рядка таблиці обчислюється різниця між значеннями мінімального та найближчого до нього тарифів відповідного стовпчика чи рядка та записується у відповідні клітинки додаткового стовпчика та рядка. Серед обчислених різниць обираємо максимальну і у відповідному стовпчику чи рядку знаходимо  мінімальний тариф з призначенням перевезення цій клітинці.

Якщо є декілька однакових тарифів, то для заповнення обирається клітинка, що відповідає максимальній різниці.

Приклад.

Умова транспортної задачі задана таблицею:

  

B1

B2

B3

B4

Зап.

A1

7

      

8

      

1

     

2

           

160

A2

4

        

5

        

9

        

8

      

140

A3

9

       

2

        

3

        

6

      

170

Потр.

120

50

190

110

470

а).Застосовуємо метод північно-західного кута:

B1

B2

B3

B4

Зап.

A1

7

   120

8

     40

1

     

2

      

160

A2

4

        

5

     10

9

     130

8

      

140

A3

9

       

2

        

3

      60

6

    110

170

Потр.

120

50

190

110

470


б).Застосовуємо метод мінімального елемента:

B1

B2

B3

B4

Зап.

A1

7

   

8

     

1

     160

2

      

160

A2

4

     120

5

     

9

     

8

     20

140

A3

9

       

2

     50

3

      30

6

     90

170

Потр.

120

50

190

110

470

в). Застосовуємо еврістичний метод Фойґеля:

B1

B2

B3

B4

Зап.

A1

7

   

8

     

1

    50

2

  110

160

1

6

-

-

A2

4

   120

5

   20

9

     

8

     

140

1

1

1

1

A3

9

       

2

    30

3

    140

6

     

170

1

1

1

7

Потр.

120

50

190

110

470

3

3

2

4

3

3

2

-

5

3

6

-

5

3

-

-

  1.  Метод потенціалів для знаходження оптимального розв’язку транспортної задачі

Метод потенціалів є особливим випадком симплекс-методу, що враховує особливості транспортної задачі. Метод потенціалів ґрунтується на наступній теоремі.

Теорема про потенціали.

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

Величини   та  називаються потенціалами пунктів постачання та пунктів споживання відповідно.

Алгоритм методу потенціалів включає наступні кроки.

  1.  Розраховуємо значення потенціалів рядків та стовпців   та , розв’язуючи систему рівнянь , що складені для заповнених клітинок транспортної задачі. Число заповнених клітинок дорівнює , а система має  невідомих, тому для визначеності приймаємо  та послідовно з рівнянь знаходимо інші значення   та .

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

а). Побудова циклу.

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

б). Переміщення перевезень в межах клітинок, пов’язаних з вільною циклом.

 Починаючи з вільної клітинки, якій приписується знак +, іншим почергово, просуваючись за циклом, приписуємо знаки — та +.

В вільну клітинку переносимо найменше з чисел  , що знаходиться в мінусових клітинках. Це число додається до клітинок зі знаком + та віднімається від клітинок зі знаком —  . В результаті вільна клітинка стає заповненою, а заповнена з мінімальним значенням та +-ом — вільною. Баланс перевезень не змінюється, оскільки в кожному стовпчику та рядку додається і віднімається одне й те ж значення.

Перехід до кроку 1.

Нижче наведені приклади можливих конфіґурацій циклів в транспортній таблиці.

Приклад.

На трьох пунктах зберігання наявні наступні запаси: a1=100, a2=150, a3=50. Потреби чотирьох пунктів споживання становлять b1=75, b2=80, b3=60, b4=85. Вартості перевезень одиниці продукції задані матрицею С  . Прямою перевіркою впевнюємося, що задача закритого типу, оскільки сумарні потреби рівні сумарним запасам. Застосуємо на першому кроці для знаходження початкового опорного розв’язку метод північно-західного кута.

B1

B2

B3

B4

Зап.

A1

6

      75

7

     25

3

5

  

100

A2

1

2      

     55

5       

       60

6

     35

150

A3

8

       

10

20

1

      50

50

Потр.

75

80

60

85

300

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

6

7

10

11

0

6

      75

7

     25

3

5

  

-5

1

2      

     55

5       

       60

6

     35

-10

8

       

10

20

1

      50

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

6

7

10

11

0

6

7

-

3

+

5

75

25

7

6

-5

1

2

+

5

-

6

0

55

60

35

-10

8

10

20

1

-12

-13

-20

50

Здійснюємо переміщення перевезення 25 в межах циклу та переходимо до нової транспортної таблиці з повторенням розрахунків.

6

0

3

4

0

6

-

7

3

+

5

75

-7

25

-1

2

1

+

2

5

-

6

7

80

35

35

-3

8

10

20

1

-5

-13

-20

50

Процес побудови циклу повторюємо, так як оптимального розв’язку ще не досягнуто.

6

7

3

11

0

6

-

7

3

5

+

40

0

60

6

-5

1

+

2

5

6

-

35

80

-7

35

-10

8

10

20

1

-12

-13

-17

50

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

6

7

3

5

0

6

7

3

5

5

0

60

35

-5

1

2

5

6

70

80

-7

-6

-4

8

10

20

1

-6

-7

-21

50

Оскільки серед потенціалів незаповнених клітинок немає ні одного додатнього, то знайдений план перевезень є оптимальним. Сумарна вартість перевезень для нього становитиме

.

  1.  Розв’язування транспортних задач з ускладненнями в постановці

Метод потенціалів може бути застосований також до розв’язування транспортних задач з додатковими умовами. Цими додатковими умовами, або ускладненнями в постановці, можуть бути наступні:

заборона на перевезення продукту з конкретних пунктів зберігання в конкретні пункти споживання;

перевезення продукту з конкретного пункту зберігання в конкретний пункт споживання лише строго визначеної кількості;

завезення з конкретного пункту зберігання в конкретний пункт споживання не менше визначеної кількості продукту;

завезення з конкретного пункту зберігання в конкретний пункт споживання не більше визначеної кількості продукту;

У тому випадку, коли поставки з Аі в Вj не можуть бути здійснені, відповідний тариф на перевезення сij =M, де Mдуже велике додатнє число.

В тому випадку, коли з Аі в Вj необхідно перевезти строго dij одиниць продукту, це число записують у відповідну клітинку, яку надалі вважаємо вільною з тарифом Mякнайбільшим.

Якщо з пункту Аі до пункту Вj необхідно перевезти не менш, ніж аij продукту, то вважаємо, що запаси Аі  та потреби Вj зменшені на аij одиниць.

Якщо з пункту Аі до пункту Вj необхідно перевезти не більш, ніж аij одиниць, то для кожного обмеження такого типу  вводиться додатковий стовпчик: в стовпчику Вj потреби = аij в додатковому стовпчику потреби

bj аij , а вартість перевезення сij=M.

  1.  Інтерпретація методу потенціалів як симплекс-методу.

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

заповнені клітинки транспортної таблиці (де є перевезення) відповідають базовим змінним, а їх значення — значенням базових змінних, а не заповнені — небазовим змінним;

знаходження клітинки, що буде заповнюватися, відповідає пошуку змінної, що вводитиметься до бази;

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

переміщення перевезення в межах циклу відповідає переходу до нової симплекс-таблиці в симплекс-методі;

для включення в базу в симплекс-методі обирається змінна з найбільшим за абсолютною величиною від’ємним значенням , а в транспортній задачі — незаповнена клітинка з найбільшим додантім значенням  потенціалу  (транспортна задача — це задача на знаходження мінімуму);

значення потенціалів незаповнених клітинок (небазових змінних)  в транспортній задачі відповідають коефіцієнтам  у  Q-рядку симплекс-таблиці (за умови відповідної переіндексації змінних);

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

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

Розглянемо транспортну задачу з двома пунктами зберігання та трьома пунктами споживання в загальному вигляді:

c11x11 + c12x12 + c13x13 + c21x21 + c22x22  + c23x23 Min

    x11                           +     x21                            = b1    

                 x12                           +      x22              = b2    

                              x13                            +     x23 = b3    

    x11 +     x12 +     x13                                          = a1    

                                           x21 +      x22 +     x23  = a2    

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

                          +                                              <= c11

                                           +                            <= c12

                                                            +           <= c13

                          +                                             <= c21

                                           +                           <= c22

                                                            +          <= c23

Таким чином, для закритої транспортної задачі в загальному вигляді

,

двоїста буде наступною:

.

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

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

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

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

  1.  Транспортна модель з проміжними пунктами

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

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

Інший метод визначення мінімальної вартості прямого перевезення пов'язаний із постановкою задачі як задачі з проміжними пунктами. При цьому допускається «перевезення» вантажу (частково або цілком) через інші вихідні пункти або використання пунктів призначення транзитом, перед тим, як вантаж досягне встановленого пункту призначення. У задачі з проміжними пунктами автоматично шукається маршрут мінімальної вартості між пунктом виробництва і пунктом призначення без попереднього визначення найкоротшого маршруту.

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

Для пояснення цього зауваження розглянемо наступну задачу.

Приклад.

Є три заводи і два центри розподілу. У моделі з проміжними пунктами буде п'ять вихідних пунктів і п'ять пунктів призначення.

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

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

Таблиця 2

0

130

90

80

215

3700

4700

135

0

101

100

108

3700

5200

95

105

0

102

68

3500

4900

79

99

110

0

205

3700

3700

200

107

72

205

0

3700

3700

3700

3700

3700

6000

5100

У табл. наведений оптимальний розв’язок розглянутої вище задачі з проміжними пунктами, у якій місткість буфера В дорівнює 3700 автомобілів. Зауважимо, що коефіцієнти вартості перевезень між спочатку заданими вихідними пунктами (Лос-Анжелес, Детройт і Новий Орлеан) і пунктами призначення (Денвер і Майамі) ті ж, що й у прикладі.  Передбачається, що інші коефіцієнти оцінюються в залежності від відстані і режиму перевезень.

Діагональні елементи отримані в результаті використання буфера. Вони не дають ніякої інформації про остаточний розв’язок. Позадіагональні елементи забезпечують одержання розв’язку, поданого на рис нижче. З Детройта до Майамі перевезення відбувається через проміжний пункт у Новому Орлеані, куди надходить 200 автомобілів.  Всі інші перевезення здійснюються безпосередньо з заводів у центри розподілу.

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

яких автомобілі потрапляють у остаточні пункти призначення. Відповідні розміри, що характеризують попит п'ятьох продавців, складають 800, 500, 750, 1000 і 650 автомобілів.  Припустимо, що продавець може одержувати товар із будь-якого центру розподілу.  (З прикладу очевидно, що розміри попиту в центрах розподілу

не використовуються в якості вихідної інформації. )  У даному випадку, як показано на рис., проміжними пунктами можуть бути тільки центри розподілу.

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

Зауважимо, що в центрах розподілу (вершини 4 і 5) ємність буфера В, рівна 3700 автомобілів, додається до відповідних розмірів обсягу виробництва і попиту.  Очевидно, що ніякої буферної ємності не потрібно додавати до розміру об'єму виробництва

4

5

6

7

8

9

10

1

X

X

X

X

X

1000

2

X

X

X

X

X

1500

3

X

X

X

X

X

1200

4

3700

5

3700

3700

3700

800

500

750

1000

650

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

1

2

3

4

5

6

7

8

9

10

1

X

X

X

X

X

1000

2

X

X

X

X

X

1500

3

X

X

X

X

X

1200

4

3700

5

3700

3700

3700

3700

3700

3700

800

500

750

1000

650

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

  1.  Метод диференційних рент.

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

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

початковий розподіл частини продукту між пунктами призначення найкращим чином (побудова умовно оптимального розподілу);

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

Алґоритм методу диференційних рент.

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

Крок 2. Скорочуємо нерозподілені поставки продукту так, щоб при цьому загальна вартість перевезень залишалась мінімальною:

визначаємо надлишкові та недостатні рядки — рядок є недостатнім (від’ємним), якщо запаси відповідного пункту зберігання розподілені повністю, а потреби не задоволені; рядок є надлишковим (додатнім), якщо потреби задоволені, і залишився продукт у відповідному пункті зберігання; Для уникнення неоднозначностей у визначенні знаку рядка, в якого нерозподілений залишок рівний 0, необхідно користатися наступним правилом: рядок вважається додатнім за умови, що друга заповнена клітинка, яка знаходиться в стовпчику, що зв’язаний з таким рядком однією заповненою клітинкою, розташована в додатньому рядку.

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

переходимо до нової таблиці — додаємо до відповідних тарифів, які знаходяться у від’ємних (недостатніх) рядках, проміжну ренту. Інші елементи не змінюємо.

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

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

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

Приклад.

B1

B2

B3

B4

A1

6

7

5

100

60

+40

A2

5

6

150

75

75

-5

A3

8

10

20

50

50

-35

75

80

60

85

5

5

4

4 є проміжною рентою.

6

7

100

60

35

+5

9

6

150

75

75

-5

12

10

24

50

50

+0

75

80

60

85

1

1

100

5

60

35

0

10

11

150

75

75

0

12

14

24

50

50

0

75

80

60

85

6

7

7

6

  1.  Задача про призначення

Задача про призначення змістовно формулюється наступним чином. Необхідно розподілити   робіт серед  виконавців таким чином, щоб сумарні витрати на виконання робіт були мінімальні. Відомі витрати  — на виконання i-ї роботи j-м виконавцем для всіх робіт та виконавців. Окрім того, відомо, що кожен з виконавців може виконувати не більш, ніж одну роботу, і кожна робота може виконуватись не більш, ніж одним виконавцем.

Ця задача є не чим іншим, як специфіцним випадком транспортної — роботи можна розглядати, як пункти зберігання, виконавців — як пункти споживання, запаси в кожному з пунктів зберігання та потреби в пунктах споживання рівні одиниці, тариф на перевезення — .

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

,

, якщо і-та робота не виконується j-м виконавцем, та 1 — якщо виконується. Слід зауважити, що розв’язок задачі про призначення завжди буде виродженим, оскільки для невиродженого розв’язку ранґ матриці коефіцієнтів С повинен становити  , в той час як призначеними можуть бути  робіт. Таким чином, задачу про призначення можна розв’язати за допомогою методів розв’язування транспортних задач, але при цьому необхідно буде заповнення  в транспортній таблиці   пустих клітинок безмежно малими перевезеннями .

В той же час виявилося можливим з врахуванням специфічних особливостей задачі про призначення побудувати ефективні алгоритми її розв’язування, одним з яких є так званий угорський алгоритм. Для обґрунтування редукції в цьому алгоритмі покажемо, що оптимальний розв’язок задачі не зміниться, якщо до будь-якого рядка чи будь-якого стовпчика додати чи відняти постійну величину. Віднімемо від  кожного i-го стовпчика  та кожного j-го рядка  постійні для відповідного рядка чи стовпчика значення  та : ,     =   .

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

Угорський алґоритм для задачі про призначення складається з наступних кроків.

Крок 1. Редукція рядків та стовпчиків матриці С.

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

Крок 2. Реалізація призначень.

a). Послідовно переглядаючи рядки, визначаємо ті з них, в яких знаходиться рівно по одному невикресленому нульовому елементу. В кожному з таких рядків виконуємо призначення, яке відповідає цьому невикресленому нульовому елементу (призначені нулі відзначаємо кружечками). При виконанні призначення в кожному стовпчику, який відповідає призначеному нулеві, викреслюємо всі невикреслені раніше елементи.

b). Послідовно переглядаємо стовпчики, визначаємо ті з них, в яких знаходиться рівно по одному нульовому елементу. В кожному з таких стовпчиків виконуємо призначення, що відповідає невикресленому нульовому елементу. При виконанні призначення в кожному рядкові, який відповідає призначеному нулеві, викреслюємо всі невикреслені раніше елементи.

c). Перевірка: Якщо знайдене таким чином призначення повне (тобто призначено  нульових елементів), то воно й буде оптимальним розв’язком задачі — стоп. Якщо деякі з нулів не викреслені (тобто залишилися рядки та стовпчики з кількістю нулів, більшою ніж 1), то обираємо рядок чи стовпчик з мінімальною кількістю нулів, довільно призначаємо один з них, викреслюємо всі нулі в в цьому рядку (стовпчику) та відповідному стовпчикові (рядку) і далі виконуємо крок 2. Якщо викреслені та призначені всі нулі в матриці, і знайдене призначення неповне, то переходимо до кроку 3.

Крок 3. Модифікація редукованої матриці.

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

a). обчислюємо число нулів в кожному невикресленому рядку та кожному невикресленому стовпчику;

b). викреслюємо рядок чи стовпчик  з максимальною кількістю нулів;

c). виконуємо a та b до того часу, поки всі нулі не будуть викреслені;

d). від всіх невикреслених елементів віднімаємо значення мінімального невикресленого елементу та додаємо його до елементів, що знаходяться на перетині викреслюючих прямих.  Перейти до кроку 2.

Приклад.

Задана матриця С:        Редукована за рядками матриця:

                

За стовпчиками:             Матриця після кроку 2:

               

Оскільки призначення неповне, переходимо до кроку 3.

Після завершення викреслювань визначаємо зміни в елементах матриці та виконуємо крок 2 з модифікованою матрицею:

 

Таким чином отримане повне призначення, яке й є оптимальним розв’язком задачі про призначення. Повертаючись до умови задачі, розраховуємо оптимальне значення функції мети для призначення:

9+4+11+4=28.

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


 

А также другие работы, которые могут Вас заинтересовать

34021. Глобальные проблемы человечества 23.5 KB
  Десять тыяч лет назад было около 5млн человек 2 тысячи лет назад – около 200 млн в 1960 г – 3 млрд в 1975 – 4 млрд в 1987 5 млрд в 2000г более 6 млрд человек.
34024. Возникновение христианства как мировой религии. Средневековая философия. Доказательства бытия Бога. Принцип средневековой философии 25.5 KB
  Доказательства бытия Бога. Существование бога самоочевидно но если мы не знаем что такое бог то эта очевидность сомнительна. Невозможно определить бытие бога. Человек не может познать бога.
34025. Философия эпохи Возрождения 24 KB
  2 Расширение кругозора человека возникновение естествознания. Место человека периферийное т. Книги понижали достоинство человека в мире низводят человека с божественной высоты до земной. Гуманизм человек предстает как высшая ценность способности которой должны быть раскрыты полностью всё для блага человека.
34026. Проблема рационализма и сенсуализма начала 19 в. (сравнить Декарта и Локка) 30 KB
  разуме в центре работы теория познания Всякое познание это сближение с опытом. Он создаёт психологическую теорию познания. Что является самым главным в процессе познания По Декарту: чувства делятся на пришедшие из вне врожденные обнаруживаются нами самими. считает что элементы познания возникают только из чувственного опыта.
34027. Томас Гоббс 26.5 KB
  Власть проистекает из инстинкта самосохранения. Власть становится результатом конвенции разумного решения. Появляется общественная власть. Договор может быть расторгнут если власть не может больше защищать.
34028. Французское Просвещение (Вольтер, Руссо) 31 KB
  Крупнейшими мыслителями и идеологами этой эпохи стали Вольтер Дидро Гольбах Гельвеций Ламетри Руссо и др. Своим метким пером он поражал старое отжившее свой век его сатира и насмешка были убийственны для феодальной камарильи смех Вольтера разрушил больше чем плач Руссо. Мировоззренческая система Жан Жака Руссо завоевала огромную популярность еще при жизни он был признанным властителем дум большинства французов второй половины XVIII века.
34029. Философия Канта 27 KB
  Основные достижения Канта теория познания гносеология и этика. Основные положения идеи теории познания. Кант ставит вопрос о диалектике познания говоря о двух понятиях: субъект и объект познания эти понятия составляют диалектическую противоположность противоречие познания. Суть этой диалектики: ведущим началом источником познания является не объект а субъект познания.