Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Задача линейного целочисленного программирования с булевыми переменными

Задача линейного целочисленного программирования с булевыми переменными

Решение задачи на составление компромиссного списка. Построение математической модели. Цена перемещения элементов. Вывод программы. Закреплении элемента а1 на первом месте, а а4 на пятом. Матрица оценок для задачи. Оптимальное решение в виде списка.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 30.01.2016
Размер файла 37,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

[Введите текст]

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. Расчетно-пояснительная часть

2.1 Построение математической модели задачи

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

1, если i-ый элемент стоит на j-ой позиции в результирующем списке

0, иначе

при i = 1,2,…,n и j = 1,2,…,n

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

где С - величина потери места i-ым элементом в установке его на j-е место в компромиссном списке.

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

Где k -- текущий список

m - количество списков

A - текущее положение в списке

Условия:

а) Каждый элемент должен войти в компромиссный список ровно один раз:

б) В каждую позицию в компромиссном списке должен войти ровно один элемент

Посчитаем цену перемещения элементов

Таблица 2

i\j

1

2

3

4

5

6

7

8

9

10

1

6

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

8

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

Составим модель задачи.

min

6 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+

5 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+

16 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+

11 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+

13 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+

6 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+

1 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+

16 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+

8 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+

8 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

st

каждый элемент должен один раз войти в компромиссный список

X1_1 + X1_2 + X1_3 + X1_4 + X1_5 + X1_6 + X1_7 + X1_8 + X1_9 + X1_10 = 1

X2_1 + X2_2 + X2_3 + X2_4 + X2_5 + X2_6 + X2_7 + X2_8 + X2_9 + X2_10 = 1

X3_1 + X3_2 + X3_3 + X3_4 + X3_5 + X3_6 + X3_7 + X3_8 + X3_9 + X3_10 = 1

X4_1 + X4_2 + X4_3 + X4_4 + X4_5 + X4_6 + X4_7 + X4_8 + X4_9 + X4_10 = 1

X5_1 + X5_2 + X5_3 + X5_4 + X5_5 + X5_6 + X5_7 + X5_8 + X5_9 + X5_10 = 1

X6_1 + X6_2 + X6_3 + X6_4 + X6_5 + X6_6 + X6_7 + X6_8 + X6_9 + X6_10 = 1

X7_1 + X7_2 + X7_3 + X7_4 + X7_5 + X7_6 + X7_7 + X7_8 + X7_9 + X7_10 = 1

X8_1 + X8_2 + X8_3 + X8_4 + X8_5 + X8_6 + X8_7 + X8_8 + X8_9 + X8_10 = 1

X9_1 + X9_2 + X9_3 + X9_4 + X9_5 + X9_6 + X9_7 + X9_8 + X9_9 + X9_10 = 1

X10_1 + X10_2 + X10_3 + X10_4 + X10_5 + X10_6 + X10_7 + X10_8 + X10_9 + X10_10 = 1

в каждую позицию компромиссного списка должен войти, только один элемент

X1_1 + X2_1 + X3_1 + X4_1 + X5_1 + X6_1 + X7_1 + X8_1 + X9_1 + X10_1 = 1

X1_2 + X2_2 + X3_2 + X4_2 + X5_2 + X6_2 + X7_2 + X8_2 + X9_2 + X10_2 = 1

X1_3 + X2_3 + X3_3 + X4_3 + X5_3 + X6_3 + X7_3 + X8_3 + X9_3 + X10_3 = 1

X1_4 + X2_4 + X3_4 + X4_4 + X5_4 + X6_4 + X7_4 + X8_4 + X9_4 + X10_4 = 1

X1_5 + X2_5 + X3_5 + X4_5 + X5_5 + X6_5 + X7_5 + X8_5 + X9_5 + X10_5 = 1

X1_6 + X2_6 + X3_6 + X4_6 + X5_6 + X6_6 + X7_6 + X8_6 + X9_6 + X10_6 = 1

X1_7 + X2_7 + X3_7 + X4_7 + X5_7 + X6_7 + X7_7 + X8_7 + X9_7 + X10_7 = 1

X1_8 + X2_8 + X3_8 + X4_8 + X5_8 + X6_8 + X7_8 + X8_8 + X9_8 + X10_8 = 1

X1_9 + X2_9 + X3_9 + X4_9 + X5_9 + X6_9 + X7_9 + X8_9 + X9_9 + X10_9 = 1

X1_10 + X2_10 + X3_10 + X4_10 + X5_10 + X6_10 + X7_10 + X8_10 + X9_10 + X10_10 = 1

end

int 100

Вывод программы.

LP OPTIMUM FOUND AT STEP 30

OBJECTIVE VALUE = 30.0000000

FIX ALL VARS.( 60) WITH RC > 2.00000

NEW INTEGER SOLUTION OF 30.0000000 AT BRANCH 0 PIVOT 30

BOUND ON OPTIMUM: 30.00000

ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 30

LAST INTEGER SOLUTION IS THE BEST FOUND

RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE

1) 30.00000

VARIABLE VALUE REDUCED COST

X1_1 0.000000 6.000000

X1_2 0.000000 6.000000

X1_3 0.000000 6.000000

X1_4 0.000000 6.000000

X1_5 0.000000 6.000000

X1_6 1.000000 6.000000

X1_7 0.000000 6.000000

X1_8 0.000000 8.000000

X1_9 0.000000 10.000000

X1_10 0.000000 12.000000

X2_1 0.000000 5.000000

X2_2 1.000000 3.000000

X2_3 0.000000 3.000000

X2_4 0.000000 3.000000

X2_5 0.000000 3.000000

X2_6 0.000000 5.000000

X2_7 0.000000 7.000000

X2_8 0.000000 9.000000

X2_9 0.000000 11.000000

X2_10 0.000000 13.000000

X3_1 0.000000 16.000000

X3_2 0.000000 14.000000

X3_3 0.000000 12.000000

X3_4 0.000000 10.000000

X3_5 0.000000 8.000000

X3_6 0.000000 6.000000

X3_7 0.000000 4.000000

X3_8 1.000000 2.000000

X3_9 0.000000 2.000000

X3_10 0.000000 2.000000

X4_1 0.000000 11.000000

X4_2 0.000000 9.000000

X4_3 0.000000 7.000000

X4_4 0.000000 5.000000

X4_5 0.000000 5.000000

X4_6 0.000000 5.000000

X4_7 0.000000 5.000000

X4_8 0.000000 5.000000

X4_9 1.000000 5.000000

X4_10 0.000000 7.000000

X5_1 0.000000 13.000000

X5_2 0.000000 11.000000

X5_3 0.000000 9.000000

X5_4 0.000000 7.000000

X5_5 0.000000 5.000000

X5_6 0.000000 3.000000

X5_7 1.000000 3.000000

X5_8 0.000000 3.000000

X5_9 0.000000 3.000000

X5_10 0.000000 5.000000

X6_1 0.000000 6.000000

X6_2 0.000000 4.000000

X6_3 0.000000 2.000000

X6_4 0.000000 2.000000

X6_5 1.000000 2.000000

X6_6 0.000000 4.000000

X6_7 0.000000 6.000000

X6_8 0.000000 8.000000

X6_9 0.000000 10.000000

X6_10 0.000000 12.000000

X7_1 1.000000 1.000000

X7_2 0.000000 1.000000

X7_3 0.000000 3.000000

X7_4 0.000000 5.000000

X7_5 0.000000 7.000000

X7_6 0.000000 9.000000

X7_7 0.000000 11.000000

X7_8 0.000000 13.000000

X7_9 0.000000 15.000000

X7_10 0.000000 17.000000

X8_1 0.000000 16.000000

X8_2 0.000000 14.000000

X8_3 0.000000 12.000000

X8_4 0.000000 10.000000

X8_5 0.000000 8.000000

X8_6 0.000000 6.000000

X8_7 0.000000 4.000000

X8_8 0.000000 2.000000

X8_9 0.000000 2.000000

X8_10 1.000000 2.000000

X9_1 0.000000 8.000000

X9_2 0.000000 6.000000

X9_3 0.000000 4.000000

X9_4 1.000000 2.000000

X9_5 0.000000 2.000000

X9_6 0.000000 2.000000

X9_7 0.000000 4.000000

X9_8 0.000000 6.000000

X9_9 0.000000 8.000000

X9_10 0.000000 10.000000

X10_1 0.000000 8.000000

X10_2 0.000000 6.000000

X10_3 1.000000 4.000000

X10_4 0.000000 4.000000

X10_5 0.000000 4.000000

X10_6 0.000000 4.000000

X10_7 0.000000 4.000000

X10_8 0.000000 6.000000

X10_9 0.000000 8.000000

X10_10 0.000000 10.000000

NO. 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

2

5

2

Что бы показать, как измениться решение при закреплении элемента а1 на первом месте, а а4 на пятом, отредактируем условие.

st

X1_1 = 1!зафексировали элемент а1 на первом месте

X2_1 + X2_2 + X2_3 + X2_4 + X2_5 + X2_6 + X2_7 + X2_8 + X2_9 + X2_10 = 1

X3_1 + X3_2 + X3_3 + X3_4 + X3_5 + X3_6 + X3_7 + X3_8 + X3_9 + X3_10 = 1

X4_5 =1 !зафиксировали элемент a4 на пятом месте

X5_1 + X5_2 + X5_3 + X5_4 + X5_5 + X5_6 + X5_7 + X5_8 + X5_9 + X5_10 = 1

X6_1 + X6_2 + X6_3 + X6_4 + X6_5 + X6_6 + X6_7 + X6_8 + X6_9 + X6_10 = 1

X7_1 + X7_2 + X7_3 + X7_4 + X7_5 + X7_6 + X7_7 + X7_8 + X7_9 + X7_10 = 1

X8_1 + X8_2 + X8_3 + X8_4 + X8_5 + X8_6 + X8_7 + X8_8 + X8_9 + X8_10 = 1

X9_1 + X9_2 + X9_3 + X9_4 + X9_5 + X9_6 + X9_7 + X9_8 + X9_9 + X9_10 = 1

X10_1 + X10_2 + X10_3 + X10_4 + X10_5 + X10_6 + X10_7 + X10_8 + X10_9 + X10_10 = 1

X1_1 + X2_1 + X3_1 + X4_1 + X5_1 + X6_1 + X7_1 + X8_1 + X9_1 + X10_1 = 1

X1_2 + X2_2 + X3_2 + X4_2 + X5_2 + X6_2 + X7_2 + X8_2 + X9_2 + X10_2 = 1

X1_3 + X2_3 + X3_3 + X4_3 + X5_3 + X6_3 + X7_3 + X8_3 + X9_3 + X10_3 = 1

X1_4 + X2_4 + X3_4 + X4_4 + X5_4 + X6_4 + X7_4 + X8_4 + X9_4 + X10_4 = 1

X1_5 + X2_5 + X3_5 + X4_5 + X5_5 + X6_5 + X7_5 + X8_5 + X9_5 + X10_5 = 1

X1_6 + X2_6 + X3_6 + X4_6 + X5_6 + X6_6 + X7_6 + X8_6 + X9_6 + X10_6 = 1

X1_7 + X2_7 + X3_7 + X4_7 + X5_7 + X6_7 + X7_7 + X8_7 + X9_7 + X10_7 = 1

X1_8 + X2_8 + X3_8 + X4_8 + X5_8 + X6_8 + X7_8 + X8_8 + X9_8 + X10_8 = 1

X1_9 + X2_9 + X3_9 + X4_9 + X5_9 + X6_9 + X7_9 + X8_9 + X9_9 + X10_9 = 1

X1_10 + X2_10 + X3_10 + X4_10 + X5_10 + X6_10 + X7_10 + X8_10 + X9_10 + X10_10 = 1

Вывод программы.

LP OPTIMUM FOUND AT STEP 21

OBJECTIVE VALUE = 30.0000000

FIX ALL VARS.(71) WITH RC > 2.00000

NEW INTEGER SOLUTION OF 30.0000000 AT BRANCH 0 PIVOT 21

BOUND ON OPTIMUM: 30.00000

ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 21

LAST INTEGER SOLUTION IS THE BEST FOUND

RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE

1) 30.00000

VARIABLE VALUE REDUCED COST

X1_1 1.000000 6.000000

X1_2 0.000000 6.000000

X1_3 0.000000 6.000000

X1_4 0.000000 6.000000

X1_5 0.000000 6.000000

X1_6 0.000000 6.000000

X1_7 0.000000 6.000000

X1_8 0.000000 8.000000

X1_9 0.000000 10.000000

X1_10 0.000000 12.000000

X2_1 0.000000 5.000000

X2_2 0.000000 3.000000

X2_3 1.000000 3.000000

X2_4 0.000000 3.000000

X2_5 0.000000 3.000000

X2_6 0.000000 5.000000

X2_7 0.000000 7.000000

X2_8 0.000000 9.000000

X2_9 0.000000 11.000000

