Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

ТЕОРИЯ И МЕТОДЫ СИСТЕМНОГО АНАЛИЗА

Оразбаев Б. Б., Курмангазиева Л. Т., Коданова Ш. К.,

Глава 6. ПРИМЕНЕНИЕ МЕТОДОВ СИСТЕМНОГО АНАЛИЗА НА ПРАКТИКЕ

1. Составление математической модели задачи распределения ресурсов, задачи о диете и задачи о раскрое

1. Мебельная фабрика выпускает столы, стулья, бюро и книжные шкафы. При изготовлении этих товаров используются два вида различных досок, причем фабрика имеет в наличии 1500 м досок 1 типа и 1000 м досок 2 типа. Кроме того, заданы трудовые ресурсы в количестве  800 чел.-ч. В таблице приведены нормативы затрат каждого вида ресурсов на изготовление 1 ед. изделия и прибыль на 1 ед. изделия:

Ресурсы

Затраты на 1 ед. изделия

Столы

Стулья

Бюро

Книжные шкафы

Доски 1 типа, м

Доски 2 типа, м

Трудовые ресурсы, чел.-ч.

5

2

3

1

3

2

9

4

5

12

11

10

Прибыль, тг./шт.

12

5

15

10

Определить оптимальный ассортимент, максимизирующий прибыль.

2. В состав рациона кормления входят три продукта: сено, силос и концентраты, содержащие питательные вещества: белок, кальций и витамины. Содержание питательных веществ (в г на 1 кг) соответствующего продукта питания и минимально необходимые нормы их потребления заданы следующей таблицей:

Продукты

Питательные вещества

Белок

Кальций

Витамины

Сено

Силос

Концентраты

50

20

180

6

4

3

2

1

1

Нормы потребления

2000

120

40

Определить оптимальный рацион кормления из условия минимальной стоимости, если цена 1 кг продукта питания соответственно составляет: сена – 3 тг., силоса – 2 тг. и концентратов – 5 тг.

3. Для изготовления брусьев трех размеров: 0,6 м, 1,5 м и 2,5 м в соотношении 2:1:3 на распил поступают бревна длиной в 3 м. Определить план распила, обеспечивающий максимальное число комплектов.

Методические рекомендации

Контрольный пример 1 (Задача составления кормовой смеси, или задача о диете). Хозяйство птицефермы насчитывает 20 000 цыплят. Недельный расход кормовой смеси составляет 0,5 кг на 1 цыпленка. В рацион входят 3 вида ингредиентов: известняк, зерно, соевые бобы, которые содержат питательные вещества: кальций, белок, клетчатку. В таблице приведены данные, характеризующие содержание (по весу) питательных веществ в каждом из ингредиентов и удельную стоимость каждого ингредиента.

Корм

Содержание питательных веществ (1 кг)

Стоимость 1 кг

кальций

белок

клетчатка

Известняк

0,38

–

–

0,04

Зерно

0,001

0,09

0,02

0,15

Соевые бобы

0,002

0,50

0,08

0,40

Смесь должна содержать:

1) не менее 0,8 %, но не более 1,2 % кальция;

2) не менее 22 % белка;

3) не менее 5 % клетчатки.

Требуется определить количество каждого из 3-х ингредиентов в недельном рационе при условии минимизации его стоимости.

Решение: Введем следующие обозначения: x1 – количество известняка (в кг) в смеси, x2 – количество зерна (в кг) в смеси, x3 – количество соевых бобов (в кг) в смеси.

1. Определим минимальный общий вес смеси, еженедельно расходуемый на кормление 20 000 цыплят: 20 000×0,5 кг = 10 000 кг. Таким образом, общий вес смеси должен быть не менее 10 000 кг, т.е. x1 + x2 + x3 ≥ 10 000.

2. Содержание кальция должно находиться в пределах от 0,008∙(x1 + x2 + x3) до 0,012∙(x1 + x2 + x3). В соответствии с таблицей
исходных данных содержание кальция равно 0,38x1 + 0,001x2 + 0,002x3. Отсюда следует, что ограничения, связанные с содержанием кальция в кормовом рационе можно представить в следующем виде:

а) смесь должна содержать не менее 0,8 % кальция:

0,38x1 + 0,001x2 + 0,002x3 ≥ 0,008∙(x1 + x2 + x3);

б) смесь должна содержать не более 1,2 % кальция:

0,38x1 + 0,001x2 + 0,002x3 ≤ 0,012∙(x1 + x2 + x3).

Эти ограничения запишем в более простой форме:

0,372x1 – 0,007x2 – 0,006x3 ≥ 0;

0,368x1 – 0,011x2 – 0,010x3 ≤ 0.

Аналогичным образом записываем ограничения на содержание в кормовой смеси белка и клетчатки:

0,220x1 + 0,130x2 – 0,280x3 ≤ 0 – содержание белка;

0,050x1 – 0,030x2 – 0,030x3 ≥ 0 – содержание клетчатки.

Таким образом, математическая формулировка задачи может быть представлена в следующем виде:

z = 0,04x1 + 0,15x2 + 0,40x3 → min,

при ограничениях

x1 + x2 + x3 ≥ 10 000 – минимальный недельный рацион;

 – содержание кальция;

0,220x1 + 0,130x2 – 0,280x3 ≤ 0 – содержание белка;

0,050x1 – 0,030x2 – 0,030x3 ≥ 0 – содержание клетчатки,

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

Контрольный пример 2 (Задача о раскрое или минимизации объектов). Продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины – по 20 дециметров. По специальным заказам потребителей фирма поставляет рулоны и других размеров, для чего производится разрезание стандартных рулонов. Данные о заказах на рулоны нестандартных размеров приведены в таблице.

Заказ

Требуемая ширина рулона, дм

Требуемое количество рулонов

1

5

150

2

7

200

3

9

300

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

A = (7, 9, 4 (остаток));

В = (5, 5, 7, 3 (остаток));

С = (5, 5, 9, 1 (остаток)).

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

Решение: Варианты установки режущей кромки запишем в виде следующей таблицы:

Требуемая ширина, дм

Вариант установки кромки

Минимальное
количество
рулонов

1

2

3

4

5

6

5

0

2

2

4

1

0

150

7

1

1

0

0

2

0

200

9

1

0

1

0

0

2

300

Потери на 1 фут длины

4

3

1

0

1

2

 

Обозначим через xj – количество стандартных рулонов, разрезаемых по варианту j . Таким образом, количество рулонов шириной 5 футов = 2x2 + 2x3 + 4x4 + x5, количество рулонов шириной 7 футов = x1 + x2 + 2x5, количество рулонов шириной 9 футов = x1 + x3 + 2x6.

Избыточное количество рулонов будет равно:

Общее выражение для суммарной величины потерь бумаги будет иметь следующий вид:

4x1 + 3x2 + x3 + x5 + 2x6 + 5y1 + 7y2 + 9y3.

Таким образом, математическая модель в общем виде записывается следующим образом:

z = 4x1 + 3x2 + x3 + x5 + 2x6 + 5y1 + 7y2 + 9y3 → min.

при ограничениях:

2x2 + 2x3 + 4x4 + x5 – y1 = 150;

x1 + x2 + 2x5 – y2 = 200;

x1 + x3 + 2x6 – y3 = 300;

xj ≥ 0, yi ≥ 0,

Заключение. Рассмотрены примеры формализации математической модели задач распределения ресурсов, задачи о диете и задачи о раскрое, приведены контрольные примеры решения задач.

Контрольные вопросы

1. Назовите основные классы задач линейного программирования.

2. Приведите примеры практической реализации математической модели задачи о раскрое.

3. Приведите примеры практической реализации математической модели задачи распределения ресурсов.

2. Прямой и двойственный симплекс-методы

Варианты заданий

1. Решить следующие задачи линейного программирования прямым симплекс-методом:

1)

x1 ≥ 0, x2 ≥ 0;

2)

x1 ≥ 0, x2 ≥ 0;

3)

x1 ≥ 0, x2 ≥ 0;

2. Решить следующие задачи линейного программирования двойственным симплекс-методом:

1)

x1 ≥ 0, x2 ≥ 0;

2)

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

Методические рекомендации

Контрольный пример 1. Решить задачу линейного программирования прямым симплекс-методом.

x1 ≥ 0, x2 ≥ 0.

Решение. Переходим к симплекс-таблице

  

–x1

–x2

1

 

y1

=

–3

4

12

 

y2

=

5

4

44

.

y3

=

4

–5

20

 

z

=

–1

–4

0

 

Так все переменные являются несвободными и нет нулевых строк, то сразу переходим к 4 шагу, т.е. к отысканию опорного решения.

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

2-й столбец с отрицательным коэффициентом z-строки выбираем в качестве разрешающего (выбираем максимальный по абсолютной
величине отрицательный коэффициент z-строки). Среди неотрицательных отношений выбираем наименьшее, т.е.

Таким образом, разрешающим элементом будет 4, взятая в рамку. После шага МЖИ получим таблицу

  

–x1

–y1

1

 

x2

=

3

 

y2

=

8

–1

32

.

y3

=

 

z

=

–4

1

12

 

Так как в z-строке есть ещё отрицательный элемент, то столбец, содержащий данный элемент, выбираем в качестве разрешающего. Среди неотрицательных отношений выбираем наименьшее, т.е. Таким образом, разрешающим элементом будет 8, взятая в рамку. После шага МЖИ получим таблицу

  

–y2

–y1

1

 

x2

=

  

6

 

x1

=

  

4

,

y3

=

  

34

 

z

=

28

 

не содержащую отрицательных коэффициентов в z-строке. Следовательно, оптимальное решение найдено: z* = 28, X* = (4, 6).

Контрольный пример 2. Решить задачу линейного программирования прямым симплекс-методом.

x1 ≥ 0, x2 ≥ 0.

Решение. Переходим к симплекс-таблице:

  

–x1

–x2

1

 

y1

=

–11

–3

–51

 

y2

=

–1

–1

–9

.

y3

=

–5

–14

–70

 

z

=

5

3

0

 

Так все переменные являются несвободными и нет нулевых строк, то сразу переходим к 4 шагу, т.е. к отысканию опорного решения.

Нахождение опорного решения (допустимого решения). Так как есть отрицательные свободные члены, то опорное решение ещё не найдено. Рассматриваем 1 строку с отрицательным свободным членом –51 (выбираем максимальный по абсолютной величине отрицательный свободный член). В данной строке есть два отрицательных коэффициента –11 и –3. Берем в качестве разрешающего, например, 1-й столбец. Вычисляем все неотрицательные отношения свободных членов к коэффициентам разрешающего столбца и среди них выбираем наименьшее, т.е. Разрешающей строкой будет 1-я строка, таким образом, разрешающим элементом является –11, взятая в рамку. Выполняем один шаг МЖИ и получим таблицу:

  

–y1

–x2

1

 

x1

=

 

y2

=

,

y3

=

 

z

=

 

в которой есть пока отрицательные свободные члены. Рассматриваем 3 строку с отрицательным свободным членом (выбираем максимальный по абсолютной величине отрицательный свободный член). В данной строке есть два отрицательных коэффициента и  Берем в качестве разрешающего, например, 2-й столбец. Вычисляем все неотрицательные отношения свободных членов к коэффициентам разрешающего столбца и среди них выбираем наименьшее, т.е. Разрешающей строкой будет 3-я строка, таким образом, разрешающим элементом является взятая в рамку. Выполняем один шаг МЖИ и получим таблицу

  

