Раздел III. Игровые задачи

Задача 7.(№7.1- 7.100). Требуется решить точным и приближенным методами (20 итораций) игру, заданную платежной матрицей.

 

7.1 7.2 7.3 7.4

-3 2 2 1 3 7 3 9 8 9 6 9 2 10 5 3 3 5 3 3

4 0 -1 5 5 2 0 8 7 3 2 6 -3 8 13 2 3 4 -1 2

2 4 3 2 1 6 1 6 2 9 4 6 -1 7 5 2 0 2 2 3

-4 4 2 1 2 5 4 2 3 8 3 3 3 3 3 4 4 0 5 5

-1 3 3 -2 1 6 4 6 1 8 7 8 7 9 2 4 4 4 0 2

7.5 7.6 7.7 7.8

3 3 -2 6 4 - 1-4 0 -2 2 2 -1 3 4 5 -5 2 -5 7 3

-1 2 -3 6 2 7 4 0 1 4 5 4 -5 6 -3 4 3 4 6 3

2 1 -6 2 1 5 3 -2 0 3 -3 4 2 -1 3 -2 8 3 4 8

-3 5 1 4 6 6 -6 7 -3 9 7 6 -5 7 -5 6 5 0 7 8

-2 4 -4 -1 4 4 -7 7 1 6 -4 3 0 -3 1 1 1 2 5 2

7.9 7.10 7.11 7.12

-3 -4 -2 -6 -7 3 -3 1 -4 -2 4 3 3 -1 0 -2 -2 2 3 -3

1 0 -1 0 -3 1 3 -4 5 4 -5 4 1 4 4 2 -1 3 5 0

3 -4 1 1 -2 4 -3 2 -2 -1 -4 2 2 5 5 -2 3 4 6 4

-4 -5 -2 -3 -3 -1 4 3 4 5 5 -3 -4 3 4 3 2 -4 -2 2

-8 3 -1 -6 -7 1 5 -3 6 6 3 3 2 -1 1 -5 3 3 2 -4

7.13 7.14 7.15 7.16

-2 3 -2 3 -2 -5 3 1 2 -6 1 -3 1 2 -6 1 3 5 -6 -4

5 -1 3 1 5 1 0 1 2 0 4 3 2 -3 1 5 -2 2 3 4

1 3 4 4 1 0 -3 0 -1 0 -1 5 -1 5 4 -1 2 -4 6 7

0 -1-22 2 0 -1 2 -1 -2 -5 3 -3 2 3 -5 8 3 7 -5 -3

3 2 -5 3 4 2 2 -2 0 -2 5 0 -2 4 3 -3 2 -5 4 1

7.17 7.18 7.19 7.20

2 -1 0 1 3 4 0 -2 3 5 -2 3 0 4 5 1 -4 1 -3 -5

1 9 0 1 1 3 0 -1 4 7 -1 4 0 5 7 2 3 4 3 0

6 7 8 8 9 5 -1 -2 2 4 -2 2 -1 3 4 0 -1 -2 -2 1

9 8 1 1 2 5 3 4 2 6 3 2 -3 5 6 -3 3 3 2 -2

3 9 4 6 5 6 1 -2 4 8 2 -4 1 6 8 -4 5 3 1 2

7.21 7.22 7.23 7.24

2 4 1 6 8 8 -3 4 5 -3 1 5 -3 4 -2 6 -5 2 3 -5

-2 3 0 4 5 4 2 -3 1 1 6 5 5 1 4 2 0 -5 2 -1

3 2 -3 5 6 9 -2 5 3 -1 2 -1 2 -2 5 7 0 3 1 -3

-1 4 5 5 7 10 10 16 8 -3 3 7 -1 7 1 8 -1 14 -1 2

-2 2 -1 3 4 2 1 -4 1 0 3 4 -1 -1 2 0 -1 6 1 1

7.25 7.26 7.27 7.28

4 2 7 2 7 0 1 5 5 4 1 2 -7 7 2 3 3 -5 -4 -5

14 13 -3 13 -2 0 2 3 4 2 -1 -1 -7 2 -1 5 5 -5 -3 -6

3 3 3 4 4 4 4 0 0 4 1 1 -4 0 1 -2 1 0 1 5

5 5 2 5 2 3 5 2 5 2 -3 2 -6 7 -3 2 3 -1 1 3

3 3 3 3 5 5 6 3 4 3 -4 1 -6 2 -3 4 -1 2 -3

7.29 7.30 7.31 7.32

0 -6 1 -1 -2 1 6 2 7 6 6 0 1 1 2 0 -1 0 -1 -2

0 -5 1 -1 -1 1 5 1 7 3 5 6 6 -2 6 0 1 1 -1 0

-10 -1 1 -1 -8 2 3 3 5 -3 5 0 0 0 1 2 2 1 1 0

-1 -3 1 -1 -2 3 -2 4 -2 4 4 3 4 3 4 -4 -1 -1 -1 2

-2 -3 0 -2 -3 3 4 4 4 -2 4 3 2 -2 5 -3 2 -2 1 2

7.33 7.34 7.35 7.36

0 1 -6 -3 0 1 2 -3 2 0 -2 2 0 1 3 4 1 2 1 -2

