Задача о покрытии множества

Задача о покрытии множества формулируется следующим образом.

Пусть M = {h₁, …, h_m} – некоторое множество объектов h_i (i = = 1,…,m), а S = {S₁, …, S_n} – семейство подмножеств S_j (j = 1,…,n), содержащих элементы множества M, и каждому из этих подмножеств поставлено в соответствие некоторое число (вес) c_j. Требуется найти такой набор подмножеств S^*Ì S, при котором достигается покрытие множества M с минимальным суммарным весом.

Сформулируем данную задачу в терминах булевого линейного программирования.

Пусть A = ||a_ij|| – булева матрица размерности m´n, элементы которой формируются исходя из условия: a_ij = 1, если h_i Î S_j (т.е. если i-й элемент множества M содержится в подмножестве S_j), и a_ij = 0 – в противном случае.

Пусть x_j – булева переменная, которая равна 1, если подмножество S_j входит в покрытие множества M, и равна 0 –в противном случае.

Тогда в формальном виде задача о покрытии множества может быть представлена следующим образом:

(4.1)

i = 1,…,m. (4.2)

Выражение (4.2) – ограничение в виде системы линейных неравенств – задаёт условие принадлежности каждого элемента множества М покрытию.

Формулировка задания

Решить задачу о покрытии множества M = {1,2,3,4,5,6,7,8}. Семейство подмножеств данного множества и значения их весов для различных вариантов выполнения задания представлены на рисунке

Код программы:
Файл 3_4_5:

clc

clear

f = [6; 7; 8; 9; 9; 5; 6; 8; 7; 5; 6; 6; 10];

A=[ 0 1 0 1 0 0 1 0 1 1 1 0 1;

1 0 1 1 0 1 0 1 0 1 1 1 0;

1 1 0 1 1 0 1 1 0 0 0 0 1;

0 0 0 0 0 1 1 0 0 0 1 0 0;

1 0 1 1 1 1 0 1 1 1 0 0 0;

0 1 1 0 1 0 0 1 0 0 1 0 1;

0 0 0 0 0 1 1 0 1 0 1 1 1;

1 1 1 0 0 0 1 0 0 1 0 1 1];

b = ones(8,1);

[x,fval] = bintprog(f, -A, -b) % вывод в двоичном виде

y = find(x) % номера подмножеств

Решение:

x =

fval =

y =

Таким образом, минимальное покрытие множества М образуют подмножества S₁ и S₁₁ с суммарным весом, равным 12.

Задача 5

Задача о максимальном паросочетании (рёберном покрытии) формулируется следующим образом: для заданного неориентированного графа требуется найти такое подмножество E^* рёбер из всего их множества E (E^* Ì E) максимальной мощности, в котором никакие два ребра не будут инцидентны (т.е. не будут иметь общей вершины).

В терминах булевого линейного программирования формально данная задача формулируется следующим образом:

(5.1)

, i = 1,…,m. (5.2)

Здесь x_j – переменные, ассоциированные с рёбрами, при этом x_j = =1, если ребро с номером j входит в максимальное паросочетание, и x_j = 0 – в противном случае.

Коэффициенты a_ij – компоненты булевой матрицы инцидентности А размерности m´n – принимают значение 1, если вершина с номером i инцидентна ребру с номером j, и значение 0 – в противном случае.

Выражение (5.2) – ограничение в виде системы линейных неравенств – задаёт условие того, что в каждой вершине сумма инцидентных ей переменных (рёбер) не превышает единицы.

Задача о максимальном взвешенном паросочетании отличается только целевой функцией, т.е. вместо выражения (5.1) имеет место

(5.3)

где с_j – вес ребра с номером j.

Формулировка задания

Решить задачу о максимальном взвешенном паросочетании для графа, изображённого на рисунке 5.1. Значения весов рёбер для различных вариантов выполнения задания представлены в таблице.

Рисунок 5.1 – Неориентированный граф

Код программы:

Файл 3_4_5:

clc

clear

f = [6;8; 9; 10; 11;

7; 12; 9; 6; 7;

8; 10; 11; 7; 5; 9];

A = [ 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0;

1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0;

0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0;

0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0;

0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1;

0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0;

0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1;

0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0];

b = ones(8,1);

x = bintprog(-f, A, b);

y = find(x) % номера ребер

Решение:

y =

Таким образом, E^* = {2,7,12,14}, т.е. в максимальное паросочетание входят рёбра с номерами 2,7,12,14

Задача 6