Материал: Основы математического моделирования. курс лекций. Перова А.В

n

x j min;

j 1

n

a ij x j 1,i 1, m;

j 1

x j {1,0}.

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

Если каждому j-му предмету приписывается вес Cj,

может быть сформулирована взвешенная задача о покрытии:

n

C jx j min

j 1

n

a ij x j 1,i 1, m,

j 1

x j {0,1}

Если каждому i-му признаку приписывается натуральное число i и требуется найти минимальное число таких

предметов, что i-м признаком обладает не менее i предметов из указанного набора, получаем задачу о кратном покрытии:

n

x j min

j1 n

aij x j i,i 1, m,

j 1

xj {0,1}

115

Задача о разбиении. Задача о разбиении аналогична задачи о покрытии с тем отличием, что признаки у различных предметов не должны совпадать:

n

x j min;

j 1

n

a ij x j 1,i 1, m;

j 1

x j {1,0}.

Задача о взвешенном разбиении формулируется следующим образом:

n

x j min;

j 1

n

aijx j 1,i 1,m;

j 1

xj {1,0}.

Кзадаче о покрытии сводится широкий круг задач информационного поиска, синтеза логических схем, задачи разбиения электронных схем на модули и покрытия схем типовыми ячейками и т.д.

Пример 5. Пусть некоторое количество информации

хранится в n массивах (файлах) длины cj, j 1,n, причем на

каждую единицу информации отводится по крайней мере один массив. Задана матрица T с элементами

116

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

Введем бинарные переменные:

Тогда математическая модель задачи формализуется в виде задачи о покрытии:

n

cij xj min;

j1 n

tij xj 1,i 1,m;

j 1

xj {1,0}.

ЛЕКЦИЯ 11 МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО

ПРОГРАММИРОВАНИЯ

Методы решения задач целочисленного программирования делятся на следующие группы:

методы отсечения; комбинаторные методы; приближенные методы.

Методы отсечения используются только для решения линейных задач, а комбинаторные и приближенные методы - как для линейных, так и для нелинейных задач.

В EXCEL для решения целочисленных задач используется метод ветвей и границ, который относится к классу комбинаторных методов. Рассмотрим этот метод.

Метод ветвей и границ основан на использовании конечности множества допустимых вариантов и замене полного перебора сокращенным направленным перебором. При этом

117

рые целочисленные переменные принимают дробные значения; тогда оптимальное решение исходной задачи не совпадает с оптимальным решением ЛП-1. В этом случае величина Z1 представляет собой верхнюю границу оптимального значения Z исходной задачи.

На следующем шаге проводится ветвление по одной из целочисленных переменных, имеющих дробное значение в оптимальном решении задачи ЛП-1. Для определения переменной, по которой производится ветвление, разработан ряд правил. Приведем некоторые из них.

1.Выбор целочисленной переменной с наибольшей дробной частью.

2.Приписывание целочисленным переменным приоритетов и ветвление по переменной с наибольшим приоритетом. Важность целочисленной переменной может определяться следующими соображениями:

- данная переменная является наиболее важной, ее значение ирает важную роль в модели по мнению разработчиков.

- коэффициент целевой функции при данной переменной превосходит остальные;

3.Находится то дополнительное ограничение, которое приводит к наибольшему возрастанию нижней границы. Цель - найти ту вершину, которая наиболее верно будет отброшена.

4.Произвольные правила выбора. Например, можно выбирать переменную с наименьшим номером.

Пусть ветвление происходит по целочисленной переменной хj, дробное значение которой в оптимальном решении

ЛП-1, равно j . Далее рассматриваются две новые задачи ЛП, обозначаемые через ЛП-2 и ЛП-3. Они получаются путем вве-

дения ограничений x j j и xj j соответственно, где

через j обозначается наибольшее целое, не превосходящее j

119