Линейное программирование ослаблено для MKP

Question

как рассчитать, чтобы найти это расслабление. Что я должен знать, чтобы найти его. Предположим, что у меня есть n предметов и m рюкзак. Поэтому я хотел узнать количество релаксации. Кто-нибудь может дать мне хоть какую-то идею. Я искал его пока. В Интернете есть статья, но не очень ясная. Пожалуйста, по крайней мере, кто-то сказали мне, вы должны прочитать эту вещь, вы должны знать эту вещь й так что я буду очень признателен

Спасибо

Answer 1

Я думаю, что ваш реальный вопрос «что такое точное определение линейно Relaxed Knackack Problem? ", Поэтому я собираюсь ответить, предполагая, что это так.

Короткий ответ, что линейно-расслаблен КП является дробным вариантом 0-1 КП [1].

Математически все, что вам нужно сделать, это преобразовать ограничение «x_i принадлежит к набору {0, 1}» и преобразовать его в «x_i должно быть любым реальным числом от 0 до 1», где x_i - величина i-го элемента в вашем рюкзаке решения.

Название происходит от того факта, что 0-1 КП является задачей целочисленного программирования. «Линейный» термин означает, что переменные решения могут принимать непрерывные значения.

Не все релаксации линейны. Вы можете просмотреть страницу Википедии this.

[1] http://en.wikipedia.org/wiki/Linear_programming_relaxation