В задаче выпуклого программирования требуется:
1) найти решение графическим методом,
2) написать функцию Лагранжа и найти ее седловую точку, используя решение, полученное графически.
x12+(x2-2)2→min
2x1+x2≥7x1+2x2≥5x1≥1x2≥0
Решение
Решение задачи графическим способом
Определение области допустимых решений (ОДР)
В неравенствах системы ограничений заменим знаки неравенств на знаки точных равенств и построим соответствующие им прямые.
l1: 2x1+x2=7
x2=7-2x1
Строим прямую l1 по двум точкам:
x1
0 3
x2
7 1
l2: x1+2x2=5
x2=2,5-0,5x1
Строим прямую l2 по двум точкам:
x1
0 3
x2
2,5 1
l3: x1=1
Прямая, параллельная оси ординат, проходящая через точку (1; 0)
l4: x2=0 – ось ординат
Строим полученные прямые (рис. 1).
Определяем полуплоскости, удовлетворяющие неравенствам системы ограничений: их пересечение образует область допустимых решений.
Четвертое неравенства определяют полуплоскость, расположенную выше оси абсцисс.
Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству системы ограничений, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять какую-либо точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты исходному неравенству. Если удовлетворяют, то искомой является та полуплоскость, которой эта точка принадлежит; в противном случае – другая полуплоскость.
Прямая l1
Точка 0;0
Неравенство 2x1+x2≥7
0≥7 – неверное
Т.е
. выбираем полуплоскость, не содержащую точку (0; 0)
Прямая l2
Точка 0;0
Неравенство x1+2x2≥5
0≥5 – неверное
Т.е. выбираем полуплоскость, не содержащую точку (0; 0)
Прямая l3
Точка 0;0
Неравенство x1≥1
0≥1 – неверное
Т.е. выбираем полуплоскость, несодержащую точку (0; 0)
Построим область допустимых решений задачи линейного программирования (рис. 1).
Рис. 1. Область допустимых решений
Заштрихованаая часть ABCDE – область допустимых решений (открытая).
Определение оптитмального решения
Координаты любой точки, принадлежащей этой области, удовлетворяют неравенствам системы ограничений и условию неотрицательности переменных. Поэтому исходная задача будет решена, если мы сможем найти точку, принадлежащую этой области, в которой целевая функция принимает минимальное значение.
Чтобы найти такую точку, построим (линию уровня): x12+(x2-2)2=h2 (где h –некоторая постоянная), проходящую через многоугольник решений. Линии уровня – это концентрические окружности, центр расположен в точке (0; 2) окружности