Материал: Математические методы и модели в экономике. Амелин С.В

Тема 5. ТРАНСПОРТНАЯ ЗАДАЧА

В результате изучения данной темы студенты должны: знать:

-область применения транспортных задач в экономике;

-математическую постановку транспортной задачи;

-методы решения транспортных задач;

уметь:

-решать открытые и закрытые транспортные задачи;

-применять транспортные модели при решении практических задач;

владеть:

-математическим аппаратом решения транспортных

задач;

-практическими навыками построения и решения транспортных задач, в том числе, с использованием ЭВМ.

Математическая постановка задачи состоит в определении оптимального плана перевозок некоторого груза из m пунктов отправления A1, A2, …, Am в n пунктов назначения B1, B2, …, Bn. При этом в качестве критерия оптимальности обычно выбирается либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

Обозначим через Cij стоимость перевозки единицы груза из i–го пункта отправления в j–й пункт назначения; аi - запасы груза в i–м пункте отправления (величина предложения); bj - потребности в этом грузе в j–м пункте назначения (величина спроса); Xij - объем перевозок (количество перемещаемых единиц груза) из i–го пункта отправления в j–й пункт назначения. Тогда математическая модель транспортной задачи имеет следующий вид: определить минимум целевой функции

115

при выполнении следующих ограничений:

Обычно исходные данные транспортной задачи представляются в виде таблицы. Внутренняя часть этой таблицы является объединением двух матриц: матрицы перевозок Х = { Xij } и матрицы стоимостей С = { Сij }:

116

Если общий запас груза у поставщиков равен потребности в грузе у потребителей, т.е. если выполняется условие

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

Определение 1. Всякое неотрицательное решение систем линейных уравнений (5.2) и (5.3), определяемое матри-

цей Х = { Xij }; i = 1, m ; j = 1, n , называется планом транспорт-

ной задачи.

Определение 2. План Х* = {Xij*}, при котором функция цели 1 принимает минимальное значение, называется оптимальным планом транспортной задачи.

Ограничения (5.2) и (5.3) транспортной задачи представляют собой две группы уравнений. Первая из них, т.е. система уравнений (5.2), означает то, что сумма перевозок по каждой строке таблицы должна быть равна соответствующему запасу аi. Каждое уравнение второй системы (5.3) означает то, что сумма перевозок по каждому столбцу таблицы должна быть равна соответствующей потребности bj. Транспортная задача представляет собой задачу линейного программирования, записанную в каноническом виде. Следовательно, ее можно решать симплексным методом. Однако для решения транспортных задач существуют специальные методы.

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

1.Закрытая транспортная задача всегда совместна, обладает планом, т.е. имеет решение.

2.Если значения и аi-е и bj-е – целые и неотрицательные, то транспортная задача имеет целочисленное решение.

3.Клетки таблицы транспортной задачи с координатами, в которых проставлены значения перевозок, называются базисными и соответствуют базисным переменным, а остальные клетки остаются свободными. Для невырожденного

117

опорного плана в таблице транспортной задачи будет заполнена положительными числами m + n – 1 клетка. Если же опорный план задачи вырожден, то часть базисных клеток будет заполнена нулями.

Нахождение первоначального опорного плана

Для определения первоначального опорного плана существуют несколько различных методов. Это – метод северозападного угла, метод минимального элемента, или минимальной стоимости, и другие.

Метод северо-западного угла. Пусть условие транс-

портной задачи задано в следующей таблице.

Поскольку сумма запасов (предложения) равна сумме потребностей (спроса) – имеем задачу закрытого типа.

Матрицу перевозок начинаем заполнять с левого верхнего (северо-западного) угла, с клетки (1,1). Для этого сравниваем два значения а1 = 30 и b1= 20, т.е. попытаемся удовлетворить потребность первого пункта назначения за счет запасов первого пункта отправления. Запасы пункта А1 больше потребности пункта В1, следовательно, в качестве значения Х11 выбираем меньшее число – b1 и запишем это число в соответствующей клетке таблицы. Таким образом, потребность пункта В1 в грузе удовлетворена, и поэтому все остальные числа этого столбца (Х21, Х31, Х41) считаем равными нулю, а соответствующие им клетки оставляем свободными.

118

Получаем новую матрицу из трех столбцов (В2, В3, В4) и че-

b2 = 90 и повторяем алгоритм. Меньшее из этих значений, равное 10, выбираем в качестве Х12 и записываем в клетку (1,2) таблицы. Тогда запас пункта А1 будет полностью исчерпан, следовательно, остальные значения перевозок из первой строки (Х13, Х14) принимаем равными нулю, а соответствующие клетки остаются свободными. Продолжая заполнять таблицу, таким образом дойдем до клетки (4,4). Построенный план является опорным. В рассматриваемой задаче число пунктов отправления m = 4 и число пунктов назначения n = 4, следовательно, невырожденный план задачи определяется числами, стоящими в m+n–1 = 4+4–1 = 7 заполненных клетках.

Запишем первоначальный опорный план в виде матри-

цы Х:

119