Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Владимирский государственный университет им. Столетовых

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Математическая экономика

.pdf

Скачиваний:

190

Добавлен:

22.03.2015

Размер:

3.49 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 89 / 319 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

§ 3.6. Задачи о назначениях и распределительные задачи

Существуют прикладные задачи, которые не связаны с какими-либо перевозками и в этом смысле не являются транспортными. Однако их формализация приводит к модели, совпадающей с транспортной моделью (3.1 – 3.4), хотя и с некоторой спецификой.

Примером такой задачи является так называемая задача о назначениях [3, 32]. Ее можно сформулировать следующим образом.

Задан перечень работ A1 ,..., Am . Для их выполнения можно использовать n станков (или другого оборудования) B1 ,..., Bn , причем одна работа может выполняться одним станком. Выполнение работы Ai на станке Bj связано с затратами cij . Если какая либо работа Ai не может быть выполнена на станке Bj , то соответствующую величину cij будем считать

равной достаточно большому числу.

Необходимо так распределить заданный комплекс работ { A1 ,..., Am } по имеющемуся парку оборудования { B1 ,..., Bn }, чтобы общие затраты были минимальными.

Для формализации этой задачи введем переменную xij , полагая:

1, если i-яработавыполняется на j-м станке;
xij ={0, если i-яработаневыполняется на j-м станке.
Тогда задача сводится к отысканию n m чисел xij , при которых
m n
y = ∑∑cij		xij → inf	(3.7)
i =1 j =1
и выполняются условия
n
i : ∑xij	=1,	i =1,..., m ,	(3.8)
j =1
m
j : ∑xij	=1,	j =1,...,n ,	(3.9)
i=1
x {0,1}.			(3.10)

Эту задачу можно условно интерпретировать как транспортную, если работы рассматривать как исходные пункты или пункты отправления (ПО), а станки (или другое используемое оборудование) как пункты назначения (ПН). В результате решения каждый ПО (работа Ai ) должен быть

связан с определенным ПН ( Bj ). Из смысла этой задачи и требования, по

которому суммы, стоящие в (3.8; 3.9), должны быть равны 1, следует, что в левых частях каждого из уравнений (3.8 – 3.9) одна какая-то переменная будет равна 1, а остальные – равны 0.

Возможна несколько иная формулировка задачи о назначениях [3]. Имеется m человек (исполнителей) A1 ,..., Am и n заданий B1 ,..., Bn . У ис-

полнителей разный уровень квалификации, поэтому на выполнение им потребуется разное время: исполнитель Ai может выполнить работу Bj за

время cij . Требуется спланировать распределение исполнителей по задани-

ям так, чтобы общие затраты времени были минимальными.

Введем переменную xij , которая будет равна 1, если исполнитель Ai назначен на работу Bj , и примем эту переменную равной 0, если этот исполнитель не будет выполнять работу Bj . В таком случае мы получаем

модель (3.7 – 3.10).

Рассматриваемую задачу о назначениях можно представить в виде транспортной табл. 3.20.

Ясно, что при m ≠ n задача будет несбалансированной. Изложенными выше способами ее можно искусственно свести к сбалансированной. В этом случае табл. 3.20 будет квадратной размерами n ×n (или m ×m ). В каждом столбце этой таблицы в одной из клеток x должно быть равно 1, а в остальных клетках x = 0 , аналогичная ситуация будет в каждой строке. Выбор клеток с x =1 необходимо осуществлять так, чтобы сумма cij для

всех выбираемых клеток оказалась минимальной по сравнению с любой другой комбинацией указанного типа.

Т а б л и ц а 3.20

ПО

ПН

Задания (работы)

Заявки

Таким образом, для

…

решения

сбалансирован-

ной

задачи

необходимо

Исполнители

отыскать (выбрать) n кле-

ток

указанной таблице

n ×n .

Может

показаться,

cm1

cmn

что

эта

задача довольно

Запасы

простая

и ее

можно ре-

шить простым перебором

различных вариантов. Однако можно показать [3], что при таком подходе

количество перебираемых вариантов будет определяться величиной n!, и

для задачи большой размерности это количество вариантов может оказаться неприемлемо большим даже для современных быстродействующих компьютеров.

Для решения рассматриваемых задач о назначениях можно использовать методы решения транспортных задач. Однако они оказываются довольно неэффективными. Поэтому для решения задач о назначениях были разработаны специальные методы. С их сущностью и примерами применения можно ознакомиться, например в [14, 32].

Более сложные задачи о назначениях (распределительные задачи) рассмотрены в [14].

Контрольные вопросы

1.Как формулируется классическая транспортная задача?

2.В чем состоит особенность классической ТЗ по сравнению с общей задачей ЛП?

3.Как формируется транспортная таблица?

4.Что представляет собой начальный опорный план для ТЗ?

5.Для чего предназначен и в чем состоит метод северо-западного угла?

6.Для чего предназначен метод потенциалов?

7.Что называется циклом в транспортной таблице, как определяется его цена?

8.Как определяется величина продукта (груза), который можно перераспределить в пределах выделенного цикла?

9.При выполнении какого условия решение транспортной задачи, получаемое методом потенциалов, является оптимальным?

10.Каким образом несбалансированную ТЗ можно свести к классической формулировке?

Задачи для самостоятельного решения

Сбалансированные задачи

Дана классическая транспортная задача с тремя ПО Ai и четырьмя ПН Bj . Информация о запасах перевозимого груза в ПО, заявках на него в ПН и удельных стоимостях перевозок представлена в приведенных ниже

транспортных таблицах. Для соответствующего варианта найти оптимальный план перевозок.

Т а б л и ц а 1

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		2		7		1		3	48


A2		5		6		2		4	23



A3		6		3		1		2	29



bj	21		14		37		28		100

Т а б л и ц а 3

ПН	B		B			B		B		a	i
ПО	1		2			3		4			i
A1		4		3			5		2	33



A2		5		1			2		7	48


A3		8		2			1		3	69



bj	44		42			38		26		150

					Т а б л и ц а 5
ПН	B		B			B		B		a	i
ПО	1		2			3		4			i
A1		8		7			1		4	84



A2		5		6			3		2	59



A3		7		4			5		1	57



bj	48		36			25		91		200

			Т а б л и ц а			2
ПН	B	B	B	B		a
ПО	1	2	3	4		i
A1	5	2	3	4		43
A1						43
A2	7	3	1	2		38
A2						38
A3	9	3	8	7		19
A3						19
bj	15	23	34	28	100

Т а б л и ц а 4

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		11		4		7		1	42


A2		8		6		5		3	29



A3		9		10		2		4	79



bj	37		55		28		30		150

Т а б л и ц а 6

ПО ПН B1 B2 B3 B4 ai

A1		4		9		7		6	64



A2		5		3		6		4	44


A3		7		9		2		1	92



bj	61		57		48		34		200
bj	61		57		48		34

Т а б л и ц а 7

ПН	B		B		B		B		a
ПО	1		2		3		4		i
A1		6		4		2		5	21


A2		8		9		3		7	43



A3		4		5		1		9	61



bj	33		28		47		17		125

Т а б л и ц а 9

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		4		2		3		1	57



A2		8		11		9		6	24


A3		5		10		4		7	59


bj	41		34		22		43		140

Т а б л и ц а 11

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		5		11		13		4	27


A2		6		4		10		8	33
A2									33

A3		7		2		3		9	60



bj	20		32		19		49		120

Т а б л и ц а 8

ПН	B		B		B		B		a
ПО	1		2		3		4		i
A1		3		2		3		4	55



A2		7		2		1		9	42


A3		8		5		2		6	28
A3									28

bj	45		38		29		13		125

Т а б л и ц а 10

ПН	B		B		B		B		a
ПО	1		2		3		4		i
A1		10		13		8		6	41


A2		11		6		5		9	34



A3		8		6		4		3	65
A3									65

bj	35		21		19		65		140

Т а б л и ц а 12

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		9		10		8		5	37



A2		7		4		9		3	34



A3		7		11		13		18	49



bj	43		21		18		38		120

Т а б л и ц а 13

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
ПО
A1		10		4		8		5	49
A1									49

A2		11		5		7		4	32
A2									32

A3		6		12		9		1	29
A3									29

bj	20		17		31		42		110

Т а б л и ц а 15

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		1		2		1		7	61



A2		3		8		4		5	28



A3		6		7		8		5	71


bj	34		43		51		32		160

Т а б л и ц а 17

ПН	B		B		B		B		a
ПО	1		2		3		4		i
A1		5		2		4		6	46


A2		3		9		8		4	37



A3		9		5		6		10	87
A3									87

bj	41		32		55		42		170

Т а б л и ц а 14

ПН	B		B		B		B		a
ПО	1		2		3		4		i
A1		6		1		5		4	42



A2		3		2		7		8	35



A3		6		9		11		1	33



bj	18		27		40		25		110

Т а б л и ц а 16

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		9		7		8		4	56



A2		6		8		3		5	52


A3		4		2		4		3	52


bj	27		49		43		41		160

Т а б л и ц а 18

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		4		5		4		3	62



A2		2		7		6		5	29


A3		6		9		7		5	79


bj	34		39		58		39		170

Т а б л и ц а 19

ПН	B		B		B		B		a
ПО	1		2		3		4		i
A1		3		7		8		2	51


A2		5		6		1		3	77



A3		4		8		7		6	52



bj	46		32		54		48		180

Т а б л и ц а 21

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		2		1		2		5	54



A2		6		5		3		2	42



A3		7		8		4		9	32



bj	29		27		55		19		130

Т а б л и ц а 23

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		5		3		2		6	68



A2		4		8		4		3	77



A3		6		5		5		2	45


bj	48		51		42		49		190

Т а б л и ц а 20

ПН	B		B			B		B		a	i
ПО	1		2			3		4			i
A1		6		5			8		4	62



A2		4		6			3		2	29


A3		1		9			7		3	79
A3										79

bj	34		39			58		39		170

					Т а б л и ц а					22
ПН	B		B			B		B		a	i
ПО	1		2			3		4			i
ПО
A1		3		2			7		5	63
A1										63

A2		6		3			4		6	41
A2										41
A3		5		1			6		9	26
A3										26

bj	18		29			17		66		130

					Т а б л и ц а					24
ПН	B		B			B		B		a	i
ПО	1		2			3		4			i
A1		1		1			4		7	52



A2		5		6			2		3	67



A3		9		7			4		8	51


bj	36		49			54		51		190

Т а б л и ц а 25

ПН	B		B		B		B		a
ПО	1		2		3		4		i
A1		5		3		2		6	75


A2		4		7		4		3	61



A3		2		5		5		1	64



bj	63		58		44		35		200

Т а б л и ц а 27

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		6		4		7		8	27



A2		5		2		3		5	80



A3		9		3		4		6	48



bj	29		33		46		47		155

Т а б л и ц а 26

ПН	B		B		B		B		a
ПО	1		2		3		4		i
A1		2		1		2		5	73



A2		4		3		2		3	38



A3		9		5		7		4	89



bj	47		59		45		49		200

Т а б л и ц а 28

ПН	B		B		B		B		a	i
ПО	1		2		3		4			i
A1		8		5		9		6	65



A2		10		7		5		8	54


A3		5		3		2		9	26


bj	61		42		25		27		155

					Т а б л и ц а 29											Т а б л и ц а 30
ПН	B B B B								a	i	ПО	ПН B B B B a
ПО	1		2		3		4			i	ПО	1		2		3		4		i
A1		4		9		7		8	59		A1		6		4		2		5	71



A2		2		6		1		3	46		A2		9		3		4		7	68
A2									46		A2									68

A3		5		4		8		9	70		A3		5		7		9		10	36
A3									70		A3									36
bj	56		45		37		37		175		bj	28		39		45		63		175
	56		45		37		37		175		bj	28		39		45		63		175

Несбалансированные задачи

Найти решение несбалансированной ТЗ, представленной соответствующей таблицей из предыдущего задания, если запас груза в ПО A1

увеличен на 5 ед., а заявки в ПН B2 уменьшены на 8 ед.

Глава 4. ЗАДАЧИ ОПТИМИЗАЦИИ, ПРЕДСТАВЛЯЕМЫЕ

НА ГРАФАХ

§ 4.1. Основные понятия теории графов

Рассмотрим некоторое конечное множество X с элементами x1, x2 ,..., xn , а также множество X 2 , элементы которого представляют собой всевозможные пары ( xi , x j ), составленные из элементов Х. Пусть в X 2 выделено некоторое подмножество U . Пару множеств G = (X , U ) называют графом. При этом элементы xi X называют вершинами графа, а

элементы uk = (xi , x j ) U – дугами этого графа. Если порядок элементов в парах ( xi , x j ) не принимается во внимание, то граф называется неориен-

тированным. Входящие в него пары называются ребрами. В противном случае, когда граф определяется упорядоченными парами элементов и, следовательно, пары ( xi , x j ) и ( x j , xi ) различны, граф называется ориен-

тированным.

Граф можно представить диаграммой, в которой вершины изображаются точками или кружками, а ребра – отрезками линий, соединяющими соответствующие пары вершин (точек). При этом дуги ориентированного графа изображаются линиями со стрелками, указывающими на порядок элементов в соответствующих парах. На рис. 4.1 приведены примеры неориентированного (а) и ориентированного (б) графов.

x2					х2	u6	х3
							х3
		u3				u5	u9
					u1		u9
	u2				x5	u2
x1					х1	u3	х5
u1	u5		u	6	u4	х4	u8
u1				6	u4		u8
	u4	x4
x3	u4	x4			б)	u7
а)					б)

