Учебное пособие 800519
.pdfРезультат представлен в табл. 7.3.2.
|
|
|
Таблица 7.3.2 |
|
|
|
|
|
|
Вариант j |
0 |
1 |
2 |
|
|
|
|
|
|
Tj |
0 |
3 |
6 |
|
Rj |
0 |
1 |
3 |
|
Sj |
0 |
6 |
7 |
|
2 шаг. Рассматриваем переменные х3 и х4. Решение приведено в табл. 7.3.3.
Таблица 7.3.3
|
1 |
|
|
|
|
|
|
|
|
3;1;4 |
|
|
|
|
|
|
|
5;3;9 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
0;0;0 |
|
|
|
|
|
|
|
2;2;5 |
|
|
|
|
|||||
|
4 |
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
||
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
Результат представлен в табл. 7.3.4. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7.3.4 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вариант j |
|
|
|
0 |
|
|
|
|
|
1 |
|
|
2 |
|
|
|
3 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tj |
|
|
|
0 |
|
|
|
|
|
2 |
|
|
3 |
|
|
|
5 |
|
|
|
||||
|
|
|
Rj |
|
|
|
0 |
|
|
|
|
|
2 |
|
|
1 |
|
|
|
3 |
|
|
|
||||
|
|
|
Sj |
|
|
|
0 |
|
|
|
|
|
5 |
|
|
4 |
|
|
|
9 |
|
|
|
||||
3 шаг. Рассматриваем |
объединенную |
|
переменную y2 и |
переменную х5. |
|||||||||||||||||||||||
Решение приведено в табл. 7.3.5. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7.3.5 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
1 |
|
|
4;2;2 |
|
|
|
6;4;7 |
|
|
|
|
7;3;6 |
|
|
|
- |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
0 |
|
|
0;0;0 |
|
|
|
2;2;5 |
|
|
|
|
3;1;4 |
|
|
|
5;3;9 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
5 |
|
|
0 |
|
|
|
1 |
|
|
|
|
2 |
|
|
|
3 |
|
|
|
|||||
|
|
(3,4) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Результаты сведены в табл. 7.3.6. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7.3.6 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
Вариант j |
|
0 |
|
|
1 |
|
|
2 |
|
3 |
|
4 |
|
|
5 |
|
6 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
Tj |
|
|
0 |
|
|
2 |
|
|
3 |
|
4 |
|
5 |
|
|
6 |
|
7 |
|
|
|
|||
|
|
|
Rj |
|
|
0 |
|
|
2 |
|
|
1 |
|
2 |
|
3 |
|
|
4 |
|
3 |
|
|
|
|||
|
|
|
Sj |
|
|
0 |
|
|
5 |
|
|
4 |
|
2 |
|
9 |
|
|
7 |
|
6 |
|
|
|
181
4 шаг. Рассматриваем объединенные переменные y1 и y3. Решение приведено в табл. 7.3.7.
Таблица 7.3.7
2 |
|
6;3;7 |
- |
9;4;11 |
- |
- |
- |
- |
|
|
|
|
|
|
|
|
|
1 |
|
3;1;6 |
5;3;11 |
6;2;10 |
7;3;8 |
8;4;15 |
- |
10;4;12 |
0 |
|
0;0;0 |
2;2;5 |
3;1;4 |
4;2;2 |
5;3;9 |
6;4;7 |
7;3;6 |
|
|
|
|
|
|
|
|
|
y1 |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
y3 |
|||||||
|
|
|
|
|
|
|
|
Оптимальное решение определяется клеткой (8;4;15). Ему соответствует решение(0,1,1,1,0). Однако это решение является не допустимым. Проводим ветвление по проблемному варианту 1 первого шага, то есть по переменной x2.
Оценка первого подмножества (х2=1).
Если х2=1, то таблица четвертого шага принимает вид (табл. 7.3.8).
Таблица 7.3.8
2 (6;3;7) |
6;3;7 |
- |
9;4;11 |
- |
- |
- |
- |
|
|
|
|
|
|
|
|
1 (3;2;6) |
3;2;6 |
5;4;11 |
6;3;10 |
7;4;8 |
- |
- |
- |
|
|
|
|
|
|
|
|
y1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
y3 |
0;0;0 |
2;2;5 |
3;1;4 |
4;2;2 |
5;3;9 |
6;4;7 |
7;3;6 |
Оптимальное решение определяется клеткой (9;4;11) и (5;4;11) с оценкой 11.
Оценка второго подмножества (х2=0).
Если х2=0, то таблица четвертого шага принимает вид (табл. 7.3.9).
Таблица 7.3.9
1 |
|
3;1;1 |
5;3;6 |
6;2;5 |
7;3;3 |
8;4;10 |
- |
10;4;7 |
|
|
|
|
|
|
|
|
|
0 |
|
0;0;0 |
2;2;5 |
3;1;4 |
4;2;2 |
5;3;9 |
6;4;7 |
7;3;6 |
|
|
|
|
|
|
|
|
|
y1 |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
y3 |
|||||||
|
|
|
|
|
|
|
|
Оптимальное решение определяется клеткой (8;4;10) с оценкой 10. Выбираем первое подмножество. Ему соответствуют два решения
х1=(1,1,0,0,1) и х2=(0,1,1,0,0). Второе решение является допустимым и, следовательно, оптимальным.
7.4.Задача оптимальной застройки района по критерию прибыли
Рассматриваются задачи оптимальной застройки района по критерию прибыли.
Имеем n участков возможного строительства и m типов домов. Задача состоит в выборе числа домов каждого типа, обеспечивающих максимальную прибыль от продажи квартир.
182
Стоимость строительства домов i-го типа Сi(хi), зависит от числа xiдомов
i-го типа, |
включенных в план застройки, и является вогнутой функцией |
0 xi bi |
. Имеются n участков для строительства домов. Строительство дома |
i-го типа на участке j требует дополнительных затрат ij. Известно количество Si жилой площади домов i-го типа и рыночная цена рi 1м2 жилой площади домовi-го типа. Обозначим уij=1, если на j-м участке строится дом i–го типа и
уij=0 в противном случае, i 1,m, j 1,n .
Прибыль от продажи квартир xi |
yij |
домов i -го типа равна |
|
||||||||||
|
|
|
|
|
|
|
j |
|
|
|
|
||
Qi pisi xi ijyij Ci (xi ) , |
|
(7.4.1) |
|||||||||||
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Задача. Определим {yij}, i 1,m, j 1,n максимизирующие |
|
||||||||||||
Q (pisi |
|
|
|
|
|
|
|
|
|
|
|
|
|
ij )yij ci |
yij |
(7.4.2) |
|||||||||||
i,j |
|
|
|
|
|
|
i |
|
j |
|
|
||
при ограничениях |
|
|
|
|
|
|
|
|
|
|
|
|
|
yij |
|
|
|
|
|
|
|
|
|
||||
1, |
j 1,n , |
|
|
|
(7.4.3) |
||||||||
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
yij bi , |
|
|
|
|
|
|
|||||||
i 1,m . |
|
|
(7.4.4) |
||||||||||
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
В линейном случае Ci (xi ) qi xi |
и (2) принимает вид |
|
|||||||||||
Q tij yij , |
|
|
|
(7.4.5) |
|||||||||
|
i ,j |
|
|
|
|
|
|
|
|
|
где
tij pisi ij qi .
В этом случае задача является частным случаем транспортной задачи.
|
|
7.4.1. Метод решения |
|
||||
Применим |
для |
решения |
задачи |
метод |
дихотомического |
||
|
|
||||||
программирования. Пусть ij i , |
i |
1,m |
. Тогда имеет место теорема. |
Теорема 7.4.1.1. Существует оптимальное решение, в котором из числа проектов, включенных в план, не более одного проекта включено с числом домов менее bi.
Доказательство. Если ij i , то
i yij i
i,j |
i |
независимо от величины yij. Без учета i (7.4.2) принимает вид
Q(x) pisi xi Ci (xi ) , |
(7.4.1.1) |
i
так как Сi(хi) вогнутые функции, то
183
i pisi xi Ci (xi )
выпуклые функции. Задача максимизации суммы выпуклых функций при
ограничениях 0 xi |
bi , |
|
|
|
xi |
n не является задачей выпуклого |
i 1,m, |
||||||
|
|
|
|
|
i |
|
программирования. В этом случае максимум достигается в крайних (угловых) точках множества ограничений. Это доказывает теорему.
Теперь можно применить подход для решения задачи минимизации стоимости строительства. А именно, предполагаем, что проект j является тем проектом, который будет включен в план с числом домов менее чем bi.
Исключаем этот проект и решаем задачу определения |
zi {0;1}, |
i j , |
||||
максимизирующих |
|
|
|
|
|
|
|
|
Dj (x) di zi , |
|
(7.4.1.2) |
||
|
|
|
i j |
|
|
|
где |
|
|
|
|
|
|
|
|
di |
sipibi |
|
|
|
при ограничении |
|
|
|
|
|
|
|
|
zibi |
t , 0 t n, |
(7.4.1.3) |
||
|
|
i j |
|
|
|
|
Это классическая задача о ранце, эффективно решаемая при |
||||||
целочисленных |
значениях |
параметров |
методом |
дихотомического |
||
программирования. |
|
|
|
|
|
|
Обозначим Bj(t) оптимальное значение Dj(x) как функцию t. |
||||||
Минимальная величина затрат определяется выражением |
|
|
||||
|
Dj (n) max[Bj (t) Sj (n t)]. |
(7.4.1.4) |
||||
|
|
t |
|
|
|
|
Число t, на котором достигается минимум (7.4.1.4), определяет количество домов j-го типа.
Решая задачу для всех значений j и выбирая лучшее решение, получаем оптимальное решение задачи.
Пример 7.4.1.1. Имеются четыре проекта, данные о которых приведены в табл. 7.4.1.1. В клетках указаны значения φi(xi).
Таблица 7.4.1.1
|
хi |
1 |
2 |
3 |
4 |
5 |
pi |
di |
i |
|
|||||||
|
|
|
|
|
|
|
|
|
1 |
|
1 |
4 |
7 |
10 |
15 |
6 |
30 |
2 |
|
-1 |
2 |
7 |
14 |
- |
8 |
32 |
3 |
|
-1 |
2 |
7 |
12 |
|
7 |
28 |
4 |
|
1 |
6 |
12 |
19 |
28 |
10 |
50 |
Примем n=11.
I. Исключаем проект 4.
1 шаг. Рассматриваем проекты 1 и 2. Решение приведено в табл. 7.4.1.2.
184
Таблица 7.4.1.2
1 |
|
4;32 |
9;62 |
0 |
|
0;0 |
5;30 |
2 |
|
0 |
1 |
|
1 |
||
|
|
|
Первое число в клетках это количество домов, а второе прибыль. Вариант (5; 30) исключаем, поскольку он доминируется вариантом (4; 32) (при меньшем числе домов получаем большую прибыль).
Результаты приведены в табл. 7.4.1.3.
Таблица 7.4.1.3
Вариант |
0 |
1 |
2 |
Число домов |
0 |
4 |
9 |
Прибыль |
0 |
32 |
62 |
2 шаг. Рассматриваем объединенный проект (1,2) и проект 3. Решение приведено в табл. 7.4.1.4
Таблица 7.4.1.4
1 |
4;28 |
8;60 |
- |
|
0 |
0;0 |
4;32 |
9;62 |
|
3 |
0 |
1 |
2 |
|
(1,2) |
||||
|
|
|
Зависимость B4(t) приведена в табл. 7.4.1.5 ( 6 t 11).
Таблица 7.4.1.5
t |
8 |
9 |
B4(t) |
60 |
62 |
Вычисляем:
D4 (n) max 60 19; 62 12 79 .
Имеем t4=2 дома.
II. Исключаем проект 1.
1 шаг. Рассматриваем проекты 3 и 4. Решение приведено в табл. 7.4.1.6.
Таблица 7.4.1.6
1 |
|
5;50 |
9;78 |
0 |
|
0;0 |
4;28 |
4 |
|
0 |
1 |
|
3 |
||
|
|
|
Результаты сведены в табл. 7.4.1.7.
185
Таблица 7.4.1.7
Вариант |
0 |
1 |
2 |
3 |
Число домов |
0 |
4 |
5 |
9 |
Прибыль |
0 |
28 |
50 |
78 |
2 шаг. Рассматриваем объединенный проект (3,4) и проект 2. Решение приведено в табл. 7.4.1.8.
Таблица 7.4.1.8
1 |
4;32 |
8;60 |
9;82 |
- |
|
0 |
0;0 |
4;28 |
5;50 |
9;78 |
|
2 |
0 |
1 |
2 |
3 |
|
(3,4) |
|||||
|
|
|
|
Зависимость B1(t) 6 t 11 приведена в табл. 7.4.1.9.
Таблица 7.4.1.9
t |
8 |
9 |
Dj(t) |
60 |
82 |
Вычисляем:
D1 (n) max( 60 7;82 4) 86 .
Имеем t1=2 дома.
III. Исключаем проект 3.
Рассматриваем объединенный проект (1,2) табл. 7.4.1.3 и проект 4. Решение приведено в табл. 7.4.1.10.
Таблица 7.4.1.10
1 |
5;50 |
9;82 |
- |
|
0 |
0;0 |
4;32 |
9;62 |
|
4 |
0 |
1 |
2 |
|
(1,2) |
||||
|
|
|
Зависимость B3(t) 6 t 1 имеет вид B3(9)=82. Вычисляем: D3 (n) 82 2 84 .
IV. Исключаем проект 2.
Рассматриваем объединенный проект (3,4) и проект 1. Решение приведено в табл. 7.4.1.11.
Таблица 7.4.1.11
1 |
5;30 |
9;58 |
10;80 |
- |
|
0 |
0;0 |
4;28 |
5;50 |
9;78 |
|
1 |
0 |
1 |
2 |
3 |
|
(3,4) |
|||||
|
|
|
|
||
|
|
186 |
|
|
Зависимость B2(t) 6 t 1 имеет видB2(9)=78, B2(10)= 80.
Вычисляем: D2 (n) max( 78 2;80 1) 80 .
Сравнивая все 4 варианта, определяем оптимальный вариант II, согласно которому в план включаются проекты 2 и 4 с максимальным количеством домов и проект 1 с двумя домами.
7.4.2.Метод ветвей и границ
Ксожалению, в случае произвольных ij, теорема 7.4.1.1 не имеет смысла. Поэтому можно применить либо метод дихотомического
программирования для всех возможных значений xi bi , |
|
|
|
i 1,m либо метод |
|||
ветвей и границ. |
|
|
|
Рассмотрим применение метода ветвей и границ. |
Пусть в результате |
ветвления (разбиение множества решений на подмножества) получено подмножество, в котором
di xi Di .
Для получения нижней оценки этого подмножества решается следующая транспортная задача:
|
Q(y) tijyij max , |
(7.4.2.1) |
|||||||||||||||||||
|
|
|
|
|
|
|
i ,j |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
yij |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
1, j 1,m, |
(7.4.2.2) |
|||||||||||||||||||
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
yij Di , i |
|
|
, |
|
(7.4.2.3) |
||||||||||||||
|
di |
1,n |
|||||||||||||||||||
|
|
|
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|||
где |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
tij aij |
qi [di Di ], i 1,n, j 1,m , |
|||||||||||||||||||
|
|
|
|
|
|
|
Ci (Di ) Ci (di ) |
|
|
|
|||||||||||
|
q |
[d |
D |
] |
, i 1,n . |
||||||||||||||||
|
|
||||||||||||||||||||
|
i |
|
i |
|
i |
|
|
|
Di di |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
Обозначим |
Q[di Di ] |
значение |
(7.4.2.1) в |
оптимальном решении этой |
|||||||||||||||||
задачи. Величина |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Q(di Di ) aiqi |
Ci (ai ) . |
(7.4.2.4) |
||||||||||||||||||
Является нижней оценкой для подмножества решений, удовлетворяющих |
|||||||||||||||||||||
|
|
|
|
|
|
|
|||||||||||||||
условиям di xi |
Di , |
i 1,n . Для |
решения |
оценочной задачи опишем |
модификацию алгоритма решения задачи о назначениях, описанной в [41]. Дадим иллюстрацию алгоритма на простом примере.
Пример 7.4.2.1. Имеются три проекта, данные о параметрах аij и pisi приведены в табл. 7.4.2.1.
Примем n=11.
187
Таблица 7.4.2.1
|
d |
1 |
2 |
3 |
4 |
pisi |
i |
|
|||||
|
|
|
|
|
|
|
1 |
|
9 |
8 |
7 |
8 |
10 |
2 |
|
5 |
7 |
7 |
6 |
9 |
3 |
|
6 |
5 |
6 |
4 |
7 |
Значения функции Сi(xj), приведены в табл.7.4.2.2.
Таблица 7.4.2.2
|
xi |
1 |
2 |
3 |
qi |
i |
|
||||
|
|
|
|
|
|
1 |
|
7 |
8 |
9 |
3 |
2 |
|
6 |
7 |
8 |
2 2/3 |
3 |
|
5 |
7 |
9 |
3 |
Предварительный шаг.
Вычисляем:
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
max (ai1 |
qi |
) max 9 |
3;5 2 |
|
|
|
;6 |
3 |
6, y11 |
1. |
||||||
|
3 |
|
|||||||||||||||
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
max (ai 2 |
qi |
) max 8 |
3;7 2 |
|
|
|
;5 |
3 |
6, y12 |
1. |
||||||
|
3 |
|
|||||||||||||||
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
1 |
|
|
|||
|
max (ai3 |
qi |
) max 7 |
3;7 2 |
|
|
|
;6 |
3 |
4 |
|
|
, y23 1. |
||||
|
3 |
3 |
|||||||||||||||
|
i |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
max (ai 4 |
qi |
) max 8 |
3;6 2 |
|
|
|
;4 |
3 |
5, y14 |
1 . |
||||||
|
3 |
|
|||||||||||||||
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Имеем |
x1 3, x2 1, x3 0. |
|
|
|
|
|
|
|
|
|
|
|
|||||
Оценка Q равна |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Q 6 5 4 |
1 |
5 20 |
1 |
. |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
3 |
|
|
|
|
3 |
|
|
|
|
|
1 шаг. Проводим ветвление по проекту 2. Оценка первого подмножества (х2=0). Вычисляем:
y11 1, y12 1, y33 1, y14 1, x1 3, x3 1.
Оценка:
Q 6 5 3 5 19 .
Оценка второго подмножества (х2≥1) q2(1,3)=1. Вычисляем:
y11 1, y22 1, y23 1, y24 1, x1 1, x2 3.
Оценка:
Q(x2 1) 23 16 17 .
Выбираем первое подмножество.
188
2 шаг. Проводим ветвление по проекту 3. Оценка первого подмножества (х2=0; х3=0). Допустимого решения не существует.
Оценка второго подмножества (х2=0; х3≥1) q3(1,3)=2. Вычисляем:
y11 1, y12 1, y33 1, y14 1, x1 3, x2 1.
Оценка:
Q(x2 0; x3 1) 20 3 17 .
Это решение является допустимым и следовательно, оптимальным.
3 шаг. Для проверки существования других оптимальных решений выбираем подмножество (х2≥1). Проводим ветвление по проекту 1.
Оценка первого подмножества (х2≥1; х1=0). Вычисляем:
y41 1, y22 1, y23 1, y24 1, x2 3, x4 1.
Оценка:
Q(x2 1; x1 0) 17 1 6 12 .
Оценка второго подмножества (х2≥1; х1≥1) q1(1,3)=1. Вычисляем:
y11 1, y12 1, y23 1, y14 1.
Оценка
Q(x2 0; x1 1) 28 2 13 17 .
Это решение является допустимым и, следовательно, также оптимальным.
Врезультате получаем два оптимальных решения:
1)y11 1, y12 1, y33 1, y14 1, x1 3, x3 1;
2)y11 1, y12 1, y23 1, y14 1, x1 3, x2 1.
Дерево ветвлений приведено на рис. 7.4.2.1.
|
х2=0 |
201/3 |
х2≥1 |
|
|
|
|
|
|
|
19 |
|
|
17 |
|
|
|
|
|
х3=0 |
|
х3≥1 |
х1=0 |
х1≥1 |
|
|
|
||
|
|
|
|
|
-∞ |
|
17 |
12 |
17 |
|
|
|
Рис.7.4.2.1
189
7.4.3. Приближенный алгоритм
Решение задачи методом ветвей и границ может привести к большому объему вычислений за счет большого числа ветвлений и необходимости решать задачи транспортного типа для получения нижних оценок.
Рассмотрим приближенный алгоритм решения задачи. Для этого заметим, что, как правило, стоимость проекта существенно превышает затраты на привязку проекта к конкретному земельному участку. Поэтому сначала решаем задачу по критерию максимизация прибыли без учета дополнительных затрат ij. После получения оптимального решения xo решается задача минимизации
|
|
|
|
|
|
|
|
|
|
|
|
дополнительных затрат, то есть задача определения yij, |
i 1,m, |
j |
1,n |
, |
|||||||
минимизирующих |
|
|
|
|
|
|
|
|
|
|
|
|
ijyij |
|
|
|
(7.4.3.1) |
||||||
|
i ,j |
|
|
|
|
|
|
||||
при ограничениях |
|
|
|
|
|
|
|
|
|
|
|
yij |
|
|
|
|
|
|
|
|
|
||
1, j 1,n , |
|
|
|
(7.4.3.2) |
|||||||
i |
|
|
|
|
|
|
|
|
|
|
|
yij |
|
|
|
|
|
|
|
||||
xoi , i 1,m . |
|
|
|
(7.4.3.3) |
|||||||
j |
|
|
|
|
|
|
|
|
|
|
|
Это классическая транспортная задача.
Пример 7.4.3.1. Рассмотрим задачу с данными примера 7.4.1.1. Применяя метод дихотомического программирования, получаем оптимальное решение без дополнительных затрат
x1 3, x2 1, x3 0, Q 24 .
Значения ij приведены в табл.7.4.3.1
Таблица 7.4.3.1
|
j |
1 |
2 |
3 |
4 |
i |
|
||||
|
|
|
|
|
|
1 |
|
1 |
2 |
3 |
2 |
2 |
|
4 |
2 |
2 |
3 |
3 |
|
1 |
2 |
1 |
3 |
Решаем транспортную задачу. Ее оптимальное решение
y11 1, y12 1, y14 1, y23 1.
Дополнительные затраты равны 7. Прибыль составляет 24-7=17, что совпадает с предшествующим решением. Приведенные вычислительные эксперименты показали, что предложенный приближенный алгоритм в 90 % случаях давал оптимальное решение, а средняя относительная ошибка не превышала 3 % при условии, что доля дополнительных затрат была не более 10 % от стоимости проекта.
190