ftd

Добавил:

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

Вуз:

Южно-Уральский Государственный Университет

Предмет:

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

Файл:

Потребности bj

.pdf

Скачиваний:

Добавлен:

09.05.2015

Размер:

1.72 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 67 / 87 8 > Следующая >>>

Пример 3.3

Решить задачу линейного программирования графическим методом

F x1 x2				x3 3x4			7x5 min,
x x x 2x 3x 4,
	1		2	3	4		5
x1	x2 4x3 x4 8x5 3,
x	x		4x		4,
2	3			5
		xj		0,	j			.
						1;5

Решение

Методом Жордана–Гаусса приведем систему уравнений-ограничений задачи к равносильной

	1	1 1	2		3		4	1	1 1		2	3		4

A	B 1	1 4	1		8		3 ~ 0 2			5	3	11		7 ~

		1 1	0						1	1	0

	0				4	4		0				4		4

	1 0	0	2		1		8	1 0 0			2	1	8
	~ 0 0	3	3	3			15 ~ 0 0 1			1		1	5 .
											1
	0 1	1	0	4			4	0 1 0				3	9

Поскольку система совместна (r=rang A rang A B 3) и выполняется ус-

ловие n r 2, где n – число неизвестных системы ограничений, то данная задача линейного программирования может быть решена графическим методом.

На основе последней матрицы запишем систему в следующем виде

x			2x	x	8,
	1		4	5	5,
			x3 x4	x5	5,	(*)
		x2	x4 3x5 9.
		x2	x4 3x5 9.
Выразим в системе (*) базисные неизвестные x1, x2,						x3 через свободные
x4, x5
	x 8 2x x ,
		1	4	5
	x3 5 x4 x5,					(**)
	x 9 x 3x .
		2	4	5

Исключим базисные переменные из целевой функции

F 8 2x4 x5 9 x4 3x5 5 x4 x5 3x4 7x5 22 x4 4x5.

По условию xj 0, j 1;5, поэтому в преобразованных уравнениях-

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

F 22 x4 4x5 min,

2x4 x5 8,x4 x5 5,

x4 3x5 9, x4 0, x5 0.

Решим задачу графическим методом. Свободный член в целевой функции 22 на отыскание оптимального решения не влияет и учитывается только при вычислении значения целевой функции.

Определим многоугольник решений


l : 2x x 8,					x4			x5	1;

1		4	5	4		8
l	2	: x x 5;		x4			x5		1;

		4	5	5			5
l : x 3x 9;					x4			x5	1;

3		4	5	9		3

l4 : x4 0; l5 : x5 0.

Найдем полуплоскость, определяемую каждым неравенством. Возьмем точку с

координатами 5;3 для всех неравенств
2 5 3 8 – верно;	5 0 – верно;
5 3 5 – верно;	5 0 – верно;
5 3 3 9 – верно;

Значит, относительно каждой прямой искомыми являются полуплоскости, в

которых лежит точка 5;3 . Пересечение этих полуплоскостей является много-

угольником решений задачи (рис. 11).
Построим	вектор цели	c 1;4	и	прямую	нулевого уровня
l0 : x4 4x5	0. Переместим	прямую l0	в	направлении	противоположном

вектору c до последней общей точки ее с многоугольником решений – точки A. Координаты этой точки определяют оптимальное решение вспомогательной задачи.

A l2 l3:


x	x 5,		x x 5,		x* 6,
4 5			4	5	4
x	3x 9;		4x 4;		x* 1.
4		5		5	5

Вычислим минимальное значение целевой функции

Fmin 22 6 4 1 20.

х5 l1 l4

c
l3 3				l0
l5			A	x4
l5	4	5		x4
0	4	5		9

l2 -5

Рис. 11

Подставим найденные значения x* и x*		в систему (**) и вычислим значения
4	5
остальных переменных
x 8 2 6 1,		x 5,
1		1
x3 5 6 1,		x3 0,
x 9 6 3 1;		x 0.
2		2

Таким образом, оптимальное решение исходной задачи:

X* 5;0;0;6;1 . Ответ: Fmin 20 при X* 5;0;0;6;1 .

Задача 3.4. На три базы A1, A2, A3 поступил однородный товар соответст-

венно в количестве: a1, a2, a3. Товар требуется перевезти в количестве b1

единиц в магазин B1, в количестве b2 единиц в магазин B2, b3 ед. в магазин

B3, b4 ед. в магазин B4, b5 ед. в магазин B5. Матрица тарифов перевозок

