|
46.Общая постановка задачи линейного планирования. Требуется определить значения n переменных (x1,x2,x3 …), которые минимизируют целевую функцию и при этом удовлетворяют условиям ограничений
Условия ограничений задач в каноническом форме представляют собой чёткое равенство левой и правой частей |
47. Геометрическая интерпретация задачи линейного плакирования. Найти параметры х1 х2… максимизирующих целевую функцию. При этом должны удовлетворятся условиям ограничения. Для этого целевую функцию умножим на (-1) , а в условиях ограничений от неравенств перейдем к равенству, введя дополнительную переменную. Изобразим полученные прямы на оси координат. Оптимальное решение на-ся в одной из вершин области допустимых решений. Если целевая функ-я зависит от n переменных, то и условие ограничения будут представлять собой объемную фигуру, а оптимальное решение будет лежать на плоскости n переменных в одной из вершин, объемной области допустимых решений. Пусть имеются вектора
A1*x1+A2*x2+…+An*xn=B |
48. Каноническая форма задачи линейного планирования. Целевая ф-ция и ур-ния ограничений д. б. записаны в канонической форме. Каноническая форма для целевой ф-ции – это нахождение минимума. Если в задаче требуется найти максимум, то для ее приведения к канонической форме нужно целевую ф-цию умножить на (-1). –F(x)= -(2x1+5x2)=>min. Канонической формой для ур-ний ограничений явл-ся четкое равенство левых и правых частей. |
|
49. Основные закономерности задачи линейного планирования. 1.Оптимальное решение, если оно существует, располагается на границе области допустимых решений. 2. Оптимальное решение может быть не единственным, если линия уровня располагается параллельно одной из сторон многоугольника, на которой достигается оптимальное решение. 3. Если область допустимых решений в направлении убывания целевой функции, то задача решения не имеет. 4. Оптимальное решение всегда достигается в одной из вершин многоугольника допустимых решений. Все остальные решения наз-ся опорными точками. |
50. Симплекс-метод решения задачи линейного планирования. Порядок расчёта: 1)задачи линейного планирования приводят к канонической форме; 2)приравниваем 0 свободные переменные и находим одно из опорных решений. Если среди параметров имеются отрицательные значения, это будет означать, что тмы находимся вне области допустимых значений. Является ли полученное решение оптимальным при отсутствии отрицательных значений параметров определяется по коэффициентам при свободных переменных функции цели. Если значения этих коэффициентов отрицательны, то полученное решение оптимально. Иначе, 3)наибольший из положительных коэффициентов при свободных переменных функции цели будет определять ту свободную переменную, которая будет изменяться от 0 до значений, обращающих в 0 базисные переменные. Находят отношения свободного члена базисной переменной. Минимальное из отношений определяет ту базисную переменную, которая поменяется местами со свободной 4)производится пересчёт новых базисных переменных через свободные переменные с подстановкой в целевую функцию 5)приравниваем к 0 свободную переменную, находим очередное опорное решение; 6)см. пункт 2. |
51. Симплекс-таблица задачи линейного планирования. Функцию цели и условия привели к канонической форме. Для условий ограничений вводим новые переменные, которые обратят неравенства в равенства. Принимаем вновь введённые переменные в качестве базисных, которые выразим через свободные переменные. Составим коэффициенты в таблицу. Если коэффициенты при свободных переменных в функции дели отрицательны, то полученное решение оптимально, и значения параметров и функции цели определяется столбцом «свободные члены». В противном случае столбец «свободные члены» определяет первое опорное (базисное) решение при равенстве нулю свободных переменных. Наибольший коэффициент в функции цели определяет разрешающий столбец. Находим наименьшее отношение bi/aij, которое определяет разрешающую строку. Элемент, стоящий на пересечении разрешающего столбца и разрешающей строки, наз. генеральным. Разрешающая строка показывает, какая базисная переменная поменяется со свободной переменной. Для пересчёта коэффициентов базисных переменных и функции цели через новые свободные переменные выполним следующее. 1)найдём λ=1/aij; aij- генеральный элемент. 2)все коэффициенты разрешающей строки умножим на λ (кроме генерального), а коэффициенты разрешающего столбца- на (- λ) и запишем в нижней части клеток. |
|
52. Понятия о методах нелинейного планирования. Целев ф-ция зависит от параметров xj и от условий ограничений W=f(xj,α)→min (max)
Случаи: 1)цел ф-ция нелин, ограничения- линейны;2)ф-ция линейна, а ограничения нелинейны;3)цел. ф-ция и условия ограничений нелинейны. Количество ограничений меньше искомых параметров. Сложность решения задач кроме нелинейности функции заключается и в том, что некоторые переменные могут меняться скачкообразно или принимать ряд фиксированных значений. Кроме того в задачах нелинейного планирования может быть несколько экстремумов и необходимо решить является ли оно локальным. Общая постановка задачи линейного планирования заключается в нахождении параметров обращающих целевую функцию к экстремуму, удовлетворяющих условиям ограничений, когда целевая функция или условия ограничений или вместе нелинейны. Положения: 1)при решении задач Нелин планирования важно знать выпукла или невыпукла область допустимых решений; 2)является ли целев ф-ция выпуклой или вогнутой или не относится ни к тому ни к другому классу. |
53. Общая, постановка задачи нелинейного планирования. Общая постановка задачи линейного планирования заключается в нахождении параметров обращающих целевую функцию к экстремуму, удовлетворяющих условиям ограничений, когда целевая функция или условия ограничений или вместе нелинейны. Положения: 1)при решении задач Нелин планирования важно знать выпукла или невыпукла область допустимых решений; 2)является ли целев ф-ция выпуклой или вогнутой или не относится ни к тому ни к другому классу. Множество решений является выпуклым, если оно любыми своими точками расположенными на прямой, лежащие в области допустим решений, полностью ему принадлежит. Функция y(t) выпукла, если отрезок, соединяющий любые две точки, принадлежит данной функции или лежат выше него. Если отрезок, принадлежащий целевой функции, располагается ниже её, тогда целев ф-ция обладает свойством вогнутости. Для задач , в кот множество допустимых значений вогнута при выпуклой функции цели любой локальный минимум целевой функции является глобальным. При вогнутой целев ф-ции на выпуклом множестве решений любой локальный экстремум является глобальным. |
54. Особенности решения задачи нелинейного планирования. Методы решения задач нелинейного планирования: Численные методы нахождения экстремумов при решении задач нелинейного планирования состоят в построении некоторой последовательности, удовлетворяющей условию: f(x0) >f(x1)>f(x2)>…>f(xn) такая последовательность называется релаксационной, а метод наз методом спуска. В этих методах точки последовательности xk вычисляется по формуле: x(k+1)=xk+αk*Pk, xk- текущее приближение параметра к экстремума; αk- параметр, характеризующий длину шага в направлении спуска; Pk- направление спуска на шаге k. Как известно градиент ф-ции от x в некоторой точке направлен в сторону возрастания ф-ции. Вектор противоположного направления наз антиградиентом. Выбирая в качестве направлении спуска антиградиент ф-ции f(x) в точке xk приходят к итерационному процессу. Для данного метода имеются особенности: Ели выбранные начальные приближения неудачны, то решение может оказаться локальным. Rebuild by Dimon and Anorexius |
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
Для решения
таой задачи те условия ограничений, в которых неравенство обозначено ≥,
должны умножить на (-1). Если все условия ограничений заданы системой
неравенств, то говорят, что задача линейного планирования задана в канонической
форме (нахождение min-ма). Каноническая форма представляет собой
нахождение минимального значения функции 
