Контрольная работа по "Прикладная математика"

 

Перемещаем  по циклу груз величиной в 10 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Поставщик	Потребитель				Запасы   груза
	B1	B2	B3	B4
A1	10 30	8	12	11	30
A2	9 10	6 20	3 10	5 20	60
A3	7	4	1	2 10	10
Потребность	40	20	10	30

 
Целевая функция F= 660

Значение  целевой функции изменилось на 10 единиц по сравнению с предыдущим этапом.

Этап 3

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки. 
Потенциалы U_i: U₁=0

V₁=C_1,1-U₁= 10

U₂=C_1,2-V₁= -1

V₂=C_2,2-U₂= 7

V₃=C_2,3-U₂= 4

V₄=C_2,4-U₂= 6

U₃=C_4,3-V₄= -4

Определяем  значения оценок S_i,j=C_i,j-(V_j-U_i) для всех свободных клеток:

Для случая X_i,j = 0 условие оптимальности оценки S_i,j определяется следующим образом: S_i,j >=0.

Для случая X_i,j = D_i,j условие оптимальности оценки S_i,j определяется следующим образом: S_i,j <=0.

оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = 0 (неоптимальные выделены курсивом)

S_1,2 = c_1,2 - (v₂ + u₁) = 1.

S_1,3 = c_1,3 - (v₃ + u₁) = 8.

S_1,4 = c_1,4 - (v₄ + u₁) = 5.

S_3,1 = c_3,1 - (v₁ + u₃) = 1.

S_3,2 = c_3,2 - (v₂ + u₃) = 1.

S_3,3 = c_3,3 - (v₃ + u₃) = 1.Так как все условия оптимальности выполнены, то полученный план является оптимальным. Транспортная задача решена.

Поставщик	Потребитель				Запасы   груза
	B1	B2	B3	B4
A1	10 30	8	12	11	30
A2	9 10	6 20	3 10	5 20	60
A3	7	4	1	2 10	10
Потребность	40	20	10	30

 

 

 

Целевая функция F= 660

Составлен оптимальный план перевозок, при  котором транспортные издержки минимальны и равны 660 усл.д.е. При этом от поставщика А1 потребителю В1 перевозится 30 единиц. От поставщика А2 потребителю В1 перевозится 10 единиц, потребителю В2 – 20 единиц, потребителю В3 – 10 единиц, потребителю В4 – 20 единиц. От поставщика А3 потребителю В4 перевозится 10 единиц.

 

 

 

 

 

Задача 75

Методом динамического программирования найти  такое распределение капиталовложений в объеме 500 у.д.е. между четырьмя предприятиями, которое максимизирует  суммарную прибыль. Известна прибыль  f_i(x_j), получаемая каждым предприятием при выделении ему капиталовложений в объеме x_j  у.д.е.

xj	0	100	200	300	400	500
f1(xj)	0	28	45	65	70	72
f2(xj)	0	25	41	55	65	64
f3(xj)	0	15	25	40	50	58
f4(xj)	0	20	33	42	48	53

Решение

Заполним первоначальную таблицу 1. Значения f₂(x₂) складываем со значениями F(ξ – x₂) = f₁(ξ – x₂), на каждой диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение .

Таблица 1

	ξ – x2	0	100	200	300	400	500
x2	F1(ξ – x2) f2( x2)	0	28	45	65	70	72
0	0	0	28*	45	65	70	72
100	25	25	53*	70*	90*	95
200	41	41	69	86	106*
300	55	55	83	100
400	65	65	93
500	64	64

 

По итогам этой таблицы заполняем  следующую таблицу 2:

Таблица 2

ξ	0	100	200	300	400	500
F2(ξ)	0	28	53	70	90	106
	0	0	100	100	100	200

 

Продолжая процесс, табулируем функции  F₃(ξ), и т.д.

Таблица 3

	ξ – x3	0	100	200	300	400	500
x3	F2(ξ – x3) f3( x3)	0	25	41	55	65	64
0	0	0	25*	41*	55	65	64
100	15	15	40	56*	70*	80*
200	25	25	50	66	80*
300	40	40	65	81
400	50	50	75
500	58	58

 

Таблица 4

ξ	0	100	200	300	400	500
F3(ξ)	0	25	41	56	70	80
	0	0	0	100	100	200

 

Для последней таблицы заполняем  только одну диагональ для ξ = 500.

 

Таблица 5

	ξ – x3	0	15	25	40	50	58
x3	F2(ξ – x3) f3( x3)	0	15	25	40	50	58
0	0						58
100	20					70
200	33				73*
300	42			67
400	48		63
500	43	43

 

Наибольшее число по этой диагонали  z_max = 73, причем для получения такой прибыли четвертому предприятию должно быть выделено 200 д.е.:

На долю остальных трех предприятий  остается 300 д.е.

По таблице 4 определяем, что третьему предприятию должно быть выделено:

На долю первого и второго  предприятий остается 200 д.е.

По таблице 2 определяем, что второму  предприятию должно быть выделено:

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

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

Задача 85

Даны четыре операции Q₁, Q₂, Q₃, Q₄. Найти средние ожидаемые доходы и риски r_i операций. Нанесите точки ( , r_i) на плоскость, найдите операции оптимальные по Парето. С помощью взвешивающей формулы найдите лучшую и худшую операции. Взвешивающая формула одна и та же: φ(Q) = 2   – r.

Q1:	0	1	2	8
	1/3	1/3	1/6	1/6