X2_10 0.000000 13.000000

X3_1 0.000000 16.000000

X3_2 0.000000 14.000000

X3_3 0.000000 12.000000

X3_4 0.000000 10.000000

X3_5 0.000000 8.000000

X3_6 0.000000 6.000000

X3_7 0.000000 4.000000

X3_8 1.000000 2.000000

X3_9 0.000000 2.000000

X3_10 0.000000 2.000000

X4_1 0.000000 11.000000

X4_2 0.000000 9.000000

X4_3 0.000000 7.000000

X4_4 0.000000 5.000000

X4_5 1.000000 5.000000

X4_6 0.000000 5.000000

X4_7 0.000000 5.000000

X4_8 0.000000 5.000000

X4_9 0.000000 5.000000

X4_10 0.000000 7.000000

X5_1 0.000000 13.000000

X5_2 0.000000 11.000000

X5_3 0.000000 9.000000

X5_4 0.000000 7.000000

X5_5 0.000000 5.000000

X5_6 0.000000 3.000000

X5_7 0.000000 3.000000

X5_8 0.000000 3.000000

X5_9 1.000000 3.000000

X5_10 0.000000 5.000000

X6_1 0.000000 6.000000

X6_2 0.000000 4.000000

X6_3 0.000000 2.000000

X6_4 1.000000 2.000000

X6_5 0.000000 2.000000

X6_6 0.000000 4.000000

X6_7 0.000000 6.000000

X6_8 0.000000 8.000000

X6_9 0.000000 10.000000

X6_10 0.000000 12.000000

X7_1 0.000000 1.000000

X7_2 1.000000 1.000000

X7_3 0.000000 3.000000

X7_4 0.000000 5.000000

X7_5 0.000000 7.000000

X7_6 0.000000 9.000000

X7_7 0.000000 11.000000

X7_8 0.000000 13.000000

X7_9 0.000000 15.000000

X7_10 0.000000 17.000000

X8_1 0.000000 16.000000

X8_2 0.000000 14.000000

X8_3 0.000000 12.000000

X8_4 0.000000 10.000000

X8_5 0.000000 8.000000

X8_6 0.000000 6.000000

X8_7 0.000000 4.000000

X8_8 0.000000 2.000000

X8_9 0.000000 2.000000

X8_10 1.000000 2.000000

X9_1 0.000000 8.000000

X9_2 0.000000 6.000000

X9_3 0.000000 4.000000

X9_4 0.000000 2.000000

X9_5 0.000000 2.000000

X9_6 1.000000 2.000000

X9_7 0.000000 4.000000

X9_8 0.000000 6.000000

X9_9 0.000000 8.000000

X9_10 0.000000 10.000000

X10_1 0.000000 8.000000

X10_2 0.000000 6.000000

X10_3 0.000000 4.000000

X10_4 0.000000 4.000000

X10_5 0.000000 4.000000

X10_6 0.000000 4.000000

X10_7 1.000000 4.000000

X10_8 0.000000 6.000000

X10_9 0.000000 8.000000

X10_10 0.000000 10.000000

NO. 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

5,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

3,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

Изменим критерий модели задачи.

min

1.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 +

3.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 +

7.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 +

6.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 +

5.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 +

2.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 +

0.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 +

8.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 +

3.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 +

4.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.500000

NEW INTEGER SOLUTION OF 9.00000000 AT BRANCH 0 PIVOT 13

BOUND ON OPTIMUM: 9.000000

ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 13

LAST INTEGER SOLUTION IS THE BEST FOUND

RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE

1) 9.000000

VARIABLE VALUE REDUCED COST

X1_1 1.000000 1.800000

X1_2 0.000000 2.200000

X1_3 0.000000 2.600000

X1_4 0.000000 3.000000

X1_5 0.000000 3.400000

X1_6 0.000000 3.800000

X1_7 0.000000 4.200000

X1_8 0.000000 5.200000

X1_9 0.000000 6.200000

X1_10 0.000000 7.200000

X2_1 0.000000 3.100000

X2_2 0.000000 2.100000

X2_3 0.000000 1.700000

X2_4 0.000000 1.300000

X2_5 1.000000 0.900000

X2_6 0.000000 1.900000

X2_7 0.000000 2.900000

X2_8 0.000000 3.900000

X2_9 0.000000 4.900000

X2_10 0.000000 5.900000

X3_1 0.000000 7.600000