-3 2 -1 1 0 2 1 -3 3 2 -4 2 0 -1 1 -4 2 1 1 0

0 0 -5 -2 1 -5 0 1 -4 0 5 -1 -3 5 -2 10 3 1 0 2

2 2 1 1 -1 -1 2 0 1 3 -4 3 0 2 1 15 3 0 0 3

0 -1 -6 -4 0 3 2 -3 3 2 -1 2 3 1 3 -4 3 2 1 0

7.37 7.38 7.39 7.40

4 1 3 -3 2 -1 4 4 3 5 5 1 7 6 7 4 7 0 8 3

3 1 3 -4 0 6 2 1 7 7 0 -2 6 5 6 3 4 -5 6 11

1 2 5 -3 -1 4 6 5 4 3 4 -1 4 0 7 2 4 -3 5 3

0 -3 1 2 -1 -2 6 4 3 4 3 2 0 1 6 1 1 1 1 1

4 2 3 -2 1 3 5 5 0 3 4 2 4 -1 6 5 6 5 7 0

7.41 7.42 7.43 7.44

1 1 3 1 1 5 5 0 8 6 -3 -6 -2 -4 0 0 -1 1 -3 -4

0 1 2 -3 0 1 4 -1 8 4 5 2 -2 -1 2 4 3 2 3 0

0 -2 0 0 1 4 3 -4 4 3 3 1 -1 -2 1 6 -1 4 4 1

2 2 -2 3 3 -1 7 3 6 8 4 -8 5 -5 7 -1 -2 1 0 0

2 2 2 -2 0 0 6 -2 1 6 2 -9 5 -1 4 -5 6 2 -3 -4

7.45 7.46 7.47 7.48

1 -5 -1 -6 -4 -4 1 -4 1 -4 0 -4 0 1 -7 -2 -5 -4 -3 -1

-1 1 -6 3 2 3 -5 1 -1 3 3 2 1 -4 0 -3 5 -4 -3 -3

2 -5 0 -4 -3 -1 1 2 2 -1 -2 4 -2 4 3 2 3 4 4 5

-3 2 1 2 3 -2 -3 -25 0 -2 2 -4 1 2 -6 5 4 -3 -3 -2

-1 3 -5 4 4 1 0 -7 1 2 4 -1 -3 3 2 -1 5 0 2 3

7.49 7.50 7.51 7.52

0 -5 0 -4 -6 -2 2 -6 1 -5 6 2 1 7 7 1 0 1 3 0

1 2 3 2 -1 3 2 2 -2 1 0 4 4 3 5 -8 -5 -8 4 0

-1 -2 -3 -3 0 -1 -4 -1 -5 -2 -2 6 4 3 4 3 2 -3 4 5

-4 2 2 1 -3 0 4 -4 4 -2 -4 6 5 4 5 -5 5 0 1 5

-5 4 2 0 1 0 4 -4 -4 -1 3 5 5 3 3 -2 -2 -1 2 -1

7.53 7.54 7.55 7.56

1 -1 1 1 2 3 1 3 -2 6 2 7 3 -1 6 -4 1 1 2 4

2 2 4 2 2 2 1 -1 0 5 10 5 2 -6 3 -5 0 -3 0 4

1 2 3 -2 1 4 0 6 5 6 2 4 1 -4 3 -8 -1 0 -1 0

3 3 3 -1 1 3 1 3 -2 5 -1 3 -2 0 2 -1 -13 -5 -4 2

3 3 -1 4 4 -1 -3 5 4 5 -1 6 4 4 5 -6 2 -4 2 -3

7.57 7.58 7.59 7.60

1 0 -3 3 -1 -3 4 0 -4 2 -9 2 -2 -7 -8 4 3 -4 4 5

1 8 5 5 2 3 0 4 5 6 -4 -5 -3 -7 -8 -1 4 -1 4 -1

-1 6 4 4 0 6 5 -4 7 -2 -5 -6 -3 -4 -4 1 0 -21 3 1

8 7 -5 10 -2 8 7 -4 8 -4 0 -1 -2 -1 -4 6 0 4 2 6

8 5 -6 7 2 -2 5 3 0 4 2 -5 0 0 -3 2 4 5 5 2

7.61 7.62 7.63 7.64

4 -1 -3 3 3 -2 -8 -6 3 3 3 3 -1 1 -1 2 2 1 -2 0

0 -4 0 1 -7 0 -6 -2 -6 -4 -4 4 3 -6 3 3 2 2 -2 -1

2 -4 1 2 -6 -1 0 -7 2 1 1 -2 1 0 1 -6 3 0 3 3

-2 4 -2 4 3 -3 1 0 1 2 2 1 2 3 1 -5 1 1 4 4

3 2 1 -4 -1 1 -4 -1 -5 -4 0 3 0 -1 -4 4 -4 -5 2 3

7.65 7.66 7.67 7.68

3 1 -6 5 -4 4 1 5 7 2 5 0 -3 3 7 7 1 5 3 0

-2 5 3 -2 4 3 0 4 5 -1 3 -1 -3 2 4 4 -3 3 2 -1

2 -1 6 2 7 0 5 6 8 6 4 -2 -3 1 3 5 2 4 1 -4

