Пример 1.1

z = x₁ + 2 x₂ ® max (min)

3 x₁ – x₂ ≥ 8

– x₁ + 3 x₂ ≤ 16

2 x₁ – x₂ ≤ 13

x₁ + 4 x₂ ≥ 20

x₁ ≥ 0; x₂ ≥ 0

С учетом системы ограничений построим множество допустимых решений Ω (рисунок 1.3).

Рисунок 1.3 – Графическое решение задачи

Строим в системе координат x₁Ox₂прямые :

l₁ : 3 x₁ – x₂ = 8;

l₂ : – x₁ + 3 x₂ = 16;

l₃ : 2 x₁ – x₂ = 13;

l₄ : x₁ + 4 x₂ = 20.

Изобразим полуплоскости, определяемые системой ограничений. Находим множество допустимых решений Ω как общую часть полученных полуплоскостей – четырехугольник АВСD.

Строим вектор градиентного направления (1; 2). Для большей наглядности построим вектор 2 = (2; 4)

Строим произвольную линию уровня целевой функции, например z = 0, перпендикулярную к вектору . Перемещаем прямую z = 0 в направлении вектора до последней точки ее пересечения с областью допустимых решений Ω. В точке С целевая функция достигает максимума. Находим координаты точки С – точки пересечения прямых l₂ и l₃ как решение системы уравнений:

Следовательно, Х^* = (11; 9).

Вычислим значение целевой функции z_mах = z (Х^*) = 11 + 2×9 = 29.

Перемещаем эту прямую z = 0 в антиградиентном направлении до последней точки ее пересечения с областью допустимых решений Ω. В точке А целевая функция достигает минимума. Находим координаты точки А – точки пересечения прямых l₁ и l₄ как решение системы уравнений:

Следовательно, Х^* = (4; 4).

Вычислим значение целевой функции z_min = z (Х^*) = 4 + 2×4 = 12.

Дата добавления: 2014-12-09; просмотров: 231; Нарушение авторских прав

Мы поможем в написании ваших работ!