Контрольная работа - Решение транспортной задачи методом северо-западного угла - файл n1.doc

Контрольная работа - Решение транспортной задачи методом северо-западного угла
скачать (241.5 kb.)
Доступные файлы (1):
n1.doc242kb.07.11.2012 04:37скачать

n1.doc

Решение транспортной задачи методом северо-западного угла
Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности). Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из в груза , а в маленькие клетки — соответствующие тарифы . Для решения требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно методом «северо-западного угла». На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из или полностью удовлетворяется потребность .
Задача:

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов:

 

1

2

3

4

5

Запасы

1

7

4

8

3

6

70

2

5

5

4

3

8

80

3

5

6

5

8

6

90

Потребности

30

30

60

90

30





Решение:

1. Проверим необходимое и достаточное условие разрешимости задачи.
?a = 70 + 80 + 90 = 240
?b = 30 + 30 + 60 + 90 + 30 = 240
 Условие баланса соблюдается. Запасы равны потребностям.
2. Сущность метода:

Суть метода состоит в следующем: будем распределять груз, начиная с загрузки левой верхней, условно называемой северо-западной, клетки (1; 1), двигаясь затем от нее по строке вправо или по столбцу вниз. (Запасы обозначим «a», потребности – «b»)

В клетку (1; 1) занесем меньшее из чисел a 1, b 1, т.е. x 11 =min (a 1, b 1). Если а 1 >b 1, то x 11 =b 1 и первый потребитель В 1 будет полностью удовлетворен. В дальнейшем 1-й столбец таблицы в расчет не принимается; в нем переменные. Двигаясь вправо по первой строке таблицы, заносим в соседнюю клетку (1; 2) меньшее из чисел (a 1 - b 1) и b 2, т.е. x 12 = min ((a 1 - b 1), b 2). Если (a 1 - b 1) a 1 то х 11 =min (a 1, b 1) =а 1. При этом запас первого поставщика будет исчерпан, а потому. Первая строка из дальнейшего рассмотрения исключается. Переходим к распределению запасов второго поставщика. В клетку (2; 1) заносим наименьшее из чисел (a 2, b 1 - а 1). Заполнив таким образом клетку (1; 2) или (2; 1), переходим к загрузке следующей клетки по второй строке либо по второму столбцу. Процесс распределения по второй, третьей и последующим строкам (столбцам) производится аналогично распределению по первой строке или первому столбцу до тех пор, пока не исчерпаются ресурсы.

Ai* - излишек нераспределенного груза от поставщика Ai

Bj* - недостача в поставке груза потребителю Bj
3. Рассмотрим на конкретном примере:

Этап 1.  Занесем исходные данные в распределительную таблицу.

 

1

2

3

4

5

Запасы

1

7

4

8

3

6

70

2

5

5

4

3

8

80

3

5

6

5

8

6

90

Потребности

30

30

60

90

30





 Этап 2. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.


 


1


2


3


4


5


Запасы


1


7[30]


4[30]


8[10]


3


6


70


2


5


5


4[50]


3[30]


8


80


3


5


6


5


8[60]


6[30]


90


Потребности


30


30


60


90


30


 


Удовлетворим потребности Потребителя 1 [30], из оставшихся Запасов 1 удовлетворим потребности Потребителя 2; ему нужно 30, значит на складе Запасов 1 остается еще 10, которые можно отправить Потребителю 3.

Глядя на таблицу, видим, что Потребители 1 и 2 удовлетворены, а Потребитель 3 не полностью. Чтобы удовлетворить Потребителя 3 довезем ему Запасы 2 с другого склада [50], а оставшиеся на складе отправим Потребителю 4 [30]. У Потребителя 4 остались еще потребности, которые удовлетворяются Запасами 3. Оставшиеся на складе Запасы 3 отправляем Потребителю 5.

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

Важно: запасы должны быть израсходованы полностью, а потребители полностью удовлетворены.

Этап 3. Подсчитаем число занятых клеток таблицы, их 7, а должно быть

m + n - 1 = 7. (где m и n – потребители и запасы)

Следовательно, опорный план является невырожденным.
Этап 4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

Зная, что u1=0 можно найти v1, v2 и v3

(u1+v1=c11 (0+7)=7;

u1+v2=c12 (0+4=4);

u1+v3=c13 (0+8)=8)


 


v1=7


v2=4


v3=8


v4=


v5=


u1=0


7[30]


4[30]


8[10]


3


6


u2=


5


5


4[50]


3[30]


8


u3=


5


6


5


8[60]


6[30]


Далее найдем u2: u2+v3=c23 u2+8=4 u2=-4

Зная, что u2=-4 можно найти v4: u2+v4=c24 -4+v4=3 v4=7

Далее подобным образом (по цепочке) находим u3 и v5:

u3+v4=c34

u3+7=8

u3=1

u3+v5=c35

1+v5=6

v5=5

Таким образом получаем таблицу со следующими данными:


 


v1=7


v2=4


v3=8


v4=7


v5=5


u1=0


7[30]


4[30]


8[10]


3


6


u2=-4


5


5


4[50]


3[30]


8


u3=1


5


6


5


8[60]


6[30]


Вывод: опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij

 (1;4): 0 + 7 > 3

 (3;1): 1 + 7 > 5

 (3;3): 1 + 8 > 5
Этап 5. Выбираем максимальную оценку свободной клетки (1;4): 3
 Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

Пояснение: вершинами многоугольника считаются те клетки, в которых есть распределенный груз.


 


1


2


3


4


5


Запасы


1


7[30]


4[30]


8[10][-]



3[+]



6


70


2


5


5


4[50][+]



3[30][-]



8


80


3


5


6


5


8[60]


6[30]


90


Потребности


30


30


60


90


30


 


Этап 6. Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 10.

Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из, стоящих в минусовых клетках. В результате получим новый опорный план.



 


1


2


3


4


5


Запасы


1


7[30]


4[30]


8


3[10]


6


70


2


5


5


4[60]


3[20]


8


80


3


5


6


5


8[60]


6[30]


90


Потребности


30


30


60


90


30


 


Этап 7. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. (см. Этап 4)


 


v1=7


v2=4


v3=4


v4=3


v5=1


u1=0


7[30]


4[30]


8


3[10]


6


u2=0


5


5


4[60]


3[20]


8


u3=5


5


6


5


8[60]


6[30]


Вывод: Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij

(2;1): 0 + 7 > 5

(3;1): 5 + 7 > 5

(3;2): 5 + 4 > 6

(3;3): 5 + 4 > 5
Этап 8. Выбираем максимальную оценку свободной клетки (3;1): 5
 Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.


 


1


2


3


4


5


Запасы


1


7[30][-]


4[30]


8


3[10][+]


6


70


2


5


5


4[60]


3[20]


8


80


3


5[+]


6


5


8[60][-]


6[30]


90


Потребности


30


30


60


90


30


 

Этап 9. Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 30.

Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.


 


1


2


3


4


5


Запасы


1


7


4[30]


8


3[40]


6


70


2


5


5


4[60]


3[20]


8


80


3


5[30]


6


5


8[30]


6[30]


90


Потребности


30


30


60


90


30


 


Этап 10. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. (см. Этап 4)


 


v1=0


v2=4


v3=4


v4=3


v5=1


u1=0


7


4[30]


8


3[40]


6


u2=0


5


5


4[60]


3[20]


8


u3=5


5[30]


6


5


8[30]


6[30]


Вывод: Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij

 (3;2): 5 + 4 > 6

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



 


1


2


3


4


5


Запасы


1


7


4[30]


8


3[40]


6


70


2


5


5


4[60][-]


3[20][+]


8


80


3


5[30]


6


5[+]


8[30][-]


6[30]


90


Потребности


30


30


60


90


30


 


Этап 12. Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 30.

Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.


 


1


2


3


4


5


Запасы


1


7


4[30]


8


3[40]


6


70


2


5


5


4[30]


3[50]


8


80


3


5[30]


6


5[30]


8


6[30]


90


Потребности


30


30


60


90


30


 


Этап 13. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.


 


v1=4


v2=4


v3=4


v4=3


v5=5


u1=0


7


4[30]


8


3[40]


6


u2=0


5


5


4[30]


3[50]


8


u3=1


5[30]


6


5[30]


8


6[30]


Вывод: Опорный план является оптимальным.

Т.к. нет оценок свободных клеток для которых ui + vi > cij
Этап 14. Определим количество затрат. Затраты составят:
 F(x) = 4*30 + 3*40 + 4*30 + 3*50 + 5*30 + 5*30 + 6*30  = 990

Задача



Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов:

 

1

2

3

4

Запасы

1

1

7

3

6

21

2

7

1

1

4

26

3

3

3

7

3

25

4

1

3

5

5

24

Потребности

25

19

24

28





Решение:

1. Проверим необходимое и достаточное условие разрешимости задачи.
?a = 21+26+25+24=96
?b = 25+19+24+28=96
 Условие баланса соблюдается. Запасы равны потребностям.

2. Построим первый опорный план.

 

1

2

3

4

Запасы

1

1[21]

7

3

6

21

2

7[4]

1[19]

1[3]

4

26

3

3

3

7[21]

3[4]

25

4

1

3

5

5[24]

24

Потребности

25

19

24

28





3. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. (где m и n – потребители и запасы)

Следовательно, опорный план является невырожденным.

4. Проверим оптимальность опорного плана.

 

v1=1

v2=-5

v3=-5

v4=-9


u1= 0

1[21]

7

3

6


u2=6

7[4]

1[19]

1[3]

4


u3=12

3

3

7[21]

3[4]


u4=14

1

3

5

5[24]

u2+v1=c12 u2+1=7 u2=6

u2+v2=c22 6+v2=1 v2=-5

u2+v3=c23 6+v3=1 v3=-5

u3+v3=c33 u3+(-5)=7 u3=12

u3+v4=c34 12+v4=3 v4=-9

u4+v4=c44 u4+(-9)=5 u4=14
5. Оценим свободные клетки. для которых ui + vi > cij

(3;1) 12+1>3

(3;2) 12+(-5)>3

(4;1) 14+1>1

(4;2) 14+(-5)>3

Опорный план не является оптимальным.
6. Выбираем максимальную оценку свободной клетки (4;1): 1

 

1

2

3

4

Запасы

1

1[21]

7

3

6

21

2

7[4][-]

1[19]

1[3][+]

4

26

3

3

3

7[21][-]

3[4][+]

25

4

1[+]

3

5

5[24][-]

24

Потребности

25

19

24

28





7. Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 4.

Прибавляем 4 к объемам грузов, стоящих в плюсовых клетках и вычитаем 4 из, стоящих в минусовых клетках. В результате получим новый опорный план.

 

1

2

3

4

Запасы

1

1[21]

7

3

6

21

2

7

1[19]

1[7]

4

26

3

3

3

7[17]

3[8]

25

4

1[4]

3

5

5[20]

24

Потребности

25

19

24

28





8. Проверим оптимальность опорного плана.

 

v1=1

v2=15

v3=15

v4=5


u1= 0

1[21]

7

3

6


u2=-14

7

1[19]

1[7]

4


u3=-8

3

3

7[17]

3[8]


u4=0

1[4]

3

5

5[20]


9. Оценим свободные клетки. для которых ui + vi > cij

(1;2) 0+15>7

(1;3) 0+15>3

(3;2) -8+18>3

(4;2) 0+15>3

(4;3) 0+15>5

Опорный план не является оптимальным.
10. Выбираем максимальную оценку свободной клетки (1;3): 3

 

1

2

3

4

Запасы

1

1[21][-]

7

3[+]

6

21

2

7

1[19]

1[7]

4

26

3

3

3

7[17][-]

3[8][+]

25

4

1[4][+]

3

5

5[20][-]

24

Потребности

25

19

24

28





11. Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 17.

Прибавляем 17 к объемам грузов, стоящих в плюсовых клетках и вычитаем 17 из, стоящих в минусовых клетках. В результате получим новый опорный план.

 

1

2

3

4

Запасы

1

1[4]

7

3[17]

6

21

2

7

1[19]

1[7]

4

26

3

3

3

7

3[25]

25

4

1[21]

3

5

5[3]

24

Потребности

25

19

24

28




12. Проверим оптимальность опорного плана.

 

v1=1

v2=3

v3=3

v4=5


u1= 0

1[4]

7

3[17]

6


u2=-4

7

1[19]

1[7]

4


u3=-8

3

3

7

3[25]


u4=0

1[21]

3

5

5[3]


Опорный план является оптимальным.
13. Затраты составят:  F(x) = 1*4 + 3*17 + 1*19 + 1*7 + 3*25 + 1*21 + 5*3  = 192




Учебный материал
© bib.convdocs.org
При копировании укажите ссылку.
обратиться к администрации