Главная | Обратная связь

Транспортная задача

Постановка задачи.Имеются m пунктов отправления А₁, А₂, ... А_m на которых сосредоточено определенное количество однородного продуктаа₁, а₂, ... а_m.Имеются n пунктов потребления В₁,В₂,...,В_n,в которые необходимо перевезти следующее количество продуктов в₁,в₂,...в_n.Если общая сумма продукта в пунктах отправления равна общей потребности в нем всех пунктов потребления

а₁+ а₂+ ...+ а_m = в₁+в₂+...+в_n

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

Из каждого пункта отправления возможна транспортировка продукта в любой пункт потребления, причем стоимость перевозок единицы груза из i -го пункта отправления в j-й пункт потребленияС_ij известна.

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

За неизвестные здесь принимаются перевозимые объемы груза. Обозначим

через Х₁₁ количество продукта, отправляемого из пункта А₁ в пункт В₁, Х₁₂ -из пункта А₁ в пункт В₂и т.д. Вообще через Х_ij обозначим количество продукта, отправляемого из i-го пункта отправления в j-й пункт потребления. Тогда количество неизвестных будет mxn неотрицательных переменных величин.

Запишем математическую модель транспортной задачи. Требуется найти такое неотрицательное решение системы из m+n уравненй

 

при котором линейная форма достигает минимума

 

F=С₁₁Х₁₁+С₁₂Х₁₂+...+С_1nX_1n+...+ C_m1X_m1+C_m2X_m2+...+ C_mnX_mn

Все условия задачи можно свести в таблицу 5. При моделировании экономических процессов для решения транспортных задач:

1) все ограничения должны иметь одинаковую размерность- тонны, тонны-километры и т.д.,

2)оценки целевой строки по всем неизвестным должны соизмеряться с неизвестными величинами. Например, если Х выражены в тоннах то С- стоимость транспортных затрат за одну тонну.

Таблица 5

B A	В1	В2 ...	Вn	Запасы в пунктах отправления
А1 А2 .. : Аm	С11 Х11 С21 Х21 ... Cm1 Xm1	С12 Х12 ... С22 ... Х22 ... ... Cm2 ... Xm2	C1n Х1n C2n Х2n ... Cmn Xmn	a1 a2 ... am
Потребность	b1	b2	bn	ai=bj

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

_{m n}

F= е еC_ijX_ij

^{i=1 j=1}

приусловиях

_n

еX_ij=a_i i=1,2,...,m

^j=1

_m

еX_ij=b_j j=1,2,...,n

ⁱ⁼¹

X_ij>=0

Транспортная задача также состоит из трех частей: цель задачи, ограничения и условия неотрицаительности.

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

е a_i = еb_j

В случае превышения запаса над потребностью, вводится фиктивный (п+1) пункт назначения с потребностью в_п+1 = а_i-b_j и при этом транспортные расходы равны нулю с_n+1=0.

Если потребности больше чем запасы то вводится фиктивный m+1 пункт отправления с запасом груза а_m+1= b_j-a_i , здесь также тарифы расхода равны нулю с_m+1j=0 .