Важный раздел целочисленной оптимизации составляют математические модели задач с булевыми переменными, т.е. переменными, принимающими только два значения "1", или "0". С помощью булевых переменных можно решать самые различные по содержанию задачи, в которых надо что-то выбирать из имеющихся различных вариантов. Примерами задач данного класса в процессе управления производством служат задачи
· оптимального назначения исполнителей на работы,
· при выборе вариантов комплектующих изделий,
· при выборе типа станка для обработки деталей,
· в задаче закрепления продавцов за товарами различных видов, и т.д.
Для того, чтобы составить матрицу условий задачи необходимо иметь исходные данные: характеристики деятельности любого исполнителя на каждой работе, определяющие значение принятого критерия оптимальности. Так, в задаче закрепления продавцов за товарами должны быть известны доходы каждого продавца от продажи товара любого вида, т.е. должна быть известна матрица
|
|
.
Продавцам соответствуют строки, а видам товаров – столбцы этой матрицы. В задаче требуется определить, за каким продавцом должен быть закреплен тот или иной товар, т.е. ответить на вопрос «будет ли -ый продавец продавать -ый товар или не будет». Таким образом, искомые неизвестные должны принимать только два значения «да», или «нет». В числовом выражении «1», или «0».
Для составления математической модели введем булевы переменные следующим образом: , если -ый продавец осуществляет продажу -го товара, и , если -ый продавец не занят продажей -го товара. В сокращенном виде
, .
Запишем булевы неизвестные в виде следующей матрицы
.
Через обозначим суммарный доход от продажи всего товара. Тогда
. (4.1)
Так как по условию каждый продавец продает только один вид товара, то
. (4.2)
Так как каждый вид товара реализуется одним продавцом, то
. (4.3)
Таким образом, математическая модель задачи о назначениях состоит в определении неотрицательных целых чисел , удовлетворяющих ограничениям (4.2)-(4.3), для которых целевая функция (4.1) максимальна. Система ограничений задачи показывает, что каждое допустимое решение можно представить матрицей, содержащей по одной единице в каждой строке и каждом столбце, а остальные элементы матрицы равны нулям. Ясно также, что число допустимых решений в задаче равно , и поэтому допустимое множество дискретно.
Математическая модель в виде (4.1)-(4.3) представляет собой классический вариант задачи о назначениях. Она относится к линейному целочисленному программированию с булевыми переменными. В принципе комбинаторные задачи приведенного вида могут быть решены полным перебором всехвозможных вариантов допустимых решений. Однако, количество этих вариантов может быть столь большим, что полный перебор невозможно осуществить в реальноне время даже с помощью современных ЭВМ. Так, при получим число допустимых решений . Если предположить, что компьютер в течение 1с находит допустимых решений и для каждого из них вычисляет значение целевой функции, то для решения задачи потребуется с, или года (). Таким образом, для решения данной задачи при больших значениях перебор допустимых решений неприменим.
|
|
Заметим, что математическая модель задачи о назначениях представляет собой частный случай сбалансированной транспортной модели при дополнительном условии целочисленности неизвестных. Поэтому для ее решения может быть применен классический метод решения – метод потенциалов. Для решения задачи можно использовать также венгерский метод и метод ветвей и границ. Однако, при наличии программного обеспечения быстрее и проще использовать информационные технологии.