Используя графический метод, найти решение следующей задачи линейного программирования:
Fx1,x2=12x1+x2→min
Построить область допустимых решений системы линейных неравенств.
x1+4x2≥74x1+x2≥83x1+2x2≥11x1≥0x2≥0
Решение
Построение области допустимых решений (ОДР)
В неравенствах системы заменим знаки неравенств на знаки точных равенств и построим соответствующие им прямые.
l1:x1+4x2=7
4x2=-x1+7
x2=-14x1+74
Строим прямую l1 по двум точкам:
x1
-1 3
x2
2 1
l2: 4x1+x2=8
x2=-4x1+8
Строим прямую l2 по двум точкам:
x1
0 1
x2
8 4
l3: 3x1+2x2=11
2x2=-3x1+11
x2=-32x1+112
Строим прямую l3 по двум точкам:
x1
1 3
x2
4 1
l4: x1=0 – ось ординат
l5: x2=0 – ось абсцисс
Строим полученные прямые (рис. 1).
Рис. 1. Прямые, задающие область опустимых решений
Определяем полуплоскости, удовлетворяющие неравенствам системы: их пересечение образует область допустимых решений.
Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству системы ограничений, а другой – нет
. Чтобы определить искомую полуплоскость, нужно взять какую-либо точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты исходному неравенству. Если удовлетворяют, то искомой является та полуплоскость, которой эта точка принадлежит; в противном случае – другая полуплоскость.
Прямая l1
Точка 0;0
Неравенство x1+4x2≥7
0+0≥7 – неверное
Т.е. выбираем полуплоскость, не содержащую точку (0; 0)
Прямая l2
Точка 0;0
Неравенство 4x1+x2≥8
0+0≥8 – неверное
Т.е. выбираем полуплоскость, не содержащую точку (0; 0)
Прямая l3
Точка 0;0
Неравенство 3x1+2x2≥11
3x1+2x2≥11 – неверное
Т.е. выбираем полуплоскость, не содержащую точку (0; 0)
Условия неотрицательности переменных определяют первую координатную четверть.
Построим область допустимых решений задачи линейного программирования, которая является пересечением указанных полуплоскостей (рис. 2).
Рис