ыфсы. Конспект лекций Санкт Петербург
 Скачать 1.77 Mb.
|
|
Графический метод линейного программирования Графический метод линейного программирования отображает ограничения в виде графиков и определяет область, которая удовлетворяет всем ограничениям. Эта область называется обла- стью возможных решений. Затем выстраивается целевая функция и определяется оптимальная точка в области возможных решений. Координаты точки могут быть определены непосред- ственно по графику. Если в задаче существует оптимальное решение, то по крайней мере одна из вершин допустимой области представляет оптимальное решение, которое можно найти пу- тем целенаправленного перебора каждого числа ее вершин. Порядок решения оптимизационной задачи: 1) поставить задачу оптимизации, завершающейся математической моделью оптимизации; 2) построить на графике ограничения; 3) определить область возможных решений; 4) построить на графике целевую функцию; 5) найти оптимальное решение. Графический метод решения удобен лишь для случая решения задачи оптимизации при двух переменных целевой функции и линейных ограничениях. Симплексный метод линейного программирования Симплексный метод линейного программирования применяется для решения оптимизационных задач, содержащих более двух переменных. Симплекс (от лат. simplex – простой) – в матема- тике простейший выпуклый многогранник данного числа измерений. Трехмерный симплекс (n = 3) – тетраэдр, двухмерный (n = 2) – треугольник, n-мерный симплекс имеет n + 1 вершин. Хотя симплексный метод и ориентирован на применение при оптимизации экономических, ре- сурсных и транспортных задач, он пригоден также для решения условных линейных техниче- ских задач, в частности задач технической диагностики. Большинство задач технической диагностики сводится к поиску минимума функции издержек F(x), связанных с эксплуатацией и ремонтом машин. В качестве переменной х могут быть пара- метры технического состояния (допустимые или предельные значения), погрешность и досто- верность измерения этого параметра, периодичность диагностирования Приведение задач линейного программирования к стандартной форме При решении задач линейного программирования симплекс-методом требуется, чтобы задача была представлена в стандартной форме, т.е. все неравенства должны быть представлены ра- венствами, а все отрицательные переменные преобразованы в неотрицательные. На практике задачи линейного программирования чаще не имеют стандартной формы. Часто ограничения имеют вид неравенств. В некоторых задачах не все переменные неотрицательные. Первый этап решения задачи линейного программирования состоит в приведении ее к стандартной форме. Основные определения можно сформулировать следующим образом: – допустимое решение представляет собой неотрицательный вектор х, для которого выполняются ограничения Ах = В; – допустимая область S состоит из всех допустимых решений; – оптимальным решением называется такой допустимый вектор x0, для которого целевая функ- ция сх0 больше любого другого допустимого решения, т.е. тогда, когда x0 S и cx 0 ≥ c x для вce x x 0 𝝐 S; Системный анализ и принятие решений Макаров Л.М. 67 – оптимальное значение задачи. При решении задач линейного программирования число уравнений меньше числа переменных (m n), т. е. задача имеет бесконечное множество решений. Классическим методом решения систем линейных уравнений является метод Гаусса - Жордана. Основная идея этого метода со- стоит в сведении системы m уравнений с n неизвестными к каноническому виду с помощью элементарных операций над строками: – умножением любого уравнения системы на положительное или отрицательное число; – прибавлением к любому уравнению другого уравнения системы, умноженного на положи- тельное или отрицательное число. В результате элементарных преобразований коэффициент при некоторой переменной в одном из уравнений системы сводят к единице, в других уравне- ниях - к нулю. Переменные x1, x2 ,..., xm, входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми – в остальные, называются базисными или зависимыми. Остальные n – m переменные (xm+1,..., xm) называются небазисными или независимыми пере- менными. При симплекс-методе анализируется лишь часть всех допустимых базисных решений по следу- ющему алгоритму: 1) выбор начального допустимого базисного решения; 2) переход от начального решения к другому допустимому базисному решению с лучшим зна- чением целевой функции; 3) продолжение поиска допустимых базисных решений, улучшающих значение целевой функ- ции. Если некоторое допустимое базисное решение нельзя улучшить, оно является оптималь- ным. Решение завершается. 4.5. Нелинейное программирование при решении задач оптимизации Нелинейное программирование применяется при решении задач, в которых нелинейны и (или) целевая функция, и (или) ограничения в виде равенств и неравенств и для которых методы ма- тематического анализа оказываются непригодными. Нелинейное программирование представ- ляет наиболее характерный метод оптимизации при проектировании машин и технологических процессов и служит для выбора наилучшего плана распределения ограниченных материальных, финансовых и трудовых ресурсов. Метод множителей Лагранжа Метод множителей Лагранжа применяется в тех случаях, когда целевая функция и ограничения представлены нелинейными функциями нескольких переменных. Одним из методов решения подобных задач является метод множителей Лагранжа, при котором задача с ограничениями преобразуется в элементарную задачу безусловной оптимизации, в которой используются неко- торые неизвестные параметры, называемые множителями Лагранжа. Развитием метода Лагранжа при нелинейном программировании является метод квадратиче- ского программирования. Задачи квадратического программирования характеризуются квадратной зависимостью целевой функции и линейной зависимостью ограничений: Для решения этих задач разработаны методы, основанные на теореме Куна - Таккера, которые представляют собой обобщение метода множителей Лагранжа для определения экстремума при наличии ограничений, представляющих не только равенства, но и неравенства. Метод последовательной частной оптимизации. Системный анализ и принятие решений Макаров Л.М. 68 В техническом проектировании очень часто встречаются задачи, обладающие свойством моно- тонности используемых зависимостей. Заметим, что монотонность является легко устанавлива- емым свойством функции. Например, имеется задача. масса стержня круглого сечения, работающего на растяжение, и до- пустимая нагрузка на стержень непрерывно возрастают при увеличении диаметра стержня, т.е. представляют собой монотонно возрастающие функции его диаметра. Приняв в качестве огра- ничения предельную нагрузку на стержень F, можно получить при известном допускаемом напряжении [σ] ограничения в виде неравенства Добавим теорию Лагранжа Теорию оптимальности выбора стратегии продаж – коммивояжера Оптимальности выбора сосудов по наполнению отмерю жидкости – Фибоначчи ФИНИШ |