Практичне заняття 3

Тема: Розв’язування транспортної задачі лінійного програмування

 

Мета заняття:  отримання навичок розв’язування транспортних задач лінійного програмування

 

Приклад 1

У проектованій системі електропостачання є два вузли із джерелами живлення й три вузли споживачів. Потужності джерел становлять A₁ і А₂, а потужності споживачів ‑ B₁, В₂ і  В₃ о.п.. Взаємне розташування вузлів і можливих  до спорудження ліній електричної мережі показані на рис. 4.1.

Рис. 3.1. Взаємне розташування вузлів та можливих до спорудження ліній електропередач

 

Питомі витрати на передачу потужностей лініями між вузлами джерел і споживачами становлять с₁₁, с₁₂, с₁₃, с₂₁, с₂₂, с₂₃ у.о./о.п.

Скласти математичну модель для розв’язку транспортної задачі.

Розв’язок: Цільова функція, що представляє собою сумарні грошові витрати на електричну мережу, у відповідності з виразом (3.1) буде мати вигляд:

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

Граничні умови відповідно до співвідношення (3.3) запишуться як:

Отримані вирази являють собою математичну модель транспортної задачі для схеми, наведеної на рис. 3.1.

 

Приклад 2

Знайти допустимий розв’язок для завдання прикладу 1 при наступних вихідних даних:

Розв’язок: Зобразимо транспортну матрицю розмірністю 2х3 (табл. 3.1) і будемо заповнювати її відповідно до алгоритму методу північно-західного кута.

Таблиця 3.1

 

У клітинку х₁₁ в якості базисної змінної заносимо менше із двох значень потужностей х₁₁=mіn(А₁=50, В₁=20)=20. Баланс для 1-го стовпця (1-го споживача) виконаний (20=20). В інші клітинки цього стовпця заносимо нулі (вільна змінна х₂₁=0). Оскільки від джерела А₁ відібрано 20 о.п., що відходять до споживача В₁, потужність цього джерела умовно заміняється величиною 50-20=30.

З незаповнених клітинок транспортної матриці, що залишилися, вибирається нова північно-західна клітинка з с₁₂=1,8. У якості базисної змінної в цю клітинку заноситься менше із двох значень потужностей х₁₂=mіn(А₁=30, В₂=25)=25. Баланс для 2-го стовпця (2-го споживача) виконаний (25=25). В інші клітинки цього стовпця заносимо нулі (вільна змінна х₂₂=0). Оскільки від джерела А₁ відібрано 25 о.п., що відходять до споживача В₂, потужність цього джерела умовно заміняється величиною .

З незаповнених клітинок транспортної матриці, що залишилися, вибирається нова північно-західна клітинка з с₁₃=1,5. У якості базисної змінної в цю клітинку заноситься менше із двох значень потужностей х₁₃=mіn(А₁=5, В₂=35)=5. Баланс для 1-го рядка (1-го джерела) виконаний (50=50).

Оскільки від джерела А₁ відібрано 5 о.п., що відходять до споживача В₃, то потужність цього споживача умовно заміняється величиною 35-5=30. Останнє значення заноситься в незаповнену клітинку, що залишилася, транспортної матриці в якості базисної змінної х₂₃=30. Баланс для 3-го стовпця (3-го споживача) виконаний (35=35).

Отже, вся транспортна матриця заповнена. Баланси потужності по рядках (по вузлах джерел) і по стовпцях (по вузлах споживачів) виконуються. Всі змінні невід’ємні.

Отриманий вихідний розв’язок є допустимим. У цьому розв’язку:

‑ вільні змінні: х₂₁=0, х₂₂=0;

‑ базисні змінні: х₁₁=20, х₁₂=25, х₁₃=5, х₂₃=30 о.п.;

‑ значення цільової функції:

Схема електричної мережі, що відповідає отриманому допустимому розв’язку, показана на рис. 3.2.

Рис. 3.2. Схема електричної мережі, яка відповідає допустимому розв’язку методом північно-західного кута

 

Приклад 3

Знайти допустимий розв’язок для завдання прикладу 1, при наступних вихідних даних:

Розв’язок: Зобразимо транспортну матрицю розмірністю 2х3 (табл. 3.2) і будемо заповнювати її відповідно до алгоритму методу мінімальної питомої вартості.

У транспортній матриці вибирається клітинка з мінімальним значенням с_іj. Це клітинка зі змінною x₁₁ і питомою вартістю с₁₁=1,2.

Таблиця 3.2

 

