Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Задача о назначениях (проблема выбора)
|
|
| Постановка задачи. В распоряжении имеется n механизмов (бригад) и n различных видов работ. Производительность каждого механизма на различных работах, вообще говоря, различна. Обозначим через cij (i, j =1, 2,.., n) производительность i -го механизма на j -й работе. Матрица C=[ cij ] называется матрицей эффективностей или производительностей. Требуется так распределить n механизмов на n работах, чтобы каждый механизм выполнял одну и только одну работу и чтобы при заданной производительности каждого механизма на каждой из работ суммарный эффект был бы максимальным. |
Эта задача является частным случаем транспортной задачи
Обозначим через xij переменную, равную единице, если i- ймеханизм назначен на j-ю работу, и равен нулю, если он на эту работу не назначен. В качестве целевой функции выбираем суммарную производительность всех механизмов
Ограничения записываем из условия, что каждый механизм выполняет одну работу и что каждая работа обеспечивается одним механизмом:
n Пример 6.9. Задача о назначениях.
Имеются три бригады В 1, В 2, В 3, каждая из которых может быть использована на каждой из 3-х строительной площадке с производительностью (в условных единицах), заданной в таблице.
Таблица.
| Строител. площадка | Производительность бригад (у.е.) | ||
| В 1 | В 2 | В 3 | |
Требуется распределить бригады по одной на каждую строительную площадку так, чтобы суммарная производительность всех бригад была максимальной.
Обозначим xij =1, если на i -ю стройплощадку назначена j -я бригада, и xij =0, если она на эту стройплощадку не назначена.
В качестве функции цели возьмем суммарную производительность всех бригад:
Z max = x 11 +2 x 12 +3 х 13+2 x 21 +4 x 22 + x 23+3 x 31 + x 32.+5 x 33.
Систему ограничений запишите из условий, что каждая бригада выполняет работу на одной определенной стройплощадке и что каждая площадка обеспечена одной бригадой рабочих.
