Программирования

Рассмотрим следующую задачу: найти такие значения переменных Х₁ и Х₂, которые максимизируют функцию цели

f(x) = C₁× Х₁+ C₂× Х₂® max (1.14)

при выполнении ограничений

а_i₁× Х₁+ а_i₂× Х₂£ b_i; (i = ); (1.15)

условие неотрицательности Х₁³ 0, Х₂³ 0. (1.16)

Каждое неравенство (1.15) и (1.16) системы ограничений геометрически представляет собой полуплоскость с граничными прямыми:

а_i₁× Х₁+ а_i₂× Х₂= b_i (i = ),

- оси координат (решение

получаем в 1 квадранте).

В том случае, если система неравенств (1.15) и (1.16) совместна, то область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. А так как множество точек пересечения данных полуплоскостей – выпуклое, то область допустимых решений задачи (1.14) – (1.16) есть выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получают из исходной системы ограничений заменой знаков неравенств на знаки точных равенств. Таким образом, исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой функция цели f(x) принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и функция цели ограничена сверху.

При указанных условиях в одной из вершин многоугольника функция цели принимает максимальное значение. Для определения данной вершины строится вектор-нормаль с координатами – коэффициентами функции цели . Перпендикулярно вектору-нормали построим линию уровня C₁× Х₁+ C₂× Х₂= h (где h – некоторое число, которое подбирается таким, чтобы эта линия уровня проходила через многоугольник решений). Будем передвигать линию уровня в направлении вектора–нормали до тех пор, пока она не дойдет до последней общей точки с многоугольником решений. Координаты этой точки и определяют оптимальный план – решение задачи.

Координаты этой точки А находятся следующим образом: решается система уравнений, которые соответствуют линиям-ограничениям, на пересечении которых эта точка находится. Подставляя значения координат этой точки в функцию цели, получаем максимальное значение целевой функции. Для нахождения минимума функции цели линия уровня передвигается не в направлении вектора-нормали, а в противоположном направлении.

При нахождении решения задачи (1.14) – (1.16) возможны следующие случаи:

1. Единственное оптимальное решение – в точке А функция цели принимает максимальное значение

Х₂

- линия уровня

С₂(f(х) ® max)

f(х) = 0 - область

вектор- допустимых значений

нормаль 0 С₁ Х₁

2. Множество точек на отрезке DВ – оптимальное решение

Х₂ линия уровня (f(х) ® min)

в любой точке этого отрезка функция цели принимает минимальное значение. В этом случае функция цели пропорциональна одному из ограничений.

0 Х₁

3. Функция цели не ограничена сверху на множестве допустимых решений

Х₂

- линия уровня (f(х)_max = + ¥)

0 Х₁

4. Система ограничений задачи несовместна. Условия противоречивы. Многоугольник решений пуст. Решения нет.

Х₂

Х₁

Пример. Найти решение задачи графическим и аналитическим методами:

f(x) = 2X₁ + X₂® max,

–2X₁ + X₂£ 2,

X₁ + X₂£ 4,

X₁ – X₂£ 1,

X₁ ³ 0, X₂³ 0.

Решение.

Построим прямые, уравнения которых получаем в результате замены в системе ограничений знаков неравенств на знаки точных равенств. Получаем уравнения прямых линий на плоскости. Для того, чтобы провести прямую линию, достаточно знать координаты двух точек. Проведем линию (1), соответствующую первому ограничению. Для этого присвоим переменной Х₂ некоторое значение, например ноль, и определим значение переменной Х₁, найдем координаты первой точки (-1; 0). Приравняв нулю переменную Х₁, найдем значение переменной Х₂ – координаты второй точки (0; 2). Для того, чтобы определить, с какой стороны от проведенной линии находится область допустимых значений, необходимо подставить в неравенство координаты какой-нибудь точки пространства, например начала координат (Х₁ = 0, Х₂ = 0). Полученное значение – ноль, меньше чем два (правая часть ограничения), а значит, точка начала координат принадлежит искомой полуплоскости. Повторим построения для всех остальных ограничений задачи и получим многоугольник решений ОDАВЕ. Построим вектор-нормаль, выходящий из начала координат в направлении точки с координатами – коэффициентами функции цели (Х₁ = 2, Х₂ = 1) или пропорциональными этим координатам (Х₁ = 1, Х₂ = 0,5). Линия уровня (соответствующая функции цели) строится перпендикулярно вектору-нормали или же функция цели приравнивается какому-либо числу, например f(x) = 2X₁ + X₂= 2 и проводится соответствующая линия. Передвинем линию уровня в направлении, указанном вектором. В результате находим точку А, в которой целевая функция принимает максимальное значение. Находим координаты этой точки. Для этого решим систему уравнений, которые соответствуют прямым, на пересечении которых находится точка А: