Студопедия

КАТЕГОРИИ:


Архитектура-(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.

Основные положения о решении ЗЛП

Задачи для самостоятельного решения

Найти максимум функции F при заданных ограничениях:

1. 2.

3. 4.

5. 6.

7.

Найти минимум функции F при заданных ограничениях:

8. 9.

10.

11.

12.

13.

14.

Ответы: 1. Fmax=4; 2. Fmax=∞; 3. Fmax=22/3; 4. решений нет; 5. Fmax=∞; 6. Fmax=37; 7. Fmax=6; 8. Fmin=∞; 9. Fmin=-1; 10. решений нет; 11. Fmin=8/3; 12. Fmin=300; 13. Fmin=9; 14. Fmin=1.


Утверждение 1. Решением системы ограничений ЗЛП (если он совместна) является выпуклый многогранник (на плоскости многоугольник).

 

Утверждение 2. Целевая функция достигает оптимальное решение хотя бы в одной угловой точке многогранника решений (если он ограниченный).

 

Утверждение 3. Если многогранник решений неограничен в направлении градиента целевой функции, то fmax = +∞, если в противоположном направлении, то fmin = -∞.

 

Утверждение 4. Точка X является угловой точкой многогранника тогда и только тогда, когда она является базисным решением системы ограничений ЗЛП.

 

Из четвертого утверждения следует, что для решения ЗЛП можно простым перебором из всех базисных решений выбрать то, в котором целевая функция принимает наибольшее или наименьшее значение. Это и будет решением задачи.

Любая система уравнений имеет конечное число базисных решений, равное ,

где п — число неизвестных,

r — ранг системы векторов условий, но сростом n число базисных решений резко растет.

Так, например, если п = 8, a r = 3, то число базисных решений

N≤ = 56.

 

Базисные решения, координаты которых удовлетворяют условию неотрицательности, являются так называемыми опорными.

 

Опорным решениемзадачи линейного программирования называется Х=( х10 , х20 , …, хт0 ,0, …, 0), для которого векторы условий, соответствующие положительным координатам А1, А2, ..., Ат, линейно независимы.

 

Число отличных от нуля координат опорного решения не может быть больше ранга r системы векторов условий (т.е. числа линейно независимых уравнений системы ограничений).



В дальнейшем будем считать, что система ограничений состоит из линейно независимых уравнений, т.е. т = r.

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

Базисом опорного решенияназывается базис системы векторов условий задачи, в состав которого входят векторы, соответствующие отличным от нуля координатам опорного решения.

<== предыдущая лекция | следующая лекция ==>
Задач линейного программирования | Симплекс-метод. Симплексный метод — это метод целенаправленного перебора опорных решений задачи линейного программирования

Дата добавления: 2014-01-04; Просмотров: 211; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.