Решение задачи о наименьшем покрытии

На основе линейного программирования

Пусть x_j=1, если S_j - покрывающее множество войдет в покрытие и равно 0 - в противном случае. Тогда задача сводится к задаче целочисленного программирования:

минимизировать Z=

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

³ 1, где i=1,2,,N.

Решение задачи оптимизации системы методом линейного программирования может быть осуществлено с помощью пакета MS EXCEL.