- •1.Типовые классы оптимизационных задач. Содержание этапа постановки задачи. Общая формальная постановка задачи.
- •2. Критерий оптимальности базисного распределения поставок.
- •Типовые классы оптимизационных задач. Вычисление решения. Классификация методов решения оптимизационных задач.
- •Распределительный метод решения транспортной задачи
- •1. Типовые классы оптимизационных задач. Выбор типа модели. Проверка и корректировка модели.
- •Открытая модель транспортной задачи.
- •1. Типовые классы оптимизационных задач. Понятие показателя и критерия эффективности.
- •Однопараметрическая постановка и решение задачи оптимизации классическим способом
- •Классический метод вычисления условного экстремума
- •1. Многопараметрическая постановка и решение задачи оптимизации классическим способом
- •2.Существо и содержание метода множителей Лагранжа
- •1. Общая и основная задачи линейного программирования
- •1. Свойства основной задачи линейного программирования
- •2.Принцип оптимальности и уравнение Беллмана
- •1.Графический метод решения задачи линейного программирования.
- •2. Постановка задачи целочисленного линейного программирования
- •1. Существо и содержание симплекс-метода решения задач линейного программирования.
- •2.Метод отсечения. Метод Гомори
- •1.Способы получения первоначального допустимого базисного решения. Метод искусственного базиса
- •2.Понятие о методе ветвей и границ
- •1.Геометрическая интерпретация основной задачи линейного программирования
- •2.Постановка задачи параметрического программирования. Аналитический метод решения задачи параметрического программирования.
- •1. Существо метода симплекс-таблиц
- •2. Постановка задачи параметрического программирования. Графический метод решения задачи параметрического программирования
- •Математическая модель транспортной задачи.
- •2.Решение задач нелинейного программирования методом штрафных функций.
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
Например,
если у нас имеется сеть, как размеченыйй
граф.
Требуется найти маршрут, оптимальный по времени. Такую задачу для такой небольшой сети можно решить методом перебора. Для метода динамического программирования введено несколько предположений:
Состояние Sk системы в конце k-го шага зависит только от предшествующего состояния Sk-1 и управления на k-м шаге (Uk). И не зависит от предшествующих состояний и предшествующих управлений. Такое требование называется отсутствием последействия и оно записывается следующим образом:
Целевая функция является аддитивной от показателя эффективности каждого шага. Т.е. если на k-м шаге имеем значение целевой функции Zk=fk()
Тогда задача пошаговой оптимизации и задача метода динамического программирования формулируется следующим образом:
Определить, какое допустимое управление U, переводящее систему S из начального состояния S0 в конечное состояние Sk, при котором целевая функция принимает наибольшее или наименьшее значение. Метод Динамического Программирования обладает следующими особенностями:
Задача оптимизации интерпретируется, как n-шаговый процесс управления.
Целевая функция равна сумме целевых функций на каждом шаге
Выбор управления на k-м шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги. Т.е. в системе отсутствует обратная связь.
Состояние Sk после k-го шага управления зависит только от состояния Sk-1 на предыдущем шаге и управления Uk на данном шаге. (Принцип отсутствия последействия)
На каждом шаге управление зависит от конечного числа управляющих переменных, а состояние Sk от конечного числа параметров.
С помощью метода динамического программирования могут решаться значительное число задач, которые относятся к следующим группам:
-задача распределения средств
-задача об оптимальном распределении ресурсов
-задачи о замене оборудования
Билет 8= Билет 20