5 10 -3 7 -1 -3 5 5 4 -2 2 -1 -2 3 6 6 -2 4 3 4

2 -3 4 -5 1 5 4 -2 0 4 4 2 3 1 5 3 1 2 1 2

7.69 7.70 7.71 7.72

2 8 3 5 4 -3 6 4 2 3 4 2 -3 -1 3 5 -1 2 6 -2

1 -2 -1 0 2 3 4 4 4 1 6 3 -2 -1 4 2 5 7 6 6

8 7 0 0 1 2 -3 2 -2 -4 3 1 -3 -2 2 -1 6 3 0 3

0 8 -1 0 0 -2 4 4 3 -1 5 1 2 -4 4 8 2 4 8 0

5 6 7 7 8 2 0 1 -1 5 7 -5 1 0 5 0 3 4 5 0

7.73 7.74 7.75 7.76

-3 2 -1 2 -3 -4 4 4 -3 -3 -1 10 7 6 1 3 8 -6 3 2

8 -8 9 -8 8 -4 6 6 -2 -2 3 6 3 -1 1 0 3 -6 0 0

-1 -2 -2 -1 -2 1 2 -1 2 2 1 11 5 7 2 -4 1 -3 2 2

0 -3 0 0 0 0 4 3 2 2 -1 12 10 18 5 -2 8 -5 3 -2

-2 -2 -2 -2 -2 0 5 -2 3 3 2 4 3 -2 1 3 4 -5 2 -3

7.77 7.78 7.79 7.80

-2 -3 1 2 2 -1 -2 5 0 0 -1 -2 1 -1 -2 1 0 -1 -5 2

-1 -3 -1 1 0 5 -6 1 2 -6 1 -5 2 0 -1 3 -3 -2 -2 -1

1 1 1 -3 -3 1 -1 -6 1 -2 0 -2 2 0 -1 2 3 3 -5 3

2 0 -2 -1 -1 6 -1 2 0 -4 -9 0 2 0 -7 3 -3 -3 -3 -2

3 2 0 1 2 7 -2 13 -2 1 1 -4 2 0 0 1 0 1 2 1

7.81 7.82 7.83 7.84

4 -2 -4 4 -3 4 2 5 -2 3 0 0 5 5 6 -5 1 2 1 -2

-3 1 -1 0 2 4 2 4 -3 1 -1 0 4 2 6 0 -2 3 1 2

-5 1 -1 -2 0 6 3 2 -2 0 1 1 2 -4 4 -4 1 1 2 -1

-5 2 -1 1 0 2 -2 1 3 0 2 2 -3 3 -3 2 3 3 0 2

-2 1 2 0 2 4 3 5 -1 2 2 2 3 -3 3 -5 1 0 1 -3

7.85 7.86 7.87 7.88

2 2 -3 3 1 3 3 2 2 1 5 3 -1 5 4 -2 0 -3 -6 -3

-1 0 4 5 5 1 0 1 0 -1 4 -2 -4 4 3 -3 -8 -2 -4 -3

3 4 2 1 2 -3 0 0 0 3 2 2 -3 5 -2 -3 6 -1 -2 -4

2 4 -4 2 1 1 2 2 0 1 -2 1 0 4 -1 -3 11 -1 -1 -4

1 3 1 1 -2 -2 3 -1 1 3 2 2 0 4 -3 -2 -8 -1 -4 -3

7.89 7.90 7.91 7.92

-2 2 3 1 3 2 0 0 0 0 4 -3 2 -2 -1 -1 -3 1 -5 -2

-2 3 2 3 4 1 -1 0 -1 -4 1 3 -4 5 4 -1 0 3 3 6

2 -4 1 1 -3 -1 -1 -3 0 -1 3 -3 1 -4 -2 -3 -1 2 2 4

1 0 3 4 2 -3 1 1 2 2 1 5 -3 6 6 6 -4 8 -7 5

-2 4 3 3 4 1 1 1 -1 -1 -1 4 3 4 5 6 0 5 -8 3

7.93 7.94 7.95 7.96

6 1 -2 2 5 8 1 6 6 3 3 2 -5 3 2 -4 -3 3 4 0

4 9 -7 1 2 1 0 3 2 2 -2 6 2 4 7 4 3 0 4 5

3 1 -5 0 2 -3 4 4 -1 -2 -1 5 -3 0 5 -3 4 -3 -2 1

-1 -1 -1 -1 -1 6 5 4 5 2 4 4 -1 7 4 -2 0 6 6 2

5 -2 3 3 4 2 1 3 -1 -2 0 3 -2 7 3 -2 1 -2 3 2

 

7.97 7.98 7.99 7.100

-6 1 -3 1 2 -1 7 -2 -1 -1 1 -5 -3 1 -4 -5 -3 2 2 -3

1 4 3 2 -3 4 5 6 6 7 4 0 3 2 3 2 4 0 -2 4

4 -1 5 -1 5 0 -3 -2 -1 1 -2 1 -2 0 -1 3 0 3 2 0

-5 3 -3 2 3 1 7 2 4 5 3 -2 2 -3 3 -24 -1 1 -2 -1

3 5 0 -2 4 7 6 -1 -1 0 3 2 1 -4 5 -6 3 2 1 2

 

Задача 8. (8.1- 8.100). Требуется по приведенным условиям составить платежную матрицу и найти решение игровой задачи.

8.1 -8.10. На контроль поступает партия из 10 изделий, в которой не более двух бракованных. Контролю можно подвергнуть не более двух изделий. Стоимость контроля одного изделия a руб. В эксплуатации бракованные изделия неизбежно обнаруживаются. За каждое обнаруженное бракованное изделие изготовитель платит штраф b руб. Найти оптимальную стратегию контроля.

№
a
b

8.11- 8.20. Каждая из фирм А и В может открыть магазин в одном из населенных пунктов Р₁, Р₂, Р₃, Р₄, численность населения и расположение которых указаны на рисунке . Если магазин фирмы А находится ближе (

дальше) магазина фирмы В от данного пункта, то его услугами пользуется a (b) процентов населения этого пункта, а остальные пользуются услугами конкурента. Если магазины находятся на одинаковом расстоянии от данного пункта, то 50% населения обращается в магазин А, остальные – в магазин В. Определить оптимальные стратегии фирм А и В, считая их целью «захват» наибольшего числа покупателей.

Р₁ ___^{10 км}_____ Р₂____^{d км}____ Р₃__ ^{25 км}______ Р₄

8 тыс. 10 тыс. g тыс. 15 тыс

№
a
b
g
d

 

8.21 – 8.30. Каждый из спортивных клубов К₁ и К₂ располагает тремя волейбольными командами. На соревнованиях каждый клуб может выставить любую их трех команд. При подаче заявок выбор противника неизвестен. Результаты предыдущих встреч клубных команд приведены в таблицах. Определить оптимальное поведение клубов.

№ 21

К1
К2
	в	п	в	п	в	п

№ 22

К1
К2
	в	п	в	п	в	п

 

№ 23

К1
К2
	в	п	в	п	в	п

№ 24

К1
К2
	в	п	в	п	в	п

№ 25

К1
К2
	в	п	в	п	в	п

№ 26

К1
К2
	в	п	в	п	в	п

 

№ 27

К1
К2
	в	п	в	п	в	п

№ 28

К1
К2
	в	п	в	п	в	п

№ 29

К1
К2
	в	п	в	п	в	п

№ 30

К1
К2
	в	п	в	п	в	п

8.31- 8.40.Предприятие изготовляет механизм, состоящий из двух блоков. Стоимость испытания одного блока равна a руб. Перед сдачей заказчику предприятие может испытать 0,1,2 блока. Заказчик может сам провести испытания такого числа блоков. Если он обнаруживает неисправность, то изготовитель обязан:

1. Оплатить заказчику стоимость испытаний;
2. Выплатить штраф в сумме b руб. за каждый неисправный блок;
3. Испытать за свой счет оставшийся блок и устранить неисправности.

Вероятность неисправности блока равна r. Определить оптимальные стратегии сторон.

№
a		0,3		0,5	1,5			0,5
b
r	0,1	0,2	0,3	0,2	0,25	0,3	0,15	0,2	0,1	0,2

 

8.41- 8.50. Две шахматные команды по 3 человека встречаются в матче по две партии. Каждая команда может выбрать двух игроков и порядок досок., на которых они будут играть. Результаты предыдущих встреч позволяют предсказать исходы некоторых индивидуальных поединков («+» - победа,

«- « - поражение, «0» - ничья). Определить оптимальные стратегии команд, оценивая выигрыши, проигрыши и ничьи в каждой партии соответственно в 1, -1, 0 очков.

 

№ 41 № 42 № 43 № 44 № 45

II

Е

F

G

II

E

F

G

II

E

F

G

II

E

F

G

II

E

F

G

I

I

I

I

I

А

+

А

+

А

+

-

+

А

+

-

А

+

-

В

-

В

+

-

В

-

+

-

В

+

-

В

С

-

+

+

С

-

С

-

+

С

-

+

С

-

+

+

№ 46 № 47 № 48 № 49 № 50

II

Е

F

G

II

E

F

G

II

E

F

G

II

E

F

G

II

E

F

G

I

I

I

I

I

А

-

+

А

-

-

+

А

-

+

А

-

+

-

А

-

В

-

+

В

+

+

В

+

-

+

В

+

+

В

+

+

-

С

+

+

С

+

-

С

+

+

С

+

С

-

+

8.51- 8.60. Для обеспечения однократной зимовки небольшой экспедиции требуется доставить к месту зимовки вместе с другими грузами запас топлива. В случае нормальной зимы достаточно 16 т, но при мягкой или суровой зиме эти цифры составят А и В т. Если осуществить заброску летом, то она будет стоить по 12 руб. за тонну. Если придется доставлять топливо зимой дополнительно, то его доставка обойдется в нормальную и суровую зиму соответственно a и b рублей за тонну дороже, чем летом. Обратная транспортировка неизрасходованного топлива по окончании зимовки обходится в 1 руб. за тонну, а его стоимость не возмещается. Найти оптимальную стратегию руководителя экспедиции.

№
А
В
a
b

8.61- 8.70. В зависимости от погодных условий летом спрос на ласты может составить по статистическим данным 600,800,1200,1600,1800 пар. Торговая база может закупить одну или несколько партий размером в А пар. Если ласты остаются непроданными, то их нужно хранить до следующего сезона. Стоимость хранения 0,2 руб. за пару. Примерно 5% пар при хранении приходит в негодность. Убыток при неудовлетворительном спросе составляет a руб. за пару, стоимость пары ласт - b руб. Найти оптимальную стратегию торговой базы и цену соответствующей игры.

№
А
a		1,5								2,5
b

8.71- 8.75. Производственное объединение запускает видеомагнитофоны, работа которых сильно зависит от параметров дефицитной микросхемы, себестоимостью a руб. Гарантийная замена неисправной схемы обходится в 10 руб. Существуют два метода проверки схемы. Один выявляет неисправности в 75% случаев и стоит b руб., второй полностью надежен и практически бесплатен, но в g% случаев приводит к выходу из строя исправной схемы. Можно поставить импортные схемы с гарантированным качеством стоимостью d руб. В случае обнаружения дефектной схемы она заменяется надежной схемой из резерва (себестоимости a руб.). Найти оптимальную стратегию объединения.

 

№
a
b
g
d

 

8.76- 8.85 В магазине два торговых зала А₁ и А₂ , которые охраняются двумя действующими независимо друг от друга полицейскими. Каждый полицейский может находиться в одном из торговых залов или наблюдать за залами по телевизору. Если вор находится в торговом зале А_i , а полицейский находится в зале А_к, то вероятность поимки вора равна Р_кi. Если полицейский находится у телевизора, то эта вероятность равна Р_оi. Найти оптимальную стратегию для полицейских.

i
к
	0,8	0,6	0,9	0,6	0,9	0,5	0,7	0,6	0,9	0,7	0,8	0,5	0,6	0,4	0,9	0,4	0,7	0,5	0,9	0,8
	0,7	0,9	0,7	0,8	0,6	0,8	0,5	0,9	0,6	0,4	0,4	0,8	0,5	0,8	0,6	0,8	0,6	0,9	0,6	0,9
	0,75	0,7		0,8	0,8	0,8	0,8	0,6	0,7	0,9	0,8	0,7	0,8	0,8	0,7	0,5	0,8	0,6	0,8	0,9

8.86- 8.95. Болезнь имеет пять разновидностей, вызываемых различными типами вируса. Имеются три лекарства L₁, L₂, L₃,. Лекарства L₁, L₂ могут быть назначены совместно, действуя при этом, независимо друг от друга. Лекарство L₁ гарантирует победу над четырьмя первыми типами вирусов с вероятностью 0,5; 0,6; 0,6; a. Второе побеждает первый и третий вирусы с вероятностью 0,5 и g, а пятый с вероятностью b. Третье лекарство дает 50% успеха против второго и полную гарантию против пятого. Любое лекарство бесполезно против неуказанных вирусов. Найти оптимальную стратегию врача при назначении лекарств.

№
a	0,5	0,6	0,7	0,8	0,5	0,4	0,7	0,6	0,8	0,2
b	0,8	0,4	0,3	0,2	0,8	0,7	0,3	0,4	0,3	0,5
g	0,4	0,6	0,5	0,7	0,3	0,8	0,4	0,6	0,4	0,9

 

8.96- 8.100. Детектив ночью может сторожить одну из двух дверей музея, где по его сведениям совершается кража ценной картины, стоимостью А марок. Операцию совершают двое. Картину уносит главарь. Поимка главаря оценивается в В марок, его сообщника в С марок. Детектив может арестовать первого выходящего (если он выходит через контролируемую дверь) или дать ему уйти, ожидая второго (в темноте он не может опознать главаря и не видит, имеет ли человек картину). Одновременный выход обоих преступников через разные двери невозможен по техническим причинам. Если выходящий вторым видит, что его партнер задержан, то он может беспрепятственно скрыться. Если же его сообщник не задержан, то он имеет возможность выйти через любую из дверей. Сообщники не знают, за какой дверью следит детектив, но уверены в его присутствии. Найти оптимальную стратегию игроков и цену игры.

№
А	106	106	107	105	104
В	105	104	105	105	105
С	103	102	102	102	103

Задача 9. (9.1- 9.100). Задача целочисленного линейного программирования. Найти наибольшее значение линейной целевой функции на множестве всех целочисленных планов системы линейных неравенств, т.е.

ƒ (х) = с₁х₁ + с₂х₂ – max

а₁₁х₁ + а₁₂х₂ £ в₁ х_i ³ 0, целое i = 1,2

а₂₁х₁ + а₂₂х₂ £ в₂

Задачу решить графически, методом Гомори и методом ветвей и границ. Параметры задач 9.1 – 9.50 приведены в таблице.

№	С1	С2	А11	А21	А12	А22	В1	В2
		5/2
						-3
						-3
						-2
			-5
								63/2
				-1
		3/5
				-1
							81/2
				-2
				-7	-7
				-5	-1
			-1			-5
			-13			-5
				-5	-13
		-1	-1			-3
		-7		-3	-1
			-3
				-5	-3
			-9
			-14			-14
		-1	-5			-8
			-14			-14
		-3		-8	-5
			-14			-14
					-3
			-3			-1
				-1	-1
				-1	-1
			-21			-3	-18
				-1	-1
		-1		-7	-1

