Общая постановка задач ЛП

ДП - метод оптимизации, в котором процесс принятия решения может быть разбит на шаги.

Рассмотрим управляемый процесс распределения ресурсов (средств) между предприятиями, замены оборудования, пополнение запасов и т.д. В результате управления система S переводится из начального состояния S₀ в состояние . Пусть управление можно разбить на n шагов, т.е. принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность n пошаговых управлений.

Пусть = (Х_1, Х₂,…, Х_к,…Х_п) - уравнение переводящее систему S из S ₀ в . Обозначим через Х_к уравнение на к шаге. Переменные Х_к удовлетворяют некоторым ограничениям и в этом смысле называется допустимым. S_к - состояние системы после к шага управления. Получаем последовательность состояний.

Показатель эффективности рассматриваемой управляемой операции - целевая функция - зависит от начального состояния и управления: Z = F(S₀, Х)

1. Состояние S_k системы в конце к шага зависит только от предшествующего состояния S_k-1 и управления на к шаге Х_к. Это называется «отсутствием последствия».

S_k = φ_k(S_k-1, Х_k), k = 1,n - уравнения состояний.

2. Целевая функция является аддитивной от показателя эффективности каждого шага. Обозначим показатель эффективности к шага через Z_k = f_k(S_k-1, Х_k), тогда

.

Задача пошаговой оптимизации формулируется так:

определить такое дополнительное решение Х, переводящее систему S из S₀ в , при котором функция принимает max(min) значения.