Warning: session_start() [function.session-start]: Cannot send session cookie - headers already sent by (output started at /var/www/nelvin/data/www/ebooktime.net/index.php:6) in /var/www/nelvin/data/www/ebooktime.net/index.php on line 7

Warning: session_start() [function.session-start]: Cannot send session cache limiter - headers already sent (output started at /var/www/nelvin/data/www/ebooktime.net/index.php:6) in /var/www/nelvin/data/www/ebooktime.net/index.php on line 7

Warning: file_get_contents(files/survey) [function.file-get-contents]: failed to open stream: No such file or directory in /var/www/nelvin/data/www/ebooktime.net/index.php on line 82
3.7.2. Розв’язування двохетапної транспортної задачі : Дослідження операцій : Бібліотека для студентів

3.7.2. Розв’язування двохетапної транспортної задачі


Повернутися на початок книги
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 

Загрузка...

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

Позначимо через х( 1) (і = 1,т,к = 1,р) обсяг перевезень продук-ції від /-го підприємства постачальника до к-vo проміжного пунк-ту; х^2) (j = 1,п , к = 1,р)  обсяг перевезень продукції від к-то про-

міжного   пункту   до у'-го   споживача   й   запишемо   економіко-математичну модель задачі. Знайти

х;(1)>0,   xf2)>0   і = 1,т,    j = 1,n,   к = 1,р, (3.44)

Кігель В. Р. Елементи лінійного цілочислового лінійного, нелінійного програму-вання: Навч. посібник. — К.: ІСДО, 1995. — 400 с.

що належать області G, визначеної умовами:

к=\ Р

Хх«') =b,    j = \,п ,

к=\

YJXT = Ххи■* і    к = 1,р, і мінімізують сумарні витрати на перевезення продукції

™р   (1) (1)    Р"   (2) (2) z = 2^ л Чк хік + 2^^ ckj xkj ~~^ mm ■

i=lk=l   k=lj=l

 

(3.45) (3.46) (3.47)

(3.48)

 

 

 

 

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

Г\ Споживачі

 

а) Система «постачальники — споживачі» Проміжні пункти

 

б) Система «постачальники — проміжні пункти — споживачі»

Рис. 3.3.

У моделі (3.44) — (3.48) c£ — транспортні витрати на пере-везення одиниці продукції від /-го постачальника до к -го промі-жного пункту; с^2) — транспортні витрати на перевезення одини-ці продукції з к-то проміжного пункту до у'-го споживача {і = \,т, j = \,п ,к = \, р)

Побудована модель (3.44)—(3.48) є модель лінійної оптиміза-ції, тому для пошуку оптимального розв'язку можна застосувати симплекс-метод, але розмірність відповідної задачі у канонічній формі є дуже велика і дорівнює (т + р + п)-(т + п)-р. Тому для розв'язування двохетапної транспортної задачі можна застосува-ти перехід до одноетапної транспортної задачі розмірності {т + р)-(п + р) за наступним алгоритмом.

Алгоритм переходу від задачі з проміжними пунктами доодноетапноїтранспортноїзадачі

1.         Замість т вихідних постачальників розглянемо (т + р) по-

стачальників, вважаючи обсяг наявної продукції в кожного з

останніх р постачальників (це нові постачальники) таким, що до-

рівнює загальному потоку продукції:

п                    

am+k = Tbj,   k = \,p.

j=\

2.         Замість п кінцевих споживачів розглянемо (п + р) спожива-

чів за умови, що потреби в продукції кожного з р останніх спо-

живачів (це нові споживачі) також дорівнюють загальному пото-

ку продукції:

т                     

bn+k=Ta,,   k = \,p.

3.         Заборонимо перевезення продукції від кожного з т перших

постачальників до кожного з п перших споживачів, а також від

кожного з р останніх постачальників до кожного з р останніх

споживачів, крім «діагональних перевезень» від (т + к) -го поста-

чальника до (п + к)-то споживача (к = \,р). Питомі транспортні витрати за згаданими «діагональними» маршрутами вважатиме-мо такими, що дорівнюють нулю.

