Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Метод деформируемого многогранника.
Краткие выводы к РАЗДЕЛУ 2. 1. Изучены ЧМ одномерной минимизации (частный случай метода 0-го порядка): МД, МЗС, МФ. 2. детально исследованы основные ЧМ многомерной безусловной оптимизации 0-го, 1-го и 2-го порядков. 3. при исследовании экстремальных свойств неизвестной функции необходимо применить комплексный подход. Вначале, используя методы 0-го порядка целесообразно найти в грубом приближении локальные и глобальные экстремумы. Затем, учитывая характерные особенности минимизируемой функции следует точно найти необходимые локальные экстремумы, используя более эффективные методы оптимизации 1-го и 2-го порядков.
ЛК №4 24.09.2003
РАЗДЕЛ 3 Линейное программирование (ЛП). В этом разделе будут изучены экстремальные свойства линейных функций переменных вида: (1) и универсальный аналитико-численный метод решения задачи ЛП – симплексный метод. Как известно, задачи ЛП – такие задачи, в которых целевая функция имеет вид (1), а область допустимых решений и определятся системой линейных неравенств и (или) уравнений. Отметим, что значительная часть практически важных задач формируется как задачи ЛП. К их числу относятся: 1) задача о рациональном размещении ресурсов; 2) задача об оптимальном выборе технологий; 3) задача о смесях; 4) задача о раскрое материалов; 5) транспортная задача. За разработку симплексного метода решения задач ЛП группе математиков-экономистов в 70-х годах 20 в. Была присвоена нобелевская премия.
Формы записи задач ЛП. А. Общая задача ЛП (ОЗЛП). (1)
- целевая функция – линейная функция переменных; - численные вещественные коэффициенты.
Требуется найти - вектор, представляющий целевой функции экстремальные значения. В ЛП называется оптимальным планом.
Б. Симметричная задача ЛП. Существуют 2 вида задач: 1) (1)
2) (4)
В. Классическая (основная) задача ЛП. (4)
Переход от симметричной формы записи ЛП к канонической. Осуществляем путем введения неотрицательных дополнительных (балансовых) переменных: , . (1) В симметрической задаче 1-го вида (задачи на max) в систему неравенств, определяющих дополнительная переменная вводится следующим образом: . После этого исходная симметричная задача преобразуется в каноническую задачу ЛП. Аналогично для симметричной задачи 2-го вида вводятся дополнительные балансные переменные:
(курс АтГ (часть 1))
АтГ (часть 1)
. Целевую функцию дополнительные (балансовые) переменные вводят с коэффициентом равным нулю (т.е. не учитываются). Учитывая важность канонической формы записи задачи ЛП, представим ее, используя матрицы и векторы: , где - матрица коэффициента ; ; ; .
Переход от канонической формы записи задачи ЛП к симметричной. Представление целевой функции как функции только от свободных переменных. (1)
Предположим, что в системе линейных уравнений (2) имеется линейно-независимых уравнений, т.е. ранг системы равен . Поскольку , то, как известно, такая система будет иметь беспечное множество решений; именно при таком условии ( ), оптимизационная задача имеет смысл (если бы , то система имела бы одно единственное решение при условии , - определитель системы), тогда нет возможности выбора оптимальной системы. Для того, чтобы преобразовать (2) в систему линейных неравенств, что свойственно симметрической задаче ЛП, необходимо используя метод Гаусса решения систем линейных уравнений преобразовать ее к виду:
Прямой ход метода Гаусса.
ЛК №5 01.10.2003
(5) Коэффициенты и определенным образом зависит от и . Поскольку , то из (5) система линейных (6) неравенств вида: , (7) Из (7) ОДР представимо системой линейных неравенств, что свойственно задаче ЛП в симметричной форме. Для того, чтобы завершить переход от канонической записи к записи задач ЛП к ее симметричной записи, необходимо представить целевую функцию только как функцию координат . Это возможно сделать используя (5): , (8) Отметим, что переменные , как известно, называются свободными (независимыми), а переменные называются базисными (зависимыми). Подобно (7), которое содержит только свободные независимые переменные, выразим целевую функцию только через свободные переменные. (9) ; ; ; , где , . (10) – выражение, представляющее целевую функцию только как функцию свободных переменных.
См ПЗ весеннего семестра 2002/2003 учебного года.
Совершен переход от канонической формы задачи ЛП к симметричной. (11)
Заметим, что (10) для целевой функции эффективно используется при исследовании симплексного метода решения задач ЛП.
|
Последнее изменение этой страницы: 2017-04-12; Просмотров: 451; Нарушение авторского права страницы