Визначення початкового опорного плану

Метод потенціалів

При застосуванні методу потенціалів використовується спеціальна форма запису умови задачі і кожного поточного плану. Ця форма називається транспортною матрицею, і будується вона таким чином. Рядки матриці взаємно однозначно відповідають постачальникам, стовпчики взаємно однозначно відповідають споживачам. На перетинанні i-го рядка і j-го стовпчика записують дві величини: ціну і об’єм перевезення.

Розв’язування транспортної задачі методом потенціалів складається з 2-х етапів. На першому етапі визначають початковий опорний план. На другому за допомогою ітераційної процедури переходять від поточного опорного плану до наступного, доки можливе зменшення цільової функції.

Розглянемо побудову початкового опорного плану на прикладі. Нехай початкова транспортна матриця має вигляд як у табл.11.1, де у верхніх частинах клітинок вказані ціни перевезень.

Таблиця 11.1

10				потреби запаси
5
x11			x12		x13		x14
4
x21			x22		x23		x24
3
x31			x32		x33		x34

Для визначення початкового опорного плану скористаємося так званим методом найкращого перевезення. Цей метод складається з m + n – 1 кроку, на кожному з яких вибирається перевезення з найменшею ціною і для нього береться найбільший можливий об’єм.

На першому кроці вибираємо клітинку (1, 2) і визначаємо максимальний можливий об’м перевезення від першого постачальника до другого споживача. Запас першого постачальника складає 20 одиниць продукції, а потреби другого споживача – 15. Об’єм перевезення від першого постачальника до другого споживача, очевидно, не перевищує мінімальної з цих двох величин. Тому визначаємо x₁₂ = 15. Оскільки при цьому потреби другого споживача задовольняються повністю, другий стовпець у транспортній матриці при подальшому визначенні початкового опорного плану можна не розглядати. Викреслемо цей стовпець. Невикористаний запас продукції у першого

Таблиця 11.2

10				Потреби   Запаси
5								20, 5
x11					x13		x14
4
x21			x22		x23		x24
3
x31			x32		x33		x34

постачальника тепер складає 20 – 15 = 5 одиниць, і транспортна матриця приймає вигляд табл.11.2.

Таблиця 11.3

10		35, 30, 10		потреби запаси
5								20, 5
x11							x14
4								40, 10
x21			x22
3								30, 20
			x32				x34

На наступному кроці вибираємо перевезення (1, 3). Тепер максимальний об’єм перевезення складає 5 одиниць, бо у першого постачальника поточний запас дорівнює 5. Продовжуючи аналогічно, отримуємо транспортну матрицю з усіма викресленими елементами (табл.11.3).

Остання таблиця визначає початковий опорний план x^’, у якому x^’₁₂ = 15, x^’₁₃ = 5, x^’₂₃ = 10, x^’₂₄ = 30, x^’₃₁ = 10, x^’₃₃ = 0, а усі інші об’єми перевезення нульові. Сумарна вартість усіх перевезень дорівнює F(x^’) = 1*15 + 2*5 + 6*10 + 2*30 + 3*10 + 4* 20 = 255.

Оскільки при визначенні початкового опорного плану на кожному кроці, крім останнього, викреслюється тільки один стовпчик або тільки один рядок, а на останньому, коли залишається невикресленою лише одна клітинка, - і стовпчик, і стовпець, кількість змінних, що можуть прийняти ненульове значення, дорівнює m + n – 1. Ці змінні утворюють множину базисних змінних.

Необов’язково у опорному плані транспортної задачі усі базисні змінні мають ненульові значення. Якщо на деякому кроці для поточних значень запасів і потреб має місце рівняння b^’_i = p^’_j, і змінній x_ij присвоюється значення b^’_i, то викреслюється тільки один рядок, а стовпчик j залишається з нульовою потребою. Тому на наступному кроці базисна змінна у j-му стовпчику отримає нульове значення. Тобто у цьому разі виникає вироджений опорний план.

Вибір клітинки з найменшою ціною на кожному кроці є евристичним принципом і тільки дає підстави для сподівання на швидше отримання розв’язку задачі. Можна вибирати клітинку довільним чином у невикресленому рядку і невикресленому стовпчику, і це не впливає на можливість отримання розв’язку задачі.

