Математика (стр. 13 )

W W2 W4 W6 W8

х4х1 х1х6 х6х3 х3х2

j1 = 97 j3= 161 j5=130 j7=112

W1 W3 W5 W7

х4х1 х1х6 х6х3 х3х2

Рис. 6

Если включить в маршрут единственно возможные в матрице W8 дуги х2х5 и х5х4, то вместе с дугами х4х1(W2), х1х6(W4), х6х3(W6) и х3х2(W8) они будут образовывать замкнутый маршрут

х2 ® х5 ® х4 ® х1 ® х6 ® х3 ® х2

Так как две дуги, последними включенные в маршрут, имеют нулевые длины в матрице W8, то длина полученного замкнутого маршрута L совпадет с нижней границей множества равной 102. Предлагается проверить это самостоятельно по исходной матрице расстояний.

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

Проверка оптимальности решения

Для проверки сравним длину полученного замкнутого маршрута равную 102, с нижними границами концевых множеств последней схемы ветвления (рис. 13). При этом отсекаются все концевые множества, имеющие нижнюю границу ji ³ j8 В нашем случае такими множествами, подлежащими отсечению, будут множества W3(j3 = 161), W5(j5 = 130), W7(j7 = 112)

Схему ветвления с отсечениями покажем на рис. 7. Он является по существу повторением рис. 6, но с отсечениями, отмеченными знаком ´. В контрольной работе рис. 6 и рис. 7 можно объединить в один рисунок.

После операции отсечения могут возникнуть два случая.

1. Все концевые множества оказались отсеченными. Это означает, что найденный маршрут является искомым, то есть имеет минимальную длину.

2. Есть концевые множества Wi, нижние границы которых меньше длины найденного маршрута. В этом случае выбираем не отсеченное концевое множество с наименьшей нижней границей и применяем к нему общий шаг описанного алгоритма (ветвление и вычисление нижних границ вновь полученных множеств). На этом этапе после каждого применения общего шага следует сравнивать нижние границы вновь полученных множеств с длиной полученного замкнутого маршрута.

В нашем случае осталось не отсеченным одно множество - множество W1 с нижней границей j1=97 £ 102 = j8.

j=75 j2=93 j4=93 j6=102 j8=102

W W2 W4 W6 W8

х4х1 х1х6 х6х3 х3х2

j1=97 j3=161 j5=130 j7=112

W1 W3 W5 W7

х4х1 х1х6 х6х3 х3х2

рис.7

В соответствии с алгоритмом переходим к общему шагу. Напомним, что матрица W1 получена из матрицы W0 запретом дуги х4х1 (вместо элемента а41 поставлен прочерк ²—² табл. 5). Матрица W1 не является приведенной. Произведя операцию приведения, получим матрицу (табл. 12).

	А1	А2	А3	А4	А5	А6
А1	¾	59	64	0	61	0
А2	42	¾	5	18	0	81
А3	49	0	¾	62	4	9
А4	¾	0	42	¾	18	36
А5	52	15	0	27	¾	55
А6	0	71	0	34	37	¾

Таблица 12 (матрица W01 )

По соображениям, указанным выше, для ветвления выбираем дугу нулевой длины х6х1. При этом множество W1 разбивается на два подмножества W9 = W1(х6х1) и W10=W1(х6х1) Нижняя граница j9 множества W9 = W1 (х6х1) будет больше нижней границы j1 множества на сумму постоянных приведения, равную 42, то есть

j9 = j1 + 42 = 97 + 42= 139.

Для того, чтобы получить нижнюю границу множества W10, из матрицы следует вычеркнуть шестую строку и первый столбец и заменить элемент а прочерком “—“. Проделав это, получим матрицу W10(табл. 13, см. на следующей стр.).

Нижняя граница множества W10 будет больше нижней границы j1 множества W1 на 9 единиц, то есть

j10 = j1 + 9 = 97 + 9 = 106

Схема ветвления, соответствующая описанному выше разбиению, изображена на рис. 8.

W1 W j=75

j1=97 W2 j2=93

х4х1 х4х1

W9 j9=139 W10 j10=106 W3 j3=161 W4 j4=93