–y1

–y3

1

 

x1

=

 

y2

=

,

x2

=

 

z

=

 

в которой есть отрицательный свободный член во второй строке. Рассматриваем данную строку и выбираем в качестве разрешающего 1-й столбец. Вычисляем все неотрицательные отношения свободных членов к коэффициентам разрешающего столбца и среди них выбираем наименьшее, т.е. Разрешающей строкой будет 2-я строка, а разрешающим элементом является взятая в рамку.

Выполняем один шаг МЖИ и получим таблицу:

  

–y2

–y3

1

 

x1

=

 

y1

=

,

x2

=

 

z

=

 

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

2-й столбец с отрицательным коэффициентом z-строки выбираем в качестве разрешающего. Вычисляем все неотрицательные отношения свободных членов к коэффициентам разрешающего столбца и среди них выбираем наименьшее, т.е.

Разрешающим элементом будет , взятая в рамку. После шага МЖИ получим таблицу

  

–y2

–y1

1

 

x1

=

  

3

 

y3

=

  

29

,

x2

=

  

6

 

z

=

–33

 

не содержащую отрицательных коэффициентов в z-строке. Следовательно, оптимальное решение найдено: z* = 33, X* = (3, 6).

Контрольный пример 3. Решить задачу линейного программирования двойственным симплекс-методом.

x1 ≥ 0, x2 ≥ 0.

Решение. Переходим к симплекс-таблице

  

–x1

–x2

1

 

y1

=

–1

3

6

 

y2

=

3

–1

6

.

z

=

–1

–1

0

 

Так все переменные являются несвободными и нет нулевых строк, то сразу переходим к 4 шагу, т.е. к отысканию оптимального решения.

Нахождение оптимального решения. Так как есть отрицательные коэффициенты в z-строке, то оптимальное решение не найдено. Рассматриваем 1-й столбец с отрицательным коэффициентом в z-строке (выбирается любой столбец с отрицательным коэффициентом z-строки). В данном столбце один положительный элемент 3, следовательно, 2-ю строку, содержащую данный элемент, выбираем в качестве разрешающей. Вычисляем все отрицательные отношения коэффициентов z-строки к коэффициентам разрешающей строки и среди них выбираем наибольшее, т.е. Таким образом, разрешающим элементом является 3, взятая в рамку. Выполняем один шаг МЖИ и получаем таблицу:

  

–y2

–x2

1

 

y1

=

8

 

x1

=

2

.

z

=

2

 

в которой есть пока отрицательные коэффициенты в z-строке. Рассматриваем 2-й столбец и 1-ю строку, содержащую положительный элемент выбираем в качестве разрешающей строки. Вычисляем все отрицательные отношения коэффициентов z-строки к коэффициентам разрешающей строки и среди них выбираем наибольшее, т.е. Таким образом, разрешающим элементом является взятая в рамку. Выполняем один шаг МЖИ и получим таблицу:

  

–y2

–y1

1

 

x2

=

  

3

 

x1

=

  

3

.

z

=

0,5

0,5

6

 

Так как все свободные члены также положительные, то найдено опорное (одновременно оптимальное) решение: z* = 6, X* = (3, 3).

Контрольный пример 4. Решить задачу линейного программирования двойственным симплекс-методом.

x1 ≥ 0, x2 ≥ 0.

Решение. Переходим к симплекс-таблице:

  

–x1

–x2

1

 

y1

=

–3

1

–1

 

y2

=

1

–3

–5

.

z

=

2

1

0

 

Так все переменные являются несвободными и нет нулевых строк, то сразу переходим к 4 шагу, т.е. к отысканию оптимального решения.

Нахождение оптимального решения. Так как z-строке нет отрицательных коэффициентов, то оптимальное решение найдено и переходим к 5 шагу – отысканию опорного (одновременно оптимального) решения.

Строку с отрицательным свободным членом выбираем в качестве разрешающей, например, 1-ю строку. Вычисляем все отрицательные отношения коэффициентов z-строки к коэффициентам разрешающей строки и среди них выбираем наибольшее, т.е. Таким образом, разрешающим элементом является –3, взятая в рамку. Выполняем один шаг МЖИ и получаем таблицу

  

–y1

–x2

1

 

x1

=

 

y2

=

.

z

=

 

в которой есть пока отрицательные свободные члены. В качестве разрешающей строки выбирается 2 строка. Вычисляем все отрицательные отношения коэффициентов z-строки к коэффициентам разрешающей строки и среди них выбираем наибольшее, т.е. Таким образом, разрешающим элементом является взятая в рамку. Выполняем один шаг МЖИ и получим таблицу:

  

–y1

–y2

1

 

x1

=

  

1

 

x2

=

  

2

.

z

=

–4

 

Так как все свободные члены положительные, то найдено опорное (одновременно оптимальное) решение: z* = 4, X* = (1, 2).

Заключение. Рассмотрены примеры решения задачи линейного программирования прямым и двойственным симплекс методом, даны соответствующие методические указания

Контрольные вопросы

1. Какие правила обыкновенных жордановых исключений поменялись местами в модифицированных жордановых исключениях?

2. Назовите правила получения двойственной задачи.

3. Сформулируйте правила выбора разрешающего элемента при нахождении допустимого решения.

3. Транспортная задача

Варианты заданий:

С помощью метода потенциалов решить следующие транспортные задачи:

1)

a1 = 50, a2 = 70, a3 = 40;

b1 = 30, b2 = 60, b3 = 45, b4 = 25;

;

2)

a1 = 115, a2 = 70, a3 = 68;

b1 = 95, b2 = 38, b3 = 50, b4 = 70;

;

3)

a1 = 25, a2 = 20, a3 = 35;

b1 = 30, b2 = 20, b3 = 12, b4 = 18;

;

4)

a1 = 60, a2 = 70, a3 = 20;

b1 = 40, b2 = 30, b3 = 30, b4 = 50;

.

Методические рекомендации

Контрольный пример. С помощью метода потенциалов решить следующую транспортную задачу:

a1 = 25, a2 = 55, a3 = 20;

b1 = 45, b2 = 15, b3 = 20, b4 = 20;

.

Решение.

Составляем следующую таблицу:

 

bj

ai

45

20 0

15

0

20

0

20

0

25

0

9

25

5

0

3

0

10

0

55

35 20

6

20

3

15

8

20

2

0

20

0

3

0

8

0

4

0

8

20

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

1) Составление первоначального (опорного) плана. По правилу северо-западного угла находим

x11 = min {a1, b1} = min {25, 45} = 25, x12 = x13 = x14 = 0.

Вносим изменения в столбец запасов и строку потребления.

Теперь x21 = min {55, 20} = 20, x31 = 0.

При этом потребность первого пункта назначения полностью удовлетворена и обращается в нуль, а запас второго пункта отправления составляет 55 – 20 = 35.

Далее имеем: x22 = min {35, 15} = 15, x32 = 0.

Аналогично x23 = min {20, 20} = 20, x33 = x24 = 0.

Наконец, x34 = min {20, 20} = 20.

Найдем для полученного опорного плана величину транспортных расходов

zоп = 25∙9 + 20∙6 + 15∙3 + 20∙8 + 20∙8 =
= 225 + 120 + 45 + 160 + 160 = 710.

2) Построение системы ui, vj для всех X-выбранных cij. Числа ui и vj определим из системы линейных уравнений

v1 – u1 = 9;

v1 – u2 = 6;

v2 – u2 = 3;

v3 – u2 = 8;

v4 – u3 = 8.

Полагая u1 = 0, найдем v1 = 9, u2 = 3, v2 = 6, v3 = 11, v4 = 8, u3 = 0.

Введем их в таблицу

 

vj

ui

9

6

11

8

0

9

25 –

5

3

 + 

10

3

6

20 + 

3

15

8

20 –

2

0

3

8

4

8

20

3) Исследование построенной системы ui, vj на потенциальность

Если для всех cij, не являющихся X-выбранными, выполняются неравенства vj – ui ≤ cij, то система ui, vj потенциальна. Таким образом, имеем

v2 – u1 = 6 – 0 = 6 > 5; α12 = 6 – 5 = 1;

v3 – u1 = 11 – 0 = 11 > 3; α13 = 11 – 3 = 8;

v4 – u1 = 8 – 0 = 8 < 10;

v4 – u2 = 8 – 3 = 5 > 2; α24 = 5 – 2 = 3;

v1 – u3 = 9 – 0 = 9 > 3; α31 = 9 – 3 = 6;

v2 – u3 = 6 – 0 = 6 < 8;

v3 – u3 = 11 – 0 = 11 > 4; α33 = 11 – 4 = 7.

Следовательно, данная система не потенциальна.

Для всех неравенств, где не выполняются условия, вычисляются αij = vj – ui – cij.

Среди всех αij выбираем наибольшее значение, т.е.

Цикл начинается с клетки с наибольшим значением т.е. с клетки (1, 3), проходит по X-выбранными клеткам и заканчивается в клетке (2, 3). Переходим к общему шагу.

Общий шаг

1) Улучшение плана. Далее находим В клетках отрицательной полуцепи значение xij уменьшается на θ, а в клетках положительной полуцепи значение xij увеличивается на θ.

2) Построение новой системы ui, vj для всех X-выбранных cij. Числа ui и vj определим из системы линейных уравнений

v1 – u1 = 9;

v3 – u1 = 3;

v1 – u2 = 6;

v2 – u2 = 3;

v4 – u3 = 8.

Полагая u1 = u3 = 0, найдем v1 = 9, v3 = 3, u2 = 3, v2 = 6, v4 = 8.

 

vj

ui

9

6

3

8

0

9

5

5

3

20

10

3

6

40 –

3

15

8

2

 + 

0

3

 + 

8

4

8

– 20

3) Исследование построенной системы ui, vj на потенциальность. Таким образом, имеем

v2 – u1 = 6 – 0 = 6 > 5; α12 = 6 – 5 = 1;

v4 – u1 = 8 – 0 = 8 < 10;

v3 – u2 = 3 – 3 = 0 < 8;

v4 – u2 = 8 – 3 = 5 > 2; α24 = 5 – 2 = 3;

v1 – u3 = 9 – 0 = 9 > 3; α31 = 9 – 3 = 6;

v2 – u3 = 6 – 0 = 6 < 8;

v3 – u3 = 3 – 0 = 3 < 4.

Так как система не потенциальна, находим наибольшее значение α, т.е. и строим цикл, начиная с клетки (3,1), проходя по X-выбранными клеткам и заканчивая в клетке (2,1).

Далее находим .

В клетках отрицательной полуцепи значение xij уменьшается на θ, а в клетках положительной полуцепи значение xij увеличивается на θ.

В результате получим следующий улучшенный план:

 

vj

ui

5

2

3

10

0

9

5

3

20

10

5

–1

6

40 –

3

15

8

2

 + 

2

3

5 + 

8

4

8

– 15

Строим новую систему потенциалов,

v3 – u1 = 3;

v4 – u1 = 10;

v1 – u2 = 6;

v2 – u2 = 3;

v1 – u3 = 3;

v4 – u3 = 8.

Полагая u1 = 0, найдем v3 = 3, v4 = 10, u3 = 2, v1 = 5, u2 = –1, v2 = 2.

3) Исследование построенной системы ui, vj на потенциальность. Имеем

v1 – u1 = 5 – 0 = 5 < 9;

v2 – u1 = 2 – 0 = 2 < 5;

v3 – u2 = 3 + 1 = 4 < 8;

v4 – u2 = 10 + 1 = 11 > 2; α24 = 11 – 2 = 9;

v2 – u3 = 2 – 2 = 0 < 8;

v3 – u3 = 3 – 2 = 1 < 4.

Цикл, начинается с клетки (2, 4). Получим следующий улучшенный план:

 

vj

ui

14

11

3

10

0

9

5

 + 

3

20

10

– 5

8

6

25

3

15 –

8

2

 + 15

11

3

20

8

4

8

Получаем следующую систему потенциалов:

v3 – u1 = 3;

v4 – u1 = 10;

v1 – u2 = 6;

v2 – u2 = 3;

v4 – u2 = 2;

v1 – u3 = 3.

Полагая u1 = 0, найдем v3 = 3, v4 = 10, u2 = 8, v1 = 14, v2 = 11, u3 = 11, исследуем ее на потенциальность

v1 – u1 = 14 – 0 = 14 > 9; α11 = 14 – 9 = 5;

v2 – u1 = 11 – 0 = 11 > 5; α12 = 11 – 5 = 6,

v3 – u2 = 3 – 8 = –5 < 8;

v2 – u3 = 11 – 11 = 0 < 8;

v3 – u3 = 3 – 11 = –8 < 4;

v4 – u3 = 10 – 11 = –1 < 8.

Начинаем цикл с клетки (1, 2), проходим по X-выбранными клеткам и заканчиваем в клетке (1,4).

Далее находим . В клетках отрицательной полуцепи значение xij уменьшается на θ, а в клетках положительной полуцепи значение xij увеличивается на θ.

Получаем следующий план:

 

vj

ui

8

5

3

4

0

9

5

5

3

20

10

2

6

25

3

10

8

2

20

5

3

20

8

4

8

Строим систему потенциалов

v2 – u1 = 5;

v3 – u1 = 3;

v1 – u2 = 6;

v2 – u2 = 3;

v4 – u2 = 2;

v1 – u3 = 3.

Полагая u1 = 0, найдем v2 = 5, v3 = 3, u2 = 2, v1 = 8, v4 = 4, u3 = 3 и исследуем ее на потенциальность

v1 – u1 = 8 – 0 = 8 < 9;

v4 – u1 = 4 – 0 = 4 < 10;

v3 – u2 = 3 – 2 = 1 < 8;

v2 – u3 = 5 – 5 = 0 < 8;

v3 – u3 = 3 – 5 = –2 < 4;

v4 – u3 = 4 – 5 = –1 < 8.

Так как полученная система является потенциальной, то получен оптимальный план

и величина транспортных расходов равна

zопт = 5∙5 + 20∙3 + 25∙6 + 10∙3 + 20∙2 + 20∙3 = 
= 25 + 60 + 150 + 30 + 40 +  + 60 = 365.

Заключение. Рассмотрены примеры решения транспортной задачи методом потенциалов, приведены методические указания.

4. Методы решения задач целочисленного программирования

Варианты заданий:

Решить следующие задачи целочисленного линейного программирования методами Гомори:

1.

xj ≥ 0 – целые (j = 1, 2);

2.

3.

xj ≥ 0 – целые
(j = 1, 2)

Методические рекомендации

Контрольный пример 1: Решить задачу целочисленного программирования методом Гомори:

xj ≥ 0 – xj целые .

Решение. Предварительный шаг. Составляем таблицу и, отбросив условие целочисленности, решаем задачу прямым симплекс-методом:

  

–x1

–x2

–x3

1

 

y1

=

3

2

0

10

 

y2

=

1

4

0

11

 

y3

=

3

3

1

13

.

z

=

–4

–5

–1

0

 

Проделав три шага модифицированных жордановых исключений

  

–x1

–y2

–x3

1

    

–y1

–y2

–x3

1

 

y1

=

0

  

x1

=

0

 

x2

=

0

,

 

x2

=

0

,

y3

=

1

  

y3

=

1

 

z

=

–1

  

z

=

–1

 

придем к таблице

  

–y1

–y2

–y3

1

 

x1

=

0

  

x2

=

 

0

 

x3

=

1

,

z

=

1

 

из которой находим оптимальное, но нецелочисленное решение задачи:

Для отыскания целочисленного решения вводим дополнительное ограничение, например для переменной x3, и записываем его в последнюю полученную таблицу

Таблица примет вид

  

–y1

–y2

–y3

1

 

x1

=

0

 

x2

=

0

.

x3

=

1

 

s3

=

0

 

z

=

1

 

Для сохранения знаков z-строки неотрицательными применим двойственный симплекс-метод. Cделав шаг МЖИ, получим из таблицы:

  

–y1

–s3

–y3

1

x1

=

   

2

x2

=

   

2

x3

=

   

1

y2

=

   

1

z

=

1

19

целочисленное оптимальное решение x1 = 2, x2 = 2, x3 = 1, max z = 19.

Заключение. Рассмотрены примеры решения задачи целочисленного программирования методом Гомолри, приведены методические указания.

Контрольные вопросы

1. Какое дополнительное ограничение вводится в методе отсечений Гомори?

2. Каким методом решаются две задачи с введенными новыми ограничениями?

3. Каким методом решается задача после введения дополнительного ограничения s?

5. Методы решения нелинейных задач безусловной и условной оптимизации

Варианты заданий:

1) Решить следующие задачи нелинейного программирования методами безусловной оптимизации:

1)

X(0) = (0, 0);

2)

X(0) = (0, 0).

2) Решить следующие задачи нелинейного программирования методами условной оптимизации:

1)

x1 ≥ 0, x2 ≥ 0;

2)

x1 ≥ 0, x2 ≥ 0, X(0) = (2, 3).

Методические рекомендации

Контрольный пример 1. Решить ЗНЛП методом сопряженных градиентов:

Решение. Начальный этап.

1. Выбираем начальную точку X(0) = (2, 2) и точность решения ε = 0,1.

2. Находим начальное направление:

Переходим к основному этапу.

Основной этап

1. Так как евклидова норма то переходим ко 2 шагу.

2. Находим шаг движения:

3. 

4. 

Так как евклидова норма то переходим ко 5 шагу.

5. Находим следующее направление:

2. 

3. 

4. 

Так как евклидова норма то X* = (0, 0), fmin = 0.

Контрольный пример 2. Решить ЗНЛП методом вторых производных (Ньютона-Рабсона):

1. Выбираем начальную точку X(0) = (2, 2).

2. Определяем градиент функции

3. Определяется матрица Гессе Н(х(k)):

4. Определяется обратная матрица H–1(x(k)):

5. Определяется точка оптимума

Таким образом, X* = (0, 0), fmin = 0.

Контрольный пример 3. Решить ЗНЛП методом Франка-Вулфа:

Решение. .

0 итерация

1 шаг. Определяем начальное решение прямым симплекс-методом:

  

–x1

–x2

1

  

y1

=

2

3

13

 

X(0) = (0, 0).

y2

=

2

1

10

  

z

=

0,4

0,4

5

  

2 шаг. Вычисляем направление: X* находится из следующей задачи линейного программирования:

  

–x1

–x2

1

   

–x1

–y1

1

 

y1

=

2

3

13

 

x2

=

 

y2

=

2

1

10

 

y2

=

 

z

=

–2

–3

0

 

z

=

0

1

13

 

3 шаг. Определяем шаг движения

4 шаг. Определяем значение новой точки

5 шаг. Вычисляем значение функции в новой точке

f(X(0)) = 0;

Так как значение функции в новой точке больше значения в предыдущей, то переходим ко 2 шагу. Все дальнейшие вычисления занесены в таблицу.

Номер итерации

x1

x2

f(x)

s1

s2

λ*

λ

0

0

0

0

2

3

0

4,33

0

4,33

1,73

1

1

0

4,33

9,25

2

1,27

4,25

1,5

4,25

–2,83

0,47

0,47

2

2

3

10,4

1,2

1,8

0

4,33

–2

1,33

0

0

3

2

3

10,4

        

Таким образом, X* = (2, 3), zmax = 10,4.

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

Контрольные вопросы

1. Чему равен шаг движения в методе Франка-Вульфа?

2. Чему равно направление движения в методе сопряженных градиентов?

3. Приведете правило останова алгоритма метода сопряженных градиентов.

6. Сетевые методы планирования и управления

Методы сетевого планирования и управления (СПУ), разработанные в начале 50-х годов, широко и успешно применяются для оптимизации планирования и управления сложными разветвленными комплексами работ, требующими участия большого числа исполнителей и затрат ограниченных ресурсов. Для оптимизации сложных сетей, состоящих из нескольких сотен работ, вместо ручного счета следует применять типовые макеты прикладных программ по СПУ, имеющиеся в составе математического обеспечения ЭВМ.

Содержание комплексной задачи

1. Представить в виде таблицы конкретные исходные данные индивидуального задания.

2. По заданному составу комплекса работ построить исходный СГ.

3. Определить ожидаемую продолжительность выполнения каждой работы.

4. Рассчитать параметры событий исходного СГ.

5. Вычислить параметры работ исходного СГ.

6. Рассчитать параметры СГ в целом.

7. Определить трудоемкость и затраты на проведение работ в исходном СГ.

8. Используя данные исходного пункта, провести оптимизацию СГ до получения минимума продолжительности критического пути, сокращая продолжительность работ путем перераспределения части ресурсов резервной зоны на работы критической зоны СГ.

9. Построить графики «Время-Затраты» для работ СГ, лежащих на критическом пути.

10. Рассчитать параметры оптимизированного СГ и сравнить с исходными. Построить оптимизированный СГ на бумаге.

11. Вычертить на миллиметровой бумаге в масштабе план-карту распределения трудовых ресурсов для оптимизированного СГ и произвести выравнивание потребности в трудовых ресурсах во времени.

Расчет временных параметров СГ

1. Составление индивидуального перечня работ и построение графика

Заданный комплекс работ упорядочивается в их логической последовательности с выделением отдельных групп работ, которые могут и должны выполняться параллельно. Для таких групп работ могут составляться частные СГ, которые затем сшиваются в один сводный СГ. Для каждой работы проверяется возможность переноса ее начала ближе к исходному, а конца – ближе к завершающему событиям СГ и при наличии такой возможности перестроить СГ.

После составления сетевого графика и его корректировке СГ принял вид (рис. 6.1).

2. Расчет параметров событий сетевого графика

Ранний срок свершения исходного события СГ принимается равным нулю. Ранний срок свершения данного промежуточного события рассчитывается путем сравнения сумм, состоящих из раннего срока свершения события, непосредственно предшествующего данному, и ожидаемой продолжительности. В качестве раннего срока свершения события принимается максимальная из сравниваемых сумм.

Таблица 6.1

Задания для варианта № 1

Наименование
работы

Работы,
предшевств.

Время
выполнения

Затрачиваемые
ресурсы

A

–

3

4

B

–

5

3

C

–

6

2

D

A, B

2

3

E

B

2

4

F

B

1

5

K

B

4

3

L

C, K

3

6

M

C, F, K

3

4

N

C, K

5

2

P

L

2

2

Q

L

3

4

S

D, E, M

4

3

T

P, S

2

4

V

L

1

2

Рассчитанный таким способом ранний срок свершения завершающего события всего СГ принимается в качестве его же позднего срока свершения. Это означает, что завершающее событие СГ никаким резервом времени не располагает.

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

Рис. 6.1

Таблица 6.2

Параметры событий сетевого графика

Срок, дни

Номер событ, исп.

Номер события

Ранний, Tp

Поздний, Tп

Резерв

Ранний

Поздний

1

0

0

0

0

0

2

5

10

5

3

6

3

5

5

0

1

4

4

9

9

0

3

7

5

9

9

0

4

6

6

12

12

0

2, 5

8

7

12

14

2

4

8

8

16

16

0

6

10

9

15

18

3

7

10

10

18

18

0

8

10

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

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

Расчет параметров работ сетевого графика

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

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

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

Поздний срок окончания работы совпадает с поздним сроком свершения ее конечного события.

Для всех работ критического пути, как не имеющих резервов времени, ранний срок начала совпадает с поздним сроком начала, а ранний срок окончания – с поздним сроком окончания.

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

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

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

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

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

В зависимости от коэффициента напряженности все работы попадают в одну из трех зон напряженности:

а) критическую, кнij > 0,8;

б) промежуточную, 0,5 < кнij < 0,8;

в) резервную, кнij < 0,5.

Таблица 6.3

Параметры работ сетевого графика

Работа

Срок
начала, дни

Срок
завершения, дни

Резерв

I, j

Б.

Тi, j

Ранний

Поздний

Ранний

Поздний

Полный

Вольный

Свободный

1,2

A

3

0

7

3

10

7

2

2

1,3

B

5

0

0

5

5

0

0

0

1,4

C

6

0

3

6

9

3

3

3

2,6

D

2

5

10

7

12

5

5

0

3,6

E

2

5

10

7

12

5

5

5

3,5

F

1

5

8

6

9

3

3

3

3,4

K

4

5

5

9

9

0

0

0

4,7

L

3

9

11

12

14

2

0

0

5,6

M

3

9

9

12

12

0

0

0

4,10

N

5

9

13

14

18

4

4

4

7,8

P

2

12

14

14

16

2

2

0

7,9

Q

3

12

15

15

18

3

0

–2

6,8

S

4

12

12

18

18

0

0

0

8,10

T

2

16

16

18

18

0

0

0

7,10

V

1

12

17

13

18

3

5

3

Расчет параметров СГ в целом

Коэффициент сложности СГ равен отношению количества работ к количеству событий в СГ. Критический путь в СГ проходит через события и работы, не обладающие резервами времени, и имеет, следовательно, максимальную продолжительность, равную сроку свершения завершающего события.

Продолжительность критического пути соответствует математическому ожиданию срока свершения завершающего события, равного сумме ожидаемых продолжительностей работ, составляющих критический путь. Дисперсия срока наступления завершающего события определяется в соответствии с центральной предельной теоремой теории вероятностей как сумма дисперсий работ критического пути, а вероятность свершения завершающего события в срок, равный продолжительности критического пути, равна р(тсв/ткр) = 0,5. Если директивный срок установлен меньше продолжительности критического пути, вероятность свершения события к директивному сроку меньше 0,5 и может быть рассчитана с помощью функции распределения нормального отклонения (функции Лапласа) Ф(и) + 0,5.

Задание. Исследовать приведенный пример составления индивидуального перечня работ и построения сетевого графика и расчета параметров событий сетевого графика. Сформулировать другой вариант приведённого примера, меняя исходные данные в табл. 6.1 и провести расчет временных параметров сетевого графика и СГ, расчет параметров работ сетевого графика и расчет параметров СГ в целом.

Заключение. Приведены примеры составления индивидуального перечня работ и построение графика и расчета параметров событий сетевого графика.

Контрольные вопросы

1. Сетевой график (СГ).

2. Расчет временных параметров сетевого графика и СГ.

3. Расчет параметров работ сетевого графика и расчет параметров СГ в целом.

7. Многокритериальные задачи линейного программирования

Лишь в редких случаях цели, которые лицо принимающее решение (ЛПР) стремится достичь в планируемой им операции, удается описать с помощью одного количественного показателя. Поэтому специалисты Системного анализа и Исследования операций считают целесообразным избегать термина «оптимизация», так как поиск оптимального решения х, доставляющего функции F(x) экстремальное значение, имеет вполне определенный смысл и давно входит в арсенал основных понятий математики. Многообразие целей ЛПР более адекватно может быть описано с помощью некоторой совокупности частных, локальных критериев, характеризующих степень достижения частных целей.

Противоречивый характер целей обуславливает, как правило, и противоречивость ч-критериев. С формальной точки зрения это приводит к тому, что свои экстремальные значения ч-критерии получают в различных точках ОДР Dx. Следовательно, ЛПР принимая решение х′ всегда должно идти на компромисс, в разумных пределах допуская ухудшение значений одних локальных критериев во имя улучшения значений других. Именно этот этап творческой деятельности ЛПР наименее формализуем и требует привлечения предыдущего опыта, интуиции и даже искусства ЛПР, обладающего практическим опытом в соответствующей предметной области. Решение, принимаемое ЛПР с привлечением совокупности ч-критериев, будем называть компромиссным, рациональным или просто решением ЛПР, избегая при этом термина «оптимальный», имеющего определенный и вполне точный смысл.

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

1. Формальная постановка многокритериальной задачи линейного
программирования

Формальная схема многокритериальной ЗЛП (МЗЛП) от обычной ЗЛП отличается наличием нескольких целевых функций:

(6.1)

(6.2)

(6.3)

где εi – неотрицательные переменные (невязки, ).

Знак max означает тот факт, что желательно увеличение каждой из линейных форм Lr(х), отражающей некоторую r-ю цель ЛРП.

Требование только максимизации не сужает общности задачи. Так, например, требование минимизации затрат некоторых ресурсов эквивалентно требованию максимизации остатка от изначально выделенных ресурсов. Наличие многих ч-критериев позволяет сделать модель (6.1)–(6.3) более адекватной изучаемой ситуации, однако выводит её из класса задач МП и требует разработки новых способов ее анализа. Начальный анализ МЗЛП состоит в удалении из области допустимых решений (ОДР) Dх явно худших, доминируемых решений х. Решение х′ доминирует решение х (х′ > х), если при х′ хотя бы один частный критерий имеет больше значение при равенстве остальных. Поэтому решение х может быть исключено из дальнейшего рассмотрения, как явно худшее, чем х′. Если решение х′ не доминируется ни одним из решений х ∈ Dx, то его называют Паретто-оптимальным (π-оптимальным) или эффективным решением (π-решением). Таким образом, π-решение – это неулучшаемое (недоминируемое) решение, и ясно, что решение ЛПР должно обладать этим свойством – другие решения нет смысла рассматривать.

Формальное определение π-оптимальности решения х′ записывается как требование об отсутствии такого решения х ∈ Dx, при котором бы были выполнены условия

(6.4)

и хотя бы одно из них – строго (со знаком >).

Иными словами, условия (6.4) выражают требование невозможности улучшения решения х′ в пределах ОДР Dx ни по одному ч-критерию без ухудшения хотя бы по одному из других.

Условие задачи

Даны целевые функции:

L1 = –x1 + 2x2 + 2;

L2 = x1 + x2 + 4;

L3 = x1 – 4x2 + 20,

и система ограничений:

x1 + x2 ≤ 15;

5x1 + x2 ≥ 1;

–x1 + x2 ≤ 5;

x2 ≤ 20; ∀xj ≥ 0.

2. Решение многокритериальной задачи линейного программирования графическим методом

Формальное условие и сведение к ЗЛП

Чтобы можно было проверить условие (7.4) (Lr(x) ≥ Lr(x′), ∀r) для некоторой произвольно взятой точки x′, не прибегая к попарному сравнению с другими, условие π-оптимальности (10.4) переформулируем в виде следующей задачи линейного программирования:

x ∈ Dx, ∀xj ≥ 0.

Смысл задачи линейного программирования нетрудно понять, если учесть, что δr – это приращение ч-критерия Lr, получаемое при смещении решения х′ в точку х. Тогда, если после решения ЗЛП окажется Dmax = 0, то это будет означать, что ни один из ч-критериев нельзя увеличить (Dmax = 0), если не допускать уменьшения любого из других (∀δr ≥ 0). Но это и есть условие π-оптимальности х′. Если же при решении окажется, что Δ ≥ 0, то значит какой-то ч-критерий увеличил свое значение без ухудшения значений других (∀δr ≥ 0), и значит .

Теперь перейдем к решению нашей задачи:

L1 = –x1 + 2x2 + 2;

L2 = x1 + x2 + 4;

L3 = x1 – 4x2 + 20;

x1 + x2 ≤ 15;

5x1 + x2 ≥ 1;

–x1 + x2 ≤ 5;

x2 ≤ 20;

∀xj ≥ 0.

Проверим некоторую точку х′ = (5; 3) (эта точка принадлежит области Dx) на предмет π-оптимальности:

Запишем ЗЛП в каноническом виде:

и в форме с-таблицы:

Т1

х1

х2

1

ε1

–1

–1

16

ε2

5

1

–4

ε3

1

–1

100

ε4

0

–1

10

δ1

1

–2

–4

δ2

1

1

–12

δ3

–1

1

–8

Δ

1

4

–24

Применяя с-метод, после замены δ3 ↔ х2, получаем:

Т2

х1

δ1

1

ε1

–3/2

1/2

29/2

ε2

11/2

–1/2

–1/2

ε3

1/2

1/2

9/2

ε4

–1/2

1/2

39/2

X2

1/2

–1/2

1/2

δ2

3/2

–1/2

–15/2

δ3

1

–2

–5

Δ

5/2

–3/2

–25/2

Опорный план не получен, следовательно делаем еще одну замену: ε1 ↔ х1:

Т3

ε3

δ1

1

x1

  

29/3

ε2

  

316/6

ε3

  

56/6

ε4

  

88/6

x2

  

16/3

δ2

  

7

δ3

  

14/3

Δ

–5/3

–2/3

70/6

В Т3 получен опорный план. Так как при этом Δ > 0, то, следовательно, система ч-критериев не противоречива и существует некоторая область, смещение в которую решения х′ способно увеличить, по крайней мере, один ч-критерий без уменьшения значений остальных

Заключение. Приведены пример формальной постановки многокритериальной задачи линейного программирования и решение приведенной задачи графическим методом.

Контрольные вопросы

1. Многокритериальные задачи.

2. Многокритериальная задача линейного программирования.

3. Методы решения многокритериальных задач.

8. Определение Парето-оптимального множества
симплекс-методом

1. Удаление пассивных ограничений

Перед построением π-множества из системы ограничений должны быть удалены пассивные ограничения. Пассивным будем называть неравенство (п-неравенство), граница которого не является частью границ области Dx, за исключением, может быть, ее отдельной точки. Неравенства, образующие границы Dx, назовем активными (а-неравенства).

