Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

5.9.1. Транспортна задача у мережевій формі

Нехай задано граф із скінченною кількістю вершин і ребер. Поставимо у відповідність кожній вершині деяке число (і = 1, 2, ..., m), яке назвемо інтенсивністю i-ої вершини, а кожній дузі (іj) — число — пропускну здатність (іj)-ої дуги, відносячи ці величини до певного відрізка часу t (0 < t < ), наприклад, до певної одиниці часу. За цих умов скінченний граф перетворюється в мережу (сіть). Позначимо через невідому величину, що означає обсяг деякої продукції, яку переміщають по (ij)-й дузі за деякий відрізок часу. Тоді для цього самого відрізка часу для кожної k-ої вершини графа можна записати таку балансову рівність:

. (5.42)

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

Природно вважати змінні і невід’ємними і обмеженими зверху числами і , так що:

. (5.43)

У свою чергу, можна вважати, що величини і можуть змінюватися в таких межах:

. (5.44)

Рівняння (5.42) можна трактувати як рівняння безперервності потоку розглядуваної продукції по певній мережі (доріг, трубопроводів і т. п.) в деякому околі k-ої вершини (пункту). Прикладом може бути рівняння збереження кількості рідини, що проходить по трубопровідній мережі.

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

. (5.45)

Легко помітити, що сформульована сітьова транспортна задача (5.42)—(5.45) є узагальненням звичайної транспортної задачі (5.1)—(5.4) за умови наявності проміжних пунктів перевезень і обмежених пропускних здатностей шляхів сполучення.