х6х1 х6х1 х1х6 х1х6

W5 j5=130 W6 j6=102

х6х3 х6х3

W7 j7=112 W8 j8=102

х3х2 х3х2

рис.8

Так как полученные нижние границы множеств W9 и W10, равные соответственно 139 и 106, выше нижней границы j8 = 102 множества W8, по которому уже составлен замкнутый маршрут проходящий все пункты ровно по одному разу, то в соответствии с алгоритмом, эти концевые множества должны быть отсечены. На рис. 15 они отмечены знаком х.

	А2	А3	А4	А5	А6	min
А1	59	64	0	61	¾	0
А2	¾	5	18	0	81	0
А3	0	¾	62	4	9	0
А4	0	42	¾	18	36	0
А5	15	0	27	¾	55	0
min	0	0	0	0	9

Таблица 13 (матрицаW10 (х6х1))

В нашей схеме (рис. 15) не осталось не отсеченных концевых множеств. Следовательно, найденный нами маршрут

х2 ® х5 ® х4 ® х1 ® х6 ® х3 ® х2

является искомым, то есть кратчайшим замкнутым маршрутом, проходящим ровно по одному разу через каждый из шести городов, и длина этого маршрута равна 102.

Контрольная работа № 4

1—20. Следующие задачи решить графически

1. 3х1 - х2 £ 3, 2. -3x1 + 2x2 £ 6 ,

x1 - х2 ³ -1, x1 + x2 £ 3 ,

2х1 + х2 £ 4, x1 £ 4,

x1 + 2х2 ³ -2, x1 - x2 ³ 0 ,

х1 ³ 0, х2 ³ 0, x1 ³ 0, x2 ³ 0

¦ (Х) = х1 + 4х2 ¾ max. ¦ (X) = 3x1 - 2x2 ¾ max.

3. x1 - 4x2 £ 16 , 4. x1 + x2 ³ 12 ,

2x1 + 3x2 ³ 12 , x1 £ 6 ,

x1 - x2 ³ 0 , x2 ³ 6 ,

x1 - 4x2 £ 12 , -2x1 + 3x2 £ 42 ,

x1 ³ 0 , x2 ³ 0 , x1 ³ 0 , x2 ³ 0 ,

¦ (X) = 5x1 - x2 ¾ min. ¦ (X) = 4x1 + 3x2 ¾ max.

5. х1 - 2х2 £ -4, 6. - х1 +2х2 £ 2,

х1 - х2 £ 1, - х1 + 2х2 ³ -1,

х2 ³ 1, х2 £ 2,

х1 + х2 ³ 5, х1 + х2 ³ -2,

х1 ³ 0, х2 ³ 0, х1 ³ 0, х2 ³ 0,

¦ (Х) = - х1 +3х2 ¾- min ¦ (Х) = 3х1 - 2х2 ¾ max

7. х1 + 2х2 ³ 5, 8. 4х1 + 3х2 ³ 12,

х1 £ 5, х1 £ 3,

х2 £ 4, х2 £ 5,

х1 + 2х2 £ 7, 5х1 + х2 ³ 5,

х1³ 0, х2 ³ 0, х1 ³ 0, х2 ³ 0,

¦ (Х) = 2х1 - 3х2 ¾ min ¦ (Х) = 2х1 + 3х2 ¾ max

9. х1 + 2х2 ³ 1, 10. х1 - х2 ³ 1,

-3х1 + х2 £ 1, х1 + 2х2 ³ 2,

х1 + х2 £ 2, х1 + х2 £ 4,

х1 ³ 0, х2 ³ 0, х1 ³ 0 , х2 ³ 0 ,

¦ (Х) = х1 - х2 ¾ min ¦ (Х) = - х1 + 4х2 ¾ max

11. х1 + х2 £ 4, 12. - х1 + 2х2 £ 2 ,

х1 £ 3 -2х1 + 3х2 ³-6 ,

х1 + х2 ³ 0, 10х1 + 7х2 £63 ,

х1 ³ 0 , х2 ³ 0 , х1 ³ 0 , х2 ³ 0 ,

¦ (Х) = 5х1 - 2х2 ¾ max ¦ (Х) = -3х1 + х2 ¾ min

