Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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

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

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

Пусть m0 = 4, n0 =3

 

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

n m          
           
           
           

 

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

n m        
         
         
         
         

 

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

 

 

 

 


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

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

 

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

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

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

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

 

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

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

Вложенная сумма (млн. руб.) Проект 1 Проект 2 Проект 3
       
       
       
       
       
       

 

 

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

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

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

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

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

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

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

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

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

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

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

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

 

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

1) Точка A1(1, 6) означает, что все средства целы, и, следовательно, во второй проект можно вложить либо 0 (из точки A1(1, 6) в точку A2(2, 6)), либо 1 (из точки A1(1, 6) в точку B2(2, 5)), либо 2 (из точки A1(1, 6) в точку C2(2, 4)), либо 3 (из точки A1(1, 6) в точку D2(2, 3)), либо 4 (из точки A1(1, 6) в точку E2(2, 2)), либо 5 (из точки A1(1, 6) в точку G2(2, 1)), либо 6 млн. руб. (из точки A1(1, 6) в точку F2(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) Точка B1(1, 5) означает, что осталось 5 млн. руб., следовательно во второй проект можно вложить либо 0 (из точки B1(1, 5) в точку B2(2, 5)), либо 1 (из точки B1(1, 5) в точку C2(2, 4)), либо 2 (из точки B1(1, 5) в точку D2(2, 3)), либо 3 (из точки B1(1, 5) в точку E2(2, 2)), либо 4 (из точки B1(1, 5) в точку G2(2, 1)), либо 5 млн. руб.(из точки B1(1, 5) в точку F2(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) Точка C1(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) Точка D1(1, 3) означает, что осталось 3 млн. руб.

0: 0+26=26

1: 9+18=27

2: 18+10=28*

3: 26+0=26.

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

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

0: 0+18=18

1: 9+10=19*

2: 18+0=18.

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

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

0: 0+10=10*

1: 9+0=9.

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

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

 

 

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

Точка A(0, 6) означает, что все средства целы, и, следовательно, в первый проект можно вложить либо 0 (из точки A(0, 6) в точку A1(1, 6)), либо 1 (из точки A (0, 6) в точку B1(1, 5)), либо 2 (из точки A(0, 6) в точку C1(1, 4)), либо 3 (из точки A(0, 6) в точку D1(1, 3)), либо 4 (из точки A(0, 6) в точку E1(1, 2)), либо 5 (из точки A(0, 6) в точку G1(1, 1)), либо 6 млн. руб. (из точки A(0, 6) в точку F1(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.

 

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

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

 

 

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

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

1) A à B1 à C2 à F3, Xопт=(1, 1, 4)

2) A à B1 à D2 à F3, Xопт=(1, 2, 3)

3) A à B1 à E2 à F3, Xопт=(1, 3, 2)

4) A à B1 à G2 à F3, Xопт=(1, 4, 1)

5) A à C1 à E2 à F3, Xопт=(2, 2, 2)

6) A à C1 à G2 à F3, Xопт=(2, 3, 1)

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

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

1) ρ 1 = 1 млн. руб., ρ 2 = 1 млн. руб, ρ 3 = 4 млн. руб.

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

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

4) ρ 1 = 1 млн. руб, ρ 2 = 4 млн. руб, ρ 3 = 1 млн. руб.

5) ρ 1 = 2 млн. руб, ρ 2 = 2 млн. руб, ρ 3 = 2 млн. руб.

6) ρ 1 = 2 млн. руб, ρ 2 = 3 млн. руб, ρ 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        

 

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

    144 152
    140 140
    118 117
    118 117

 

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

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

 

        6 10
        15 11
        6 7
        9 8
        9 11

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

 

Таблица 3.3.1.а.

Вложенная сумма (млн. руб.) Нефтяной проект Про-во напитков Строи-во коттеджей
  0, 14 0, 09 0, 11
  0, 26 0, 17 0, 20
  0, 39 0, 22 0, 29
  0, 45 0, 26 0, 37
  0, 50 0, 27 0, 44
  0, 53 0, 28 0, 48

 

Таблица 3.3.1.б.

 

Вложенная сумма (млн. руб.) Нефтяной проект Про-во напитков Строи-во коттеджей
  0, 10 0, 12 0, 08
  0, 17 0, 22 0, 15
  0, 25 0, 29 0, 21
  0, 31 0, 34 0, 26
  0, 40 0, 40 0, 30
  0, 50   0, 33

 

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

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

Вложенная сумма (млн. руб.) Р1 Р2 Р3
  0, 14 0, 16 0, 13
  0, 17 0, 19 0, 16
  0, 23 0, 24 0, 25
  0, 25 0, 26 0, 32
  0, 30 0, 35 0, 36

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

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

Вложенная сумма (млн. руб.) Р1 Р2 Р3
  0, 10 0, 09 0, 11
  0, 15 0, 11 0, 12
  0, 16 0, 19 0, 15
  0, 20 0, 21 0, 29
  0, 25 0, 27 0, 30

 

<== предыдущая лекция | следующая лекция ==>
Упражнения | 
Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.022 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал