Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
смирнов шпоры.docx
Скачиваний:
2
Добавлен:
01.05.2025
Размер:
500 Кб
Скачать
☆

1. Общая и основная задачи линейного программирования

Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

где аij , bi , cj - заданные постоянные величины, и k ≤ m. Следовательно, общая ЗЛП может иметь функцию с любым видом находимого экстремума, а накладываемые ограничения могут иметь как неравенства, так и равенства. Основной (или канонической) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции цели (6) при выполнении условий ограничений (8) и (9), где k=0 , l=n, т.е. все ограничения только равенства при условии неотрицательности неизвестных.

2.Общая постановка задачи динамического программирования . Метод Динамического программирования. (Метод Беллмана)

Существо метода заключается в поэтапном решении задачи. При этом выделяют два этапа решения задачи. На первом этапе осуществляется условная оптимизация. На втором этапе – безусловная оптимизация. Каждый из этапов выполняется по шагам. Есть 2 пути решения задачи. Начиная с последнего объекта и двигаясь к первому и от первого объекта двигаясь к первому. Но абсолютное большинство задач решается, начиная с последнего объекта. Именно на основе метода динамического программирования построены все основные алгоритмы, а с помощью них протоколы маршрутизации в распределенных сетях. Метод предполагает одну N-мерную задачу, в которой некий управляемый объект из состояния S0 s в состояние Sk может перевестись с помощью управления, являющимся N-мерным вектором. В задачу, состоящую из n одномерных задач, в которых тот же самый объект, из того же самого исходного состояния и в тоже самое конечное состояние Sk приводится по шагам. При этом к нему должно быть приложено скалярное управление Uk.

Беллман сформулировал и доказал принцип оптимальности, который в настоящее время трактуется как принцип оптимальности Беллмана: каково бы ни было состояние S системы, в результате какого-либо числа шагов, на ближайшем шаге необходимо выбирать управление таким образом, чтобы оно в совокупности с оптимальным управлением на всех шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая и данный.Таким образом метод динамического программирования является иторационным пошаговым методом, реализующим уравнение оптимальности (уравнение Беллмана)

По существу этот метод говорит о том, что начиная с последнего элемента (т.е. с результата) необходимо на каждом шаге выбирать такое воздействие, которое является оптимальным на данном шаге. И тогда оптимальным будет и весь процесс управления от S0 до Sk

Например, если у нас имеется сеть, как размеченыйй граф.

Требуется найти маршрут, оптимальный по времени. Такую задачу для такой небольшой сети можно решить методом перебора. Для метода динамического программирования введено несколько предположений:

    1. Состояние Sk системы в конце k-го шага зависит только от предшествующего состояния Sk-1 и управления на k-м шаге (Uk). И не зависит от предшествующих состояний и предшествующих управлений. Такое требование называется отсутствием последействия и оно записывается следующим образом:

    1. Целевая функция является аддитивной от показателя эффективности каждого шага. Т.е. если на k-м шаге имеем значение целевой функции Zk=fk()

Тогда задача пошаговой оптимизации и задача метода динамического программирования формулируется следующим образом:

Определить, какое допустимое управление U, переводящее систему S из начального состояния S0 в конечное состояние Sk, при котором целевая функция принимает наибольшее или наименьшее значение. Метод Динамического Программирования обладает следующими особенностями:

  1. Задача оптимизации интерпретируется, как n-шаговый процесс управления.

  2. Целевая функция равна сумме целевых функций на каждом шаге

  3. Выбор управления на k-м шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги. Т.е. в системе отсутствует обратная связь.

  4. Состояние Sk после k-го шага управления зависит только от состояния Sk-1 на предыдущем шаге и управления Uk на данном шаге. (Принцип отсутствия последействия)

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

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

-задача распределения средств

-задача об оптимальном распределении ресурсов

-задачи о замене оборудования

Билет 8= Билет 20