Транспортная задача с избытком

Через конечное число шагов приходят к искомому оптимальному базисному  решению. [2]

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

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

1.   Распределительный метод. При этом методе для каждой пустой клетки строят цикл и для каждого цикла непосредственно вычисляют алгебраическую сумму тарифов.

2.   Метод потенциалов. При этом методе предварительно находят потенциалы баз и потребителей, а затем вычисляют для каждой пустой клетки алгебраическую сумму тарифов с помощью потенциалов. [4]

2.4 Математическая модель

 

Переменными (неизвестными) транспортной задачи являются x_ij ..,i-(=1,2, ..., k), j= 1,2, ..., n — объемы перевозок от каждого i -го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок:  
  
или

	a 1	a2	…	an
b 1	x 11	x 12		x 1n
b 2	x 21	…		x 2n
…	…	…	…	…
bk	x k1	…	…	x kn

 

 

 

 

 

 

 

Так как произведение c_ijx_ij . определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны  . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция задачи имеет вид:

Система ограничений задачи состоит из двух групп уравнений. Первая группа из k уравнений описывает тот факт, что запасы всех kпоставщиков вывозятся полностью:

Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех nпотребителей:  
  
Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:  
  
  
  
  
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.  
  
Такая задача называется задачей с правильным балансом, а ее модель — закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой.  
Математическая формулировка транспортной задачи такова: найти переменные X =(x_ij ) задачи удовлетворяющие системе ограничений:  
  
условиям неотрицательности  и обеспечивающие минимум целевой функции.  
  
Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу A системы уравнений-ограничений задачи.

 
Сверху над каждым столбцом матрицы  указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы  ограничений. Каждый столбец матрицыA, соответствующий переменной х_ij.., является вектором-условием задачи и обозначается через A_ij. Каждый вектор имеет всего k+ nкоординат, и только две из них, отличные от нуля, равны единице. Первая единица вектора A_ij стоит на i-м месте, а вторая - на (k+j)-м  месте, т.е.

Таким образом в векторной  форме задача будет выглядеть  так:  
 [11]

 

2.5 Открытая и закрытая транспортная задача

 

Для решения транспортной задачи разработано несколько методов, каждый из которых отличается от другого  методом заполнения матрицы перевозок. 
          Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. [5]

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

Различают два типа транспортных задач: но критерию стоимости (план перевозок  оптимален, если достигнут минимум  затрат на его реализацию) и по критерию времени (план оптимален, если на его  реализацию затрачивается минимум  времени).

Обозначим количество груза, имеющегося на каждой из баз (запасы), соответственно ,а общее количество имеющегося в наличии груза– :

;

заказы каждого из потребителей (потребности) обозначим соответственно , а общее количество потребностей – :

,

Тогда при условии

- мы имеем закрытую модель, а при условии

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

Очевидно, в случае закрытой модели весь имеющийся в наличии  груз развозится полностью, и все  потребности заказчиков полностью  удовлетворены; в случае же открытой модели либо все заказчики удовлетворены  и при этом на некоторых базах  остаются излишки груза  , либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены .

Так же существуют одноэтапные  модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный  пункт”, например – склад.

План перевозок с указанием  запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:

Пункты Отправления	Пункты назначения				Запасы
			…
			…
			…
…	…	…	…	…	…
			…
Потребности			…		или

 

Условие или означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное означает количество груза, перевозимого с базы потребителю : совокупность этих величин образует матрицу (матрицу перевозок).

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

Совокупность тарифов  также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:

 

 

 

 

 

 

 

Пункты Отправления	Пункты назначения									Запасы
						…
						…
						…
…	…			…		…	…			…
						…
Потребности						…				или

 

Сумма всех затрат, т. е. стоимость  реализации данного плана перевозок, является линейной функцией переменных :

  [7]

 

 

 

2.6 Незамкнутая транспортная задача с избытком

В случае выполнения (1.4) (открытая модель) баланс транспортной задачи может  нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах  отправления превышает сумму  поданных заявок (транспортная задача  с избытком запасов):

å аi > å bj ( где i=1,...,m ; j=1,...,n );

          2. Сумма поданных заявок превышает наличные запасы (транспортная задача с избытком заявок):

                å аi < å bj ( где i=1,...,m ; j=1,...,n );

Рассмотрим последовательно  эти два случая:

2.6.1 Транспортная задача с избытком запасов.

Сведем её к ранее рассмотренной  транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов  назначения В1, B2, ... , Bn, введём ещё один, фиктивный, пункт назначения Bn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

bn+1 = å аi - å bj ( где i=1,...,m ; j=1,...,n ) ,

а стоимость перевозок  из всех пунктов отправления в  фиктивный пункт назначения bn+1 будем  считать равной нулю. Введением фиктивного пункта назначения B n+1 с его заявкой b n+1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как  обычную транспортную задачу с правильным балансом. [8]

2.6.2 Транспортная задача с избытком заявок

Эту задачу можно свести к обычной транспортной задаче с  правильным балансом, если ввести фиктивный  пункт отправления Am+1 с запасом am+1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю. [9]

2.6.3 Пример: транспортная задача линейного программирования.

На складах №1, №2, №3 имеются  запасы продукции в количествах 90, 400 и 110 тонн соответственно. Продукцию необходимо доставить к потребителям П1, П2, П3, заявки которых составляют 140, 300 и 160 тонн. Склады и потребители расположены в различных районах города, поэтому расстояния между каждой парой из них различно. Соответственно транспортные расходы по перевозке товара с i-го склада к j-му потребителю также различны. Стоимость доставки единицы товара (одной тонны) от каждого склада к каждому потребителю в условных денежных единицах (у.д.е.) известна и представлена в табл.1.1.

Таблица 1.1.

Склады	Потребители
	П1	П2	П3
Склад№1	2	5	2
Склад№2	4	1	5
Склад №3	3	6	8

Требуется составить план перевозок – определить количество груза x ij , которое должно быть вывезено из каждого i-го склада и доставлено к каждому j-му потребителю. При этом, с одной стороны, должна быть обеспечена доставка грузов всем потребителям в соответствии с их заявками, а с другой стороны, весь товар должен быть полностьювывезен со складов. План перевозок должен быть таким, чтобы совокупная стоимость транспортных издержек была минимальной.