Эквивалентные формы задач линейного программирования (ЛП)

1. Эквивалентные формы задач линейного программирования (ЛП)

2.

Общая задача ЛП
а11 x1 ... а1n xn b1,
.... .... ....,
аk1x1 ... аknxn bk ,
аk 1x1 ... аk 1n xn bk 1,
.... .... ....,
аm1x1 ... аmn xn bm ,
x j 0, j {1, 2, ..., n}
L с1x1 ... сn xn min(max)

3.

Общая задача ЛП
• Ограничения как в виде равенств, так и в
виде неравенств;
• Условие неотрицательности может быть
наложено не на все переменные;
• Минимазация (максимазиция) целевой
функции

4.

Стандартная форма задачи ЛП
а11 x1 ... а1n xn b1,
.... .... ....,
а
x
...
а
x
b
,
m
1
1
mn
n
m
x j 0, j 1, 2, ..., n
L с1x1 ... сn xn min(max)

5.

Стандартная форма задачи ЛП
• Однородная система ограничений в виде
системы неравенств;
• Все переменные не являются
отрицательными;
• Минимазация (максимазиция) целевой
функции

6.

Каноническая форма задачи ЛП
а11 x1 ... а1n xn b1,
.... .... ....,
а
x
...
а
x
b
,
m
1
1
mn
n
m
x j 0, j 1, 2, ..., n
L с1x1 ... сn xn min(max)

7.

Каноническая форма задачи ЛП
• Однородная система ограничений в виде
системы уравнений;
• Все переменные не являются
отрицательными;
• Минимазация (максимазиция) целевой
функции

8.

Пример построения канонической формы
• Привести задачу к КФ на максимум:
2 x1 x2 x3 2,
3x 2 x x 6,
1
2
3
x
x
x
4
,
1
2
3
x1 0, x2 0
L 3 x1 2 x2 x3 min

9.

Пример построения канонической формы
• Введем дополнительные (слабые)
переменные
2 x1 x2 x3 x4 2,
3x 2 x x x 6,
1
2
3
5
x
x
x
4
,
1
2
3
x1 0, x2 0, x4 0, x5 0,
L 3 x1 2 x2 x3 min

10.

Пример построения канонической формы
• Первый приём.
• Заменим x3 разностью двух неотрицательных
переменных: x3 x3 ' x3 ", x3 ' 0, x3 " 0

11.

Пример построения канонической формы
• Заменим x3 разностью двух неотрицательных
переменных: x x ' x ", x ' 0, x " 0
3
3
3
3
3
2 x1 x2 ( x3 ' x3") x4 2,
3x 2 x ( x ' x ") x 6,
1
2
3
3
5
x
x
(
x
'
x
"
)
4
,
1
2
3
3
x1 0, x2 0, x4 0, x5 0, x3 ' 0, x3" 0
L 3x1 2 x2 ( x3 ' x3") min

12.

Пример построения канонической формы
2 x1 x2 ( x3 ' x3") x4 2,
3x 2 x ( x ' x ") x 6,
1
2
3
3
5
x
x
(
x
'
x
"
)
4
,
1
2
3
3
x1 0, x2 0, x4 0, x5 0, x3 ' 0, x3" 0
L' L 3x1 2 x2 x3 ' x3 " max

13.

Пример построения канонической формы
• Второй приём.
• Найдем из какого-либо уравнения
переменную x3 .
• Пусть из третьего уравнения
x3 4 x1 x2

14.

Пример построения канонической формы
x3 4 x1 x2
2 x1 x2 (4 x1 x2 ) x4 2,
3x1 2 x2 (4 x1 x2 ) x5 6,
x 0, x 0, x 0, x 0,
2
4
5
1
L 3x1 2 x2 (4 x1 x2 ) min

15.

Пример построения канонической формы
x1 2 x2 x4 2,
2 x1 x2 x5 2,
x 0, x 0, x 0, x 0,
2
4
5
1
L 4 4x1 x2 min

16.

Пример построения канонической формы
x1 2 x2 x4 2,
2 x1 x2 x5 2,
x 0, x 0, x 0, x 0,
2
4
5
1
L' L 4 4x1 x2 max

17.

Ответ
x4 7 x5 3x6 1,
2 x 3x x 6,
4 5 6
3
x
x
2
x
3
4
5
6
x4 0, x5 0, x6 0,
L 7 x4 21x5 14 x6 18 max