Рис. 4.1

Используя подобные диаграммы, можно приведенному выше теоре- тико-множественному определению графа дать простую и наглядную ин-

терпретацию: граф – это множество точек, называемых вершинами, и множество линий, соединяющих отдельные пары этих точек и называемых ребрами или дугами.

Вершины xi и x j , определяющие ребро uk = (xi , x j ) , называются концевыми вершинами этого ребра. При этом в ориентированном графе одна из концевых вершин дуги uk = (xi , x j ) называется начальной (первая – xi ), а другая – x j – конечной. Две вершины называются смежными, если

они являются концевыми вершинами некоторого ребра. Два ребра называются смежными, если они имеют общую концевую вершину. Ребро называется инцидентным некоторой вершине xi , если она является концевой

точкой этого ребра. Отметим, что концевые вершины ребра в графе не обязательно различны. Если uk = (xi , xi ) U , то ребро uk называют петлей.

Иногда рассматривают графы, в которых имеется более одного ребра с одинаковыми концевыми вершинами. Такие ребра называют параллельными, а соответствующий граф – мультиграфом. Граф, не содержащий параллельных ребер и петель, называется простым.

Используя упомянутые понятия смежности и инцидентности, графы можно задавать в удобной матричной форме. Так, например, любой граф G = (X , U ) , имеющий n вершин, однозначно определяется матрицей А с

