Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Найти максимум функции F при заданных ограничениях:
1. 2.
3. 4.
5. 6.
7.
Найти минимум функции F при заданных ограничениях:
8. 9.
10. 11.
12. 13.
14.
Ответы: 1. F max=4; 2. F max=∞; 3. F max=22/3; 4. решений нет; 5. F max=∞; 6. F max=37; 7. F max=6; 8. F min=∞; 9. F min=-1; 10. решений нет; 11. F min=8/3; 12. F min=300; 13. F min=9; 14. F min=1.
Основные положения о решении ЗЛП
5.
Утверждение 1. Решением системы ограничений ЗЛП (если он совместна) является выпуклый многогранник (на плоскости многоугольник).
Утверждение 2. Целевая функция достигает оптимальное решение хотя бы в одной угловой точке многогранника решений (если он ограниченный).
Утверждение 3. Если многогранник решений неограничен в направлении градиента целевой функции, то fmax = +∞, если в противоположном направлении, то fmin = -∞.
Утверждение 4. Точка X является угловой точкой многогранника тогда и только тогда, когда она является базисным решением системы ограничений ЗЛП.
Из четвертого утверждения следует, что для решения ЗЛП можно простым перебором из всех базисных решений выбрать то, в котором целевая функция принимает наибольшее или наименьшее значение. Это и будет решением задачи.
Любая система уравнений имеет конечное число базисных решений, равное ,
где п — число неизвестных,
r — ранг системывекторов условий, но сростом n число базисных решений резко растет.
Так, например, если п = 8, a r = 3, то число базисных решений
N≤ = 56.
Базисные решения, координаты которых удовлетворяют условию неотрицательности, являются так называемыми опорными.
Опорным решением задачи линейного программирования называется Х= (х 10, х 20 , …, хт0 , 0, …, 0), для которого векторы условий, соответствующие положительным координатам А 1, А2,..., Ат, линейно независимы.
Число отличных от нуля координат опорного решения не может быть больше ранга r системы векторов условий (т.е. числа линейно независимых уравнений системы ограничений).
В дальнейшем будем считать, что система ограничений состоит из линейно независимых уравнений, т.е. т = r.
Если число отличных от нуля координат опорного решения равно т, то оно (решение) называется невырожденным, в противном случае (меньше т) — вырожденным.
Базисом опорного решения называется базис системы векторов условий задачи, в состав которого входят векторы, соответствующие отличным от нуля координатам опорного решения.
Дата публикования: 2015-11-01; Прочитано: 389 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!