Транспортная задача. 
Исследование операций в экономике

Экономико-математическая модель транспортной задачи

Важным частным случаем задачи линейного программирования является так называемая транспортная задача.

7.1. Построить экономико-математическую модель следующей задачи. Имеются три поставщика и четыре потребителя. Мощность поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары «поставщик — потребитель» сведены в таблицу поставок (табл. 7.1).

Таблица 7.1

Поставщики.	Мощность поставщиков.	Потребители и их спрос.

В левом верхнем углу произвольной (г, у)-клетки (г — номер строки, У — номер столбца) стоит так называемый коэффициент затрат — затраты на перевозку единицы груза от г-го поставщика к j-му потребителю; например, в левом верхнем углу клетки (1,4) стоит число 3, следовательно, перевозка единицы груза от 1-го поставщика к 4-му потребителю обойдется в 3 условных денежных единицы и т. д.

Задача ставится следующим образом. Найти объемы перевозок для каждой пары «поставщик — потребитель» так, чтобы:

• 1) мощности всех поставщиков были реализованы;
• 2) опросы всех потребителей были удовлетворены;
• 3) суммарные затраты на перевозку были бы минимальны.

Решение. Построим экономико-математическую модель данной задачи. Искомый объем перевозки от г-го поставщика к 7-му потребителю обозначим через х~ и назовем поставкой клетки (i, j). Например, х[2 — искомый объем перевозки от 1-го поставщика ко 2-му потребителю, или поставка клетки (1, 2) и т. д. Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных х}. Так, например, объем груза, забираемого от 1-го поставщика, должен быть равен мощности этого поставщика — 60 единицам, т. е. (уравнение баланса по первой строке). Таким образом, чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок, т. е.

(7.1).

Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса составляем для каждого столбца таблицы поставок:

(7.2).

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует дополнительно предположить, что

Суммарные затраты F на перевозку выражаются через коэффициенты затрат и поставки следующим образом:

(7.3).

Теперь можно дать математическую формулировку задачи (без обращения к ее содержательному экономическому смыслу). На множестве неотрицательных решений системы ограничений (7.1) и (7.2) найти такое решение , при котором линейная функция (7.3) принимает минимальное значение.

Особенности экономико-математической модели транспортной задачи:

• • система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме);
• • коэффициенты при переменных системы ограничений равны единице или пулю;
• • каждая переменная входит в систему ограничений два раза: один раз — в систему (ТЛ) и один раз — в систему (7.2).

Для математической формулировки транспортной задачи в общей постановке обозначим через с-коэффициенты затрат, через М. — мощности поставщиков, через N. — мощности потребителей, где i = 1,2,…, mj = 1,2,…, и; ni — число поставщиков, ? — число потребителей. Тогда система ограничений примет вид.

(7.4).

(7.5).

Система (7.4) включает в себя уравнение баланса по строкам, а система (7.5) — по столбцам таблицы поставок. Линейная функция в данном случае.

(7.6).

Математическая формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (7.4), (7.5) найти такое решение , при котором значение линейной функции (7.6) минимально.

Произвольное допустимое решение системы ограничений (7.4), (7.5) назовем распределением поставок. Такое решение задает заполнение таблицы поставок, поэтому в дальнейшем значение произвольной переменной х~ и содержимое соответствующей клетки таблицы поставок будут отождествляться.

Транспортная задача, приведенная в задаче 7.1, обладает важной особенностью: суммарная мощность поставщиков равна суммарной мощности потребителей, т. е.

(7.7).

Такие транспортные задачи называются закрытыми (говорят также, что транспортная задача в этом случае имеет закрытую модель). В противном случае транспортная задача называется открытой (открытая модель транспортной задачи).

Частный случай транспортной задачи, для которого мощности всех поставщиков и потребителей единичны, называется задачей о назначениях (о распределении персонала или задачей выбора). «Поставщики» в данном случае интерпретируются как исполнители некоторого вида работ, «потребители» — это виды работ, «коэффициенты затрат» — трудозатраты исполнителей на виды работы. Требуется составить такой план закрепления исполнителей за видами работы, при котором суммарные трудозатраты были бы минимальны.

Рассмотрим закрытую транспортную задачу. Являясь задачей линейного программирования, транспортная задача может быть решена симплексным методом. Однако специфичная форма системы ограничений данной задачи позволяет существенно упростить обычный симплексный метод. Модификация симплексного метода применительно к транспортной задаче называется распределительным методом, или методом потенциалов. По аналогии с общим случаем решение в нем осуществляется по шагам, и каждому шагу соответствует разбиение переменных на основные (базисные) и неосновные (свободные).

Число г основных переменных транспортной задачи равно рангу системы линейных уравнений (максимальному числу линейно независимых уравнений в системе ограничений).

Теорема 7.1. Ранг r системы уравнений (7.4), (7.5) при условии (7.7) равен т + п — 1^[1].

? Прежде всего заметим, что уравнения системы (7.4), (7.5) при условии (7.7) линейно зависимы и, следовательно, ранг системы не больше, чем т + п — 1. Действительно, сравним сумму.

(7.8).

первых т уравнений системы (сумму уравнений системы (7.4)) с суммой.

(7.9).

оставшихся п уравнений (суммой уравнений системы (7.5)).

Согласно условию (7.7) правые части уравнений (7.8) и (7.9) совпадают. Левые части (7.8) и (7.9), являющиеся суммами всевозможных переменных х~ данной задачи, также совпадают. Следовательно, совпадают уравнения (7.8) и (7.9), т. е. сумма первых т уравнений системы ограничений равна сумме оставшихся п уравнений системы ограничений: уравнения системы (7.4), (7.5) линейно зависимы.

Докажем, что ранг г системы не меньше, чем т + п — 1. Из линейной алгебры известно, что если некоторые k переменных произвольной системы линейных уравнений можно линейно выразить через остальные переменные системы, то ранг этой системы не меньше, чем к.

Выразим, например, переменные х~, входящие в первый столбец и первую строку табл. 7.1, через остальные переменные Ху где i = 2, 3,…, m, j = 2, 3, …, п. Сначала найдем такие выражения для переменных, отличных от хп. Для каждой переменной хх. первой строки, где j = 2,3,…, п, воспользуемся уравнением баланса по соответствующему столбцу.

(7.10).

Аналогично для каждой переменной первого столбца, где i = 2, 3, т, воспользуемся уравнением баланса по соответствующей строке:

Для нахождения выражения для х] { воспользуемся, например, уравнением баланса по первой строке:

(7.11).

Подставляя в правую часть уравнения (7.11) выражения для Ху, где j = 2, 3,…, п из уравнения (7.10), получаем искомое выражение для .гп.

Таким образом, т + п- 1 переменных этой задачи можно выразить через остальные тп — т — п + 1 переменные, т. е. ранг г системы г? т + п -1.

Сравнивая два полученных ограничения на ранг г системы (7.4) и (7.5) {г~>т + п-1 и гйт+п-1), получаем, что г= т + п — 1. ¦

Основное следствие теоремы 7.1: число г основных (базисных) переменных закрытой транспортной задачи равно т + п- 1, где т — число поставщиков; п — число потребителей. Каждому разбиению переменных х~ задачи на основные (базисные) и неосновные (свободные) соответствует базисное решение (см. гл. 2) и, как следствие, заполнение таблицы поставок, которое также назовем базисным. Иными словами, распределение поставок называется базисным, если переменные, соответствующие заполненным клеткам, можно принять за основные переменные. Клетки, отвечающие базисным переменным, в дальнейшем будем называть базисными, а клетки, соответствующие свободным переменным, — свободными, или пустыми. Поскольку в дальнейшем мы используем исключительно базисные распределения поставок, то термины «базисная клетка» и «заполненная клетка» будут считаться равнозначными.

Подобно тому как это было в симплексном методе, в распределительном методе решения транспортной задачи будем переходить от одного базисного распределения поставок к другому в сторону невозрастания целевой функции вплоть до оптимального решения. Для начала такого движения потребуется исходное базисное распределение поставок — так называемый опорный план.

• [1] Все доказательства при первом чтении могут быть опущены.