48. Каноническая форма задачи линейного планирования.

Целевая ф-ция и ур-ния ограничений д. б. записаны в канонической форме. Каноническая форма для целевой ф-ции – это нахождение минимума. Если в задаче требуется найти максимум, то для ее приведения к канонической форме нужно целевую ф-цию умножить на (-1). –F(x)= -(2x1+5x2)=>min. Канонической формой для ур-ний ограничений явл-ся четкое равенство левых и правых частей.

49. Основные закономерности задачи линейного планирования.

1.Оптимальное решение, если оно существует, располагается на границе области допустимых решений.

2. Оптимальное решение может быть не единственным, если линия уровня располагается параллельно одной из сторон многоугольника, на которой достигается оптимальное решение.

3. Если область допустимых решений в направлении убывания целевой функции, то задача решения не имеет.

4. Оптимальное решение всегда достигается в одной из вершин многоугольника допустимых решений.

Все остальные решения наз-ся опорными точками.

50. Симплекс-метод решения задачи линейного планирования.

Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Симплекс-метод, называемый также методом последовательного улучшения плана, реализует перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции. Основная идея этого метода следующая. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если «да», то задача решена. Если «нет», то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается, т.е. к не худшему допустимому решению. Если некоторая угловая точка имеет несколько смежных, то вычислительная процедура метода обеспечивает переход к той из них, для которой улучшение целевой функции будет наибольшим. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции Е. При построении начального базиса в заданной задаче использовался метод искусственного базиса, поэтому найденное решение не является допустимым. В этом случае для решения задачи необходимо использовать двухэтапный симплекс-метод.

51.Симплекс-таблица задачи линейного планирования.

Построение симплекс-таблицы Выбираем начальное допустимое базисное решение. Базисным решением называется решение, полученное при нулевых значениях небазисных переменных, т.е. x_i=0, i=m+1,...,n. Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных неотрицательны, т.е. x_j = b_j >=0, j=1,2,...,m. В этом случае целевая функция примет следующий вид: S = c_b* x_b = c_1* b₁ + c_2* b₂+...+c_m* b_m. Заполняем первоначальную таблицу симплекс - метода:

 Таблица 2.3

cb	xb	c1	c2	...	cm	cm+1	...	cn	bi
	базис	x1	x2	...	xm	xm+1	...	xn
с1	x1	1	0	...	0	a1,m+1	...	an	b1
с2	x2	0	1	...	0	a2,m+1	...	a2n	b2
...	...	...	...	...	...	...	...	...	...
cm	xm	0	0	...	1	am,m+1	...	amn	bm
									S

Анализ симплекс-таблицы 1, Вычисляем вектор относительных оценок c при помощи правила скалярного произведения c_j = c_j - c_b* S_j , где

с_b - вектор оценок базисных переменных;

S_j - j-тый столбец в канонической системе, соответствующей рассматриваемому базису.

Дополняем первоначальную таблицу c - строкой.

2.      Если все оценки c_j  <=0 (c_j  >= 0), i=1,...,n, то текущее допускаемое решение - максимальное (минимальное). Решение найдено.

3.      Впротивном случае в базис необходимо ввести небазисную переменную x_r с наибольшим значением c_j вместо одной из базисных переменных (табл. 2.5).

4. При помощи правила минимального отношения min(b_i /a_ir) определяем переменную x_p, выводимую из базиса. Если коэффициент a_ir отрицателен, то b_i /a_ir =  бесконечность . В результате пересечение столбца, где находится вводимая небазисная переменная x_r и строки, где находится выводимая базисная переменная x_p определит положение ведущего элемента таблицы

5.      Применяем элементарные преобразования для получения нового допускаемого базового решения и новой таблицы. В результате ведущий элемент должен равняться 1, а остальные элементы столбца ведущего элемента принять нулевое значение.

6. Вычисляем новые относительные оценки с использованием правила скалярного преобразования и переходим к шагу 4