Ітераційна процедура поліпшення опорного плану

Для того, щоб визначити, чи є оптимальним поточний опорний план, скористаємося ознакою оптимальності симплекс-таблиці – невід’ємність коефіцієнтів індексного рядку. Визначити знак цих коефіцієнтів можна за допомогою матриці A коефіцієнтів системи рівнянь (11.6). Індексний рядок поточної симплекс-таблиці дорівнює сумі індексного рядка і лінійної комбініції рядків-обмежень початкової симплекс-таблиці. Оскільки початкова симплекс-таблиця може бути утворена вилученням довільного рівняння системи (11.6), коефіцієнти індексного рядку поточної симплекс-таблиці можна отримати як суму рядка коефіцієнтів цільової функції і лінійної комбінації рядків матриці A. При цьому довільному коефіцієнту лінійної комбінації можна присвоїти нульове значення, що відповідає вилученню відповідного рівняння з системи (11.6).

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

Будемо позначати потенціали, що відповідають першим m рядкам матриці A, як u_i, i = 1, m, а останнім n рядкам - як v_j, j = 1, n. Тоді для коефіцієнтів c^’_ij індексного рядку поточної симплекс-таблиці мають місце рівняння

c^’_ij = c_ij + u_i + v_j, i = 1, m, j = 1, n, (11.8)

де c_ij - коефіцієнти індексного рядка початкової симплекс-таблиці, або коефіцієнти цільової функції.

Для базисних змінних c^’_ij = 0, і це означає, що потенціали задовольняють однорідній системі рівнянь

c_ij + u_i + v_j = 0, (i, j) N_B, (11.9)

Таблиця 11.4

5
4
3

де N_B - множина пар індексів (i, j), відповідаючих базисним змінним. Визначивши з цієї системи потенціали, можна підрахувати коефіцієнти індексного рядка для небазисних змінних, і таким чином дізнатися, чи оптимальний поточний план.

Тепер повернемося до прикладу. Отриманий початковий опорний план можна уявити у скороченій (без вказаних запасів і потреб) транспортній матриці (табл.11.4). Для того, щоб відрізняти базисні клітинки від небазисних, у останніх не будемо вказувати об’єм перевезення.

Для табл.11.4 система (11.9) приймає вигляд

c₁₂ + u₁ + v₂ = 1 + u₁ + v₂ = 0,

c₁₃ + u₁ + v₃ = 2 + u₁ + v₃ = 0,

c₂₃ + u₂ + v₃ = 6 + u₂ + v₃ = 0,

c₂₄ + u₂ + v₄ = 2 + u₂ + v₄ = 0,

c₃₁ + u₃ + v₁ = 3 + u₃ + v₁ = 0,

c₃₃ + u₃ + v₃ = 4 + u₃ + v₃ = 0.

Оскільки потенціал v₃ входить у найбільшу кількість рівнянь, для спрощення обчислень доцільно йому присвоїти нульове значення. Тоді отримуємо

v₃ = 0, u₁ = -2, u₂ = -6, u₃ = -4, v₁ = 1, v₂ = 1, v₄ = 4.

Визначимо коефіцієнти для небазисних змінних, використовуючи рівняння (11.8).

c^’₁₁ = c₁₁ + u₁ + v₁ = 5 – 2 + 1 = 4 > 0,

c^’₁₄ = c₁₄ + u₁ + v₄ = 7 – 2 + 4 = 9 > 0,

c^’₂₁ = c₂₁ + u₂ + v₁ = 4 – 6 + 1 = -1 < 0.

Від’ємне значення c^’₂₁ вказує на те, що змінну x₂₁ доцільно зробити базисною. Для визначення максимального допустимого значення x₂₁ позначимо збільшення об’єму перевезення від другого постачальника до першого споживача через w і запишемо цю величину у клітинку (2, 1) поточної транспортної матриці. Зберігання незмінної суми об’ємів перевезень у рядку 2 вимагає зменшення об’єму перевезення у деякій базисній клітинці цього рядка. Якщо зменшити об’єм перевезення у клітинці (2, 4), то порушиться сумарний об’єм перевезень у четвертому стовпчику. Тому зменшуємо об’єм у клітинці (2, 3) на величину w. Далі збільшуємо об’єм перевезення у базисній клітинці (3, 3) і зменшуємо – у (3, 1). У результаті отримуємо цикл, що містить визначену небазисну клітинку (2, 1) і базисні – (2, 3), (3, 3), (3, 1). Сусідні клітинки цього циклу знаходяться у одному стовпчику або у одному рядку. При цьому у одній з двох сусідніх клітинок об’єм перевезення збільшується на w, а у іншій зменшується на w. Тому сумарний об’єм перевезень у кожному стовпчику і у кожному рядку не змінюється (табл.11.5.

Таблиця 11.5

5
4
w					10-w
3
10-w					20+w

Оскільки об’єм перевезення повинен мати невід’ємне значення, максимальне допустиме значення w дорівнює мінімальному об’єму перевезення у базисних клітинках циклу, де відбувається віднімання w. Для табл.11.5 w = 10, і у двох клітинках (2, 3) і (3, 1) об’єм перевезення приймає нульове значення, але тільки одна з цих клітинок, наприклад, (2, 3) стає небазисною. Транспортна матриця для нового опорного плану x^’’ показана у табл.11.6. Відповідна сумарна вартість усіх перевезень - F(x^’’) = 1*15 + 2*5 + 4*10 + 2*30 + 4* 30 = 245.

Таблиця 11.6

5
			15- w		5+ w
4
10- w			w
3
0+w					30- w

За таблицею 11.6 для визначення потенціалів отримуємо систему

1 + u₁ + v₂ = 0,

2 + u₁ + v₃ = 0,

4 + u₂ + v₁ = 0,

2 + u₂ + v₄ = 0,

3 + u₃ + v₁ = 0,

4 + u₃ + v₃ = 0.

Розв’язком цієї системи є u₁ = 0, v₂ = -1, v₃ = -2, u₃ = -2, v₁ = -1, u₂ = -3, v₄ = 1.

Коефіцієнти індексного рядку при небазисних змінних отримують значення

c^’₁₁ = 5 + 0 – 1 = 4 > 0,

c^’₁₄ = 7 + 0 + 1 = 8 > 0,

c^’₂₂ = 1 – 3 – 1 = -3 < 0.

Тому змінна x₂₂ стає базисною, і як можна бачити з табл.11.6, x₂₁ стає небазисною, а w = 10. Наступна транспортна матриця з опорним планом x^’’’ показана у табл.11.7. Відповідна сумарна вартість усіх перевезень - F(x^’’’) = 1*5 + 2*15 + 1*10 + 2*30 + 3*10 + 4* 20 = 215.

Табл.11.7

5
4
3

Тепер для потенціалів отримуємо систему

1 + u₁ + v₂ = 0,

2 + u₁ + v₃ = 0,

1 + u₂ + v₂ = 0,

2 + u₂ + v₄ = 0,

3 + u₃ + v₁ = 0,

4 + u₃ + v₃ = 0.

Розв’язок системи - u₁ = 0, v₂ = -1, v₃ = -2, u₃ = -2, v₁ = -1, u₂ = 0, v₄ = -2. Для коефіцієнтів індексного рядку при небазисних змінних маємо

c^’₁₁ = 5 + 0 – 1 = 4 > 0,

c^’₁₄ = 7 + 0 - 2 = 8 > 0,

c^’₂₁ = 4 + 0 – 1 = 3 > 0,

c^’₂₃ = 6 + 0 – 2 = 3 > 0,

c^’₃₂ = 7 - 2 – 1 = 4 > 0,

c^’₃₄ = 5 - 2 – 2 = 1 > 0,

що свідчить про оптимальність останнього плану. Отже, F_min(x) = 215, а розв’язок задачі – x₁₂ = 5, x₁₃ = 15, x₂₂ = 10, x₂₄ = 30, x₃₁ = 10, x₃₃ = 20, і усі інші змінні дорівнюють нулю.

Дата добавления: 2014-01-13