Динамическое программирование
1 – 4. Задачи об оптимальном распределении ресурсов между двумя отраслями на п лет
1 (30 вариантов). Планируется работа двух отраслей производства на период в три года. Средства х, вложенные в I отрасль в начале года, дают в конце года прибыль Аx и возвращаются в размере Вxlt;x; аналогично для II отрасли функция прибыли равна Сx, а возврата – Dx (Dxlt;x).
В конце года все возвращенные средства заново перераспределяются между I и II отраслями, новые средства не поступают, прибыль в производство не вкладывается.Количество средств, выделенное на развитие двух отраслей в начале периода, составляет z1=100 единиц. Требуется распределить средства между отраслями на каждый год планируемого периода так, чтобы суммарный доход, полученный от этих отраслей за три года, был максимальным.
Коэффициенты А, В, С и D для 30 вариантов приведены ниже.
| Варианты | ||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
А | 3 | 4 | 4 | 3 | 5 | 2 | 6 | 1 | 5 | 3 | 7 | 8 | 3 | 2 | 6 |
В | 0,5 | 0,7 | 0,3 | 0,3 | 0,7 | 0,8 | 0,2 | 0,2 | 0,7 | 0,8 | 0,4 | 0,3 | 0,8 | 0,7 | 0,1 |
С | 4 | 6 | 8 | 1 | 7 | 4 | 4 | 4 | 6 | 6 | 4 | 6 | 5 | 4 | 2 |
D | 0,2 | 0,4 | 0,6 | 0,9 | 0,3 | 0,4 | 0,7 | 0,6 | 0,4 | 0,4 | 0,9 | 0,5 | 0,3 | 0,3 | 0,8 |
| Варианты | ||||||||||||||
| 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
А | 4 | 3 | 4 | 8 | 6 | 2 | 2 | 2 | 5 | 6 | 3 | 1 | 4 | 3 | 5 |
В | 0,4 | 0,9 | 0,7 | 0,3 | 0,3 | 0,9 | 0,7 | 0,3 | 0,5 | 0,2 | 0,8 | 0,9 | 0,4 | 0,2 | 0,7 |
С | 3 | 4 | 7 | 6 | 4 | 4 | 3 | 1 | 7 | 4 | 5 | 3 | 2 | 2 | 6 |
D | 0,6 | 0,4 | 0,3 | 0,8 | 0,6 | 0,5 | 0,2 | 0,8 | 0,2 | 0,7 | 0,4 | 0,4 | 0,8 | 0,6 | 0,3 |
2.
Планируется деятельность двух отраслей производства на п лет. Начальные ресурсы s0. Средства х, вложенные в I отрасль в начале года, дают в конце года прибыль f1(x) и возвращаются в размере q1(x)lt;x; аналогично для II отрасли функция прибыли равна f2(x), а возврата – q2(x) (q2(x)lt;x). В конце года все возвращенные средства заново перераспределяются между I и II отраслями, новые средства не поступают, прибыль в производство не вкладывается.Требуется распределить имеющиеся средства s0 между двумя отраслями производства на п лет так, чтобы суммарная прибыль от обеих отраслей за п лет оказалась максимальной.
Необходимо:
а) построить модель ДП для задачи и вычислительную схему;
б) решить задачу при : s0=100 ед., п=3, f1(x)=8х, q1(x)=0,4x, f2(x)=6x, q2(x)=0,7x.
3. s0=400 ед., п=4, f1(x)=0,4х, q1(x)=0,5x, f2(x)=0,3x, q2(x)=0,8x.
4. s0=100 ед., п=4, f1(x)=0,1х2, q1(x)=0,75x, f2(x)=0,5x, q2(x)=0,3x.
5 – 13. Задачи о нахождении оптимальных маршрутов перевозки груза из пункта 1 в конечный пункт.
5. На сети дорог, изображенной на рис. 1, а, б, указаны стоимости перевозки единицы груза между отдельными пунктами сети. Найти наиболее экономный маршрут доставки груза из пункта А в пункт Б. Чему равны суммарные затраты по доставке единицы груза оптимальным маршрутом?
|
|
Рис. 1,а | Рис. 1,б |
6. На сети дорог, изображенной на рис. 2, а, б, указаны стоимости перевозки единицы груза между отдельными пунктами сети. Найти на сети маршруты, ведущие
|
|
Рис. 2,а | Рис. 2,б |
в конечный пункт 12 из всех остальных пунктов, при перевозке груза по которым затраты минимизируются. Определить величину этих затрат для каждого найденного оптимального маршрута.
7. Определить экономный маршрут движения транспорта из начального пункта А
|
|
Рис. 3,а | Рис. 3,б |
в конечный пункт Б на сети дорог, изображенной на рис. 3, а, б. Стоимости между промежуточными пунктами сети на рисунке указаны. Чему равна стоимость оптимального маршрута?
8. На сетевом графике комплекса работ, изображенном на рис. 4, а, б, найти
|
|
Рис. 4,а | Рис. 4,б |
критический путь и определить критический срок.
9 – 12. Найти оптимальные маршрут и расстояние из пункта 1 в конечный пункт 10 (рис. 5, а, б; 6 а, б).
|
|
Рис. 5, а | Рис. 5, б |
|
|
Рис. 6,а | Рис. 6,б |
13 (10 вариантов). На данной сети дорог (рис. 7) имеется несколько маршрутов, по которым можно доставить груз из пункта 1 в пункт 10. Известны стоимости cij перевозки единицы груза между пунктами сети. Найти наиболее экономный маршрут доставки груза из пункта 1 в пункт 10 и соответствующие ему затраты. | |
Рис. 7 |
Все необходимые данные для 10 вариантов приведены в таблице.
№№ | с12 | с13 | с14 | с25 | с27 | с35 | с36 | с37 | с45 | с46 | с47 | с58 | с59 | с68 | с69 | с79 | с8,10 | с9,10 |
1 | 7 | 3 | 5 | 2 | 7 | 9 | 3 | 1 | 8 | 4 | 5 | 2 | 6 | 1 | 9 | 4 | 3 | 8 |
2 | 4 | 8 | 4 | 6 | 1 | 5 | 3 | 5 | 4 | 8 | 2 | 7 | 4 | 9 | 6 | 1 | 7 | 2 |
3 | 9 | 2 | 5 | 3 | 7 | 4 | 6 | 8 | 1 | 3 | 5 | 8 | 7 | 1 | 4 | 5 | 9 | 5 |
4 | 1 | 6 | 2 | 5 | 3 | 6 | 8 | 4 | 7 | 2 | 9 | 5 | 3 | 6 | 1 | 4 | 6 | 1 |
5 | 5 | 3 | 8 | 2 | 5 | 8 | 1 | 7 | 5 | 9 | 1 | 3 | 5 | 8 | 4 | 9 | 2 | 7 |
6 | 8 | 1 | 5 | 9 | 2 | 6 | 8 | 4 | 5 | 2 | 6 | 1 | 8 | 3 | 6 | 2 | 5 | 9 |
7 | 3 | 5 | 4 | 1 | 6 | 2 | 7 | 4 | 6 | 8 | 3 | 7 | 2 | 9 | 2 | 8 | 1 | 3 |
8 | 6 | 2 | 6 | 7 | 3 | 9 | 2 | 8 | 5 | 2 | 9 | 4 | 6 | 7 | 4 | 6 | 7 | 6 |
9 | 1 | 9 | 3 | 8 | 7 | 4 | 9 | 3 | 7 | 4 | 8 | 6 | 3 | 1 | 8 | 1 | 9 | 4 |
10 | 4 | 6 | 1 | 3 | 5 | 7 | 3 | 6 | 2 | 5 | 9 | 1 | 8 | 2 | 3 | 5 | 3 | 8 |
14 – 38.
Задачи о замене оборудования.Плановый период эксплуатации оборудования рассчитай на n лет. В конце этого периода имеющееся оборудование должно быть продано. Стоимость нового оборудования равна соst. Даны также ликвидная стоимость likv(i) и затраты zаtr(i) на содержание в течение одного года оборудования возраста i лет, i=0,1,..., n. Требуется найти оптимальную стратегию замены оборудования за указанный временной период, минимизирующий суммарные затраты.
14. n= 4, соst=8500, |
| 15. n=4, соst=3000, | ||||||||||||||||||||||||||||||||||||
|
|
|
16. n=4, соst=8400, |
| 17. n=4, соst=1000, | ||||||||||||||||||||||||||||||||||||
|
|
|
18. n=4, соst=9000, |
| 19. n=4, соst=4000, | |||||||||||||||||||||||||||||||||||||||
|
|
|
20. n=5, соst=5400, | 21. n=5, соst=1100, | |||||||||||||||||||||||||||||||||||||||||||
|
|
22. n=5, соst=3200, | 23. n=5, соst=3000, | |||||||||||||||||||||||||||||||||||||||||||
|
|
24. п=6, соst=3000, | 25. n=6, соst=2600, | |||||||||||||||||||||||||||||||||||||||||||||||||
|
|
26. п=6, соst=1500, | 27. n=6, соst=4000, | |||||||||||||||||||||||||||||||||||||||||||||||||
|
|
28. п=7 соst=5500, | 29. n=7, соst=2000, | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
30. п=7 соst=1100, | 31. n=7, соst=3000, | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
32. п=8 соst=1000, | 33. n=8, соst=1300, | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
34. п=5 соst=8000, | 35. 10, соst=7500, а данные в таблице необходимо умножить на 10. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
36. n=5, соst=4000, likv(i)=соst·2-i, zаtr(i)=600(i+1).
37. n=5, соst=8000, likv(i)=соst·2-i, zаtr(i)=0,1соst·(i+1).
38. n=5, соst(k)=5000+5000(k-1), k – год покупки, k=1, 2, …, 5,
likv(i)=соst(k) 2-i, zаtr(i)=0,1соst(k)·(i+1).
39 – 46. Задачи об оптимальном распределении капиталовложений между п предприятиями.
Группе из п предприятий П1, П2, .... ,Пп выделяются дополнительные средства на реконструкцию и модернизацию производства. Известна матрица f, в которой на позиции (i, k) находится величина fik, fik?0, равная приросту выпуска продукции на предприятии Пk, при выделении ему дополнительных средств в размере i ден. ед. (i=0, 1, …, m; k=1, 2, ..., n). Требуется так распределить между предприятиями общую сумму средств в m ден. ед., чтобы суммарный прирост выпуска продукции был максимальным. Вложения кратны ?.
39. fТ=, п=3, т=9, ?=1.
40. fТ=, п=4, т=5, ?=1.
41. fТ=, п=4, т=9, ?=1.
42. В условиях задачи 39 найти оптимальное распределение средств т=8.
43. В условиях задачи 40 найти оптимальное распределение средств между 2-, 3- и 4-м предприятиями.
44. fТ=, п=4, т=5, ?=1.
45. fТ=, п=8, т=10, ?=1.
46 (10 вариантов). п=4, т=250, ?=50. Значения коэффициентов матрицы f для 10 вариантов приведены в таблице (при т=0 коэффициенты f11=f12=f13=f14=0).
№№ | fij | |||||||||||||||||||
f21 | f22 | f23 | f24 | f31 | f32 | f33 | f34 | f41 | f42 | f43 | f44 | f51 | f52 | f53 | f54 | f61 | f62 | f63 | f64 | |
1 | 5 | 7 | 6 | 4 | 9 | 10 | 8 | 11 | 21 | 20 | 21 | 19 | 33 | 34 | 32 | 35 | 38 | 39 | 40 | 41 |
2 | 8 | 10 | 7 | 10 | 13 | 12 | 14 | 13 | 22 | 21 | 22 | 23 | 31 | 38 | 29 | 30 | 39 | 40 | 38 | 41 |
3 | 11 | 12 | 10 | 11 | 16 | 15 | 17 | 14 | 23 | 24 | 22 | 25 | 32 | 31 | 32 | 30 | 38 | 39 | 40 | 38 |
4 | 10 | 9 | 7 | 8 | 15 | 16 | 13 | 14 | 24 | 22 | 20 | 21 | 33 | 34 | 31 | 32 | 40 | 39 | 41 | 40 |
5 | 12 | 13 | 11 | 11 | 17 | 15 | 16 | 18 | 23 | 25 | 21 | 22 | 34 | 33 | 35 | 34 | 42 | 41 | 43 | 44 |
6 | 21 | 20 | 22 | 23 | 30 | 28 | 31 | 29 | 42 | 41 | 40 | 41 | 51 | 52 | 53 | 50 | 62 | 63 | 61 | 64 |
7 | 22 | 23 | 24 | 21 | 31 | 30 | 32 | 29 | 43 | 41 | 42 | 40 | 52 | 53 | 51 | 53 | 63 | 64 | 65 | 66 |
8 | 23 | 24 | 25 | 22 | 32 | 31 | 33 | 30 | 44 | 43 | 42 | 41 | 53 | 52 | 54 | 55 | 70 | 72 | 71 | 73 |
9 | 25 | 26 | 27 | 28 | 34 | 33 | 35 | 35 | 46 | 46 | 45 | 44 | 57 | 58 | 56 | 55 | 78 | 77 | 79 | 80 |
10 | 15 | 12 | 17 | 13 | 32 | 30 | 33 | 31 | 39 | 38 | 40 | 37 | 46 | 45 | 47 | 44 | 52 | 54 | 60 | 63 |
Еще по теме Динамическое программирование:
- Общая постановка задачи динамического программирования
- 16.5. Задача динамического программирования в терминах теории графов.
- 3.5. Нелинейное и динамическое программирование; понятие об имитационном моделировании
- 16.4. Решение задачи о кратчайшем пути методами динамического программирования.
- 9.4. Математика элементы векторной оптимизации; элементы сетевого планирования; модели управления запасами; динамическое программирование; оптимальное управление
- Основные этапы развития технологий программирования Программирование в кодах и ассемблер
- • Принцип оптимальности в планировании и управлении, общая задача оптимального программирования • Формы записи задачи линейного программирования и ее экономическая интерпретация • Математический аппарат • Геометрическая интерпретация задачи • Симплексный метод решения задачи 2.1. Принцип оптимальности в планировании и управлении, общая задача оптимального программирования
- Модульное программирование
- Язык программирования
- 3.3. Целочисленное программирование
- б. Линейное программирование
- Программирование государственных финансов
- Визуальное программирование интерфейса
- Программирование, управляемое событиями
- Языки программирования высокого уровня
- Параметрическое программирование 1 (35 вариантов).