5 Приведите озлп к каноническому виду.

• неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополнительных переменных;

• если целевая функция F →max (максимизируется), она заменяется на функцию –F→ min (которая минимизируется).

Система ограничений имеет вид:

Неравенства были обращены в сторону «больше», поэтому вводя дополнительн ые переменные y₁, y₂, y₃ ≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:

Если бы сначала система ограничений была бы со знаком ≤, то дополнительные переменные были бы со знаком «+»

6 Приведите ОснЗлп к каноническому виду.

Любую ЗЛП можно привести к каноническому виду, используя следующие правила:

а) максимизация целевой функции f (x) = c1x1+…+cnxn равносильна минимизации

целевой функции: f (x) =-c1x1 -…-cnxn;

б) ограничение в виде неравенства, например, 3Х1 + 2Х2 – Х3 ≤ 6, может быть приве-

дено к стандартной форме 3Х1 + 2Х2 – Х3 + Х4 = 6, где новая переменная Х4 неотрицательна.

Ограничение Х1 – Х2 + 3Х3 ≥ 10 может быть приведено к стандартной форме Х1 – Х2 + 3Х3 – Х5 = 10, где новая переменная Х5 неотрицательна;

в) если некоторая переменная Хk может принимать любые значения, а требуется, что-

бы она была неотрицательная, ее можно привести к виду Xk

Xk= Xk′− Xk′′, где Xk′≥ 0 и Xk′′ ≥ 0

7 Перечислите свойства множества планов р.

• Множество планов Р задачи линейного программирования (ЗЛП) есть замкнутое выпуклое множество.

• Множество Р может быть как ограниченным, так и неограниченным, кроме того оно может оказаться пустым.

• Напомним, что множество точек Р пространства E_n есть выпуклое множество, если вместе с любыми двумя его точками X₁ и X₂ ему принадлежит и любая выпуклая линейная комбинация этих точек, то есть если X₁, X₂ Î P, то и любая точка также принадлежит множеству Р.

8 Дайте определение оптимального плана КЗЛП.

Дайте определение плана КЗЛП. Планом или допустимым решением задачи линейного программирования называется вектор X пространства Еn, компоненты которого удовлетворяют функциональным и прямым ограничениям задачи.

9 Какая ЗЛП называется разрешимой?

Задача линейного программирования называется разрешимой, если она имеет хотя бы один допустимый план. Если же злп не имеет допустимых решений, то она называется неразрешимой.

10 Дайте определение выпуклого множества.

Множество в аффинном пространстве называется выпуклым, если оно содержит вместе с любыми двумя точками соединяющий их отрезок.

11 Дайте определение гиперплоскости.

Множество точек Х =(Х1,Х2,...,Хn) пространства En , компоненты которых удовлетворяют условию

C1X1+ C2X2+...+ CnXn = b, называется гиперплоскостью пространства En.

Гиперплоскость — Гиперплоскость подпространство евклидова или аффинного пространства коразмерности 1, то есть с размерностью, на единицу меньшей, чем объемлющее пространство.

Размерность Г. на единицу меньше размерности рассматриваемого пространства Еn. Напр., для трехмерного пространства гиперплоскостью является плоскость, для двухмерного пространства — прямая на плоскости (отражаемая уравнением a₁x₁ + a₂x₂ = b).

Г. делит пространство (соответствующей размерности) на два полупространства, все точки каждого из них определяются неравенствами.