ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.04.2024
Просмотров: 223
Скачиваний: 0
30
Метод «здравого смысла»
В методе северно-западного угла мы не заботились о том, чтобы делать назначения в клетки с минимальной стоимостью перевозки. Попробуем сделать это в методе «здравого смысла» (его называют также методом минимальной стоимости). Распределение начинаем с элемента минимальной стоимости.
Элемент минимальной стоимости (8) расположен в клетке (3,2) (см. исходную матрицу). Поэтому с этой клетки начинаем распределять поставки, назначая максимально возможную, т.е. x32=8. Других поставок в этом столбце быть не должно, так как потребности склада 2 исчерпаны. При решении задачи на бумаге рекомендуется вычеркнуть этот столбец из матрицы. Следующий наименьший показатель ищем среди незачеркнутых элементов. Он равен 10 и соответствует клетке (1,4), где вновь выбирается максимально возможная поставка x14=7. Теперь необходимо вычеркнуть первую строку, так как использована вся мощность предприятия 1. Поэтому переходим к клетке (3,4) и т.д. Получим оставшиеся назначения: x34=7, x23=7, x21=2, x31=3.
Снова занесем полученное решение в таблицу.
|
1 |
2 |
3 |
4 |
|
|
|
|
|
|
|
1 |
|
|
|
7(10) |
7 |
2 |
2(70) |
|
7(40) |
|
9 |
3 |
3(40) |
8(8) |
|
7(20) |
18 |
|
|
|
|
|
|
|
5 |
8 |
7 |
14 |
|
|
|
|
|
|
|
Общие затраты при этом решении равны
2*70+3*40+8*8+7*40+7*10+7*20=814 (ед.стоим.).
Получили снижение затрат на 201 (ед.стоим.).
Метод штрафов
Во втором методе мы старались использовать минимальные затраты,
31
но не всегда могли это сделать. Очевидно, необходимо определить поставку по крайней мере в одной клетке каждой строки или хотя бы в одной клетке каждого столбца. В этом алгоритме оцениваются потери (штрафы), обусловленные тем, что мы не используем минимальный показатель затрат в каждой строке и каждом столбце. Эти потери представляют собой разность между наименьшим показателем затрат в строке или столбце и следующим за ним по величине.
Подсчитаем штрафы в каждой строке и каждом столбце. Занесем их в матрицу, добавив еще один столбец справа и строку внизу. Получим:
|
1 |
2 |
3 |
4 |
|
Штрафы |
|
|
|
|
|
|
|
1 |
19 |
30 |
50 |
10 |
7 |
9 |
2 |
70 |
30 |
40 |
60 |
9 |
10 |
3 |
40 |
8 |
70 |
20 |
18 |
12 |
|
|
|
|
|
|
|
|
5 |
8 |
7 |
14 |
|
|
|
|
|
|
|
|
|
Штрафы |
21 |
22 |
10 |
10 |
|
|
|
|
|
|
|
|
|
Распределение начинаем с клетки (3,2), которой соответствует максимальный штраф (22), и выделим в нее максимально возможный объем, x32=8. Теперь можно исключить столбец 2, что требует пересчета штрафов и корректировки объема, который может быть поставлен предприятием 3. Нумерацию оставшихся столбцов и строк не меняем. Получим таблицу:
|
1 |
3 |
4 |
|
Штрафы |
|
|
|
|
7 |
|
1 |
19 |
50 |
10 |
9 |
|
2 |
70 |
40 |
60 |
9 |
20 |
3 |
40 |
70 |
20 |
10 |
20 |
|
|
|
|
|
|
|
5 |
7 |
14 |
|
|
|
|
|
|
|
|
Штрафы |
21 |
10 |
10 |
|
|
|
|
|
|
|
|
Теперь наибольший штраф (21) соответствует клетке (1,1). Поэтому в эту клетку направляется максимально возможный объем, x11=5. Исключаем
32
столбец 1. Снова пересчитываем штрафы и корректируем объем, который может быть поставлен первым предприятием. Получим таблицу:
|
3 |
4 |
|
Штрафы |
|
|
|
|
40 |
1 |
50 |
10 |
2 |
|
2 |
40 |
60 |
9 |
20 |
3 |
70 |
20 |
10 |
50 |
|
|
|
|
|
|
7 |
14 |
|
|
|
|
|
|
|
Штрафы |
10 |
10 |
|
|
|
|
|
|
|
Далее наибольший штраф равен 50 (клетка (3,4)), x34=10.
|
3 |
4 |
|
Штрафы |
|
|
|
|
40 |
1 |
50 |
10 |
2 |
|
2 |
40 |
60 |
9 |
20 |
7 4
Штрафы 10 50
Снова наибольший штраф равен 50 (клетка (1,4), x14=2.
Таким образом, остаются лишь предприятие 2, имеющее в наличии 9 единиц продукции, и склады 3 и 4, которым требуется 7 и 2 единиц продукции соответственно. Поэтому принимаем x23=7 и x24=2.
Итак, допустимое решение имеет вид: x32=8, x11=5, x34=10, x14=2, x23=7, x24=2.
Занесем это решение в таблицу:
|
1 |
2 |
3 |
4 |
|
|
|
|
|
|
|
1 |
5(19) |
|
|
2(10) |
7 |
2 |
|
|
7(40) |
2(60) |
9 |
3 |
|
8(8) |
|
10(20) |
18 |
|
|
|
|
|
|
|
5 |
8 |
7 |
14 |
|
|
|
|
|
|
|
Вычислим затраты, соответствующие полученному решению: 5*19+8*8+7*40+2*10+2*60+10*20=779, что на 35 единиц меньше, чем