2.3. Розробка математичної моделі задачі дослідження

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

Таблиця 2.1

Споживачі		В1	В2	...	Вn
Постачальники		b1	b2	...	bn
A1	а1	с11 x11	с12 x12	...	с1n x1n
A2	а2	с21 x21	с22 x22	…	с2n x2n
…	…	…	…	…	…
Am	аm	сm1 xm1	сm2 xm2	…	сmn xmn

Мають виконуватися такі умови:

1. сумарний обсяг продукції, що вивозиться з кожного і-го пункту, має дорівнювати запасу продукції в даному пункті:

2. сумарний обсяг продукції, що ввезений кожному j-му споживачеві, має дорівнювати його потребам:

3. сумарна вартість всіх перевезень повинна бути мінімальною:

Очевидно, що .

У скороченій формі запису математична модель транспортної задачі за критерієм вартості перевезень має такий вигляд:

(2.4)

за обмежень:

; (2.5)

; (2.6)

. (2.7)

У розглянутій задачі має виконуватися умова:

. (2.8)

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

Домовимося планом транспортної задачі називати будь-який невід’ємний розв’язок системи обмежень (2.5)—(2.7), який позначають матрицею . Значення невідомих величин — обсяги продукції, що мають бути перевезені від i-х постачальників до j-х споживачів, називатимемо перевезеннями.

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

Теорема (умова існування розв’язку транспортної задачі): необхідною і достатньою умовою існування розв’язку транспортної задачі (2.4)—(2.7) є її збалансованість: .

Доведення. Необхідність. Нехай задача (2.4)—(2.7) має розв’язок , тоді для нього виконуються рівняння-обмеження (2.5) і (2.6). Підсумуємо відповідно ліві та праві частини систем рівнянь (2.5) і (2.6). Матимемо:

, (2.9)

(2.10)

Оскільки ліві частини рівнянь (2.9) та (2.10) збігаються, то праві також рівні одна одній, отже, виконується умова:

. (2.11)

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

Нехай = W > 0. Розглянемо величини ( ). Підставивши значення в систему обмежень задачі (2.4)—(2.7), матимемо:

;

.

Оскільки умови (2.5) та (2.6) виконуються, то є планом наведеної транспортної задачі.

Виберемо з елементів найбільше значення і позначимо його через . Якщо замінити в цільовій функ­ції (2.4) всі коефіцієнти на , то, враховуючи (2.5), матимемо:

.

Виберемо з елементів найменше значення і позначимо його через . Якщо замінити в цільовій функ­ції (2.4) всі коефіцієнти на , то, враховуючи (2.5), матимемо:

.

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

.

Теорему доведено.

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

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

Як згадувалося вище, транспортна задача (2.4)—(2.6) є звичайною задачею лінійного програмування і може бути розв’язана симплексним методом, однак особливості побудови математичної моделі транспортної задачі дають змогу розв’язати її простіше. Легко помітити, що всі коефіцієнти при змінних у рівняннях (2.5), (2.6) дорівнюють одиниці, а сама система обмежень (2.5), (2.6) задана в канонічній формі. Крім того, система обмежень (2.5), (2.6) складається з mn невідомих та m + n рівнянь, які пов’язані між собою співвідношенням (2.11). Якщо додати відповідно праві та ліві частини систем рівнянь (2.5) та (2.6), то отримаємо два однакових рівняння:

;

.

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