52 Понятия о методах нелинейного планирования.

Целев ф-ция зависит от параметров x_j и от условий ограничений W=f(x_j,α)→min (max)

Случаи: 1)цел ф-ция нелин, ограничения- линейны;2)ф-ция линейна, а ограничения нелинейны;3)цел. ф-ция и условия ограничений нелинейны.

Общая постановка задачи линейного планирования заключается в нахождении параметров обращающих целевую функцию к экстремуму, удовлетворяющих условиям ограничений, когда целевая функция или условия ограничений или вместе нелинейны.

Положения:

1)при решении задач Нелин планирования важно знать выпукла или невыпукла область допустимых решений;

2)является ли целев ф-ция выпуклой или вогнутой или не относится ни к тому ни к другому классу.

Функция y(t) выпукла, если отрезок, соединяющий любые две точки, принадлежит данной функции или лежат выше него.

Если отрезок, принадлежащий целевой функции, располагается ниже её, тогда целев ф-ция обладает свойством вогнутости.

Для задач , в кот множество допустимых значений вогнута при выпуклой функции цели любой локальный минимум целевой функции является глобальным. При вогнутой целев ф-ции на выпуклом множестве решений любой локальный экстремум является глобальным.

Если система ограничений нелинейна, а целев ф-ция нелинейна, то целев ф-ция достигает оптимума не на границе области допустимых решений, а если и достигает, то не обязательно в вершине; в задачах, имеющих локальный экстремумы могут не совпадать с глобальными, так как область допустимых решений не всегда выпукла.

53 Общая, постановка задачи нелинейного планирования.

Общая постановка задачи линейного планирования заключается в нахождении параметров обращающих целевую функцию к экстремуму, удовлетворяющих условиям ограничений, когда целевая функция или условия ограничений или вместе нелинейны.

Положения:

1)при решении задач Нелин планирования важно знать выпукла или невыпукла область допустимых решений;

2)является ли целев ф-ция выпуклой или вогнутой или не относится ни к тому ни к другому классу.

Множество решений является выпуклым, если оно любыми своими точками расположенными на прямой, лежащие в области допустим решений, полностью ему принадлежит.

Функция y(t) выпукла, если отрезок, соединяющий любые две точки, принадлежит данной функции или лежат выше него.

Если отрезок, принадлежащий целевой функции, располагается ниже её, тогда целев ф-ция обладает свойством вогнутости.

Для задач , в кот множество допустимых значений вогнута при выпуклой функции цели любой локальный минимум целевой функции является глобальным. При вогнутой целев ф-ции на выпуклом множестве решений любой локальный экстремум является глобальным.

Если система ограничений нелинейна, а целев ф-ция нелинейна, то целев ф-ция достигает оптимума не на границе области допустимых решений, а если и достигает, то не обязательно в вершине; в задачах, имеющих локальный экстремумы могут не совпадать с глобальными, так как область допустимых решений не всегда выпукла.

54 Особенности решения задачи нелинейного планирования.

Методы решения задач нелинейного планирования:

Численные методы нахождения экстремумов при решении задач нелинейного планирования состоят в построении некоторой последовательности, удовлетворяющей условию:

f(x⁰) >f(x¹)>f(x²)>…>f(xⁿ) такая последовательность называется релаксационной, а метод наз методом спуска.

В этих методах точки последовательности x^k вычисляется по формуле: x^(k+1)=x^k+α_k*P^k,

x^k- текущее приближение параметра к экстремума;

α_k- параметр, характеризующий длину шага в направлении спуска;

P^k- направление спуска на шаге k.

Как известно градиент ф-ции от x в некоторой точке направлен в сторону возрастания ф-ции. Вектор противоположного направления наз антиградиентом. Выбирая в качестве направлении спуска антиградиент ф-ции f(x) в точке x^k приходят к итерационному процессу. Для данного метода имеются особенности:

Ели выбранные начальные приближения неудачны, то решение может оказаться локальным.