Відмінності між версіями «Зведення відкритої задачі до закритої.»
(Створена сторінка: == Зведення відкритої задачі до закритої == Якщо при перевірці збалансованості <br><center><math> ...) |
|||
| Рядок 3: | Рядок 3: | ||
<br><center><math> \sum\limits_{i=1}^m a_i = \sum\limits_{j=1}^n b_j </math> </center> | <br><center><math> \sum\limits_{i=1}^m a_i = \sum\limits_{j=1}^n b_j </math> </center> | ||
виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу. | виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу. | ||
| − | Це здійснюється введенням фіктивного (умовного) постачальника A_{m+1} у разі перевищення загального попиту над запасами | + | Це здійснюється введенням фіктивного (умовного) постачальника <math>A_{m+1}</math> у разі перевищення загального попиту над запасами |
<br><center><math> \sum\limits_{i=1}^m a_i < \sum\limits_{j=1}^n b_j </math> </center> | <br><center><math> \sum\limits_{i=1}^m a_i < \sum\limits_{j=1}^n b_j </math> </center> | ||
із ресурсом обсягом <center> | із ресурсом обсягом <center> | ||
Версія за 11:28, 4 травня 2012
Зведення відкритої задачі до закритої
Якщо при перевірці збалансованості
виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу. Це здійснюється введенням фіктивного (умовного) постачальника Неможливо розібрати вираз (невідома помилка): A_{m+1}
у разі перевищення загального попиту над запасами
Неможливо розібрати вираз (невідома помилка): a_{m+1} = \sum\limits_{j=1}^n b_j - \sum\limits_{i=1}^m a_i
Якщо ж загальні запаси постачальників перевищують попит споживачів
то до закритого типу задача зводиться введенням фіктивного (умовного) споживача Неможливо розібрати вираз (невідома помилка): B_{n+1}
з потребою
Вартість перевезення одиниці продукції від фіктивного по-стачальника Неможливо розібрати вираз (невідома помилка): A_{m+1}
( або фіктивного споживача Неможливо розібрати вираз (невідома помилка): B_{m+1}
) до кожного зі споживачів (виробників) має дорівнювати нулю або бути набагато більшою за реальні витрати Неможливо розібрати вираз (невідома помилка): C_{ij} =(i=\overline{1,m}; j=\overline{1,n})
Як правило, у такому разі використовують нульові значення вартостей перевезень, що дає змогу спростити обчислення.
Всі коефіцієнти при змінних у рівняннях
Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m x_{ij} = b_i (j=\overline{1,m}); (2)
дорівнюють одиниці, а сама система в канонічній формі. Система обмежень (1) , (2) складається з mn невідомих та m + n рівнянь, які пов’язані між собою співвідношенням
Неможливо розібрати вираз (невідома помилка): \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 базисних змінних.