Чтобы грани не были включены в , не имея никакого отношения к , неравенство ε1 должно быть удалено из исходной системы
ограничений. Условием для исключения неравенства εi ≥ 0 из системы является несовместность (или вырожденность) данной системы неравенств при условии εi = 0. Геометрически это означает, что граница εi = 0 неравенства εi ≥ 0 не пересекается с областью Dx или имеет одну общую точку. Если граница εi = 0 имеет общую угловую точку с Dx (вырожденность), то с удалением п-неравенства εi ≥ 0 эта точка не будет утеряна, так как она входит в границы других неравенств. Помимо заданных m неравенств проверке подлежат и n условий неотрицательности переменных, так как координатные плоскости (оси) также могут входить в границы Dx.

В качестве примечания можно отметить, что поскольку п-неравенства (пассивные неравенства) для любой точки x ∈ Dx будут выполнены, то по мере выявления п-неравенств и введения их в базис они удаляются из с-таблицы.

Запишем систему неравенств Dx в форме с-таблицы:

Т1

х1

х2

1

bi/ais

bi/ais

ε1

–1

–1

15

15

15

ε2

5

1

–1

1/5

1

ε3

1

–1

5

–

5

ε4

0

–1

20

–

20

Т2

ε1

x2

1

    

x1

ε2

1

х1

–1

–1

15

    

ε1

4

–1

14

ε2

–5

–4

74

    

x2

–5

1

1

ε3

–1

–2

20

    

ε3

2

–1

4

ε4

0

–1

20

    

ε4

1

–1

19

ОП – получен, следовательно х2 и ε1 – активные ограничения; из Т2 получаем:

Т3

ε1

ε3

1

x1

1

1/2

5

ε2

–3

2

34

x2

–1/2

–1/2

10

ε4

2

1/2

10

отсюда делаем вывод, что ε3 – активное ограничение; из Т3 получаем:

Т4

ε4

ε3

1

x1

  

10

ε2

  

19

x2

  

15/2

ε1

  

–5

Опорный план не получен, следовательно ε4 – пассивное ограничение.

2. Определение π-множества с-методом

При подготовке решения для ЛПР интерес будет представлять информация обо всем множестве π-оптимальных (эффективных) решений . Графический метод позволяет сформулировать довольно простой подход к определению множества . Суть этого подхода в следующем. Решая усеченную задачу линейного программирования, устанавливаем факт существования д-конуса (Δmax > 0). Поскольку для линейных ЦФ конфигурация д-конуса не зависит от положения его вершины х′, то, помещая ее на границу εi области Dx, решаем усеченную ЗЛП с добавлением εi, соответствующего i-му участку границ Dx. Вырождение д-конуса в точку х′ будет признаком π-оптимальности и всех других точек данной грани. С помощью с-метода указанная процедура легко проделывается для пространства любой размерности n. Неудобство указанного метода состоит в том, что потребуется на каждой грани ОДР Dx найти точку х′ (по числу граней Dx) сформулировать и решить столько же ЗЛП размера R×n.

Существенно сократить объем вычислений можно путем выбора вершины д-конуса в фиксированной точке х′ = (1)n и в нее же параллельно себе перенести грани, составляющие границы Dx

Приведенные к точке х′ = (1)n приращения δ–r и невязки εi запишутся в виде:

где черта сверху у δ, ε и Δ означает, что эти величины приведены к точке х′ = (1)n.

По существу, (8) – ЗЛП размера (R + m)×n (Δ → max), а ее решение позволит найти все грани, составляющие π-множество .

Составляем с-таблицу, не учитывая пассивные ограничения, т.е ε1:

Т1

х1

х2

1

ε2

–1

–1

2

ε3

5

1

–6

ε4

1

–1

0

х1

1

0

–1

х2

0

1

–1

δ1

1

–2

1

δ2

1

1

–2

δ3

–1

4

–3

Δ

1

3

–4

В начале решается усеченная ЗЛП (под чертой):

Т2

х1

δ1

1

ε1

–3/2

1/2

3/2

ε2

11/2

–1/2

–11/2

ε3

1/2

1/2

–1/2

х1

1

0

–1

х2

1/2

–1/2

–1/2

x2

1/2

–1/2

1/2

δ2

3/2

–1/2

–3/2

δ3

1

–2

–1

Δ

5/2

–3/2

–5/2

Т3

δ3

δ1

1

ε1

–3/2

–5/2

0

ε2

11/2

21/2

0

ε3

1/2

3/2

0

х1

1

2

0

х2

1/2

1/2

0

x2

1/2

1/2

1

δ2

3/2

5/2

0

x1

1

2

1

Δ

5/2

7/2

0

Т4

ε1

δ1

1

δ3

  

0

x2

  

1

δ2

  

0

x1

  

1

Δ

–5/3

–2/3

0

, так как Δmax = 0.

Данный метод построения множества обладает недостатком, связанным с разрушением области допустимых решений (ОДР) Dx при переносе ее граней в х′. Действительно, вершины области Dx в преобразованной модели никак не отражены, а именно одна из них может составить π-множество в случае его совпадения с оптимальным решением. Такое совпадение возможно, если все ч-критерии достигают максимум на одной вершине. Физически это значит, что они слабопротиворечивы – угол при вершине д-конуса приближается к 180° (градиенты ч-критериев имеют практически совпадающие направления). Данный случай имеет место, если в π-множество не вошла ни одна из граней ОДР Dx. Следовательно, π-множество совпадает с оптимальным решением. Для определения π-множества решается обычная ЗЛП с одним из ч-критериев. Если при этом получено множество оптимальных решений, то решается ЗЛП с другим ч-критерием. Пересечение оптимальных решений и является π-множеством. Для ЛПР указание на то, что некоторая грань π-оптимальна, является только обобщенной информацией.

3. Определение альтернативных вариантов многокритериальной задачи

Наиболее разумным решением многокритериальной задачи было бы органическое объединение всех ч-критериев в виде единой ЦФ. Иногда это удается сделать путем создания более общей модели, в которой ч-критерии являются аргументами более общей целевой функции, объединяющей в себе все частные цели операции. На практике этого редко удается достигнуть, что, собственно, и является основной причиной появления проблемы многокритериальности. Однако наиболее распространенный подход к решению проблемы пока остается все-таки один: тем или иным путем свести решение многокритериальной задачи к решению однокритериальной задачи. В основе подхода лежит предположение о существовании некой функции полезности, объединяющей в себе ч-критерии, но которую в явном виде, как правило, получить не удается. Получение наиболее обоснованной «свертки» ч-критериев является предметом исследований нового научного направления, возникшего в связи с проблемой многокритериальности – теории полезности. В данной работе будут рассмотрены некоторые подходы, позволяющие получить варианты решения многокритериальных задач при тех или иных посылках и которые лицо принимающее решение (ЛПР) должно рассматривать как альтернативные при принятии окончательного решения и которые, конечно, должны удовлетворять необходимому условию – π-оптимальности.

4. Метод гарантированного результата

При любом произвольном решении х ∈ Dx каждый из ч-критериев примет определенное значение и среди них найдется, по крайней мере, один, значение которого будет наименьшим:

Метод гарантированного результата (ГР) позволяет найти такое (гарантированное) решение, при котором значение «наименьшего» критерия станет максимальным. Таким образом, целевая функция (ЦФ) является некоторой сверткой локальных критериев, а МЗЛП сводится к задаче КВП (кусочно-выпуклого программирования) при ОДР Dx, заданной линейными ограничениями.

Исходные условия записываем в каноническом виде:

δ1 = х1 – 2х2 – φ + 2;

δ2 = х1 + х2 – φ + 4;

δ3 = –х1 + 4х2 – φ + 20;

ε1 = –х1 – х2 + 15;

ε2 = 5х1 + х2 – 1;

ε3 = x1 – х2 + 5,

потом в виде с-таблицы:

Т1

х1

х2

φ

1

ε1

–1

–1

0

15

ε2

5

1

0

–1

ε3

1

–1

0

5

δ1

1

–2

–1

2

δ2

1

1

–1

4

δ3

–1

4

–1

20

Вводя в базис переменную φ (δ1 ↔ φ), получаем обычную ЗЛП при максимизации ЦФ φ.

Т2

х1

х2

δ1

1

ε1

–1

–1

0

15

ε2

5

1

0

–1

ε3

1

–1

0

5

φ

1

–2

–1

2

δ2

0

3

1

2

δ3

–2

6

1

18

Т3

δ3

x2

δ1

1

bi/ais

ε1

1/2

–4

–1/2

6

6/4

ε2

–5/2

16

5/2

44

–

ε3

–1/2

2

2

14

–

φ

–1/2

1

–1/2

11

–

δ2

0

3

–1

2

–

х1

–1/2

3

1/2

9

–

Т4

δ3

ε1

δ1

1

x2

   

3/2

ε2

   

68

ε3

   

17

φ

–3/8

–1/4

–5/8

25/2

δ2

   

13/2

х1

   

27/2

Решение ЗЛП приводит к конечной с-таблице Т4. Видно, что полученное гарантированное решение х π-оптимально, поскольку введение в базис любой свободной переменной (т.е. ее увеличение) приведет к снижению φ – нижнего уровня ч-критериев (∀сj < 0). Из таблицы также видно, что решение х0 = (27/2; 3/2) находится на грани ε4, при этом значения ч-критериев равны (находим по формуле Lr(xr) = φ + δr):

L1 = L3 = φ = 25/2;

L2 = φ + δ2 = 25/2 + 13/2 = 19;

LΣ = 88/2 = 44;

x°°= (27/2; 3/2).

Если бы в строке φ имелись нули, то это означало бы, что одну из соответствующих переменных можно ввести в базис (увеличить без снижения уровня φ). Это могло бы привести и к увеличению приращения δr для некоторого ч-критерия, находящегося в базисе.

Заключение. Рассмотрены задачи удаления пассивных ограничений, определение π-множества с-методом, определения альтернативных вариантов многокритериальной задачи и описан метод гарантированного результата. Приведены соответствующие примеры.

Контрольные вопросы

1. Активные и пассивные ограничения.

2. Парето-множество.

3. Симплекс метод.

3. Метод гарантированного результата.

9. Методологические основы и методы проведения экспертных процедур

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

Применение математико-статистических методов значительно расширяет возможности использования информации, полученной от специалистов. Практика показала, что даже простые статистические методы в сочетании с экспертной информацией при выборе перспективных решений часто приводят к более успешным результатам, чем «точные» расчеты с ориентацией на средние показатели.

Основные трудности, возникающие в процессе математического описания, поиске и выборе решений при управлении технологическими объектами нефтеперерабатывающих производств, обусловлены прежде всего недостаточно высоким качеством и неполнотой имеющейся информации. Выделим некоторые причины возникновения таких информационных трудностей:

– исходная статистическая информация зачастую бывает недостаточно достоверной. Часто, даже при наличии достоверных данных, они не могут служить надежной базой для принятия решений, направленных в будущее, поскольку существующие условия и обстоятельства могут в дальнейшем измениться;

– часть информации может иметь качественный характер, который не поддается количественной оценке. Поскольку такие факторы и явления оказывают существенное влияние на результаты решений, их нельзя не учитывать;

– на практике часто возникают ситуации, когда, в принципе, необходимую информацию можно получить, однако из-за больших затрат времени или средств сбора информации нецелесообразен.

Характерными особенностями метода экспертных оценок как инструмента решения сложных проблем производства являются, во-первых, обоснованная организация проведения всех этапов экспертизы, обеспечивающая наибольшую эффективность работы на каждом из этапов, и, во-вторых, применение количественных методов как при организации экспертизы, так и при обработке результатов. Эти две особенности отличают метод экспертных оценок от обычной экспертизы, широко применяемой в различных сферах человеческой деятельности.

Область применения метода экспертных оценок весьма широка. Основными задачами производства, в том числе и нефтепереработки, решаемыми методом экспертных оценок, являются:

– определение целей и задач управления с упорядочением их по степени важности;

– определение альтернативных вариантов решения задачи с оценкой их предпочтения;

– построение математических моделей сложных объектов и процессов при дефиците информации;

– решение задачи принятия решений на основе количественной и качественной информации и т.д.

Перейдем к рассмотрению вопросов практического применения методов экспертных оценок для различных задач.

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

Как уже отмечалось, в таких случаях дополнительные данные, компенсирующие недостающую информацию, получают на основе экспертного опроса. Специалисты-эксперты могут количественно или качественно описать исследуемый объект. Затем с помощью специальных формальных методов осуществляется обработка собранной информации.

Особую роль играют экспертные оценки в управлении. Изложение метода экспертных оценок как одного из научных инструментов для решения сложных проблем в процессе управления дано в работе. Недостаточные полнота и достоверность информации часто не позволяют применить традиционные методы математического моделирования и принятия решений при управлении объектами. В этих условиях, как было отмечено, экспертные процедуры дают возможность решать перечисленные задачи.

Процедуры экспертной оценки расплывчатых категорий и подходы к проведению экспертизы при нечеткой информации обсуждены в работе.

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

В последнее время получило развитие достаточно перспективное направление, связанное с применением экспертных оценок для создания экспертных систем. Согласно определению, экспертная система обладает возможностями имитировать поведение опытного эксперта в определенной предметной области: она обладает как его знаниями, так и логикой рассуждений. Через блок взаимодействия с экспертом экспертные знания должны поступать в ЭВМ, перерабатываться и составлять в своей совокупности базу знаний экспертной системы. Экспертная система содержит также базу данных, включающую в себя данные о предметной области, структуру проблемы, известные причинно-следственные связи. Важным элементом экспертной системы является механизм логического вывода, который дает возможность использовать знания эксперта о предметной области.

1. Методы экспертной оценки

Перейдем к рассмотрению методов экспертного оценивания.

К наиболее распространенным методам экспертной оценки относятся ранжирование, непосредственная оценка, последовательное сравнение и парное сравнение

Для описания перечисленных методов предположим, что имеется конечное число измеряемых объектов О1, О2, …, Оn сформулированы показатели сравнения (критерии) I1, I2, …, Ik по которым осуществляется сравнение объектов. Методы измерения различаются лишь процедурой сравнения, которая включает построение отношений между объектами эмпирической системы, выбор функции, отражающей объекты эмпирической системы на числовую систему и определение типа шкалы измерений.

Ранжирование представляет собой процедуру упорядочения объектов, выполняемую экспертом. На основе этих знаний и опыта эксперт располагает объекты в порядке предпочтения, руководствуясь одним или несколькими показателями сравнения. Этот вид оценки позволяет выбрать из исследуемой совокупности факторов наиболее существенный.

Сущность процедуры ранжирования заключается в следующем. При ранжировании эксперт должен расположить объекты (альтернативы) в порядке, который представляется ему наиболее рациональным, и приписать каждому из них числа натурального ряда – ранги. При этом ранг 1 получает наиболее предпочтительная альтернатива, а ранг N – наименее предпочтительная. Если среди сравниваемых альтернатив имеются эквивалентные по важности, то эксперт присваивает им дробные (связанные) ранги.

При групповой экспертной оценке каждый i-й эксперт присваивает каждому j-му объекту ранг rij. В результате проведения экспертного оценивания получается матрица рангов , [n×m], где m – число экспертов , а п – число объектов .

Для каждого объекта подсчитывают сумму рангов:

полученную от всех экспертов. Затем, исходя из величины Rij, устанавливают результирующий ранг для каждого объекта.

Наивысший (первый) ранг присваивают объекту, получившему наименьшую сумму рангов, и, наоборот, объекту, получившему наибольшую сумму рангов, присваивают самый низкий ранг. Остальные объекты упорядочивают в соответствии со значением суммы рангов относительно объекта, которому присваивается первый ранг.

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

Достоинством ранжирования как метода оценивания является простота осуществления процедур. Недостаток этого метода заключается в том, что с увеличением числа объектов резко снижаются точность и надежность метода.

Метод непосредственной оценки представляет собой процедуру приписывания объектам числовых значений. Диапазон изменения какой-либо качественной переменной разбивается на несколько интервалов, каждому из которых присваивается определенная оценка (балл), например, от 0 до 5. Задача эксперта заключается в помещении каждого из рассматриваемых объектов в определенный оценочный интервал либо в соответствии со степенью обладания тем или иным свойством, либо в соответствии с предположениями эксперта об их значимости.

Метод последовательных сравнений. Последовательное сравнение представляет собой комплексную процедуру измерения, включающую как ранжирование, так и непосредственную оценку.

Алгоритмы процедуры последовательной оценки состоит из следующих, выполняемых экспертами, шагов:

1. Осуществляется ранжирование объектов.

2. Производится непосредственная оценка объектов на отрезке [0, 1],
полагая, что числовая оценка первого и ранжировка объекта равна единице f(О1) = 1.

3. i = 1.

4. Эксперт решает, будет ли i-й объект превосходить по предпочтительности все остальные объекты, вместе взятые.

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

В противном случае, эксперт изменяет величину Д00 так, чтобы выполнялось условие:

6. i = i + 1.

7. Если i ≤ n + 1, то перейти к пункту 4, иначе к пункту 8.

8. Вывод результатов и конец процедуры.

Как видно, описанная процедура состоит в систематической проверке оценок на базе их последовательного сравнения.

Применение метода последовательных сравнений предполагает, что, если задан некоторый интервал действительного переменного, например, [0, 1], то эксперт, основываясь на имеющейся у него информации, может установить предварительные оценки для каждого объекта, а затем уточнить их на основе сравнения с помощью определенной логической процедуры.

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

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

В результате сравнения пары объектов oi oj эксперт упорядочивает эту пару, высказывая, что либо ( предпочтение), либо oi ∞ oj, Выбор числового представления f естественно произвести так, что если , то , если предпочтение в паре обратное, , а если объекты эквивалентны, то естественно полагать, что f(oi) ∞ f(oj).

Производить парное сравнение удобно не только тогда, когда различия между объектами настолько малы, что непосредственное ранжирование или оценка не обеспечивают их разумного упорядочения, но и в случае возникновения проблемы, связанной с большим количеством сравниваемых факторов. Таким образом, метод парных сравнений имеет некоторые преимущества перед другими методами упорядочения в случаях, когда объектов (факторов, альтернатив) много и (или) они трудно различимы.

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

2. Качественные экспертные оценки и их особенности

Качественными (нечеткими) называются экспертные оценки, не содержащие чисел. Их можно подразделить на две группы:

– оценки, проводимые по заранее составленным шкалам (оценка качественных признаков);

– оценки, шкалы для которых заранее не могут быть составлены.

Оценки первой группы применяются при определении значений признаков, имеющих качественную вариацию, все значения которых могут быть заранее перечислены и определены некоторыми стандартными терминами или выражениями. Например, признак «влияние исследуемого параметра процесса на количество и качество получаемого продукта» может иметь следующие градации:

– сильно увеличивается выход продукта, а качество продукта ухудшается;

– увеличивается количество продукта, качество не меняется;

– количество получаемого продукта не меняется, качество улучшается и т.д.

Оценивая влияния данного параметра на количество и качество, эксперт указывает на одну из перечисленных градаций и, следовательно, проводит выбор оценки из числа заранее определенных значений.

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

Из-за сложности технологических процессов и объектов нефтепереработки, нехватки или отсутствия промышленных средств измерения и контроля, присутствия человека-оператора в процессе управления, собранная информация о их функционировании, как правило, носит нечеткий характер. В этих условиях для оценки нечетких параметров необходимо провести качественную экспертную процедуру.

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

Основными этапами алгоритма экспертной оценки в условиях неопределенности, связанной с нечеткостью информации, являются:

1) категоризация объекта оценки, классов задач, операций и алгоритмов;

2) выбор класса квалификаторов (лингвистические переменные, тер множество), адекватных объекту оценки и классу операций;

3) выбор типа шкал, описывающих объект и задачи;

4) определение способа оценки и проведение оценки;

5) проверка на субъективную совместимость признаков и их совокупности (соответствие интуитивному образу объекта).

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

В конкретных задачах рассматриваются следующие способы представления нечетких параметров:

– значением функции принадлежности μc(x) ∈ [0, 1];

– значением на шкале, являющейся совокупностью фиксированных элементов xq;

– значением на шкале, являющейся совокупностью нечетких элементов qv, μc(xq);

– в виде графика (например, в виде типовых линий);

– в виде аналитической функции.

Нечеткие параметры удобно представлять в параметрической форме в виде треугольника, трапеции или экспоненциальной кривой. Эти способы представления нечетких параметров пригодны также для получения относительных мер нечеткости.

К применяемым способам опроса экспертов в соответствии с выбранным способом представления нечетких категорий относятся:

– индивидуальное измерение, в интервале [0, 1];

– индивидуальное формирование графика функции принадлежности;

– индивидуальное формирование элемента шкалы в виде треугольника, трапеции и т.д;

– индивидуальное формирование фиксированных точек (края – середины промежутка);

– индивидуальное формирование аналитической функции. Отметим, что формальное представление нечетких характеристик может осуществляться следующими основными путями:

– непосредственным диалогом исследователя (консультанта) с ЛПР (экспертом);

– диалогом ЛПР с ЭВМ;

– диалогом ЛПР с партнерами по коммуникации с помощью ЭВМ.

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

3. Этапы работ по организации и проведения экспертной оценки

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

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

Параллельно с процессом формирования экспертной группы, группа управления проводит разработку организации и методики проведения опроса экспертов. При этом решаются следующие вопросы: место проведения опроса, предполагаемое количество и задачи туров опроса, форма и порядок проведения опроса, форма оформления результатов опроса.

Следующим этапом работы группы управления является определение организации и методики обработки данных опроса. Здесь необходимо определить задачи и сроки обработки, процедуры и алгоритмы обработки, средства проведения обработки.

В процессе непосредственного проведения опроса экспертов и обработки его результатов группа управления осуществляет выполнение комплекса работ в соответствии с разработанным планом, корректируя его по мере необходимости.

Проведение экспертной оценки завершается оформлением полученных результатов. На этом этапе производится анализ результатов
экспертного оценивания, составление отчета, представление итогов работы в удобном для пользователя виде.

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

(6.5)

где m, n – соответственно количество экспертов и объектов rij – ранг, присваиваемый j-м экспертом, i-му объекту  – оценка математического ожидания по объекту.

При наличии связанных рангов коэффициент конкордации вычисляется по выражению (6.6):

(6.6)

где  – показатель связанных рангов в j-й ранжировке; Hj – число групп связанных рангов в j-й ранжировке; hk – число равных рангов в k-й группе связанных рангов при ранжировке j-м экспертом. Если совпадающих рангов нет, то Hj = 0, hk = 0 и, следовательно, Tj = 0. В этом случае формула (6.5) совпадает с формулой (6.6).

Коэффициент конкордации равен 1, если все ранжировки экспертов одинаковы, и равен нулю, если все ранжировки различны, т.е. совершенно нет совпадения.

Коэффициент конкордации, вычисляемый по формуле (6.5) или (6.6), является оценкой истинного значения коэффициента и, следовательно, представляет собой случайную величину.

Для определения значимости оценки коэффициента конкордации необходимо знать распределение частот для различных значений числа экспертов т количества объектов п. Для больших значений пит можно использовать известные статистические методы. При числе объектов п > 7 оценка значимости коэффициента конкордации может быть произведена по критерию x2. Величина Wm(n – 1) имеет х2 распределение с v = п – 1 степенями свободы.

При наличии связанных рангов x2 распределение с v = п – 1 степенями свободы имеет величину:

(6.7)

Приведем пример проведения экспертной оценки для выявления определяющих параметров на процесс замедленного коксования.

Пяти экспертам было предложено проранжировать 10 факторов, наиболее сильно влияющих на протекание процесса замедленного коксования на УЗК. Результаты опроса представлены в табл. 6.4, цифры в которой характеризуют место (ранг), отведенное данному фактору в ранжированном ряду.

Введенные обозначения:

x1 – расход сырья;

x2 – плотность (коксуемость) сырья;

x3 – температура на перевале печей П-2,3:

x4 – давление в печах вторичного сырья;

x5 – расход острого орошения в К-1;

x6 – расход циркуляционного в К-2;

x7 – температура перетока в колонну К-2;

x8 – температура перетока в колонну К-3;

x9 – температура на входе коксовых камер (реакторов);

x10 – давление в реакторах,

где ri – сумма рангов;  – средняя сумма рангов;  – отклонения рангов от среднего;  – квадрат отклонения; Ri – итоговые ранги факторов.

Средняя сумма рангов

Вычисляем сумму квадратов отклонений

Результаты обработки экспертной информации приведены в нижеприведенной таблице.

Таблица 6.4

Эксперт

Факторы

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

1

1

3

4,5

4,5

6,5

6,5

9

10

2

8

2

1,5

1,5

5

6

7,5

7,5

9,5

9,5

3

4

3

2

2

4,5

4,5

7,25

7,25

7,25

7,25

2

6

4

1

3

4

5

7,5

7,5

9,5

9,5

2

6

5

1,5

1,5

5,5

5,5

7

8

9

10

3,5

3,5

7

11

23,5

30,5

35,7

36,7

44,2

46,2

12,5

27,5

Δi

–20,5

–16,5

–2

3

8,25

9,25

16,7

18,7

–15

0

420,2

272,2

4

9

68,1

85,6

281

352

225

0

Ri

I

II

IV

VI

VII

VIII

IX

X

III

V

Поскольку в ранжировках имеются связанные ранги, то вычисление коэффициента конкордации (согласованности мнений экспертов) выполним с использованием формулы (9.2).

Сначала вычислим величины Tj:

T1 = 23 – 2 + 23 – 2 = 12;

T2 = 23 – 2 + 23 – 2 + 23 – 2 = 18;

T3 = 33 – 3 + 23 – 2 + 43 – 4 = 90;

T4 = 23 – 2 + 23 = 12;

T5 = 23 – 2 + 23 – 2 + 23 – 2 = 18.

Подставляя значения Tj , S и n = 10, m = 5 в формулу (9.1), получаем

Оценим значимость коэффициента конкордации. В данном случае число степеней свободы v = п – 1 = 9.

Табличное значение x2 для v = 9 и 5 % уровня значимости

Подставляя значения величины в формулу (7.3), получаем

Поскольку значения (21,07 < 38,615), то гипотеза о согласии экспертов в ранжировках принимается.

Таким образом, в результате экспертной процедуры получили ранжировку по степени влияния режимных параметров на выходы целевых продуктов. Как видно из табл. 9.1, наиболее сильно влияют на выход продуктов, количество (расход) и качество (плотность) сырья (ранг соответственно I и II), температура на входе реактора (ранг III) и т.д.

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

В результате анализа работ по экспертным оценкам и по результатам данного раздела можно сделать следующие выводы:

1) при исследовании сложных, количественно трудноописываемых объектов нефтепереработки применение статистических методов в сочетании с экспертной информацией позволяет получить более успешные результаты;

2) для широкого круга прикладных задач производства экспертные процедуры являются эффективным, а в условиях неопределенности и единственным средством их решения;

3) в условиях невозможности количественной оценки состояния исследуемого объекта и проблемы, проводится качественная экспертная оценка с последующей обработкой результатов экспертизы на основе методов теории нечетких множеств.

Заключение. Изложены методологические основы экспертной оценки. Рассмотрены и кратко описаны основные методы экспертной оценки. Рассмотрены качественные экспертные оценки и их особенности. Дано описание этапов работ по организации и проведения экспертной оценки

Контрольные вопросы

1. Методологические основы экспертной оценки.

2. Методы экспертной оценки.

3. Метод ранжирования.

4. Метод последовательного сравнения.

5. Метод парных сравнений.

6. Качественные экспертные оценки и их особенности.

7. Этапы работ по организации и проведения экспертной оценки.

10. Интеллектуальные модели в управлении, нейро-нечеткие модели, генетические алгоритмы

1. Системы интеллектуального управления

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

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

В случае использования в системе управления искусственного интеллекта в качестве интеллектуального преобразователя реализуются:

– экспертные системы;

– ситуационное управление;

– управление структурной динамикой сложных технологических и другие интеллектуальные системы и их элементы.

Интересным примером использования интеллектуального преобразователя в системе управления является использование динамической экспертной системы, структура которой предложенного в виде двух блоков: синтеза и реализации цели (рис. 6.2).

Математическая модель интеллектуальной системы управления состоит из трех частей:

– интеллектуального преобразователя (экспертной системы, включающей базы данных и знаний);

– объекта управления;

– управляющее устройства системы (вычислительных и преобразующих и исполнительных устройств).

Интеллектуальный преобразователь представляет из себя логико-преобразующее устройство, который преобразовывает информацию о внешней среде и объекте управления трансформирует в сигналы Y, в сигналы воздействия на управляющие устройства системы. Математическая модель интеллектуального преобразователя описывается в оператором виде:

Y = F(x, u, w, p, z), (10.1)

где F(.) – некоторый оператор интеллектуального преобразования, характеризующий структуру или и работу интеллектуального преобразователя; x – вектор состояния системы управления; u – вектор управления; w – вектор воздействий внешней среды; p – вектор сигналов цели; z – вектор параметров объекта. Объект управления в достаточно общем случае описывается уравнениями вида:

x = f(x, u, w, z, t), y = C(x), x(t0) = x0, t ≥ t0, (10.2)

где f(.) – вектор – функция, описывающая объект управления; С(.) – заданная функция выходных сигналов; t – координата времени; y – вектор выхода или измерений.

Рис. 6.2. Структурная схема системы интеллектуального управления
с динамической экспертной системой

Управляющее устройства системы (вычислительных и преобразующих и исполнительных устройств) формируют управляющие воздействия на объект управления u из множества его возможных значений в соответствие с решаемой задачей для достижения сформированной интеллектуальным преобразователем цели.

Для формирования воздействий на систему управления объектом в интеллектуальном преобразователе используется блок принятия решения, который может быть рассмотрен как самостоятельный элемент. Блок принятия решений формируется на основе теории принятия решений.

2. Нейро-нечеткие модели

В самом упрощенном виде нейронную сеть можно рассматривать как способ моделирования в технических системах принципов организации и механизмов функционирования головного мозга человека. Согласно современным представлениям, кора головного мозга человека представляет собой множество взаимосвязанных простейших ячеек – нейронов, количество которых оценивается числом порядка 1010. Технические системы, в которых предпринимается попытка воспроизвести, пусть и в ограниченных масштабах, подобную структуру (аппаратно или программно), получили наименование нейронные сети.

Нейрон головного мозга получает входные сигналы от множества других нейронов, причем сигналы имеют вид электрических импульсов. Входы нейрона делятся на две категории – возбуждающие и тормозящие. Сигнал, поступивший на возбуждающий вход, повышает возбудимость нейрона, которая при достижении определенного порога приводит к формированию импульса на выходе. Сигнал, поступающий на тормозящий вход, наоборот, снижает возбудимость нейрона. Каждый нейрон характеризуется внутренним состоянием и порогом возбудимости. Если сумма сигналов на возбуждающих и тормозящих входах нейрона превышает этот порог, нейрон формирует выходной сигнал, который поступает на входы связанных с ним других нейронов, т.е. происходит распространение возбуждения по нейронной сети. Типичный нейрон может иметь до 10J связей с другими нейронами.

Подход, базирующийся на нейронных сетях, часто рассматривается как несимволический, или субсимволический (subsymbolic), поскольку основная информационная единица, подлежащая обработке, является не символом, а чем-то более примитивным. Независимо от способа реализации, нейронную сеть можно рассматривать как взвешенный ориентированный граф. Узлы в этом графе соответствуют нейронам, а ребра – связям между нейронами. С каждой связью ассоциирован вес – рациональное число, – который отображает оценку возбуждающего или тормозящего сигнала, передаваемого по этой связи на вход нейрона-реципиента, когда нейрон-передатчик возбуждается.

Поскольку нейронная сеть носит явно выраженный динамический характер, время является одним из основных факторов ее функционирования. При моделировании сети время изменяется дискретно, и состояние сети можно рассматривать как последовательность мгновенных снимков, причем каждое новое состояние зависит только от предыдущего цикла возбуждения нейронов.

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

Часть узлов сети используется в качестве выходных, и их состояние активности считывается в конце процесса вычислений. Но часто интерес представляет и состояние всей сети после того, как вычисления закончатся, либо состояние узлов с высоким уровнем активности. В некоторых случаях интерес может представлять наблюдение за процессом установки сети в стабильное состояние, а в других – запись уровня активизации определенных узлов перед тем, как процесс распространения активности завершится.

Определение. Сеть связности (connectionist network) может рассматриваться как взвешенный ориентированный граф, в котором для каждого узла i выполняются следующие требования:

1) состояние активности узла в любой момент времени t является действительным числом (будем обозначать его как ai(t));

2) вес связи, которая связывает узел i с любым другим узлом у сети, является действительным числом wij;

3) активность узла в момент t + 1 является функцией от его активности в момент времени t, ai(t); взвешенной суммы сигналов на входах в момент времени t, neti{f}; произвольного внешнего входного сигнала xi(t).

Простая функция вычисления состояния активности узла i, удовлетворяющая требованию (3) приведенного выше определения, имеет вид

Это, однако, не единственно возможный способ определения активности. Функции других видов включают добавление термов, соответствующих росту или спаду активности, или имеют вид нелинейных дифференциальных функций

При конструировании сети веса связей могут быть назначены априори или изменяться со временем. В последнем случае изменение весов является одним из следствий активности сети. Веса можно рассматривать как отражение знаний, а процесс их настройки и уточнения – как процесс обучения системы. Поскольку веса существенно влияют на распространение активности по сети, от них во многом зависит и поведение сети, а следовательно, изменяя веса, можно изменять поведение сети в желаемом направлении.

Как отмечено выше, знания в сети связности представлены неявно, поскольку нельзя выделить один определенный структурный элемент сети, который представлял бы отдельное правило или сущность предметной области. Знание отражено именно во взвешенных связях между мириадами отдельных элементов сети. Таким образом, в данном случае мы имеем дело с распределенными знаниями, которые нельзя представить в виде простого перечисления числовых или символических элементов. По этой причине часто можно встретить утверждение, что в нейронных сетях выполняется субсимволическая обработка информации.

В сетях связности знания сохраняются не в декларативном виде, а потому они не могут быть доступны для интерпретации со стороны какого-либо внешнего процессора. Доступ к знаниям и процесс логического вывода могут быть описаны только в терминах активности сети.

Нейро-нечеткие сети и модели

Объединение возможностей нейронных сетей и нечеткой логики является наиболее перспективным подходом к организации систем интеллектуального анализа данных. Системы нечеткой логики компенсируют две основные «непрозрачности» НС в представлении знаний и объяснений результатов работы интеллектуальной системы, т.е. НЛ наилучшим образом дополняет нейронные сети.

Нечеткая логика позволяет формализовать качественную информацию, полученную от экспертов-экономистов для конкретной сферы применения, и представить совокупность полученных знаний в виде системы нечетких правил логического вывода, позволяющих анализировать заключения, полученные в процессе работы гибридной интеллектуальной системы.

Нейронные сети дают возможность отобразить алгоритмы нечеткого логического вывода в структуре НС, вводя в информационное поле нейронной сети информацию, полученную от экспертов-экономистов.

Сформированная подобным образом база знаний автоматически корректируется в процессе обучения нейро-нечеткой сети исходя из реальных значений анализируемых экономических показателей и результаты коррекции могут быть подвергнута последующему анализу.

Нейро-нечеткие модели могут быть реализованы несколькими способами. В простейшем случае совместную модель можно рассматривать, как препроцессор, где механизм обучения искусственной нейронной сети (ANN) определяет правила нечеткого вывода (FIS). Как только параметры FIS определяются, ANN работает в обычном режиме. Функции принадлежности обычно аппроксимируются нейронной сетью из обучающих данных.

Другой подход в реализации нейро-нечетких моделей – это параллельная модель, которой нейронная сеть помогает нечёткой системе определить требующиеся параметры, особенно если входные переменные системы не могут быть непосредственно измерены. Обучение происходит только в нейронной сети, и нечёткая система остаётся неизменной.

В некоторых случаях нечёткие выходы не могут быть непосредственно применены к процессу. В этом случае нейронная сеть может действовать как постпроцессор нечётких выходов.

Наиболее распространенной являются интегрированные модели, в которых обучающий алгоритм нейронной сети используется для определения параметров системы нечёткого вывода. Нечёткая система вывода и соответствующие функции принадлежности базируются на априорных знаниях системы. С другой стороны, механизм обучения нейронной сети не зависит от априорной информации, а является стандартным для выбранной архитектуры искусственной нейронной сети.

3. Генетические алгоритмы

Генетический алгоритм – это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде.

Генетический алгоритм – новейший, но не единственно возможный способ решения задач оптимизации. С давних пор известны два основных пути решения таких задач – переборный и локально-градиентный. У этих методов свои достоинства и недостатки, и в каждом конкретном случае следует подумать, какой из них выбрать.

Если на некотором множестве задана сложная функция от нескольких переменных, то генетический алгоритм – это программа, которая за разумное время находит точку, где значение функции достаточно близко к максимально возможному. Выбирая приемлемое время расчета, мы получим одно из лучших решений, которые вообще возможно получить за это время.

Итак, Генетические алгоритмы – универсальные алгоритмы поиска, основанные на принципе развития, наблюдаемого в природе, сочетают в себе лучшие качества известных методов оптимизации, такие как высокая скорость работы при независимости от свойств используемого критерия оптимизации (например, гладкости функции). Они обеспечивают поиск оптимального значения параметров в широкой области их значений. Название – Генетические Алгоритмы – связано с тем, что они работают аналогично естественному отбору в природе. Поэтому в описаниях этих алгоритмов используются термины из биологии и генетики, такие как – Ген, Хромосома, Фитнесс, Популяция и другие.

Генетический алгоритм – это в первую очередь эволюционный алгоритм, другими словами, основная фишка алгоритма – скрещивание (комбинирование). Как несложно догадаться идея алгоритма взята у природы, путем перебора и самое главное отбора получается правильная «комбинация».

Алгоритм делится на три этапа:

– Скрещивание.

– Селекция (отбор).

– Формирования нового поколения.

Если результат нас не устраивает, эти шаги повторяются до тех пор, пока результат нас не начнет удовлетворять или произойдет одно из ниже перечисленных условий:

– Количество поколений (циклов) достигнет заранее выбранного максимума.

– Исчерпано время на мутацию.

Создание новой популяции. На этом шаге создается начальная популяция, которая, вполне возможно, окажется не кошерной, однако велика вероятность, что алгоритм эту проблему исправит. Главное, чтобы они соответствовали «формату» и были «приспособлены к размножению».

Размножение. Тут все как у людей, для получения потомка требуется два родителя. Главное, чтобы потомок (ребенок) мог унаследовать у родителей их черты. При этом размножаются все, а не только выжившие (эта фраза особенно абсурдна, но так как у нас все в сферическом вакууме, то можно все), в противном случае выделится один альфа самец, гены которого перекроют всех остальных, а нам это принципиально не приемлемо.

Мутации. Мутации схожи с размножением, из мутантов выбирают некое количество особей и изменяют их в соответствии с заранее определенными операциями.

Отбор. Тут начинается самое сладкое, мы начинаем выбирать из популяции долю тех, кто «пойдет дальше». При этом долю «выживших» после нашего отбора мы определяем заранее руками, указывая в виде параметра. Как ни печально, остальные особи должны погибнуть.

Вы успешно прослушали «сказку» про чудо-алгоритм и вполне возможно заждались, когда мы его начнем эксплуатировать наконец, хочу вас обрадовать, время настало.

Давайте рассмотрим на примере моих любимых Диофантовых уравнений (Уравнения с целочисленными корнями).

Наше уравнение: a + 2b + 3c + 4d = 30.

Вы наверно уже подозреваете, что корни данного уравнения лежат на отрезке [1; 30], поэтому мы берем 5 случайных значений a, b, c, d. (Ограничение в 30 взято специально для упрощения задачи).

И так, у нас есть первое поколение:

(1, 28, 15, 3)

(14, 9, 2, 4)

(13, 5, 7, 3)

(23, 8, 16, 19)

(9, 13, 5, 2)

Для того чтобы вычислить коэффициенты выживаемости, подставим каждое решение в выражение. Расстояние от полученного значения до 30 и будет нужным значением.

Меньшие значения ближе к 30, соответственно они более желанны. Получается, что большие значения будут иметь меньший коэффициент выживаемости. Для создания системы вычислим вероятность выбора каждой (хромосомы). Но решение заключается в том, чтобы взять сумму обратных значений коэффициентов, и исходя из этого вычислять проценты. (P.S. 0.135266 – сумма обратных коэффициентов)

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

3–1, 5–2, 3–5, 2–5, 5–3.

Как было сказано ранее, потомок содержит информацию о генах отца и матери. Это можно обеспечить различными способами, но в данном случае будет использоваться «кроссовер». (| = разделительная линия)

Х. – отец: a1 | b1,c1, d1 Х. – мать: a2 | b2,c2,d2 Х. – потомок: a1,b2,c2,d2 or a2,b1,c1,d1.

Х. – отец: a1,b1 | c1,d1 Х. – мать: a2,b2 | c2,d2 Х. – потомок: a1,b1,c2,d2 or a2,b2,c1,d1.

Х. – отец: a1,b1,c1 | d1 Х. – мать: a2,b2,c2 | d2 Х. – потомок: a1,b1,c1,d2 or a2,b2,c2,d1.

Есть очень много путей передачи информации потомку, а кроссовер – только один из множества. Расположение разделителя может быть абсолютно произвольным, как и то, отец или мать будут слева от черты.

А теперь сделаем тоже самое с потомками:

Х. – отец: (13 | 5,7,3) Х. – мать: (1 | 28,15,3) Х. – потомок: (13,28,15,3).

Х. – отец: (9,13 | 5,2) Х. – мать: (14,9 | 2,4) Х. – потомок: (9,13,2,4).

Х. – отец: (13,5,7 | 3) Х. – мать: (9,13,5 | 2) Х. – потомок: (13,5,7,2).

Х. – отец: (14 | 9,2,4) Х. – мать: (9 | 13,5,2) Х. – потомок: (14,13,5,2).

Х. – отец: (13,5 | 7, 3) Х. – мать: (9,13 | 5, 2) Х. – потомок: (13,5,5,2).

Теперь вычислим коэффициенты выживаемости потомков.

(13,28,15,3) – |126 – 30| = 96(9,13,2,4) – |57 – 30| = 27;

(13,5,7,2) – |57 – 30| = 22;

(14,13,5,2) – |63 – 30| = 33;

(13,5,5,2) – |46 – 30| = 16.

Печально так как средняя приспособленность (fitness) потомков оказалась 38,8, а у родителей этот коэффициент равнялся 59,4. Именно в этот момент целесообразнее использовать мутацию, для этого заменим один или более значений на случайное число от 1 до 30.

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

Системы с большей популяцией (например, 50 вместо 5-и сходятся к желаемому уровню (0) более быстро и стабильно.

Код

На этом простота заканчивается и начинается чудесный C++...

Класс на C++ требует 5 значений при инициализации: 4 коэффициента и результат. Для вышепривиденного примера это будет выглядеть так: CDiophantine dp(1,2,3,4,30);

Затем, чтобы решить уравнение, вызовите функцию Solve(), которая возвратит аллель, содержащую решение. Вызовите GetGene(), чтобы получить ген с правильными значениями a, b, c, d. Стандартная процедура main.cpp, использующая этот класс, может быть такой:

Задания. Программно реализовать генетический алгоритм Дать анализ полученных результатов, провести сравнения генетических алгоритмов с другими алгоритмами оптимизации.

Заключение. Даны теоретические сведения по интеллектуальны моделям в управлении, рассмотрены нейро-нечеткие модели, генетические алгоритмы. Приведен пример к использованию генетических алгоритмов.

Контрольные вопросы

1. Структура систем интеллектуального управления.

2. Математическая модель интеллектуального преобразователя.

3. Структурная схема системы интеллектуального управления с динамической экспертной системой.

4. Экспертные системы.

5. Структура и основные блоки экспертной системы.

6. Нейронные сети.

7. Нейро-нечеткие модели.

8. Адаптивная нейро-нечеткая система вывода – ANFIS.

9. Совместная нейро-нечеткая модель.

10. Параллельная нейро-нечёткая модель.

11. Генетические алгоритмы.