Постановка й математична модель транспортної задачі

Розглянемо традиційну постановку одноетапної задачі планування перевезень - транспортної задачі (ТЗ).

У деяких пунктах А ₁, А ₂,..., а_і, ..., А_т, що називаються постачальниками, зосереджено товар у кількості відповідно а ₁, а ₂,..., а_і, ..., а_т. Пункти В ₁, В ₂,..., B_i, …, В_n, що називаються споживачами, мають потребу в цьому товарі в кількості відповідно b ₁, b ₂,..., b_i, …, b_n. Числа a_i називатимемо потужностями (пропозиціями) постачальників, a b_j – попитами споживачів. Між пунктами A_i і B_j існують комунікації та відомо затрати на перевезення товарів від A_i до B_j. Треба скласти план перевезень, який забезпечує мінімум транспортних витрат.

Для того щоб цю задачу можна було подати у виглядіЗЛП, треба зробити ряд, у більшості випадків обґрунтованих, припущень.

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

2. Вартість перевезень пропорційна обсягу товару, що перевозиться, тобто задано матрицю тарифів С = || с_ij || розмірності m ´ n,де с_ij – вартість перевезення одиниці товару від A_i до B_j.

У ході постановки ТЗ дуже важливу роль відіграють два параметри - сумарний попит і сумарна пропозиція. Сумарний попит відображує ту кількість товару, яка потрібна споживачам. За взятих позначеньвін дорівнює . Сумарна пропозиція - загальна кількість товарів, що знаходяться у поставщиків, дорівнює . Між цими двома величинами може бути одне з трьох співвідношень: менше, більше або дорівнює.

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

= . (2.80)

У противному разі ТЗ називається відкритою.

Дата добавления: 2015-07-14