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

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

В m пунктах отправления А1,А2,…,Аm имеется однородный груз в количествах а1,а2,…,аm. Этот груз необходимо отправить в n пункты потребления В1,В2,…,Вn,спрос, которого составляет b1,b1,…,bn. Задано: Сij-транспортные затраты на перевозку единицы груза и из пункта Аi в пункт Вj (i=1,m; j=1,n). Определить такой план перевозок при котором весь груз из пунктов отправления будет выведен, спрос всех потребителей удовлетворен и при этом суммарные транспортные задачи будут минимальными. Матем.модель. Введем переменные: Хij- объем груза из Аi→ Вj (i=1,m; j=1,n).

X= план перевозок

Всю данную информацию поместим в распределительную таблицу:

Ai/Bj	B1	B2	…	Bn
A1	C11 x11	C12 x12	…	C1n x1n
A2	C21 x21	C22 x22	…	C2n x2n
…	…	…	…	…
An	Cm1 xm1	Cm2 xm2		Cmn xmn

Целевая функция:

2. L(x)=C₁₁X₁₁+C₁₂X₁₂+…+C_1nX_1n+C₂₁X₂₁+C₂₂X₂₂+...+ +C_2nX_2n+….+C_m1X_m1+ +C_m2X_m2+...+C_mnX_mn→min

_{m n}

L(x)=∑∑CijXij→min ^{i=1 j=1} _n

Ограничение 1: ∑Xij=ai, i=1,m x₁₁+x₁₂+..+x_1n=a₁ (←eto sistema) (2) ^j=1 x₂₁+x₂₁+..+x_2n=a₂ …………………….

x_m1+x_m2+..+x_mn=a_n

Условие, что все поставщики должны быть полностью разгружены Ограничение 2 _m x₁₁+x₁₂+..+x_m1=b₁ (←eto sistema) (3) ∑Xij=bj, j=1,n x₂₁+x₂₁+..+x_m2=b₂ ⁱ⁼¹ …………………….

x_1n+x_2n+..+x_mn=b_n

Условие,что спрос всех потребителей удовлетворен Ограничение 3: (4) Xij≥0 i=1,m j=1,n Перевозки только в одном направлении (из Ai→Bj) (i=1,m; j=1,n).

Ограничения (2) и (3) в векторном виде:

(5) P₁₁X₁₁+P₁₂X₁₂+...+P_1nX_1n+P₂₁X₂₁+P₂₂X₂₂+…+P_2nX_2n+…+P_m1X_m1+P_m2X_m2+…+P_mnX_mn=P₀

P11= , P12= ,…, P0=

12. Основные понятия и определения транспортной задачи. Определения плана, опорного плана, невырожденного плана, оптимального плана

Определение1. Всякое неотрицательное решение систем:

(2)и (3)

Определяемое матрицей Х=||X_ij||_mxn Называется планом транспортной задачи.

Определение2

План Х=||X_ij||_mxn называется опорным, если векторы Р_ij входящие в разложение P11x11+p12x12+…+p1nx1n+p21x21+p22x22+…+p2nx2n+…+pm1xm1+pm2[m2+…+pmnxmn=p0

P11= , P12= , P0=

С ненулевым коэффициентом-линейно-независимые

Определение3

Опорный план Х=||X_ij||_mxn называется невырожденным,если он содержит ровно m+n-1 ненулевых элементов.

Определение 4. План Х=||X_ij||_mxn при котором целевая ф-ия f(x)=c11x11+c12x12+…+c1nx1n+c21х21+…+с2nx2n+…+cm1xm1+cm2xm2+…+cmnxmn----min достигает минимального значения, называется оптимальным.

Основные свойства модели транспортной задачи:

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

Теорема 2. Ранг матрицы системы ограничений (2)и (3) на единицу меньше числа ограничений r(A)=m+n-1. Ранг матрицы- наивысший порядок отличенного от нуля минора(определитель)

Критерий оптимального опорного плана

f(x)= ,

спрос полностью удовлетворен. хij≥0. I меняется от 1 до m

Каждому пункту отправления Ai=Ui, i=1n, а каждому пункту потребленияBj=Vj, j=1m эти величины таковы, что выполняется условие: cij+uij-vij=0, dlya Xij>0.

Х=||X_ij||_mxn- план перевозок.

Cij`=cij+uij-vij. C`=||c`ij||mxn-оценочная матрица опорного плана Х=||X_ij||_mxn. Ui, vj- потенциалы.

Теорема критерия оптимальности.

Для того, чтобы план Х=||X_ij||_mxn был оптимальным необх-мо и дост-но,чтобы все элементы оценочной матрицы были положительными, т.е должны выполняться след-е условия.

cij+uij-vij≥0, для xij=0

cij+uij-vij=0, для xij>-0