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

Оптимальное решение определяется путем максимальной длины. Этот прежний путь длины 15.

Оценка второго подмножества.

Если х4=0, то путь максимальной длины [(0;0); (2;3); (3;5); (4;5); (5;9)] с

длиной 13. Выбираем первое подмножество (х4=1). Теперь для ветвления берем проблемную вершину (2;3), то есть переменную х2.

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

Если х2=1 , то путь кратчайшей длины в вершину (4;8) будет равен 6>5. Поэтому дугу [(2;3); (3;5)] исключаем. Путь максимальной длины

[(0;0); (1;0); (2;3); (3;3); (4;6); (5;0)] с длиной 12.

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

Путь максимальной длины [(0;0); (1;0); (2;0); (3;2); (4;5); (5;9)] с длиной 11.

Теперь выбираем подмножество (х4=0) с максимальной оценкой 13. Соответствующее решение х=(0,1,1,0,1) удовлетворяет ограничению (7.1.2) и поэтому является оптимальным. Дерево ветвлений приведено на рис. 7.1.6.

В данном случае число ветвлений равно 2. В общем случае число ветвлений не превышает числа 2q, где q − число проблемных вершин.

Рис. 7.1.6

Получим нижнюю оценку для задачи (7.1.1)-(7.1.3). Для этого на сети рис. 7.1.4 ищем пути не минимальной, а максимальной длины в каждую вершину

Если длина максимального пути превышает 5, то соответствующая дуга удаляется. В нашем примере это дуга [(3;5); (4;8)] .

Эта сеть содержит только допустимые пути, то есть пути, которым соответствуют решения, удовлетворяющие обоим неравенствам. Определяем в этой сети пути максимальной длины, беря в качестве длин дуг коэффициенты целевой функции (7.1.5) (рис. 7.1.8). Определяя пути максимальной длины в этой сети, получаем решение х=(0,1,1,0,1), которое является оптимальным. Однако это не всегда так, поскольку сеть может содержать не все допустимые пути.

Рис. 7.1.8

Рассмотренный алгоритм, естественно, обобщается на случай, когда хi принимает значения не только 0 или 1, а любые целочисленные значения на отрезке [0; bi ], i 1,n . В этом случае просто несколько усложняется построение

Определяем кратчайшие пути в сети (рис. 7.1.9) при длинах дуг, равных tiхi неравенства (7.1.7). Сеть не изменилась.

172

Рис.7.1.9

Пусть целевая функция имеет вид

x1 2x2 5x3 6x4 3x5 .

Определим путь максимальной длины в сети при длинах дуг, равных siхi

(рис. 7.1.10).

Однако соответствующее решение х=(0,0,0,1,1) не удовлетворяет неравенству (7.1.7). Поэтому применим метод ветвей и границ. Для ветвления выбираем проблемную вершину (4;7), то есть переменную х4.

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

Если х4=1, то дугу [(4;7); (5;8)] следует исключить из сети. Теперь путь максимальной длины [(1;0); (2;0); (3;0); (4;7); (5;7)]длины 6. На этом пути нет

173

проблемных вершин. Поэтому соответствующее решение х=(0,0,0,1,0) является оптимальным в этом подмножестве.

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

Путь максимальной длины [(1;0); (2;0); (3;5); (4;5); (5;6)] с длиной 8. Этот

путь также не имеет проблемных вершин. Поэтому соответствующее решение х=(0,0,1,0,1) является оптимальным в данном подмножестве.

Выбираем второе подмножество. Оптимальное решение х=(0,0,1,0,1) с величиной целевой функции 8.

7.2. Табличный метод допустимых решений

Можно не строить сеть ВДР, а использовать табличный способ вычислений.

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

Таблица 7.2.1

Поясним эту таблицу. Первое число в каждой клетке − это сумма соответствующих величин ti, второе – сумма соответствующих величин сi,а третье − сумма соответствующих величин si. Результаты представим в виде табл. 7.2.2.

Таблица 7.2.2

Поясним эту таблицу. У клеток (0,1) и (1,0) первые числа совпадают. Поэтому второе число в варианте 1 равно минимальному из вторых чисел этих клеток, а третье – максимальному.

2 шаг. Рассматриваем объединенную переменную y1=(х1,х2)и переменнуюх3. Решение приведено табл. 7.2.3.

Таблица 7.2.3

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

Определяем клетку с максимальным третьим числом. Это клетка (8;5;15). Соответствующее решение не является допустимым. Поэтому применяем метод ветвей и границ. Для ветвления, как и ранее, берем переменную х4.

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

Поскольку х4=1, то следует рассмотреть задачу с четырьмя переменными при ограничениях N=6 иС=3. Первый шаг остается без изменений. На втором шаге

175

исключается вариант 5, поскольку Т=8>6, а С=5>3. Рассматриваем объединенную переменную y1=(х1,х2,х3)и переменнуюх5. Решение приведено в табл. 7.2.8.

Таблица 7.2.8

Достаточно на четвертом шаге вместо второй строчки подставить вторую строчку из третьего шага, поскольку х4=0. Решение приведено в табл. 7.2.9.

Таблица 7.2.9

Оптимальное решение определяется клеткой (9;4;13) с величиной жилой площади 13.

Выбираем первое подмножество. Соответствующее решение не допустимо. Для ветвления выбираем вершину 2.

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

Поскольку х4=1 и х2=1, то остаются три переменных. Имеем N=4, С=1. Оптимальное решение определяется сразу: х1=0, х2=1, х3=0, х4=1, х5=1, S=12.

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

Оптимальное решение также сразу определяется х1=0, х2=0, х3=1, х4=1, х5=1 с величиной полезной площади S=11.

Выбираем подмножество х4=0. Ему соответствует решениех1=0, х2=1, х3=1, х4=0, х5=1 с величиной жилой площади 13, которое является оптимальным.

Метод таблиц ВДР в отличие от метода сетей ВДР можно применить для любого сетевого представления ограничений задачи. Как известно, в основе метода дихотомического программирования лежит процедура рассмотрения пар переменных и (или) обобщенных переменных. Опишем основной шаг этой процедуры.

176

Заметим, что вариант 1 является проблемным.

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

Таблица 7.2.11

178

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

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

Таблица 7.2.15

Оптимальное решение определяется клеткой (8;5;15). Ей соответствует решение х=(0,1,1,1,0). Однако оно не удовлетворяет ограничению (7.1.2), поскольку содержит проблемный вариант 1 первого шага. Применим метод ветвей и границ. Ветвление проводим по переменной х2 (можно по х1).

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

Поскольку х2=1, то таблица четвертого шага принимает вид (табл. 7.2.16)

Таблица 7.2.16

Заметим, что клетка (8;6;15) исключена, так как 2+4=6>5. Оптимальное решение определяется клеткой (9;5;13). Это решение х=(0,1,1,0,1) с оценкой 13. Это решение является допустимым и поэтому оптимальным в данном подмножестве.

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

В этом случае таблица четвертого шага принимает вид (табл. 7.2.17)

179

Таблица 7.2.17

Оптимальное решение определяется клеткой (9;5;11) с оценкой 11. Выбираем первое подмножество. Итак, оптимальное решение

х=(0,1,1,0,1) с оценкой 13.

Заметим, что число ветвей в данном случае меньше, чем в рассмотренной выше структуре дихотомического представления. Это и понятно, поскольку число проблемных вариантов в данном случае меньше (всего один проблемный вариант).

7.3.Учет рисков при формировании плана застройки земельного участка

На практике учет рисков, как правило, производится на основе качественных шкал. В частности, в Сбербанке России применяется трехбалльная шкала: 1 – низкий риск, 2 – средний риск, 3 – высокий риск. Примем, что каждый тип домов имеет определенную оценку рискаri, i 1,n . Для учета рисков введем ограничения на суммарный риск варианта застройки

Для решения задачи (7.1.1)-(7.1.3), (7.3.1) применим метод дерева допустимых решений, удовлетворяющих неравенствам (7.1.2) и (7.1.3) и повторим основные шаги алгоритма его построения, заметив параметры ci (вторые числа каждого варианта) на параметры ri. Дадим иллюстрацию алгоритма на данных примера 7.2.2.

Пример 7.3.1. Пусть ограничение (7.3.1) имеет вид

x1 2x2 2x3 x4 2x5 4

(допускается всего один тип домов со средним риском).

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

Таблица 7.3.1