Задание №3
Дано:
|
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие |
А1 |
7 |
4 |
15 |
9 |
14 |
120 |
А2 |
11 |
2 |
7 |
3 |
10 |
150 |
А3 |
4 |
5 |
12 |
8 |
17 |
100 |
Потребность |
65 |
90 |
60 |
70 |
300 |
|
Решение:
Пошагово осуществим поиск опорного плана методом северо-западного угла:
Потребности пункта B1 удовлетворены.
Запасы склада А1 исчерпаны.
Потребности пункта B2 удовлетворены.
.
Потребности пункта B3 удовлетворены.
.
Запасы склада А2 исчерпаны.
.
Потребности пункта B4 удовлетворены.
.
Для удовлетворения потребностей пункта B5 не хватает товара в количестве 215 единиц.
Данные полученные при поиске опорного плана методом северо-западного угла сведены в таблицу:
|
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие | ||||
А1 |
7 |
4 |
15 |
9 |
14 |
120 |
[55] |
[0] | ||
[65] |
[55] |
|
|
| ||||||
А2 |
11 |
2 |
7 |
3 |
10 |
150 |
[115] |
[55] |
[0] | |
|
[35] |
[60] |
[55] |
| ||||||
А3 |
4 |
5 |
12 |
8 |
17 |
100 |
[85] |
[0] | ||
|
|
|
[15] |
[85] | ||||||
Потребность |
65 |
90 |
60 |
70 |
300 |
| ||||
[35] |
[0] |
[15] | ||||||||
[0] |
[0] |
[0] |
[215] |
|
Далее добавим фиктивную строку:
|
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие | |||
А1 |
7 |
4 |
15 |
9 |
14 |
120 |
[55] |
[0] | |
[65] |
[55] |
|
|
| |||||
А2 |
11 |
2 |
7 |
3 |
10 |
150 |
[115] |
[55] |
[0] |
|
[35] |
[60] |
[55] |
| |||||
А3 |
4 |
5 |
12 |
8 |
17 |
100 |
[85] |
[0] | |
|
|
|
[15] |
[85] | |||||
A4 |
17 |
17 |
17 |
17 |
17 |
215 |
[0] | ||
|
|
|
|
215 | |||||
Потребность |
65 |
90 |
60 |
70 |
300 |
| |||
[35] |
[15] |
[215] | |||||||
[0] |
[0] | ||||||||
[0] |
[0] |
[0] |
|
.
Потребности пункта B5 удовлетворены.
Получен начальный план перевозок, а его суммарная стоимость составила:
Осуществим поиск опорного плана методом наименьшей стоимости, данные сведем в таблицу:
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие | |||||||
А1 |
7 |
4 |
15 |
9 |
14 |
120 |
[0] | |||||
|
|
|
|
(6) [120] | ||||||||
А2 |
11 |
2 |
7 |
3 |
10 |
150 |
[60] |
[0] | ||||
|
(1) [90] |
|
(2) [60] |
| ||||||||
А3 |
4 |
5 |
12 |
8 |
17 |
100 |
[35] |
[10] |
[0] | |||
(3) [65] |
|
(5) [25] |
(4) [10] |
| ||||||||
A4 |
17 |
17 |
17 |
17 |
17 |
215 |
[180] |
[0] | ||||
|
|
(7) [35] |
|
(8) [180] | ||||||||
Потребность |
65 |
90 |
60 |
70 |
300 |
| ||||||
[35] |
[10] |
[180] | ||||||||||
[0] |
[0] |
[0] |
[0] |
[0] |
|
Получен начальный план перевозок, а его суммарная стоимость составила:
Осуществим поиск оптимального плана перевозок с помощью метода потенциалов основываясь на опорном плане, полученном методом наименьшей стоимости:
7 |
7 |
14 | |
0 |
2 |
2 | |
0 |
3 |
3 | |
5 |
4 | ||
5 |
7 |
12 | |
5 |
3 |
8 | |
10 |
7 |
17 | |
10 |
7 |
17 |
Значения для свободных клеток:
Значение | |
1 | |
-5 | |
1 | |
-1 | |
12 | |
0 | |
3 | |
-2 | |
5 | |
8 | |
5 | |
4 |
Выберем наименьшее отрицательное значение и приняв его за начало цикла расставим затем знаки начиная с «» и чередуя его с «»:
|
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие | |||||||
А1 |
7 |
4 |
15 |
9 |
14 |
120 |
[0] | ||||||
|
(+)
|
|
|
(6) (–) [120] | |||||||||
А2 |
11 |
2 |
7 |
3 |
10 |
150 |
[60] |
[0] | |||||
|
(1) (–) [90] |
|
(2) (+) [60] |
| |||||||||
А3 |
4 |
5 |
12 |
8 |
17 |
100 |
[35] |
[10] |
[0] | ||||
(3) [65] |
|
(5) (+) [25] |
(4) (–) [10] |
| |||||||||
A4 |
17 |
17 |
17 |
17 |
17 |
215 |
[180] |
[0] | |||||
|
|
(7) (–) [35] |
|
(8) (+) [180] | |||||||||
Потребность |
65 |
90 |
60 |
70 |
300 |
| |||||||
[35] |
[10] |
[180] | |||||||||||
[0] |
[0] |
[0] |
[0] |
[0] |
|
Выбираем минимальное число (данное число равно 10) в «» ячейках цикла и учитывая знаки цикла прибавляем это число или отнимаем, а также обновим расстановку знаков «+» и «»:
|
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие |
А1 |
7 |
4 |
15 |
9 |
14 |
120 |
|
(+) [10] |
|
|
(–) [110] | ||
А2 |
11 |
2 |
7 |
3 |
10 |
150 |
|
(–) [80] |
(+)
|
[70] |
| ||
А3 |
4 |
5 |
12 |
8 |
17 |
100 |
[65] |
|
(+) [35] |
|
| ||
A4 |
17 |
17 |
17 |
17 |
17 |
215 |
|
|
(–) [25] |
|
(+) [190] | ||
Потребность |
65 |
90 |
60 |
70 |
300 |
|
|
Ячейка заполняется, а ячейкастала пустой.
Найдем значения:
0 |
4 |
4 | |
0 |
14 |
14 | |
4 |
2 | ||
5 |
3 | ||
6 |
4 | ||
14 |
12 | ||
3 |
14 |
17 | |
3 |
14 |
17 |
Найдем значения для свободных клеток:
Значение | |
1 | |
1 | |
4 | |
7 | |
3 | |
5 | |
5 | |
8 | |
10 | |
9 |
Выбираем минимальное число (данное число равно 25) в «» ячейках цикла (согласно расстановке знаков на предыдущей стадии) и учитывая знаки цикла прибавляем это число или отнимаем:
|
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие |
А1 |
7 |
4 |
15 |
9 |
14 |
120 |
|
(+) [35] |
|
|
(-) [85] | ||
А2 |
11 |
2 |
7 |
3 |
10 |
150 |
|
(-) [55] |
[25] |
[70] |
(+)
| ||
А3 |
4 |
5 |
12 |
8 |
17 |
100 |
[65] |
|
(+) [35] |
|
| ||
A4 |
17 |
17 |
17 |
17 |
17 |
215 |
|
|
|
|
[215] | ||
Потребность |
65 |
90 |
60 |
70 |
300 |
|
|
Ячейка заполняется, а ячейкастала пустой.
Найдем значения:
2 |
2 |
4 | |
2 |
12 |
14 | |
0 |
2 |
2 | |
0 |
7 |
7 | |
0 |
3 |
3 | |
5 |
-1 |
4 | |
5 |
7 |
12 | |
5 |
12 |
17 |
Найдем значения для свободных клеток:
Значение | |
6 | |
6 | |
4 | |
12 | |
-2 | |
-2 | |
0 | |
0 | |
13 | |
10 | |
5 | |
9 |
Выбираем минимальное число (на данной стадии это число равно 55) в «–» ячейках цикла (согласно расстановке знаков на предыдущей стадии) и учитывая знаки цикла прибавляем это число или отнимаем:
|
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие |
А1 |
7 |
4 |
15 |
9 |
14 |
120 |
|
[90] |
|
|
[30] | ||
А2 |
11 |
2 |
7 |
3 |
10 |
150 |
|
|
[25] |
[70] |
[55] | ||
А3 |
4 |
5 |
12 |
8 |
17 |
100 |
[65] |
|
[35] |
|
| ||
A4 |
17 |
17 |
17 |
17 |
17 |
215 |
|
|
|
|
[215] | ||
Потребность |
65 |
90 |
60 |
70 |
300 |
|
Ячейка заполняется, а ячейкастала пустой.
Найдем значения:
4 |
0 |
4 | |
4 |
10 |
14 | |
0 |
7 |
7 | |
0 |
3 |
3 | |
0 |
10 |
10 | |
5 |
-1 |
4 | |
5 |
7 |
12 | |
7 |
10 |
17 |
Найдем значения для свободных клеток:
Значение | |
4 | |
4 | |
2 | |
12 | |
2 | |
0 | |
0 | |
2 | |
11 | |
10 | |
3 | |
7 |
Все , задача решена.
Общие затраты на перевозку всех единиц продукции составят: