Метод наименьшей стоимости.

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

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.

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

Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

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

Для этого элемента запасы равны Метод наименьшей стоимости. 22, потребности 41. Поскольку минимальным является 22, то вычитаем его.

x33 = min(22,41) = 22.

x x x x 22 - 22 = 0
41 - 22 = 19

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

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

x11 = min(21,36) = 21.

x x x x 21 - 21 = 0
x x x x
36 - 21 = 15

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

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

x55 = min(8,17) = 8.

x x x x
x x x x
x x x x 8 - 8 = 0
17 - 8 = 9

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

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

x41 = min(15,15) = 15.

x x x x
x
x x x x
x x x x 15 - 15 = 0
x x Метод наименьшей стоимости. x x
15 - 15 = 0

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

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

x22 = min(46,33) = 33.

x x x x
x 46 - 33 = 13
x x x x
x x x x
x x x x
33 - 33 = 0

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

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

x25 = min(13,9) = 9.

x x x x
x 13 - 9 = 4
x x x x
x x x x
x x x x
9 - 9 = 0

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

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

x24 = min(4,53) = 4.

x x x x
x x 4 - 4 = 0
x x x x
x x Метод наименьшей стоимости. x x
x x x x
53 - 4 = 49

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

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

x63 = min(68,19) = 19.

x x x x
x x
x x x x
x x x x
x x x x
68 - 19 = 49
19 - 19 = 0



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

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

x64 = min(49,49) = 49.

x x x x
x x
x x x x
x x x x
x x x x
49 - 49 = 0
49 - 49 = 0

Полученная матрица распределения запасов

Запасы
13[21]
25[33] 29[4] 25[9]
12[22]
17[15]
16[8]
0[19] 0[49]
Потребности

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

Значение целевой функции для Метод наименьшей стоимости. этого опорного плана равно:

F(x) = 13*21 + 25*33 + 29*4 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*49 = 2086

Строим новый план.

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

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

x11 = min(21,36) = 21.

x x x x 21 - 21 = 0
36 - 21 = 15

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

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

x33 = min(22,41) = 22.

x x x x
x x x x 22 - 22 = 0
41 - 22 = 19

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

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

x55 = min(8,17) = 8.

x x x x
x x x x
x x x x 8 - 8 = 0
17 - 8 = 9

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

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

x41 = min(15,15) = 15.

x x x x
x
x x x x
x x x x 15 - 15 = 0
x x x x
15 - 15 = 0

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

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

x22 = min(46,33) = 33.

x x x x
x 46 - 33 = 13
x x x x
x x x x
x x x x
33 - 33 = 0

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

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

x25 = min(13,9) = 9.

x x x x
x 13 - 9 = 4
x x x x
x x x x
x x x x
9 - 9 = 0

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

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

x24 = min(4,53) = 4.

x x x x
x x 4 - 4 = 0
x x x x
x x x x
x x x x
53 - 4 = 49

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

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

x63 = min(68,19) = 19.

x x x x
x x
x x x x
x x x x
x x x x
68 - 19 = 49
19 - 19 = 0

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

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

x64 = min(49,49) = 49.

x x x x
x x
x x x x
x x x x
x x x x
49 - 49 = 0
49 - 49 = 0

Полученная матрица распределения ресурсов

Запасы
13[21]
25[33] 29[4] 25[9]
12[22]
17[15]
16[8]
0[19] 0[49]
Потребности

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

Значение целевой функции для этого опорного плана равно:

F(x) = 13*21 + 25*33 + 29*4 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*49 = 2086

Строим новый план.

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

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

x55 = min(8,17) = 8.

x x x x 8 - 8 = 0
17 - 8 = 9

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

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

x33 = min(22,41) = 22.

x x x x 22 - 22 = 0
x x x x
41 - 22 = 19

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

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

x11 = min(21,36) = 21.

x x x x 21 - 21 = 0
x x Метод наименьшей стоимости. x x
x x x x
36 - 21 = 15

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

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

x41 = min(15,15) = 15.

x x x x
x
x x x x
x x x x 15 - 15 = 0
x x x x
15 - 15 = 0

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

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

x22 = min(46,33) = 33.

x x x x
x 46 - 33 = 13
x x x x
x x x x
x x x x
33 - 33 = 0

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

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

x25 = min(13,9) = 9.

x x x x
x 13 - 9 = 4
x x x Метод наименьшей стоимости. x
x x x x
x x x x
9 - 9 = 0

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

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

x24 = min(4,53) = 4.

