Содержание
Введение 3
1 Задача о назначениях. Венгерский метод 4
1.1 Задача о назначениях 4
1.2 Венгерский метод решения задачи о назначениях 7
2 Решение задачи о назначениях с помощью венгерского метода 15
Заключение 20
Список использованной литературы 21
Введение
Задача о назначениях является частным случаем классической транспортной задачи и, как следствие, является задачей транспортного типа.
Транспортная задача – задача о наиболее экономном плане перевозок однородного или взаимозаменяемого продукта из пункта производства (станций отправления), в пункты потребления (станции назначения) – является важнейшей частной задачей линейного программирования, имеющей обширные практические приложения не только к проблемам транспорта.
Применительно к задаче о назначениях симплексный метод не эффективен, так как любое ее допустимое базисное решение является вырожденным. Специфические особенности задачи о назначениях позволили разработать эффективный метод ее решения, известный как венгерский метод.
1 Задача о назначениях. Венгерский метод 1.1 Задача о назначениях
Предположим, что имеется п различных работ, каждую из которых может выполнить любой из п привлеченных исполнителей. Стоимость выполнения і-й работы j-м исполнителем известна и равна Cіj (в условных денежных единицах). Необходимо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.
В исследовании операций задача, сформулированная выше, известна как задача о назначениях. Введем переменные Xij, где Xij принимает значение 1 в случае, когда і-ю работу выполняет j-й исполнитель, и значение 0 во всех остальных случаях, i,j = 1, п. Тогда ограничение
гарантирует выполнение каждой работы лишь одним исполнителем, ограничение
гарантирует, что каждый из исполнителей будет выполнять лишь одну работу. Стоимость выполнения всего комплекса работ равна
Таким образом, задачу о назначениях можно записать следующим образом:
(1)
Задача о назначениях (1) является частным случаем классической транспортной задачи, в которой надо положить
При этом условие
означает выполнение требования целочисленности переменных xіj. Это связано с тем, что мощности всех источников и стоков равны единице, откуда следует, что в допустимом целочисленном решении значениями переменных могут быть только 0 и 1.
Как частный случай классической транспортной задачи, задачу о назначениях можно рассматривать как задачу линейного программирования. Поэтому в данном случае используют терминологию и теоретические результаты линейного программирования.
В задаче о назначениях переменное хіj может принимать значение 0 или 1. При этом, согласно (1), в любом допустимом решении лишь п переменных могут принимать значения 1. Таким образом, любое допустимое базисное решение задачи о назначениях будет вырожденным.
На практике встречаются задачи о назначениях, в постановках которых параметр понимается как эффективность выполнения і-й работы j-м исполнителем. В этих случаях нужно так распределить работы между исполнителями, чтобы суммарная эффективность их выполнения была бы максимальной, т.е.
(2)
где максимум ищется при ограничениях, указанных в (1).
Параметры задачи о назначениях (1) удобно представлять матрицей , которую называют матрицей стоимости.Предположим, что и С = (cіj) — две матрицы стоимости, элементы которых связаны следующим образом:
где — некоторые постоянные. Таким образом, для получения матрицы С* нужно к элементам каждой і-й строки матрицы С прибавить число d,-, а к элементам ее каждого j-гo столбца — число Ц. В этом случае, если X — допустимое решение, удовлетворяющее ограничениям из (1), и
то с учетом ограничений из (1) типа равенства имеем
где
Таким образом, для любого допустимого решения X соответствующие ему значения функций будут отличаться на постоянную у, которая не зависит от X. Поэтому, если есть две задачи о назначениях с одним и тем же множеством G допустимых решений и целевыми функциями соответственно, то их оптимальные решения совпадают. Нетрудно убедиться в наличии аналогичного свойства и у классической транспортной задачи.
Если задача о назначениях является задачей максимизации, т.е. ищется максимум целевой функции на множестве G допустимых решений, которое задается системой ограничений из (1), то эквивалентную ей задачу минимизации
(3)
формально нельзя отнести к задачам о назначениях, поскольку коэффициенты ее целевой функции не являются положительными. Это несоответствие можно преодолеть, заменив (3) эквивалентной задачей
(4)
в которой
так как в этом случае для всех имеет место неравенство .
1.2 Венгерский метод решения задачи о назначениях
При обсуждении постановки задачи о назначениях было отмечено, что эта задача является частным случаем классической транспортной задачи и, как следствие, является задачей транспортного типа. Применительно к задаче о назначениях симплексный метод не эффективен, так как любое ее допустимое базисное решение является вырожденным. Специфические особенности задачи о назначениях позволили разработать эффективный метод ее решения, известный как венгерский метод.
Заключение
Суть венгерского метода состоит в следующем: Путем прибавления определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так называемых независимых нулей. Набор нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные xij равными 1, а все остальные – равными 0, согласно утверждению 2, получим оптимальный план назначения.
Алгоритм венгерского метода состоит из предварительного шага и не более, чем (n-2) последовательно повторяющихся итераций. На предварительном этапе в случае решения задачи на максимум, ее преобразуют в эквивалентную задачу на минимум. На этом же этапе выделяется система независимых нулей. Каждая последующая итерация направлена на увеличение хотя бы на 1 числа независимых нулей. Как только число независимых нулей k станет равным размерности матрицы (k=n) , задача решена.
Оптимальный план назначения определится положением независимых нулей на последней итерации.
Список использованной литературы
Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. 2-е узд. / Под ред.. В.С. Зарубина, А.П. Крищенко. – М.: Узд-во МГТУ им. Н.Э. Баумана, 2002. – 436 с.
Зайченко Ю.П. Исследование операций: Учеб. пособие для студентов вузов. – 2-е изд., перераб. и доп. – Киев: Вища школа. Главное изд-во, 1979. 392 с.
И. А. Акулич. Математическое программирование в примерах и задачах. - М.: «Высшая школа», 1986.- 319 с.
Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.
Таха Х. Введение в исследование операций: в двух книгах. Кн.1,2 Пер. с англ. - М.: Мир, 1985.
Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. – М.: Издательство БЕК, 1998. – 141с.
Другие работы по теме:
Потоки в логистике
Сервисные потоки — потоки услуг (нематериальной деятельности, особого вида продукции или товара), генерируемые логистической системой в целом или ее подсистемой (звеном, элементом) с целью удовлетворения внешних или внутренних потребителей организации бизнеса.
«Логистика: система хранения грузов»
Реализуется главная цель логистики путем решения большого комплекса задач, главная из которых – достижение максимального эффекта с минимумом затрат в условиях нестабильной обстановки на рынке
Логистическая система и ее основные подсистемы
Трактовка понятия логистическая система Одним из базовых в логистике является понятие логистическая система, которую по праву можно рассматривать как одну из самых ранних среди созданных человеком социально-экономических систем.
Логистика как научное направление
Задание по Логистике к Контрольной работе. Определение номера варианта по номеру зачетной книжки. Всего 20 вариантов. Последние две цифры зачетной книжки
Мате Залка
Введение 1 Биография 2 Память 3 Библиография Список литературы Введение Ма́те За́лка (венг. Zalka Mбtй; настоящее имя Бела Франкль, венг. Frankl Bйla; 23 апреля 1896, Матольч, Венгрия — 11 июня 1937, Уэска, Испания) — венгерский писатель и революционер, активный участник гражданских войн в России 1918—1921 и Испании 1936—1939.
Витез, Янош
Янош Витез (венг. Jбnos Vitйz; ок. 1408-1471) — венгерский епископ, канцлер Венгерского королевства, воспитатель Матьяша Хуньяди. Учился в Падуанском университете. Вернувшись в Венгрию, этот сын мелкопоместного хорватского дворянина сделал головокружительную карьеру: от загребского каноника до варадского епископа, а затем эстергомского архиепископа-примаса и канцлера Венгерского королевства.
Клапка, Дьёрдь
Введение 1 Биография 1.1 Участие в революции 1.2 Эмиграция 1.3 Возвращение на родину Введение Дьёрдь Клапка (венг. Klapka Gyцrgy, 7 апреля 1820 — 17 мая 1892) — венгерский военачальник, участник Венгерской революции 1848 года.
Турзо, Дьёрдь
Введение 1 Биография 2 Участие в «деле графини Батори» 3 В искусстве 3.1 Кинематограф Введение Дьёрдь (Юрай) Турзо (1557, замок Льетавский Град у Жилины — 1616, Битча) — венгерский аристократ и государственный деятель. Граф. Палатин Венгрии в 1609—1616 гг.
Европейский пикник
— демонстрация мира на австрийско-венгерской границе вблизи города Шопрон 19 августа 1989 года. С согласием обеих стран открыли пограничные ворота на старой Братиславской дороге между Санкт-Маргаретен (Бургенланд) и Шопронкёхида (Sopronkőhidal) символически на три часа. На этом же месте австрийский министр иностранных дел Алоиз Мок и его венгерский коллега Дьюла Хорн 27 июня 1989 совместно разрезали пограничный забор, чтобы подчеркнуть начатую Венгрией 2 мая 1989 года ликвидацию наблюдательных сооружений.
Северная Трансильвания
Введение 1 История 1.1 После I Мировой войны 1.2 Венгерская аннексия 1.3 Окончание II Мировой войны 3 Источники Список литературы Введение Северная Трансильвания (рум. Transilvania de Nord, венг. Йszaki Erdйly) — историко-культурный венгерский регион в составе горной области Трансильвания, составляющей географический запад современной республики Румыния.
Гавро, Лайош
Введение 1 До 1917 года 2 Гражданская война 3 После Гражданской 4 Арест и смерть 5 Факты Список литературы Введение Ла́йош Га́вро (в СССР также Гавро, Людовик Матвеевич) (28 декабря 1894, Брашов — 23 мая 1938) — венгерский интернационалист, активный участник Гражданской войны в России.
Лигети, Карой
Введение 1 Биография 2 Память Список литературы Введение Ка́рой Ша́ндор Ли́гети (венг. Ligeti Kбroly Sбndor, 8 декабря 1890, Кишкёрёш, Австро-Венгрия — 2 июня 1919, Омск, Советская Россия) — венгерский революционер-интернационалист, поэт, руководитель венгерской парторганизации при Федерации иностранных групп РСДРП(б) и редактор её газеты, командир венгерского интернационального отряда.
Сабо, Эрвин
Введение 1 Биография 2 Память 3 Работы Список литературы Введение Эрвин Сабо (венг. Szabу Ervin, 23 августа 1877, Сланица — 29 сентября 1918, Будапешт) — венгерский коммунист (изначально левый социал-демократ, затем эволюционировавший в сторону анархо-синдикализма), теоретик марксизма, деятель рабочего движения, историк и социолог.
Сечени, Иштван
Введение 1 Происхождение, молодость 2 Реформатор 3 Революция 1848—1849 годов в Венгрии 4 Последние годы жизни Введение Граф Иштван Сечени Граф Иштван Сечени (венг. Grуf Szйchenyi Istvбn; 21 сентября 1791, Вена — 8 апреля 1860, Дёблинг) — венгерский политик-реформатор и писатель, внёсший значительный вклад в подъём национального чувства в Венгрии перед всплеском радикализма в 1840-е гг.
Иштван I Святой
Король Иштван I Святой Иштван Великий ) (венг. (Szent) I. Istvбn, в латинизированном варианте Стефан I ) (ок. 970/975 — 15 августа 1038) — нитранский князь (995—997), венгерский надьфейеделем (с 997) и первый король Венгерского королевства (с 1000/1001) из династии Арпадов.
Констанция Арагонская
Введение 1 Королева Венгрии 2 Жена императора Фридриха II 3 Браки и дети Введение Констанция Арагонская (1179 — 23 июня 1222 года, Катания) — принцесса из Арагонского королевского дома (Барселонская династия). В первом браке — королева Венгрии, во втором — императрица Священной Римской империи, королева Германии и Сицилии.
Мадьяр, Людвиг Игнатьевич
План Введение 1 Биография 2 Научная деятельность 3 Книги Введение Лайош Мадьяр Людвиг Игнатьевич Мадьяр или Лайош Мадьяр (венг. Ludwig (Lajos) Magyar, настоящее имя — Мильхофер или Мильгорф Лайош, 25 ноября 1891, Иштванди, комитат Шомодь — 2 ноября 1937, СССР) — венгерский историк-китаевед, политолог и экономист.
Битва на реке Шайо
План Введение 1 Предпосылки 2 Соотношение сил 3 Ход битвы 4 Последствия Битва на реке Шайо Введение Битва на реке Шайо (на реке Сайо, Солёной; в долине Мохи) — сражение 11 апреля 1241 года между войсками венгерского короля Белы IV и его брата, хорватского герцога Коломана, с одной стороны, и монгольскими войсками во главе с Батыем, Шибаном, Каданом и Субэдэем, действовавших в рамках Западного похода монголов 1236—1242 годов и, в частности, похода на Юго-Западную Русь и в Центральную Европу 1240—1242 годов.
Оттон III герцог Баварии
План Введение 1 Биография 2 Семья и дети Введение Оттон III (нем. Otto I von Niederbayern, венг. Ottу; 11 февраля 1261(12610211), Бургхаузен — 9 сентября 1312, Ландсхут) — в 1290—1312 годах герцог Нижней Баварии из династии Виттельсбахов, являвшийся с 1305 по 1307 годы венгерским королём под именем Бела V.
Венгерская автономная область
Жёлтый цвет — территории, входившие в область всё время её существования; красный цвет — отделённые в 1960, зелёный — добавленные в 1960 Венгерская автономная область
Королевство Венгрия
План Введение 1 История 1.1 Древневенгерский период 1.2 Первый австрийский период 1.3 Османский период 2 Австро-Венгрия Королевство Венгрия Введение
Погань, Йожеф
План Введение 1 Биография 2 Сочинения 2.1 На английском языке Введение Джон Пеппер Йожеф Погань (венг. Pogбny Jуszef, урожённый Йожеф Шварц, американский псевдоним — Джон Пеппер (англ. John Pepper); 8 ноября 1886, Будапешт — 1938, СССР) — венгерский писатель, журналист, литературный критик, деятель Венгерской советской республики (ВСР), работник Госплана СССР и Коминтерна.
Дудаш, Йожеф
Йожеф Дудаш , венг. Jуzsef Dudбs (22 сентября 1912, Марошвашархей, Венгерское королевство (ныне в составе Румынии) — 19 января 1957, Будапешт) — венгерский и румынский радикальный политический деятель, возглавивший во время Венгерской революции 1956 г. группы боевиков, виновные в массовых погромах и убийствах сотрудников госбезопасности[1].
Альпари, Дьюла
Дьюла Альпари (венг. Alpбri Gyula; 19 января 1882, Дунафёльдвар — 17 июля 1944, концлагерь Заксенхаузен) — венгерский политический деятель и журналист.
Чеснеки де Милвань, Дьюла
Граф Дью́ла Че́снеки де Ми́лвань (28 июня 1914, Чорваш, Королевство Венгрия, Австро-Венгрия — после 1970, Бразилия) — венгерский поэт, переводчик, политик, в годы 2-й мировой войны — формальный правитель марионеточного Пиндско-Мегленского княжества.
Миндсенти, Йожеф
Миндсенти, Йожеф Его Высокопреосвященство кардинал Йо́жеф Ми́ндсенти (венг. Mindszenty Jуzsef, настоящее имя Йожеф Пехм , венг. Jуzsef Pehm; 29 марта 1892 — 6 мая 1975) — венгерский кардинал. Архиепископ Эстергома и примас Венгрии. Кардинал-священник с титулом церкви Санто-Стефано-Ротондо с 18 февраля 1946.
Баттяни, Лайош
Лайош Баттяни де Неметуйвар (венг. Lajos Batthyбny de Nйmetъjvбr, 10 февраля 1807(18070210), Прессбург — 6 октября 1849, Пешт) — венгерский политик, глава правительства Венгрии во время Венгерского восстания 1848—1849 годов.
Фогараши, Бела
Бела Фогараши (венг. Fogarasi Bйla, 25 июля 1891 — 28 апреля 1959) — венгерский философ-марксист. Биография Участник радикального политического движения в Венгрии до Первой мировой войны, видный работник культурного фронта в Венгерской советской республике, соратник Дьёрдя Лукача, участник его «Воскресного кружка», в котором состояли такие деятели венгерской культуры, как Бела Балаш, Фредерик Антал, Арнольд Хаузер и другие.
Балаш, Бела
Бела Балаш (правильнее Балаж , венг. Balбzs Bйla; наст. имя и фамилия Герберт Бауэр , венг. Bauer Herbert, 4 августа 1884, Сегед, — 17 мая 1949, Будапешт) — венгерский писатель, поэт, драматург, сценарист, теоретик кино.
Печ
Венгерский город Печ родился на месте римского поселения. Печ развивался неспешно, в те далекие времена никому и в голову не могло прийти, что именно здесь в будущем расположится епископат, а спустя века вырастет первый венгерский университет.
Секешфехервар
Секешфехервар называли городом королей. Он лежит у истоков венгерской государственности. Это один из древнейших городов страны. Здесь короновали и хоронили королей, хранили корону и коронационные принадлежности.
Бела Барток (Bartok)
Венгерский композитор, пианист и музыковед-фольклорист. Родился в семье директора сельскохозяйственного училища, музыканта-любителя (играл в местном оркестре) и учительницы. Учился в Будапештской музыкальной академии им. Листа (1899—1903).