элементами aij , равными числу дуг, идущих от xi к x j (при их отсутствии aij = 0). Эта матрица называется матрицей смежности вершин графа. Для графов, изображенных на рис. 4.1, она имеет вид

x1	x1 x2 x3 x4 x5	x1	x1 x2 x3 x4 x5
	0 0 1 0 0		0 1 1 1 1
x	0 0 0 1 1	x	0 0 1 0 0
2		2
A = x3	1 0 0 1 1	, A = x3	0 1 0 0 1 .
x	0 1 1 0 1	x	0 0 0 1 1
4		4
x	0 1 1 1 0	x	0 0 0 0 0
5		5

Очевидно, что для неориентированного графа матрица А будет симметрической.

Другие виды матриц, задающих графы, см., например в [28].

При решении многих задач на графах на базе исходных графов образуют новые графы. Широко используются, в частности, следующие разновидности получаемых при этом графов.

<<< < Предыдущая 1 2 3 4 5 6 7 89 / 319 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
25.09.2019623.1 Кб2мат анализ.doc
#
22.03.2015271.27 Кб30Матан.pdf
#
21.03.20152.6 Mб33Матвеев П.Е. Ценностный подход в этике.pdf
#
26.09.2019246.21 Кб3Математика экзамен.docx
#
21.03.201531.74 Кб103Математика-зимняя сессия_1 семестр.doc
#
22.03.20153.49 Mб190Математическая экономика.pdf
#
21.03.20152.48 Mб33материаловедение зачет.doc
#
21.03.2015141.31 Кб26матлаб.doc
#
07.03.201615.55 Mб857Медведев В.С., Потемкин В.Г. Нейронные сети. MATLAB 6.doc
#
07.03.20161.24 Mб883Медицина катастроф.Методпособие к лабор.docx
#
07.03.2016179.31 Кб236Медицина катостроф.МУ к лабораторным.docx

x2					х2	u6	х3
							х3
		u3				u5	u9
					u1		u9
	u2				x5	u2
x1					х1	u3	х5
u1	u5		u	6	u4	х4	u8
u1				6	u4		u8
	u4	x4
x3	u4	x4			б)	u7
а)					б)

x2					х2	u6	х3
							х3
		u3				u5	u9
					u1		u9
	u2				x5	u2
x1					х1	u3	х5
u1	u5		u	6	u4	х4	u8
u1				6	u4		u8
	u4	x4
x3	u4	x4			б)	u7
а)					б)

x2					х2	u6	х3
							х3
		u3				u5	u9
					u1		u9
	u2				x5	u2
x1					х1	u3	х5
u1	u5		u	6	u4	х4	u8
u1				6	u4		u8
	u4	x4
x3	u4	x4			б)	u7
а)					б)