13. 3х1 + 2х2 ³6 , 14. х1 +2х2 £ 10,

х1 £ 4 , 2х1 + х2 £ 10,

х2 £ 4 , х1 + 3х2 ³ 3,

х1 + х2 £ 6 , 5х1 - х2 ³ -5,

х1 ³ 0 , х2 ³ 0 , х1 ³ 0, х2 ³ 0,

¦ (Х) = 2х1 - 5х2 ¾ max ¦ (Х) = х1 + х2¾ max

15. х1 + 3х2 ³ 7, 16. - х1 + 3х2 ³ 3 ,

3х1 + 2х2 ³ 21/2 , х1 £ 2 ,

х1 - 2х2 £ 4, - х1 + 3х2 ³ 3 ,

х1 ³ 0 , х2 ³ 0, х1 ³ 0 , х ³ 0,

¦ (Х) = х1 + х2 ¾ min. ¦ (Х) = х1 - х2 ¾ max.

17. х1 + х2 ³ 0, 18. х1 - х2 £ 10,

х1 + х2 £ 3, 5х1 - х2 ³ 10

х1 + 3х2 £ 5, х1 ³ 3,

5х1 - х2 £ 5, х1 + х2 £ 12,

х1 ³ 0, х2 ³ 0, х1 ³ 0, х2 ³ 0,

¦(Х) = 2х1 + х2 ¾ max. ¦(Х) = 3х1 + 4х2 ¾ max.

19. -2х1 + 3х2 £ 6, 20. х1 - х2 ³ -2,

х1 + х2 £ 6, 3х1 + 2х2 ³ 6,

-2х1 + х2 £ -6, 3х1 + х2 £ 10,

х1 ³ 0, х2 ³ 0, х1 ³ 0, х2 ³ 0,

¦(Х) = - х1 + 2х2 ¾ max. ¦(Х) = 2х1 - 3х2 ¾ m

Решить транспортную задачу. Заданы мощности поставщиков ai(i = 1,2,3), емкости потребителей bj ( j= 1,2,3) и матрица стоимостей перевозок единицы продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, при котором суммарные транспортные затраты будут наименьшими.

2.
bj ai	25	40	35
20	3	6	4
90	5	9	3
60	4	8	6

3.
bj ai	16	20	35
15	6	7	5
8	5	6	4
20	9	10	6

4.
bj ai	20	12	8
22	7	6	3
12	8	4	2
16	2	3	1

1.
bj ai	40	120	170
90	5	6	8
65	6	9	10
75	4	7	5

5.
bj ai	19	31	10
20	5	8	3
10	2	4	2
12	7	6	3
6.
bj ai	14	20	22
50	3	8	9
18	3	4	5
12	2	7	6

7.
bj ai	20	18	17
30	9	7	4
15	5	3	2
45	10	8	5
8.
bj ai	18	40	12
32	9	8	4
15	8	7	3
7	4	3	2

12.
bj ai	40	12	20
17	8	4	9
30	6	3	7
15	5	2	4

11.
bj ai	14	20	30
25	4	5	9
10	2	3	3
12	4	6	8

9.
bj ai	17	13	25
20	8	3	6
15	4	2	5
30	9	4	7

10.
bj ai	12	19	9
18	5	8	2
22	8	9	4
15	6	7	3

13.
bj ai	17	21	8
24	5	7	4
16	4	8	3
20	6	9	4

14.
bj ai	20	12	37
15	5	3	7
10	3	2	3
24	6	4	8

15.
ai bj	10	7	18
15	6	3	7
18	4	2	9
12	5	3	8

16.
bj ai	9	31	20
20	3	9	8
14	4	6	7
12	2	4	5

20.
bj ai	21	30	32
16	5	9	7
32	4	6	5
20	3	5	4

19.
bj ai	25	19	21
40	5	3	6
17	2	1	2
23	7	4	8

18.
bj ai	20	14	16
30	5	2	6
15	2	1	3
25	4	2	8

17.
bj ai	20	10	30
35	6	3	7
15	3	2	4
20	5	4	8

Найти оптимальные стратегии и цену игры, заданной платежной матрицей А. Сделать проверку.