Ответы_на_вопросы_по_материалам_курса_МО

3. Проверяем полученное решение на оптимальность. Для этого рассчитываем потенциалы поставщиков uiи потребителей vjс учетом заполненных клеток и условия: ui+vj=cij

Для небазисных переменных рассчитываем оценки оптимальности, используя выражение

Сравниваем полученные оценки с нулем. Если они все меньше или равны 0 (для задачи на минимум), то получено оптимальное решение. Если хотя бы одна оценка больше нуля, то переходим к шагу 4.

4. Среди оценок находим ту, у которой значение больше. Переменная, соответствующая данной оценке, переходит в базисные. Строим цикл пересчета для определения значения переменной, входящей в базис, переменной, покидающей базис и значений скорректированных величин поставок для остальных базисных переменных цикла. Переходим к шагу 3.

Транспортная задача по критерию времени.

В такой транспортной задаче решающую роль играет не стоимость перевозок, а время, которое затрачивается на доставку груза. Оптимальным планом считается план, который минимизирует время перевозок.

Подобные задачи возникают при перевозках скоропортящегося продукта, в военном деле, где зачастую стоимость перевозок играет второстепенное значение.

Как и в прочих транспортных задачах, закрытой задача считается при

А открытой – при невыполнении этого равенства. Как и в обычных ТЗ есть поставщики и потребители

Известны tij, i = 1, 2, …, m, j = 1, 2, …, n – время, за которое груз доставляется от каждого i – го поставщика каждому j – му потребителю.

Требуется составить такой план перевозок, который бы минимизировал время развоза груза всем потребителям.

Также составляется матрица перевозок, в которой теперь содержатся не тарифы перевозок, а время перевозок.

Математическая модель задачи выглядит:

T(X)=max{tij}min, при xij>0, где xij–объем перевозимого груза от i-го поставщика j-му потребителю, T(X) –время, за которое план перевозок будет полностью выполнен.

Алгоритм решения Транспортная задача по критерию времени методом приоритетных связей решается так

же, как и классическая. Из полученного оптимального решения извлекаются его временные составляющие, формируется целевая функция T(X) и оптимальный план решения задачи по критерию времени.

31

32

Математическая формулировка динамических задач.

Динамическое программирование – математические методы нахождения оптимальных решений в задачах с многошаговой структурой, т.е. не в виде одного значения, а в виде функции изменяющейся во времени или пространств с целью минимизации затрат на перевод системы из одного состояния в другое.

Математическая модель динамической задачи – это дифференциальное уравнение

0

, где T – время протекания процесса управления, Qi[x(t), U(t)] –мгновенные потери в момент времени t.

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

Общая идея динамического программирования: если сложно оптимизировать сложную задачу, то следует разложить еѐ на ряд более простых. На каждом шаге оптимизируется задача меньшего размера.

Примером задачи динамического программирования может служить задача нахождения минимального пути в графе.

Принцип оптимальности: оптимальное управление на каждом шаге определяется состоянием системы на начало этого шага и целью управления.

Принцип погружения: природа задач, допускающих использование метода ДП, не меняется при изменении количества шагов N, т.е. форма такой задачи инвариантна относительно N. В этом смысле каждый конкретный процесс с заданным числом шагов оказывается как бы погруженным в семейство подобных ему.

Математическая формулировка принципа оптимальности.

Принцип оптимальности Беллмана:

− основное функциональное уравнение ДП

Вычислительные аспекты динамического программирования.

33