КАТЕГОРИИ: Архитектура-(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) |
Задач линейного программирования
с п переменными
Графическим методом можно решить задачи линейного программирования, имеющие каноническую форму и удовлетворяющие условию n - r ≤ 2, где п— число неизвестных системы; r — ранг системы векторов-условий (число линейно независимых уравнений системы). Если уравнения системы ограничений линейно независимы, то r = т, где т — число уравнений.
Рассмотрим алгоритм метода на конкретном примере. Пример. Решить графическим методом задачу F(X)=x 1+ x 2+5 x 3+3 x 4→ max
Решение. Проверяем, применим ли графический метод при решении данной задачи. Нетрудно видеть, что любые два из векторов-условий, например линейно независимы, так как их координаты непропорциональны. Поэтому ранг системы векторов-условий r= 2. Находим п – r = 4 - 2 = 2 ≤ 2. Следовательно, метод применим.
Приведем систему уравнений-ограничений к равносильной, с помощью линейных преобразований, предварительно записав её в матричной форме:
.
Таким образом, получили систему: .
Выразим переменные х 1 и х 2:
х 2=4-2 х 3- х 4
х 1=9-2 х 2 -3 х3 -3 х 4=9-2(4-2 х 3- х 4)-3 х3 -3 х 4=9-8+4 х 3+2 х 4 -3 х3 -3 х 4=1+ х3 - х 4 Т.к. х 1≥0 и х 2≥0, то систему уравнений мы записываем в виде системы неравенств:
В результате получим эквивалентную задачу линейного программирования с двумя переменными, которая решается графическим методом F (X)= 1+ х3 - х 4+4-2 х 3- х 4+5 х 3+3 х 4= =5+4 х 3+ х 4 → max
, х 3≥0, х 4≥0.
Находим оптимальное решение эквивалентной задачи и соответствующее ему максимальное значение целевой функции: С (2,0), F (C)=5+4·2+0=13.
Используем систему ограничений исходной задачи, приведенную к каноническому виду, и оптимальное решение задачи с двумя переменными для нахождения оптимального решения исходной задачи:
х 2=4-2 х 3- х 4=4-2·2-0=0, х 1=1+ х3 - х 4=1+2-0=3.
Следовательно, X= (3,0,2,0);
F (X)=3+0+5·2+3·0=13.
Ответ: max F (X)= 13, при X= (3,0,2,0).
Дата добавления: 2014-01-04; Просмотров: 367; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |