Матан_ЛинПрог

1 1 1			2 2 3	4 2 5	5 3 0
	1	2	3 2 1	4 3 4
2

Эта система имеет 7 уравнений и восемь неизвестных. Поэтому, положим

1 0. Тогда, 1 1, 2 2, 2 1, 3 0, 4 4, 3 0, 5 0. К

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

			ПУНКТЫ							ПУНКТЫ НАЗНАЧЕНИЯ																ЗАПАС			i
		ОТПРАВЛ.								В1		В2	В3			В4					Ф.П.					ГРУЗА
										1	-	2	4		+				1				0						0
				A1						30		20							3								50
										2	+	3	1		-				5				0						-1
				A2								0	10		20								1				30
										3		2	4						4				0						0
				A3											0							10					10
		ПОТРЕБН.
			В ГРУЗЕ							30		20	10		20							10					90
				j						1		2	0		4							0
	Вычислим теперь ij для свободных клеток по формуле (8.6).
13 3 1 с13 0 0 4 4															25 5 2 с25 0 ( 1) 0 1
							с			4 0 1 3																с		1 0 3 2
		14		4		1	14			0 0 0 0								31				1			3	с	31	2 0 2 0
		15		5		1	с										32					2			3		32
							15
							с			1 ( 1) 2 0																с		0 0 4 4
		21		1		2			21									33				3			3		33
																														X0
Так как, среди ij										есть положительные числа -														3 и 1, то план								не
является оптимальным. Запишем эти														положительные												оценки			14	3		в
клетку A1B4					и 25 1					в клетку			A2 . .. Среди них выберем наибольшую

оценку и округлим её.

С этой клетки начинаем строить цикл пересчета так, чтобы вершины цикла находились в заполненных клетках. Клетке A1B4 придаем знак "+", а остальным клеткам, в которых находятся вершины цикла, - поочередно знаки "-" и "+". Наименьшее из чисел в минусовых клетках равно 20. Это число добавим в клетки, где стоят знаки "+" и вычтем из клеток, где стоят знаки "-".

Пусть клетка A2B4		станет свободной, а										A1B2		останется заполненной, но с
нулевой поставкой.
Получим новую таблицу и новый опорный план X1.
	ПУНКТЫ		ПУНКТЫ НАЗНАЧЕНИЯ												ЗАПАС	i
	ОТПРАВЛ.		В1		В2				В3				В4	Ф.П.	ГРУЗА
			1	-	2				4		+ 1			0		0
	A1		30		0								20		50
			2					3	1				5	0		-1

A2		20		10						30
	3	+ 2			4	-	4		0		-3
A3	1	3					0	10		10
ПОТРЕБН.
В ГРУЗЕ	30	20		10			20	10		90
j	1	2		0			1	-3
		30			0		0	20
					20		10	0
		X1 0							,
				0	0		0	0

при	котором		F1 1 30 2 0 1 20 3 20 1 10 4 0 120 (ден.ед.).
Значение функции уменьшилось.				1 0 . Найденные
	Проверяем	этот	план на оптимальность. Пусть
значения i и		j	по формуле (8.5) запишем в	таблицу, а также

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

положительных ij

два: 31

1

и 32

3 . Выберем наибольшее из них,

т.е. число 3 и строим цикл пересчета. В минусовых клетках стоят нули. Поэтому в следующей таблице при добавлении и вычитании числа 0 план X1 не изменится. Клетка A3B2 заполнится нулевой поставкой, а из минусовых клеток, одна клетка должна стать свободной, другая - заполненной, но нулевой поставкой. Пусть A1B2 будет свободной, а A3B4 - нулевой. Получим новую таблицу

	ПУНКТЫ				ПУНКТЫ НАЗНАЧЕНИЯ												ЗАПАС	i
	ОТПРАВЛ.		В1			В2				В3		В4		Ф.П.		ГРУЗА
		-	1				2			4		+	1		0			0
	A1				30							20					50
		+			2	-		3		1			5		0			-4
	A2		3			20				10					1		30
			3			+			2	4		-	4		0			-3
	A3		1				0						0	10			10
	ПОТРЕБН. В
	ГРУЗЕ		30			20				10		20		10			90
	j		1				-1			-3			1	-3
и
	план									30		0	0	20
					X2 X1 0							20 10 0 ,
												0	0	0
										0

при котором F2 1 30 1 20 3 20 1 10 2 0 4 0 120 (ден.ед.).

Проверим на оптимальность.

Пусть 1 0 . Находим	i и	j ,	а также ij для свободных клеток.
Таких положительных ij	три:	21	3 ,	25 1 и 31 1 . Выберем

наибольшее из них, т.е. число 3 и строим цикл пересчета. Из минусовых клеток наименьшая поставка снова число 0. Поэтому в следующей таблице при добавлении и вычитании числа 0 план X2 не изменится.

ПУНКТЫ	ПУНКТЫ НАЗНАЧЕНИЯ											ЗАПАС	i
ОТПРАВЛ.	В1	В2			В3	В4				Ф.П.		ГРУЗА
	1	2			4	1					0		0
A1	30					20						50
	2	- 3			1	5			+		0		-1
A2	0	20			10						1	30
	3	+ 2			4	4			-		0		0
A3		0								10		10
ПОТРЕБН.
В ГРУЗЕ	30	20			10	20	10					90
j	1	2			0	1	0

План X3 X2, при котором

	F3	1 30 1 20 2 0 3 20 1 10 2 0 120 (ден.ед.).
Проверим на оптимальность.			j	, а также ij для свободных клеток.
Пусть 1	0 .	Находим i и

Положительное число среди ij одно: 25 1 . Строим цикл. Наименьшее

число из минусовых клеток 10. Это число добавим в плюсовые клетки и вычтем из минусовых клеток. Получим новую таблицу:

	ПУНКТЫ	ПУНКТЫ НАЗНАЧЕНИЯ								ЗАПАС	i
	ОТПРАВЛ.	В1	В2		В3			В4	Ф.П.	ГРУЗА
		1	2			4		1	0		0
	A1	30						20		50
		2	3			1		5	0		-1
	A2	0	10		10				10	30
		3	2			4		4	0		0
	A3		10							10
	ПОТРЕБН.
	В ГРУЗЕ	30	20		10			20	10	90
	j	1	2		0			1	-1
новый план:				30		0		0	20
						10		10
			Х4 0						0
					0	10		0
									0

и значение

F4		1 30 1 20 2 0 3 10 1 10 2 10 110 (ден.ед.).
Проверим на оптимальность.							j	, а также ij для свободных клеток.
Пусть 1	0	. Находим i				и
Все ij 0. Полученный план X4 является оптимальным, т.е.
		30	0	0	20
			10	10	0		при котором Fmin			110(ден.ед.).
X* 0						,
			10	0	0
Задача	2.	0
		Составить			опорный			план	данной	задачи	1 методом
"минимального элемента".											тарифом cij .
Заполнение		клеток		начнем		с	клетки		с минимальным

Наименьший тариф равен 1 и клеток с таким тарифом три. Поэтому начнем заполнение с любой такой клетки. Например, с клетки A1 B1, затем A2 B3 и A1 B4 , учитывая потребности в грузах и имеющиеся запасы груза.

	ПУНКТЫ	ПУНКТЫ НАЗНАЧЕНИЯ									ЗАПАС
	ОТПРАВЛ.	В1		В2	В3		В4		Ф.П.		ГРУЗА
		1		2		4		1		0
	A1	30					20				50
		2		3		1		5		0
	A2			10	10				10		30
		3		2		4		4		0
	A3			10							10
	ПОТРЕБН.
	В ГРУЗЕ	30		20	10		20		10		90
Потребности пунктов B1,				B3 и	B4	удовлетворены, а запасы пункта A1

исчерпаны, поэтому оставшиеся незаполненные клетки в столбцах B1, B3 и B4 , а также в строке A1 исключаются из последующего распределения груза.

Затем заполняем клетки с тарифом, равным 2, затем клетки с тарифом, равным 3, и т.д., пока все запасы не будут исчерпаны, а потребности не удовлетворены.

30		0	0	20
		10	10	0
Получим опорный план X0 0					,
	0	10	0	0

при котором значение функции

F0 1 30 1 20 3 10 1 10 2 10 110 (ден.ед.).

Полученный план совпадает с оптимальным планом, т.е. X0 X и

F0 Fmin .

Упражнения

Найти оптимальное распределение поставок и минимальные затраты на перевозки:

8.1. 8.2.

	П.	ПУНКТ НАЗНАЧ.				ЗАП.
	О.	В1	В2	В3	В4	ГРУЗ.
	A1	2	3	2	A1	50
	A2	2	4	5	A2	70
	A3	6	5	7	A3	60
	П.	60	60	50	30
	8.3.
	П.	ПУНКТ НАЗНАЧ.				ЗАП.
	О.	В1	В2	В3	В4	ГРУЗ.
	A1	2	3	2	1	80
	A2	2	4	5	3	30
	A3	6	5	7	4	50
	П.	100	20	40	30
	8.5.
	П.	ПУНКТ НАЗНАЧ.				ЗАП.
	О.	В1	В2	В3	В4	ГРУЗ.
	A1	5	4	6	3	30
	A2	4	5	5	8	70
	A3	7	3	4	7	70
	П.	50	50	40	60
	8.7.
	П.	ПУНКТ НАЗНАЧ.				ЗАП.
	О.	В1	В2	В3	В4	ГРУЗ.
	A1	6	3	5	6	150
	A2	1	2	3	5	120
	A3	7	3	2	2	150
	П.	100	100	100	100
	8.9.
	П.	ПУНКТ НАЗНАЧ.				ЗАП.
	О	В1	В2	В3	В4	ГРУЗ.
	A1	6	9	5	9	220
	A2	8	5	4	7	190
	A3	7	1	7	5	250
	П.	180	90	110	190
	8.11.
	П.	ПУНКТ НАЗНАЧ.				ЗАП.
	О.	В1	В2	В3	В4	ГРУЗ.
	A1	5	4	5	4	150
	A2	4	2	4	2	200
	A3	5	3	2	1	300
	A4	3	5	6	2	50
	П.	200	150	240	100

	П.	ПУНКТ НАЗНАЧ.					ЗАП.
	О.	В1		В2	В3	В4	ГРУЗ.
	A1	6	4		4	8	200
	A2	6	2		5	5	300
	A3	8	2		10	6	100
	П.	450	250		100	100
		8.4.
	П.	ПУНКТ НАЗНАЧ.					ЗАП.
	О.	В1		В2	В3	В4	ГРУЗ.
	A1	2		4	7	6	25
	A2	3		5	4	5	18
	A3	1		8	2	5	12
	П.	15		25	8	12
		8.6.
	П.	ПУНКТ НАЗНАЧ.					ЗАП.
	О.	В1		В2	В3	В4	ГРУЗ.
	A1	7		8	4	3	110
	A2	2		4	5	9	110
	A3	3		5	5	4	80
	П.	50		90	90	70
		8.8.
	П.	ПУНКТ НАЗНАЧ.					ЗАП.
	О.	В1		В2	В3	В4	ГРУЗ.
	A1	2	2		5	6	200
	A2	5	3		4	5	100
	A3	6	5		5	3	100
	П.	100	50		150	150
		8.10.
	П.	ПУНКТ НАЗНАЧ.					ЗАП.
	О.	В1		В2	В3	В4	ГРУЗ.
	A1	3	5		6	2	95
	A2	6	4		7	5	35
	A3	5	4		6	5	55
	П.	150	230		160	160
		8.12.
	П.	ПУНКТ НАЗНАЧ.					ЗАП.
	О.	В1		В2	В3	В4	ГРУЗ.
	A1	2		3	8	7	200
	A2	3		4	7	3	160
	A3	5		3	6	5	140
	A4	5		3	2	1	60
	П.	160		180	120	150

8.13.

П.	ПУНКТ НАЗНАЧ.				ЗАП.
О.	В1	В2	В3	В4	ГРУЗ.
A1	5	5	3	6	200
A2	2	2	4	5	150
A3	4	5	3	5	120
A4	3	5	6	2	50
П.	100	100	150	160
8.15.
П.	ПУНКТ НАЗНАЧ.				ЗАП.
О.	В1	В2	В3	В4	ГРУЗ.
A1	5	4	15	7	150
A2	21	14	13	11	650
A3	16	19	12	12	600
A4	15	14	17	12	200
П.	200	300	400	250
8.17.
П.	ПУНКТ НАЗНАЧ.				ЗАП.
О.	В1	В2	В3	В4	ГРУЗ.
A1	5	4	15	7	150
A2	5	1	7	9	95
A3	2	4	6	11	35
A4	9	7	13	1	55
П.	75	85	45	75
8.19.
П.	ПУНКТ НАЗНАЧ.				ЗАП.
О.	В1	В2	В3	В4	ГРУЗ.
A1	5	5	3	6	150
A2	2	2	4	5	150
A3	4	5	3	5	200
A4	9	7	3	1	300
П.	200	150	160	160

8.14.

П.	ПУНКТ НАЗНАЧ.				ЗАП.
О.	В1	В2	В3	В4	ГРУЗ.
A1	19	28	15	27	200
A2	31	24	25	17	450
A3	25	29	26	21	450
A4	5	13	20	11	300
П.	100	350	50	150
	8.16.
П.	ПУНКТ НАЗНАЧ.				ЗАП.
О.	В1	В2	В3	В4	ГРУЗ.
A1	5	6	4	5	30
A2	3	6	5	2	50
A3	8	1	1	2	55
A4	5	3	2	1	60
П.	75	40	10	20
	8.18.
П.	ПУНКТ НАЗНАЧ.				ЗАП.
О.	В1	В2	В3	В4	ГРУЗ.
A1	5	5	4	3	100
A2	6	5	3	5	100
A3	2	4	4	5	200
A4	5	3	2	1	60
П.	100	100	150	100
	8.20.
П.	ПУНКТ НАЗНАЧ.				ЗАП.
О.	В1	В2	В3	В4	ГРУЗ.
A1	6	9	5	9	100
A2	8	5	4	7	450
A3	7	1	7	5	450
A4	5	3	2	1	300
П.	200	300	400	250

Использованная литература:

1.И.Л Акулич. Математическое программирование в примерах и задачах. Москва, 1986.

2.А.И. Карасев, Н.Ш. Кремер, Т.И. Савельева. Математические методы и модели в планировании. Москва, 1987.

3.Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко. Математическое программирование. Москва, 1976.

4.А.И. Карасев, З.М. Аксютина, Т.И. Савельева. Курс высшей математики для экономических вузов. Москва, 1982.

5.Сборник задач по математике для ВТУЗОВ. Методы оптимизации уравнения в частных производных. Интегральные уравнения. /Под редакцией А.В.Ефимова. Москва, 1990.

6.Ю.Л. Заславский. Сборник задач по линейному программированию. Москва, 1969.

7.Исследование операций в экономике. /Под редакцией профессора Н.И.Кремера. Москва, 1997.

СОДЕРЖАНИЕ

1.Постановка задач линейного программирования. Построение математических моделей экономических задач………………………………….3

2.Решение системы линейных уравнений методом Жордана-Гаусса…...11

3.Графический метод решения задач линейного программирования…...15

4.Симплексный метод решения задач линейного программирования….20

5.Метод искусственного базиса……………………………………………28

6.Двойственные задачи линейного программирования………………….32

7.Двойственный симплексный метод……………………………………..40

8.Транспортная задача……………………………………………………...44

9.Использованная литература……………………………………………...55