![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сведения из теории. Важный раздел целочисленной оптимизации составляют математические модели задач с булевыми переменными
Важный раздел целочисленной оптимизации составляют математические модели задач с булевыми переменными, т.е. переменными, принимающими только два значения " 1", или " 0". С помощью булевых переменных можно решать самые различные по содержанию задачи, в которых надо что-то выбирать из имеющихся различных вариантов. Примерами задач данного класса в процессе управления производством служат задачи · оптимального назначения исполнителей на работы, · при выборе вариантов комплектующих изделий, · при выборе типа станка для обработки деталей, · в задаче закрепления продавцов за товарами различных видов, и т.д. Для того, чтобы составить матрицу условий задачи необходимо иметь исходные данные: характеристики деятельности любого исполнителя на каждой работе, определяющие значение принятого критерия оптимальности. Так, в задаче закрепления продавцов за товарами должны быть известны доходы каждого продавца от продажи товара любого вида, т.е. должна быть известна матрица
Продавцам Для составления математической модели введем булевы переменные
Запишем булевы неизвестные в виде следующей матрицы
Через
Так как по условию каждый продавец продает только один вид товара, то
Так как каждый вид товара реализуется одним продавцом, то
Таким образом, математическая модель задачи о назначениях состоит в определении неотрицательных целых чисел Математическая модель в виде (4.1)-(4.3) представляет собой классический вариант задачи о назначениях. Она относится к линейному целочисленному программированию с булевыми переменными. В принципе комбинаторные задачи приведенного вида могут быть решены полным перебором всехвозможных вариантов допустимых решений. Однако, количество этих вариантов может быть столь большим, что полный перебор невозможно осуществить в реальноне время даже с помощью современных ЭВМ. Так, при Заметим, что математическая модель задачи о назначениях представляет собой частный случай сбалансированной транспортной модели при дополнительном условии целочисленности неизвестных. Поэтому для ее решения может быть применен классический метод решения – метод потенциалов. Для решения задачи можно использовать также венгерский метод и метод ветвей и границ. Однако, при наличии программного обеспечения быстрее и проще использовать информационные технологии.
|