Мат. методы (Новичихин)

11

Задаемся потенциалом четвертой строки U4=10. Затем по правилу оптимизации определяем остальные потенциалы; например: при U4=10 потенциал V5 определится:

V 5 = U 4 + c45 = 10 + 10 = 20

U 3 = V 5 − c35 = 20 − 9 = 11 и т.д.

После определения всех потенциалов проверяем оптимальность плана по условию

V j −U i ≤ cij для xij=0

Величиной нарушения будем считать значение:

H = Vj − Ui − cij , т.е. H>0

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

Наибольшее нарушение равное H31=4 имеем в клетке R3P1.

Выявив величину нарушения, вводим поправки в ранее принятый план путем изменения значений xij.

Для этого из выбранной клетки с нарушением проводим замкнутую ломаную линию, двигаясь аналогично ходу шахматной ладьи, при этом изменение движения производим в загруженных клетках на угол 900. Эта линия носит название контура. Там где линия меняет направление, корреспонденции подлежат изменению. Поставим знаки «+» и «-» у вершины контура, начиная с «+» в клетке с нарушением . «+»означает, что корреспонденция должна быть увеличена , а «-» - уменьшена.

Величина потока улучшения должна быть равна минимальной корреспонденции со знаком «-», т.е. xул.=min xij(-). Такая корреспонденция у нас в клетке R3P3=130. Перемещаем эту величину по контуру и получаем новый план (табл.6).

При улучшении плана в одной или нескольких загруженных ранее клетках могут оказаться 0. Если число загруженных клеток равно (m+n-1), то освободившиеся клетки переходят в число незагруженных. Если число загруженных клеток меньше (m+n-1), то одна из освободившихся клеток с 0 может считаться загруженной.

Следующий план (табл.6) оказался снова не оптимальным. Улучшение плана продолжаем дальше.

							12
													Таблица 6
			13		13		15		16		20
	Ri	Pj	P1		P2		P3		P4		P5		ai
9	R1		10	4	190	4	+1	5	+1	6	+4	7	200
				-								+
12	R2			7	70	1	230	3		8		11	300
11	R3		130	2		4		8	140	5	80	9	350
				+								-
10	R4			10		7		9	+3	3	150	10	150
	bj		140		260		230		140		230		1000

Во второй итерации наибольшее нарушение имеет клетка R1P5; H=4. Для этой клетки строим контур, начиная в клетке R1P5; поток улучшения xул.=10 (min значение потока по контуру со знаком «-»). Перемещаем по контуру это значение и получаем новый план (табл.7)

													Таблица 7
			13		17		19		16		20
	Ri	Pj	P1		P2		P3		P4		P5		ai
13	R1			4	190	4	+1	5		6	10	7	200
16	R2			7	70	1	230	3		8		11	300
11	R3		140	2	+2	4		8	140	5	70	9	350
										-		+
10	R4			10		7		9	+3	3	150	10	150
										+		-
	bj		140		260		230		140		230		1000
													Таблица 8
			13		17		19		13		20
	Ri	Pj	P1		P2		P3		P4		P5		ai
13	R1			4	190	4	+1	5		6	10	7	200
						-						+
16	R2			7	70	1	230	3		8		11	300
11	R3		140	2	+2	4		8		5	210	9	350
						+						-
10	R4			10		7		9	140	3	10	10	150
	bj		140		260		230		140		230		1000

13

xул по данной итерации (-140).

Перемещаем xул по контуру и получаем следующий план (табл.8).

Применив к этому варианту все принятые действия, получим новый вариант плана (табл.9) xул=190.

				Таблица 9
13	15	17	13	20

	Ri	Pj	P1		P2		P3		P4		P5		ai
13	R1			4		4		5		6	200	7	200
14	R2			7	70	1	230	3		8		11	300
11	R3		140	2	190	4		8		5	20	9	350
10	R4			10		7		9	140	3	10	10	150
	bj		140		260		230		140		230		1000

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

Если получим клетки с H=Vj-Ui-cij=0, то это значит, что существуют другие оптимальные планы, имеющие минимальные значения критерия оптимальности.

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

14

3 Двухэтапная транспортная задача

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

Единый вопрос: «кто кого снабжает?», решаемый транспортной задачей распадается на два взаимосвязанных вопроса: «с какого предприятия - на какой склад?» и «с какого склада - какому потребителю?» следует перевозить продукцию, чтобы получить минимум затрат.

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

Двухэтапная транспортная задача формулируется следующим образом. Допустим, имеются пункты производства R1, R2,…,R m с возможными размера-

ми ресурсов a1, a2,…,a m. Известны также потребители ресурсов P1, P2,…,P n с потреб-

ностями b1,…, bj,…,b n.

По пути к потребителю каждая единица продукции должна быть завезена на один из складов D1,…,D k с перерабатывающей способностью S1,…,S k.

cik – затраты на перевозку единицы продукции от любого изготовителя Ri на любой склад Dk;

ckj – затраты на перевозку со склада Dk к потребителю Pj;

Sk – издержки хранения и обработки продукции на складе Dk;

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

∑ Dk ³ ∑ Ri

( k ) (i )

Общая мощность предприятий должна быть больше потребностей, т.е.

∑ R ³ ∑ Pj

(i) ( j )

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

xik – размер поставки от поставщика Ri на Dk; xkj – размер поставки со склада Dk к Pj.

План должен удовлетворять следующим условиям:

∑ xkj = Pj

( k )

∑ xik £ Ri

k

Поступление продукции на склад не превышает его перерабатывающей способности:

15

∑ xik £ ∑ Dk

(i ) (k )

Сумма поступления продукции на склад равна сумме её вывоза с того же склада:

∑ xik £ ∑ xkj

(i) (k )

Целевая функция выглядит следующим образом:

F = ∑∑cik × xik + ∑∑ckj × xkj + ∑ Sk ∑ xkj ® min

(i) (k )

( k ) ( j )

(k )

j

или

F = ∑∑cik × xik + ∑∑ckj × xkj + ∑∑ Sk × xik ® min ;

(i) (k )

( k ) ( j )

k

k

так как ∑∑ Sk xkj = ∑∑ Sk × xik

( k ) ( j )

(i) ( k )

Если ∑ Dk = ∑ Pj , то двухэтапная задача может решаться как две независимых

( k ) ( j )

задачи.

Если ∑ Dk > ∑ Pj , то решения по прикреплению складов к заводам и потреби-

( k ) ( j )

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

Рассмотрим пример:

R1=350; R2=400; R3=550 ед. ресурсов; D1=900; D2=500 ед.

P1=360; P2=230; P3=410; P4=200 ед. ресурсов.

Составляем матрицу. Особенность её заключается в том, что склады представлены в ней и как потребители, и как поставщики (табл. 24).

																Таблица 24
			6		7		11		12		13		10		0
	Ri	Pj	D1		D2		P1		P2		P3		P4		Pф		ai
4	R1		350	2	+1	2		м		м		м		м		0	350
				-		+
3	R2			5	400	4		м		м		м		м		0	400
0	R3		350	6	100	7		м		м		м		м	100	0	550
				+		-
6	D1		200	0		м	60	5	230	6	410	7		8		м	900
								+				-
8	D2			м		0	300	3		7	+1	4	200	2		м	500
								-				+
	bj		900		500		360		230		410		200		100		2700
		Начальный план при решении задачи составляется в следующем порядке.

16

В начале методом наименьшего значения показателя оптимальности заполняется первая нижняя часть матрицы. Избыток мощности складов заносят в клетки фиктивной диагонали (D1D1 и D2D2) – левый нижний квадрант.

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

вклетки столбца фиктивного потребителя.

Врезультате решения (методом потенциалов) получаем оптимальную матрицу (табл.25).

Как видно из табл.25 мощность поставщика R3 используется не полностью. Перерабатывающая способность складов недоиспользуется на 200ед.

															Таблица 25
			6		6		11		12		13		11	0
	Ri	Pj	D1		D2		P1		P2		P3		P4	Pф		ai
4	R1		250	2	100	2		м		м		м	м		0	350
2	R2			5	400	4		м		м		м	м		0	400
0	R3		450	6		7		м		м		м	м	100	0	550
6	D1		200	0		м	360	5	230	6	110	7	8		м	900

9	D2	м	0	3	7	300	4	200	2		м	500
	bj	900	500	360	230	410		200		100		2700

В левом верхнем квадранте матрицы получено оптимальное прикрепление поставщиков к складам, в правом нижнем – прикрепление потребителей к складам.