КАТЕГОРИИ: Архитектура-(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) |
Приведение ЗЛП к канонической форме
Алгоритмы решения ЗЛП (например, симплекс-метод) разработаны для канонической формы. Приведем стандартную ЗЛП (5.2) к канонической форме. Для этого обратим ограничения-неравенства в равенства, введя дополнительные неотрицательные переменные yi, (m - количество ограничений), которые входят в целевую функцию f(x) с нулевыми коэффициентами. В этом случае исходная задача будет эквивалентна исходной, так как оптимальное значение целевой функции не изменится: max (+0• yi) при ограничениях- равенствах , Пример1. Привести ЗЛП к каноническому виду: f(x)=2x1 +x2 – х3 → max при ограничениях 2x2 – x3 ≤5 x1 +x2 – x3 ≥ -1 2x1 – x2 ≤-3 х1≤ 0, x3 ≥ 0 Решение. Введем в каждое ограничение дополнительные неотрицательные переменные х4, х5, х6, причем в первое и третье ограничение переменные х4, х6 войдут со знаком «+», а во второе ограничение х5 войдет со знаком «-»: 2x2 – x3 + х4 =5 x1 +x2 – x3 - х5 = -1 2x1 – x2 +х6=-3 x4 ≥ 0, x5 ≥ 0, x6 ≥ 0 Свободные члены (правые части ограничений) в канонической форме должны быть положительными, поэтому два последних ограничения умножим на -1: 2x2 – x3 + х4 =5 -x1 -x2 + x3 + х5 = 1 -2x1 + x2 -х6=3. В канонической форме все переменные должны быть неотрицательными. Поэтому проведем замену: хj = хj+ - хj-, j=1,2, причем хj+·хj-=0. При этом количество оптимизируемых переменных увеличивается: f(x)=2x1+ - 2x1-+ x2+ - x2- - x3→ max 2x2+ - 2x2-- х3 +х4 =5 -x1+ + x1-- x2+ + x2-+ х3 + х5 =1 -2x1+ + 2x1-+ x2+ - x2-- х6 =3 хj+ ≥ 0, хj-≥ 0, j=1,2 Переобозначим переменные: x1+ → х1; x1-→ х7; x2+ → х2; x2-→ х8. Получим следующую задачу оптимизации: f(x)= 2x1 + x2– x3 -2x7 – х8 → max 2x2 - х3 +х4 - 2x8=5 -x1 - x2 + х3 + х5 + x7 +x8 =1 -2x1 + x2 - х6 + 2x7 - x8=3 хj ≥ 0,
Дата добавления: 2014-01-07; Просмотров: 319; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |