КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Общая постановка задачи линейного программирования. Постановки задачи линейного программирования
Постановки задачи линейного программирования Линейное программирование
Для изучения данного раздела дисциплины необходимо знание темы 2. Изучив тему, студент должен: - знать формы записи ЗЛП, основные определения и свойства ЗЛП; - уметь использовать графический, симплекс-метод, Р-метод, двухэтапный симплекс-метод решения ЗЛП; - приобрести навыки решения ЗЛП с помощью MS Excel; - уметь определять интервалы изменения коэффициентов целевой функции, при которых структура оптимального плана остается неизменной; - уметь определять интервалы изменения значений констант в правой части ограничений, при которых структура оптимального плана остается неизменной. Цель изучения –изучение темы «Линейное программирование» должно дать достаточно полное представление о возможностях применения методов линейного программирования и интерпретации получаемых с их помощью результатов.
Линейное программирование – область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений, т.е. линейных равенств или неравенств, связывающих эти переменные. К задачам линейного программирования приводится широкий круг вопросов планирования экономических и технико-экономических процессов, где ставится задача поиска наилучшего (оптимального) решения; само возникновение и развитие линейного программирования непосредственно связано с экономической проблематикой. Как показывают приведенные в теме 1 примеры, левая и правая части ограничений линейной модели могут быть связаны знаками «£», «=», «³». Также и переменные, фигурирующие в линейных моделей, могут быть неотрицательными, отрицательными или не иметь ограничений в знаке, поэтому задачи линейного программирования имеют несколько вариантов постановки.
Общая задача линейного программирования (ОЗЛП) может быть сформулирована следующим образом: найти значения переменных Х1, Х2,…,Хn, максимизирующие линейную форму (x1,x2,…,xn) = c1x1+…+cnxn (3.1) при условиях
i = 1,…, m1 (m1 £ m), (3.2)
i = m1 + 1,…, m, xj ³ 0, j = 1,…, p (p £ n). (3.3)
Соотношения (3.2) и (3.3) будем называть соответственно функциональными и прямыми ограничениями задачи линейного программирования (ЗЛП). Значения переменных Хj (j = 1, 2,…, n) можно рассматривать как компоненты некоторого вектора = (Х1, Х2,…, Хn) пространства Еn. Определение. Планом, или допустимым решением, задачи линейного программирования будем называть вектор пространства Еn, компоненты которого удовлетворяют функциональным и прямым ограничениям задачи. Множество всех планов задачи линейного программирования (3.1) – (3.3) будем обозначать Р. Теорема 3.1. Множество планов Р задачи линейного программирования (ЗЛП) есть замкнутое выпуклое множество. Множество Р может быть как ограниченным, так и неограниченным, кроме того оно может оказаться пустым. Напомним, что множество точек Р пространства En есть выпуклое множество, если вместе с любыми двумя его точками и ему принадлежит и любая выпуклая линейная комбинация этих точек, то есть если , , то и любая точка , 0 ≤ λ ≤ 1 также принадлежит множеству Р. Множество точек = (Х1, Х2,…, Хn) пространства En, компоненты которых удовлетворяют условию C1X1 + C2X2 +…+ CnXn = b, называется гиперплоскостью пространства En. Множество точек = (Х1, Х2,…, Хn) пространства En, компоненты которых удовлетворяют условию C1X1 + C2X2 +…+ CnXn ≤ b (≥ b), называется полупространством пространства En.
Очевидно, что гиперплоскость и полупространство являются выпуклыми множествами пространства En. Напомним, что точка выпуклого множества К является крайней, если в К не существует таких точек и , ≠ , что , при некотором . Геометрически это означает, что эта крайняя точка не может лежать внутри отрезка, соединяющего две точки выпуклого множества. Она лишь может быть одной из концевых точек этого отрезка. Определение. План = (Х1*,…Хn*) будем называть решением задачи линейного программирования, или ее оптимальным планом, если . Определение. Будем говорить, что задача линейного программирования разрешима, если она имеет хотя бы один оптимальный план.
Дата добавления: 2014-12-29; Просмотров: 950; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |