Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Тоді цільова функція приймає вигляд




F = cij xij ® min.

Врахуємо, що на кожному верстаті виконується не більше однієї роботи

xij £ 1, i = 1, m.

Необхідності виконання кожної роботи відповідає система нерівностей

xij ³ 1, j = 1, n.

За формою ця задача майже співпадає з транспортною: верстати – пункти зберігання, запаси у яких дорівнюють одиниці; роботи – споживачі, потреби яких дорівнюють одиниці. Відміна полягає у додатковому обмеженні – змінні xij приймають значення 0 або 1. Але оскільки відомо, що транспортна задача з цілими правими частинами, маюча розв’язок, завжди має і цілочисельний розв’язок, вказана відміна несуттєва. Отже, задача про призначення є окремим випадком транспортної задачі.

Задачі математичного програмування, у яких змінні приймають лише значення 0 або 1, називають задачами бівалентного (булевого) програмування.

Для розв’язування задачі про призначення можна скористатися методом потенціалів, але існує більш ефективний спеціальний алгоритм, названий угорським методом на честь його винахідника угорського математика Едварда Егерварі. Саме ідеї, покладені у основу цього методу відіграли значну роль у розвитку методів дискретної математики.




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


Дата добавления: 2014-01-13; Просмотров: 283; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.