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

Страницы:
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 

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

291рядок (щось одне). Цим самим або запаси відповідного пункту відправлення, або потреби вказаного пункту призначення вва­жаємо нульовими, що гарантує одержання п + т 1 зайнятих клітинок, у яких стоять компоненти опорного плану. Відмін­ність від нуля п + т 1 компонент опорного плану, тобто запов-неність п+т 1 клітинок транспортної таблиці, є обов'язковою умовою для дослідження цього плану на оптимальність.

6.2.1. Метод пiвнiчно-захiдного кута. Будуватимемо допустимий план в таблиці умов транспортної задачі, де кож­ній змінній      відповідає клітинка (і, і).

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

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

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

Споживачi

Запа­си

 

Вг

В2

Вз

В4

 

Аг

7

120

8

40

1

2

160

А2

4

5

10

9

130

8

140

Аз

9

2

3

60

6

110

170

Потреби

120

50

190

110

470

Оскільки задача закрита, то можна будувати опорний план. У клітинку (1, 1) помістимо 120 од., бо споживачеві В\ більше не треба. При цьому перший стовпчик виключаємо з розгляду. Далі у клітинку (1, 2) поміщаємо 40 од. і оскільки запаси в пункті А\ ви­черпано, то перший рядок виключаємо з розгляду. Споживачеві В2 додаємо 10 од. з пункту А2 і другий стовпчик більше не розглядає­мо. Продовжуючи аналогічно далі, у клітинку (3, 3) помістимо 60 од. вантажу. Залишилася клітинка (3, 4), а запаси постачальника і

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

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

Очевидно, що вартість перевезень при одержаному опорному плані

/ 120   40    0      0 \ х0 = І    0     10   130    0 І \   0     0    60    110 )

дорівнює

] = 7 120 + 8 40 + 5 10 + 9 130 + 3 60+ +6 110 = 3520 гр. од. ►

6.2.2. Метод мінімальної вартості (метод міні­мального елемента). Суть методу полягає в тому, що з усієї таблиці умов транспортної задачі вибирають клітинку, в якій стоїть найменша вартість і туди записують найменше з чисел а% або Ь]. Потім з розгляду виключають або рядок, що від­повідає постачальнику, запаси якого повністю вичерпані, або стовпчик, який відповідає споживачу, потреби якого повністю задоволені, або і рядок і стовпчик, якщо вичерпані запаси по­стачальника і задоволені потреби споживача. Далі з клітинок, які залишилися, знову вибираємо ту, де знаходиться найменша вартість перевезення і процес розподілу запасів продовжуємо до тих пір, поки всі запаси не будуть розподілені, а потреби задоволені.

Приклад 2. Методом мінімальної вартості знайти опорний план транспортної задачі з прикладу 1

293


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

Споживачі

Запа­си

 

 

В2

Вз

В4

 

Аг

7

8

1

160

2

160

А2

4

120

5

9

8

20

140

Аз

9

2

50

3

30

6

90

170

Потреби

120

50

190

110

470

Мінімальний тариф, що дорівнює 1, знаходиться в клітинці (1, 3). Помістимо у цю клітинку 160 од. і виключимо з розгляду перший рядок, бо запаси постачальника А\ вичерпані. Вважаємо, що потреби пункту призначення Бз вже дорівнюють 30 од.

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

/   0     0    160    0 \ Х0 = І   120    0     0    20   І . \   0    50    30    90 )

При цьому плані перевезень загальна вартість перевезень стано­вить

/ =1 • 160 + 4 • 120 + 8 • 20 + 2 • 50 + 3 • 30 + 6 • 90 = 1530 гр. од.

Одержали, що вартість перевезень нижча, ніж у випадку опорно­го плану, який побудовано в прикладі 1 методом північно-західного кута. ►

6.2.3. Метод подвійної переваги. Якщо транспортна таблиця велика, то перебрати всі клітинки важко. У цьому ви­падку використовують метод подвійної переваги, зміст якого полягає в такому.

У кожному стовпчику помічаємо значком V клітинку з най­меншою вартістю. Потім це саме зробимо в кожному рядку. Як результат матимемо у деяких клітинках помітки VV. Цим

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

Приклад 3. Знайти опорний план транспортної задачi з при­кладу 1, використовуючи метод подвійної переваги.

Заповнюємо спочатку клітинки (1, 3), (2, 1) і (3, 2), які мають дві помітки VV. Далі заповнюємо клітинки (3, 3), (3, 4) і (2, 4) у порядку зростання вартостей

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

Споживачi

Запа­си

 

 

В2

Вз

В4

 

Аг

7

8

1 УУ 160

2 У

160

А2

4 УУ 120

5

9

8

20

140

Аз

9

2 УУ 50

3

30

6

90

170

Потреби

120

50

190

110

470

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

/   0     0    160    0 \ Х0 = (   120    0     0    20  ) ,

0   50  30 90

/ =1 • 160 + 4 • 120 + 8 • 20 + 2 • 50 + 3 • 30 + 6 • 90 = 1530 гр. од. ►

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

6.3. Знаходження оптимального плану транспорт­ної задачі методом потенціалів. Для визначення оптималь­ного плану транспортної задачі розроблено декілька методів.

295

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

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

Теорема. Якщо для деякого невиродженого опорного плану X = (ху) іє{і,...,т} транспортної задачі Існують такі числа щ,

ІЄ{1,...,п}

і Є {1,..., т} та    , і Є {1,..., п}, що

в і — аі = Су   при   ху > 0,

в і — аі < Су   при       = 0,

для вЫх і Є {1,..., т}, і Є {1,..., п}, то цей план є опти­мальним.

Страницы:
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лінійна алгебра й аналітична геометрія