У цю клітинку в якості базисної змінної заносимо менше із двох значень потужностей х₁₁=mіn(А₁=50, В₁=20)=20. Баланс для 1-го стовпця (1-го споживача) виконаний (20=20). В  інші клітинки цього стовпця заносимо нулі (вільна змінна х₂₁=0). Оскільки від джерела А₁ відібрано 20 о.п., що відходять до споживача В₁, потужність цього джерела умовно заміняється величиною 50-20=30.

З незаповнених клітинок транспортної матриці, що залишилися, вибирається клітинка з найменшою питомою вартістю с₁₃=1,5. У якості базисної змінної в цю клітинку заноситься менше із двох значень потужностей х₁₃=mіn(А₁=30, В₃=35)=30. Баланс для 1- го рядка (1-го джерела) виконаний. В інші клітинки цього рядка заносимо нулі (вільна змінна х₁₂=0). Оскільки споживачеві В₃ поставлено 30 о.п., потужність цього споживача умовно заміняється величиною 35-30=5.

З незаповнених клітинок транспортної матриці, що залишилися, вибираємо клітинку з найменшою питомою вартістю с₂₃=2,1. У якості базисної змінної в цю клітинку заносимо менше із двох значень потужностей х₂₃=mіn(А₂=30,В₃=5)=5. Баланс для 3-го стовпця (3-го споживача) виконаний.

Оскільки від джерела А₂ відібрано 5 о.п., що відходять до споживача В₃, потужність цього джерела умовно заміняється величиною 30-5=25. Останнє значення заноситься в незаповнену клітинку, що залишилася, транспортної матриці в якості базисної змінної х₂₂=25.

Отже, вся транспортна матриця заповнена. Баланси потужності по рядках (по вузлах джерел) і по стовпцях (по вузлах споживачів) виконуються. Всі змінні невід’ємні.

Отриманий вихідний розв’язок є допустимим. У цьому розв’язку:

‑ вільні змінні: х₁₂=0, х₂₁=0;

‑ базисні змінні: х₁₁=20, х₁₃=30, х₂₂=25, х₂₃=5 о.п.;

‑ значення цільової функції:

Схема електричної мережі, що відповідає отриманому допустимому розв’язку, показана на рис. 3.3.

Рис. 3.3. Схема електричної мережі, яка відповідає допустимому розв’язку методом допустимої питомої вартості

 

Приклад 4

Розв’язати задачу розглянутого вище прикладу 3 для випадку, коли потужність, передана лінією х₁₃, обмежена величиною 20 о.п. (х₁₃ ≤ 20).

Розв’язок. У вихідній транспортній матриці (табл. 4.3) третій стовпець розбиваємо на два стовпці з умовними споживачами В₃'=35-20=15 і В₃"=20 о.п. Питому вартість передачі потужності від джерела А₁ до умовного споживача В₃' приймемо рівною 100 у.о./о.п. Інші питомі вартості такі ж, як у табл. 3.3.

Вихідний допустимий розв’язок отриманий методом найменшої питомої вартості й представлений в табл. 3.3.

В цьому розв’язку вільні змінні х₁₃'=х₂₁=x₂₃"=0; базисні змінні х₁₁=20, х₁₂=10, х₁₃"=20, х₂₂=15, x₂₃"=15 о.п.

Значення цільової функції:

Таблиця 3.3

 

Далі використовуємо метод потенціалів. Для прийнятого довільно значення одного з потенціалів (U₁=1) величини інших потенціалів визначаємо за виразом V_i+U_j=с_ij,, який справедливий для базисних змінних (табл. 3.3).

Оскільки для вільної змінної х₂₁

переводимо цю змінну в базис. Цикл перерахунку змінних відзначений у табл. 3.3. знаками "+" і "‑". У розряд вільних перейде базисна змінна х₂₂. Новий допустимий розв’язок показаний в табл. 3.4.

 

 

Таблиця 3.4

 

Рис. 3.4. Оптимальна схема електричної мережі

 

Цей розв’язок є оптимальним, оскільки для всіх вільних змінних виконується умова:

при якій переведення будь-якої вільної змінної в базис приведе до збільшення цільової функції Z. Схема, що відповідає оптимальному розв’язку, наведена на рис. 3.4.

 

Приклад 5

У проектованій системі електропостачання є два вузли джерел живлення та два вузли споживачів. Потужності джерел становлять A₁=100 і A₂=50, а потужності споживачів - B₃=90 і B₄=60 о.п. Питомі витрати на передачу потужностей лініями між вузлами становлять с₁₂=10, с₁₃=5, с₁₄=2, с₂₃=4, с₂₄=3 і с₃₄=2 у.о./о.п.

Потрібно знайти оптимальну схему електричної мережі.

Розв’язок: Відповідно до умов завдання прийнята наступна наскрізна нумерація вузлів А₁, А₂, В₃ і В₄. Складемо транспортну матрицю. Ця матриця буде квадратною розмірністю 4х4 (табл. 3.5).

Таблиця 3.5

	U1=1	U2=2	U3=6	U4=3	Запаси
V1=-1	0 0	10 0	-              5 40	+             2 60	А1 = 100
V2=-2	10 0	0 0	4 50	3 0	А2 = 50
V3=-6	5 0	4 0	0 0	2 0	В3 = 0
V4=-3	2 0	3 0	+             2 0	-              0 0	В4 = 0
Потреби	А1 = 0	А2 = 0	В3 = 90	В4 = 60	= 520

 

Праворуч від матриці, де розміщені потужності джерел живлення, зазначені нульові потужності вузлів 3 і 4 (В₃=0,  В₄=0), оскільки ці вузли не є джерелами. Знизу під матрицею, де розміщені потужності споживачів, зазначені нульові потужності вузлів 1 і 2 (А₁=0, А₂=0), оскільки ці вузли не є споживачами.

Вихідний допустимий розв’язок знайдено методом найменшої питомої вартості. В отриманому допустимому розв’язку:

‑ вільні змінні

‑ базисні змінні

‑ значення цільової функції Z= с₁₃х₁₃+ с₁₄x₁₄+ с₂₃x₂₃ = 5·40 + 2·60 + +4·50 = 520 у.о.

Присвоїмо кожному рядку потенціал V_i, а кожному стовпцю ‑ потенціал U_j. Відповідно до методу потенціалів для всіх базисних змінних сума потенціалів дорівнює питомій вартості:

Задамося довільно значенням одного з потенціалів (U₁=1). Обчислені значення інших потенціалів показані в табл. 3.5. Оскільки для базисних транзитних змінних питомі вартості с_ii=0, потенціали з однаковими індексами рівні за величиною й протилежні за знаком V_i=-U_i. Отриманому вихідному допустимому розв’язку відповідає схема електричної мережі, наведена на рис. 3.5,а. Спробуємо покращити отриманий розв’язок.

Рис. 3.5. Вихідна (а) та оптимальна (б) схеми електричної мережі

 

Для всіх вільних змінних перевіримо співвідношення суми потенціалів з питомою вартістю. Для вільної змінної х₃₄:

Отже, вільну змінну х₃₄ варто перевести в базис. Для цієї змінної будуємо цикл (табл. 3.5). Початкова вершина циклу лежить у клітинці вільної змінної х₃₄. Інші вершини циклу лежать у клітинках, що відповідають  базисним змінним х₁₃, х₁₄ і х₄₄. Початковій вершині привласнюємо знак "+", далі знаки вершин циклу чергуються.

При збільшенні вільної змінної х₄₃ базисна змінна х₁₄ буде збільшуватися, а базисні змінні х₁₃ і х₄₄ будуть зменшуватися. Оскільки транзитна базисна змінна х₄₄ входить у розв’язок задачі зі знаком "мінус", її зміна у від’ємну сторону не обмежена. Зменшення базисної змінної х₁₃=40 обмежено нульовим значенням. Тому значення всіх змінних у вершинах циклу варто змінити на 40 о.п.

У новому допустимому розв’язку (табл. 3.6):

‑ вільні змінні х₁₂=х₁₃=х₂₁=х₂₄=х₃₁=х₃₂=х₃₄=х₄₁=х₄₂=0;

‑ базисні змінні х₁₁=х₂₂=х₃₃=0, х₄₄=-40, х₁₄=100, х₂₃=50, х₄₃=40 о.п.;

‑ значення цільової функції F=с₁₄х₁₄+с₂₃x₂₃+с₄₃x₄₃= 2·100+4·50+2·40= =480 у.о.

Таблиця 3.6

					Запаси
	0 0	10 0	5 0	2 100	А1 = 100
	10 0	0 0	4 50	3 0	А2 = 50
	5 0	4 0	0 0	2 0	В3 = 0
	2 0	3 0	2 40	0 -40	В4 = 0
Потреби	А1 = 0	А2 = 0	В3 = 90	В4 = 60	F= 480

 

У цьому розв’язку для  всіх вільних змінних виконується умова:

Отже, переведення будь-якої вільної змінної в базис не поліпшить розв’язку. Отриманий розв’язок є оптимальним. Оптимальна схема електричної мережі показана на рис. 3.5,б.