Метод минимального элемента
Метод минимального элемента при нахождении опорного решения учитывает стоимости перевозок, прежде всего, осуществляются перевозки (заполняются клетки транспортной таблицы) с минимальными стоимостями перевозок единицы продукции от производителя к потребителю.
Шаг 0. Условие транспортной задачи задают в виде транспортной таблицы.
Шаг 1. Проверяют выполнение условия баланса. Если условие баланса не выполняется, т.е. задача открытая, то ее сводят к закрытому типу.
Шаг 2. Создают таблицу плана перевозок, в которой заполнены только объемы производства и объемы потребления. Выбирают клетку таблицы, которой соответствует минимальная стоимость перевозки единицы продукции от производителя к потребителю. В выбранную клетку аналогично методу северо-западного угла помещают максимально возможное число единиц продукции, разрешенное ограничениями на запасы и заявки. После этого, если предложение производителя исчерпано, остальные клетки соответствующей строки заполняют нулями; если спрос удовлетворен, остальные клетки соответствующего столбца заполняют нулями.
Таблица 1.2.1
|
22 |
|
24 |
|
7 |
|
25 |
|
23 |
|
29 |
24 |
|||||
|
|
|
|
|
|
|
|
1 5 |
|
9 |
|
||||||
|
1 |
|
21 |
|
30 |
|
10 |
|
7 |
|
19 |
14 |
|||||
14 |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
2 |
|
26 |
|
3 |
|
18 |
|
30 |
|
27 |
19 |
|||||
8 |
|
|
|
10 |
|
|
|
|
|
1 |
|
||||||
|
22 |
|
10 |
|
9 |
|
29 |
|
26 |
|
23 |
27 |
|||||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
||||||
|
18 |
|
16 |
|
13 |
|
17 |
|
18 |
|
19 |
16 |
|||||
|
|
|
|
|
|
14 |
|
2 |
|
|
|
||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|||||||||||
W = 14+16+190+30+14*17+15*23+36+9*29+27+8*23=1341
Таблица 1.2.2
|
22 |
|
24 |
|
7 |
|
25 |
|
23 |
|
29 |
24 |
|
|
|
|
10 |
|
|
|
5 |
|
9 |
|
|
|
1 |
|
21 |
|
30 |
|
10 |
|
7 |
|
19 |
14 |
4 |
|
|
|
|
|
|
|
10 |
|
|
|
|
|
2 |
|
26 |
|
3 |
|
18 |
|
30 |
|
27 |
19 |
18 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
22 |
|
10 |
|
9 |
|
29 |
|
26 |
|
23 |
27 |
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|
|
18 |
|
16 |
|
13 |
|
17 |
|
18 |
|
19 |
16 |
|
|
|
|
|
|
14 |
|
2 |
|
|
|
|
22 |
19 |
10 |
14 |
17 |
18 |
100 |
||||||
W = 4+36+190+70+14*17+5*23+70+36+9*29+27+8*23=1231
Таблица 1.2.3
|
22 |
|
24 |
|
7 |
|
25 |
|
23 |
|
29 |
24 |
||
|
|
|
|
10 |
|
9 |
|
5 |
|
|
|
|||
|
1 |
|
21 |
|
30 |
|
10 |
|
7 |
|
19 |
14 |
||
4 |
|
|
|
|
|
|
|
1 0 |
|
|
|
|||
|
2 |
|
26 |
|
3 |
|
18 |
|
30 |
|
27 |
19 |
||
18 |
|
|
|
|
|
|
|
|
|
1 |
|
|||
|
22 |
|
10 |
|
9 |
|
29 |
|
26 |
|
23 |
27 |
||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|||
|
18 |
|
16 |
|
13 |
|
17 |
|
18 |
|
19 |
16 |
||
|
|
|
|
|
|
5 |
|
2 |
|
9 |
|
|||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
||||||||
W = 4+36+190+70+9*25+5*17+5*23+70+36+27+8*23+9*19=1213
Таблица 1.2.4
|
22 |
|
24 |
|
7 |
|
25 |
|
23 |
|
29 |
24 |
|
|
|
|
10 |
|
9 |
|
5 |
|
|
|
|
|
1 |
|
21 |
|
30 |
|
10 |
|
7 |
|
19 |
14 |
3 |
|
|
|
|
|
|
|
11 |
|
|
|
|
|
2 |
|
26 |
|
3 |
|
18 |
|
30 |
|
27 |
19 |
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
|
10 |
|
9 |
|
29 |
|
26 |
|
23 |
27 |
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|
|
18 |
|
16 |
|
13 |
|
17 |
|
18 |
|
19 |
16 |
|
|
|
|
|
|
5 |
|
1 |
|
10 |
|
|
22 |
19 |
10 |
14 |
17 |
18 |
100 |
||||||
W = 3+38+190+70+9*25+5*17+5*23+11*7+18+8*23+190=1195
Таблица 1.2.5
|
22 |
|
24 |
|
7 |
|
25 |
|
23 |
|
29 |
24 |
|
|
|
|
10 |
|
8 |
|
6 |
|
|
|
|
|
1 |
|
21 |
|
30 |
|
10 |
|
7 |
|
19 |
14 |
3 |
|
|
|
|
|
|
|
11 |
|
|
|
|
|
2 |
|
26 |
|
3 |
|
18 |
|
30 |
|
27 |
19 |
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
|
10 |
|
9 |
|
29 |
|
26 |
|
23 |
27 |
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|
|
18 |
|
16 |
|
13 |
|
17 |
|
18 |
|
19 |
16 |
|
|
|
|
|
|
6 |
|
1 |
|
10 |
|
|
22 |
19 |
10 |
14 |
17 |
18 |
100 |
||||||
W = 3+38+190+70+8*25+6*17+6*23+11*7+8*23+190=1192
Таким образом, последний опорный план является оптимальным.
Минимальные затраты составят:
W = 1192