Материал: Задача линейного целочисленного программирования с булевыми переменными
Задача линейного целочисленного программирования с булевыми переменными
1. Задание на курсовую работу
Имеется m списков длиной n элементов каждый, в которых в разном порядке расположены одни и те же элементы.
Требуется:
Составить результатный (компромиссный) список, наименее уклоняющийся от исходных списков (в смысле потери места каждым элементом).
Показать, как изменится решение, если:
элемент а1 закрепить на первом месте, а а4 на пятом,
списки имеют разный приоритет: w1=0.3, w2=0.7;
Привести примеры практически возможных ситуаций, в которых могут возникать такие списки, из которых в последующем формируется один.
Исходные данные
Таблица 1
|
Список |
Элементы |
|||||||||
|
1 |
a7 |
a2 |
a10 |
a4 |
a6 |
a9 |
a1 |
a8 |
a5 |
a3 |
|
2 |
a1 |
a7 |
a6 |
a9 |
a2 |
a5 |
a10 |
a3 |
a4 |
a8 |
2. Расчетно-пояснительная часть
.1 Построение математической модели
задачи
В качестве переменных примем булевы переменные, имеющие следующий смысл:
, если i-ый элемент стоит на j-ой позиции в результирующем списке
, иначе
при i = 1,2,…,n и j = 1,2,…,n
В качестве критерия принимаем общую (суммарную)
величину потерь мест каждым элементом при установке в компромиссный список,
которую нужно минимизировать.
где С - величина потери места i-ым
элементом в установке его на j-е место в компромиссном списке.
Cij - показывает на сколько i-ый элемент
результирующего списка будет отклоняться от исходных списков, если он будет
стоять на j-ой позиции в результирующем списке.
Где k - текущий список- количество списков- текущее положение в списке
Условия:
а) Каждый элемент должен войти в компромиссный список ровно один раз:
б) В каждую позицию в компромиссном списке
должен войти ровно один элемент
Посчитаем цену перемещения элементов
Таблица 2
|
i\j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||||||||||
|
1 |
6 |
6 |
6 |
6 |
6 |
6 |
8 |
10 |
12 |
|||||||||||
|
2 |
5 |
3 |
3 |
3 |
3 |
5 |
7 |
9 |
11 |
13 |
||||||||||
|
3 |
16 |
14 |
12 |
10 |
8 |
6 |
4 |
2 |
2 |
2 |
||||||||||
|
4 |
11 |
9 |
7 |
5 |
5 |
5 |
5 |
5 |
5 |
7 |
||||||||||
|
5 |
13 |
11 |
9 |
7 |
5 |
3 |
3 |
3 |
3 |
5 |
||||||||||
|
6 |
6 |
4 |
2 |
2 |
2 |
4 |
6 |
8 |
10 |
12 |
||||||||||
|
7 |
1 |
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
17 |
16 |
14 |
12 |
10 |
8 |
6 |
4 |
2 |
2 |
2 |
|
9 |
8 |
6 |
4 |
2 |
2 |
2 |
4 |
6 |
8 |
10 |
||||||||||
|
10 |
8 |
6 |
4 |
4 |
4 |
4 |
4 |
6 |
8 |
10 |
Составим модель задачи.
X1_1+6 X1_2+6 X1_3+6 X1_4+6 X1_5+6 X1_6+6 X1_7+8 X1_8+10 X1_9+12 X1_10+
X2_1+3 X2_2+3 X2_3+3 X2_4+3 X2_5+5 X2_6+7 X2_7+9 X2_8+11 X2_9+13 X2_10+
X3_1+14 X3_2+12 X3_3+10 X3_4+8 X3_5+6 X3_6+4 X3_7+2 X3_8+2 X3_9+2 X3_10+
X4_1+9 X4_2+7 X4_3+5 X4_4+5 X4_5+5 X4_6+5 X4_7+5 X4_8+5 X4_9+7 X4_10+
X5_1+11 X5_2+9 X5_3+7 X5_4+5 X5_5+3 X5_6+3 X5_7+3 X5_8+3 X5_9+5 X5_10+
X6_1+4 X6_2+2 X6_3+2 X6_4+2 X6_5+4 X6_6+6 X6_7+8 X6_8+10 X6_9+12 X6_10+
X7_1+1 X7_2+3 X7_3+5 X7_4+7 X7_5+9 X7_6+11 X7_7+13 X7_8+15 X7_9+17 X7_10+
X8_1+14 X8_2+12 X8_3+10 X8_4+8 X8_5+6 X8_6+4 X8_7+2 X8_8+2 X8_9+2 X8_10+
X9_1+6 X9_2+4 X9_3+2 X9_4+2 X9_5+2 X9_6+4 X9_7+6 X9_8+8 X9_9+10 X9_10+
X10_1+6 X10_2+4 X10_3+4 X10_4+4 X10_5+4 X10_6+4 X10_7+6 X10_8+8 X10_9+10 X10_10
каждый элемент должен один раз войти в компромиссный список_1 + X1_2 + X1_3 + X1_4 + X1_5 + X1_6 + X1_7 + X1_8 + X1_9 + X1_10 = 1_1 + X2_2 + X2_3 + X2_4 + X2_5 + X2_6 + X2_7 + X2_8 + X2_9 + X2_10 = 1_1 + X3_2 + X3_3 + X3_4 + X3_5 + X3_6 + X3_7 + X3_8 + X3_9 + X3_10 = 1_1 + X4_2 + X4_3 + X4_4 + X4_5 + X4_6 + X4_7 + X4_8 + X4_9 + X4_10 = 1_1 + X5_2 + X5_3 + X5_4 + X5_5 + X5_6 + X5_7 + X5_8 + X5_9 + X5_10 = 1_1 + X6_2 + X6_3 + X6_4 + X6_5 + X6_6 + X6_7 + X6_8 + X6_9 + X6_10 = 1_1 + X7_2 + X7_3 + X7_4 + X7_5 + X7_6 + X7_7 + X7_8 + X7_9 + X7_10 = 1_1 + X8_2 + X8_3 + X8_4 + X8_5 + X8_6 + X8_7 + X8_8 + X8_9 + X8_10 = 1_1 + X9_2 + X9_3 + X9_4 + X9_5 + X9_6 + X9_7 + X9_8 + X9_9 + X9_10 = 1_1 + X10_2 + X10_3 + X10_4 + X10_5 + X10_6 + X10_7 + X10_8 + X10_9 + X10_10 = 1
в каждую позицию компромиссного списка должен войти, только один элемент_1 + X2_1 + X3_1 + X4_1 + X5_1 + X6_1 + X7_1 + X8_1 + X9_1 + X10_1 = 1_2 + X2_2 + X3_2 + X4_2 + X5_2 + X6_2 + X7_2 + X8_2 + X9_2 + X10_2 = 1_3 + X2_3 + X3_3 + X4_3 + X5_3 + X6_3 + X7_3 + X8_3 + X9_3 + X10_3 = 1_4 + X2_4 + X3_4 + X4_4 + X5_4 + X6_4 + X7_4 + X8_4 + X9_4 + X10_4 = 1_5 + X2_5 + X3_5 + X4_5 + X5_5 + X6_5 + X7_5 + X8_5 + X9_5 + X10_5 = 1_6 + X2_6 + X3_6 + X4_6 + X5_6 + X6_6 + X7_6 + X8_6 + X9_6 + X10_6 = 1_7 + X2_7 + X3_7 + X4_7 + X5_7 + X6_7 + X7_7 + X8_7 + X9_7 + X10_7 = 1_8 + X2_8 + X3_8 + X4_8 + X5_8 + X6_8 + X7_8 + X8_8 + X9_8 + X10_8 = 1_9 + X2_9 + X3_9 + X4_9 + X5_9 + X6_9 + X7_9 + X8_9 + X9_9 + X10_9 = 1_10 + X2_10 + X3_10 + X4_10 + X5_10 + X6_10 + X7_10 + X8_10 + X9_10 + X10_10 = 1
end100
Вывод программы.OPTIMUM FOUND AT STEP 30VALUE = 30.0000000ALL VARS.( 60) WITH RC > 2.00000INTEGER SOLUTION OF 30.0000000 AT BRANCH 0 PIVOT 30ON OPTIMUM: 30.00000COMPLETE. BRANCHES= 0 PIVOTS= 30INTEGER SOLUTION IS THE BEST FOUNDINSTALLING BEST SOLUTION...FUNCTION VALUE
) 30.00000VALUE REDUCED COST_1 0.000000 6.000000_2 0.000000 6.000000_3 0.000000 6.000000_4 0.000000 6.000000_5 0.000000 6.000000_6 1.000000 6.000000_7 0.000000 6.000000_8 0.000000 8.000000_9 0.000000 10.000000_10 0.000000 12.000000_1 0.000000 5.000000_2 1.000000 3.000000_3 0.000000 3.000000_4 0.000000 3.000000_5 0.000000 3.000000_6 0.000000 5.000000_7 0.000000 7.000000_8 0.000000 9.000000_9 0.000000 11.000000_10 0.000000 13.000000_1 0.000000 16.000000_2 0.000000 14.000000_3 0.000000 12.000000_4 0.000000 10.000000_5 0.000000 8.000000_6 0.000000 6.000000_7 0.000000 4.000000_8 1.000000 2.000000_9 0.000000 2.000000_10 0.000000 2.000000_1 0.000000 11.000000_2 0.000000 9.000000_3 0.000000 7.000000_4 0.000000 5.000000_5 0.000000 5.000000_6 0.000000 5.000000_7 0.000000 5.000000_8 0.000000 5.000000_9 1.000000 5.000000_10 0.000000 7.000000_1 0.000000 13.000000_2 0.000000 11.000000_3 0.000000 9.000000_4 0.000000 7.000000_5 0.000000 5.000000_6 0.000000 3.000000_7 1.000000 3.000000_8 0.000000 3.000000_9 0.000000 3.000000_10 0.000000 5.000000_1 0.000000 6.000000_2 0.000000 4.000000_3 0.000000 2.000000_4 0.000000 2.000000_5 1.000000 2.000000_6 0.000000 4.000000_7 0.000000 6.000000_8 0.000000 8.000000_9 0.000000 10.000000_10 0.000000 12.000000_1 1.000000 1.000000_2 0.000000 1.000000_3 0.000000 3.000000_4 0.000000 5.000000_5 0.000000 7.000000_6 0.000000 9.000000_7 0.000000 11.000000_8 0.000000 13.000000_9 0.000000 15.000000_10 0.000000 17.000000_1 0.000000 16.000000_2 0.000000 14.000000_3 0.000000 12.000000_4 0.000000 10.000000_5 0.000000 8.000000_6 0.000000 6.000000_7 0.000000 4.000000_8 0.000000 2.000000_9 0.000000 2.000000_10 1.000000 2.000000_1 0.000000 8.000000_2 0.000000 6.000000_3 0.000000 4.000000_4 1.000000 2.000000_5 0.000000 2.000000_6 0.000000 2.000000_7 0.000000 4.000000_8 0.000000 6.000000_9 0.000000 8.000000_10 0.000000 10.000000_1 0.000000 8.000000_2 0.000000 6.000000_3 1.000000 4.000000_4 0.000000 4.000000_5 0.000000 4.000000_6 0.000000 4.000000_7 0.000000 4.000000_8 0.000000 6.000000_9 0.000000 8.000000_10 0.000000 10.000000. ITERATIONS= 30
BRANCHES= 0 DETERM.= 1.000E 0
Из данного решения следует, что оптимальное
значение L = 30, компромиссный список имеет вид.
Таблица 3
|
Элемент |
a7 |
a2 |
a10 |
a9 |
a6 |
a1 |
a5 |
a3 |
a4 |
a8 |
|
Стоимость |
1 |
3 |
4 |
2 |
2 |
6 |
3 |
5 |
2 |
Что бы показать, как измениться решение при закреплении элемента а1 на первом месте, а а4 на пятом, отредактируем условие._1 = 1!зафексировали элемент а1 на первом месте_1 + X2_2 + X2_3 + X2_4 + X2_5 + X2_6 + X2_7 + X2_8 + X2_9 + X2_10 = 1_1 + X3_2 + X3_3 + X3_4 + X3_5 + X3_6 + X3_7 + X3_8 + X3_9 + X3_10 = 1_5 =1 !зафиксировали элемент a4 на пятом месте_1 + X5_2 + X5_3 + X5_4 + X5_5 + X5_6 + X5_7 + X5_8 + X5_9 + X5_10 = 1_1 + X6_2 + X6_3 + X6_4 + X6_5 + X6_6 + X6_7 + X6_8 + X6_9 + X6_10 = 1_1 + X7_2 + X7_3 + X7_4 + X7_5 + X7_6 + X7_7 + X7_8 + X7_9 + X7_10 = 1_1 + X8_2 + X8_3 + X8_4 + X8_5 + X8_6 + X8_7 + X8_8 + X8_9 + X8_10 = 1_1 + X9_2 + X9_3 + X9_4 + X9_5 + X9_6 + X9_7 + X9_8 + X9_9 + X9_10 = 1_1 + X10_2 + X10_3 + X10_4 + X10_5 + X10_6 + X10_7 + X10_8 + X10_9 + X10_10 = 1_1 + X2_1 + X3_1 + X4_1 + X5_1 + X6_1 + X7_1 + X8_1 + X9_1 + X10_1 = 1_2 + X2_2 + X3_2 + X4_2 + X5_2 + X6_2 + X7_2 + X8_2 + X9_2 + X10_2 = 1_3 + X2_3 + X3_3 + X4_3 + X5_3 + X6_3 + X7_3 + X8_3 + X9_3 + X10_3 = 1_4 + X2_4 + X3_4 + X4_4 + X5_4 + X6_4 + X7_4 + X8_4 + X9_4 + X10_4 = 1_5 + X2_5 + X3_5 + X4_5 + X5_5 + X6_5 + X7_5 + X8_5 + X9_5 + X10_5 = 1_6 + X2_6 + X3_6 + X4_6 + X5_6 + X6_6 + X7_6 + X8_6 + X9_6 + X10_6 = 1_7 + X2_7 + X3_7 + X4_7 + X5_7 + X6_7 + X7_7 + X8_7 + X9_7 + X10_7 = 1_8 + X2_8 + X3_8 + X4_8 + X5_8 + X6_8 + X7_8 + X8_8 + X9_8 + X10_8 = 1_9 + X2_9 + X3_9 + X4_9 + X5_9 + X6_9 + X7_9 + X8_9 + X9_9 + X10_9 = 1_10 + X2_10 + X3_10 + X4_10 + X5_10 + X6_10 + X7_10 + X8_10 + X9_10 + X10_10 = 1
Вывод программы.OPTIMUM FOUND AT STEP 21VALUE = 30.0000000ALL VARS.(71) WITH RC > 2.00000INTEGER SOLUTION OF 30.0000000 AT BRANCH 0 PIVOT 21ON OPTIMUM: 30.00000COMPLETE. BRANCHES= 0 PIVOTS= 21INTEGER SOLUTION IS THE BEST FOUNDINSTALLING BEST SOLUTION...FUNCTION VALUE
) 30.00000VALUE REDUCED COST_1 1.000000 6.000000_2 0.000000 6.000000_3 0.000000 6.000000_4 0.000000 6.000000_5 0.000000 6.000000_6 0.000000 6.000000_7 0.000000 6.000000_8 0.000000 8.000000_9 0.000000 10.000000_10 0.000000 12.000000_1 0.000000 5.000000_2 0.000000 3.000000_3 1.000000 3.000000_4 0.000000 3.000000_5 0.000000 3.000000_6 0.000000 5.000000_7 0.000000 7.000000_8 0.000000 9.000000_9 0.000000 11.000000_10 0.000000 13.000000_1 0.000000 16.000000_2 0.000000 14.000000_3 0.000000 12.000000_4 0.000000 10.000000_5 0.000000 8.000000_6 0.000000 6.000000_7 0.000000 4.000000_8 1.000000 2.000000_9 0.000000 2.000000_10 0.000000 2.000000_1 0.000000 11.000000_2 0.000000 9.000000_3 0.000000 7.000000_4 0.000000 5.000000_5 1.000000 5.000000_6 0.000000 5.000000_7 0.000000 5.000000_8 0.000000 5.000000_9 0.000000 5.000000_10 0.000000 7.000000_1 0.000000 13.000000_2 0.000000 11.000000_3 0.000000 9.000000_4 0.000000 7.000000_5 0.000000 5.000000_6 0.000000 3.000000_7 0.000000 3.000000_8 0.000000 3.000000_9 1.000000 3.000000_10 0.000000 5.000000_1 0.000000 6.000000_2 0.000000 4.000000_3 0.000000 2.000000_4 1.000000 2.000000_5 0.000000 2.000000_6 0.000000 4.000000_7 0.000000 6.000000_8 0.000000 8.000000_9 0.000000 10.000000_10 0.000000 12.000000_1 0.000000 1.000000_2 1.000000 1.000000_3 0.000000 3.000000_4 0.000000 5.000000_5 0.000000 7.000000_6 0.000000 9.000000_7 0.000000 11.000000_8 0.000000 13.000000_9 0.000000 15.000000_10 0.000000 17.000000_1 0.000000 16.000000_2 0.000000 14.000000_3 0.000000 12.000000_4 0.000000 10.000000_5 0.000000 8.000000_6 0.000000 6.000000_7 0.000000 4.000000_8 0.000000 2.000000_9 0.000000 2.000000_10 1.000000 2.000000_1 0.000000 8.000000_2 0.000000 6.000000_3 0.000000 4.000000_4 0.000000 2.000000_5 0.000000 2.000000_6 1.000000 2.000000_7 0.000000 4.000000_8 0.000000 6.000000_9 0.000000 8.000000_10 0.000000 10.000000_1 0.000000 8.000000_2 0.000000 6.000000_3 0.000000 4.000000_4 0.000000 4.000000_5 0.000000 4.000000_6 0.000000 4.000000_7 1.000000 4.000000_8 0.000000 6.000000_9 0.000000 8.000000_10 0.000000 10.000000. ITERATIONS= 21
BRANCHES= 0 DETERM.= 1.000E 0
Из данного решения следует, что оптимальное
значение L = 30, компромиссный список имеет вид.
Таблица 4
|
Элемент |
a1 |
a7 |
a2 |
a6 |
a4 |
a9 |
a10 |
a3 |
a5 |
a8 |
|
Стоимость |
6 |
1 |
3 |
2 |
5 |
2 |
4 |
2 |
3 |
2 |
В случае когда, списки имеют разный приоритет,
нужно помножить цену потери места на приоритет - w.
Тогда матрица оценок для задачи
примет следующий вид.
Таблица 5
|
i\j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
1 |
1,8 |
2,2 |
2,6 |
3 |
3,4 |
3,8 |
4,2 |
5,2 |
6,2 |
7,2 |
|
2 |
3,1 |
2,1 |
1,7 |
1,3 |
0,9 |
1,9 |
2,9 |
3,9 |
4,9 |
5,9 |
|
3 |
7,6 |
6,6 |
4,6 |
3,6 |
2,6 |
1,6 |
0,6 |
1 |
1,4 |
|
|
4 |
6,5 |
5,5 |
4,5 |
3,5 |
3,1 |
2,7 |
2,3 |
1,9 |
1,5 |
2,5 |
|
5 |
5,9 |
4,9 |
3,9 |
2,9 |
1,9 |
0,9 |
1,3 |
1,7 |
2,1 |
3,1 |
|
6 |
2,6 |
1,6 |
0,6 |
1 |
1,4 |
2,4 |
3,4 |
4,4 |
5,4 |
6,4 |
|
7 |
0,7 |
0,3 |
1,3 |
2,3 |
3,3 |
4,3 |
5,3 |
6,3 |
7,3 |
8,3 |
|
8 |
8,4 |
7,4 |
6,4 |
5,4 |
4,4 |
3,4 |
2,4 |
1,4 |
1 |
0,6 |
|
9 |
3,6 |
2,6 |
1,6 |
0,6 |
1 |
1,4 |
2,4 |
4,4 |
5,4 |
|
|
10 |
4,8 |
3,8 |
2,8 |
2,4 |
2 |
1,6 |
1,2 |
2,2 |
3,2 |
4,2 |
Изменим критерий модели задачи.
.8 X1_1 + 2.2 X1_2 + 2.6 X1_3 + 3.0 X1_4 + 3.4 X1_5 + 3.8 X1_6 + 4.2 X1_7 + 5.2 X1_8 + 6.2 X1_9 + 7.2 X1_10 +
.1 X2_1 + 2.1 X2_2 + 1.7 X2_3 + 1.3 X2_4 + 0.9 X2_5 + 1.9 X2_6 + 2.9 X2_7 + 3.9 X2_8 + 4.9 X2_9 + 5.9 X2_10 +
.6 X3_1 + 6.6 X3_2 + 5.6 X3_3 + 4.6 X3_4 + 3.6 X3_5 + 2.6 X3_6 + 1.6 X3_7 + 0.6 X3_8 + 1.0 X3_9 + 1.4 X3_10 +
.5 X4_1 + 5.5 X4_2 + 4.5 X4_3 + 3.5 X4_4 + 3.1 X4_5 + 2.7 X4_6 + 2.3 X4_7 + 1.9 X4_8 + 1.5 X4_9 + 2.5 X4_10 +
.9 X5_1 + 4.9 X5_2 + 3.9 X5_3 + 2.9 X5_4 + 1.9 X5_5 + 0.9 X5_6 + 1.3 X5_7 + 1.7 X5_8 + 2.1 X5_9 + 3.1 X5_10 +
.6 X6_1 + 1.6 X6_2 + 0.6 X6_3 + 1.0 X6_4 + 1.4 X6_5 + 2.4 X6_6 + 3.4 X6_7 + 4.4 X6_8 + 5.4 X6_9 + 6.4 X6_10 +
.7 X7_1 + 0.3 X7_2 + 1.3 X7_3 + 2.3 X7_4 + 3.3 X7_5 + 4.3 X7_6 + 5.3 X7_7 + 6.3 X7_8 + 7.3 X7_9 + 8.3 X7_10 +
.4 X8_1 + 7.4 X8_2 + 6.4 X8_3 + 5.4 X8_4 + 4.4 X8_5 + 3.4 X8_6 + 2.4 X8_7 + 1.4 X8_8 + 1.0 X8_9 + 0.6 X8_10 +
.6 X9_1 + 2.6 X9_2 + 1.6 X9_3 + 0.6 X9_4 + 1.0 X9_5 + 1.4 X9_6 + 2.4 X9_7 + 3.4 X9_8 + 4.4 X9_9 + 5.4 X9_10 +
.8 X10_1 + 3.8 X10_2 + 2.8 X10_3 + 2.4 X10_4 + 2.0 X10_5 + 1.6 X10_6 + 1.2 X10_7 + 2.2 X10_8 + 3.2 X10_9 + 4.2 X10_10
Вывод LINDO с данными критерием:
FIX ALL VARS.(82) WITH RC > 0.500000INTEGER SOLUTION OF 9.00000000 AT BRANCH 0 PIVOT 13ON OPTIMUM: 9.000000COMPLETE. BRANCHES= 0 PIVOTS= 13INTEGER SOLUTION IS THE BEST FOUNDINSTALLING BEST SOLUTION...FUNCTION VALUE
) 9.000000VALUE REDUCED COST_1 1.000000 1.800000_2 0.000000 2.200000_3 0.000000 2.600000_4 0.000000 3.000000_5 0.000000 3.400000_6 0.000000 3.800000_7 0.000000 4.200000_8 0.000000 5.200000_9 0.000000 6.200000_10 0.000000 7.200000_1 0.000000 3.100000_2 0.000000 2.100000_3 0.000000 1.700000_4 0.000000 1.300000_5 1.000000 0.900000_6 0.000000 1.900000_7 0.000000 2.900000_8 0.000000 3.900000_9 0.000000 4.900000_10 0.000000 5.900000_1 0.000000 7.600000_2 0.000000 6.600000_3 0.000000 5.600000_4 0.000000 4.600000_5 0.000000 3.600000_6 0.000000 2.600000_7 0.000000 1.600000_8 1.000000 0.600000_9 0.000000 1.000000_10 0.000000 1.400000_1 0.000000 6.500000_2 0.000000 5.500000_3 0.000000 4.500000_4 0.000000 3.500000_5 0.000000 3.100000_6 0.000000 2.700000_7 0.000000 2.300000_8 0.000000 1.900000_9 1.000000 1.500000_10 0.000000 2.500000_1 0.000000 5.900000_2 0.000000 4.900000_3 0.000000 3.900000_4 0.000000 2.900000_5 0.000000 1.900000_6 1.000000 0.900000_7 0.000000 1.300000_8 0.000000 1.700000_9 0.000000 2.100000_10 0.000000 3.100000_1 0.000000 2.600000_2 0.000000 1.600000_3 1.000000 0.600000_4 0.000000 1.000000_5 0.000000 1.400000_6 0.000000 2.400000_7 0.000000 3.400000_8 0.000000 4.400000_9 0.000000 5.400000_10 0.000000 6.400000_1 0.000000 0.700000_2 1.000000 0.300000_3 0.000000 1.300000_4 0.000000 2.300000_5 0.000000 3.300000_6 0.000000 4.300000_7 0.000000 5.300000_8 0.000000 6.300000_9 0.000000 7.300000_10 0.000000 8.300000_1 0.000000 8.400000_2 0.000000 7.400000_3 0.000000 6.400000_4 0.000000 5.400000_5 0.000000 4.400000_6 0.000000 3.400000_7 0.000000 2.400000_8 0.000000 1.400000_9 0.000000 1.000000_10 1.000000 0.600000_1 0.000000 3.600000_2 0.000000 2.600000_3 0.000000 1.600000_4 1.000000 0.600000_5 0.000000 1.000000_6 0.000000 1.400000_7 0.000000 2.400000_8 0.000000 3.400000_9 0.000000 4.400000_10 0.000000 5.400000_1 0.000000 4.800000_2 0.000000 3.800000_3 0.000000 2.800000_4 0.000000 2.400000_5 0.000000 2.000000_6 0.000000 1.600000_7 1.000000 1.200000_8 0.000000 2.200000_9 0.000000 3.200000_10 0.000000 4.200000. ITERATIONS= 13
BRANCHES= 0 DETERM.= 1.000E 0
Из данного решения следует, что оптимальное значение L = 9,
Оптимальное решение в виде компромиссного списка
имеет вид:
Таблица 6
|
Элемент |
a1 |
a7 |
a6 |
a9 |
a2 |
a5 |
a10 |
a3 |
a4 |
a8 |
|
Стоимость |
1.8 |
0.3 |
0.6 |
0.6 |
0.9 |
0.9 |
1.2 |
0.6 |
1.5 |
0.6 |
По данным, указанными в таблице 6, видно, что
элементы компромиссного списка, остались на местах списка с более высоким
приоритетом.
3. Пример задачи
Суть задачи из данного варианта заключается в
том, что один ресурс можно применить, только к одному объекту, в качестве
примера можно привести распределение рабочих по местам, так чтобы
минимизировать время производства продукции.