Учебное пособие 800519

Результат представлен в табл. 7.3.2.

2 шаг. Рассматриваем переменные х3 и х4. Решение приведено в табл. 7.3.3.

Таблица 7.3.3

181

4 шаг. Рассматриваем объединенные переменные y1 и y3. Решение приведено в табл. 7.3.7.

Таблица 7.3.7

Оптимальное решение определяется клеткой (8;4;15). Ему соответствует решение(0,1,1,1,0). Однако это решение является не допустимым. Проводим ветвление по проблемному варианту 1 первого шага, то есть по переменной x2.

Оценка первого подмножества (х2=1).

Если х2=1, то таблица четвертого шага принимает вид (табл. 7.3.8).

Таблица 7.3.8

Оптимальное решение определяется клеткой (9;4;11) и (5;4;11) с оценкой 11.

Оценка второго подмножества (х2=0).

Если х2=0, то таблица четвертого шага принимает вид (табл. 7.3.9).

Таблица 7.3.9

Оптимальное решение определяется клеткой (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-го типа на участке j требует дополнительных затрат ij. Известно количество Si жилой площади домов i-го типа и рыночная цена рi 1м2 жилой площади домовi-го типа. Обозначим уij=1, если на j-м участке строится дом i–го типа и

уij=0 в противном случае, i 1,m, j 1,n .

где

tij pisi ij qi .

В этом случае задача является частным случаем транспортной задачи.

Теорема 7.4.1.1. Существует оптимальное решение, в котором из числа проектов, включенных в план, не более одного проекта включено с числом домов менее bi.

Доказательство. Если ij i , то

i yij i

независимо от величины yij. Без учета i (7.4.2) принимает вид

i

так как Сi(хi) вогнутые функции, то

183

i pisi xi Ci (xi )

выпуклые функции. Задача максимизации суммы выпуклых функций при

программирования. В этом случае максимум достигается в крайних (угловых) точках множества ограничений. Это доказывает теорему.

Теперь можно применить подход для решения задачи минимизации стоимости строительства. А именно, предполагаем, что проект j является тем проектом, который будет включен в план с числом домов менее чем bi.

Число t, на котором достигается минимум (7.4.1.4), определяет количество домов j-го типа.

Решая задачу для всех значений j и выбирая лучшее решение, получаем оптимальное решение задачи.

Пример 7.4.1.1. Имеются четыре проекта, данные о которых приведены в табл. 7.4.1.1. В клетках указаны значения φi(xi).

Таблица 7.4.1.1

Примем n=11.

I. Исключаем проект 4.

1 шаг. Рассматриваем проекты 1 и 2. Решение приведено в табл. 7.4.1.2.

184

Таблица 7.4.1.2

Первое число в клетках это количество домов, а второе прибыль. Вариант (5; 30) исключаем, поскольку он доминируется вариантом (4; 32) (при меньшем числе домов получаем большую прибыль).

Результаты приведены в табл. 7.4.1.3.

Таблица 7.4.1.3

2 шаг. Рассматриваем объединенный проект (1,2) и проект 3. Решение приведено в табл. 7.4.1.4

Таблица 7.4.1.4

Зависимость B4(t) приведена в табл. 7.4.1.5 ( 6 t 11).

Таблица 7.4.1.5

Вычисляем:

D4 (n) max 60 19; 62 12 79 .

Имеем t4=2 дома.

II. Исключаем проект 1.

1 шаг. Рассматриваем проекты 3 и 4. Решение приведено в табл. 7.4.1.6.

Таблица 7.4.1.6

Результаты сведены в табл. 7.4.1.7.

185

Таблица 7.4.1.7

2 шаг. Рассматриваем объединенный проект (3,4) и проект 2. Решение приведено в табл. 7.4.1.8.

Таблица 7.4.1.8

Зависимость B1(t) 6 t 11 приведена в табл. 7.4.1.9.

Таблица 7.4.1.9

Вычисляем:

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

Зависимость 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

Зависимость 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 не имеет смысла. Поэтому можно применить либо метод дихотомического

ветвления (разбиение множества решений на подмножества) получено подмножество, в котором

di xi Di .

Для получения нижней оценки этого подмножества решается следующая транспортная задача:

модификацию алгоритма решения задачи о назначениях, описанной в [41]. Дадим иллюстрацию алгоритма на простом примере.

Пример 7.4.2.1. Имеются три проекта, данные о параметрах аij и pisi приведены в табл. 7.4.2.1.

Примем n=11.

187

Таблица 7.4.2.1

Значения функции Сi(xj), приведены в табл.7.4.2.2.

Таблица 7.4.2.2

Предварительный шаг.

Вычисляем:

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.

Рис.7.4.2.1

189

7.4.3. Приближенный алгоритм

Решение задачи методом ветвей и границ может привести к большому объему вычислений за счет большого числа ветвлений и необходимости решать задачи транспортного типа для получения нижних оценок.

Рассмотрим приближенный алгоритм решения задачи. Для этого заметим, что, как правило, стоимость проекта существенно превышает затраты на привязку проекта к конкретному земельному участку. Поэтому сначала решаем задачу по критерию максимизация прибыли без учета дополнительных затрат ij. После получения оптимального решения xo решается задача минимизации

Это классическая транспортная задача.

Пример 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

Решаем транспортную задачу. Ее оптимальное решение

y11 1, y12 1, y14 1, y23 1.

Дополнительные затраты равны 7. Прибыль составляет 24-7=17, что совпадает с предшествующим решением. Приведенные вычислительные эксперименты показали, что предложенный приближенный алгоритм в 90 % случаях давал оптимальное решение, а средняя относительная ошибка не превышала 3 % при условии, что доля дополнительных затрат была не более 10 % от стоимости проекта.

190