Статьи по информатике
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Применение логических уравнений для решения задачи о назначениях

Шалимова Е. М.

Задача о назначениях - это целочисленная задача линейного программирования, которая заключается в выборе такого распределения ресурсов по некоторым действующим объектам, при котором минимизируется стоимость назначения. Предполагается, что каждый ресурс назначается ровно один раз и каждому объекту приписывается ровно один ресурс. Математически это формулируется следующим образом. Пусть С=[сij]- матрица стоимостей, где сij - затраты, связанные с назначением i-ro ресурса на j-й объект, и . Определим матрицу Х =[xij] следующим образом: xij=1, если i-й ресурс назначен на j-й бъект, xij=0 в противном случае. Тогда, необходимо минимизировать общую стоимость назначений, при условиях, что xij≥ 0, , для всех , .

Для решения этой задачи можно воспользоваться алгоритмами линейного программирования или венгерским алгоритмом [1]. Однако, особенности данной задачи, заключающиеся в том, что элементы матрицы Х=[xij] могут принимать только два значения 0 или 1 и правые части ограничений равны 1, позволяют применить для решения рассматриваемой задачи аппарат булевой алгебры. Математическую модель представим системой логических уравнений, каждое уравнение которой определяет все возможные назначения для одного ресурса с помощью операции дизъюнкции. Возможность назначения i-ro ресурса на j-й объект будем обозначать парой ij. Таким образом, система задает все возможные назначения. Перейдем от системы логических уравнений к одному уравнению и решим его, используя метод раскрытия скобок. Для того, чтобы учесть ограничения, при выполнении операции конъюнкции положим, что ijkj=0. В результате преобразований получим все возможные назначения. Найдем стоимости полученных назначений и выберем оптимальное. Предложенный подход о не требует построения начального решения и позволяет использовать любой критерий оптимизации в отличие от симплекс-метода и венгерского алгоритма.

Библиографический список

1. Филлипс Д. Методы анализа сетей/ Д. Филлипс, А. Гарсиа-Диас.–М:Мир.,1984.-с.496.

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство

Агрономия

Преподавателям

Юридические темы

Google