9.51 – 9.60. Прутки длиной L метров разрезаются на заготовки длиной l₁ и l₂ м. Заготовок первого типа нужно получить не менее к₁ шт., второго – не менее к₂ шт. Определить минимальное число разрезанных прутков. Допускаются лишь способы разрезания, при которых длина остатка меньше любого числа l₁ и l₂ .

№
L						8,9			13,6
l1	1,5	2,5		1,8		3,5	4,3	3,4	4,2	3,7
l2		1,8	2,4	1,2	1,1	1,8	2,7	4,3	4,7	4,5
к1
к2

9.61 – 9.70. При соблюдении всех условий предыдущей задачи заготовки объединяются в комплекты, содержащие к_i заготовок длины l_i, i = 1,2. Имеется М прутков. Составить план разрезания прутков, гарантирующий получение максимального числа комплектов (данные о к₁ и к₂ теперь не используются).

№
М
n1
n2

9.71 – 9.80. В условиях задачи 9.51 – 9.56 определить план разрезания прутков, минимизирующий сумму остатков.

9.81- 9.90. Продукты А₁, А₂, А₃ грузятся в контейнер, упакованные в мешки. Ценность одного мешка с грузом А_i равна С_i. Его вес р_i , а объем V_i . Объем контейнера равен Y, а вес не должен превосходить р ед. Определить план загрузки контейнера, при котором максимально число помещенных в контейнер мешков. Данные для решения приведены в таблице.

№
Y
Р
V1
V2
V3
Р1
Р2
Р3

9.91 – 9.100. Смесь должна содержать не менее a единиц вещества А и не менее b единиц вещества В. Для ее приготовления используются готовые продукты I и П, продаваемые цельными упаковками. Одна упаковка продукта I содержит g₁ вещества А и d₁ вещества В. Продукту П отвечают аналогичные числа g₂ и d₂ . Цены упаковок продуктов I и П равны соответственно с₁и с₂ . Составить требуемую смесь минимальной стоимости.

№
a
b
С1
С2
g1
d1
g2
d2

Задача 10.(10.1 – 10.105). Задача коммивояжера. Найти кратчайший маршрут, проходящий точно по одному разу через каждый из заданных пунктов А₁, А₂ …….А_n и удовлетворяющий дополнительным условиям, приводимым ниже. Матрицы взаимных расстояний приведены в таблицах. Элемент а_iк равен расстоянию от пункта А_i до пункта А_к (которое может не совпадать с расстоянием от пункта А_к до пункта А_i ). У каждой матрицы приведены номера соответствующих ей задач.

10.1- 10.20. Найти кратчайший из замкнутых маршрутов.

10.21- 10.40. Найти кратчайший из замкнутых маршрутов, которые:

10.21 – 10.25. Содержат дуги А₁"А₂ и А₁" А₅ .

10.26 – 10.30. Содержит дугу А₁"А₂, но не содержит дуги А₁" А₅

10.35 – 10.39. Не содержит дуг А₂"А₃ и А₃" А₅

10.40. Не содержит дуг вида А_i А_i+1 . i = 1,2,3,4,5.

10.41 – 10.50. Найти кратчайший из замкнутых маршрутов.

10.51 – 10.100. Найти кратчайший путь из разомкнутых маршрутов, которые:

10.51 – 10.60. Начинается в пункте А₁ .

10.61 – 10.70 Начинается в пункте А₁ , а оканчиваются в пункте А₅ .

10.71 – 10.74. Оканчиваются в пункте А₅ .

10.75 – 10.79. Начинается в пункте А₃ и содержат дугу А₂"А₅ .

10.80 – 10.84. Оканчиваются в пункте А₃ и содержат дугу А₂"А₅ .

10.85 – 10.89. Оканчиваются в пункте А₄ и не содержат дугу А₁"А₃ .

10.90 – 10.95. Начинается в пункте А₂ и не содержат дугу А₁"А₅ .

10.96 – 10.99. Содержат дугу А₃"А₄ , но не содержат дугу А₁"А₂ .

10.100. Не содержат дуг вида А_i А_i+1 . i = 1,2,3,4,5.

10.101. На станке обрабатываются детали А₁,А₂ ,А₃, А₄ , А₅ , А₆ . При переходе от обработки детали А_i к обработке детали А_d на настройку станка затрачивается время t_ig . В начальный момент станок настроен на деталь А₁ , которая обрабатывается первой. Найти порядок обработки деталей, при котором минимально суммарное время настройки.

10.102. В приборную доску вмонтированы элементы А₁ ……. А₆ . Эти элементы нужно соединить последовательно так, чтобы суммарная длина соединяющих их проводов была минимальна (к крайним элементам присоединяются выводы электросети).

10.103. В приборную доску вмонтированы элементы А₁ ……. А₆ , которые соединяются последовательно (для последующего присоединения к электросети). Элемент А₃ не должен непосредственно соединяться с элементами А₄ и А₆ . Найти порядок соединения элементов, при котором минимальна суммарная длина использованных проводов.

10.104. В приборную доску вмонтированы элементы А₁ и А₆ и элементы В приборную доску вмонтированы элементы А₂ , А₃ , А₄ , А₅ . Указанные элементы нужно соединить последовательно и подключить к электросети. Произвести соединение так, чтобы суммарная длина соединяющих проводов была минимальной.

 

№ 1,19,46,59,101 № 2,20,62,68 №3,21,48,103

- 1 6 8 8 7 6 - 3 3 12 8 4 7 - 11 6 9 1 6 3 - 1 4 9 5 3 7 - 8 5 4 5 6 11 -

- 5 10 15 18 11 1 - 9 19 8 7 8 3 - 7 7 6 5 15 3 - 1 10 8 9 7 17 - 15 7 12 5 12 10 -

- 37 28 13 17 22 37 - 18 34 19 24 28 18 - 25 14 16 13 34 25 - 37 17 17 19 14 37 - 23 22 24 16 17 23 -

№ 4,22,31,50 № 5,23,32,47,102 № 6,24,33,49,104

- 35 41 38 19 40 51 - 43 27 24 31 63 100 – 58 89 50 32 27 44 - 71 33 51 60 73 80 - 49 49 38 50 44 50 -

- 35 41 63 28 45 35 - 29 37 45 40 41 29 - 53 91 50 63 37 53 - 72 43 28 45 91 72 - 51 45 40 50 43 51 -

- 71 35 83 58 40 71 - 45 69 35 70 35 45 - 73 18 45 83 69 73 - 91 56 58 35 18 91 - 72 40 70 45 56 72 -

№7,25,34,53 № 8,26,35,51 № 9,27,36,52

- 37 41 28 35 30 36 - 53 41 44 42 45 51 - 29 30 50 93 71 45 - 51 81 18 48 63 51 - 29 70 45 54 60 43 -

- 3 6 8 11 10 4 - 6 11 8 9 8 12 - 5 10 7 10 12 10 - 2 11 10 11 1 9 - 8 6 10 7 8 9 -

- 35 18 24 37 25 35 - 23 71 52 30 18 23 - 45 34 40 24 71 45 - 25 37 37 52 34 25 - 42 25 30 40 37 40 -

№ 10,28,37,54 № 11,29,38,55 № 12,30,39,58,91

- 35 43 18 27 20 35 - 17 29 34 25 43 17 - 41 32 30 18 29 41 - 51 42 27 34 32 51 - 31 20 25 30 42 31 -

- 8 7 6 4 5 3 - 6 4 7 9 8 6 - 5 6 4 3 9 5 - 7 6 5 7 8 9 - 7 6 5 3 7 8 -

- 7 8 9 12 6 7 - 11 7 9 8 8 11 - 10 6 5 9 12 6 - 7 9 12 9 7 11 - 10 6 8 5 9 10 -

 

№ 13,57,67,77 № 14,41,63,73 № 15,42,64,95

- 35 18 27 45 64 35 - 7 12 15 27 71 44 - 54 31 49 60 35 58 - 60 27 31 50 28 15 - 35 29 17 16 38 42 -

- 40 35 28 19 32 35 - 15 27 18 29 28 37 - 20 41 35 35 18 12 - 25 43 21 46 17 35 - 21 45 37 28 18 10 -

- 6 7 8 5 7 5 - 8 4 9 8 2 4 - 6 7 6 6 3 9 - 11 10 2 7 9 10 - 11 5 6 10 7 9 -

№ 16,43,56,65 № 17,44,59,66 № 15,42,64,95

- 47 35 40 31 29 71 - 38 15 14 25 41 35 - 27 31 40 37 19 17 - 25 30 63 29 41 19 - 43 19 21 37 42 26 -

- 14 32 53 8 44 53 - 2 14 30 39 50 53 - 52 2 17 1 58 54 - 52 51 18 13 4 58 - 15 39 48 46 9 2 -

- 4 21 10 10 7 3 - 20 10 18 12 12 8 - 1 8 10 6 12 32 - 2 8 10 18 7 9 - 13 7 12 10 8 13 -

№16,43,56,65 № 17,44,59,66 № 18,45,60,72

- 47 35 40 31 29 71 - 38 15 14 25 41 35 - 27 31 40 37 19 17 - 25 30 63 29 41 19 - 43 19 21 37 42 26 -

- 14 32 53 8 44 53 - 2 14 30 39 50 53 - 52 2 17 1 58 54 - 52 51 18 13 4 58 - 15 39 48 46 9 2 -

- 4 21 10 10 7 3 - 20 10 18 12 12 8 - 1 8 10 6 12 32 - 2 8 10 18 7 9 - 13 7 12 10 8 13 -

№ 40,61,71,100 № 76,80,82,88,93 № 69,75,79,85,94

- 10 9 10 11 6 12 - 8 7 9 7 8 13 - 9 10 8 12 8 7 - 8 7 15 16 6 10 - 11 11 12 13 8 7 -

- 6 10 13 18 17 7 - 11 17 16 17 13 17 - 12 19 16 9 18 17 - 12 21 12 18 9 18 - 19 14 18 16 18 20 -

- 10 12 14 18 13 10 - 16 13 16 16 12 16 - 17 14 14 14 18 13 - 16 19 18 16 15 20 - 21 13 14 14 19 21 -

 

№ 70,78,85.99 № 66, 87,90,96 № 74,84,89,97

