Розв’язок транспортної задачі

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

Таблиця №1

Отримувачі   Виробники				….	n	Відправлено
	C11 X11	C12 X12	C13 X13	….	C1n X1n	Q1
	C21 X21	C22 X22	C23 X23	….	C2n X2n	Q2
….	….	….	….	….	….	….
m	Cm1 Xm1	Cm2 Xm2	Cm3 Xm3	….	Cmn Xmn	Qm
Отримано	b1	B2	B3	….	Bn

Кожний розв’язок системи рівнянь (1) є одним з можливих варіантів розв’язання і носить назву допустимого плану.

Дана задача лінійного програмування полягає у знаходженні з безлічі допустимих планів такого плану, який буде обертати в мінімум цільову функцію:

Такий допустимий план має назву оптимального. При складанні вихідного плану перевезень зручно користуватись прийомом, який відомий під назвою північно-західного кута.

Метод північно-західного кута полягає у наступному:

1. Спочатку максимально можлива кількість вантажу міститься у верхню ліву ячійку таблиці №1. Цій клітці відповідає змінна . Потім заповнюється сусідня клітка в першому рядку якщо на пункті виробництва залишився вантаж (тобто ).

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

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

Ми одержали деякий початковий допустимий план вихідної задачі, для якого можна розрахувати значення цільової функції.

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

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

Одержуємо новий план і знову розраховуємо значення цільової функції.

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

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

Приклад №5. Потрібно вибрати оптимальну схему трьох вузлів електричних навантажень, яка відповідає мінімуму капітальних вкладень.

Живлення здійснюється від двох ТП. Схема і параметри зазначені на мал. 2. Прийняти, що капітальні вкладення пропорційні довжині і перетину лінії.

Розв’язок:

1. Дана задача може бути зведена до транспортної. Число вихідних пунктів m =2, пунктів споживання n =3.

,

тобто ми маємо справу з відкритою моделлю.

2. Зведемо її до закритої. Введемо фіктивний пункт П4, який споживає 50 кВА, відстань від якого до кожної ТП дорівнює нулю.

3. Цільова функція буде зображувати собою суму добутків потужності та відстань:

4. Для розв’язання задачі складемо вихідний план транспортної задачі (таблиця №1).

Таблиця №1

Отримувачі   Виробники	П1	П2	П3	П4	Відправлено
ТП1
ТП2
Отримано

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

Обираємо прямокутний контур з однією вільною ячійкою. Визначаємо і звіряємо суми тарифів діагоналей. Отримуємо: (2+0) = (2+0)

тобто можна завантажувати ячійку ТП1-П3.

5. Складаємо новий допустимий план (таблиця №2), для якого цільова функція не змінилася (L=1460), оскільки суми тарифів діагоналей були однаковими.

Таблиця №2

Отримувачі   Виробники	П1	П2	П3	П4	Відправлено
ТП1		90
ТП2
Отримано

Для позначеного в таблиці №2 прямокутного контуру сума тарифів діагоналі з вільною ячійкою менша суми тарифів другої діагоналі:

(4+2) > (3+2)

6. Будуємо новий допустимий план (таблиця №3)

Таблиця №3

Отримувачі   Виробники	П1	П2	П3	П4	Відправлено
ТП1	6
ТП2
Отримано

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

Таким же шляхом визначаємо наступні рішення і відповідні їм значення цільової функції:

(6+2) > (5+2)

7. Будуємо наступний допустимий план (таблиця №4):

Таблиця №4

Отримувачі   Виробники	П1	П2	П3	П4	Відправлено
ТП1	6
ТП2
Отримано

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

Для позначеного прямокутного контуру (таблиця №4) визначаємо і звіряємо суми тарифів діагоналей:

(6+0) > (5+0)

8. Будуємо новий допустимий план (таблиця №5):

Таблиця №5

Отримувачі   Виробники	П1	П2	П3	П4	Відправлено
ТП1
ТП2
Отримано

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

1 контур (6+0) > (5+0) – не можна робити перерозподіл (тому що

діагональ з вільною ячійкою більша ніж з

заповненою)

2 контур (6+2) > (5+2) – не можна робити перерозподіл.

3 контур (6+3) = (5+4) – перерозподіл не має змісту, оскільки не

відбудеться поліпшення параметру, який

оптимізується.

Значення ЦФ при оптимальному варіанті розподілу:

Оптимальна схема електропостачання прийме такий вигляд:

10.3. Питання для самоконтролю:

1. Формулювання транспортної задачі?

2. Які моделі транспортної задачі бувають?

3. Метод північно-західного кута?

4. Коли припиняється процес оптимізації?

Лекція №11