cij между базами и магазинами, запасы товаров на базах и потребности в
товарах для магазинов заданы таблицей:
Базы	Магазины	B	B	B	B	B	Запасы a
		1	2	3	4	5	i
	A1	c11	c12	c13	c14	c15	a1
	A2	c21	c22	c23	c24	c25	a2
	A3	c31	c32	c33	c34	c35	a3
Потребности bj		b1	b2	b3	b4	b5
Спланировать план перевозок таким образом, чтобы общая их стои-
мость была минимальной.
Данные к условию задачи, соответствующие вариантам:

1)	Магазины	B	B	B	B	B	Запасы a
Базы	Магазины	B	B	B	B	B	Запасы a
	A1	1	2	3	4	5	i
	A1	14	8	17	5	3	120
	A2	21	10	7	11	6	180
	A3	3	5	8	4	9	200
Потребности bj		70	120	105	125	110
2)	Магазины	B	B	B	B	B	Запасы a
Базы	Магазины	B	B	B	B	B	Запасы a
	A1	1	2	3	4	5	i
	A1	21	18	14	3	6	400

	A2	7	11	10	5	12	370
	A3	4	8	16	9	13	380
Потребности bj		250	200	290	260	100
3)	Магазины	B	B	B	B	B	Запасы a
Базы	Магазины	B	B	B	B	B	Запасы a
	A1	1	2	3	4	5	i
	A1	14	8	17	5	3	530
	A2	21	10	7	11	6	570
	A3	3	5	8	4	9	600
Потребности bj		300	380	450	370	250
4)	Магазины	B	B	B	B	B	Запасы a
Базы	Магазины	B	B	B	B	B	Запасы a
		1	2	3	4	5	i

A1	2	10	15	14	4	350
A2	3	7	12	5	8	350
A3	21	18	6	13	16	300
Потребности bj	180	220	230	270	100

5)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	12	9	7	11	6	350
	A2	4	3	12	2	8	300
	A3	5	17	9	4	11	300
Потребности bj		180	220	230	270	100
6)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	2	4	11	5	3	400
	A2	8	17	13	7	6	370
	A3	14	10	5	8	9	380
Потребности bj		250	200	290	210	150
7)	Магазины	B	B	B	B	B	Запасы a
Базы	Магазины	B	B	B	B	B	Запасы a
Базы	A1	1	2	3	4	5	i
	A1	2	4	5	11	3	120
	A2	12	8	6	14	11	150
	A3	10	15	7	9	18	100
Потребности bj		85	65	90	60	70
8)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	3	8	7	11	15	120
	A2	14	3	1	8	6	180
	A3	9	5	16	7	12	200
Потребности bj		70	120	105	125	110
9)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai

A1	11	4	15	7	2	260
A2	20	9	7	14	5	400
A3	18	10	3	8	6	240
Потребности bj	180	200	190	230	100

10)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	12	9	7	11	6	150
	A2	4	3	12	2	8	170
	A3	5	17	9	4	11	260
Потребности bj		100	70	150	150	80
11)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	7	4	15	9	14	170
	A2	11	2	7	3	10	150
	A3	4	5	12	8	17	180
Потребности bj		90	120	110	130	70
12)	Магазины	B	B	B	B	B	Запасы a
Базы	Магазины	B	B	B	B	B	Запасы a
Базы	A1	1	2	3	4	5	i
	A1	2	4	11	5	3	350
	A2	8	17	13	7	6	200
	A3	14	10	5	8	9	270
Потребности bj		190	280	110	100	120
13)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	3	10	14	15	6	370
	A2	2	22	4	12	9	450
	A3	8	5	11	15	7	480
Потребности bj		300	280	330	290	100
14)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai

15)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	14	8	17	5	3	370
	A2	21	10	7	11	6	450
	A3	3	5	8	4	9	480
Потребности bj		300	280	320	200	100
16)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	11	4	15	7	2	200
	A2	20	9	7	14	5	300
	A3	18	10	3	8	6	200
Потребности bj		120	230	190	160	120
17)	Магазины	B	B	B	B	B	Запасы a
Базы	Магазины	B	B	B	B	B	Запасы a
Базы	A1	1	2	3	4	5	i
	A1	3	8	7	11	15	560
	A2	14	3	1	8	6	570
	A3	9	5	16	7	12	620
Потребности bj		300	330	350	370	250
18)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	2	10	15	14	4	150
	A2	3	7	12	5	8	170
	A3	21	18	6	13	16	260
Потребности bj		100	90	160	150	80
19)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai

A1	14	8	17	5	3	120
A2	21	10	7	11	6	100
A3	3	5	8	4	9	230
Потребности bj	70	120	105	125	110

20)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	12	9	7	11	6	175
	A2	24	3	12	2	8	165
	A3	5	17	9	4	11	180
Потребности bj		50	110	110	100	70
21)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	3	8	7	11	15	200
	A2	14	3	1	8	6	400
	A3	9	5	16	7	12	200
Потребности bj		180	200	190	230	100
22)	Магазины	B	B	B	B	B	Запасы a
Базы	Магазины	B	B	B	B	B	Запасы a
Базы	A1	1	2	3	4	5	i
	A1	2	4	11	5	3	250
	A2	8	17	13	7	6	300
	A3	14	10	5	8	9	270
Потребности bj		120	230	190	160	120
23)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	3	10	14	15	6	100
	A2	2	22	4	12	9	150
	A3	8	5	11	15	7	180
Потребности bj		90	120	110	130	70
24)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai

A1	21	18	14	3	6	370
A2	7	11	10	5	12	450
A3	4	8	16	9	13	480
Потребности bj	300	280	330	290	100

25)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	2	4	5	11	3	260
	A2	12	8	6	14	11	400
	A3	10	15	7	9	18	240
Потребности bj		180	200	100	200	100
26)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	7	4	15	9	14	150
	A2	11	2	7	3	10	170
	A3	4	5	12	8	17	260
Потребности bj		100	90	160	150	80
27)	Магазины	B	B	B	B	B	Запасы a
Базы	Магазины	B	B	B	B	B	Запасы a
Базы	A1	1	2	3	4	5	i
	A1	3	10	14	15	6	560
	A2	2	22	4	12	9	570
	A3	8	5	11	15	7	620
Потребности bj		300	380	450	220	250
28)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai
	A1	2	4	5	11	3	400
	A2	12	8	6	14	11	370
	A3	10	15	7	9	18	380
Потребности bj		250	200	290	260	150
29)	Магазины	B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины	B1	B2	B3	B4	B5	Запасы ai

A1	11	4	15	7	2	350
A2	20	9	7	14	5	350
A3	18	10	3	8	6	300
Потребности bj	180	220	230	270	100

30)	Магазины		B1	B2	B3	B4	B5	Запасы ai
Базы	Магазины		B1	B2	B3	B4	B5	Запасы ai
A1			21	18	14	3	6	120
A2			7	11	10	5	12	150
A3			4	8	16	9	13	100
Потребности bj			80	60	80	60	50
Пример 3.4
На три базы	Ai,	i 1;3	поступил однородный товар, который требуется
перевезти в магазины Bj ,			j 1;5. Матрица тарифов перевозок (cij ) между
базами и магазинами, запасы товаров (ai ) на базах и потребности в товарах
(bj ) для магазинов заданы таблицей:
Базы	Магазины		B1	B2	B3	B4	B5	Запасы ai
A1			2	3	4	5	1	430
A2			2	4	3	6	7	320
A3			6	5	8	5	4	380
Потребности bj			190	200	220	210	150
Спланировать план перевозок таким образом, чтобы общая их стои-
мость была минимальной.
Решение
Найдем суммарные запасы поставщиков (баз) и суммарные запросы потреби-
телей (магазинов)		3
		3
		ai 430 320 380 1130,
	5	i 1
	5
	bj 190 200 220 210 150 970.
	j 1
3		5
Поскольку ai bj			, то данная задача с неправильным балансом. Необ-
i 1		j 1

ходимо ввести шестого, фиктивного потребителя с потребностями

b6 1130 970 160

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

<<< < Предыдущая 1 2 3 4 5 67 / 87 8 > Следующая >>>

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

#
09.09.2019580.76 Кб2FM.docx
#
14.07.201993.16 Кб0frantsia_FR10.docx
#
08.05.201510.52 Mб22frontpage2002.doc
#
08.05.20158.82 Mб17frontpage2002.pdf
#
08.05.20151.19 Mб78ftd-1.pdf
#
09.05.20151.72 Mб39ftd.pdf
#
09.05.2015353.98 Кб9ftd.pdf
#
16.03.201613.91 Mб21ftd.pdf
#
09.05.20151.32 Mб10ftd.pdf
#
08.05.20151.87 Mб88ftd.pdf
#
14.07.201962.41 Кб5FYeDYeRAL_NOYe_AGYeNSTVO_PO_OBRAZOVANIYu (1).docx