Задача о назначениях — различия между версиями

Материал из ALL
Перейти к: навигация, поиск
(Новая страница: «[[Математическая модель ТЗ]] == Постановка задачи == Пусть имеется '''m''' п…»)
 
Строка 1: Строка 1:
−
[[файл:ТЗ01.JPG|thumb|300|[[Математическая модель]] ТЗ]]
+
[[файл:ЗН01.JPG|thumb|300|[[Математическая модель]] ЗН]]
 
== Постановка задачи ==
 
== Постановка задачи ==
−
Пусть имеется '''m''' поставщиков '''(A1,A2,…,Am)''' и '''n''' потребителей '''(B1,B2,…,Bn)'''  однородного продукта. Пусть заданы объёмы поставок '''a<sub>i</sub>''' продукта поставщиком '''Ai''' и объёмы потребностей '''b<sub>j</sub>''' в продукте у потребителя '''Bj'''. Пусть известны транспортные расходы '''c<sub>ij</sub>''' на перевозку единицы продукта от поставщика '''Ai'''  к потребителю '''Bj''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда классическая [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТЗ) формулируется следующим образом:
+
Пусть имеется '''n''' работ '''(A1,A2,…,An)''' и '''n''' исполнителей '''(B1,B2,…,Bn)'''. Пусть известны доходы '''c<sub>ij</sub>''' от назначения '''i'''-ой работы '''j'''-ому исполнителю и необходимо определить назначения с наибольшей суммой доходов, при этом каждая работа назначается только одному исполнителю и каждый исполнитель назначается только на одну работу.
 +
Тогда задача о назначениях (ЗН) формулируется следующим образом:
  
−
[[файл:ТЗ01.JPG]],
+
[[файл:ЗН01.JPG]],
  
−
где  '''x<sub>ij</sub>''' - объём перевозок продукта от поставщика '''Ai''' к потребителю '''Bj'''.
+
где  '''x<sub>ij</sub>''' – '''1''' если есть назначение '''i'''-ой работы '''j'''-ому исполнителю, '''0''' - если нет назначения.
−
 
+
−
[[Трёхиндексная транспортная задача|Транспортную задачу]] можно представить в виде таблицы
+
−
 
+
−
[[файл:ТЗ03.JPG]].
+
−
 
+
−
== Условия разрешимости ==
+
−
Для разрешимости задачи необходимо выполнение условий баланса:
+
−
 
+
−
[[файл:ТЗ02.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>)''' с помощью '''[[Алгоритм расчёта потенциалов|алгоритма расчёта потенциалов]]''' и оценок оптимальности.
+
== Пример ЗН ==
 +
[[файл:ЗН10.JPG]]
  
−
4.Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxn''' - оптимальное и конец работы.
+
[[файл:ЗН11.JPG]]
  
−
5.Определяем оценку '''Δx''', элемент '''(i<sub>x</sub>,j<sub>x</sub>)''' и новое опорное решение '''Xmxn''' с помощью '''[[Алгоритм перераспределения перевозок|алгоритма перераспределения перевозок]]'''.
+
=== Подготовительный этап ===
 +
[[файл:ЗН12.JPG]]
  
−
6.Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i<sub>x</sub>,j<sub>x</sub>)U(i<sub>o</sub>,j<sub>o</sub>)'''.
+
[[файл:ЗН13.JPG]]
−
Переходим к пункту 3.
+
  
−
== Пример ТЗ ==
+
[[файл:ЗН14.JPG]]
−
[[файл:ТЗ10.JPG]]
+
  
−
=== Нахождение допустимого решения ===
+
=== Решение венгерским методом ===
−
[[файл:ТЗ11.JPG]]
+
[[файл:ЗН21.JPG]]
−
[[файл:ТЗ12.JPG]]
+
[[файл:ЗН22.JPG]]
−
[[файл:ТЗ13.JPG]]
+
[[файл:ЗН23.JPG]]
−
[[файл:ТЗ14.JPG]]
+
  
−
=== Решение методом потенциалов ===
+
Оптимальное решение равно
−
[[файл:ТЗ21.JPG]]
+
[[файл:ЗН30.JPG]]
−
[[файл:ТЗ22.JPG]]
+
−
[[файл:ТЗ23.JPG]]
+
  
 
== Другие задачи: ==
 
== Другие задачи: ==
Строка 64: Строка 36:
 
*[[Общая прямая задача линейного программирования]];
 
*[[Общая прямая задача линейного программирования]];
 
*[[Общая двойственная задача линейного программирования]];
 
*[[Общая двойственная задача линейного программирования]];
 +
*[[Классическая транспортная задача]];
 
*[[Распределительная задача]];
 
*[[Распределительная задача]];
−
*[[Задача о назначениях]];
 
 
*[[Транспортная задача с промежуточными пунктами]];
 
*[[Транспортная задача с промежуточными пунктами]];
 
*[[Трёхиндексная транспортная задача]];
 
*[[Трёхиндексная транспортная задача]];

Версия 12:41, 15 ноября 2015

Математическая модель ЗН

Постановка задачи

Пусть имеется n работ (A1,A2,…,An) и n исполнителей (B1,B2,…,Bn). Пусть известны доходы cij от назначения i-ой работы j-ому исполнителю и необходимо определить назначения с наибольшей суммой доходов, при этом каждая работа назначается только одному исполнителю и каждый исполнитель назначается только на одну работу. Тогда задача о назначениях (ЗН) формулируется следующим образом:

ЗН01.JPG,

где xij – 1 если есть назначение i-ой работы j-ому исполнителю, 0 - если нет назначения.

Метод решения

Задача о назначениях решается венгерским методом.

Пример ЗН

ЗН10.JPG

Файл:ЗН11.JPG

Подготовительный этап

ЗН12.JPG

ЗН13.JPG

ЗН14.JPG

Решение венгерским методом

ЗН21.JPG ЗН22.JPG ЗН23.JPG

Оптимальное решение равно ЗН30.JPG

Другие задачи:

Ссылки

  • Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
  • Участник:Logic-samara
Источник — «https://allll.net/w/index.php?title=Задача_о_назначениях&oldid=18883»