Вопрос 3. Методы решения транспортных задач

Пример 1.

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

Таблица 2

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

Рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть оправлено от каждого поставщика каждому потребителю с минимальными транспортными издержками.

Решение. Построим экономико-математическую модель. Искомый объем перевози от i-го поставщика к j-му потребителю обозначим через и назовем - поставкой клетки(i,j). (например, искомый объем перевозки от 1-го поставщика ко 2-му потребителю или поставка клетки (1;2))

Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных .

Например, объем груза забираемого от 1-го поставщика, должен быть равен его мощности – 60 единицам, т.е. (уравнение баланса по первой строке), т.о. чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнение баланса для каждой строки таблицы поставок, т.е.

(7)

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

(8)

Объем перевозимого груза не может быть отрицателен (i=1,2,3; j=1,2,3,4)

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

(9)

Математическая формулировка: На множестве не отрицательных решений системы ограничений (7) и (8) найти такое решение ,при котором линейная функция (9) примет минимальное значение.

Для математической формулировки транспортной задачи обозначим через -коэффициенты затрат, - мощности поставщиков, через -мощности потребителей, где i=1,2,…,m; j=1,2,….n, где m-число поставщиков, n-число потребителей. Тогда система ограничений примет вид:

, i=1,2…,m (10)

,j=1,2,…,n (11)

Система (10) включает в себя уравнение баланса по строкам, а система (11)- по столбцам поставок. Линейная функция в данном случае:

(12)

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

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

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

- такая задача называется закрытой (13)

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

Рассмотрим закрытую задачу. Решение осуществляется по шагам и каждому шагу соответствует разбиение переменных на базисные и свободные.

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

Теорема. Ранг – r- системы уравнений (10) и (11) при условии (13) равен m+n-1. (Доказательство см. «Исследования операций в экономике» под ред. Н. Ш. Кремера, стр. 126-128).

Основное следствие теорем: - число –r- базисных переменных закрытой транспортной задачи равно m+n-1, где m- число поставщиков, n- число потребителей.

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

Клетки, отвечающие базисным переменным будем называть базисными, а клетки соответствующие свободным переменным – свободными. Поскольку в дальнейшем мы используем исключительно базисные распределения поставок, то термин «базисная клетка» и заполненная клетка будут считаться равнозначными.

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