15. Економічна постановка і математична модель закритої транспортної задачі (тз). Властивості планів тз.

ТЗ наз-ся закритою, якщо сумарний попит дорівнює сумарній пропозиції:

(1)

Економічна постановка закритої ТЗ:

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

Щоб скласти мат. модель, уведемо матрицю змінних X=|x_ij|, де x_ij - запланований обсяг перевезень від A_i до B_j. Очевидно, що розмірність цієї матриці mxn і матриця визначає шуканий план перевезень.

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

Аналогічно запланована кількість товару, що надходить до B_j, склад-ся з поставок від A₁- x_1j, від A₂- x_2j, від A_m- x_mj. Сума - це к-ть товару, що направляється до B_j. Оскільки всіх споживачів треба задовольнити, отримуємо таку систему обмежень:

(3)

Знайдемо мат. вираз цільової функції задачі – сумарної вартості перевезень. Тариф перевезень, тобто вартість перевезення одиниці товару за маршрутом A_iB_j, становить С_ij. Якщо за цим маршрутом перевозиться x_ij одиниць товару, то затрати становитимуть с_ij x_ij. Вираз відображує вартість перевезень від A_i до всіх B_j. Підсумовуючи його за j, дістаємо вартість перевезень

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

(4)

Будь-яка закрита ТЗ має розв'язок – опт. план (можливо не єдиний).

Властивості ТЗ:

1. Опорний план може бути виродженим: кількість ненульових поставок (заповнених кліток) менше розмірності ТЗ. В цьому випадку неможливо побудувати систему потенціалів та оцінити оптимальність. Вихід – додається необхідна к-ть 0-поставок, не порушуючи опорність (ациклічність).

2. Неєдиність опт. плану.

16. Економічна постановка і математичні моделі відкритих тз. Зведення їх до закритої тз. Інтерпретація додаткових змінних.

ТЗ наз-ся відкритою, якщо сумарний попит не дорівнює сумарній пропозиції.

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

Розглянемо мат. модель такої задачі. Весь товар, який мають постачальники, вивозиться: (1)

Споживачі одержують товар у кількостях, які менші або дорівнюють попиту на нього: (2)

Умова невід'ємності

і цільова функція (3)-(4)

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

Отже, щоб звести відкриту ТЗ (1)-(4) до канонічного виду, тобто до закритої ТЗ, вводять (m+1)-го фіктивного постачальника, потужність якого

і тарифи перевезень від нього дорівнюють нулю.

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

Величина x_in+1 – це к-ть товару, що залишився в A_i . Оскільки ці товари не перевозяться, транспортні витрати для них =0, отже, тарифи перевезень до фіктивного споживача можна вважати такими, що =0.