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

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

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
English     Русский Rules