- 9 11 13 11 14 8 - 13 10 16 16 6 9 - 13 15 15 11 9 16 - 20 20 8 14 17 19 - 22 12 14 19 17 20 -

- 5 8 11 6 3 5 - 17 4 12 7 8 17 - 7 9 11 11 4 7 - 12 8 6 12 9 12 - 15 3 7 11 8 15 -

- 3 20 9 9 6 4 - 21 11 19 13 15 11 - 4 11 13 5 11 31 - 7 7 8 16 5 7 - 11 4 9 7 5 10 -

№ 81,86,92,98

- 34 24 8 11 15 34 - 13 28 12 16 24 13 - 19 7 8 8 28 19 - 30 10 11 12 7 30 - 15 15 16 8 10 15 -

 

10.105. Санкт- Петербургские автотуристы должны посетить по одному разу в одной поездке Москву, Ярославль, Калугу, Псков и Новгород. Составить кратчайший маршрут поездки.

Задача 11. (1.11 – 11.100)

11.1 – 11.50. Найти кратчайший путь от вершин х₀ до остальных вершин графа. Граф описывается перечнем всех своих дуг (верхняя строка) и их длинами (нижняя строка). Дуга х_iх_g с обозначается парой чисел ig.

1.01 02 04 12 13 23 35 36 37 41 45 51 56 511 67 610 78 79 710 89 910 1011 1012 1112 17 30 8 12 28 15 53 30 53 11 51 7 14 32 21 5 7 13 12 4 3 14 16 33
2.01 05 14 15 17 27 28 29 211 32 40 48 52 57 63 68 610 74 79 89 96 103 109 1012 119 1110 12 23 42 13 31 10 33 50 42 20 15 35 34 18 19 8 21 12 65 56 19 19 8 17 18 50
3. 01 02 03 04 15 19 26 27 32 36 41 43 45 58 59 65 76 86 87 810 811 98 910 1011 117 23 25 19 8 32 48 22 12 5 26 14 10 50 35 15 10 8 10 15 3 11 17 21 9 12
4. 01 02 03 05 12 15 16 24 25 34 45 48 49 56 58 59 67 710 86 87 810 98 910 29 15 7 8 5 8 29 7 10 4 9 35 36 35 29 15 19 15 8 30 44 17 12
5. 01 02 03 12 14 23 25 26 34 37 310 35 47 48 56 57 69 610 78 710 711 810 811 910 1011 120 94 95 85 79 37 53 48 54 62 105 29 36 68 53 39 75 60 27 47 94 60 46 32 17
6.01 02 04 12 13 16 28 29 36 38 43 45 49 57 59 69 710 86 910 40 44 60 70 15 75 50 85 32 80 45 31 78 63 50 43 56 44 24
7. 01 03 04 12 15 25 26 37 48 49 410 56 58 69 610 611 78 79 811 812 912 1012 1112 40 10 55 10 20 25 28 19 35 15 30 10 15 50 41 60 33 42 45 35 40 39 34
8. 01 02 03 14 15 26 27 32 35 36 48 52 56 58 67 611 75 79 710 87 89 910 1110 17 49 17 28 19 8 30 32 33 43 23 12 12 32 15 20 12 34 11 21 18 15 14
9.01 02 03 06 12 14 24 25 26 32 36 34 45 411 56 511 69 72 76 78 86 89 911 102 104 109 1011 16 28 25 19 18 21 14 19 9 12 18 21 20 11 17 15 7 17 10 12 15 15 14 17 21 18 20
10. 01 02 04 12 13 16 29 36 38 42 43 45 48 49 59 69 710 85 86 87 910 40 18 27 50 10 55 63 23 50 25 37 23 45 91 40 25 43 15 27 20 35
11.01 03 04 12 13 26 32 34 35 37 45 57 59 68 610 76 810 96 97 98 22 18 30 53 10 10 30 11 40 55 48 21 40 25 35 17 12 17 17 20
12.01 05 14 15 17 27 28 29 32 43 48 52 57 63 68 74 79 83 89 96 13 17 23 18 16 20 25 29 20 15 29 30 28 21 14 16 28 25 20 25
13.01 03 04 12 13 26 32 34 35 37 45 57 59 68 610 76 810 96 97 96 17 33 18 43 15 40 20 15 20 70 38 39 30 19 25 9 7 17 8 40
14. 01 02 03 04 12 17 23 26 27 34 45 56 59 67 68 69 78 89 98 14 5 13 14 8 4 7 16 13 6 4 5 15 3 4 12 8 9 40
15.01 05 14 15 17 27 28 29 46 48 52 57 63 68 610 74 79 83 89 96 15 15 21 20 16 15 20 18 15 29 30 28 21 14 17 20 21 16 26 17
16.01 02 03 12 24 25 26 27 32 37 45 48 56 58 510 67 610 710 89 109 4 6 6 1 7 4 10 7 4 8 4 9 3 5 10 5 15 13 6 2
17.01 03 06 12 14 24 25 26 29 32 36 37 45 56 69 78 79 86 89 95 97 20 17 35 25 18 15 21 7 17 15 18 29 18 7 ⇐ Предыдущая1234Следующая ⇒ Поделиться: Воспользуйтесь поиском по сайту: ©2015 - 2023 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...