Изменения

Перейти к: навигация, поиск

Задача о назначениях

4078 байтов убрано, 10:20, 28 сентября 2016
[[файл:ТЗ01ЗН01.JPG|thumb|300|[[Математическая модель]] ТЗЗН]]'''Задача о назначениях''' – это задача оптимального назначения работ исполнителям.
== Постановка задачи ==
Пусть имеется '''mn''' поставщиков работ '''(A1,A2,…,AmAn)''' и '''n''' потребителей исполнителей '''(B1,B2,…,Bn)''' однородного продукта. Пусть заданы объёмы поставок '''a<sub>i</sub>''' продукта поставщиком '''Ai''' и объёмы потребностей '''b<sub>j</sub>''' в продукте у потребителя '''Bj'''. Пусть известны транспортные расходы доходы '''c<sub>ij</sub>''' на перевозку единицы продукта от поставщика назначения '''Aii''' -ой работы к потребителю '''Bjj''' -ому исполнителю и необходимо определить план перевозок назначения с минимальной наибольшей суммой транспортных расходовдоходов, тогда классическая [[Транспортная задача с промежуточными пунктами|транспортная при этом каждая работа назначается только одному исполнителю и каждый исполнитель назначается только на одну работу.Тогда задача]] о назначениях (ТЗЗН) формулируется следующим образом:
[[файл:ТЗ01ЗН01.JPG]], где '''x<sub>ij</sub>''' - объём перевозок продукта от поставщика '''Ai''' к потребителю '''Bj'''. [[Трёхиндексная транспортная задача|Транспортную задачу]] можно представить в виде таблицы  [[файл:ТЗ03.JPG]]. == Условия разрешимости ==Для разрешимости задачи необходимо выполнение условий баланса: [[файл:ТЗ02.JPG]], т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём.
где '''x<sub>ij</sub>''' – '''1''' если есть назначение '''i'''-ой работы '''j'''-ому исполнителю, '''0''' - если нет назначения.
== Метод решения ==
Необходимо найти начальное опорное решение, например, Задача о назначениях решается венгерским методом северо-западного угла.== Пример ЗН ==[[файл:ЗН09.JPG]]
Затем транспортная задача решается методом потенциалов[[файл:ЗН10.JPG]]=== Подготовительный этап ===[[файл:ЗН12.JPG]]
=== Метод северо-западного угла ===Метод северо-западного угла для нахождения допустимого решения транспортной задачи состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах[[файл:ЗН13. JPG]]
1.Удовлетворяем потребности потребителей '''(b<sub>j</sub>>0)''' за счёт поставщиков '''(a<sub>i</sub>>0)''', т.е. назначаем соответствующие перевозки по формулам: '''x<sub>ij</sub>=min(ai,bj), ai=ai-x<sub>ij</sub>, b<sub>j</sub>=b<sub>j</sub>-x<sub>ij</sub>'''. 2.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности. === Метод потенциалов === 1.Берём решение '''Xmxn''' и базис '''Zmxn''', найденные, например, с помощью '''алгоритма северо-западного угла'''.  2.Определяем значение целевой функции '''L=ΣΣc<sub>ij</sub>x<sub>ij</sub>''' и базис опорного решения '''Bo={(i,j)|z<sub>ij</sub>=1}'''. 3.Определяем оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>)''' с помощью '''[[Алгоритм расчёта потенциалов|алгоритма расчёта потенциалов]]''' и оценок оптимальности. 4.Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxn''' - оптимальное и конец работы. 5.Определяем оценку '''Δx''', элемент '''(i<sub>x</sub>,j<sub>x</sub>)''' и новое опорное решение '''Xmxn''' с помощью '''[[Алгоритм перераспределения перевозок|алгоритма перераспределения перевозок]]'''. 6.Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i<sub>x</sub>,j<sub>x</sub>)U(i<sub>o</sub>,j<sub>o</sub>)'''.Переходим к пункту 3. == Пример ТЗ ==[[файл:ТЗ10ЗН14.JPG]] === Нахождение допустимого решения ===[[файл:ТЗ11.JPG]][[файл:ТЗ12.JPG]][[файл:ТЗ13.JPG]][[файл:ТЗ14.JPG]] === Решение венгерским методом потенциалов ===[[файл:ТЗ21ЗН21.JPG]][[файл:ТЗ22ЗН22.JPG]][[файл:ТЗ23ЗН23.JPG]]
Оптимальное решение равно
[[файл:ЗН30.JPG]]
== Другие задачи: ==
*[[Каноническая задача]];*[[Производственная задача]];*[[Общая прямая задача линейного программирования]];*[[Общая двойственная задача линейного программирования]];*[[Распределительная задача]];*[[Задача о назначениях]];*[[Транспортная задача с промежуточными пунктами]];*[[Трёхиндексная транспортная задача]];*[[Задача целочисленного программирования]];*[[Задача о рюкзаке]].{{Список ЗТТ}}
== Ссылки ==
* Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
* [[Участник:Logic-samara]]
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]
40 519
правок