Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Сведения из теории. Важный раздел целочисленной оптимизации составляют математические модели задач с булевыми переменными




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

· оптимального назначения исполнителей на работы,

· при выборе вариантов комплектующих изделий,

· при выборе типа станка для обработки деталей,

· в задаче закрепления продавцов за товарами различных видов, и т.д.

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

.

 

Продавцам соответствуют строки, а видам товаров – столбцы этой матрицы. В задаче требуется определить, за каким продавцом должен быть закреплен тот или иной товар, т.е. ответить на вопрос «будет ли -ый продавец продавать -ый товар или не будет». Таким образом, искомые неизвестные должны принимать только два значения «да», или «нет». В числовом выражении «1», или «0».

Для составления математической модели введем булевы переменные следующим образом: , если -ый продавец осуществляет продажу -го товара, и , если -ый продавец не занят продажей -го товара. В сокращенном виде

, .

Запишем булевы неизвестные в виде следующей матрицы

.

 

Через обозначим суммарный доход от продажи всего товара. Тогда

. (4.1)

Так как по условию каждый продавец продает только один вид товара, то

. (4.2)

Так как каждый вид товара реализуется одним продавцом, то

. (4.3)

Таким образом, математическая модель задачи о назначениях состоит в определении неотрицательных целых чисел , удовлетворяющих ограничениям (4.2)-(4.3), для которых целевая функция (4.1) максимальна. Система ограничений задачи показывает, что каждое допустимое решение можно представить матрицей, содержащей по одной единице в каждой строке и каждом столбце, а остальные элементы матрицы равны нулям. Ясно также, что число допустимых решений в задаче равно , и поэтому допустимое множество дискретно.

Математическая модель в виде (4.1)-(4.3) представляет собой классический вариант задачи о назначениях. Она относится к линейному целочисленному программированию с булевыми переменными. В принципе комбинаторные задачи приведенного вида могут быть решены полным перебором всехвозможных вариантов допустимых решений. Однако, количество этих вариантов может быть столь большим, что полный перебор невозможно осуществить в реальноне время даже с помощью современных ЭВМ. Так, при получим число допустимых решений . Если предположить, что компьютер в течение 1с находит допустимых решений и для каждого из них вычисляет значение целевой функции, то для решения задачи потребуется с, или года ( ). Таким образом, для решения данной задачи при больших значениях перебор допустимых решений неприменим.



Заметим, что математическая модель задачи о назначениях представляет собой частный случай сбалансированной транспортной модели при дополнительном условии целочисленности неизвестных. Поэтому для ее решения может быть применен классический метод решения – метод потенциалов. Для решения задачи можно использовать также венгерский метод и метод ветвей и границ. Однако, при наличии программного обеспечения быстрее и проще использовать информационные технологии.

 


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал