Лекция 4
.pdfДве задачи ЛП, обладающие указанными свойствами, называются
симметричнымивзаимно двойственнымизадачами, или просто
двойственнымизадачами. Алгоритмсоставления двойственной задачи:
•Привестивсе неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум целевой функции, топриводят их к виду: <=, если минимум, то к виду <=. Если требование не соблюдается, неравенство умножают на -1.
•Составитьрасширенную матрицу системы АI, в которую включить матрицукоэффициентов при переменных а, столбец свободных членовсистемы ограничений b и строку коэффициентов при переменных в целевой функции с.
•Найти матрицуAII, транспонированную к АI.
•Сформулироватьдвойственную задачу на основании полученной матрицыАI, и условия неотрицательностипеременных.
11
ПРИМЕР ДВОЙСТВЕННОЙ ЗАДАЧИ:
F x1 |
2 x2 |
max |
|
|
|
x1 0 |
x2 0 |
2 x1 |
x2 |
1 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 x1 x2 1 |
|
|
2 1 |
1 |
|
x1 4 x2 24 |
|||||||||||
|
|
x1 x2 3 |
|||||||||||||||
|
|
|
|
|
|
1 4 |
24 |
|
|||||||||
x 4 x 24 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
1 |
2 |
|
|
A |
1 |
1 |
3 |
|
|
x x |
|
5 |
|||||
|
|
|
|
I |
|
|
|
2 |
|||||||||
x1 x2 3 |
|
|
|
1 |
1 |
5 |
1 |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
1 2 |
F |
|
|
|
|
|
|
|
|
|
|
x1 x2 5 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
2 |
1 |
1 1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
4 |
1 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
AII 1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
3 5 |
Z |
|
|
|
2 y y |
|
y |
|
y |
|
1 |
||||
1 24 |
|
|
|
|
|
|
|||||||||||
Z y1 24y2 |
3y3 |
5y4 min |
|
1 |
2 |
|
3 |
|
|
|
4 |
2 |
|||||
y1 |
4 y2 |
y3 |
y4 |
||||||||||||||
y1 0 y2 0 y3 0 y4 0
Уже известная Вам задача линейного программирования |
12 |
|
5x1 7x2 |
6x3 |
9,5x4 max |
||||||||
|
x1 |
3x2 |
2x3 |
x4 100 |
|||||||
|
x 2x |
2 |
2x 2x |
4 |
60 |
||||||
|
|
1 |
|
3 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
10x1 10x2 7x3 5x4 310 |
||||||||||
|
5x 10x 5x |
4 |
200 |
||||||||
|
|
|
1 |
|
3 |
|
|
|
|
|
|
|
|
|
5x2 |
4x3 |
x4 150 |
|
|||||
|
|
|
|||||||||
|
x1 |
|
|||||||||
|
xi |
0, i 1,2,...,4 |
|
|
блочный |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
значение |
|
|
|
|
|
0 |
||||
|
|
|
|
|
|
||||||
|
прибыль |
|
|
|
|
|
5 |
||||
Вид ресурса |
|
электроэнергия |
1 |
трудовые ресурсы |
1 |
железобетонные изделия |
10 |
кирпич |
5 |
пиломатериалы |
1 |
100u1 60u2 310u3 200u4 150u5 min
u1 u2 10u3 5u4 u5 5
3u1 2u2 10u3 5u5 7
2u1 2u2 7u3 10u4 4u5 6
u1 2u2 5u3 5u4 u5 9.5
Переменные ui 0, i 1,2,...,4
панельный |
кирпичный |
монолитный |
|
|
|
|
|
0 |
0 |
0 |
ЦФ |
|
|
|
|
|
|
|
|
||||
7 |
6 |
9,5 |
|
0 |
|
|
|
|
|
|
|
||||
Ограничения |
|
|
|
|
|
|
|
Потребность |
|
|
|
|
Количество ресурса |
||
|
|
|
|
в наличии |
|||
|
|
|
|
|
|
||
3 |
2 |
1 |
0 |
|
<= |
100 |
|
2 |
2 |
2 |
0 |
|
<= |
60 |
|
10 |
7 |
5 |
0 |
|
<= |
310 |
|
0 |
10 |
5 |
0 |
|
<= |
200 |
|
5 |
4 |
1 |
0 |
|
<= |
150 |
13 |
РЕЗУЛЬТАТ РЕШЕНИЯ ДВОЙСТВЕННОЙЗАДАЧИ
A |
B |
1 |
|
2 |
|
электроэнергия |
|
значение |
|
||
3 |
0 |
||
4 |
прибыль |
100 |
|
5 |
|
|
|
|
Вид |
|
|
6 |
продукта |
|
|
блочный |
1 |
||
7 |
|||
8 |
панельный |
3 |
|
9 |
кирпичный |
2 |
|
10 |
монолитный |
1 |
C |
D |
E |
F |
G |
H |
I |
Переменные |
|
|
|
|
|
|
трудовые ресурсы |
железобетонные изделия |
кирпич |
пиломатериалы |
|
|
|
4,5 |
0 |
0,1 |
0 |
ЦФ |
|
|
|
|
|||||
60 |
310 |
200 |
150 |
290 |
|
|
|
|
|
|
Левая |
|
Количество |
|
|
|
|
|
||
Ограничения |
|
|
Знак |
ресурса в |
||
|
|
часть |
||||
|
|
|
|
|
наличии |
|
|
|
|
|
|
|
|
1 |
10 |
5 |
1 |
5 |
>= |
5 |
2 |
10 |
0 |
5 |
9 |
>= |
7 |
2 |
7 |
10 |
4 |
10 |
>= |
6 |
2 |
5 |
5 |
1 |
9,5 |
>= |
9,5 |
|
|
|
|
|
|
14 |
|
|
|
|
|
|
Результ. |
Нормир. |
|
Целевой |
Допустимое |
Допустимое |
|
|
|
|
Ячейка |
Имя |
значение стоимость Коэффициент |
|
|
|||||
|
|
|
$B$3 |
значениеблочный |
|
20 |
0 |
|
5 |
|
|
|
|
|
|
$C$3 |
значениепанельный |
|
0 |
-2 |
|
7 |
|
|
|
|
|
|
$D$3 |
значениекирпичный |
|
0 |
-4 |
|
6 |
|
|
|
|
|
|
$E$3 |
значениемонолитный |
|
20 |
0 |
|
9,5 |
|
|
|
|
|
Ограничения |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
Результ. |
Теневая |
Ограничение |
Допустимое |
Допустимое |
||
|
|
|
Ячейка |
Имя |
значение |
Цена |
Правая |
|
|
|||
|
|
|
$F$7 |
электроэнергияЦФ |
|
40 |
0 |
|
|
|
|
|
|
|
|
$F$8 |
трудовыересурсыЦФ |
|
60 |
4,5 |
|
|
|
|
|
|
|
|
$F$9 |
железобетонныеизделияЦФ |
300 |
0 |
|
|
|
|
||
|
|
|
$F$10 |
кирпич ЦФ |
|
200 |
0,1 |
|
|
|
|
|
Изменяемыеячейки |
$F$11 |
пиломатериалыЦФ |
|
40 |
0 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Результ. |
Нормир. |
|
Целевой |
|
Допустимое |
Допустимое |
|
|
Ячейка |
|
Имя |
значение стоимость Коэффициент Увеличение Уменьшение |
|
|||||||
|
$B$3 |
значениеэлектроэнергия |
0 |
60 |
100 |
1E+30 |
60 |
|
||||
|
$C$3 |
значениетрудовыересурсы |
4,5 |
0 |
60 |
20 |
2 |
|
||||
|
$D$3 |
значениежелезобетонныеизделия |
0 |
10 |
310 |
1E+30 |
10 |
|
||||
|
$E$3 |
значениекирпич |
|
0,1 |
0 |
200 |
3,333333333 |
50 |
|
|||
|
$F$3 |
значениепиломатериалы |
0 |
110 |
150 |
1E+30 |
110 |
|
||||
|
Ограничения |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
Результ. |
Теневая |
Ограничение |
Допустимое |
Допустимое |
|
||
|
Ячейка |
|
Имя |
значение |
Цена |
Правая |
|
Увеличение |
|
|
||
|
$G$7 блочныйЛеваячасть |
5 |
|
|
|
|
|
|
|
|||
|
$G$8 |
панельныйЛеваячасть |
9 |
|
|
|
|
|
|
|
||
|
$G$9 кирпичныйЛеваячасть |
10 |
|
|
|
|
|
|
15 |
|||
$G$10 монолитныйЛеваячасть |
9,5 |