Модели транспортной задачи

1. Закрытая модель перевозки однородных грузов.

2. Открытая модель перевозки однородных грузов.

3. Модель перевозки взаимозаменяемых грузов.

4. Задача оптимального назначения.

1. Закрытая модель перевозки однородных грузов:

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

Постановка задачи: Предположим, что есть m пунктов отправления (m поставщиков) и n пунктов потребления.

a_i - запас груза (количество продукта i-того поставщика);

b_j - потребность в грузе j-тому потребителя j = ;

Поставщики и потребители связаны транспортными сетями, для каждого маршрута задана величина:

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

t_ij может быть:

- время доставки груза, тогда цель – минимизация затрат;

- расстояние по соответствующему маршруту, цель – минимизация пробега (в тонно/километрах);

- стоимостным показателем – тариф перевозки единицы груза в соответствующем маршруте.

Цель – выбрать наилучший маршрут перевозки и количество перевозимого по нему груза с целью минимума суммарных затрат. Закрытая модель перевозки  а_i =  b_j характеризуется тем, что сумма запасов равна сумме потребностей.

Модель 1:  min (1)

, j = (2)

, i = (3)

x_ij  0 (4)

переменных m  n, ограничений m + n

Условие закрытости модели: (5)

В системе ограничений коэффициенты при переменных равны единице. Если b_j и a_i – целые числа, то переменные тоже будут целыми числами.

Ранг r  m + n - 1 количество линейно не зависимых ограничений на 1 меньше, чем общее количество ограничений. Количество не нулевых значений переменных х_ij > 0, равно рангу

х_ij > 0 = r.

4 поставщика, 5 потребителей: 20 переменных; реальных поставок будет 8. Также в эту модель можно включать затраты на производство единицы продукции с_ij = t_ij + s_i, где – суммарные затраты, с учетом минимальных затрат на транспортировку (t_ij) и производство (s_i).

Для закрытой модели решение будет такое же (см. выше).

Целевая функция изменится

2. Открытая модель перевозки однородных грузов:

Модель 2:

 min (1)

, j = (2)

, i = (3)

x_ij  0

Дополнительный поставщик (m +1): а_m+1 =  b_j -  a_i, стоимость перевозки от условного поставщика равна нулю.

Потребность запасы	b1	b2	…	bn	Условие: bn+1
a1 a2 … аm условие: аm+1	t11 x11 t21 x21 … tm1 xm1 0 xm+1, 1	t12 x12 t22 x22 … tm2 x m2 0 xm+1, 2	… … … … …	t1n x1n t2n x2n … tmn xmn 0 xm+1, n	0 x1, n+1 0 x2, n+1 … 0 xm, n+1

В пунктире столбец – для второго условия

х_{m+1, 1}, x_{m+1, 2}, …, x_{m+1, n} – дополнительные переменные, обозначающие недоставку груза соот-ветствующему потребителю.

Модель 3: