Задачи линейного программирования. (Тема 3)

1. Задачи линейного программирования (ЗЛП)

2.

Для задач линейного программирования характерно наличие
следующих 3-х компонентов:
целевая функция;
• система ограничений;
• ограничения на знак переменных
ЗЛП – это задача следующего вида:
n
z x j c j max(min)
j 1
(1)
(i 1,m)
(2)
n
aij x j ( , , ) bi
j 1
x 0 ( j 1,l )
j
l n
(3)
Уравнение (1) – это целевая функция, а (2) и (3) – это система
ограничений.

3.

Вектор X ( x , , x ) называется допустимым планом ЗЛП,
1
n
если он удовлетворяет ограничениям (2) и (3).
Вектор X * ( x*, , x* ) называется оптимальным планом ЗЛП,
1
n
если он является допустимым и обеспечивает минимум или
максимум целевой функции.
Множество всех допустимых планов ЗЛП образует область
допустимых значений (ОДЗ).

4.

Формы записи ЗЛП
1) Развёрнутая форма записи:
z c x c x c x min(max)
11 2 2
n n
a x a x b ,
11 1
1n n 1
x b ,
a x a
k
1
1
kn
n k
a
x a
x b ,
k 1,1 1
k
1
,
n
n k 1
a x a x b ,
ln n l
l1 1
a
x a
x b ,
l 1,1 1
l 1,n n l 1
x a x b .
a
mn n m
m1 1
x , x 0, p n
1
p

5.

2) Матричная форма записи ЗЛП:
(1) CX min(max), C (c , , c );
1
n
b
x
(2) AX ( , , )B,
1
1
B ;
X
,
X 0,
b
x
m
n
(3) A (a )
.
ij m n
3) Векторная форма записи ЗЛП:
z CX min(max)
n
T
Aj X j B
j 1
x 0, ( j 1,n)
j
a
1j
Aj ,
a
mj

6.

Каноническая форма записи ЗЛП
n
z c x min
j j
j 1
(1)
n
aij x j bi , (i 1,m) (2)
j 1
В системе ограничений стоят знаки только равенства.
x 0, ( j 1,n)
j
b 0, (i 1,m)
i
(3)
(4)
В системе ограничений присутствует выделенный исходный базис.
Базисным решением системы уравнений называется
решение, в котором значение всех небазисных переменных
равно нулю. Базисное решение называется вырожденным,
если в нем хотя бы одна базисная переменная равна нулю.
Базисное решение называется опорным, если значение всех
базисных переменных неотрицательно.

7. Приведение ЗЛП к канонической форме

1) max z’=-z,
z' c x c x min
11
n n
2) 3x1 x2 5 3x1 x2 xn 1 5, xn 1 0
Если в ограничении стоит знак
, то к левой части ограничения до-
бавляем дополнительную переменную xn k со знаком “+”(
3) Если xk 0 не указано, то xk xk ' xk ",
x
0);
n k
x ', x " 0
k k
Пункты (4) и (5) означают поиск в системе ограничений исходного
опорного решения.
Если в ЗЛП нет опорного решения, то такая задача не имеет
решений по причине несовместности системы ограничений.
ЗЛП может не иметь решения по двум причинам:
1) система ограничений несовместна;
2) целевая функция не ограничена на ОДЗ.

8.

Пример
1)
z 3x 4 x 5x max
1
2
5
2)
8 x 4 x 3x x 10,
2
3 6
1
2 x 4 x 18,
5
1
7 x 8 x x 15.
4 7
2
8x 4 x 3x 10,
1
2
3
2 x 4 x 18,
5
1
7 x2 8x4 15.
x , x , x 0
1 3 4
3) x2 x2' x2", x5 x5 ' x5"
x , x , x 0, x , x 0,
6 7
1 3 4
4)
z' 3x 4 x ' 4 x " 5x ' 5x " min
1
2
2
5
5
8 x 4 x ' 4 x " 3x x 10,
2
2
3 6
1
2 x 4 x ' 4 x " 18,
5
5
1
7 x ' 7 x " 8 x x 15.
2
4 7
2
x , x , x , x , x , x ', x ", x ', x " 0
1 3 4 6 7 2 2 5 5
x ', x ", x ', x " 0,
2 2 5 5
z' 3x 4 x 5x min
1
2
5
8 4 4 3 0 0 0 1 010
2 0
0 0 0 4 40018
0 7 7 0 80 0 0115