Задача 2.4

Xij-количество направленных студентов от i-ого студенческого отряда к j-ому полю.

Z- суммарное количество убранного картофеля со всех полей за рабочий день

Z”-суммарные издержки от убранного картофеля всех отрядов и со всех полей.

Ui-оценка i-ого отряда

Vj-оценка j-ого поля

Ai-количество студентов в i-ом отряде

Bj-потребность в рабочей силе в j-ом поле

рij- производительность труда i-ого отряда в j-ом поле на одного человека.

Матрица производительности труда, pij

Ai,Bj		B1	B2	B3	B4	В0
		47	59	49	43	51
А1	70	3	7	2	5	0
А2	99	2	3	4	6	0
А3	80	6	4	3	5	0

Проверка на балансированность:

EAi=70+99+80=249 чел.

EBj=47+59+49+43=198 чел.

Задача не балансированна. Вводим фиктивное поле В0 с требуемой численностью 249-198=51 чел.

Математическая модель прямой задачи:

Z=3X₁₁+7X₁₂+2X₁₃+5X₁₄+2X₂₁+3X₂₂+4X₂₃+6X₂₄+6X₃₁+4X₃₂+3X₃₃+5X₃₄ -MAX

Система ограничений:

X₁₁+X₁₂+X₁₃+X₁₄=70 X₁₁+X₂₁+X₃₁=47

X₂₁+X₂₂+X₂₃+X₂₄=99 X₁₂+X₂₂+X₃₂=59

X₃₁+X₃₂+X₃₃+X₃₄=80 X₁₃+X₂₃+X₃₃=49

Xij=>0 X₁₄+X₂₄+X₃₄=43

Xij=>0

Математическая модель двойственной задачи:

Z’=70U₁+99U₂+80U₃+47V₁+59V₂+49V₃+43V₄ - MIN

Система ограничений:

Ui+Vj=>cij

Ui,Vj –произвольное значение

Первый начальный план по методу наибольшего элемента

ai bj	47		59		49		43		51		Ui
70		3	59	7		2	1 1 -w	5	+ w0		U1= -1
99	18 -w	2		3	49	4	32	+w6			U2=0
										0
80	29 +w	6		4		3			51	-w	U3=4
								5		0
Vj	V1= 2		V2=8		V3=4		V4=6		V5= -4		W=11

r=7 – число базисных клеток

m=3 – число строк

n=5 – число столбцов

[r=7] =[m+n-1=7] – план невырожден и задача имеет оптимальное решение. Это позволит найти потенциалы всех базисных клеток.

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

Ui+Vj=>cij – критерий оптимальности плана

Для всех базисных клеток составим и решим систему уравнений: Ui+Vj=cij

U1+V2=7 U1= -1 V1=2

U1+V4=5 U2=0 V2=8

U2+V1=2 U3=4 V3=4

U2+V3=4 V4=6

U2+V4=6 V5= -4

U3+V1=6

U3+V5=0

Для всех свободных клеток проверим выполнение неравенства: Ui+Vj=>cij

U1+V1=1<3 не выполняется на 2

U1+V4=-5<0 не выполняется на 5

В клетку с₁₄ ставим +w

ai bj	47		59		49		43		51		Ui
70		3	59	7		2		5	11 0		U1=4
99	7 -W	2		3	49	4	43	6		+W	U2=0
										0
80	40 +W	6		4		3			40 -W		U3=4
								5		0
Vj	V1= 2		V2=3		V3=4		V4=6		V5= -4		W=7

Для всех базисных клеток составим и решим систему уравнений: Ui+Vj=cij

U1+V2=7 U1=4 V1=2

U1+V5=0 U2=0 V2=3

U2+V1=2 U3=4 V3=4

U2+V3=4 V4=6

U2+V4=6 V5= -4

U3+V1=6

U3+V5=0

Для всех свободных клеток проверим выполнение неравенства: Ui+Vj=>cij

U2+V5=-4<0 не выполняется на 4

В клетку с₂₅ ставим +w

ai bj	47		59		49		43		51		Ui
70		3	59	7		2		5	11 0		U1=0
99		2		3	49	4	43	6	7		U2=0
										0
80	47	6		4		3			33		U3=0
								5		0
Vj	V1= 6		V2=7		V3=4		V4=6		V5=0

Для всех базисных клеток составим и решим систему уравнений: Ui+Vj=cij

U1+V2=7 U1=0 V1=6

U1+V5=0 U2=0 V2=7

U2+V3=4 U3=0 V3=4

U2+V4=6 V4=6

U2+V5=0 V5= 0

U3+V1=6

U3+V5=0

Для всех свободных клеток проверим выполнение неравенства: Ui+Vj=>cij –для всех клеток выполняется. Третий план содержит оптимальное решение.

Zmax=59*7+49*4+43*6+47*6=1149

Zmin=47*6+59*7+49*4+43*6=1149

Максимальное суммарное количество убранного картофеля со всех полей за рабочий день составит 1149 центнер при условии что:

C первого отряда направляем 59 чел. на второе поле;

Со второго отряда направляем 49 чел. на третье и 43 чел. на четвертое поле;

С третьего отряда направляем 47 чел. на первое поле.

Нераспределенными по полям окажутся студенты первого отряда в количестве 11 чел., студенты второго отряда в количестве 7 чел. и студенты третьего отряда в количестве 33 чел.