Лекция 4
.pdfДВОЙСТВЕННАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
УЧЕБНЫЕВОПРОСЫ:
1.Решениепрямой задачи распределения ресурсов в надстройке«Поиск решения».
2.Анализотчетов.
3.Двойственнаязадача линейногопрограммирования.
1
УСЛОВИЕЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
Строительноепредприятиеможетвозводитьжилые объекты четырех типов:панельный,блочный,кирпичныйи монолитный.Реализация единицыплощадикаждоговида жилья даетприбыль в5; 7;6 и 9,5 условныхединицсоответственно.Перечень ресурсов,их количествои нормырасходадля производстваединицыплощадикаждоговида жильяприведеныв таблице.Требуетсясоставитьтакойплан строительства,чтобы прибыль от реализациибыла максимальной.
Вид ресурса
электроэнергия
трудовыересурсы
железобетонныеизделия
кирпич
пиломатериалы
Нормы расхода
блочный |
панельный |
кирпичный |
монолитный |
Количество ресурса в |
|
|
|
|
|
|
|
|
|
наличии |
1 |
3 |
2 |
1 |
100 |
|
1 |
2 |
2 |
2 |
60 |
|
10 |
10 |
7 |
5 |
310 |
|
5 |
0 |
10 |
5 |
200 |
|
1 |
5 |
4 |
1 |
150 |
2 |
ФОРМАЛИЗОВАННОЕПРЕДСТАВЛЕНИЕЗАДАЧИ
|
|
Переменные |
|
|
|
|
|
блочный |
панельный |
кирпичный |
монолитный |
|
|
|
|
|
|
|
|
|
значение |
0 |
0 |
0 |
0 |
ЦФ |
|
|
|
прибыль |
5 |
7 |
6 |
9,5 |
|
0 |
|
|
|
|
Ограничения |
|
|
|
|
|
|
Вид ресурса |
|
Потребность |
|
|
|
|
Количество ресурса |
|
|
|
|
|
|
в наличии |
|||
|
|
|
|
|
|
|
|
|
электроэнергия |
1 |
3 |
2 |
1 |
0 |
|
<= |
100 |
трудовые ресурсы |
1 |
2 |
2 |
2 |
0 |
|
<= |
60 |
железобетонные изделия |
10 |
10 |
7 |
5 |
0 |
|
<= |
310 |
кирпич |
5 |
0 |
10 |
5 |
0 |
|
<= |
200 |
пиломатериалы |
1 |
5 |
4 |
1 |
0 |
|
<= |
150 |
3
ПОДГОТОВКА К РЕШЕНИЮЗАДАЧИ В НАДСТРОЙКЕ «ПОИСК РЕШЕНИЯ»
РЕЗУЛЬТАТЫ РЕШЕНИЯ ЗАДАЧИ В НАДСТРОЙКЕ «ПОИСК РЕШЕНИЯ»
|
|
Переменные |
|
|
|
|
|
|
|
блочный |
панельный |
кирпичный |
монолитный |
|
|
|
|
|
|
|
|
|
|
|
|
|
значение |
20 |
0 |
0 |
20 |
ЦФ |
|
|
|
прибыль |
5 |
7 |
6 |
9,5 |
|
290 |
|
|
|
|
Ограничения |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Количество ресурса |
|
|
|
|
|
|
|
|
в наличии |
|
|
|
|
|
40 |
|
<= |
100 |
|
|
|
|
|
60 |
|
<= |
60 |
|
|
|
|
|
300 |
|
<= |
310 |
|
|
|
|
|
200 |
|
<= |
200 |
пиломатериалы |
1 |
5 |
4 |
1 |
40 |
|
<= |
150 |
|
|
|
|
|
|
|
|
5 |
ОТЧЕТ ПО РЕЗУЛЬТАТАМ РЕШЕНИЯ
елевая ячейка (Максимум)
|
|
Ячейка |
Имя |
Исходно |
Результат |
|
|
|
|
$F$4 |
прибыль ЦФ |
0 |
290 |
|
|
зменяемые ячейки |
|
|
|
|
|||
|
|
Ячейка |
Имя |
Исходно |
Результат |
|
|
|
|
$B$3 |
значение блочный |
0 |
20 |
|
|
|
|
$C$3 |
значение панельный |
0 |
0 |
|
|
|
|
$D$3 |
значение кирпичный |
0 |
0 |
|
|
|
|
$E$3 |
значение монолитный |
0 |
20 |
|
|
граничения |
|
|
|
|
|||
|
|
Ячейка |
Имя |
Значение |
формула |
Статус |
Разница |
|
|
$F$7 |
электроэнергия ЦФ |
40 |
$F$7<=$H$7 |
не связан. |
60 |
|
|
$F$8 |
трудовые ресурсы ЦФ |
60 |
$F$8<=$H$8 |
связанное |
0 |
|
|
$F$9 |
железобетонные изделия ЦФ |
300 |
$F$9<=$H$9 |
не связан. |
10 |
|
|
$F$10 |
кирпич ЦФ |
200 |
$F$10<=$H$10 связанное |
0 |
|
|
|
$F$11 |
пиломатериалы ЦФ |
40 |
$F$11<=$H$11 |
не связан. |
110 |
|
|
$B$3 |
значение блочный |
20 |
$B$3>=0 |
не связан. |
20 |
|
|
$C$3 |
значение панельный |
0 |
$C$3>=0 |
связанное |
0 |
|
|
$D$3 |
значение кирпичный |
0 |
$D$3>=0 |
связанное |
0 |
|
|
$E$3 |
значение монолитный |
20 |
$E$3>=0 |
не связан. |
20 |
6
ОТЧЕТ ПО УСТОЙЧИВОСТИ РЕШЕНИЯ
Изменяемыеячейки
|
|
|
|
Результ. |
Нормир. |
Целевой |
Допустимое |
Допустимое |
|
|
Ячейка |
Имя |
значение стоимость Коэффициент Увеличение Уменьшение |
||||
|
|
$B$3 |
значениеблочный |
20 |
0 |
5 |
1 |
|
|
|
$C$3 |
значениепанельный |
0 |
-2 |
7 |
2 |
|
|
|
$D$3 |
значениекирпичный |
0 |
-4 |
6 |
4 |
|
|
|
$E$3 |
значениемонолитный |
20 |
0 |
9,5 |
0,5 |
|
Ограничения |
|
|
|
|
|
|||
|
|
|
|
Результ. |
Теневая |
Ограничение |
Допустимое |
Допустимое |
|
|
Ячейка |
Имя |
значение |
Цена |
Праваячасть Увеличение Уменьшение |
||
|
|
$F$7 |
электроэнергияЦФ |
40 |
0 |
100 |
1E+30 |
|
|
|
$F$8 |
трудовыересурсы ЦФ |
60 |
4,5 |
60 |
20 |
|
|
|
$F$9 |
железобетонныеизделияЦФ |
300 |
0 |
310 |
1E+30 |
|
|
|
$F$10 |
кирпичЦФ |
200 |
0,1 |
200 |
3,333333333 |
|
|
|
$F$11 |
пиломатериалы ЦФ |
40 |
0 |
150 |
1E+30 |
|
7
ОТЧЕТ ПО ПРЕДЕЛАМ РЕШЕНИЯ
Целевое
Ячейка Имя значение
$F$4 прибыльЦФ |
290 |
Изменяемое Ячейка Имя значение
$B$3 |
значениеблочный |
20 |
$C$3 |
значениепанельный |
0 |
$D$3 |
значениекирпичный |
0 |
$E$3 |
значениемонолитный |
20 |
Нижний |
Целевое |
|
Верхний |
Целевое |
предел результат |
|
предел |
результат |
|
0 |
190 |
|
20 |
290 |
0 |
290 |
|
0 |
290 |
0 |
290 |
|
0 |
290 |
0 |
100 |
|
20 |
290 |
8
ФОРМИРОВАНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ
•Если в прямой задаче ищут максимум функции, в
двойственной – минимум и наоборот.
•Коэффициенты при переменных в линейной (целевой) функции одной задачи являются свободными членами
системы ограничений в другой.
•Меняются знаки ограничений: неравенства вида <= заменяются на неравенства вида >= и наоборот.
•Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.
ai, j dj,i
9
СВОЙСТВА ДВОЙСТВЕННЫХ ЗАДАЧ
•Число неравенств в системе ограничений в прямой задаче
совпадает с числом переменных в двойственной задаче.
•Условия неотрицательности переменных имеются в обеих задачах.
•Оптимальные решения прямой и двойственной задач совпадают.
•Симметричность прямой и двойственной задач заключается в том, что значения теневой цены в прямой задаче совпадают с решением двойственной и наоборот.
10