2.2 Построение целевой функции

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

Z = Х₁ - 3Х₂ = 0.

Эта прямая, проходящая через начало координат, строится следующим образом. Легко заметить, что в левой части данного уравнения стоит скалярное произведение двух векторов:

N = (с₁, с₂) = (1, -3) и Х = (х₁, х₂).

Скалярное произведение равно нулю когда векторы перпендикулярны.

Построим вектор N – вектор нормали. Он проходит через начало координат и точку (1, -3). Перпендикулярно ему через начало координат проведем прямую. Это и будет прямая целевой функции Z = 0.

В ектор N всегда показывает направление возрастания (максимизации) значения целевой функции, а противоположный ему вектор (- N ) – направление убывания (минимизации) значения целевой функции.

П ередвигая прямую Z = 0 по области допустимых решений параллельно самой себе в направление вектора N, значения целевой функции будут возрастать. Передвижение ее в направлении вектора ( - N ) дает убывание целевой функции.

П ередвижение на графике прямой Z = 0 равносильно изменению значения b в уравнении Х₁ - 3Х₂ = b. Каждому значению b соответствует прямая. Полученные прямые параллельны между собой и называются линиями уровня. Особенность линии уровня состоит в том, что целевая функция принимает на ней одинаковые значения, т.е. подставив координаты любой точки линии уровня в целевую функцию, ее значение изменяться не будет.

3. Нахождение оптимального решения

Оптимальному решению рассматриваемой задачи соответствует точка В, которая лежит на пересечении прямых (2) и (4):

-X₁ + X₂ = 3

X₁ + X₂ = 10 .

Для определения координат точки В решим систему двух линейных уравнений с двумя неизвестными. В результате получим, что минимум целевой функции достигается в точке В:

1 1 7 13

Х₁^* = 3—, Х₂^* = 6-- , Z_min = --- -- 3--- = - 16.

2 2 2 2

3 Вопросы для самоконтроля

1. Какие задачи линейного программирования можно решить графическим методом?

2. Какую область образуют допустимые решения задачи линейного программирования и что она собой представляет?

3. Какое множество называется выпуклым?

4. Что такое угловая точка?

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

6. Какая зависимость существует между областью определения задачи и ее решением?

7. Какие возможны исходы при решении задачи линейного программирования?

8. Что показывает направляющий вектор N?

9. Что показывает направляющий вектор -N?

10. Что такое линии уровня?