11.3.4. Эквивалентные формулировки знп

ЗНП может быть сформулирована многими разными способами.

1. Пусть имеется конечное множество V = {«i,..., v_p} и семейство подмножеств этого множества Е = {Е_ь..., Е_р}. Каждому подмножеству Ei приписан вес. Найти покрытие Е' (Е' с Е) наименьшего веса.

ЗАМЕЧАНИЕ

Из этой формулировки происходит название «задача о наименьшем покрытии».

Рис 11.1 связь различных задач

2. ЗНП можно сформулировать как задачу линейного программирования:

р min Y^ CiXi

i=l

при ограничениях

где

_с. > 0 - J¹' если^еЕ",

|0, в противном случае,

1, если Vi е ej,

О, в противном случае.

3. Дана булева матрица Т : array [l..p,l..p] of 0..1. Каждому столбцу приписан вес Cj. Найти такое множество столбцов минимальной стоимости, чтобы любая строка содержала единицу хотя бы в одном из выбранных столбцов.