- •Одномерная оптимизация. Необходимые и достаточные условия оптимальности. Принцип сужения интервала неопределенности для унимодальных функций.
- •Одномерная оптимизация. Постановка задачи. Метод половинного деления. Оценка погрешности.
- •Одномерная оптимизация. Постановка задачи. Метод "золотого" сечения, Фибоначчи.
- •Одномерная оптимизация. Постановка задачи. Метод Ньютона-Рафсона.
- •6. Одномерная оптимизация. Постановка задачи. Метод квадратической аппроксимации.
- •7. Многомерная оптимизация. Основные определения и понятия функции нескольких переменных (фнп). Необходимые и достаточные условия экстремума.
- •8. Многомерная оптимизация. Основные определения и понятия функции нескольких переменных (фнп). Обусловленность задачи поиска минимума фнп.
- •9. Постановка задачи безусловной оптимизации фнп. Методы нулевого порядка. Метод покоординатного спуска.
- •1.2& Метод покоординатного спуска.
- •10. Постановка задачи безусловной оптимизации фнп. Метод многогранника. Алгоритм метода.
- •Постановка задачи безусловной оптимизации фнп. Метод Монтер-Карло. Алгоритм метода. Основные параметры метода.
- •12. Постановка задачи безусловной оптимизации фнп. Градиентные методы и метод наискорейшего спуска.
- •13. Постановка задачи безусловной оптимизации фнп. Градиентный метод с добрым шагом. Алгоритм выбора длины шага.
- •14. Постановка задачи безусловной оптимизации фнп. Овражный метод.
- •15. Постановка задачи безусловной оптимизации фнп. Методы второго порядка. Метод Ньютона.
- •16. Пз безусловной оптимизации фнп. Методы второго порядка. Метод Ньютона с дробным шагом. Алгоритм выбора длины шага.
- •17. Общая постановка задачи условной оптимизации. Постановки задач линейного и целочисленного программирования. Необходимые и достаточные условия оптимальности злп.
- •18. Общая и стандартная постановки злп. Переход от общей постановки задачи к стандартной.
- •19. Графическое решение злп. Основные понятия и идея решения задачи.
- •20. Симплекс-метод решения злп. Построение начальной симплекс-таблицы.
- •21.Оценка решения, представленного данной таблицей, на оптимальность и, если оптимум не достигается, поиск переменной, вводимой в базис.
- •22.Определение выводимой из базиса переменной.
- •23. Выбор начального решения
- •24. Анализ ресурсов.
- •25. Анализ цен
- •26. Целочисленное деление.
- •27. Постановка транспортной задачи. Балансировка задачи.
- •28. Сведение транспортной задачи к задаче линейного программирования.
- •29. Постановка транспортной задачи. Поиск допустимого нач.Решения. Метод с-з угла. Метод min стоимости.
- •35.Алгоритм Форда-Фалкерсона
21.Оценка решения, представленного данной таблицей, на оптимальность и, если оптимум не достигается, поиск переменной, вводимой в базис.
Указанные операции осуществляются на основе анализа всех элементов индексной строки, соответствующих небазисным переменным. Если все эти элементы неотрицательны в задачах на максимум (неположительны в задачах на минимум), то данное решение оптимально и, соответственно, вычислительный процесс прекращается. В противном случае в задачах на максимум ищется наибольший по абсолютной величине отрицательный элемент (в задачах на минимум наибольший положительный элемент). Переменная, вводимая в базис, соответствует именно этому элементу. Соответствующий столбец называется ключевым (главным, разрешающим) столбцом.
Для понимания смысла действий на первом шаге следует учесть, что каждый элемент индексной строки, взятый с обратным знаком, показывает, насколько изменяется значение целевой функции при изменении соответствующей переменной на единицу. Значит, если в задачах на максимум все рассматриваемые элементы индексной строки неотрицательны, то при введении любой небазисной переменной в базис (то есть при придании ей какого-либо положительного значения) значение целевой функции либо не возрастет (если соответствующий элемент равен нулю), либо даже уменьшится (если элемент положителен). Это и означает, что мы достигли оптимума больше нет возможности увеличить значение целевой функции. Если же среди элементов индексной строки есть отрицательные (случай максимизации целевой функции), то это означает, что придавая соответствующей небазисной переменной положительное значение (вводя ее в базис), мы можем повысить значение целевой функции, при этом, чем больше элемент по абсолютной величине, тем быстрее будет расти целевая функция с ростом переменной. Именно поэтому при решении задачи на максимум каждая очередная итерация начинается с выбора наибольшего по модулю отрицательного значения элемента индексной строки.
22.Определение выводимой из базиса переменной.
Общее правило выбора выводимой из базиса переменной формулируется следующим образом: из базиса должна выводиться та переменная текущего базиса, которая раньше других обращается в нуль при возрастании вводимой в базис переменной. Аналитическая процедура реализации этого правила такова:
поочередно разделить значения элементов столбца
на соответствующие положительные элементы ключевого столбца:
Ту строку, в которой результат деления оказался минимальным, называют ключевой (главной, разрешающей) строкой, а базисная переменная, расположенная в этой строке, подлежит выводу из базиса. Элемент, лежащий на пересечении ключевого столбца и ключевой строки называют ключевым (главным, разрешающим) элементом.
23. Выбор начального решения
Для задачи, представленной в стандартной форме, количество переменных обычно больше, чем количество ограничений. Поэтому для нахождения начального решения задачи требуется выразить m переменных (т.е. количество переменных, равное количеству уравнений) через остальные n-m переменных, принять эти n-m переменных равными нулю и, таким образом, найти значения m переменных. Переменные, значения которых принимаются равными нулю, называются небазисными, а остальные m переменных - базисными. Значения базисных переменных неотрицательны (некоторые из них могут оказаться равными нулю). Количество базисных переменных всегда равно количеству ограничений. Найденное таким образом решение называется начальным допустимым базисным решением. Оно соответствует всем ограничениям.
Начальное решение проще всего найти в случае, когда в каждом ограничении есть переменная, которая входит в него с коэффициентом 1 и при этом отсутствует в других ограничениях. Такие переменные принимаются в качестве базисных (они образуют начальный базис задачи). Остальные (небазисные) переменные принимаются равными нулю. Таким образом, базисные переменные принимают значения, равные правым частям ограничений.