Реферат

Реферат Транспортная задача 3

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 28.12.2024




 Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

 
 b1
 b2
 b3
b 4
 b5
 Запасы

 a1
 13
 9
 15
 3
 18
 53

 a2
 7
 8
 6
 10
 9
 17

 a3
 16
 4
 10
 11
 29
 30

 Потребности
 20
 20
 20
 13
 27
 

 Проверим необходимое и достаточное условие разрешимости задачи.

 ∑ a = 53 + 17 + 30 = 100

 ∑ b = 20 + 20 + 20 + 13 + 27 = 100

 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

 Занесем исходные данные в распределительную таблицу.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13
 9
 15
 3
 18
 53

 2
 7
 8
 6
 10
 9
 17

 3
 16
 4
 10
 11
 29
 30

 Потребности
 20
 20
 20
 13
 27
 

 1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

 Искомый элемент равен 13

 Для этого элемента запасы равны 53, потребности 20. Поскольку минимальным является 20, то вычитаем его.

 13
 9
 15
 3
 18
 33

 x
 8
 6
 10
 9
 17

 x
 4
 10
 11
 29
 30

 0
 20
 20
 13
 27
 0

 

 Искомый элемент равен 9

 Для этого элемента запасы равны 33, потребности 20. Поскольку минимальным является 20, то вычитаем его.

 13
 9
 15
 3
 18
 13

 x
 x
 6
 10
 9
 17

 x
 x
 10
 11
 29
 30

 0
 0
 20
 13
 27
 0

 

 Искомый элемент равен 15

 Для этого элемента запасы равны 13, потребности 20. Поскольку минимальным является 13, то вычитаем его.

 13
 9
 15
 x
 x
 0

 x
 x
 6
 10
 9
 17

 x
 x
 10
 11
 29
 30

 0
 0
 7
 13
 27
 0

 

 Искомый элемент равен 6

 Для этого элемента запасы равны 17, потребности 7. Поскольку минимальным является 7, то вычитаем его.

 13
 9
 15
 x
 x
 0

 x
 x
 6
 10
 9
 10

 x
 x
 x
 11
 29
 30

 0
 0
 0
 13
 27
 0

 

 Искомый элемент равен 10

 Для этого элемента запасы равны 10, потребности 13. Поскольку минимальным является 10, то вычитаем его.

 13
 9
 15
 x
 x
 0

 x
 x
 6
 10
 x
 0

 x
 x
 x
 11
 29
 30

 0
 0
 0
 3
 27
 0

 

 Искомый элемент равен 11

 Для этого элемента запасы равны 30, потребности 3. Поскольку минимальным является 3, то вычитаем его.

 13
 9
 15
 x
 x
 0

 x
 x
 6
 10
 x
 0

 x
 x
 x
 11
 29
 27

 0
 0
 0
 0
 27
 0

 

 Искомый элемент равен 29

 Для этого элемента запасы равны 27, потребности 27. Поскольку минимальным является 27, то вычитаем его.

 13
 9
 15
 x
 x
 0

 x
 x
 6
 10
 x
 0

 x
 x
 x
 11
 29
 0

 0
 0
 0
 0
 0
 0

 

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9[20]
 15[13]
 3
 18
 53

 2
 7
 8
 6[7]
 10[10]
 9
 17

 3
 16
 4
 10
 11[3]
 29[27]
 30

 Потребности
 20
 20
 20
 13
 27
 

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

 2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

 4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

 u1 + v1 = 13; 0 + v1 = 13; v1 = 13

 u1 + v2 = 9; 0 + v2 = 9; v2 = 9

 u1 + v3 = 15; 0 + v3 = 15; v3 = 15

 u2 + v3 = 6; 15 + u2 = 6; u2 = -9

 u2 + v4 = 10; -9 + v4 = 10; v4 = 19

 u3 + v4 = 11; 19 + u3 = 11; u3 = -8

 u3 + v5 = 29; -8 + v5 = 29; v5 = 37

 
 v1=13
 v2=9
 v3=15
 v4=19
 v5=37

 u1=0
 13[20]
 9[20]
 15[13]
 3
 18

 u2=-9
 7
 8
 6[7]
 10[10]
 9

 u3=-8
 16
 4
 10
 11[3]
 29[27]

 Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

 (1;4): 0 + 19 > 3; ∆14 = 0 + 19 - 3 = 16

 (1;5): 0 + 37 > 18; ∆15 = 0 + 37 - 18 = 19

 (2;5): -9 + 37 > 9; ∆25 = -9 + 37 - 9 = 19

 max(16,19,19) = 19

 Выбираем максимальную оценку свободной клетки (1;5): 18

 Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9[20]
 15[13][-]
 3
 18[+]
 53

 2
 7
 8
 6[7][+]
 10[10][-]
 9
 17

 3
 16
 4
 10
 11[3][+]
 29[27][-]
 30

 Потребности
 20
 20
 20
 13
 27
 

 Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9[20]
 15[3]
 3
 18[10]
 53

 2
 7
 8
 6[17]
 10
 9
 17

 3
 16
 4
 10
 11[13]
 29[17]
 30

 Потребности
 20
 20
 20
 13
 27
 

 4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

 u1 + v1 = 13; 0 + v1 = 13; v1 = 13

 u1 + v2 = 9; 0 + v2 = 9; v2 = 9

 u1 + v3 = 15; 0 + v3 = 15; v3 = 15

 u2 + v3 = 6; 15 + u2 = 6; u2 = -9

 u1 + v5 = 18; 0 + v5 = 18; v5 = 18

 u3 + v5 = 29; 18 + u3 = 29; u3 = 11

 u3 + v4 = 11; 11 + v4 = 11; v4 = 0

 
 v1=13
 v2=9
 v3=15
 v4=0
 v5=18

 u1=0
 13[20]
 9[20]
 15[3]
 3
 18[10]

 u2=-9
 7
 8
 6[17]
 10
 9

 u3=11
 16
 4
 10
 11[13]
 29[17]

 Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

 (3;1): 11 + 13 > 16; ∆31 = 11 + 13 - 16 = 8

 (3;2): 11 + 9 > 4; ∆32 = 11 + 9 - 4 = 16

 (3;3): 11 + 15 > 10; ∆33 = 11 + 15 - 10 = 16

 max(8,16,16) = 16

 Выбираем максимальную оценку свободной клетки (3;2): 4

 Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9[20][-]
 15[3]
 3
 18[10][+]
 53

 2
 7
 8
 6[17]
 10
 9
 17

 3
 16
 4[+]
 10
 11[13]
 29[17][-]
 30

 Потребности
 20
 20
 20
 13
 27
 

 Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 17. Прибавляем 17 к объемам грузов, стоящих в плюсовых клетках и вычитаем 17 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9[3]
 15[3]
 3
 18[27]
 53

 2
 7
 8
 6[17]
 10
 9
 17

 3
 16
 4[17]
 10
 11[13]
 29
 30

 Потребности
 20
 20
 20
 13
 27
 

 4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

 u1 + v1 = 13; 0 + v1 = 13; v1 = 13

 u1 + v2 = 9; 0 + v2 = 9; v2 = 9

 u3 + v2 = 4; 9 + u3 = 4; u3 = -5

 u3 + v4 = 11; -5 + v4 = 11; v4 = 16

 u1 + v3 = 15; 0 + v3 = 15; v3 = 15

 u2 + v3 = 6; 15 + u2 = 6; u2 = -9

 u1 + v5 = 18; 0 + v5 = 18; v5 = 18

 
 v1=13
 v2=9
 v3=15
 v4=16
 v5=18

 u1=0
 13[20]
 9[3]
 15[3]
 3
 18[27]

 u2=-9
 7
 8
 6[17]
 10
 9

 u3=-5
 16
 4[17]
 10
 11[13]
 29

 Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

 (1;4): 0 + 16 > 3; ∆14 = 0 + 16 - 3 = 13

 Выбираем максимальную оценку свободной клетки (1;4): 3

 Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9[3][-]
 15[3]
 3[+]
 18[27]
 53

 2
 7
 8
 6[17]
 10
 9
 17

 3
 16
 4[17][+]
 10
 11[13][-]
 29
 30

 Потребности
 20
 20
 20
 13
 27
 

 Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9
 15[3]
 3[3]
 18[27]
 53

 2
 7
 8
 6[17]
 10
 9
 17

 3
 16
 4[20]
 10
 11[10]
 29
 30

 Потребности
 20
 20
 20
 13
 27
 

 4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

 u1 + v1 = 13; 0 + v1 = 13; v1 = 13

 u1 + v3 = 15; 0 + v3 = 15; v3 = 15

 u2 + v3 = 6; 15 + u2 = 6; u2 = -9

 u1 + v4 = 3; 0 + v4 = 3; v4 = 3

 u3 + v4 = 11; 3 + u3 = 11; u3 = 8

 u3 + v2 = 4; 8 + v2 = 4; v2 = -4

 u1 + v5 = 18; 0 + v5 = 18; v5 = 18

 
 v1=13
 v2=-4
 v3=15
 v4=3
 v5=18

 u1=0
 13[20]
 9
 15[3]
 3[3]
 18[27]

 u2=-9
 7
 8
 6[17]
 10
 9

 u3=8
 16
 4[20]
 10
 11[10]
 29

 Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

 (3;1): 8 + 13 > 16; ∆31 = 8 + 13 - 16 = 5

 (3;3): 8 + 15 > 10; ∆33 = 8 + 15 - 10 = 13

 max(5,13) = 13

 Выбираем максимальную оценку свободной клетки (3;3): 10

 
Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9
 15[3][-]
 3[3][+]
 18[27]
 53

 2
 7
 8
 6[17]
 10
 9
 17

 3
 16
 4[20]
 10[+]
 11[10][-]
 29
 30

 Потребности
 20
 20
 20
 13
 27
 

 Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9
 15
 3[6]
 18[27]
 53

 2
 7
 8
 6[17]
 10
 9
 17

 3
 16
 4[20]
 10[3]
 11[7]
 29
 30

 Потребности
 20
 20
 20
 13
 27
 

 4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

 u1 + v1 = 13; 0 + v1 = 13; v1 = 13

 u1 + v4 = 3; 0 + v4 = 3; v4 = 3

 u3 + v4 = 11; 3 + u3 = 11; u3 = 8

 u3 + v2 = 4; 8 + v2 = 4; v2 = -4

 u3 + v3 = 10; 8 + v3 = 10; v3 = 2

 u2 + v3 = 6; 2 + u2 = 6; u2 = 4

 u1 + v5 = 18; 0 + v5 = 18; v5 = 18

 
 v1=13
 v2=-4
 v3=2
 v4=3
 v5=18

 u1=0
 13[20]
 9
 15
 3[6]
 18[27]

 u2=4
 7
 8
 6[17]
 10
 9

 u3=8
 16
 4[20]
 10[3]
 11[7]
 29

 Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

 (2;1): 4 + 13 > 7; ∆21 = 4 + 13 - 7 = 10

 (2;5): 4 + 18 > 9; ∆25 = 4 + 18 - 9 = 13

 (3;1): 8 + 13 > 16; ∆31 = 8 + 13 - 16 = 5

 max(10,13,5) = 13

 Выбираем максимальную оценку свободной клетки (2;5): 9

 Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9
 15
 3[6][+]
 18[27][-]
 53

 2
 7
 8
 6[17][-]
 10
 9[+]
 17

 3
 16
 4[20]
 10[3][+]
 11[7][-]
 29
 30

 Потребности
 20
 20
 20
 13
 27
 

 Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 7. Прибавляем 7 к объемам грузов, стоящих в плюсовых клетках и вычитаем 7 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 
 1
 2
 3
 4
 5
 Запасы

 1
 13[20]
 9
 15
 3[13]
 18[20]
 53

 2
 7
 8
 6[10]
 10
 9[7]
 17

 3
 16
 4[20]
 10[10]
 11
 29
 30

 Потребности
 20
 20
 20
 13
 27
 

 4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

 u1 + v1 = 13; 0 + v1 = 13; v1 = 13

 u1 + v4 = 3; 0 + v4 = 3; v4 = 3

 u1 + v5 = 18; 0 + v5 = 18; v5 = 18

 u2 + v5 = 9; 18 + u2 = 9; u2 = -9

 u2 + v3 = 6; -9 + v3 = 6; v3 = 15

 u3 + v3 = 10; 15 + u3 = 10; u3 = -5

 u3 + v2 = 4; -5 + v2 = 4; v2 = 9

 
 v1=13
 v2=9
 v3=15
 v4=3
 v5=18

 u1=0
 13[20]
 9
 15
 3[13]
 18[20]

 u2=-9
 7
 8
 6[10]
 10
 9[7]

 u3=-5
 16
 4[20]
 10[10]
 11
 29

 Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

 Минимальные затраты составят:

 F(x) = 13*20 + 3*13 + 18*20 + 6*10 + 9*7 + 4*20 + 10*10  = 962

1. Реферат Біохімічні фактори витривалості
2. Реферат Назначение административного наказания
3. Реферат Парижский мирный договор 1763
4. Доклад Екатерина II 7
5. Курсовая на тему Виноградно винодельческий комплекс Крыма
6. Курсовая Потоковое видео и открытые системы
7. Реферат Антиглобализм как социальное движение современного мира
8. Курсовая Авторский проект как частный вид Интернет-журналистики
9. Реферат Антропный космологический принцип его естественнонаучный и философско-методологический смысл
10. Диплом Совершенствование организации проведения анализа финансового состояния предприятия