Реферат: Курсовая работа по ЭММ
Иначе говоря, Х есть множество точек (х1 , х2 ,..., х n ) Î Rn , удовлетворяющих системе неравенств (1.2).
В этом случае задача оптимизации приобретает следующий вид. Даны функция n переменных f (х1 , х2 , ..., х n ) и система неравенств (1.1). Требуется найти max (min) f при условиях (1.1).
f (х1 , х2 , ..., х n ) ® max (min) при условиях (1.1).
Понятно, что следует найти не только само значение max (min) f , но и точку или точки, если их несколько, в которых это значение достигается. Такие точки называются оптимальными решениями . Множество всех оптимальных решений будем называть оптимальным множеством и обозначать Х* .
Задачи подобного рода получили название задачи математического программирования ( не следует путать математическое программирование с машинным). При этом функцию f называют целевой функцией, а неравенства gi ³ 0 ( i = 1,2,..., m ) - ограничениями . В большинстве случаев в число ограничений входят условия неотрицательности переменных:
х1 ³ 0, х2 ³ 0,..., х n ³ 0
или части переменных, но это, впрочем, не обязательно.
В зависимости от характера функции f , g 1 , ..., gm различают разные виды математического программирования. Наиболее простой и часто встречающийся случай, когда эти функции являются линейными, т.е. каждая из них имеет вид
а1 х1 +а2 х2 + ...+а n х n + b .
Дадим теперь общую формулировку задачи линейного программирования.
Пусть S - система линейных ограничений ( т.е. линейных уравнений или нестрогих линейных неравенств) с n переменными х1 , х2 ,..., х n , а f (х) - целевая функция вида
f (х) = с1 х1 + с2 х2 + ...+ с n xn + c .
Требуется решить задачу
f (х) ® max (min) при условиях S .
Обычно система S включает в себя условия неотрицательности всех переменных:
х1 ³ 0, х2 ³ 0,..., х n ³ 0 , (1.3)
что вытекает из реального смысла чисел х1 , х2 ,..., х n . Будем называть эти условия тривиальными ограничениями.
1.1 Каноническая задача.
В этом случае система S , помимо тривиальных ограничений (1.3), включает в себя только уравнения .
Определение:
Если ищется max значение функции цели, а все ограничения являются равенством, все переменные не отрицательны, то такая система - называется системой в каноническом виде, а задача - является задачей в канонической форме.
В этом случае модель задач можно записать в векторной форме:
f (х) = с1 х1 + с2 х2 + ...+ с n xn ® max
`А1 х1 + `А2 х2 + ... + `Аn хn = B
xj = 0 (j =1`,n)
`A1 = `A2 = `B =
Записать задачу в каноническом виде:
f = -х1 +2х2 -х3 +х4 ® min
xj =0 ( j =1 ` ; 4)
Вместо того, чтобы исследовать функцию f на min, будем исследовать на
f 1 = - f на max.
В ограничениях содержащих £ к левой части прибавим дополнительную не отрицательную переменную. В ограничениях содержащих ³ - в левой части вычтем не отрицательную дополнительную переменную. Условие не отрицательности в равенство не переводится.
f 1 = - f =х1 - 2х2 + х3 - х4 ® max
х j ³ 0 ( j = ` 1; 7)
Вводимые дополнительные переменные имеют экономический смысл. В ограничении исходной задачи, отражается расход и наличие ресурсов, то числовое значение дополнительной переменной, показывает количество не израсходованного ресурса определенного вида.
Замечание: Если переменная хк не подчинена условию не отрицательности, ее нужно заменить на разность двух не отрицательных величин
xk = uk + vk .
Определение: Совокупность не отрицательных чисел х1 , х2 ,..., х n , удовлетворяющих ограничениям задачи, называются допустимым решением или просто планом задачи.
План Х* = (х1 * , х2 * , ..., х n * ) при котором целевая функция достигает своего экстремального значения, называется оптимальной.
Не нулевые допустимые решения задачи, называются базисными решениями, если соответствуют им векторы ` А j образуют линейно не зависимую систему.
1.2 Симплекс - метод .
С самого начала укажем, что симплекс-метод в его непосредственной форме предназначен для решения канонической задачи линейного программирования.
Для работы по симплекс-методу требуется:
1. привести задачу к канонической форме;