Добавил:

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

Вуз:

Сибирский Государственный Университет Путей Сообщения

Предмет:

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

Файл:

rgr_1.docx

Скачиваний:

Добавлен:

01.07.2025

Размер:

241 Кб

Скачать

☆

<<< < Предыдущая 1 2 34 / 54 5 > Следующая >>>

4.Метод потенциалов

U_i и V_i– потенциалы поставщиков и потребителей соответственно.

U_i + V_i= C_ij для Х_ij >0

i= , j=

U_i + V_i C_ijдля Х_ij =0 (*)

Для каждой занятой клетки сумма потенциалов должна быть равна стоимости единицы перевозки, стоящей в этой клетке: U_i + V_i= C_ij
Для каждой незанятой клетки сумма потенциалов должна быть меньше или равна стоимости единиц перевозки, стоящей в этой клетке: U_i + V_i C_ij

Если хотя бы одна незанятая клетка не удовлетворяет условию (*), то в эту клетку надо переместить некоторое количество груза.

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

Таблица 1.4.1

	22			24			7			25			23		29	24		U1=-2
22			2
	1			21			30			10			7		19	14		U2=-4
			14
	2			26			3			18			30		27	19		U3=0
			3			10			6
	22			10			9			29			26		23	27		U4=11
									8			17		2
	18			16			13			17			18		19	16		U5=6
														16
22		19			10			14			17			18			100
V1=24		V2=26			V3=3			V4=18			V5=15			V6=12

W =22*22+48+14*21+3*26+30+6*18+8*29+17*26+46+16*19=2066

Таблица 1.4.2

	22			24			7			25			23		29	24		U1=14
22			2
	1			21			30			10			7		19	14		U2=-19
												14
	2			26			3			18			30		27	19		U3=-11
			3			10			6
	22			10			9			29			26		23	27		U4=0
			14						8			3		2
	18			16			13			17			18		19	16		U5=-4
														16
22		19			10			14			17			18			100
V1=8		V2=10			V3=14			V4=29			V5=26			V6=23

W =22*22+48+3*26+140+30+6*18+8*29+14*7+3*26+46+16*19=1646

Таблица 1.4.3

	22			24			7			25			23		29	24		U1=20
19			2									3
	1			21			30			10			7		19	14		U2=4
												14
	2			26			3			18			30		27	19		U3=0
3						10			6
	22			10			9			29			26		23	27		U4=11
			17						8					2
	18			16			13			17			18		19	16		U5=7
														16
22		19			10			14			17			18			100
V1=2		V2=-1			V3=3			V4=18			V5=3			V6=12

W =19*22+6+48+170+30+6*18+8*29+3*23+14*7+46+16*19=1529

Таблица 1.4.4

	22			24			7			25			23		29	24		U1=20
19									2			3
	1			21			30			10			7		19	14		U2=4
												14
	2			26			3			18			30		27	19		U3=0
3						10			6
	22			10			9			29			26		23	27		U4=24
			19						6					2
	18			16			13			17			18		19	16		U5=20
														16
22		19			10			14			17			18			100
V1=2		V2=-14			V3=3			V4=5			V5=3			V6=-1

W = 19*22+6+190+30+50+6*18+6*29+3*23+14*7+46+16*19=1493

Таблица 1.4.5

	22		24			7			25			23			29	24		U1=7
19							2			3
	1		21			30			10			7			19	14		U2=-9
										14
	2		26			3			18			30			27	19		U3=0
3				10			6
	22		10			9			29			26			23	27		U4=3
		19											8
	18		16			13			17			18			19	16		U5=-1
							6						10
22		19			10			14			17			18			100
V1=2		V2=7			V3=3			V4=18			V5=16			V6=20

W=19*22+6+190+30+50+6*18+6*17+3*23+14*7+8*23+190=1445

Таблица 1.4.6

	22			24				7				25				23				29		24
9							10				2				3								U1=0
	1			21				30				10				7				19		14
															14								U2=-16
	2			26				3				18				30				27		19
13											6												U3=-20
	22			10				9				29				26				23		27
			19																8				U4=-4
	18			16				13				17				18				19		16
											6								10				U5=-8
22			19			10				14				17				18			100
V1=22		V2=14			V3=7				V4=25				V5=23				V6=27

W = 9*22+26+190+70+50+6*18+6*17+23*3+14*7+8*23+190=1285

Таблица 1.4.7

	22			24				7				25				23				29		24
							10				2				12								U1=0
	1			21				30				10				7				19		14
9															5								U2=-16
	2			26				3				18				30				27		19
13											6												U3=-7
	22			10				9				29				26				23		27
			19																8				U4=-4
	18			16				13				17				18				19		16
											6								10				U5=-8
22			19			10				14				17				18			100
V1=9		V2=14			V3=7				V4=25				V5=23				V6=27

W = 9+26+190+70+50+6*18+6*17+12*23+35+8*23+190=1240

Таблица 1.4.8

	22		24		7		25			23			29		24
				10		8			6
	1		21		30		10			7			19		14
3									11
	2		26		3		18			30			27		19
19
	22		10		9		29			26			23		27
		19										8
	18		16		13		17			18			19		16
						6						10
22		19		10		14		17			18			100

W = 3+38+190+70+8*25+6*17+6*23+11*7+8*23+190=1192

Больше нет ячеек, удовлетворяющих условию С_ij≥ U_i + V_j, значит оптимальный план перевозок найден.

<<< < Предыдущая 1 2 34 / 54 5 > Следующая >>>

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

#
01.05.202547 Кб3Referat_po_filosofii.docx
#
01.07.202562 Кб1repetitor_info_03ddcf2b.doc
#
01.07.2025609 Кб2research OB.docx
#
01.05.2025311 Кб4Rezhim_truda_i_otdykha_DZhinsoman переделанный2...doc
#
01.05.202528 Кб1rgr - копия.docx
#
01.07.2025241 Кб2rgr_1.docx
#
22.03.2016291 Кб11RGR_Lineynaya_algebra.pdf
#
01.07.2025118 Кб1RGR_po_metodam_PUR.docx
#
01.07.2025208 Кб2RGR2.docx
#
17.04.201590 Кб29RT_PKZ.doc
#
04.08.201947 Кб9Russky_yazyk.docx

	22		24		7		25			23			29		24
				10		8			6
	1		21		30		10			7			19		14
3									11
	2		26		3		18			30			27		19
19
	22		10		9		29			26			23		27
		19										8
	18		16		13		17			18			19		16
						6						10
22		19		10		14		17			18			100

	22		24		7		25			23			29		24
				10		8			6
	1		21		30		10			7			19		14
3									11
	2		26		3		18			30			27		19
19
	22		10		9		29			26			23		27
		19										8
	18		16		13		17			18			19		16
						6						10
22		19		10		14		17			18			100

	22		24		7		25			23			29		24
				10		8			6
	1		21		30		10			7			19		14
3									11
	2		26		3		18			30			27		19
19
	22		10		9		29			26			23		27
		19										8
	18		16		13		17			18			19		16
						6						10
22		19		10		14		17			18			100