Пример 3. Задача о распределении средств между предприятиями.

Пример 2. Задача об оптимальной последовательности операций.

Овощная база должна разгрузить m₀ автомобилей и погрузить n₀ автомобилей. Продолжительность операций указана в таблицах.

Пусть m₀ = 4, n₀ =3

Таблица 1. Погрузка

Таблица 2. Разгрузка

Опишем состояние системы набором чисел (m, n), где m – число разгруженных автомобилей, n - число погруженных автомобилей. Последовательность операций отгрузки/погрузки соответствует пути от x₀ до x_конечн. Таким образом, задача сводится к нахождению минимального маршрута от x₀ до x_конечн.

Определение. Ранг вершины сети – это максимальное число дуг до вершины.

Для вершины (3; 2): ранг ρ (3; 2) = min {14+16; 15+17} = 30.

Ответ: минимальное время погрузочно-разгрузочных работ = 79 мин.

Оптимальная схема погрузки/разгрузки:

1) Р → П → Р → П → П → Р → Р

2) Р → П → Р → Р → П → П → Р

Пример 3. Задача о распределении средств между предприятиями.

Как распределить имеющиеся 6 миллионов рублей между проектами так, чтобы суммарная прибыль была максимальной?

Если точка имеет координаты (n; m), то это значит, что средства распределены между n предприятиями и осталось m условных единиц груза.

Нужно пройти от точки А(0, 6), в которой все средства целы, до точки F₃(3, 0), в которой все средства распределены между тремя проектами.

Решаем задачу методом динамического программирования с помощью условной пошаговой оптимизации. Идем от конечного состояния к начальному.

Рассмотрим состояние S₃=F₃(3, 0) – конечное состояние.

Рассмотрим состояние S₂ (двум проектам средства уже выделены, необходимо выделить средства третьему проекту):

1) Точка A₂(2, 6) означает, что все средства целы, и, следовательно, все 6 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 44.

2) Точка B₂(2, 5) означает, что осталось 5 млн. руб., и, следовательно, 5 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 40.

3) Точка C₂(2, 4) означает, что осталось 4 млн. руб., и, следовательно, 4 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 35.

4) Точка D₂(2, 3) означает, что осталось 3 млн. руб., и, следовательно, 3 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 26.

5) Точка E₂(2, 2) означает, что осталось 2 млн. руб., и, следовательно, 2 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 18.

6) Точка G₂(2, 1) означает, что осталось 1 млн. руб., и, следовательно, 1 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 10.

7) Точка F₂(2, 0) означает, что осталось 0 млн. руб., и, следовательно, прибыль будет равна 0.

Рассмотрим состояние S₁ (одному проекту средства уже выделены, необходимо выделить средства второму проекту):

1) Точка A₁(1, 6) означает, что все средства целы, и, следовательно, во второй проект можно вложить либо 0 (из точки A₁(1, 6) в точку A₂(2, 6)), либо 1 (из точки A₁(1, 6) в точку B₂(2, 5)), либо 2 (из точки A₁(1, 6) в точку C₂(2, 4)), либо 3 (из точки A₁(1, 6) в точку D₂(2, 3)), либо 4 (из точки A₁(1, 6) в точку E₂(2, 2)), либо 5 (из точки A₁(1, 6) в точку G₂(2, 1)), либо 6 млн. руб. (из точки A₁(1, 6) в точку F₂(2, 0)). Поэтому из таблицы (берем второй столбец, соответствующий прибыли от второго проекта, и третий столбец, соответствующий прибыли от третьего проекта) следует, что общая прибыль по второму и третьему проектам (по всем возможным вариантам) будет равна

0: 0+44=44

1: 9+40=49

2: 18+35=53*

3: 26+26=52

4: 34+18=52

5: 40+10=50

6: 42+0=42.

Выберем максимальную прибыль 53. Эта прибыль соответствует вложению 2 млн. руб. во второе предприятие.

(Заметим, что слева в сумме выписан второй столбец, дополненный вверху нулем, а справа – перевернутый третий столбец, дополненный снизу нулем.)

2) Точка B₁(1, 5) означает, что осталось 5 млн. руб., следовательно во второй проект можно вложить либо 0 (из точки B₁(1, 5) в точку B₂(2, 5)), либо 1 (из точки B₁(1, 5) в точку C₂(2, 4)), либо 2 (из точки B₁(1, 5) в точку D₂(2, 3)), либо 3 (из точки B₁(1, 5) в точку E₂(2, 2)), либо 4 (из точки B₁(1, 5) в точку G₂(2, 1)), либо 5 млн. руб.(из точки B₁(1, 5) в точку F₂(2, 0)). Поэтому из таблицы следует, что общая прибыль по второму и третьему проектам (по всем возможным вариантам) будет равна

