Задача оптимального распределения инвестиций. Решение различных практических задач динамического программирования: Оптимальное распределение ресурсов
Такого рода задачи основаны на функции Беллмана и при решении используется метод обратной прогонки (см. Типовые задания). Также можно воспользоваться сервисом Процедура прямой прогонки .
Инструкция . Выберите количество предприятий и количество строк (количество вариантов эффективного вложения), нажмите Далее (см. Пример заполнения). Если доход и остатки предприятий задан в виде функций f(x) и g(x) , задача решается через этот калькулятор .
Пример №1 . Определите оптимальный план расширения производства трех предприятий, если известна их прибыль в год при отсутствии вложений и при инвестировании 1, 2, 3 или 4 млн. Определите, при каком инвестировании будет максимальный процент прироста прибыли.
| f1 | f2 | f3 | x i |
| 40 | 30 | 35 | 0 |
| 90 | 110 | 95 | 1 |
| 395 | 385 | 270 | 2 |
| 440 | 470 | 630 | 3 |
| 620 | 740 | 700 | 4 |
I этап. Условная оптимизация
.
1-ый шаг. k = 3.
| e 2 | u 3 | e 3 = e 2 - u 3 | f 3 (u 3) | F* 3 (e 3) | u 3 (e 3) |
| 1 | 0 | 1 | 35 | ||
| 1 | 0 | 95 | 95 | 1 | |
| 2 | 0 | 2 | 35 | ||
| 1 | 1 | 95 | |||
| 2 | 0 | 270 | 270 | 2 | |
| 3 | 0 | 3 | 35 | ||
| 1 | 2 | 95 | |||
| 2 | 1 | 270 | |||
| 3 | 0 | 630 | 630 | 3 | |
| 4 | 0 | 4 | 35 | ||
| 1 | 3 | 95 | |||
| 2 | 2 | 270 | |||
| 3 | 1 | 630 | |||
| 4 | 0 | 700 | 700 | 4 |
2-ый шаг. k = 2.
| e 1 | u 2 | e 2 = e 1 - u 2 | f 2 (u 2) | F* 2 (e 1) | F 1 (u 2 ,e 1) | F* 2 (e 2) | u 2 (e 2) |
| 1 | 0 | 1 | 30 | 95 | 125 | 125 | 0 |
| 1 | 0 | 110 | 0 | 110 | |||
| 2 | 0 | 2 | 30 | 270 | 300 | ||
| 1 | 1 | 110 | 95 | 205 | |||
| 2 | 0 | 385 | 0 | 385 | 385 | 2 | |
| 3 | 0 | 3 | 30 | 630 | 660 | 660 | 0 |
| 1 | 2 | 110 | 270 | 380 | |||
| 2 | 1 | 385 | 95 | 480 | |||
| 3 | 0 | 470 | 0 | 470 | |||
| 4 | 0 | 4 | 30 | 700 | 730 | ||
| 1 | 3 | 110 | 630 | 740 | 740 | 1 | |
| 2 | 2 | 385 | 270 | 655 | |||
| 3 | 1 | 470 | 95 | 565 | |||
| 4 | 0 | 740 | 0 | 740 |
3-ый шаг. k = 1.
| e 0 | u 1 | e 1 = e 0 - u 1 | f 1 (u 1) | F* 1 (e 0) | F 0 (u 1 ,e 0) | F* 1 (e 1) | u 1 (e 1) |
| 1 | 0 | 1 | 40 | 125 | 165 | 165 | 0 |
| 1 | 0 | 90 | 0 | 90 | |||
| 2 | 0 | 2 | 40 | 385 | 425 | 425 | 0 |
| 1 | 1 | 90 | 125 | 215 | |||
| 2 | 0 | 395 | 0 | 395 | |||
| 3 | 0 | 3 | 40 | 660 | 700 | 700 | 0 |
| 1 | 2 | 90 | 385 | 475 | |||
| 2 | 1 | 395 | 125 | 520 | |||
| 3 | 0 | 440 | 0 | 440 | |||
| 4 | 0 | 4 | 40 | 740 | 780 | 780 | 0 |
| 1 | 3 | 90 | 660 | 750 | |||
| 2 | 2 | 395 | 385 | 780 | |||
| 3 | 1 | 440 | 125 | 565 | |||
| 4 | 0 | 620 | 0 | 620 |
Примечание : Столбцы 1 (вложенные средства), 2 (проект) и 3 (остаток средств) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация .
Из таблицы 3-го шага имеем F* 1 (e 0 = 4 млн.руб.) = 780 тыс.руб., то есть максимальная прибыль от инвестирования e 0 = 4 млн.руб. равна 780 тыс.руб.
Из этой же таблицы получаем, что первому предприятию следует выделить u* 1 (e 0 = 4 млн.руб.) = 0 млн.руб.
При этом остаток средств составит: e 1 = e 0 - u 1 , e 1 = 4 - 0 = 4 млн.руб.
Из таблицы 2-го шага имеем F* 2 (e 1 = 4 млн.руб.) = 740 тыс.руб., т.е. максимальная прибыль при e 1 = 4 млн.руб. равна 740 тыс.руб.
Из этой же таблицы получаем, что второму предприятию следует выделить u* 2 (e 1 = 4 млн.руб.) = 1 млн.руб.
При этом остаток средств составит: e 2 = e 1 - u 2 , e 2 = 4 - 1 = 3 млн.руб.
Последнему предприятию достается 3 млн.руб. Итак, инвестиции в размере 4 млн.руб. необходимо распределить следующим образом: первому предприятию ничего не выделять, второму предприятию выделить 1 млн.руб., третьему предприятию выделить 3 млн.руб., что обеспечит максимальную прибыль, равную 780 тыс.руб.
Пример №2 . Имеются 4 предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятии в зависимости от выделенных средств Х представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.
Лабораторная работа
Информатика, кибернетика и программирование
Средства X выделенные kому предприятию приносит в конце года прибыль. Функции заданы таблично: X f1X f2X f3X f4X 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 Определить какое количество средств нужно выделить каждому предприятию чтобы суммарная прибыль равная сумме прибылей полученных от каждого предприятия была наибольшей. Пусть количество средств выделенных kому предприятию. Уравнения на м шаге удовлетворяют условию: либо kому предприятию ничего не выделяем: либо не больше того что...
Лабораторная работа 4_2. Решение задачи о распределении ресурсов методом динамического программирования.
Цель работы изучить возможности табличного процессора MS Excel для решения задачи распределения ограниченных ресурсов методом динамического программирования.
Краткие теоретические сведения
Построение модели динамического программирования (ДП) и применение метода ДП для решения задачи сводится к следующему:
- выбирают способ деления процесса управления на шаги;
- определяют параметры состояния и переменные управления X k на каждом шаге;
- записывают уравнения состояний;
- вводят целевые функции k -ого шага и суммарную целевую функцию;
- вводят в рассмотрение условные максимумы (минимумы) и условное оптимальное управление на k -ом шаге: .
- Записывают основные для вычислительной схемы ДП уравнения Беллмана для и по правилу:
- Решают последовательно уравнения Беллмана (условная оптимизация) и получают две последовательности функций и.
- После выполнения условной оптимизации получают оптимальное решение для конкретного состояния:
а) и
б) по цепочке оптимальное управление (решение) .
Постановка задачи динамического программирования в общем виде.
Условие задачи . Планируется деятельность четырех промышленных предприятий на очередной год. Начальные средства: у.е. Размеры вложения в каждое предприятие кратны 1 условной единице. Средства X , выделенные k
|
f 1 (X) |
f 2 (X) |
f 3 (X) |
f 4 (X) |
|
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль (равная сумме прибылей, полученных от каждого предприятия), была наибольшей.
Решение. Пусть - количество средств, выделенных k -ому предприятию. Суммарная прибыль равна. Переменные X удовлетворяют ограничениям: . Требуется найти переменные, удовлетворяющие данным ограничениям и обращающие в максимум функцию Z .
Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств можно рассматривать как 4-шаговый, номер шага совпадает с номером предприятия; выбор переменных уравнения на 1, 2, 3, 4 шагах соответственно; - конечное состояние процесса распределения равно нулю, т.к. все средства должны быть вложены в производство, =0 .
Уравнения состояний и схему распределения можно представить в виде:
Здесь - параметр состояния количество средств, оставшихся после k -ого шага, т.е. средства, которые остается распределить между оставшимися (4- k ) предприятиями.
Введем в рассмотрение функцию - условно оптимальную прибыль, полученную от -го, (k +1 )-го, …, 4-го предприятий, если между ними распределялись оптимальным образом средства). Уравнения на -м шаге удовлетворяют условию: (либо k -ому предприятию ничего не выделяем: , либо не больше того, что имеем к k -ому шагу:).
Уравнения Беллмана имеют вид:
Решение уравнений осуществляется путем последовательной оптимизации каждого шага.
4 шаг. Все средства, оставшиеся к 4-ому шагу, следует вложить в 4-е предприятие, поскольку согласно таблице прибыли монотонно возрастают. При этом для возможных значений получим:
3 шаг . Делаем предположения относительно остатка средств к 3-ему шагу: может принимать значения 0,1,2,3,4,5 (=0, если все средства отданы 1-ому и 2-ому предприятиям и т.д.). В зависимости от этого выбираем и сравниваем для разных при фиксированных значениях значения суммы. Для каждого максимальное из этих значений есть - условная оптимальная прибыль, полученная при оптимальном распределении средств между 3-м и 4-м предприятиями. Полученные значения для приведены в таблице в графах 5 и 6 соответственно.
|
S k-1 |
k =3 |
k =2 |
k =1 |
||||||||
|
f 3 (X 3 )+ |
f 2 (X 2 )+ |
f 1 (X 1 )+ |
|||||||||
|
0+4=4 3+0=3 |
0+4=4 6+0=6 |
0+6=6 8+0=8 |
|||||||||
|
0+6=6 3+4=7 4+0=4 |
0+7=7 6+4=10 9+0=9 |
0+10=10 8+6=14 10+0=10 |
|||||||||
|
0+8=8 3+6=9 4+4=8 7+0=7 |
0+9=9 6+7=13 9+4=13 11+0=11 |
0+13=13 8+10=18 10+6=16 11+0=11 |
|||||||||
|
0+13=13 3+8=11 4+6=10 7+4=11 11+0=11 |
0+13=13 6+9=15 9+7=16 11+4=15 13+0=13 |
0+16=16 8+13=21 10+10=20 11+6=17 12+0=12 |
|||||||||
|
0+16=16 3+13=16 4+8=12 7+6=13 11+4=15 18+0=18 |
0+18=18 6+13=19 9+9=18 11+7=18 13+4=17 15+0=15 |
0+19=19 8+16=24 10+13=23 11+10=21 12+6=18 18+0=18 |
|||||||||
2 шаг k =2. Для всех возможных значений значения и находятся в столбцах 8 и 9 соответственно; первые слагаемые в столбце 7 значения взяты из условия, вторые слагаемые взяты из столбца 5 при.
1 шаг . Условная оптимизация проведена в таблице при k =1 для.
Если, то=5; прибыль, полученная от четырех предприятий при условии, что =5 средств между оставшимися тремя предприятиями будут распределены оптимально, равна.
Если, то=4; суммарная прибыль при условии, что =4 средств между оставшимися тремя предприятиями будут распределены оптимально, равна.
Аналогично, при, и;
При, и;
При, и;
Сравнивая полученные значения, получим при.
Вычисляя, получим, а по таблице в столбце 9 находим. Далее находим, а в столбце 6 . Наконец, и. Оптимальное решение.
Ответ. Максимум суммарной прибыли равен 24 у.е. при условии, что 1-ому предприятию выделена 1 у.е.; 2-ому предприятию выделено 2 у.е.; 3-ому предприятию - 1 у.е.; 4-ому предприятию - 1 у.е.
Реализация задачи в MS Excel
- Ввод исходных данных в таблицу показан на Рис.1.
Рис.1. Ввод исходных данных в ячейки рабочего листа MS Excel
2. Порядок заполнения ячеек таблицы:
1). В ячейку E 15 введем формулу ИНДЕКС($B$3:$F$8;ПОИСКПОЗ($C15;$B$3:$B$8);G$12+1) и скопируем формулу в диапазоне ячеек с E 15 до E 35.
2). В ячейку F 15 введем формулу
ИНДЕКС($B$3:$F$8;ПОИСКПОЗ($D15;$B$3:$B$8);5) и скопируем формулу в диапазон ячеек с F 15 до F 35.
3). В ячейку G 15 введем формулу E 15+ F 15 и скопируем формулу в диапазон: G 15 - G 35.
4). Находим максимальное значение для каждого состояния от 0 до 5, для этого в ячейку H 15 введем формулу МАКС(G15); после ввода формулы в ячейку H 16 необходимо изменить диапазон с G 16 на G 16: G 17 и т.д. по всему столбику до ячейки H 30 (Рис.2а).
3. Находим значение управления, которому соответствует максимальное значение функции, для этого в ячейку I 15 введем формулу ИНДЕКС($ C 15: G 15;ПОИСКПОЗ(H 15; G 15;0);1), скопируем формулу в ячейку I 16 и увеличим диапазон, в результате в ячейке I 16 получим: ИНДЕКС($ C 16: G 17;ПОИСКПОЗ(H 16; G 16: G 17;0);1). Далее скопируем формулу в ячейки I 18, I 21, I 25, I 30 , постепенно увеличивая диапазон (Рис.2б)
Рис.2а. Вид рабочего листа с формулами, k =3.
Рис.2б (правая часть рабочего листа с формулами, k =3
В результате получим:
Рис. 3 . Результат выполнения первого шага (k =3).
4. Выделяем диапазон E 15: I 35, выполняем команду Копировать J 15 и выполняем команду Вставить .
5. Изменим формулу функции. В ячейки K 15, K 16, K 18, K 21, K 25, K 30 введем соответственно максимальные значения предыдущего шага, находящиеся в ячейках H 15, H 16, H 18, H 21, H 25, H 30. В остальные ячейки поместим значения, стоящие в этом же столбце и соответствующие предыдущим S k . :
В ячейку K 17 копируем значения ячейки К15;
в ячейки К19 и К20 значения К16 и К17;
в К22:К24 значения К18:К20;
в К26:К29 значения К21:К24;
в К31:К35 значения К25:К29;
В результате получим:
Рис.4. Результат выполнения второго шага (k =2).
6. Выделяем диапазон ячеек J 15: N 35, выполняем команду Копировать , устанавливаем курсор в ячейку O 15, выполняем команду Вставить . В результате получаем заполненную таблицу с решением для k =1 (Рис.5)
7. Объясним полученные результаты: при. Вычисляя, получим, а по таблице в столбце 12 находим. Далее определяем, а из столбца 6 . Наконец, и. Таким образом, оптимальное значение, а значение функции 24 у.е., что согласуется с данными, полученными вручную.
Рис.6. Результат выполнения третьего шага (k =1).
Контрольные упражнения. Варианты.
1. Планируется деятельность четырех промышленных предприятий на очередной год. Начальные средства у.е. Размеры вложения в каждое предприятие кратны 1 у.е. Средства X , выделенные k -ому предприятию (), приносит в конце года прибыль. Функции заданы таблично:
|
f 1 (X) |
f 2 (X) |
f 3 (X) |
f 4 (X) |
|
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.
2. Планируется деятельность трех промышленных предприятий на очередной год. Начальные средства: у.е. Размеры вложения в каждое предприятие кратны 1 у.е. Средства X , выделенные k -ому предприятию (), приносит в конце года прибыль. Функции заданы таблично:
|
f 1 (X) |
f 2 (X) |
f 3 (X) |
|
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль, была наибольшей.
А также другие работы, которые могут Вас заинтересовать |
|||
| 58796. | Geographical Outlook | 977.5 KB | |
| By the end of the lesson you should be able to recognize and understand new words and word combinations in the text, to read and understand the gist and details despite the natural difficulties. | |||
| 58797. | Інформація та інформаційні процеси. Обчислювальна система | 128 KB | |
| Загальна характеристика теми. Правила техніки безпеки в кабінеті ПЕОМ. Інформатика. Поняття інформації. Інформація і шум. Інформаційні процеси. Інформація й повідомлення. | |||
| 58798. | Операційні системи | 126 KB | |
| Робочий стіл. Основні об’єкти Windows. Виділення об’єкта. Операції, властивості та основні команди для роботи з об’єктами. Контекстне меню об’єкта. Ярлики та їх призначення. | |||
| 58799. | Основи роботи з дисками | 144.5 KB | |
| Загальна характеристика теми. Форматування диска. Діагностика та дефрагментація дисків. Відновлення інформації на диску. Правила записування та зчитування інформації з дискет. | |||
| 58800. | Текстовий редактор | 190 KB | |
| Системи опрацювання текстiв i їх основнi функцiї. Завантаження текстового редактора. Iнтерфейс редактора. Інформаційний рядок. Режими екрана, використання вікон. | |||
| 58801. | Графічний редактор | 708 KB | |
| Загальна характеристика теми. Машинна графiка. Графiчний екран. Система опрацювання графiчної інформації. Вказiвки малювання графiчних примiтивiв при роботi з редактором. Типи графічних файлів. | |||
| 58802. | Електронні таблиці | 280.5 KB | |
| Навчальна. Охарактеризувати нову тему, висвітлити її роль в курсі інформатики. Ввести поняття електронна таблиця. Ознайомити учнів з програмами опрацювання ЕТ, правилами введення та редагування інформації в ЕТ, способами форматування ЕТ. | |||
| 58803. | Системи управління базами даних (СУБД) | 156.5 KB | |
| Бази даних. Фактографічні й документальні БД. Iєрархiчна, мережева, реляцiйна модель бази даних. Основнi елементи та об’єкти бази даних: поле, запис, файл. СУБД. | |||
Динамическое программирование (ДП) – это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой.
Приведем
общую постановку задачи ДП. Рассматривается
управляемый процесс (распределение
средств между предприятиями, использование
ресурсов в течение ряда лет и т.п.). В
результате управления система (объект
управления) переводится из начального
состояния
в состояние
.
Предположим, что управление можно
разбить на
шагов. На каждом шаге выбирается одно
из множества допустимых управлений
,
переводящее систему в одно из состояний
множества
.
Элементы множества
и
определяются из условий конкретной
задачи. Последовательность состояний
системы можно изобразить в виде графа
состояний, представленного на рис. 3.1.
На
каждом шаге n
достигается эффект
.
Предположим, что общий эффект является
суммой эффектов, достигнутых на каждом
шаге. Тогда задача ДП формулируется
так: определить такое допустимое
управление
,
переводящее систему из состояния
в состояние
,
при котором функция цели
принимает наибольшее (наименьшее)
значение, т.е.
Решение задач методом ДП осуществляется на основе принципа оптимальности, который был сформулирован американским ученым Р.Беллманом: каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Обозначим
через
условно-оптимальное значение целевой
функции на интервале от шагаn
до последнего
-го
шага включительно, при условии, что
передn
-ым
шагом система находилась в одном из
состояний множества
,
а наn
-ом
шаге было выбрано такое управление из
множества
,
которое обеспечило целевой функции
условно-оптимальное значение, тогда
условно-оптимальное значение целевой
функции в интервале от (n
+1
)-го
до
-го
шага включительно.
В принятых обозначениях принцип оптимальности Беллмана можно записать в математической форме следующим образом
Равенство (3.1) называется основным функциональным уравнением динамического программирования. Для каждой конкретной задачи уравнение имеет особый вид.
Вычислительная процедура метода ДП распадается на два этапа: условную и безусловную оптимизацию.
На этапе условной оптимизации в соответствии с функциональным уравнением определяются оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего.
На
этапе безусловной
оптимизации
шаги рассматриваются, начиная с первого.
Поскольку исходное состояние
известно, выбирается оптимальное
управление из множества
.
Выбранное оптимальное управление
приводит систему во вполне определенное
состояние
.
Благодаря тому, что исходное состояние
в начале второго шага известно, становится
возможным выбрать оптимальное управление
на втором шаге
и т.д. Таким образом, строится цепь
взаимосвязанных решений безусловной
оптимизации.
3.1. Задача оптимального распределения ресурсов
Пусть
на реконструкцию и модернизацию основного
производства объединению выделяется
некоторый объем материальных ресурсов
Х
.
Имеется N
предприятий, между которыми нужно
распределить данный ресурс. Обозначим
через
прибыль, которому приносит народному
хозяйству выделениеj
-му
предприятию
единиц ресурса. Предполагается, что
размер прибыли зависит как от выделенного
количества ресурса, так и от предприятия.
Причем прибыль, получаемая предприятиями
измеряется в одних и тех же единицах и
общая прибыль объединения состоит из
прибылей отдельных предприятий.
Необходимо найти оптимальный план
распределения ресурсов между предприятиями,
при котором общая прибыль объединения
будет максимальной.
Поставленную задачу нужно рассмотреть как многошаговую.
На
этапе условной оптимизации будем
рассматривать эффективность вложения
средств на одном (например, на первом
предприятии), на двух предприятиях
вместе (на первом и втором), на трех
предприятиях вместе (на первом, втором
и третьем) и т.д., и наконец, на всех N
предприятиях вместе. Задача состоит в
определении наибольшего значения
функции
при условии, что
.
Воспользуемся
рекуррентным соотношением Беллмана
(3.1), которое для данной задачи приводит
к следующим функциональным уравнениям
при
:
Здесь
функция
определяет максимальную прибыль первого
предприятия при выделении емуx
единиц ресурса, функция
определяет максимальную прибыль первого
и второго предприятий вместе при
выделении имx
единиц ресурса, функция
определяет максимальную прибыль первого,
второго и третьего предприятий вместе
при выделении имx
единиц ресурса и т.д., и наконец, функция
определяет максимальную прибыль всех
предприятий вместе при выделении имx
единиц ресурса.
На этапе безусловной оптимизации определяется оптимальный план распределения ресурсов между предприятиями.
Пример 3.1.
Для
увеличения объемов выпуска пользующейся
повышенным спросом продукции четырем
предприятиям производственного
объединения выделены средства в размере
50 млн. руб. Каждому из предприятий может
быть выделено: 0, 10, 20, 30, 40 или 50 млн. руб.
При этом ежегодный прирост выпуска
продукции каждым из предприятий
в зависимости от капиталовложений
известен и приведен в табл. 3.1.
Таблица 3.1
|
Объем выделенных средств x (млн. руб.) |
Ежегодный прирост выпуска продукции (млн. руб.), в зависимости от объема выделенных средств |
|||
|
|
|
|
|
|
Найти оптимальный план распределения средств между предприятиями, обеспечивающий максимальный ежегодный прирост выпуска продукции производственным объединением.
Краткая теория
Динамическое программирование (иначе - динамическое планирование) - это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой. Многие экономические процессы расчленяются на шаги естественным образом. Это все процессы планирования и управления, развиваемые во времени. Естественным шагом в них может быть год, квартал, месяц, декада, неделя, день и т. д. Однако метод динамического программирования может использоваться при решении задач, где время вообще не фигурирует; разделение на шаги в таких задачах вводится искусственно. Поэтому «динамика» задач динамического программирования заключается в методе решения.
В экономической практике встречается несколько типов задач, которые по постановке или способу решения относятся к задачам динамического программирования. Это задачи оптимального перспективного и текущего планирования во времени. Их решают либо путем составления комплекса взаимосвязанных статических моделей для каждого периода, либо путем составления единой динамической задачи оптимального программирования с применением многошаговой процедуры принятия решений. К задачам динамического программирования следует отнести задачи многошагового нахождения оптимума при размещении производительных сил, а также оптимального быстродействия.
Типичные особенности многошаговых задач.
1. Рассматривается система, состояние которой на каждом шаге определяется вектором . Дальнейшее изменение ее состояния зависит только от данного состояния и не зависит от того, каким путем система пришла в него. Такие процессы называются процессами без последействия.
2. На каждом шаге выбирается одно решение , под действием которого система переходит из предыдущего состояния в новое . Это новое состояние является функцией состояния на начало интервала и принятого в начале интервала решения т. е.
3. Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
4. На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений .
5. Требуется найти такое допустимое управление для каждого шага , чтобы получить экстремальное значение функции цели за все шагов.
Любую многошаговую задачу можно решать по-разному. Во-первых, можно считать неизвестными величинами щ и находить экстремум целевой функции одним из существующих методов оптимизации, т. е. искать сразу все элементы решения на всех шагах. Отметим, что этот путь не всегда приводит к цели, особенно когда целевая функция задана в виде таблиц или число переменных очень велико. Второй путь основан на идее проведения оптимизации поэтапно. Поэтапность отнюдь не предполагает изолированности в оптимизации этапов. Наоборот, управление на каждом шаге выбирается с учетом всех его последствий. Обычно второй способ оптимизации оказывается проще, чем первый, особенно при большом числе шагов. Идея постепенной, пошаговой оптимизации составляет суть метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса в целом. Лучше много раз решать сравнительно простую задачу, чем один раз - сложную.
С первого взгляда идея может показаться тривиальной: если трудно оптимизировать сложную задачу, то следует разбить ее на ряд более простых. На каждом шаге оптимизируется задача малого размера, что уже нетрудно. При этом принцип динамического программирования вовсе не предполагает, что каждый шаг оптимизируется изолированно, независимо от других. Напротив, пошаговое управление должно выбираться с учетом всех его последствий.
Можно сформулировать следующие принципы, лежащие в основе динамического программирования: принцип оптимальности и принцип погружения.
Оптимальное управление на каждом шаге определяется состоянием системы на начало этого шага и целью управления. Или в развернутой форме: оптимальная стратегия обладает таким свойством, что, каковы бы ни были начальное состояние и начальные решения, последующие решения должны приниматься исходя из оптимальной стратегии с учетом состояния, вытекающего из первого решения. Этот принцип имеет довольно простую математическую интерпретацию, выражающуюся в составлении определенных рекуррентных соотношений (функциональных уравнений Р. Беллмана).
Природа задачи, допускающей использование метода динамического программирования не меняется при изменении количества шагов , т. е. форма такой задачи инвариантна относительно . В этом смысле всякий конкретный процесс с заданным числом шагов оказывается как бы погруженным в семейство подобных ему процессов и может рассматриваться с позиции более широкого класса задач.
Реализация названных принципов дает гарантию того, что решение, принимаемое на очередном шаге, окажется наилучшим относительно всего процесса в целом, а не узких интересов данного этапа. Последовательность пошаговых решений приводит к решению исходной -шаговой задачи.
Дадим математическую формулировку принципа оптимальности для задач с аддитивным критерием оптимальности (сепарабельная функция цели). Для простоты будем считать, что начальное и конечное состояния системы заданы. Обозначим через значение функции цели на первом этапе при начальном состоянии системы и при управлении , через -соответствующее значение функции цели только на втором этапе, …., через - на этапе, …, через - на -м этапе. Очевидно, что
Надо найти оптимальное управление такое, что доставляет экстремум целевой функции при ограничениях .
Для решения этой задачи погружаем ее в семейство подобных. Введем обозначения. Пусть - соответственно области определения для подобных задач на последнем этапе, двух последних и т.д.; - область определения исходной задачи. Обозначим через
соответственно условно-оптимальные значения функции цели на последнем этапе, двух последних и т.д., на последних и т.д., на всех этапах.
Начинаем с последнего этапа. Пусть - возможные состояния системы на начало -го этапа. Находим:
Для двух последних этапов получаем:
Аналогично:
…………………….
…………………….
Выражение (5) представляет собой математическую запись принципа оптимальности. Выражение (4) - общая форма записи условно-оптимального значения функции цели для оставшихся этапов. Выражения (1)-(5) называются функциональными уравнениями Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т.е. для нахождения оптимального управления на шагах нужно знать условно-оптимальное управление на предшествующих этапах и т.д. Поэтому функциональные уравнения часто называются рекуррентными (возвратными) соотношениями Беллмана.
Пример решения задачи
Условие задачи
Производственное объединение выделяет четырем входящим в него предприятиям кредит в сумме 100 млн.ден.ед. для расширения производства и увеличения выпуска продукции. По каждому предприятию известен возможный прирост выпуска продукции (в денежном выражении) в зависимости от выделенной ему суммы . Для упрощения вычислений выделяемые суммы кратны 20 млн.ден.ед. При этом предполагаем, что прирост продукции на предприятии не зависит от суммы средств, вложенных в другие предприятия, а общий прирост выпуска в производственном объединении равен сумме приростов, полученных на каждом предприятии объединения.
Требуется найти оптимальное решение распределения кредита между предприятиями, чтобы общий прирост выпуска продукции на производственном объединении был максимальным.
| Выделяемые средства , млн.ден.ед. | Предприятие | №1 | №2 | №3 | №4 | Прирост выпуска продукции на предприятиях млн.ден.ед. | 20 | 10 | 12 | 11 | 16 | 40 | 31 | 24 | 36 | 37 | 60 | 42 | 36 | 45 | 46 | 80 | 62 | 52 | 60 | 63 | 100 | 76 | 74 | 77 | 80 |
Решение задачи
Если сроки со сдачей контрольной работы поджимают, на сайте всегда можно заказать cрочное решение задач по методам оптимальных решений .
Динамическое программирование представляет собой многоэтапный поиск оптимального решения. Оптимизация многошагового процесса базируется на принципе оптимальности Р. Беллмана.
Вычисления в динамическом программировании выполняются рекуррентно - оптимальное решение одной подзадачи используется в качестве исходных данных для поиска оптимального решения следующей подзадачи. Решив последнюю подзадачу, мы получим оптимальное решение исходной задачи.
| Выделяемые средства | 0 | 0 | 0 | 0 | 0 | 20 | 10 | 12 | 11 | 16 | 40 | 31 | 24 | 36 | 37 | 60 | 42 | 36 | 45 | 46 | 80 | 62 | 52 | 60 | 63 | 100 | 76 | 74 | 77 | 80 |
Шаг 1
В соответствии с вычислительной схемой динамического программирования рассмотрим сначала случай , т.е. предположим, что все имеющиеся средства выделяются на реконструкцию и модернизацию одного предприятия. Обозначим через максимально возможный дополнительный доход на этом предприятии, соответствующий выделенной сумме . Каждому значению отвечает вполне определенное (единственное) значение дополнительного дохода, поэтому можно записать, что:
Шаг 2
Пусть теперь , т.е. средства распределяются между двумя предприятиями. Если второму предприятию выделена сумма , то дополнительный доход на нем составит . Оставшиеся другому предприятию средства в зависимости от величины (а значит, и ) позволят увеличить дополнительный доход до максимально возможного значения . При этом условии общий дополнительный доход на двух предприятиях:
Шаг 3
Пусть теперь , т.е. средства распределяются между тремя предприятиями. Если третьему предприятию выделена сумма , то дополнительный доход на нем составит . Оставшиеся средства в зависимости от величины (а значит, и ) позволят увеличить дополнительный доход до максимально возможного значения . При этом условии общий дополнительный доход на трех предприятиях:
Шаг 4
Пусть теперь , т.е. средства распределяются между четырьмя предприятиями. Если четвертому предприятию выделена сумма , то дополнительный доход на нем составит . Оставшиеся средства в зависимости от величины (а значит, и ) позволят увеличить дополнительный доход до максимально возможного значения . При этом условии общий дополнительный доход на четырех предприятиях:
Ответ
Оптимальный план распределения между 4 предприятиями 100 единиц ресурса:
| 0 | 20 | 40 | 40 |
При этом суммарный прирост продукции достигнет максимальной величины, равной 85.
Средняя стоимость решения контрольной работы 700 - 1200 рублей (но не менее 300 руб. за весь заказ). На цену сильно влияет срочность решения (от суток до нескольких часов). Стоимость онлайн-помощи на экзамене/зачете - от 1000 руб. за решение билета.
Все вопросы по стоимости можете задать прямо в чат, предварительно скинув условие задач и сообщив необходимые вам сроки решения. Время ответа - несколько минут.
Примеры близких по теме задач
Основная модель управления запасами
На примере решения задачи рассмотрена основная модель управления запасами (модель Уилсона). Вычислены такие показатели модели как оптимальный размер партии заказа, годовые затраты на хранение, интервал между поставками и точка размещения заказа.
Задача квадратичного программирования
Приведен образец решения задачи квадратичного выпуклого программирования графическим методом.
Игры в смешанных стратегиях
Содержит изложенные в краткой и доступной форме теоретические сведения о матричной игре без седловой точки и способе сведения такой задачи к задаче линейного программирования, для отыскания ее решения в смешанных стратегиях. Приведен пример решения задачи.
Дадим математическую
формулировку принципа оптимальности.
Для простоты будем считать, что
начальное x 0 и конечное x T состояния системы заданы.
Обозначим через z 1 (х 0 , u 1) значение функции
цели на первом этапе при начальном состоянии
системы x 0 и при управлении u 1 , через z 2 (х 1 ,u 2) – соответствующее
значение функции цели только на втором
этапе, ..., через
z i (х i -1 ,u i)
– на i-м этапе, ..., через z N (х N -1 , u N) -на N-м этапе. Очевидно, что
Надо найти оптимальное управление u*= (; ;...;), такое, что доставляет экстремум целевой функции (1) при ограничениях.
Для решения этой задачи погружаем ее в семейство подобных. Введем обозначения. Пусть – соответственно области
определения для подобных
задач на последнем этапе, двух последних
и т. д.;
– область определения исходной задачи.
Обозначим через F 1 (x N -1), F 2 (x N -2), …, F k (x N -k), …, F N (x 0) соответственно условно-оптимальные
значения функции цели на последнем этапе,
двух последних и т. д., на k последних и т. д., на всех N этапах.
Начинаем с последнего этапа. Пусть х N-1 – возможные состояния системы на начало N-го этапа. Находим:
F 1 (x N -1) = z N (x N -1 , u N). (2)
Для двух последних этапов получаем
F 2 (x N -2) = (Z N -1 (x N -2 , u N -1) + F 1 (x N -1)). (3)
Аналогично:
F 3 (x N -3) = (Z N -2 (x N -3 , u N -2) + F 2 (x N -2)). (4)
………………………………………………….
F k (x N -k) = (z N-k +1 (x N -k , u N-k +1) + F k- 1 (x N-k +1)). (5)
…………………………………………………..
F N (x 0) = (z 1 (x 0 , u 1) + F N -1 (x 1)). (6)
Выражение (6) представляет собой математическую запись принципа оптимальности. Выражение (5) – общая форма записи условно-оптимального значения функции цели для k оставшихся этапов. Выражения (2) – (6) называются функциональными уравнениями Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т. е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N – 1 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотношениями Беллмана.
- Особенности задач динамического программирования
На основании выше сказанного можно выделить следующие особенности задач динамического программирования.
- Рассматривается система, состояние которой на каждом шаге определяется вектором x t . Дальнейшее изменение ее состояния зависит только от данного состояния x t и не зависит от того, каким путем система пришла в это состояние. Такие процессы называются процессами без последействия.
- На каждом шаге выбирается одно решение u t , под действием которого система переходит из предыдущего состояния x t -1 в новое х t . Это новое состояние является функцией состояния на начало интервала x t -1 и принятого в начале интервала решения u t , т. е. x t = x t (x t -1 ,u t).
- Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
- На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений.
- Требуется найти такое допустимое управление u t для каждого шага t, чтобы получить экстремальное значение функции цели за все Т шагов.
Любую допустимую последовательность действий для каждого шага, переводящую систему из начального состояния в конечное, называют стратегией управления. Стратегия управления, в результате которой можно получить экстремальное значение функции цели, называется оптимальной.
Геометрическая интерпретация задачи динамического программирования состоит в следующем. Пусть n – размерность пространства состояний. В каждый момент времени координаты системы имеют вполне определенное значение. С изменением времени t могут изменяться значения координат вектора состояния. Назовем переход системы из одного состояния в другое траекторией ее движения в пространстве состояний. Такой переход осуществляется воздействием на координаты состояния. Пространство, в котором координатами служат состояния системы, называется фазовым. Особенно наглядно задачу динамического программирования можно интерпретировать в случае, если пространство состояний двухмерно. Область возможных состояний в этом случае изобразится некоторой фигурой, начальное и конечное состояния системы – точками х 0 , (рис. 1). Управление – это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X 0 или X T , которой эти точки принадлежат.
Рисунок 1
Тогда допустимые управления переводят точки из области Х 0 в X T . Задача динамического программирования геометрически может быть сформулирована следующим образом: найти такую фазовую траекторию, начинающуюся в области Х 0 и оканчивающуюся в области Х T , для которой функция цели достигает экстремального значения. Если в задаче динамического программирования известны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конечные области, то говорят о задаче со свободными концами.
- ЗАДАЧА РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
2.1 Общая постановка задачи
Рассмотрим применение метода динамического программирования на примере распределения средств между шестью объектами реконструкции предприятия горводоканала:
1. Центральная насосно- фильтровальная станция;
2. Восточная насосно- фильтровальная станция;
3. Водопроводная насосная станции перекачки;
4. Центральная станция аэрации;
5. Восточная станция аэрации;
6. Загородная станция аэрации.
Общая сумма средств, предоставленная на развитие составляет не более 195 тысяч гривен. На основе технико-экономических расчетов установлено, что в результате реконструкции в зависимости от количества потраченных средств объекты будут иметь производительность, приведенную в таблице 1.1. Необходимо определить оптимальное распределение средств между объектами реконструкции, которая обеспечит максимальное увеличение производительности этих объектов. Таким образом, в этой задаче используется критерий оптимизации - суммарная производительность предприятий объектов реконструкции.
Таблица 1.1 Входные данные продуктивности объектов реконструкции
Порядковый номер объекта |
Объем ресурсов, выданных на развитие объектов (тыс. грн.) |
|||||||||||||
Продуктивность объектов результате развития (тыс. м3) |
||||||||||||||
- Блок схема программы
Рисунок 1. Основная программа
QtObj – количество объектов
QtRes – количество ресурсов
effMatrix - матрица производительности объектов,
distVector – вектор выделенных ресурсов
Шаг 1. Условная оптимизация
Шаг 2. Безусловная оптимизация
I = QtObj-1,0 формируем вектор результат
Рисунок 2. Ввод данных
distVector – вектор дистанций, effMatrix = матрица производительности
если все элементы матрицы введены
если вектор производительности- не
отрицательный
Рисунок 3. Условная оптимизация,
формируем мартицу выхода (максимум функции цели)
outMatrix – матрица максимума цели
QtObj – количество объектов
QtRes – количество ресурсов
Matrix – матрица производительности
distVect – вектор дистанций (вектор ресурсов)
нет да Если первое предприятие
Поиск максимума
да maxItem = temp; outMatrix[i][j] = maxItem
- Структура алгоритма программы
- Ввод данных – класс DataDlg.
Переменные члены класса.
//вектор для хранения объема ресурсов
std::vector
//матрица производительности объектов
int** effMatrix;
//функция перевода строки в число
int StringToInt(CString);
//функция проверки корректности введенных данных
BOOL FillMatrix();
//функция очистки ресурсов, после закрытия окна
virtual BOOL DestroyWindow();
//функция инициализации диалога
virtual BOOL OnInitDialog();
- Вычисление результатов – основ ной класс программы courseWorkDlg
Переменные члены класса
int Value; //значение производительности
int MaxIndex;// максимальный индекс в векторе ресурсов
int Facility;//предприятие
int Recource;//выделенный ресурс
Item ** outMatrix; //матрица максимума цели
std::vector
void BuildOutMatrix(int **,std::vector
afx_msg void OnBnClickedButton1();// обработчик нажатия на кнопку «Вычислить», который запускает процесс вычислений.
virtual BOOL DestroyWindow();//очистка ресурсов программы
- Вывод результатов класс Report
Назначение данного класса – это вывод вектора результата в табличной форме.
2.4 Результаты работы программы
Начальный ввод данных
- Ввод данных о продуктивности объектов реконструкции
- Если не все поля заполнены
- Если введен неправильный символ
Корректный ввод данных
Показ результата
- Ввод данных
Результат работы программы
Начальный ввод данных
Ввод продуктивности объектов
Приложение.
Листинг программы
int DataDlg::StringToInt(CString str)
const wchar_t* s = T2CW(str);
int val = _wtoi(s);
// все поля заполнены?
BOOL DataDlg::FillMatrix()
bool flag = true;
for (int i = 0; i < Cells.GetSize(); i ++){
for (int j = 0 ; j < Cells.GetAt(i)->Edits.GetSize(); j ++){
CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;
if (temp->m_hWnd != NULL){
temp->GetWindowText(str);
if (str.IsEmpty()){
MessageBox(L"Нужно заполнить все поля", L"Ошибка", MB_ICONERROR | MB_OK);
Описание работы
Целью данной работы является реализация на ЭВМ решения задачи оптимального распределения средств на расширение производства.
Задачи курсовой работы:
Рассмотреть теоретические аспекты решения задач динамического программирования; рекуррентность природы задач данного типа; принципы оптимальности Беллмана.
Разработка алгоритма. Блок - схемы. Структура алгоритма.
Реализация на ЭВМ разработанного алгоритма на выбранном языке программирования.
Содержание
ВВЕДЕНИЕ ……………………………………………2
Динамическое программирование
Основные понятия …………………4
Принципы динамического программирования. Функциональные уравнения Беллмана …………………….5
Особенности задач динамического программирования……………….10
Задача распределения ресурсов……………………12
Общая постановка задачи ………………………….13
Блок схема программы
Структура алгоритма программы
Результат работы программы
Заключение
Список используемой литературы