Надамо економічне тлумачення пошукових змінних:

Ху (і = \,т, j = п + \,п + р) є обсяги перевезень від кожного реального постачальника до кожного проміжного пункту;

Ху (і = т + \,т + р; j = \,гі) є обсяги перевезень з кожного проміжного пункту до кожного кінцевого споживача;

Ху    (i = m + k,j = n + k,   к = \,р) є обсяги перевезень для кож-

ного к -го проміжного пункту через решту проміжних пунктів.

Матрицю питомих транспортних витрат для побудованої од-ноетапної транспортної задачі (показано витрати лише за незабо-роненими маршрутами руху перевезень в одноетапній задачі, здобутій перетворенням вихідної двохетапної задачі) подано в табл. 3.9.

Таблиця 3.9

 

 j          1          2          ...         n          И+ 1    n + 2    ...         n + p

1                                 ...                     1          l

C12     ...         clj

2                                 ...                     1

c 21     1

c22      ...         l

2p

                                   ■-.                                          '■.       

m                                 ...                     1

Cm\     1 Cm2 ...         1 r

mp

m+ \     cu        c 12     ...         C\n      0                      ...        

m + 2   2 C21  4          ...         2 C2n              0          ...        

                                   ■-.                                          '■.       

m +p    C?l       u          ...         c1                                ...         0

Приклад 3.7. Три постачальники, що мають відповідно 50, 70, 100 одиниць вантажу, транспортують його двом споживачам в обсязі відповідно 140 і 80 одиниць. Транспортування продукції здійснюється через два проміжні пункти, проте перший постача-

льник має змогу надсилати продукцію й безпосередньо першому споживачеві, не вдаючись до поставок через проміжні пункти. Водночас перший постачальник не може надсилати свою проду-кцію через другий проміжний пункт — цей маршрут для нього заборонений. Уся продукція від другого й третього постачальни-ків може надсилатись споживачам лише через проміжні пункти (транспортна система зображена на рис. 3.4). Відомі питомі вар-тості перевезень за кожним з можливих маршрутів (табл. 3.10). Необхідно знайти оптимальний план перевезень.

 

Рис. 3.4.

Таблщя 3.10

 

а'         140      80        220      220

50        15                    10       

70                               8          7

100                             12        6

220      6          4          0         

220      8          6                      0

Питомі транспортні витрати для незаборонених маршрутів

В табл. 3.10 наведені вихідні дані для одноетапної транспортної задачі, утвореної з початкової задачі з урахуванням заборонених ма-ршрутів транспортування вантажу (відповідні клітинки зафарбовані).

Щоб перейти від даної транспортної задачі до одноетапної, розглянемо її як задачу про п'ятьох постачальників (трьох вихід-них і двох додаткових) і чотирьох споживачів (двох вихідних і двох додаткових). Обсяг продукції в кожного з додаткових по-стачальників і попиту на продукцію з боку кожного додаткового споживача вважатимемо такими, що дорівнюють потоку продук-ції у вихідній транспортній системі, а саме:

50 + 70 + 100 = 140 + 80 = 220 (одиниць продукції).

Заборонимо перевезення за окремими маршрутами. Це такі маршрути:

(1, 2) — перший постачальник не повинен надсилати свою продукцію безпосередньо другому споживачеві;

(1, 4) — цей самий постачальник не повинен надсилати свою продукцію безпосередньо на другий проміжний пункт;

(2, 1), (2, 2), (3, 1), (3, 2) — другий і третій постачальники не повинні надсилати свою продукцію безпосередньо споживачам:

(4, 4), (5, 3) — перевезення продукції з одного проміжного пункту на інший заборонено.

Усі вихідні дані для одноетапної транспортної задачі, побудова-ної в результаті перетворення вихідної задачі, наведено на табл. 3.10.

Для визначення опорного розв'язку застосуємо метод північ-но-західного кута, отримуємо табл. 3.11.

Таблиця 3.11

 

            V\        V2       V3       F4

U\        15       /

*^              50             10       

и2                               8          /

-^              70  7         1

ІІз                               12        /

~^            100 6         /

Un       6     / ^              90      4          /

—                  80         о      / *^              50  

Us        У         6     j                0        J

^^            220

Побудуємо систему рівнянь для визначення потенціалів и. (і = 1,5), v. (/ = 1,4) за схемою

И. + V ■ = С;у  ДЛЯ Ху Ф 0 ,

маємо

Mj + Vj = 15; и2 + v3 = 8; и3 + v3 = 12; и4 + Vj = 6; и4 + v2 = 4;       (3.49)

и4 + v3 = 0; us + v4 = 0 .

Кількість невідомих дорівнює 9, проте система складається з 7 рівнянь. Отже, х" розв'язок є виродженим.

За схемою методу потенціалів для уникнення виродженості припустимо, що в клітці (5,1) є деяке число. Отже отримуємо ще одне рівняння для визначення потенціалів:

+ v =8

Щ + Vj

(3.50) 3 системи (2.45), (2.46) знайдемо: v1 = 0; v2 = -2; v3 = -6; v4 = -8,

иг = 15; u2 = 14; и3 = 18 ; и4 = 6; м5 = 8 . Для оцінки х" на оптимальність визначимо

 

Л

 

+ v -С   для х" = 0 ,

 

А13 = 15 - 6 -10 = -1; Л24 = 14 - 8 - 7 = -1; Л34 = = 18-8-6 = 4; Л52 =8-2-6 = 0

Отже, Л34 додатне, тому х° не є оптимапьним розв'язком. Для

покращання розв'язку побудуємо компенсуючий ланцюжок (див. табл. 3.12)

Таблщя 3.12

 

15

50                    10       

                        8

70        7         J

                        12        /

^S            100 -0         6        j

^*S                       0*

6     / ^S              90 - 0^        4      /

S                      80       0         j

^^               50 + 0     

8          /

^/                 ^ + 0                               o      / ^*S            220 - 0

9*=min{90;100;220} = 90.

Відкоригуємо табл. 3.12 з урахуванням визначеного значення 9* =90 (табл. 3.13) і побудуємо систему для визначення потен-ціалів.

Таблщя 3.13

 

            V\        Vi        V3       V4

            15       /                       10        I                                             

U\        50                    У                                                       

                                   8          )                      7          /          

Uj                                У                     70        У                    

                                   12        )                      6          У        

и3                               У                     10        У                     90

            6     /    4         /            0          )                                             

ІІц       У         80        У                     140                            

            8        J            6     /                                       0          /          

Us        90        У                                            У                     130

щ + vi = 15, «2 + V3 = 8, M3 + V3 = 12, щ + V4 = 6, M4 + V2 = 4,

M4 + V3 = 0, M5 + Vl = 8, щ + V4 = 0.

Звідси, щ = 13; щ = 8; щ = 12; «4 = 0; «5 = 6; vi = 2; V2 = 4; V3 = 0; V4 = -6.

А13=13 + 0-10;Л24=8-6-7 = -5;

A

 

 0 + 2 - 6 = -4 ; Л52 =6 + 4-6 = 4.

 

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

xj'j = 50 (цей вантаж безпосередньо транспортується від пер-шого постачальника першому споживачеві);

х24 = 70 (цей вантаж спочатку транспортується від другого по-стачальника на перший проміжний пункт, а потім першому спо-живачеві (х*41 =70);

х3*5=100 (100 одиниць вантажу від третього постачальника спочатку транспортуються до другого проміжного пункту, а по-тім в кількості 20 одиниць до першого споживача і в кількості 80 одиниць до другого споживача). При цьому сумарні транспор-тні витрати z* дорівнюють 2970 одиницям.

Ha рис. 3.5 наведено схему оптимального перевезення ванта-жу від постачальників до споживачів з урахуванням проміжних пунктів зберігання вантажу.

хп = 50

 

Рис. 3.5.