X3_2 0.000000 6.600000

X3_3 0.000000 5.600000

X3_4 0.000000 4.600000

X3_5 0.000000 3.600000

X3_6 0.000000 2.600000

X3_7 0.000000 1.600000

X3_8 1.000000 0.600000

X3_9 0.000000 1.000000

X3_10 0.000000 1.400000

X4_1 0.000000 6.500000

X4_2 0.000000 5.500000

X4_3 0.000000 4.500000

X4_4 0.000000 3.500000

X4_5 0.000000 3.100000

X4_6 0.000000 2.700000

X4_7 0.000000 2.300000

X4_8 0.000000 1.900000

X4_9 1.000000 1.500000

X4_10 0.000000 2.500000

X5_1 0.000000 5.900000

X5_2 0.000000 4.900000

X5_3 0.000000 3.900000

X5_4 0.000000 2.900000

X5_5 0.000000 1.900000

X5_6 1.000000 0.900000

X5_7 0.000000 1.300000

X5_8 0.000000 1.700000

X5_9 0.000000 2.100000

X5_10 0.000000 3.100000

X6_1 0.000000 2.600000

X6_2 0.000000 1.600000

X6_3 1.000000 0.600000

X6_4 0.000000 1.000000

X6_5 0.000000 1.400000

X6_6 0.000000 2.400000

X6_7 0.000000 3.400000

X6_8 0.000000 4.400000

X6_9 0.000000 5.400000

X6_10 0.000000 6.400000

X7_1 0.000000 0.700000

X7_2 1.000000 0.300000

X7_3 0.000000 1.300000

X7_4 0.000000 2.300000

X7_5 0.000000 3.300000

X7_6 0.000000 4.300000

X7_7 0.000000 5.300000

X7_8 0.000000 6.300000

X7_9 0.000000 7.300000

X7_10 0.000000 8.300000

X8_1 0.000000 8.400000

X8_2 0.000000 7.400000

X8_3 0.000000 6.400000

X8_4 0.000000 5.400000

X8_5 0.000000 4.400000

X8_6 0.000000 3.400000

X8_7 0.000000 2.400000

X8_8 0.000000 1.400000

X8_9 0.000000 1.000000

X8_10 1.000000 0.600000

X9_1 0.000000 3.600000

X9_2 0.000000 2.600000

X9_3 0.000000 1.600000

X9_4 1.000000 0.600000

X9_5 0.000000 1.000000

X9_6 0.000000 1.400000

X9_7 0.000000 2.400000

X9_8 0.000000 3.400000

X9_9 0.000000 4.400000

X9_10 0.000000 5.400000

X10_1 0.000000 4.800000

X10_2 0.000000 3.800000

X10_3 0.000000 2.800000

X10_4 0.000000 2.400000

X10_5 0.000000 2.000000

X10_6 0.000000 1.600000

X10_7 1.000000 1.200000

X10_8 0.000000 2.200000

X10_9 0.000000 3.200000

X10_10 0.000000 4.200000

NO. 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 с.

2. Юдин Д.Б., Гольдштейн Е.Г. Задачи и методы линейного программирования / М.: «Сов. радио»,1961 - 494 с.

Размещено на Allbest.ru


Подобные документы

  • Методика решения задач линейного программирования

    Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.

    контрольная работа [118,5 K], добавлен 11.04.2012

  • Решение задачи линейного программирования

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

    курсовая работа [100,0 K], добавлен 31.10.2014

  • Решение задачи линейного программирования симплекс-методом

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

    курсовая работа [1,1 M], добавлен 21.03.2012

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

    Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.

    курсовая работа [581,5 K], добавлен 13.10.2008

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

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

    курсовая работа [663,9 K], добавлен 10.06.2014

  • Решение задач симплекс-методом

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

    контрольная работа [191,1 K], добавлен 05.04.2016

  • Решение задач линейного программирования

    Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.

    курсовая работа [132,0 K], добавлен 09.12.2008

  • Решение транспортной задачи линейного программирования в среде MS Excel

    Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.

    дипломная работа [2,4 M], добавлен 20.11.2010

  • Разработка модели и решение задачи линейного программирования на примере задачи об оптимизации размещения рекламы. Компания "Медиа Оптимизатор"

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

    курсовая работа [607,2 K], добавлен 13.03.2015

  • Задача линейного программирования

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

    курсовая работа [232,4 K], добавлен 01.06.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены