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

КурсоваяПомощь в написанииУзнать стоимостьмоей работы

Суть задачи из данного варианта заключается в том, что один ресурс можно применить, только к одному объекту, в качестве примера можно привести распределение рабочих по местам, так чтобы минимизировать время производства продукции. Была составлена математическая модель задачи и получено оптимальное решение при помощи программного пакета LINDO. Было так же рассмотрено решение задачи со списками… Читать ещё >

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

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

1. Задание на курсовую работу

Имеется m списков длиной n элементов каждый, в которых в разном порядке расположены одни и те же элементы.

Требуется:

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

Показать, как изменится решение, если:

элемент а1 закрепить на первом месте, а а4 на пятом, списки имеют разный приоритет: w1=0.3, w2=0.7;

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

Исходные данные Таблица 1.


Список.	Элементы.
	a7.	a2.	a10.	a4.	a6.	a9.	a1.	a8.	a5.	a3.
	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.


ij.

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

min.

6 X1₁+6 X1₂+6 X1₃+6 X1₄+6 X1₅+6 X1₆+6 X1₇+8 X1₈+10 X1₉+12 X1₁₀+.

5 X2₁+3 X2₂+3 X2₃+3 X2₄+3 X2₅+5 X2₆+7 X2₇+9 X2₈+11 X2₉+13 X2₁₀+.

16 X3₁+14 X3₂+12 X3₃+10 X3₄+8 X3₅+6 X3₆+4 X3₇+2 X3₈+2 X3₉+2 X3₁₀+.

11 X4₁+9 X4₂+7 X4₃+5 X4₄+5 X4₅+5 X4₆+5 X4₇+5 X4₈+5 X4₉+7 X4₁₀+.

13 X5₁+11 X5₂+9 X5₃+7 X5₄+5 X5₅+3 X5₆+3 X5₇+3 X5₈+3 X5₉+5 X5₁₀+.

6 X6₁+4 X6₂+2 X6₃+2 X6₄+2 X6₅+4 X6₆+6 X6₇+8 X6₈+10 X6₉+12 X6₁₀+.

1 X7₁+1 X7₂+3 X7₃+5 X7₄+7 X7₅+9 X7₆+11 X7₇+13 X7₈+15 X7₉+17 X7₁₀+.

16 X8₁+14 X8₂+12 X8₃+10 X8₄+8 X8₅+6 X8₆+4 X8₇+2 X8₈+2 X8₉+2 X8₁₀+.

8 X9₁+6 X9₂+4 X9₃+2 X9₄+2 X9₅+2 X9₆+4 X9₇+6 X9₈+8 X9₉+10 X9₁₀+.

8 X10₁+6 X10₂+4 X10₃+4 X10₄+4 X10₅+4 X10₆+4 X10₇+6 X10₈+8 X10₉+10 X10₁₀.

st.

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

X1₁ + X1₂ + X1₃ + X1₄ + X1₅ + X1₆ + X1₇ + X1₈ + X1₉ + X1₁₀ = 1.

X2₁ + X2₂ + X2₃ + X2₄ + X2₅ + X2₆ + X2₇ + X2₈ + X2₉ + X2₁₀ = 1.

X3₁ + X3₂ + X3₃ + X3₄ + X3₅ + X3₆ + X3₇ + X3₈ + X3₉ + X3₁₀ = 1.

X4₁ + X4₂ + X4₃ + X4₄ + X4₅ + X4₆ + X4₇ + X4₈ + X4₉ + X4₁₀ = 1.

X5₁ + X5₂ + X5₃ + X5₄ + X5₅ + X5₆ + X5₇ + X5₈ + X5₉ + X5₁₀ = 1.

X6₁ + X6₂ + X6₃ + X6₄ + X6₅ + X6₆ + X6₇ + X6₈ + X6₉ + X6₁₀ = 1.

X7₁ + X7₂ + X7₃ + X7₄ + X7₅ + X7₆ + X7₇ + X7₈ + X7₉ + X7₁₀ = 1.

X8₁ + X8₂ + X8₃ + X8₄ + X8₅ + X8₆ + X8₇ + X8₈ + X8₉ + X8₁₀ = 1.

X9₁ + X9₂ + X9₃ + X9₄ + X9₅ + X9₆ + X9₇ + X9₈ + X9₉ + X9₁₀ = 1.

X10₁ + X10₂ + X10₃ + X10₄ + X10₅ + X10₆ + X10₇ + X10₈ + X10₉ + X10₁₀ = 1.

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

X1₁ + X2₁ + X3₁ + X4₁ + X5₁ + X6₁ + X7₁ + X8₁ + X9₁ + X10₁ = 1.

X1₂ + X2₂ + X3₂ + X4₂ + X5₂ + X6₂ + X7₂ + X8₂ + X9₂ + X10₂ = 1.

X1₃ + X2₃ + X3₃ + X4₃ + X5₃ + X6₃ + X7₃ + X8₃ + X9₃ + X10₃ = 1.

X1₄ + X2₄ + X3₄ + X4₄ + X5₄ + X6₄ + X7₄ + X8₄ + X9₄ + X10₄ = 1.

X1₅ + X2₅ + X3₅ + X4₅ + X5₅ + X6₅ + X7₅ + X8₅ + X9₅ + X10₅ = 1.

X1₆ + X2₆ + X3₆ + X4₆ + X5₆ + X6₆ + X7₆ + X8₆ + X9₆ + X10₆ = 1.

X1₇ + X2₇ + X3₇ + X4₇ + X5₇ + X6₇ + X7₇ + X8₇ + X9₇ + X10₇ = 1.

X1₈ + X2₈ + X3₈ + X4₈ + X5₈ + X6₈ + X7₈ + X8₈ + X9₈ + X10₈ = 1.

X1₉ + X2₉ + X3₉ + X4₉ + X5₉ + X6₉ + X7₉ + X8₉ + X9₉ + X10₉ = 1.

X1₁₀ + X2₁₀ + X3₁₀ + X4₁₀ + X5₁₀ + X6₁₀ + X7₁₀ + X8₁₀ + X9₁₀ + X10₁₀ = 1.

end.

int 100.

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

LP OPTIMUM FOUND AT STEP 30.

OBJECTIVE VALUE = 30.0.

FIX ALL VARS.(60) WITH RC > 2.0.

NEW INTEGER SOLUTION OF 30.0 AT BRANCH 0 PIVOT 30.

BOUND ON OPTIMUM: 30.0.

ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 30.

LAST INTEGER SOLUTION IS THE BEST FOUND.

RE-INSTALLING BEST SOLUTION…

OBJECTIVE FUNCTION VALUE.

1) 30.0.

VARIABLE VALUE REDUCED COST.

X1₁ 0.0 6.0.

X1₂ 0.0 6.0.

X1₃ 0.0 6.0.

X1₄ 0.0 6.0.

X1₅ 0.0 6.0.

X1₆ 1.0 6.0.

X1₇ 0.0 6.0.

X1₈ 0.0 8.0.

X1₉ 0.0 10.0.

X1₁₀ 0.0 12.0.

X2₁ 0.0 5.0.

X2₂ 1.0 3.0.

X2₃ 0.0 3.0.

X2₄ 0.0 3.0.

X2₅ 0.0 3.0.

X2₆ 0.0 5.0.

X2₇ 0.0 7.0.

X2₈ 0.0 9.0.

X2₉ 0.0 11.0.

X2₁₀ 0.0 13.0.

X3₁ 0.0 16.0.

X3₂ 0.0 14.0.

X3₃ 0.0 12.0.

X3₄ 0.0 10.0.

X3₅ 0.0 8.0.

X3₆ 0.0 6.0.

X3₇ 0.0 4.0.

X3₈ 1.0 2.0.

X3₉ 0.0 2.0.

X3₁₀ 0.0 2.0.

X4₁ 0.0 11.0.

X4₂ 0.0 9.0.

X4₃ 0.0 7.0.

X4₄ 0.0 5.0.

X4₅ 0.0 5.0.

X4₆ 0.0 5.0.

X4₇ 0.0 5.0.

X4₈ 0.0 5.0.

X4₉ 1.0 5.0.

X4₁₀ 0.0 7.0.

X5₁ 0.0 13.0.

X5₂ 0.0 11.0.

X5₃ 0.0 9.0.

X5₄ 0.0 7.0.

X5₅ 0.0 5.0.

X5₆ 0.0 3.0.

X5₇ 1.0 3.0.

X5₈ 0.0 3.0.

X5₉ 0.0 3.0.

X5₁₀ 0.0 5.0.

X6₁ 0.0 6.0.

X6₂ 0.0 4.0.

X6₃ 0.0 2.0.

X6₄ 0.0 2.0.

X6₅ 1.0 2.0.

X6₆ 0.0 4.0.

X6₇ 0.0 6.0.

X6₈ 0.0 8.0.

X6₉ 0.0 10.0.

X6₁₀ 0.0 12.0.

X7₁ 1.0 1.0.

X7₂ 0.0 1.0.

X7₃ 0.0 3.0.

X7₄ 0.0 5.0.

X7₅ 0.0 7.0.

X7₆ 0.0 9.0.

X7₇ 0.0 11.0.

X7₈ 0.0 13.0.

X7₉ 0.0 15.0.

X7₁₀ 0.0 17.0.

X8₁ 0.0 16.0.

X8₂ 0.0 14.0.

X8₃ 0.0 12.0.

X8₄ 0.0 10.0.

X8₅ 0.0 8.0.

X8₆ 0.0 6.0.

X8₇ 0.0 4.0.

X8₈ 0.0 2.0.

X8₉ 0.0 2.0.

X8₁₀ 1.0 2.0.

X9₁ 0.0 8.0.

X9₂ 0.0 6.0.

X9₃ 0.0 4.0.

X9₄ 1.0 2.0.

X9₅ 0.0 2.0.

X9₆ 0.0 2.0.

X9₇ 0.0 4.0.

X9₈ 0.0 6.0.

X9₉ 0.0 8.0.

X9₁₀ 0.0 10.0.

X10₁ 0.0 8.0.

X10₂ 0.0 6.0.

X10₃ 1.0 4.0.

X10₄ 0.0 4.0.

X10₅ 0.0 4.0.

X10₆ 0.0 4.0.

X10₇ 0.0 4.0.

X10₈ 0.0 6.0.

X10₉ 0.0 8.0.

X10₁₀ 0.0 10.0.

NO. ITERATIONS= 30.

BRANCHES= 0 DETERM.= 1.000E 0.

Из данного решения следует, что оптимальное значение L = 30, компромиссный список имеет вид.

Таблица 3.


Элемент.	a7.	a2.	a10.	a9.	a6.	a1.	a5.	a3.	a4.	a8.
Стоимость.

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

st.

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

X2₁ + X2₂ + X2₃ + X2₄ + X2₅ + X2₆ + X2₇ + X2₈ + X2₉ + X2₁₀ = 1.

X3₁ + X3₂ + X3₃ + X3₄ + X3₅ + X3₆ + X3₇ + X3₈ + X3₉ + X3₁₀ = 1.

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