Задача линейного целочисленного программирования с булевыми переменными
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. Пример задачи
Суть задачи из данного варианта заключается в
том, что один ресурс можно применить, только к одному объекту, в качестве
примера можно привести распределение рабочих по местам, так чтобы
минимизировать время производства продукции.
Заключение
компромиссный список задача
программа
В курсовой работе рассмотрена задача линейного
целочисленного программирования с булевыми переменными.
Была составлена математическая модель задачи и
получено оптимальное решение при помощи программного пакета LINDO. Было так же
рассмотрено решение задачи со списками имеющие разный приоритет.
Список литературы
1. Гольдштейн
А.Л. Оптимизация в LINDO / Перм. гос. техн. ун-т, Пермь, 2000. - 88 с.
. Юдин
Д.Б., Гольдштейн Е.Г. Задачи и методы линейного программирования / М.: «Сов.
радио»,1961 - 494 с.