Решение транспортной задачи

Автор работы: Пользователь скрыл имя, 07 Октября 2011 в 22:08, задача

Краткое описание

Решение транспортной задачи.

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

Скачать целиком (37.61 Кб) Сколько стоит заказать работу?
Содержимое работы - 1 файл

контр.docx

— 40.65 Кб (Скачать файл)
 

3*220 + 6*20 + 6*100 + 3*160 + 2*140 + 3*170 + 5*90  = 3100

Шаг 4. Определяем оценку для каждой свободной клетки.

(1;2): В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  
 

  1 2 3 4 5 Запасы
1 3[220] 6[+] 6[20] 6[100][-] 6 340
2 1 2 3[160] 4 2[140] 300
3 4 3[170][-] 8 5[90][+] 6 260
Потребности 220 170 180 190 140  
 

Цикл приведен в таблице (1,2; 1,4; 3,4; 3,2; ).

Оценка свободной  клетки равна Δ12 = 2.

(1;5): В свободную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

  1 2 3 4 5 Запасы
1 3[220] 6 6[20][-] 6[100] 6[+] 340
2 1 2 3[160][+] 4 2[140][-] 300
3 4 3[170] 8 5[90] 6 260
Потребности 220 170 180 190 140  
 

Цикл приведен в таблице (1,5; 1,3; 2,3; 2,5; ).

Оценка свободной  клетки равна Δ15 = 1.

(2;1): В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

  1 2 3 4 5 Запасы
1 3[220][-] 6 6[20][+] 6[100] 6 340
2 1[+] 2 3[160][-] 4 2[140] 300
3 4 3[170] 8 5[90] 6 260
Потребности 220 170 180 190 140  
 

Цикл приведен в таблице (2,1; 2,3; 1,3; 1,1; ).

Оценка свободной  клетки равна Δ21 = 1.

(2;2): В свободную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

  1 2 3 4 5 Запасы
1 3[220] 6 6[20][+] 6[100][-] 6 340
2 1 2[+] 3[160][-] 4 2[140] 300
3 4 3[170][-] 8 5[90][+] 6 260
Потребности 220 170 180 190 140  
 

Цикл приведен в таблице (2,2; 2,3; 1,3; 1,4; 3,4; 3,2; ).

Оценка свободной  клетки равна Δ22 = 1.

(2;4): В свободную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

  1 2 3 4 5 Запасы
1 3[220] 6 6[20][+] 6[100][-] 6 340
2 1 2 3[160][-] 4[+] 2[140] 300
3 4 3[170] 8 5[90] 6 260
Потребности 220 170 180 190 140  
 

Цикл приведен в таблице (2,4; 2,3; 1,3; 1,4; ).

Оценка свободной  клетки равна Δ24 = 1.

(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

  1 2 3 4 5 Запасы
1 3[220][-] 6 6[20] 6[100][+] 6 340
2 1 2 3[160] 4 2[140] 300
3 4[+] 3[170] 8 5[90][-] 6 260
Потребности 220 170 180 190 140  
 

Цикл приведен в таблице (3,1; 3,4; 1,4; 1,1; ).

Оценка свободной  клетки равна Δ31 = 2.

(3;3): В свободную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  
 

  1 2 3 4 5 Запасы
1 3[220] 6 6[20][-] 6[100][+] 6 340
2 1 2 3[160] 4 2[140] 300
3 4 3[170] 8[+] 5[90][-] 6 260
Потребности 220 170 180 190 140  
 

Цикл приведен в таблице (3,3; 3,4; 1,4; 1,3; ).

Оценка свободной  клетки равна Δ33 = 3.

(3;5): В свободную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

  1 2 3 4 5 Запасы
1 3[220] 6 6[20][-] 6[100][+] 6 340
2 1 2 3[160][+] 4 2[140][-] 300
3 4 3[170] 8 5[90][-] 6[+] 260
Потребности 220 170 180 190 140  
 

Цикл приведен в таблице (3,5; 3,4; 1,4; 1,3; 2,3; 2,5; ).

Оценка свободной  клетки равна Δ35 = 2.

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

Таким образом, последний опорный план является оптимальным.

Минимальные затраты  составят:

3*220 + 6*20 + 6*100 + 3*160 + 2*140 + 3*170 + 5*90  = 3100

Все вычисления и комментарии к полученным результатам  доступны в расширенном режиме.

Информация о работе Решение транспортной задачи