Транспортная задача
.pdf3.2. Закрытая и открытая транспортная задача |
21 |
2. Спрос превышает запас
m |
n |
|
|
C |
|
cij x ij |
min |
i 1 |
j |
1 |
|
При ограничениях: |
|
|
|
m |
|
n |
|
если |
|
|
a i |
b j |
|||
|
i |
1 |
|
|
|
j |
1 |
|
|
|
|
|
|
||||
|
n |
|
|
|
|
|
|
|
|
x ij |
a i , i |
|
1, m |
|
|||
i |
1 |
|
|
|
|
|
|
|
m |
|
|
|
|
|
|
|
|
|
x ij |
b j , |
j |
|
1, n |
|
||
i |
1 |
|
|
|
|
|
|
|
x ij 0
3.2. Закрытая и открытая транспортная задача |
22 |
2. Спрос превышает запас
Решение
n |
m |
|
b j |
a i |
a m 1 |
j 1 |
i 1 |
|
|
|
|
Фиктивный
поставщик
3.3. Метод северо-западного угла |
23 |
«Метод северо-западного угла» на примере:
Пример:
С 3-х баз требуется доставить в магазины однородный товар. Пусть на базе А1 имеется 50 единиц груза, на базе А2
– 40 единиц, на базе А3 – 20 единиц. Указанный товар нужно отгрузить 4-м потребителям: В1, В2, В3, В4, потребности которых составляют соответственно 35, 25, 30, 25 единиц товара. Стоимость перевозки от базы до потребителей представлена в таблице:
|
В1 |
В2 |
В3 |
В4 |
|
|
|
|
|
А1 |
3 |
2 |
4 |
6 |
|
|
|
|
|
А2 |
2 |
3 |
1 |
2 |
|
|
|
|
|
А3 |
3 |
2 |
7 |
4 |
|
|
|
|
|
Требуется составить такой план перевозок, который обеспечит минимальные транспортные расходы.
3.3. Метод северо-западного угла |
24 |
Решение:
1 этап. Составление распределительной таблицы
|
В1 |
В2 |
В3 |
В4 |
Наличие |
|
|
|
|
|
товара |
|
|
|
|
|
|
А1 |
3 |
2 |
4 |
6 |
50 |
|
|
|
|
|
|
А2 |
2 |
3 |
1 |
2 |
40 |
|
|
|
|
|
|
А3 |
3 |
2 |
7 |
4 |
20 |
|
|
|
|
|
|
Потребность |
30 |
25 |
30 |
25 |
110 |
в товаре |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3.3. Метод северо-западного угла |
25 |
Решение:
2 этап. Составление модели
Целевая функция (стоимость всей перевозки):
C 3x11 2 x12 4 x13 6 x14 2 x21 3x22 x23 2 x24 3x31 2 x32 7 x33 4 x34 min
Проверяем задачу на разрешимость: |
3 |
4 |
|
|
|
||
|
|
ai |
b j |
|
|
i 1 |
j 1 |
3 |
4 |
|
|
ai 50 40 20 110 , |
b j |
30 25 30 25 110 |
i 1 |
j 1 |
|
Ограничения по поставкам |
Ограничения по потребителям |
|
x11 + x12 + x13 + x14 = 50 |
|
x11 + x21 + x31 = 30 |
x21 + x22 + x23 + x 24 = 40 |
|
x12 + x22 + x32 = 25 |
x31 + x32 + x33 + x34 = 20 |
|
x13 + x23 + x33 = 30 |
x14+ x24 + x34 = 25
xij |
0, i 1,3, j 1,4 |
3.3. Метод северо-западного угла |
26 |
Условимся:
1.Построение опорных решений системы, а также преобразования этих решений будут производиться в таблицах.
2.Если базисное неизвестное xij = a, то это число записывается в соответствующей клетке (i, j), и эта клетка называется загруженной, если же переменная не базисная, то xij = 0 и соответствующая клетка остается свободной
3.3. Метод северо-западного угла |
27 |
3 этап. Составление плана
Метод северо-западного угла заключается в том, что заполнение таблицы начинают с левого верхнего угла, двигаясь далее по строке вправо или по столбцу вниз.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Наличие |
|
|
|
|
|
В1 |
|
|
|
|
В2 |
|
|
В3 |
В4 |
|
товара |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
min (25, 20) = 20 |
|
|
|
|
|
|
|
||||||
min (50, 30) = 30 |
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
50-30 = 20 |
|||||||||||
|
|
3 |
|
|
4 |
|
6 |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|||
|
А1 |
30 |
|
|
20 |
|
|
|
|
|
|
50 |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А2 |
|
|
|
2 |
|
|
|
|
3 |
|
|
|
|
1 |
|
2 |
40 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А3 |
|
|
|
3 |
|
|
|
|
2 |
|
|
|
|
7 |
|
4 |
20 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потреб |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ность в |
30 |
|
|
|
|
25 |
|
|
30 |
25 |
110 |
||||||||
|
товаре |
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30-30 = 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
25 - 20 = 5 |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3.3. Метод северо-западного угла |
28 |
Метод северо-западного угла заключается в том, что заполнение таблицы начинают с левого верхнего угла, двигаясь далее по строке вправо или по столбцу вниз.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Наличие |
|
|
|
В1 |
|
|
В2 |
|
|
|
В3 |
В4 |
товара |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А1 |
30 |
|
3 |
20 |
|
2 |
|
|
|
4 |
|
6 |
50 |
|||
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
min (5, 40) = 5 |
3 |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|||||||
А2 |
|
|
|
2 |
|
|
|
|
|
|
1 |
|
2 |
40 |
||
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А3 |
|
|
|
3 |
|
|
|
2 |
|
|
|
7 |
|
4 |
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потреб |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ность в |
30 |
|
25 |
|
|
|
30 |
25 |
110 |
|||||||
товаре |
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30-30 = 0 |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
25 - 20 = 5 |
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3.3. Метод северо-западного угла |
29 |
Метод северо-западного угла заключается в том, что заполнение таблицы начинают с левого верхнего угла, двигаясь далее по строке вправо или по столбцу вниз.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Наличие |
|
|
|
|
|
В1 |
|
|
В2 |
|
|
|
|
В3 |
|
В4 |
товара |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А1 |
30 |
|
3 |
20 |
|
2 |
|
|
|
|
4 |
|
|
|
6 |
50 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
min (30, 35) = 30 |
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
min (5, 40) = 5 |
3 |
|
|
|
|
|
40-5 = 35 |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
А2 |
|
|
|
2 |
|
|
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
||
|
|
|
|
5 |
|
|
|
|
|
30 |
|
|
|
|
|
|
40 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А3 |
|
|
|
3 |
|
|
|
2 |
|
|
|
|
7 |
|
|
|
4 |
20 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потреб |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ность в |
30 |
|
25 |
|
|
|
30 |
|
25 |
110 |
|
||||||||||
товаре |
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30-30 = 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
5 - 5 = 0 |
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3.3. Метод северо-западного угла |
30 |
Метод северо-западного угла заключается в том, что заполнение таблицы начинают с левого верхнего угла, двигаясь далее по строке вправо или по столбцу вниз.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Наличие |
|
|
|
|
В1 |
|
|
В2 |
|
|
|
В3 |
В4 |
товара |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А1 |
30 |
|
3 |
|
20 |
|
2 |
|
|
|
4 |
|
|
6 |
50 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
min (25, 5) = 5 |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
40-35 = 5 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А2 |
|
|
2 |
|
|
|
3 |
|
|
|
1 |
|
|
2 |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
5 |
|
|
|
30 |
|
|
5 |
|
|
|
40 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А3 |
|
|
3 |
|
|
|
2 |
|
|
|
7 |
|
|
4 |
20 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потреб |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ность в |
30 |
|
|
25 |
|
|
30 |
|
25 |
|
110 |
|
|||||||
товаре |
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30-30 = 0 |
|
|
|
|
|
30 - 30 = 0 |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
5 - 5 = 0 |
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|