Симплексный метод решения задач линейного

5.

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

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

Найти максимум функции 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.

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

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

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

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

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

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

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

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

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

N≤ = 56.

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

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

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

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

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

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

Дата добавления: 2014-01-04