Конспект лекцій (стр. 11 )

Потрібно скласти найбільш економічний план перевезення.

Математичне формування транспортної задачі:

(1)

– матриця вартості перевезень

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

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

1. Запас у постачальників більший, ніж потреби споживачів:

2. Попит перевищує наявність вантажів:

Відкриті моделі можна зводити до закритих.

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

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

Таблиця №1

Отримувачі Виробники	1	2	3	….	n	Відправлено
1	C11 X11	C12 X12	C13 X13	….	C1n X1n	Q1
2	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	6 140	4 90	2	0 20	250
ТП2	5	3	2 130	0 30	160
Отримано	140	90	130	50

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

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

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

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

Таблиця №2

Отримувачі Виробники	П1	П2	П3	П4	Відправлено
ТП1	6 140	4 90	2 20	0	250
ТП2	5	3	2 110	0 50	160
Отримано	140	90	130	50

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

(4+2) > (3+2)

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

Таблиця №3

Отримувачі Виробники	П1	П2	П3	П4	Відправлено
ТП1	6 140	4	2 110	0	250
ТП2	5	3 90	2 20	0 50	160
Отримано	140	90	130	50

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