Методы оптимальных решений. Часть 1. Линейное программирование

31

D

L(X)=7

L(X)=5

									Рис. 2
3. Даны следующие ЗЛП:
L X 2x1				x2	max	L x1 , x2			x1 x2	max
2x1		3x2		5		2x1		x2 2
а) 5x1		2x2		7		б) x1	2x2 8
x		2x		3		x	x		5
	1		2			1		2
x1	0, x2			0		x1	0, x2 0

Поставить им в соответствие симметричные двойственные:

L Y 5y1

7 y2

3y3

min

L Y 2 y1 8y2 5y3

min

2 y1 y2

y3 1

а) 2 y1 5y2

y3 2

б)

2 y2 y3 1

y1

3y1 2 y2

2 y3 1

y

0, y

2

0

1

L Y 5y1

7 y2

3y3

min

L Y 5y1

7 y2 3y3

min

в)

2 y1 5y2

y3 2

2 y1 5y2

y3 2

2 y3 1

г)

2 y3 1

3y1 2 y2

3y1 2 y2

y

0, y

2

0

y

0, y

2

0

1

1

L Y 2 y1

8y2

5y3

min

L Y 2 y1

8y2 5y3 min

д)

2 y1 y2 y3

1

2 y1 y

2

y3 1

2 y2 y3 1

е)

2 y2 y3 1

y1

y1

y

0, y

2

0

y

0, y

2

0

1

1

32

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

Ответы. 1) в.

2) Рис. 1 Линейная форма неограничена сверху ( ( ) = +∞). Минимум – на рисунке:

Рис. 2 Максимум линейной формы ; минимум линейной формы

33

3) а↔в; б↔д.

1

1

11

1

4

4) = 0

,

= 11 ,

( ) = ( ) = 3.

0

0

0

(2)

(0 )

4.2 Транспортная задача

1. Укажите правильные записи транспортной задачи:

m

m

n

m n

L X cij xij min

L X

cij xij min

L X cij xij

min

i 1

i 1

j 1

i 1 j 1

m

m

m

xij

b j , j 1, n

xij b j , j 1, n

xij

b j , j 1, n

а)

i 1

б) i 1

в) i 1

n

xij

ai

n

n

,i 1, m

x

ij

a

, i 1, m

x

ij

a

, i 1, m

i

i

j 1

j 1

j 1

x

ij

0,i 1, m, j 1, n

x

ij

0, i 1, m, j 1, n

x

ij

0, i 1, m, j 1, n

m

n

m

n

L X cij xij min

L X xij min

i 1

j 1

i 1

j 1

m

m

xij

b j , j 1, n

cij xij

b j , j 1, n

г) i 1

д)

i 1

.

n

n

x

a

, i 1, m

c

x

a

, i 1, m

ij

ij

ij

i

i

j 1

j 1

x

ij

0, i 1, m, j 1, n

x

ij

0, i 1, m, j 1, n

2. Составить первый план тремя способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Определить значение линейной формы.

	B1	B2	B3	B4	З
A1	47	8	20	65	11
A2	33	0	7	28	22
A3	24	70	3	46	8
П	5	54	65	3	127

34

3. Для следующей ТЗ составить первый план методом минимальной стоимости и найти

оптимальный план методом потенциалов.

	B1	B2	B3	B4	З
A1	47	5	41	38	59
A2	34	41	70	17	73
A3	21	41	38	50	53
П	5	70	38	8

Ответы. 1) б, в, г.

2) задача на недостаток, вводим фиктивного поставщика А4 с запасами 4 = 86.

Метод северо-западного угла ( 1) =843;

	В1		В2		В3		В4		З
А1		47		8		20		65	11	6	0
		5		6
А2		33		0		7		28	22	0
				22
А3		24		70		3		46	8	0
				8
А4		0		0		0		0	86	68	3	0
				18		65		3
П		5		54		65		3	127
		0		48		0		0
				26
				18
				0

35

Метод минимальной стоимости ( 1) =379
		В1		В2		В3		В4		З
	А1		47		8		20		65	11	3	0
							8		3
	А2		33		0		7		28	22	0
					22
	А3		24		70		3		46	8	0
							8
	А4		0		0		0		0	86	81	49	0
			5		32		49
	П		5		54		65		3	127
			0		32		16		0
					0		8
							0

Метод Фогеля ( 1) = 112

				В1			В2			В3			В4			З		Разн	Разн	Разн	Разн	Разн	Разн
																		ость	ость	ость	ость	ость	ость
А1				47			8			20			65			11		12	12	12	12
							11									0
А2				33			0			7			28			22		7	7	7	7	7
							22									0
А3				24			70			3			46			8		21	21	67
										8					0
А4				0			0			0			0			86		0	0	0	0	0	0
				5			21			57			3		83 78 57
	П			5			54			65			3			127
			0			43 21 0			57 0			0
Разность			24			0			3				28
Разность				24		0			3
Разность						0			3
Разность						0			7
Разность						0			0

36

4. Задача на избыток.

Оптимальный план :

	В1		В2		В3		В4		Запасы
А1		47		5		41		38	59
				59
А2		34		41		70		17	73
				1				8
А3		21		41		38		50	53
		5		10		38
Потр		5		70		38		8	185

Оптимальные расходы: ( ) = 2431 у.е.

ЛИТЕРАТУРА

4.Математические методы и модели исследования операций: Учебник для ВУЗов / А.С. Шапкин, Н.П. Мазаева. – 4-е изд. – М.: Дашков и К0, 2007.- 395с.

5.Исследование операций в экономике: учеб. пособие / Н. Ш. Кремер, И.М. Тришин, Б.А. Путко, М.Н. Фридман; под. Ред. Н.Ш. Кремера. – 2-е изд. – М.: Юрайт, 2010. – 430с

6.Экономико-математические методы и модели: пособие к решению задач/ А.И. Стрикалов, И.А. Печенежская. – Ростов на Дону: Феникс, 2008. – 348с.

7.Математические методы и модели в экономике: учеб. пособие для вузов / под редакцией проф. Н.А. Орехова. – М.: Юнити-Дана, 2004. – 302с.