Материал: 5462
36
Задачи для самостоятельного решения
Найти оптимальный план перевозок по данным задачи и при дополнительных условиях. Результаты сравнить.
1. ai = (200; 160; 140; 220); b j = (160; 180; 120; 150); 2 3 9 7
С
3 4 6 1
5 1 2 2
4 5 8 1
1)коммуникация (3,4) временно не работает;
2)по маршруту (2,1) необходимо перевезти 50 ед. груза;
3)первый и четвертый пункты отправления должны быть обязательно разгружены.
2. ai = (430; 370; 240; 80); b j = (350; 150; 220; 310);
|
3 |
6 |
5 |
10 |
|
С |
6 |
5 |
7 |
8 |
|
4 |
8 |
3 |
9 |
||
|
|||||
|
8 |
6 |
7 |
5 |
1)коммуникация (1,3) временно не работает;
2)по маршруту (3,3) необходимо привезти 150 ед. груза;
3)обязательно вывезти груз у второго и третьего поставщиков.
3. ai = (35; 47; 55); b j = (23; 48; 15; 20);
|
1 |
1 |
6 |
4 |
С |
4 |
3 |
2 |
7 |
|
3 |
5 |
9 |
4 |
1)по маршруту (1,2) груз перевозить нельзя;
2)по маршруту (2,3) необходимо перевезти не менее 10 ед. груза;
3)обязательно вывезти ресурсы первого и второго поставщиков.
4. ai = (64; 36; 75; 45); b j = (42; 88; 20; 30); 2 4 5 1
С
2 3 9 4
8 4 3 3
5 4 3 4
37
1)груз по маршрутам (1,4) и (2,1) перевозить нельзя;
2)по маршруту (3,3) должно быть перевезено 15 ед. груза;
3)обязательно вывезти ресурсы второго и четвертого поставщиков.
5.ai = (30; 5; 47; 42); b j = (10; 35; 15; 28; 55);
3 7 1 5 4
С
7 5 8 6 3
6 4 8 3 2
3 1 7 4 2
1)коммуникация (3,5) закрыта;
2)по маршруту (3,2) перевезти не менее 20 ед. груза;
3)обязательно удовлетворить второго, третьего и пятого потребителей.
6. ai = (80; 40; 35; 27); b j = (65; 30; 28; 72); 2 4 5 1
С
2 3 9 4
8 4 2 5
3 2 4 7
1)коммуникации (2,4) и (3,1) временно закрыты;
2)по маршруту (1,2) перевезти 15 ед. груза;
3)обязательно удовлетворить потребности первого, второго и третьего потребителей.
7.ai = (54; 46; 50); b j = (45; 75; 30; 35);
|
4 |
3 |
2 |
7 |
С |
1 |
1 |
6 |
4 |
|
3 |
5 |
9 |
4 |
1)груз по маршруту (3,3) перевозить нельзя;
2)по маршруту (1,2) необходимо перевезти не менее 30 ед. груза;
3)обязательно удовлетворить потребности второго и третьего потребителей.
8.ai = (26; 48; 84); b j = (42; 37; 18; 20);
9 3 5 4 С 6 7 8 6 3 8 4 5
1)коммуникация (3,4) временно не работает,
2)по маршруту (2,1) перевезти не менее 30 ед. груза
38
3) необходимо обязательно вывезти груз у первого и второго поставщиков.
9. ai = (37; 15; 46; 40); b j = (18; 32; 45; 25; 55); 7 5 6 3 8
С
6 4 3 2 8
3 4 2 7 3
3 5 4 3 3
1)коммуникации (2,4) и (3,3) временно не работают;
2)по маршруту (3,2) перевезти не менее 25 ед. груза;
3)удовлетворить потребности первого и пятого потребителей.
10. ai = (180; 230; 120; 210); b j = (175; 115; 150; 240); 7 2 2 3
С
6 9 2 8
4 5 2 3
5 4 3 2
1)по маршрутам (1,1) и (3,2) груз перевозить нельзя;
2)по маршруту (2,3) необходимо перевезти не менее 70 ед. груза;
3)первый и четвертый пункты должны быть полностью разгружены.
Глава 4. Транспортные задачи по критерию времени
Необходимость решения таких задач обусловлена аварийными поставками, при перевозках скоропортящегося груза, обеспечении сырьем бесперебойных производств и при других обстоятельствах.
Задача состоит в следующем.
Заданы m поставщиков и n потребителей с известными ресурсами и потребителями и матрица времени доставки груза Т 
tij m n . Для задачи
выполнено условие баланса ai |
b j . Среди множества планов задачи |
ij
Хk найти такой, для которого минимизируется время реализации:
T min Tk .
xk
Алгоритм решения задачи
1.Находим первоначальный план Х1 по методу минимального элемента матрицы Т.
39
2.Перебором определяем наибольшую продолжительность перевозок, включенных в план Х1:
T1 |
max tij . |
|
i, j X1 |
3.Исключаем из рассмотрения клетки с продолжительностью большей
или равной Т1, чтобы не увеличить продолжительность всего комплекса перевозок, находим следующий план Х2, имеющий время реализации Т2. Аналогичным образом находим всевозможные планы перевозок Х к . Продолжительность Т к реализации любого плана Х к , если их производят параллельно, так же, как и для плана Х1:
Tk |
max tij . |
|
i, j X k |
4.Среди всех найденных планов находим план, имеющий наименьшее время реализации
T min Tk |
min |
max tij . |
|
X k |
i, j X k |
Эта задача не является задачей линейного программирования, а относится к числу задач на минимакс.
Пример. Пусть мощности поставщиков ai , спрос потребителей b j и
матрица времени T |
tij |
представлены в таблице |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bj |
|
63 |
34 |
43 |
50 |
|
65 |
70 |
|
|
ai |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
75 |
|
|
1,5 |
3 |
2,5 |
1 |
|
2 |
1,8 |
|
|
100 |
|
1 |
3,5 |
2 |
3 |
|
4 |
1 |
||
|
150 |
|
1,2 |
2 |
2,2 |
2,5 |
|
2,5 |
3 |
||
Определить минимальное время реализации плана перевозок.
Решение. Проверяем условие баланса ai |
bj 325. |
1.Находим первоначальный план Х1 по методу минимального элемента матрицы времени (табл. 3)
40
План Х1 |
|
|
|
|
|
|
|
Таблица 3 |
|
63 |
34 |
43 |
50 |
|
65 |
70 |
|
|
|
1,5 |
|
3 |
2,5 |
1 |
2 |
18 |
75 |
|
|
|
|
50 |
|
|
25 |
100 |
|
1 |
|
3,5 |
2 |
3 |
4 |
1 |
63 |
|
|
|
|
|
|
37 |
|
|
|
|
|
|
|
|
||
150 |
|
1,2 |
|
2 |
2,2 |
2,5 |
2,5 |
5 |
|
|
|||||||
|
34 |
43 |
|
|
65 |
8 |
||
|
|
|
|
|||||
2. Определяем время реализации плана Х1: |
|
|||||||
|
|
|
|
T1 |
max tij |
t36 |
3 (час). |
|
|
|
|
|
|
i, j x1 |
|
|
|
Наиболее продолжительная перевозка от третьего поставщика к шестому потребителю.
3.Исключаем из рассмотрения клетки с производительностью большей или равной 3, чтобы не увеличить продолжительность всего комплекса перевозок при перемещении поставок по контуру.
4.Сокращаем время перевозок, исключая из плана наиболее
продолжительные |
перевозки. В нашем примере t36 3 . Строим |
замкнутый маршрут для клетки (3,6). Таких маршрутов несколько |
|
(3,6)-(1,6)-(1,5)-(3,5); |
(3,6)-(2,6)-(2,3)-(3,3); |
(3,6)-(1,6)-(1,4)-(3,4); |
(3,6)-(2,6)-(2,1)-(3,1). |
(3,6)-(1,6)-(1,3)-(3,3); |
|
(3,6)-(1,6)-(1,1)-(3,1); |
|
Выбираем маршрут (3,6)-(2,6)-(2,1)-(3,1). Пометим клетку (3,6) знаком плюс и чередуем по вершинам маршрута знаки. Поставка, перемещаемая
по маршруту, |
min(8,63) 8 . |
" "
Получаем план Х2 (табл. 4)