В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія - страница 101

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 

Числа аі та називаються потенщалами відповідно пунктів відправлення Аі  і пунктів призначення Ву,  і Є

{1, . . . , т}, . Є {1, . . . , п}.

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

Якщо є деякий опорний план, то спочатку знаходимо потен­ціали аі, і Є {1,..., т}, і    , і Є {1,..., п}, з системи рівнянь

в) — аі = Су, (6)

де Сіу - тарифи перевезень, які стоять у заповнених клітинках таблиці умов транспортної задачі. Оскільки число заповнених клітинок дорівнює п + т — 1, то система (6) з т + п невідомими містить т + п — 1 рівнянь. Це означає, що число невідомих на одиницю більше, ніж число рівнянь. Тому одне з невідомих

296можна взяти нульовим, наприклад, аі = 0. Решту аі та знаходимо з системи (6).

Після того, як усі потенціали знайдено, для кожної з віль­них клітинок знаходимо числа

=    аі Су. (7)

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

Переміщення вантажу в межах клітинок, які зв'язані з цією вільною клітинкою циклом здійснюємо за таким правилом: 1) кожній з клітинок, які зв'язані циклом із зазначеною віль­ною клітинкою присвоюємо певний знак, вільній клітинці знак плюс, а всім іншим - почергово знаки мінус і плюс; 2) у цю вільну клітинку переносимо менше з чисел хіу, які знаходять­ся в мінусових клітинках. Одночасно це число додаємо до від­повідних чисел, які стоять у плюсових клітинках і віднімаємо від чисел, які стоять у мінусових клітинках. Вільна клітинка стає заповненою, а мінусова клітинка, в якій стояло мінімальне число хіу, - вільною.

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

З описаного вище випливає, що алгоритм методу потен­ціалів такий:

297

1) знаходять за допомогою одного із описаних вище ме­тодів початковий опорний план. При цьому число заповнених клітинок повинно дорівнювати п + т — 1, тобто план повинен бути невиродженим;

2) для заповнених клітинок таблиці транспортної задачі записують систему рівнянь (6) і знаходять потенціали щ і

вз;

3) для кожної вільної клітинки визначають числа йу (7). Якщо серед чисел йу немає додатних, то одержано оптималь­ний план транспортної задачі; якщо ж вони є, то переходять до нового опорного плану;

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

5) одержаний опорний план перевіряють на оптималь-ність, тобто знову повторюють всі дії, починаючи з кроку 2).

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

Приклад 4. За допомогою методу потенціалів розв'язати за­дачу, яка задана таблицею

Постачаль-

Споживачі

Запа-

ники

Ві

в2

вз

си

Аі

5

2

3

 

 

 

 

 

15

А2

2

4

6

 

 

 

 

 

25

Аз

5

3

3

 

 

 

 

 

35

Потреби

20

20

45

75

85

Оскільки потреби більші за запаси, то введемо фіктивний пункт постачання а4 із запасами 04 = 85 — 75 і нульовими тарифа­ми перевезень. Тоді одержимо збалансовану (закриту) транспортну задачу

298


Постачаль­ники

Споживачі

Запа­си

 

 

В2

Вз

 

Аг

5

 

3

15

А2

2|

—20—

6

25

Аз

5

3

0

3

35

35

А4

0

0

0

10

10

Потреби

20

20

45

85

Побудуємо початковий опорний план методом північно-західного кута. Число заповнених клітинок повинно дорівнювати п + т 1 = 3 + 4 1 = 6, а є 5. Це означає, що опорний план є виродженим, а тому треба вважати одну із порожніх клітинок заповненою. За цю клітинку можна взяти (2, 3) або (3, 2), бо при заповнені клітинки (2, 2) ми одночасно вичерпали запаси постачальника А2 і задоволь­нили потреби споживача В2 і виключили з розгляду одночасно ря­док і стовпчик, а треба було щось одне. Вважатимемо заповненою клітинку (3, 2). Одержаний невироджений опорний план дослідимо на оптимальність. Розглянемо заповнені клітинки і складемо для них систему рівнянь (6):

вг аг = 5,   вг «2 = 2,   /?2 «2 = 4,

в2 «з = 3,    вз «з = 3,    вз «4 = 0.

Взявши «г = 0, знаходимо вг = 5, «2 = 3, в2 = 7, «з = 4, вз = 7, «4 = 7.

Для кожної вільної клітинки знаходимо числа сі^ (7): (г2 = 7 0 2 = 5,    Сгз = 7 0 3 = 4,    ( = 7 3 6 = 2,

Сзг = 5 4 5 = —4,    С4г =5 7 0 = 2,    (42 = 7 7 0 = 0.

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

299


5

2

15

3

2

20

4

5

6

5

3

0

3

35

0

0

0

10

Перевіряємо цей опорний план на оптимальність. Для заповне­них клітинок складемо систему рівнянь (6):

/?2 - «1 = 2,    ві - «2 = 2,    /?2 - «2 = 4,

в2 - «3 = 3,    вз - «3 = 3,    вз - «4 = 0,

звідки одержуємо, що «і =0, /?2 = 2, «2 = -2, ві =0, «з = -1,

вз = 2, «4 = 2.

Для кожної з порожніх клітинок маємо відповідно: «ц =0 - 0 -5 = -5, <<13 = 2 -0 - 3 = -1, <<23 = 2 + 2 - 6 = -2, <<31 =0+1 - 5 = -4, <<4і =0 - 2 - 0 = -2, <<42 = 2 - 2 - 0 = 0. Оскільки всі < 0, то план оптимальний:

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 


Похожие статьи

В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія