3. Линейное программирование

3.1. Основные понятия

ЗЛП: minf(x),xX

X={xRⁿ :g_j(x)0,j= 1...m},f,g_j - линейны для любогоj.

Таким образом ЗЛП- частный случай ЗНП.

Определение:

Функция называется линейной, если справедливо:

f(₁x₁+ ₂x₂) = ₁f(x₁) + ₂f(x₂), где _iR, x_iX.

В n-мерном пространстве линейная функция может быть определена так:

f(x) = (c,x)

f(x) = c₁x₁+ ....+ c_nx_n

Ограничения

Расширим класс задач

,

то есть передвинуть область в n-мерном пространстве.

Определение:

Если при задании допустимого множества Xиспользуются только неравенства, то это ЗЛП в стандартной форме.

Определение:

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

Возможны смешанные задачи.

ЗЛП в канонической форме эквивалентна некоторой задаче в стандартной форме и наоборот.

Пусть есть только неравенства. Как от них избавиться?

Надо расширить пространство: в каждое из неравенств добавляется еще одна координата (переменная) x_n+i 0

 +  +...+ +=

 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

• +  +...+ +=

Ограничения типа равенств можно представить в виде двух ограничений типа неравенств. Пусть (, x) = 0 , тогда (, x)0 и (, x)0

Матричная форма записи ЗЛП.

X = {Ax = b , x  0 , x } ; A - матрица размерности mn ; x - вектор размерности n ; b - вектор размерности m ;

f(x) = (c,x) - линейная функция;

f(x) - ЗЛП

Упражнение: Доказать, что допустимое множество Х ЗЛП – выпукло.

Определение: Точка x выпуклого множества называется крайней (угловой), если из

 + (1 - ) = x следует== x , т.е. крайнюю точку нельзя выразить с помощью линейной комбинации других точек выпуклого множества.

Теорема ( о представлении ) :

Всякая точка допустимого ограниченного множества ЗЛП допускает представление в виде выпуклой комбинации его крайних точек .

(без доказательства)

Теорема ( о существовании оптимальной точки ) :

Если целевая функция на допустимом множестве ЗЛП ограничена снизу, то оптимальная точка существует.

Доказательство: (без доказательства).

Таким образом, существует альтернатива :

1. либо минимум целевой функции на X есть -  ,

2. либо существует оптимальная точка : (c ,) =(c, x) , если X не пусто.

3.2. Геометрическая интерпретация злп.

Пусть X = {x , Ax  b , x  0} , f(x) = (c,x) - целевая функция

A=- матрица, где- строка длины n ;

b=- вектор размерности m.

Тогда одно условие принимает вид : (, x) , i =

Множество точек, для которых справедливо это неравенство - полупространство с граничной гиперплоскостью (, x) =.

Определение: Гиперплоскость в пространстве - это пространство размерности . Таким образом, допустимое множество X является пересечением конечного числа полупространств.

Рассмотрим двумерный случай (n = 2) :

Гиперплоскость - прямая; полупространство - полуплоскость.

Рис.1а.

* здесь ограниченное допустимое множество

x  0, т.е. допустимое множество находится в 1 квадранте.

Рис.2а.

* здесь неограниченное допустимое множество

Какая точка может быть оптимальной для ЗЛП?

Наряду с допустимыми множествами введем в рассмотрение целевую функцию.

Рис.1б.

Для функции 2 (рис.2б) точки min нет. Даже в случае неограниченного допустимого множества оптимальная точка может существовать ( но ее может и не быть) .