x x x x
x x 4 - 4 = 0
x x x x
x x x x
x x x x
53 - 4 = 49

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

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

x63 = min(68,19) = 19.

x x x x
x x
x x x x
x x x x
x x x x
68 - 19 = 49
19 - 19 = 0

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

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

x64 = min(49,49) = 49.

x x x Метод наименьшей стоимости. x
x x
x x x x
x x x x
x x x x
49 - 49 = 0
49 - 49 = 0

Полученная матрица распределения ресурсов

Запасы
13[21]
25[33] 29[4] 25[9]
12[22]
17[15]
16[8]
0[19] 0[49]
Потребности

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

Значение целевой функции для этого опорного плана равно:

F(x) = 13*21 + 25*33 + 29*4 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*49 = 2086

Строим новый план.

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

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

x41 = min(15,36) = 15.

x x x x 15 - 15 = 0
36 - 15 = 21

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

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

x33 = min(22,41) = 22.

x x x x 22 - 22 = 0
x x x x
41 - 22 = 19

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

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

x11 = min(21,21) = 21.

x x x x 21 - 21 = 0
x
x x x x
x x x x
x
21 - 21 = 0

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

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

x55 = min(8,17) = 8.

x x x x
x
x x x x
x x x x
x x x x 8 - 8 = 0
17 - 8 = 9

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

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

x22 = min(46,33) = 33.

x x x x
x 46 - 33 = 13
x x x x
x x x x
x x x x
33 - 33 = 0

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

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

x25 = min(13,9) = 9.

x x x x
x 13 - 9 = 4
x x x x
x x x x
x x x x
9 - 9 = 0

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

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

x24 = min(4,53) = 4.

x x x x
x x 4 - 4 = 0
x x x x
x x x x
x x x x
53 - 4 = 49

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

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

x63 = min(68,19) = 19.

x x x x
x x
x x x x
x x x x
x x x x
68 - 19 = 49
19 - 19 = 0

Искомый элемент Метод наименьшей стоимости. равен 0

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

x64 = min(49,49) = 49.

x x x x
x x
x x x x
x x x x
x x x x
49 - 49 = 0
49 - 49 = 0

Матрица распределения ресурсов выглядит следующим образом:

Запасы
13[21]
25[33] 29[4] 25[9]
12[22]
17[15]
16[8]
0[19] 0[49]
Потребности

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

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 13*21 + 25*33 + 29*4 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*49 = 2086

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

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

x12 = min(21,33) = 21.

x x x x 21 - 21 = 0
33 - 21 = 12

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

Для этого элемента запасы Метод наименьшей стоимости. равны 22, потребности 41. Поскольку минимальным является 22, то вычитаем его.

x33 = min(22,41) = 22

x x x x
x x x x 22 - 22 = 0
41 - 22 = 19

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

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

x55 = min(8,17) = 8.

x x x x
x x x x
x x x x 8 - 8 = 0
17 - 8 = 9

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

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

x41 = min(15,36) = 15.

x x x x
x x x x
x x x x 15 - 15 = 0
x x x x
36 - 15 = 21

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

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

x21 = min Метод наименьшей стоимости.(46,21) = 21.

x x x x
46 - 21 = 25
x x x x
x x x x
x x x x
21 - 21 = 0

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

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

x22 = min(25,12) = 12.

x x x x
25 - 12 = 13
x x x x
x x x x
x x x x
12 - 12 = 0

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

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

x25 = min(13,9) = 9.

x x x x
13 - 9 = 4
x x x x
x x x x
x x x x
9 - 9 = 0

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

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

x24 = min Метод наименьшей стоимости.(4,53) = 4.

x x x x
x 4 - 4 = 0
x x x x
x x x x
x x x x
53 - 4 = 49

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

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

x63 = min(68,19) = 19.

x x x x
x
x x x x
x x x x
x x x x
68 - 19 = 49
19 - 19 = 0

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

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

x64 = min(49,49) = 49.

x x x x
x
x x x x
x x x x
x x x x
49 - 49 = 0
49 - 49 = 0

Матрица распределения ресурсов:

Запасы
21[21]
22[21] 25[12] 29[4] 25[9]
12[22]
17[15]
16[8]
0[19] 0[49]
Потребности

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

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

Значение целевой функции для этого опорного плана равно:

F(x) = 21*21 + 22*21 + 25*12 + 29*4 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*49 = 2191


documentaalrcer.html
documentaalrjoz.html
documentaalrqzh.html
documentaalryjp.html
documentaalsftx.html
Документ Метод наименьшей стоимости.