Кафедра прикладной математики

Кафедра прикладной математики

КУРСОВАЯ РАБОТА

по дисциплине «Прикладная математика»

Выполнил(а) ………………..

Институт

Отделение

Курс II

Группа ……………….

Руководитель ……………….

Дата сдачи на проверку..............................

Дата защиты..............................

Оценка..............................

Подпись руководителя..............................

Москва - 2002

 

 

Оглавление

 

Линейная производственная задача.............................................................................................. 3

Двойственная задача....................................................................................................................... 7

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

Метод динамического программирования................................................................................. 15

Динамическая задача управления производством и запасами............................................... 18

Матричная модель сотрудничества и конкуренции............................................................... 25

Задача о максимальном потоке в сети...................................................................................... 28

Список литературы....................................................................................................................... 32

 

Линейная производственная задача

Постановка задачи

Сформулировать линейную производственную задачу и составить ее математическую модель.

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

В последней симплексной таблице указать обращенный базис Q^-1, соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения

H = Q^-1 * B.

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

 

 

Исходные данные

 

Предприятие выпускает 4 вида продукции, используя для этого три вида ресурсов. Известна технологическая матрица A, в которой каждый элемент a_ij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:

А =

 

Известен вектор B объемов ресурсов, каждый элемент которого b_i означает предельное количество i-го ресурса для выпуска всего объема продукции:

 

В =

 

Также известен вектор удельной прибыли C, элементы которого c_j означают прибыль от производства единицы продукции j-го вида:

 

С =

 

Требуется составить производственную программу, обеспечивающую предприятию наибольшую прибыль при имеющихся ограниченных ресурсах.

 

 

Решение

Математическая модель задачи: найти производственную программу

(х₁, х₂, х₃, х₄),

 

максимизирующую прибыль

 

Z = 34 * х₁ + 20 * х₂ + 8 * х₃ + 23 * х₄

 

при ограничениях по ресурсам

 

2 * х1			+	2 * х3	+	3 * х4	<=
х1	+	5 * х2	+	4 * x3	+	2 * х4	<=		(1)
3 * х1	+	4 * х2			+	х4	<=

 

где по смыслу задачи

 

x₁ >= 0; x₂ >= 0; x₃ >= 0; x₄ >= 0

 

Введя дополнительные неотрицательные неизвестные х₅, х₆, х₇, заменяем неравенства (1) уравнениями вида:

 

2 * х1			+	2 * х3	+	3 * х4	+	х5	=
х1	+	5 * х2	+	4 * x3	+	2 * х4	+	х6	=
3 * х1	+	4 * х2			+	х4	+	х7	=

 

Решаем полученную задачу симплексным методом (методом направленного перебора базисных допустимых решений) (см. Таблицу 1).

Таблица 1

C	Базис	Hi	х1	х2	х3	х4	х5	х6	х7
	х5
	х6
	х7
	z – z0		-34	-20	-8	-23
	х5	182/3		-8/3		7/3			-2/3
	х6	178/3		11/3		5/3			-1/3
	х1	122/3		4/3		1/3			1/3
	z – z0	4148/3		76/3	-8	-35/3			34/3
	х4			-8/7	6/7		3/7		-2/7
	х6				18/7		-5/7		1/7
	х1				-2/7		-1/7		3/7
	z – z0

 

Как видно из последней симплексной таблицы, оптимальная производственная программа имеет вид

 

х₁ = 32, х₂ = 0, х₃ = 0, х₄ = 26,

 

а максимальная прибыль равна

 

Z_max = 1686

 

При этом 1-й и 3-й ресурсы будут исчерпаны полностью (х₅=0, х₇=0), а 2-й ресурс будет иметь остаток х₆ = 8 единиц.

 

Обращенный базис, отвечающий оптимальной производственной программе, содержится в последней симплексной таблице:

 

	3/7		-2/7
Q –1 =	-5/7		1/7
	-1/7		3/7

 

Для того, чтобы убедиться в правильности полученного решения, следует проверить отношение Н = Q^-1 * В:

 

	3/7		-2/7				426/7 – 244/7
Q-1 * В =	-5/7		1/7	*		=	-710/7 + 100 + 122/7	=
	-1/7		3/7				-142/7 + 366/7

 

Следовательно, полученное решение верно.

 

Так как х₂ = 0, х₃= 0, можно составить математическую модель задачи с двумя переменными (х₁ и х₄):

 

Z =	34 * х1	+	23 * х4	->	max
	2 * х1	+	3 * х4	<=
	х1		2 * x4	<=
	3 * х1	+	х4	<=

 

Графическое решение такой модели изображено на Рисунке 1.

 

Рисунок 1

 

 

Решая систему двух линейных уравнений, получаем оптимальный результат:

 

2 * х1	+	3 * х4	=
3 * х1	+	х4	=

 

 

х1	=
х3	=
Zmax	=

 

Полученный графическим методом результат совпадает с тем, который был получен ранее при использовании симплекс-метода.

Двойственная задача

 

 

Постановка задачи

Сформулировать задачу, двойственную линейной производственной задаче, как задачу определения расчетных оценок ресурсов, и найти ее решение, пользуясь второй основной теоремой двойственности (о дополняющей нежесткости). Указать оценку единицы каждого ресурса, минимальную суммарную оценку всех ресурсов, оценки технологий.

Применить найденные двойственные оценки ресурсов к решению следующей задачи.

Сформулировать задачу о расшивке “узких мест” производства и составить математическую модель. Определить область устойчивости двойственных оценок, где сохраняется структура программы производства. Решить задачу о “расшивке узких мест производства” при условии, что дополнительно можно получить от поставщиков не более 1/3 первоначального объема ресурса каждого вида (если задача окажется с двумя переменными, то только графически); найти план приобретения дополнительных объемов ресурсов, дополнительную возможную прибыль.

 

 

Исходные данные – см. Задачу 1.

 

 

Решение

 

При решении двойственной задачи требуется найти оценку единицы каждого вида ресурса. Это - задача линейного программирования, постановка которой формулируется следующим образом.

Найти вектор двойственных оценок

 

(у₁, у₂, у₃),

 

минимизирующий общую всех ресурсов

 

f = 142 * y₁ + 100 * y₂ + 122 * y₃

 

при условии, что по каждому виду продукции суммарная оценка ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции

 

2 * у1	+	у2	+	3 * y3	>=
		5 * у2	+	4 * у3	>=
2 * у1	+	4 * y2			>=
3 * у1	+	2 * y2	+	у3	>=

 

причем оценки ресурсов не могут быть отрицательными

 

у₁ >= 0, у₂ >= 0, у₃ >= 0.

 

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений х(х₁,х₂,х₃) и у(у₁,у₂,у₃) пары двойственных задач необходимо и достаточно выполнение условий

 

х1 * (	2 * у1	+	у2	+	3 * y3	-		) = 0
х2 * (			5 * у2	+	4 * у3	-		) = 0
х3 * (	2 * у1	+	4 * y2			-		) = 0
х4 * (	3 * у1	+	2 * y2	+	у3	-		) = 0

 

у1 * (	2 * х1			+	2 * х3	+	3 * х4	-		) = 0
у2 * (	х1	+	5 * х2	+	4 * x3	+	2 * х4	-		) = 0
у3 * (	3 * х1	+	4 * х2			+	х4	-		) = 0

 

 

Ранее (см. Задачу 1) было найдено, что в решении исходной задачи х₁>0 и х₄>0. Поэтому

 

2 * у1	+	у2	+	3 * y3	-		= 0
3 * у1	+	2 * y2	+	у3	-		= 0

 

Если же учесть, что 2-й ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю:

y₂ = 0

 

то приходим к системе уравнений

 

2 * у1	+	3 * y3	-		= 0
3 * у1	+	у3	-		= 0

 

откуда следует

 

у₁ = 5,

у₃ = 8.

 

Таким образом, получили двойственные оценки ресурсов

 

у₁ = 5, у₂ = 0, у₃ = 8,

 

причем общая оценка всех ресурсов равна

 

f_min = 1686

 

Заметим, что это решение содержалось в последней строке симплексной таблицы исходной задачи.

 

Экономический смысл

Двойственная оценка 1-го ресурса у₁ = 5 показывает, что добавление одной единицы этого ресурса обеспечит прирост прибыли в 5 единиц, двойственная оценка 3-го ресурса у₃ = 8 - что добавление одной единицы 3-го ресурса обеспечит прирост прибыли в 8 единиц. Двойственная оценка 2-й технологии D₂ = 12 показывает, что если произвести одну единицу продукции 2-го вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 12 единиц, оценка 3-й технологии D₃ = 18 - что производство одной единицы продукции 3-го вида снизит прибыль на 18 единиц.

 

При выполнении оптимальной производственной программы 1-й и 3-й ресурсы используются полностью, т.е. образуют “узкие места производства”. Будем их заказывать дополнительно. Пусть T(t₁, t₂, t₃) - вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие

 

H + Q^-1 * T >= 0

 

Задача состоит в том, чтобы найти вектор

 

T (t₁, t₂, t₃)

 

максимизирующий суммарный прирост прибыли

 

w = 5 * t₁ + 8 * t₃ (1)

 

при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)

 

		3/7		-2/7		t1
	+	-5/7		1/7	*		>=		(2)
		-1/7		3/7		t3

 

предполагая, что дополнительно можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида

 

t1
	=<	1/3	*		(3)
t3

 

 

причем по смыслу задачи

 

t₁ >= 0, t₃ >= 0 (4)

 

Переписав неравенства (2) и (3) в виде

 

-3 * t1	+	2 * t3	=<
5 * t1	-	t3	=<
t1	-	3 * t3	=<		(5)
t1			=<	47.33
		t3	=<	40.67

 

приходим к задаче линейного программирования: максимизировать (1) при условиях (4), (5).

Эту задачу решаем графическим методом (см. Рисунок 2).

 

Рисунок 2

 

Решаем систему уравнений:

 

5 * t1	-	t3	=
		t3	=	40.67

 

Программа “расшивки” имеет вид

 

t₁ = 30.53, t₂ = 0, t₃ = 40.67

 

и прирост прибыли составит

 

w = 478.01

 

 

Сводка результатов приведена в Таблице 2.

 

Таблица 2

cj					bi	x4+i	yi	ti
								30.53
aij
								40.67
xj								478.01
D j

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

 

 

Постановка задачи

Составить математическую модель транспортной задачи. Если полученная модель окажется открытой, то свести ее к замкнутой и найти оптимальное решение транспортной задачи методом потенциалов.

 

 

Исходные данные

 

Стоимости перевозок:

 

 

Вектор объемов производства:

 

А = (80, 60, 30).

 

Вектор объемов потребления:

 

В = (34, 40, 38, 53).

 

Решение

Так как размеры объемов производства превышают размеры объемов потребления на 5 единиц, вводим фиктивного b₅=5 потребителя и определяем первоначальный опорный план методом северо-западного угла:

 

	b1=34	b2=40	b3=38	b4=53	b5=5
a1=80
a2=60
a3=30

 

 

Находим оптимальное решение транспортной задачи методом потенциалов.

 

	b1=34	b2=40	b3=38	b4=53	b5=5
a1=80		- 7	+ 2			p1 = 0
a2=60		+ 5 *	- 4			p2 = 2
a3=30						p3 = 1
	q1 = 2	q2 = 7	q3 = 2	q4 = 0	q5 = -1
	D21 = 3	D22 = 4	D33 = -3	D14 = -3	D15 = -1
	D31 = 0	D32 = 4			D25 = 1
	Zmin =

 

 

	b1=34	b2=40	b3=38	b4=53	b5=5
a1=80		- 7			+ 0 *	p1 = 0
a2=60		+ 5		- 2		p2 = -2
a3=30				+ 1	- 0	p3 = -3
	q1 = 2	q2 = 7	q3 = 2	q4 = 4	q5 = 3
	D21 = -1	D32 = 0	D13 = -4	D14 = 1	D15 = 3
	D31 = -4		D33 = -7		D25 = 0
	Zmin =

 

	b1=34	b2=40	b3=38	b4=53	b5=5
a1=80		- 7		+ 3 *		p1 = 0
a2=60		+ 5		- 2		p2 = -2
a3=30						p3 = -3
	q1 = 2	q2 = 7	q3 = 2	q4 = 4	q5 = 0
	D21 = 0	D32 = 0	D23 = -4	D14 = 1	D25 = -2
	D31 = -4		D33 = -7		D35 = -3
	Zmin =

 

 

	b1=34	b2=40	b3=38	b4=53	b5=5
