11767

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

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

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

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

Украинкский

2013-04-11

656.5 KB

80 чел.

  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 та додаванням значення максимального елемента матриці умови задачі.


 

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

46122. Методика логопедического обследования заикающегося ребёнка 17 KB
  Из беседы с родителями логопед выясняет наиболее значимые события происшедшие в семье ОБО ВСЕМВСПОМИНАЙ После уточнения сведений о ребенке проводится обследование речи заикающегося и внеречевых процессов оказывающих непосредственное влияние на его речевую деятельность. Проводится исследование его общительности моторики подражательности импрессивной и экспрессивной речи игровой учебной производственной деятельности особенности личности заикающегося.Для исследования речи детей используются картинки книжки со стихами...
46123. Методика логопедического обследования при нарушениях письменной речи 25.5 KB
  Цель обследования: выявление этиологии симптоматики нарушений чтения и письма. Обследование письма. Нарушение письма у детей это особые специфические затруднения которые обусловлены системным недоразвитием определенных сторон речевой деятельности ребенка которое у детей достигших школьного возраста при нормальных умственных способностях и слухе проявляется прежде всего в недостаточной сформированности представлений о звуковом и морфологическом составе слова. Общие методические рекомендации обследованию письма у детей...
46124. Технология развития общей, мелкой моторики рук у детей с нарушениями речи 16 KB
  Коррекция особенностей моторного развития детей направлена на нормализацию мышечного тонуса исправление неправильных поз развитие статической выносливости равновесия упорядоченного темпа движений синхронного взаимодействия между движениями и речью запоминание серии двигательных актов воспитание быстроты реакции на словесные инструкции развитие тонких двигательных координаций необходимых для полноценного становления навыков письма. Этому служат следующие упражнения: сжимать резиновую грушу или теннисный мячик; разгибать и...
46125. Методика развития артикуляционной моторики у детей с речевыми нарушениями 16.5 KB
  Особо можно выделить кончик языка ибоковые края передней и средней частей языка так как от их работы зависит качество звуков. В артикуляционную гимнастику входят упражнения в ходе которых вырабатываются следующие положения кончика языка: опущен за нижние зубы Почистим зубы поднят вверх к альвеолам Маляр Грибок Гармошка. После того как каждое положение будет отработано дается упражнение на переключение с одного положения языка на другое Качели. Средняя часть спинки языка наиболее ограничена в...
46126. Технология формирования интонационной стороны речи у детей. Развитие дыхательной и голосовой функций 19.5 KB
  ВОССТАНОВЛЕНИЕ ГОЛОСА У ДЕТЕЙ Восстановление голосовой функции у детей осуществляется комплексно совместными усилиями медицины и специализированной области логопедии фонопедии. Однако начальным звеном всегда является психотерапевтическая беседа основная цель которой убедить ребенка в возможности восстановления голоса установить с ним контакт включить его в активную работу разъяснив цели и задачи коррекции. Собственно голосовые упражнения состоят из вызывания голоса закрепления голоса и автоматизации процесса голосоведения....
46127. Характеристика этапов и содержания работы по формированию правильного произношения у детей(не выделяют точное колличество этапов,поэтому это не носит принципиального характера. 23.5 KB
  Логопед в ходе выполнения ребенком задания проверяет правильно ли он выбрал позу для произношения нужного звука. Поскольку это не всегда приводит к положительным результатам логопеду следует в таких случаях отвлечь внимание от звука переключив на другой объект. По мере овладения движением необходимым для реализации звука логопед переходит к отработке движений обязательных для других звуков. Этап формирования первичных произносительных умений и навыков Цель данного этапа заключается в том чтобы сформировать у ребенка первоначальные...
46128. Организация и содержание совместной работы логопеда и воспитателя (учителя) детского сада (школы) для детей с нарушениями речи 21 KB
  Организация и содержание совместной работы логопеда и воспитателя учителя детского сада школы для детей с нарушениями речи. Взаимодействие логопеда и воспитателя В задачу воспитателя входит выявление степени отставания детей в усвоении программного материала по всем видам учебной и игровой деятельности. Это необходимо для устранения пробелов в развитии детей и создания условий для успешного обучения в среде нормально развивающихся сверстников. С этой целью в первые две недели воспитатели определяют возможности детей в изобразительной...
46129. Индивидуальные логопедические занятия с детьми дошкольного возраста как эффективная форма коррекционной работы 22.5 KB
  Не менее важным является развитие фонематического слуха и фонематического восприятия. Активизация мыслительной деятельности детей развитие внимания и памяти необходимые условия для успешного и разностороннего обучения дошкольников. развитие памяти внимания мышления воображения обязательная составляющая индивидуального логопедического занятия. Целенаправленная работа по развитию мелкой моторики пальцев рук ускоряет созревание речевых областей истимулирует развитие речи ребенка позволяет быстрее исправить дефектное звукопроизношение.
46130. Фронтальные логопедические занятия в условиях дошкольного образовательного учреждения компенсирующего вида (с логопедическими группами) 21 KB
  Обучение на занятиях основная форма коррекционновоспитательной работы с детьми имеющая важное значение для формирования коммуникативной функции речи и общей готовности к школе. Дети с нарушениями речи нередко характеризуются нарушением внимания пониженной познавательной активностью замкнутостью недостаточно сформированной игровой деятельностью и другими особенностями психического развития. На групповых занятиях логопед формирует умение войти в общий темп работы следовать общим инструкциям оценивать достижения партнера...