Транспортная задача
.pdf
3.1. Постановка задачи, основные определения |
11 |
|
|
потребители
поставщики
Потреб. |
1 |
… |
j |
|
… |
n |
Запас |
||
Поставщ. |
|
||||||||
|
|
|
|
|
|
|
|
|
|
1 |
c11 |
… |
|
c1j |
… |
c1n |
|
a1 |
|
x11 |
x1j |
|
x1n |
|
|
||||
|
|
|
|
|
|
|
|||
… |
… |
… |
… |
|
… |
… |
|
… |
|
i |
ci1 |
… |
|
cij |
… |
cin |
|
ai |
|
xi1 |
xij |
|
xin |
|
|
||||
|
|
|
|
|
|
|
|||
… |
… |
… |
… |
|
… |
… |
|
… |
|
m |
cm1 |
… |
|
cmj |
… |
cmn |
|
am |
|
xm1 |
xmj |
|
xmn |
|
|
||||
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
m |
n |
|
Спрос |
b1 |
… |
bj |
|
… |
bn |
|
a |
b |
|
|
|
|
|
|
|
i 1 |
j |
1 |
|
|
|
|
|
|
|
|
|
|
стоимость доставки единицы груза от i-го поставщика к j-ому потребителю
3.1. Постановка задачи, основные определения |
12 |
|
|
Стоимость перевозок можно выразить так
C = c11x11 + … + cijxij + … + cmnxmn → min
или более компактно
m |
n |
|
C |
cij x ij |
min |
i 1 |
j 1 |
|
это целевая функция, которая позволяет определить численное значение критерия оптимальности на всех этапах расчетов и в оптимальном плане
3.1. Постановка задачи, основные определения |
13 |
|
|
Необходимо найти минимальное значение целевой функции при следующих возможных условиях:
1 условие. Вывоз всего груза от каждого поставщика:
x 11 |
... |
x ij |
... |
x 1n |
a 1 |
... |
... |
... |
... |
... |
... |
x i1 |
... |
x ij |
... |
x in |
a i |
... |
... |
... |
... |
... |
... |
x m1 |
... |
x mj |
... |
x mn |
a m |
|
|
|
или |
|
|
n
x ij |
a i где i = 1 … m |
j 1
3.1. Постановка задачи, основные определения |
14 |
|
|
Необходимо найти минимальное значение целевой функции при следующих возможных условиях:
2 условие. Удовлетворение спроса каждого потребителя:
x 11 |
... |
x i1 |
... |
x m1 |
b1 |
... |
... |
... |
... |
... |
... |
x 1j |
... |
x ij |
... |
x mj |
b j |
... |
... |
... |
... |
... |
... |
x 1n |
... |
x 1n |
... |
x mn |
bn |
|
|
|
или |
|
|
m
x ij |
b j |
где j = 1 … m |
i 1
3.1. Постановка задачи, основные определения |
15 |
|
|
Необходимо найти минимальное значение целевой функции при следующих возможных условиях:
3 условие. Равенство запаса и спроса:
a1 |
... ai |
... am |
b1 |
... b j |
... bn |
||
|
|
|
или |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m |
n |
|
|
|
|
|
|
|
a i |
|
b j |
|
|
|
|
i |
1 |
j |
1 |
|
|
|
|
|
|
|
|
|
|
Равенство запаса и спроса есть необходимое и достаточное условие совместимости и, следовательно, разрешимости транспортной задачи.
3.2. Закрытая и открытая транспортная задача |
16 |
Закрытая модель транспортной задачи
Спрос равен запасу
m |
n |
a i |
b j |
i 1 |
j 1 |
Открытая модель транспортной задачи
Спрос не равен запасу
m |
n |
a i |
b j |
i 1 |
j 1 |
3.2. Закрытая и открытая транспортная задача |
17 |
Модель закрытой транспортной задачи
m |
n |
|
C |
cij x ij |
min |
i 1 j 1
При ограничениях:
n
x
i 1 m
x
i 1
ij |
a i , i 1, m |
ij |
b j , j 1, n |
x ij 
0
3.2. Закрытая и открытая транспортная задача |
18 |
Открытая модель транспортной задачи
1. Запас превышает |
m |
n |
|
a i |
b j |
||
спрос |
|||
i 1 |
j 1 |
||
|
2. Спрос превышает |
m |
n |
|
a i |
b j |
||
запас |
|||
i 1 |
j 1 |
||
|
3.2. Закрытая и открытая транспортная задача |
19 |
1. Запас превышает спрос
C
При ограничениях:
если
n
x ij |
a i |
i 1
m
x ij |
b j |
i 1
m n
cij x ij |
min |
i 1 j 1
m n
a i |
b j |
i 1 |
j 1 |
Не требуется весь имеющийся груз вывозить от поставщика, после удовлетворения спроса часть его
может остаться не вывезенной
Потребности (спрос) каждого
потребителя необходимо удовлетворить полностью
x ij 
0
3.2. Закрытая и открытая транспортная задача |
20 |
1. Запас превышает спрос
Решение
m |
n |
|
|
|
a i |
|
b j |
bn 1 |
|
i 1 |
j |
1 |
|
|
|
|
|
|
|
cn |
|
0 |
Фиктивный |
|
1 |
потребитель |
|||
При введении фиктивного потребителя
открытая модель преобразуется в закрытую