a1=80						p1 = 0
a2=60						p2 = -1
a3=30						p3 = -2
	q1 = 2	q2 = 6	q3 = 2	q4 = 3	q5 = 0
	D21 = 0	D12 = -1	D23 = -3		D25 = -1
	D31 = -3	D32 = 0	D33 = -6		D35 = -2
	Zmin =

 

Все потенциалы свободных клеток D_ij неположительные, следовательно, решение, представленное в последней таблице, является оптимальным, причем минимальная стоимость всех перевозок составляет 423 единицы.

 

Постановка задачи

Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб. (выделяемые суммы кратны 100 тыс. руб.).

 

 

Исходные данные

Значения функции f_j(х_j) приведены в Таблице 1 (считаем их заданными, их определение - довольно трудоемкая экономическая задача):

 

Таблица 1

xj
f1(xj)
f2(xj)
f3(xj)
f4(xj)

 

 

Решение

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

Введем параметр состояния x - количество рублей, выделяемых нескольким предприятиям, и определим функцию состояния F_k(x) - максимальная прибыль на первых k предприятиях, если они вместе получат х_k рублей.

Табулируя последовательно функции F_k(x), получим решение, ход которого приведен в Таблицах 2-6.

 

Таблица 2

	x-х2
х2	F(x-x2) f2(x2)
		22*	42*
			57*	70*
				82*
				92*	101*
				101*

 

Таблица 3

x
F2(x)
x2(x)								400/500

 

Таблица 4

	x-х3
х3	F(x-x3) f3(x3)
		0*	22*	42*	57*
				71*	86*	99*
					99*	112*

 

Таблица 5

x
F2(x)
x2(x)							200/300

Таблица 6

	x-х4
х4	F(x-x4) f4(x4)
								115*

 

Z_max = 115 тыс. руб.,

 

причем четвертому предприятию должно быть выделено

х₄* = х₄(700) = 100 тыс. руб.

 

На долю остальных трех предприятий остается 600 тыс. руб. Из Таблицы 5 видно, что третьему предприятию должно быть выделено

1) х₃* = х₃(700 - х₄*) = х₃(600) = 200 тыс. руб.

2) х₃* = х₃(700 - х₄*) = х₃(600) = 300 тыс. руб.

 

Продолжая обратный процесс, находим

1) х₂* = х₂(700 - х₄* - х₃*) = х₂(400) = 200 тыс. руб.

2) х₂* = х₂(700 - х₄* - х₃*) = х₂(300) = 200 тыс. руб.

 

На долю первого предприятия останется

1) х₁* = 700 - х₄* - х₃* - х₂* = 200 тыс. руб.

2) х₁* = 700 - х₄* - х₃* - х₂* = 100 тыс. руб.

 

Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:

1) х₁* = 200; х₂* = 200; х₃* = 200; х₄* = 100

2) х₁* = 100; х₂* = 200; х₃* = 300; х₄* = 100

 

Оно обеспечивает производственному объединению наибольший возможный прирост прибыли 115 тыс. руб.

В качестве проверки правильности решения задачи можно использовать равенство

 

f₁(x₁*) + f₂(x₂*) + f₃(x₃*) + f₄(x₄*) = Z_max

1) f₁(200) + f₂(200) + f₃(200) + f₄(100) = 33 + 37 + 29 + 16 = 115 = Z_max

2) f₁(100) + f₂(200) + f₃(300) + f₄(100) = 20 + 37 + 42 + 16 = 115 = Z_max

 

Следовательно, полученные решения верны.

Постановка задачи

Рассмотреть динамическую задачу управления производством и запасами.

 

 

Исходные данные

 

Спрос (заявки) потребителей на продукцию составляют: на первый этап d₁ = 5 единиц, на второй – d₂ = 1, на третий - d₃ = 2 единицы. К началу первого этапа на складе имеется только 4 единицы продукции, т.е. начальный уровень запаса равен y₁=4. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h₁ = 2, h₂ = 1, h₃ = 1. Затраты на производство x_j единиц продукции на j-м этапе определяются функцией

 

j_j(x_j) = 2 * x_j² + 6 (1)

 

т.е. а = 2; b = 0; с = 6. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а общие затраты на производство и хранение за все три этапа были наименьшими.

 

 

Решение

 

Воспользовавшись рекурентными соотношениями, последовательно вычисляем F₁ (x = y₂), F₂ (x = y₃),..., F_k (x = y_k+1),... и соответственно находим ₁ (x= y₂), ₂ (x = y₃),..., ` _k (x = y_k+1),...

 

Положим k = 1. Тогда имеем

 

F₁(x= y₂) = min{2 * x_j² + 6 + 2 * y₂} (2)

 

Учтем, что параметр состояния x = у₂ может принимать целые значения на отрезке

0 у₂ d₂ + d₃

0 y₂ 3

т.е.

у₂ = 0, 1, 2, 3

 

При этом каждому значению параметра состояния должна отвечать определенная область изменения переменной x₁, характеризуемая условием

 

0 х₁ d₁ + у₂

0 х₁ 5 + у₂

 

Из балансового уравнения

 

х₁ + у₁ - d₁ = у₂

 

непосредственно следует, что объем производства связан со значением параметра состояния x= у₂ соотношением

 

x₁ = y₂ + d₁ - y₁ = y₂ + 5 - 4 = y₂ + 1 (3)

 

Каждому значению у₂ отвечает единственное значение х₁ и потому

 

F₁(x = y₂) = W₁ (x₁, y₂)

 

Придавая у₂ различные целые значения от 0 до 3 и учитывая (3), находим

 

y₂ = 0, x₁ = 1, W₁ (1;0) = 2 * 1² + 6 + 2 * 0 = 8

y₂ = 1, x₁ = 2, W₁ (2;1) = 2 * 2² + 6 + 2 * 1 = 16

y₂ = 2, x₁ = 3, W₁ (3;2) = 2 * 3² + 6 + 2 * 2 = 28

y₂ = 3, x₁ = 4, W₁ (4;3) = 2 * 4² + 6 + 2 * 3 = 44

 

Значения функции состояния F₁(x) представлены в Таблице 1.

Таблица 1

x = y2
F1 (x = y2)
x1(x=y2)

 

 

Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию F₂(x = y₃):

 

F₂(x = y₃) = min W₁ (x₁, y₂) = min{a * x₂² + b * x₂ + c + h₂ * y₃ + F₁(y₂)} =

= min {2 * x₂² + 6 + y₃ + F₁(y₂)} (4)

 

Здесь минимум берется по единственной переменной х₂, которая может изменяться в пределах

 

0 £ x₂ £ d₂ + y₃ или 0 £ x₂ £ 1 + y₃ (5)

 

где верхняя граница зависит от параметра состояния x = у₃, который принимает значения на отрезке

 

0 £ y₃ £ d₃, т.е. 0 £ y₃ £ 2 (6)

 

а аргумент у₂ в последнем слагаемом справа в соотношении (4) связан с х₂ и у₃ балансовым уравнением

 

x₂ + y₂ - d₂ = y₃

откуда следует

y₂ = y₃ + d₂ - x₂ = y₃ + 1 - x₂ (7)

 

Придавая параметру состояния различные значения от 0 до 2, будем последовательно вычислять W₂ (x₂, x), а затем определять F₂(x) и ₂(x).

 

Положим x = у₃ = 0. Тогда, согласно (5),

 

0 £ x₂ £ 1,

 

т.е. переменная х₂ может принимать значения 0, 1, которым отвечает значение у₂, вычисляемое по формуле (7):

 

у₂ = 1 - х₂

 

Последовательно находим:

 

x₂ = 0, y₂ = 1 - 0 = 1, W₂ (0,0) = 2 * 0² + 6 + 0 + F₁(1) = 6 + 16 = 22

x₂ = 1, y₂ = 1 - 1 = 0, W₂ (1,0) = 2 * 1² + 6 + 0 + F₁(0) = 8 + 8 = 16*

 

Наименьшее из полученных значений W₂ есть F₂ (0), т.е.

 

F₂ (x = y₃ = 0) = min W₂ (x₂,0) = min (22, 16) = 16,

x₂

 

причем минимум достигается при значении х₂, равном

 

` ₂ (x = y₃ = 0) = 1

 

Положим x = у₃ = 1. Тогда, согласно (5),

 

0 £ x₂ £ 2,

 

т.е. переменная х₂ может принимать значения: 0, 1, 2, а каждому значению х₂ отвечает определенное значение у₂, вычисляемое по формуле (7)