Простейшая транспортная задача (Т-задача)

Основополагающая для всех транспортных задач. Исходные данные: m – число пунктов отправления (ПО); n – число пунктов назначения (ПН); C_ij – затраты на перевозку единицы груза из пункта i в пункт j, " ij; a_i – количество груза в пункте i," i (возможности ПО); b_j – потребность в грузе в пункте j, " j.

Критерий - суммарные затраты на перевозку. Модель записывается в виде:

Однако такая запись модели корректна только если Задача, в которой - сбалансированная. Любая несбалансированная задача легко приводится к сбалансированной. Поэтому здесь рассмотрим только сбалансированную задачу:

" X_ij ³ 0.

Х– матрица перевозок; С – матрица транспортных затрат;

a =(a₁, a₂,.., a_m) – вектор возм-тей ПО;

b =(b₁, b₂,..., b_n) – вектор потр-й ПН.

Особенности задачи:

¨ Модель содержит две группы условий, размерность которых равна соответствующему числу ПО и ПН; число переменных равно произведению m ´ n;

¨ Все коэффициенты при переменных в условиях равны единице;

¨ Каждая переменная входит в условия ровно 2 раза, по 1 в кажд. группу условий;

¨ Задача имеет простые условия разрешимости, кот. определяются след. теоремой:

Для разрешимости Т-задачи необходимо и достаточно, чтобы она была сбалансированной. Теорема справедлива при конечных значениях С_ij.

Доказательство. Необходимость доказывается исходя из того, что задача разрешима. В этом случае все условия задачи выполняются. Просуммируем условия ПО по i, а условия ПН по j:

Так как левые части равенств =, то = и правые. Т.о, в разрешимой задаче всегда имеет место формальный баланс возможностей и потребностей.

Достаточность. Задача ЛП всегда разрешима, если допустимое множество – выпуклый многогранник, то есть непустое и ограниченное. Ограниченность переменных снизу задана явно, а ограничение сверху следует из конечности всех a_i и b_j, больше которых переменные быть не могут -> множество ограничено. Докажем, что оно непустое. Для этого достаточно найти хотя бы одно доп. решение. Одно из таких решений можно построить, если задача сбалансирована: -->

Оно неотрицательно. Остается проверить выполнение основных условий задачи.

Þ решение удовлетворяет условиям ПО;

решение удовлетворяет условиям ПН ←

Т.о, доп. множество сбаланс. задачи непустое и ограниченное-> задача разрешима.

Условия ПО и ПН – линейно зависимы из-за сбалансированности задачи. Ранг системы равен m+n- 1. Такую размерность имеют базис и базисное решение Т-задачи.

Транспортная задача с ограниченными пропускными способностями (T_d - задача)

Отличается от предыдущей задачи учетом ограничений на пропускные возможности коммуникаций. Ее модель имеет вид

0 £ X_ij £ d_ij, " i,j,

где d_ij –пропускная способность коммуникации i j.

Ограничения вносят коррективы в свойства задачи. Из особенностей модели, присущих Т-задаче, сохраняются все, кроме последней. В Т_d-задаче условие сбалансированности не является достаточным для разрешимости задачи. В число необходимых условий существования решения помимо его входят еще две группы условий, отражающих физическую реализуемость решения:

Они требуют, чтобы суммарная пропускная способность коммуникаций, входящих в каждый ПН была не меньше объема поставок, а выходящих из ПО – не меньше количества вывози­мого груза. Если хотя бы одно из них нарушается, задача заведомо неразрешима. Однако и выполнение всех необходимых условий не гарантирует разрешимость Т_d-задачи. Пример (рис): задача неразрешима, так как невозможно поставить во второй пункт назначения 8 единиц груза.