 |
Последовательность решения задачи с параметром в целевой функции.
|
|
|
|
1. Записать исходное опорное решение задачи в полную симпликсную таблицу.
2. Взять t = α, α – начальное значение параметра t (или t = tнижн., т.е. нижняя граница отрезка); при условии, что α ≠ - ∞.
Находим Δj по формуле Δj = Δj’ + tΔj”
3. Проверка решения на оптимальность (при решении на max: все Δj ≥0).
Если решение не оптимальное, то решаем задачу симпликсным методом до получения оптимального решения.
Если решение оптимальное, то переходим к п. 4.
4. Определяем отрезок значений параметра t, для которых полученное решение сохраняется оптимальность.
Оптимальное решение будет оптимальным до тех пор, пока неотрицательны все оценки Δj.
Этот отрезок определяется исходя из решения системы линейных неравенств:
Δ’1 + tΔ”1 ≥ 0
Δ’2 + tΔ”2 ≥ 0
Δ’3 + tΔ”3 ≥ 0
Исходя из решения системы, определяем предел изменения параметра t.
tнижн. ≤ t ≤ tверх.
5. Выписываем из таблицы оптимальное решение:
Отрезок [tнижн.; tверх.]
- Если tверх. ≥ β, то решение закончено.
- Если <, то переходим к п. 6.
6. Для нахождения оптимального решения на следующем отрезке определяем разрешающий столбец:
Берем t = tверх., который является верхней границей предыдущего отрезка и подставляем в уравнение.
Находим столбец, по которому Δj = Δj’ + tΔj” = 0
Этот столбец является разрешающим.
При дальнейшем увеличении t (t > tверх.) оценка Δj станет отрицательной, решение – неоптимально.
7. Выполняем симпликсные преобразования однократного замещения с выбранным разрешающим столбцом и получаем новое оптимальное решение.
Переходим к п. 4.
Процесс решения продолжается, пока не закончится разбиение (рассмотрение) заданного интервала [α;β].
|
|
|
* Если параметр t задан на [-∞; +∞], то для начала исследования берем любую точку числовой оси и проводим исследование в обе стороны от первоначально полученного отрезка.
Описание динамического процесса управления. Примеры экономических задач, представленных в терминах динамического программирования.
Динамическое программирование – метод многоэтапной или многошаговой оптимизации, т.е. он предусматривает разбиение процесса принятия решения и управления на последовательные шаги или этапы.
Свойства:
1. Целевая функция должна обладать свойством аддитивности, т.е. м/б представлена в виде суммы слагаемых функций, зависящих от ограниченного числа переменных, или задачи сепарабельной целевой функции – представляет собой слагаемое, зависящее только от одной переменной.
Z = f1(x1) + f2(x2) +... + fn(xn)
Если в первоначальной постановке целевая функция не обладает данным свойством, то целевую функцию преобразовывают, если это возможно, или изменяют постановку задачи.
Прологарифмировать обе части:
lgZ = lg f1(x1) + lg f2(x2) +... + lg fn(xn)
2. В данной задаче должно отсутствовать последствие, т.е. решение, принятое на предыдущем этапе не должно оказывать параметрическое влияние на решения на последующих этапах.
Задача параметрического программирования м/б использована для решения следующих задач:
1. Распределение инвестиций, капитальных вложений м/у возможными направлениями использования.
2. Распределение ресурсов м/у предприятиями.
3. Выбор оптимальной стратегии замены оборудования.
4. Нахождение оптимальных маршрутов перемещения по заданной сети.
Схема процесса принятия решений:
ч/з x (x1, x2,..., xn) – обозначаются шаговые управления
S - система: S0 – начальная система, Sn – конечное состояние системы.
Под управлением процессом в целом понимается последовательность шаговых управлений.
Уравнение состояния системы:
|
|
|
Sk = φk (Sk-1; xk).
Sk-1 – предшествующее состояние системы
xk – шаговое управление на k-шаге
φk – некоторая функция.
Целевая функция:
fk – некоторая функция, определяющая критерий эффективности k-шага.
Z – «выигрыш».
Постановка задачи: определить такое допустимое управление x, переводящее систему S из состояния S0 в состояние Sn, при котором целевая функция Z принимает наибольшее/ наименьшее значение.
Особенности многошаговых задач, решаемых методом динамического программирования. Принцип оптимальности Р. Беллмана.
Схема процесса принятия решений:
ч/з x (x1, x2,..., xn) – обозначаются шаговые управления
S - система: S0 – начальная система, Sn – конечное состояние системы.
Под управлением процессом в целом понимается последовательность шаговых управлений.
Уравнение состояния системы:
Sk = φk (Sk-1; xk).
Sk-1 – предшествующее состояние системы
xk – шаговое управление на k-шаге
φk – некоторая функция.
Целевая функция:
fk – некоторая функция, определяющая критерий эффективности k-шага.
Z – «выигрыш».
Постановка задачи: определить такое допустимое управление x, переводящее систему S из состояния S0 в состояние Sn, при котором целевая функция Z принимает наибольшее/ наименьшее значение.
Принцип Беллмана - вычислительная схема:
Какого бы ни было состояние системы, в результате к.-либо числа шагов, на ближайшем шаге управление надо выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге.
2 этапа:
1. Этап условной оптимизации (предварительный):
2. Этап безусловной оптимизации:
В основе решения задач динамического программирования лежит принцип оптимальности Беллмана: на каждом этапе принимается такое решение, которое обеспечивает оптимальность с данного этапа до конца процесса, то есть на каждом этапе необходимо принимать решение, просматривая его последствия до самого конца процесса. Так как последовательность решений следует просматривать до самого конца процесса, то варианты анализируют с конца процесса.
Функциональные уравнения Беллмана – это математическая формулировка принципа оптимальности Беллмана. Оптимальное управление обладает следующим свойством: каковы бы ни были начальное состояние S 0 и решение в начальный момент времени, последующие решения должны составлять оптимальное управление относительно состояния, полученного в результате предыдущего решения.
|
|
|
35. Схема решения задачи о распределении средств методом динамического программирования.
Оптимальное распределение ресурсов
Пусть имеется некоторое количество ресурсов х, которое необходимо распределить между п различными предприятиями, объектами, работами и т.д. так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения.
Сумма прибыли от k-ого предприятия = общая прибыль. Прибыль не зависит от вложения в другие предприятия.
1) Число шагов = число предприятий.
2) Все средства должны быть распределены.
3) На каждом шаге системы (Sk) определяется количество средств, которые остаются после k-ого шага.
4) Выигрышем на k-ом шаге является прибыль, которую приносит k-ое предприятие при Xk.
5) Определяем функциональное уравнение на последнем шаге (сколько средств осталось)
6) Составляем уравнение Беллмана:
|
|
|
