Постановка транспортной задачи
Рассмотрим следующую задачу, называемую транспортной задачей.
Имеется m поставщиков A1,A2 ,..., Am, у которых сосредоточены запасы одного и того же груза в количестве m a1,a2,...,am единиц, соответственно. Этот груз нужно доставить n потребителям B1,B2,..., Bn, заказавшим b1, b2,...,bn единиц этого груза, соответственно. Известны также все тарифы перевозок груза cij (стоимость перевозок единицы груза) от поставщика Ai к потребителю Bj. Требуется составить такой план перевозок, при котором общая стоимость всех перевозок была бы минимальной.
Условие транспортной задачи удобно записать в виде следующей:
Обозначим суммарный запас груза у всех поставщиков символом a , а суммарную потребность в грузе у всех потребителей – символом b. Тогда
Транспортная задача называется закрытой, если a = b . Если же
a ≠ b , то транспортная задача называется открытой. В случае открытой задачи при a < b весь груз будет вывезен, однако будут недопоставки груза экономически невыгодным потребителям. При a > b , наоборот, будут удовлетворены все потребители, но часть груза останется на складах экономически невыгодных поставщиков.
Пусть xij (xij ≥ 0) – количество груза, отправляемого поставщиком Ai потребителю Bj. Тогда суммарные затраты z на перевозки будут вычисляться по формуле:
Функция z называется целевой функцией.
Математическая формулировка транспортной задачи заключается в нахождении плана перевозок X = {xij}, который удовлетворяет системе ограничений
и доставляет минимум целевой функции z.
План перевозок, реализующий минимум целевой функции z , называется оптимальным.
Смысл первой группы равенств в системе ограничений состоит в том, что суммарное количество груза, отправленное всем потребителям каждым поставщиком, равно запасу груза у этого поставщика. Вторая группа равенств в системе ограничений показывает, что суммарное количество груза, полученное каждым потребителем от всех поставщиков, равно заказу этого потребителя.
|