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

Транспортной задачи.

Постановка задачи. Математическая модель

Лекция. Транспортная задача

Постановка задачи:

Однородный груз сосредоточен у m поставщиков в объемах а₁, а₂, …, а_m.

Данный груз необходимо доставить n потребителям в объемах, b₁, b₂, …, b_n.

Известен С_ij (i= 1, 2, …, m; j=1, 2,…, n) – стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю.

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

Исходные данные транспортной задачи записываются в таблице вида:

bj аi	b1	b2	…	bn
А1	С11	С12	…	С1n
А2	С21	С22	…	С2n
…	…	…	…	…
аm	Cm1	Cm2	...	Cmn

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

Математическая модель транспортной задачи в общем виде имеет вид:

Целевая функция задачи Z(X) выражает требование обеспечить минимум суммарных затрат на перевозку всех грузов. Вторая группа из уравнений ограничений записанных в общем виде, выражает требование, что запасы всех m, поставщиков вывозятся полностью, а также полностью должны удовлетворятся запросы всех n потребителей. Последнее неравенство является условием неотрицательности всех переменных.

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

такая задача называется сбалансированной, а её модель закрытой. Если же это равенство не выполняется, то задача называется несбалансированной (с неправильным балансом), а её модель – открытой.

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

Математическая модель двойственной задачи:

если целевая функция Z’ стремится к минимуму то в системе ограничении меняется знак: экономический смысл перемененных двойственной задачи:

U_i – условная оценка i-го поставщика (условная плата поставщика перевозчику);

V_j – условная оценка j-го потребителя (условная плата потребителя перевозчику).

U_i, V_j – называются потенциалами.

Определения:

1) Если задача открыта, то необходимо добавить фиктивного поставщика или потребителя с недостающим объемом поставки и нулевой стоимостью перевозки. Распределение поставки фиктивному потребителю (поставщику), идет в последнюю очередь.

2) Клетка в плане перевозок называется базисной (закрытой), если в нее ставится перевозка.

3) Количество базисных клеток определяется соотношением r=m+n-1. опорное решение не может иметь базисных клеток больше, чем r.

4) План называется вырожденным, если количество базисных клеток меньше r, т.е. базисных клеток не хватает при выполненном условии, что объем поставок поставщиков распределен полностью и спрос потребителей также удовлетворен. В этом случае необходимо добавить нулевую перевозку.

5) Если в задаче указана не только стоимость перевозки, но и стоимость производства товара, тогда необходимо сложить эти стоимости с учетом перевозки товара от i-го поставщика j-му потребителю. Кроме того, математическая модель составляется с учетом этой суммарной стоимости.

Дата добавления: 2015-06-27