задача 4
.doc
Искомый элемент равен 10
Для этого элемента запасы равны 100, потребности 100. Поскольку минимальным является 100, то вычитаем его.
x14 = min(100,100) = 100.
|
5 |
x |
x |
10 |
x |
100 - 100 = 0 |
|
x |
2 |
2 |
x |
x |
0 |
|
x |
x |
x |
9 |
2 |
0 |
|
0 |
0 |
0 |
100 - 100 = 0 |
0 |
0 |
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
|
1 |
5[100] |
8 |
7 |
10[100] |
3 |
200 |
|
2 |
4 |
2[125] |
2[325] |
5 |
6 |
450 |
|
3 |
7 |
3 |
5 |
9[150] |
2[100] |
250 |
|
Потребности |
100 |
125 |
325 |
250 |
100 |
|
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 5*100 + 10*100 + 2*125 + 2*325 + 9*150 + 2*100 = 3950
Искомый элемент равен 3
Для этого элемента запасы равны 200, потребности 100. Поскольку минимальным является 100, то вычитаем его.
x15 = min(200,100) = 100.
|
5 |
8 |
7 |
10 |
3 |
200 - 100 = 100 |
|
4 |
2 |
2 |
5 |
x |
450 |
|
7 |
3 |
5 |
9 |
x |
250 |
|
100 |
125 |
325 |
250 |
100 - 100 = 0 |
0 |
Искомый элемент равен 2
Для этого элемента запасы равны 450, потребности 125. Поскольку минимальным является 125, то вычитаем его.
x22 = min(450,125) = 125.
|
5 |
x |
7 |
10 |
3 |
100 |
|
4 |
2 |
2 |
5 |
x |
450 - 125 = 325 |
|
7 |
x |
5 |
9 |
x |
250 |
|
100 |
125 - 125 = 0 |
325 |
250 |
0 |
0 |
Искомый элемент равен 2
Для этого элемента запасы равны 325, потребности 325. Поскольку минимальным является 325, то вычитаем его.
x23 = min(325,325) = 325.
|
5 |
x |
x |
10 |
3 |
100 |
|
x |
2 |
2 |
x |
x |
325 - 325 = 0 |
|
7 |
x |
x |
9 |
x |
250 |
|
100 |
0 |
325 - 325 = 0 |
250 |
0 |
0 |
Искомый элемент равен 5
Для этого элемента запасы равны 100, потребности 100. Поскольку минимальным является 100, то вычитаем его.
x11 = min(100,100) = 100.
|
5 |
x |
x |
x |
3 |
100 - 100 = 0 |
|
x |
2 |
2 |
x |
x |
0 |
|
x |
x |
x |
9 |
x |
250 |
|
100 - 100 = 0 |
0 |
0 |
250 |
0 |
0 |
Искомый элемент равен 9
Для этого элемента запасы равны 250, потребности 250. Поскольку минимальным является 250, то вычитаем его.
x34 = min(250,250) = 250.
|
5 |
x |
x |
x |
3 |
0 |
|
x |
2 |
2 |
x |
x |
0 |
|
x |
x |
x |
9 |
x |
250 - 250 = 0 |
|
0 |
0 |
0 |
250 - 250 = 0 |
0 |
0 |
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
|
1 |
5[100] |
8 |
7 |
10 |
3[100] |
200 |
|
2 |
4 |
2[125] |
2[325] |
5 |
6 |
450 |
|
3 |
7 |
3 |
5 |
9[250] |
2 |
250 |
|
Потребности |
100 |
125 |
325 |
250 |
100 |
|
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 5*100 + 3*100 + 2*125 + 2*325 + 9*250 = 3950
Искомый элемент равен 3
Для этого элемента запасы равны 250, потребности 125. Поскольку минимальным является 125, то вычитаем его.
x32 = min(250,125) = 125.
|
5 |
x |
7 |
10 |
3 |
200 |
|
4 |
x |
2 |
5 |
6 |
450 |
|
7 |
3 |
5 |
9 |
2 |
250 - 125 = 125 |
|
100 |
125 - 125 = 0 |
325 |
250 |
100 |
0 |
Искомый элемент равен 2
Для этого элемента запасы равны 450, потребности 325. Поскольку минимальным является 325, то вычитаем его.
x23 = min(450,325) = 325.
|
5 |
x |
x |
10 |
3 |
200 |
|
4 |
x |
2 |
5 |
6 |
450 - 325 = 125 |
|
7 |
3 |
x |
9 |
2 |
125 |
|
100 |
0 |
325 - 325 = 0 |
250 |
100 |
0 |
Искомый элемент равен 2
Для этого элемента запасы равны 125, потребности 100. Поскольку минимальным является 100, то вычитаем его.
x35 = min(125,100) = 100.
|
5 |
x |
x |
10 |
x |
200 |
|
4 |
x |
2 |
5 |
x |
125 |
|
7 |
3 |
x |
9 |
2 |
125 - 100 = 25 |
|
100 |
0 |
0 |
250 |
100 - 100 = 0 |
0 |
Искомый элемент равен 4
Для этого элемента запасы равны 125, потребности 100. Поскольку минимальным является 100, то вычитаем его.
x21 = min(125,100) = 100.
|
x |
x |
x |
10 |
x |
200 |
|
4 |
x |
2 |
5 |
x |
125 - 100 = 25 |
|
x |
3 |
x |
9 |
2 |
25 |
|
100 - 100 = 0 |
0 |
0 |
250 |
0 |
0 |
Искомый элемент равен 5
Для этого элемента запасы равны 25, потребности 250. Поскольку минимальным является 25, то вычитаем его.
x24 = min(25,250) = 25.
|
x |
x |
x |
10 |
x |
200 |
|
4 |
x |
2 |
5 |
x |
25 - 25 = 0 |
|
x |
3 |
x |
9 |
2 |
25 |
|
0 |
0 |
0 |
250 - 25 = 225 |
0 |
0 |
Искомый элемент равен 9
Для этого элемента запасы равны 25, потребности 225. Поскольку минимальным является 25, то вычитаем его.
x34 = min(25,225) = 25.
|
x |
x |
x |
10 |
x |
200 |
|
4 |
x |
2 |
5 |
x |
0 |
|
x |
3 |
x |
9 |
2 |
25 - 25 = 0 |
|
0 |
0 |
0 |
225 - 25 = 200 |
0 |
0 |
Искомый элемент равен 10
Для этого элемента запасы равны 200, потребности 200. Поскольку минимальным является 200, то вычитаем его.
x14 = min(200,200) = 200.
|
x |
x |
x |
10 |
x |
200 - 200 = 0 |
|
4 |
x |
2 |
5 |
x |
0 |
|
x |
3 |
x |
9 |
2 |
0 |
|
0 |
0 |
0 |
200 - 200 = 0 |
0 |
0 |
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
|
1 |
5 |
8 |
7 |
10[200] |
3 |
200 |
|
2 |
4[100] |
2 |
2[325] |
5[25] |
6 |
450 |
|
3 |
7 |
3[125] |
5 |
9[25] |
2[100] |
250 |
|
Потребности |
100 |
125 |
325 |
250 |
100 |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 10*200 + 4*100 + 2*325 + 5*25 + 3*125 + 9*25 + 2*100 = 3975
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v4 = 10; 0 + v4 = 10; v4 = 10
u2 + v4 = 5; 10 + u2 = 5; u2 = -5
u2 + v1 = 4; -5 + v1 = 4; v1 = 9
u2 + v3 = 2; -5 + v3 = 2; v3 = 7
u3 + v4 = 9; 10 + u3 = 9; u3 = -1
u3 + v2 = 3; -1 + v2 = 3; v2 = 4
u3 + v5 = 2; -1 + v5 = 2; v5 = 3
|
|
v1=9 |
v2=4 |
v3=7 |
v4=10 |
v5=3 |
|
u1=0 |
5 |
8 |
7 |
10[200] |
3 |
|
u2=-5 |
4[100] |
2 |
2[325] |
5[25] |
6 |
|
u3=-1 |
7 |
3[125] |
5 |
9[25] |
2[100] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;1): 0 + 9 > 5; ∆11 = 0 + 9 - 5 = 4
(3;1): -1 + 9 > 7; ∆31 = -1 + 9 - 7 = 1
(3;3): -1 + 7 > 5; ∆33 = -1 + 7 - 5 = 1
max(4,1,1) = 4
Выбираем максимальную оценку свободной клетки (1;1): 5
Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
|
1 |
5[+] |
8 |
7 |
10[200][-] |
3 |
200 |
|
2 |
4[100][-] |
2 |
2[325] |
5[25][+] |
6 |
450 |
|
3 |
7 |
3[125] |
5 |
9[25] |
2[100] |
250 |
|
Потребности |
100 |
125 |
325 |
250 |
100 |
|
Цикл приведен в таблице (1,1; 1,4; 2,4; 2,1; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
|
1 |
5[100] |
8 |
7 |
10[100] |
3 |
200 |
|
2 |
4 |
2 |
2[325] |
5[125] |
6 |
450 |
|
3 |
7 |
3[125] |
5 |
9[25] |
2[100] |
250 |
|
Потребности |
100 |
125 |
325 |
250 |
100 |
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u1 + v4 = 10; 0 + v4 = 10; v4 = 10
u2 + v4 = 5; 10 + u2 = 5; u2 = -5
u2 + v3 = 2; -5 + v3 = 2; v3 = 7
u3 + v4 = 9; 10 + u3 = 9; u3 = -1
u3 + v2 = 3; -1 + v2 = 3; v2 = 4
u3 + v5 = 2; -1 + v5 = 2; v5 = 3
|
|
v1=5 |
v2=4 |
v3=7 |
v4=10 |
v5=3 |
|
u1=0 |
5[100] |
8 |
7 |
10[100] |
3 |
|
u2=-5 |
4 |
2 |
2[325] |
5[125] |
6 |
|
u3=-1 |
7 |
3[125] |
5 |
9[25] |
2[100] |