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

Страницы:
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,..., п}. Матрицю

X = (Хіу) іє{1,...,гп} ,

складену з цих змінних, називають планом перевезень.

Транспортну задачу та її розв'язування зручно подавати у вигляді транспортної таблиці (матриці) вигляду

286


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

Споживачі

Запа­си

 

 

 

В3

 

 

 

Аг

сгг

жи

 

 

 

сгп

аг

 

 

 

 

 

 

 

Аг

сц

жц

 

жгу

 

сіп

жіп

аі

 

 

 

 

 

 

 

 

 

 

 

 

стп

жтп

 

Потреби

Ьг

 

Ьі

 

Ьп

 

Якщо вважати, що весь вантаж треба вивезти з пунктів відправлення Аі, і Є {1,... ,т}, і задовольнити потреби всіх пунктів призначення В і , з Є {1,... ,п}, то математична модель транспортної задачі має вигляд

тп

/ = ^ ^ СіуХіу тіп; (1)

і=13=1

при обмеженнях

п

іу = аі,   і Є{1,...,т}; (2)

3 = 1 т

/^2Хіз = Ьз,   і Є{1,...,п}; (3)

і=1

Хіу > 0,   і Є{1,...,т},   і Є{1,...,п}. (4) У розглянутій задачі має виконуватися умова

тп

і=1 у=1

Транспортну задачу називають збалансованою або за­критою, якщо виконується умова (5). Якщо ж ця умова не

287виконується, то транспортну задачу називають незбалансо-ваною або відкритою.

Доведено [14], що збалансованість, тобто умова (5) є необ­хідною і достатньою умовою існування розв'язку транспортної задачі (1) - (4).

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

т п

від співвідношення між сумами      бц і      Ьз.

і=1 3 = 1

тп

У випадку, коли       ец   >        Ьз  вводиться фіктивний

і=1 3=1

(п + 1)-й пункт призначення (споживач) з потребою Ьп =

тп

аі       Ьз, відповідні тарифи якого вважаються нульови-

і=1 3=1

ми, тобто Сіп+1

тп

Якщо ж      аі <^^Ьз, тобто загальні потреби перевищу-

і=1 3=1

ють запаси, то вводиться фіктивний + 1)-й пункт відправ-

пт

лення (постачальник) із запасом вантажу ат =      Ьз аі

3=1 і=1

і тарифами ст+1 3 =0, з Є {1,..., п}.

Очевидно, що транспортна задача (1) - (4) є звичайною за­дачею лінійного програмування і може бути розв'язана сим­плексним методом. Однак особливості будови математичної моделі транспортної задачі дозволяють розв'язати її простіше. Легко помітити, що всі коефіцієнти при змінних у рівняннях (2) і (3) дорівнюють одиниці, а самі системи задані в канонічній формі. Крім того, система обмежень (2), (3) складається з тп невідомих та т + п рівнянь, які зв'язані маж собою співвід­ношенням (5). Якщо додати відповідно праві та ліві частини

288систем рівнянь (2) і (3), то отримаємо два однакових рівняння:

т    п т п

/\2^2Хи = Е" Ь'

і=1]=\ і=1 ]=\

т    п п т

і=1 ;=1 і=\ і=1

Наявність у системі обмежень двох однакових рівнянь свід­чить про її лінійну залежність. Якщо одне з цих рівнянь від­кинути, то в загальному випадку система обмежень містити­ме т + п 1 лінійно незалежних рівнянь, а тому її можна розв'язати відносно т + п 1 базисних змінних. Назвемо опор­ним планом транспортної задачі такий її допустимий план X = (хіу) іе{і,...,т}, який містить не більше ніж т + п 1 до-

ЗЄ{ї,..',п}

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

Опорний план X* = (х*;) іе{і,...,т}, при якому цільова функ-

і {1,...,п}

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

Якщо умови транспортної задачі і її опорний план записані у вигляді таблиці, то клітинки, в яких Хі; > 0, називаються заповненими, всі інше - порожніми.

Заповнені клітинки відповідають базисним змінним і для невиродженого плану їхня кількість дорівнює т + п 1.

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

Відносно розташування вершин циклу повинні виконувати­ся такі умови:

289

1) в одному рядку (або стовпчику) містяться тільки дві вер-

2) остання (завершальна) вершина циклу знаходиться в то­му самому рядку, що й перша (вихідна);

3) якщо умовно з'єднати вершини циклу відрізками, то в кожній наступній вершині здійснюється поворот на 900.

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

Доведено [14], що кількість вершин (клітинок), які утворю­ють будь-який цикл транспортної задачі, завжди парна.

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

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

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

шини циклу;

290дачі - неможливості побудови циклу для заповнених клітинок.

Для побудови початкового опорного плану транспортної за­дачі існує декілька методів, які опишемо в наступному пункті.

6.2. Побудова опорних планів транспортної за­дачі. Розглянемо три методи побудови початкового опорного плану: північно-західного кута; мінімальної вартості та подвій­ної переваги. Суть цих методів полягає в тому, що опорний план знаходять послідовно за п + т 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лінійна алгебра й аналітична геометрія