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

Пусть имеется m (i=1;т) поставщиков, располагающих некоторым однородным продуктом в объемах по а_i единиц, и n получателей с объемами потребления по b_j единиц. Задана матрица C=|с_ij|, где с_ij — стоимость перевозки единицы продукции от i-го поставщика j-му потребителю. Возникает задача определения плана перевозок X=| x_ij |, где x_ij — количество единиц продукции, поставляемой по коммуникации ij. Целевой функцией можно считать суммарную стоимость всех перевозок.

Условия задачи в табличном виде выглядят следующим образом:

	b1	b2	...	bj	...	bn
a1	x11 c11	x12 c12	...	x1j c1j	...	x1n c1n
a2	x21 c21	x22 c22	...	x2j c2j	...	x2n c2n
...	...	...	...	...	...	...
ai	xi1 ci1	xi2 ci2	...	xij cij	...	xin cin
...	...	...	...	...	...	...
am	xm1 cm1	xm2 cm2	...	xmj cmj	...	xmn cmn

Если (1)

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

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

Функция цели — минимизация суммарных затрат на перевозку продукции

. (2)

при ограничениях:

1) на запасы продукции у поставщиков

(3)

2) на запросы потребителей, которые должны быть полностью удовлетворены,

(4)

3) условия неотрицательности, исключающие обратные перевозки:

. (5)

Матрицу X=| x_ij|, удовлетворяющую ограничениям, называют допустимым планом перевозок, а переменные x_ij — допустимыми перевозками.

Графический способ задания условий задачи

Допустимый план Х, доставляющий целевой функции минимальное значение именуется оптимальным; С=|| с_ij || называется матрицей тарифов или матрицей транспортных издержек. Отрезок или линия, соединяющая i-го поставщика с j-м потребителем, называется коммуникацией и обозначается (ij) или (A_iB_j). Если на всех коммуникациях (ij) проставлены величины перевозок х_ij, то получается транспортная сеть.

Если условие не выполняется, то модель транспортной задачи называется открытой. В случае, если запасы поставщиков больше потребностей получателей, вводят n+1–гo фиктивного потребителя, запросы которого равны излишкам запаса, т. е.

.

Тарифы C_i;n+1 считают равными нулю. Получим расширенную закрытую задачу. Ее оптимальный план даст оптимальный план исходной задачи. Поставки х_i;n+1 в оптимальном плане расширенной задачи покажут остатки продукции на складах поставщиков.

Если потребности превышают запасы, то вводят m+1-ro фиктивного поставщика. Его запасы считают равными недостающей продукции:

.

Тарифы с_m+1;j равны некоторому большому положительному числу М. В расширенной задаче получим баланс потребностей и запасов. Поставки x_m+1;j в оптимальном плане расширенной задачи покажут объемы недостачи продукции.

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