Задача о назначениях - История изменений

Logic-samara в 10:20, 28 сентября 2016

2016-09-28T10:20:59Z

Logic-samara в 10:20, 28 сентября 2016

2016-09-28T10:20:04Z

Logic-samara в 17:52, 2 февраля 2016

2016-02-02T17:52:47Z

Logic-samara в 04:43, 14 января 2016

2016-01-14T04:43:35Z

Logic-samara в 19:53, 13 января 2016

2016-01-13T19:53:15Z

Logic-samara в 19:39, 13 января 2016

2016-01-13T19:39:50Z

Logic-samara в 19:34, 13 января 2016

2016-01-13T19:34:28Z

Logic-samara в 05:59, 16 ноября 2015

2015-11-16T05:59:52Z

Logic-samara в 05:50, 16 ноября 2015

2015-11-16T05:50:38Z

Logic-samara в 12:41, 15 ноября 2015

2015-11-15T12:41:47Z

@@ Строка 27: / Строка 27: @@
 Оптимальное решение равно
 [[файл:ЗН30.JPG]]
-== Другие ТЗ: ==
+== Другие задачи: ==
 {{Список ЗТТ}}
 == Ссылки ==

@@ Строка 27: / Строка 27: @@
 Оптимальное решение равно
 [[файл:ЗН30.JPG]]
-== Другие задачи: ==
+== Другие ТЗ: ==
-*[[Каноническая задача]];
+{{Список ЗТТ}}
-*[[Производственная задача]];
-*[[Общая прямая задача линейного программирования]];
-*[[Общая двойственная задача линейного программирования]];
-*[[Транспортная задача]];
-*[[Распределительная задача]];
-*[[Задача о назначениях]];
-*[[Транспортная задача с промежуточными пунктами]];
-*[[Трёхиндексная транспортная задача]];
-*[[Задача целочисленного программирования]];
-*[[Задача о рюкзаке]].
 == Ссылки ==
 * Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
 * [[Участник:Logic-samara]]
 [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]

@@ Строка 34: / Строка 34: @@
 *[[Транспортная задача]];
 *[[Распределительная задача]];
 *[[Транспортная задача с промежуточными пунктами]];
 *[[Трёхиндексная транспортная задача]];

@@ Строка 15: / Строка 15: @@
 [[файл:ЗН10.JPG]]
 === Подготовительный этап ===
-[[файл:ЗН11.JPG]]
+[[файл:ЗН12.JPG]]
 [[файл:ЗН13.JPG]]

@@ Строка 21: / Строка 21: @@
 [[файл:ЗН14.JPG]]
 === Решение венгерским методом ===
 [[файл:ЗН22.JPG]]
 [[файл:ЗН23.JPG]]
 Оптимальное решение равно

← Предыдущая		Версия 05:59, 16 ноября 2015
Строка 29:		Строка 29:

	Оптимальное решение равно		Оптимальное решение равно
		+
	[[файл:ЗН30.JPG]]		[[файл:ЗН30.JPG]]

@@ Строка 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]],
-−
-т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём.
 == Метод решения ==
-Необходимо найти начальное опорное решение, например, методом северо-западного угла.
+Задача о назначениях решается венгерским методом.
-−
-Затем транспортная задача решается методом потенциалов.
-−
-=== Метод северо-западного угла ===
-Метод северо-западного угла для нахождения допустимого решения  транспортной задачи состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах.
-−
-.Удовлетворяем потребности потребителей '''(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>'''.
-−
-.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности.
-−
-=== Метод потенциалов ===
-−
-.Берём решение '''Xmxn''' и базис '''Zmxn''', найденные, например, с помощью '''алгоритма северо-западного угла'''.
-−
-.Определяем значение целевой функции '''L=ΣΣc<sub>ij</sub>x<sub>ij</sub>''' и базис опорного решения '''Bo={(i,j)|z<sub>ij</sub>=1}'''.
-.Определяем оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>)''' с помощью '''[[Алгоритм расчёта потенциалов|алгоритма расчёта потенциалов]]''' и оценок оптимальности.
+== Пример ЗН ==
-.Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxn''' - оптимальное и конец работы.
+[[файл:ЗН11.JPG]]
-.Определяем оценку '''Δx''', элемент '''(i<sub>x</sub>,j<sub>x</sub>)''' и новое опорное решение '''Xmxn''' с помощью '''[[Алгоритм перераспределения перевозок|алгоритма перераспределения перевозок]]'''.
+=== Подготовительный этап ===
-.Определяем новое значение целевой функции '''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: @@
 *[[Общая прямая задача линейного программирования]];
 *[[Общая двойственная задача линейного программирования]];
 *[[Распределительная задача]];
 *[[Транспортная задача с промежуточными пунктами]];
 *[[Трёхиндексная транспортная задача]];