0: 0+40=40

1: 9+35=44*

2: 18+26=44*

3: 26+18=44*

4: 34+10=44*

5: 40+0=40

Выберем максимальную прибыль 44. Эта прибыль соответствует вложению либо 1, либо 2, либо 3, либо 4 млн. руб. во второе предприятие.

3) Точка C₁(1, 4) означает, что осталось 4 млн. руб., и, следовательно, рассуждая аналогично предыдущему, получим

0: 0+35=35

1: 9+26=35

2: 18+18=36*

3: 26+10=36*

4: 34+0=34

Выберем максимальную прибыль 36. Эта прибыль соответствует вложению либо 2, либо 3 млн. руб. во второе предприятие.

4) Точка D₁(1, 3) означает, что осталось 3 млн. руб.

0: 0+26=26

1: 9+18=27

2: 18+10=28*

3: 26+0=26.

Выберем максимальную прибыль 28. Эта прибыль соответствует вложению 2 млн. руб. во второе предприятие.

5) Точка E₁(1, 2) означает, что осталось 2 млн. руб.

0: 0+18=18

1: 9+10=19*

2: 18+0=18.

Выберем максимальную прибыль 19. Эта прибыль соответствует вложению 1 млн. руб. во второе предприятие.

6) Точка G₁(1, 1) означает, что осталось 1 млн. руб.

0: 0+10=10*

1: 9+0=9.

Выберем максимальную прибыль 10. Эта прибыль соответствует вложению 0 млн. руб. во второе предприятие.

7) Точка F₁(1, 0) означает, что осталось 0 млн. руб., и, следовательно, прибыль будет равна 0.

Рассмотрим состояние начальное состояние S₀ = A(0, 6) (необходимо выделить средства первому проекту):

Точка A(0, 6) означает, что все средства целы, и, следовательно, в первый проект можно вложить либо 0 (из точки A(0, 6) в точку A₁(1, 6)), либо 1 (из точки A (0, 6) в точку B₁(1, 5)), либо 2 (из точки A(0, 6) в точку C₁(1, 4)), либо 3 (из точки A(0, 6) в точку D₁(1, 3)), либо 4 (из точки A(0, 6) в точку E₁(1, 2)), либо 5 (из точки A(0, 6) в точку G₁(1, 1)), либо 6 млн. руб. (из точки A(0, 6) в точку F₁(1, 0)). Поэтому из таблицы, используя первый столбец для первого проекта, следует, что общая прибыль по первому, второму и третьему проектам (по всем возможным вариантам) будет равна

0: 0+53=53

1: 12+44=56*

2: 20+36=56*

3: 25+28=53

4: 28+19=47

5: 30+10=40

6: 31+0=31.

(Заметим, что слева в сумме выписан первый столбец таблицы, дополненный вверху нулем, а справа – столбец, выписанный из максимальных прибылей состояния S₁, дополненный снизу нулем.)

Выберем максимальную прибыль 56. Эта прибыль соответствует вложению либо 1, либо 2 млн. руб. в первое предприятие.

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

Оптимальные траектории:

1) A à B₁ à C₂ à F_3, X_опт=(1, 1, 4)

2) A à B₁ à D₂ à F_3, X_опт=(1, 2, 3)

3) A à B₁ à E₂ à F_3, X_опт=(1, 3, 2)

4) A à B₁ à G₂ à F_3, X_опт=(1, 4, 1)

5) A à C₁ à E₂ à F_3, X_опт=(2, 2, 2)

6) A à C₁ à G₂ à F_3, X_опт=(2, 3, 1)

Итак, оптимальная (максимальная) прибыль Р_опт = 56.

Оптимальная схема вложения:

1) ρ ₁ = 1 млн. руб., ρ ₂ = 1 млн. руб, ρ ₃ = 4 млн. руб.

2) ρ ₁ = 1 млн. руб, ρ ₂ = 2 млн. руб, ρ ₃ = 3 млн. руб.

3) ρ ₁ = 1 млн. руб, ρ ₂ = 3 млн. руб, ρ ₃ = 2 млн. руб.

4) ρ ₁ = 1 млн. руб, ρ ₂ = 4 млн. руб, ρ ₃ = 1 млн. руб.

5) ρ ₁ = 2 млн. руб, ρ ₂ = 2 млн. руб, ρ ₃ = 2 млн. руб.

6) ρ ₁ = 2 млн. руб, ρ ₂ = 3 млн. руб, ρ ₃ = 1 млн. руб.

Задача 3.1.1. Туристическая компания “Супертранс” предлагает билеты на авиарейсы:

Рейс Цена (в условных единицах)

1. Москва — Новосибирск 105

2. Москва — Иркутск 175

3. Москва — Алма-Ата 210

4. Москва — Рим 200

5. Новосибирск — Якутск 85

6. Новосибирск — Иркутск 75

7. Новосибирск — Хабаровск 80

8. Новосибирск — Владивосток 130

9. Иркутск — Якутск 80

10. Иркутск — Хабаровск 35

11. Якутск — Хабаровск 40

12. Якутск — Владивосток 50

13. Хабаровск — Владивосток 25

14. Хабаровск — Пекин 120

15. Алма-Ата — Иркутск 60

16. Алма-Ата — Токио 280

17. Алма-Ата — Пекин 150

18. Рим — Пекин 250

19. Рим — Токио 300

20. Пекин — Токио 110

21. Владивосток — Токио 160

Начертите граф авиалиний компании и найдите в нём минимальный по стоимости маршрут из Москвы в Токио.

Задача 3.1.2. Туристическая компания “Супертранс” предлагает билеты на авиарейсы:

Рейс Цена (в условных единицах)

1. Москва — Новосибирск 110

2. Москва — Иркутск 180

3. Новосибирск — Якутск 70

4. Новосибирск — Иркутск 60

5. Новосибирск — Хабаровск 120

6. Новосибирск — Владивосток 170

7. Иркутск — Якутск 60

8. Иркутск — Хабаровск 50

9. Якутск — Хабаровск 40

10. Якутск — Владивосток 80

11. Хабаровск — Владивосток 20

Начертите граф авиалиний компании и найдите в нём минимальный по стоимости маршрут из Москвы во Владивосток.

Задача 3.1.3. Туристическая компания “Супертранс” предлагает билеты на авиарейсы:

Рейс Цена (в условных единицах)

1. Москва — Новосибирск 95

2. Москва — Иркутск 155

3. Новосибирск — Якутск 85

4. Новосибирск — Иркутск 45

5. Новосибирск — Хабаровск 105

6. Новосибирск — Владивосток 145

7. Иркутск — Якутск 35

8. Иркутск — Хабаровск 45

9. Якутск — Хабаровск 45

10. Якутск — Владивосток 75

11. Хабаровск — Владивосток 25

Начертите граф авиалиний компании и найдите в нём минимальный по стоимости маршрут из Москвы во Владивосток.

Задача 3.2.1. Овощная база должна разгрузить 4 автомашины с капустой и отправить в магазины 3 автомашины с картофелем. Время разгрузки и погрузки зависит от числа m разгруженных и числа n погруженных автомобилей. В таблице время разгрузки указано в нижних правых углах клеток, а время погрузки - в верхних левых углах.

Таблица 3.2.1.а. Зависимость времени разгрузки/погрузки от числа разгруженных автомобилей m и числа погруженных — n.

m n

Таблица 3.2.1.б. Зависимость времени разгрузки/погрузки от числа разгруженных автомобилей m и числа погруженных — n.

m n

Задача 3.2.2. Решить технологическую задачу динамического программирования.

m(разг.) n(погр.)	m=0	m=1	m=2	m=3
n=0
n=1
n=2
n=3
n=4

Визуализация данных:

Задача 3.2.3. Решите задачу о погрузке и разгрузке автомобилей на овощебазе:

Визуализация данных:

Задача 3.3.1. Инвестиционная компания “Русский Клондайк” намерена вложить 6 миллионов рублей в нефтяной проект, производство напитков и строительство коттеджей. Зависимость ожидаемой прибыли от вложенной в дело суммы, установленная в результате маркетинговых исследований фирмы, представлена в таблице (по вариантам). Найдите оптимальную схему капитальных вложений.

Таблица 3.3.1.а.

Таблица 3.3.1.б.

Задача 3.3.2. Дана таблица зависимости прибыли от вложений в дело различных сумм, указанных в первом столбце в проектах Р₁, Р₂ и Р₃.

Найдите максимальную прибыль и укажите, при каком распределении вложений она достигается.

Задача 3.3.3. Дана таблица зависимости прибыли от вложений в дело различных сумм, указанных в первом столбце в проектах Р₁, Р₂ и Р₃.

Найдите максимальную прибыль и укажите, при каком распределении вложений она достигается.