Исследование операций в экономике

Задача 1

Решить графическим методом задачу линейного программирования:

а) найти область допустимых значений (многоугольник решений);

б) найти оптимумы целевой функции.

max и min Z = 2x1 + 4x2

x1 + 3x2 6

x1 + 5x2 5

x1 + x2 6

x1 0, x2 0

Прямые ограничения x1 0, x2 0 означают, что область решений будет лежать в первой четверти декартовой системы координат (рис. 1).

. Множество решений каждого нестрогого неравенства - объединение решений уравнения и строгого неравенства. Заданы уравнения прямых, для построения каждой прямой достаточно двух точек. Удобно строить прямые по точкам пересечения их с осями координат (когда одна из координат равна нулю).

Найдем точки пересечения прямых с осями координат:

Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости. В качестве такой точки удобно брать начало координат. Множества решений 3-го неравенства - полуплоскость, лежащая ниже построенной III-й прямой. Это выясним, взяв контрольную точку, например, (0; 0): 2*0+1*0=0 < 6. Множества решений 1-го и 2-го неравенств - полуплоскости, лежащие выше построенных соответственно I-й и II-й прямых. Это выясним, взяв контрольную точку, например, (0; 0): 2*0+3*0=0 > 6, 1*0+5*0=0 > 5. Добавив прямые ограничения, получим многоугольник решений (заштрихованный), обозначим вершины полученного многоугольника решений ABCD.

Координаты этих вершин являются допустимыми решениями данной задачи линейного программирования. Их можно определить, решая систему уравнений двух пересекающихся соответствующих прямых.

Например, точка В - точка пересечения II и III прямых:

б) Приравняем целевую функцию F к постоянной величине а:

x1 + 4x2 = а.

Это уравнение - множество точек, в котором целевая функция принимает значение, равное а. Построим линию уровня при а = 0 (пунктирная прямая): 2x1 + 4x2 = 0.

Точка пересечения этой прямой с осями координат: (0; 0).

При х1 = 1 2*1 + 4*х2 = 0 х2 = 2/4 = 1/2 (1, 1/2).

Для определения направления к оптимуму построим вектор-градиент , координаты которого - частные производные функции F, т.е. = (с1; с2) = (2; 4). Для построения соединим точку (2; 4) с началом координат.

Для нахождения максимума целевой функции смещаем линию уровня параллельно самой себе в направлении вектора-градиента. Максимум достигается в точке A, координаты которой найдем, решая систему уравнений пересекающихся прямых III и x1 =0: