Студопедия

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

КАТЕГОРИИ:

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






Задача о назначениях (проблема выбора)






 

Постановка задачи. В распоряжении имеется 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.

Систему ограничений запишите из условий, что каждая бригада выполняет работу на одной определенной стройплощадке и что каждая площадка обеспечена одной бригадой рабочих.


Поделиться с друзьями:

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