Зведення відкритої задачі до закритої.

Зведення відкритої задачі до закритої

Якщо при перевірці збалансованості транспортної задачі транспортна задача

Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m a_i = \sum\limits_{j=1}^n b_j

виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу. Це здійснюється введенням фіктивного (умовного) постачальника Неможливо розібрати вираз (невідома помилка): A_{m+1}

у разі перевищення загального попиту над запасами 

Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m a_i < \sum\limits_{j=1}^n b_j із ресурсом обсягом

Неможливо розібрати вираз (невідома помилка): a_{m+1} = \sum\limits_{j=1}^n b_j - \sum\limits_{i=1}^m a_i

.

Якщо ж загальні запаси постачальників перевищують попит споживачів

Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m a_i > \sum\limits_{j=1}^n b_j

то до закритого типу задача зводиться введенням фіктивного (умовного) споживача Неможливо розібрати вираз (невідома помилка): B_{n+1}

з потребою  

Неможливо розібрати вираз (невідома помилка): b_{n+1} = \sum\limits_{i=1}^m a_i - \sum\limits_{j=1}^n b_j

Вартість перевезення одиниці продукції від фіктивного по-стачальника Неможливо розібрати вираз (невідома помилка): A_{m+1}

( або фіктивного споживача Неможливо розібрати вираз (невідома помилка):  B_{m+1} 
) до кожного зі споживачів (виробників) має дорівнювати нулю або бути набагато більшою за реальні витрати Неможливо розібрати вираз (невідома помилка):   C_{ij} =(i=\overline{1,m}; j=\overline{1,n}) 
Як правило, у такому разі використовують нульові значення вартостей перевезень, що дає змогу спростити обчислення.

Всі коефіцієнти при змінних у рівняннях

Неможливо розібрати вираз (невідома помилка): \sum\limits_{j=1}^n x_{ij} = a_i (i=\overline{1,m}); (1)

Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m x_{ij} = b_i (j=\overline{1,m}); (2)

дорівнюють одиниці, а сама система в канонічній формі. Система обмежень (1) , (2) складається з mn невідомих та m + n рівнянь, які пов’язані між собою співвідношенням
Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m a_i = \sum\limits_{j=1}^n b_j . Якщо додати відповідно праві та ліві частини систем рівнянь (1) та (2)

Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m \sum\limits_{j=1}^n x_{ij} = \sum\limits_{i=1}^m a_i = \sum\limits_{j=1}^n b_j

Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m \sum\limits_{j=1}^n x_{ij} = \sum\limits_{j=1}^n b_j = \sum\limits_{i=1}^m a_i

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

Джерело