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

Размещено на http://www.allbest.ru/

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

Сформулировать линейную производственную задачу и составить ее математическую модель, взяв исходные данные из приложения 1, где технологическая матрица А затрат различных ресурсов на единицу каждой продукции, вектор объемов ресурсов В и вектор удельной прибыли С при возможном выпуске четырех видов продукции с использованием трех видов ресурсов

компактно записаны в виде

c1 c2 c3 c4

а11 а12 а13 а14 b1

a21 a22 a23 a24 b2

a31 a32 a33 a34 b3

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

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

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

1.16

27 10 9 8

3 5 0 6 144

2 0 1 0 130

1 4 2 3 140

Задача имеет вид:

F(X) = 27x1 + 10x2 + 9x3 + 8x4 > max при ограничениях:

3x1 + 5x2 + 6x4?144

2x1 + x3?130

x1 + 4x2 + 2x3 + 3x4?140

Для приведения к канонической форме необходимо:

В 1-м неравенстве смысла (?) вводим базисную переменную x5. В 2-м неравенстве смысла (?) вводим базисную переменную x6. В 3-м неравенстве смысла (?) вводим базисную переменную x7.

3x1 + 5x2 + 0x3 + 6x4 + 1x5 + 0x6 + 0x7 = 144

2x1 + 0x2 + 1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 130

1x1 + 4x2 + 2x3 + 3x4 + 0x5 + 0x6 + 1x7 = 140

F(X) = 27x1 + 10x2 + 9x3 + 8x4

Расширенная матрица системы ограничений-равенств данной задачи:

3	5	0	6	1	0	0	144
2	0	1	0	0	1	0	130
1	4	2	3	0	0	1	140

Поскольку в системе имеется единичная матрица, то соответствующие уравнения имеют вид:

3x1 + 5x2 + 6x4 + x5 = 144

2x1 + x3 + x6 = 130

x1 + 4x2 + 2x3 + 3x4 + x7 = 140

Выразим базисные переменные через остальные:

x = - 3x1 - 5x2 - 6x4 - x5+144

x = - 2x1 - x3 - x6+130

x = - x1 - 4x2 - 2x3 - 3x4 - x7+140

Подставим их в целевую функцию:

F(X) = 27x1 + 10x2 + 9x3 + 8x4

F(X) = 27x1 + 10x2 + 9x3 + 8x4 > max

Система неравенств:

- 3x1 - 5x2 - 6x4 - x5+144 ? 0

- 2x1 - x3 - x6+130 ? 0

- x1 - 4x2 - 2x3 - 3x4 - x7+140 ? 0

Приводим систему неравенств к следующему виду:

3x1 + 5x2 + 6x4 + x5 ? 144

2x1 + x3 + x6 ? 130

x1 + 4x2 + 2x3 + 3x4 + x7 ? 140

F(X) = 27x1 + 10x2 + 9x3 + 8x4 > max

Упростим систему.

3x1 + 5x2 + 6x4 + x5 ? 144

2x1 + x3 + x6 ? 130

x1 + 4x2 + 2x3 + 3x4 + x7 ? 140

F(X) = 27x1 + 10x2 + 9x3 + 8x4 > max

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

Определим максимальное значение целевой функции F(X) = 27x1 + 10x2 + 9x3 + 8x4 при следующих условиях-ограничений.

3x1 + 5x2 + 6x4 + x5?144

2x1 + x3 + x6?130

x1 + 4x2 + 2x3 + 3x4 + x7?140

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (?) вводим базисную переменную x8. В 2-м неравенстве смысла (?) вводим базисную переменную x9. В 3-м неравенстве смысла (?) вводим базисную переменную x10.

3x1 + 5x2 + 0x3 + 6x4 + 1x5 + 0x6 + 0x7 + 1x8 + 0x9 + 0x10 = 144

2x1 + 0x2 + 1x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 + 1x9 + 0x10 = 130

1x1 + 4x2 + 2x3 + 3x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 + 1x10 = 140

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

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

x8, x9, x10,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,0,0,0,0,144,130,140)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x8	144	3	5	0	6	1	0	0	1	0	0
x9	130	2	0	1	0	0	1	0	0	1	0
x10	140	1	4	2	3	0	0	1	0	0	1
F(X0)	0	-27	-10	-9	-8	0	0	0	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

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

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления:bi / ai1

и из них выберем наименьшее:

min (144:3 , 130:2 , 140:1) = 48

Следовательно, 1-ая строка является ведущей.

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	min
x8	144	3	5	0	6	1	0	0	1	0	0	48
x9	130	2	0	1	0	0	1	0	0	1	0	65
x10	140	1	4	2	3	0	0	1	0	0	1	140
F(X1)	0	-27	-10	-9	-8	0	0	0	0	0	0	0

Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 1 войдет переменная x1 .

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x8 плана 0 на разрешающий элемент РЭ=3

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x1 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 .

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9	x 10
144:3	3:3	5:3	0:3	6:3	1:3	0:3	0:3	1:3	0:3	0:3
130-(144 * 2):3	2-(3 * 2):3	0-(5 * 2):3	1-(0 * 2):3	0-(6 * 2):3	0-(1 * 2):3	1-(0 * 2):3	0-(0 * 2):3	0-(1 * 2):3	1-(0 * 2):3	0-(0 * 2):3
140-(144 * 1):3	1-(3 * 1):3	4-(5 * 1):3	2-(0 * 1):3	3-(6 * 1):3	0-(1 * 1):3	0-(0 * 1):3	1-(0 * 1):3	0-(1 * 1):3	0-(0 * 1):3	1-(0 * 1):3
0-(144 * -27):3	-27-(3 * -27):3	-10-(5 * -27):3	-9-(0 * -27):3	-8-(6 * -27):3	0-(1 * -27):3	0-(0 * -27):3	0-(0 * -27):3	0-(1 * -27):3	0-(0 * -27):3	0-(0 * -27):3

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	48	1	12/3	0	2	1/3	0	0	1/3	0	0
x9	34	0	-31/3	1	-4	-2/3	1	0	-2/3	1	0
x10	92	0	21/3	2	1	-1/3	0	1	-1/3	0	1
F(X1)	1296	0	35	-9	46	9	0	0	9	0	0

Итерация №1.

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

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления:bi / ai3

и из них выберем наименьшее:

min (- , 34:1 , 92:2) = 34

Следовательно, 2-ая строка является ведущей.

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	min
x1	48	1	12/3	0	2	1/3	0	0	1/3	0	0	-
x9	34	0	-31/3	1	-4	-2/3	1	0	-2/3	1	0	34
x10	92	0	21/3	2	1	-1/3	0	1	-1/3	0	1	46
F(X2)	1296	0	35	-9	46	9	0	0	9	0	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 2 войдет переменная x3 .

Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x9 плана 1 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x3 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x3 и столбец x3 .

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9	x 10
48-(34 * 0):1	1-(0 * 0):1	12/3-(-31/3 * 0):1	0-(1 * 0):1	2-(-4 * 0):1	1/3-(-2/3 * 0):1	0-(1 * 0):1	0-(0 * 0):1	1/3-(-2/3 * 0):1	0-(1 * 0):1	0-(0 * 0):1
34:1	0:1	-31/3:1	1:1	-4:1	-2/3:1	1:1	0:1	-2/3:1	1:1	0:1
92-(34 * 2):1	0-(0 * 2):1	21/3-(-31/3 * 2):1	2-(1 * 2):1	1-(-4 * 2):1	-1/3-(-2/3 * 2):1	0-(1 * 2):1	1-(0 * 2):1	-1/3-(-2/3 * 2):1	0-(1 * 2):1	1-(0 * 2):1
1296-(34 * -9):1	0-(0 * -9):1	35-(-31/3 * -9):1	-9-(1 * -9):1	46-(-4 * -9):1	9-(-2/3 * -9):1	0-(1 * -9):1	0-(0 * -9):1	9-(-2/3 * -9):1	0-(1 * -9):1	0-(0 * -9):1

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	48	1	12/3	0	2	1/3	0	0	1/3	0	0
x3	34	0	-31/3	1	-4	-2/3	1	0	-2/3	1	0
x10	24	0	9	0	9	1	-2	1	1	-2	1
F(X2)	1602	0	5	0	10	3	9	0	3	9	0

транспортный задача динамический программирование

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

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	48	1	12/3	0	2	1/3	0	0	1/3	0	0
x3	34	0	-31/3	1	-4	-2/3	1	0	-2/3	1	0
x10	24	0	9	0	9	1	-2	1	1	-2	1
F(X3)	1602	0	5	0	10	3	9	0	3	9	0

Оптимальный план можно записать так:

x1 = 48

x3 = 34

x10 = 24

F(X) = 27*48 + 9*34 = 1602

Возвращаемся к системе уравнения в СЗЛП.

x = - 3x1 - 5x2 - 6x4 - x5+144

x = - 2x1 - x3 - x6+130

x = - x1 - 4x2 - 2x3 - 3x4 - x7+140

Подставим в них найденные переменные.

x = -3*48 -5*0 + 0*34 -6*0 -1*0 + 0*0 + 0*0 + 144 = 0

x = -2*48 + 0*0 -1*34 + 0*0 + 0*0 -1*0 + 0*0 + 130 = 0

x = -1*48 -4*0 -2*34 -3*0 + 0*0 + 0*0 -1*0 + 140 = 24

Проверка в Excel:



Рис. 1

Целесообразно в заданных условиях выпускать продукцию 1 и 3. При этом имеется излишек ресурса 3 в количестве 24.

Формулировка задачи для графического решения имеет вид:

F(X) = 27x1 + 9x3 > max при ограничениях:

3x1 ?144

2x1 + x3?130

x1 + 2x3?140

Графическое решение имеет вид:

Рис. 2

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

Вектор двойственных оценок, минимизирующий общую оценку ресурсов, будет иметь вид:

Здесь - расчетные или двойственные оценки ресурсов.

Ограничения:

Оценки ресурсов

По второй теореме двойственности

и

Так как , то с учетом избыточности третьего ресурса задача сводится к решению системы

Откуда

Общая оценка всех ресурсов

Таким образом, добавление ресурса 1 или 2 обеспечит прирост прибыли на 3 и 9 единиц соответственно.

Задача о «расшивке узких мест»

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

При условии сохранения

, а также в предположении, что

Графическое решение задачи имеет вид:

Рис. 3



Прирост прибыли составит 738 единиц.

Транспортная задача линейного программирования

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

	27	20	39	42
35	3	5	3	6
60	5	6	1	7
40	1	4	2	3

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

F = ??cijxij, (1)

при условиях:

?xij = ai, i = 1,2,…, m, (2)

?xij = bj, j = 1,2,…, n, (3)

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

	1	2	3	4	Запасы
1	3	5	3	6	35
2	5	6	1	7	60
3	1	4	2	3	40
Потребности	27	20	39	42

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 35 + 60 + 40 = 135

?b = 27 + 20 + 39 + 42 = 128

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	Запасы
1	3	5	3	6	0	35
2	5	6	1	7	0	60
3	1	4	2	3	0	40
Потребности	27	20	39	42	7

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

	1	2	3	4	5	Запасы
1	3	5[20]	3	6[15]	0	35
2	5	6	1[39]	7[14]	0[7]	60
3	1[27]	4	2	3[13]	0	40
Потребности	27	20	39	42	7

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

	v1=4	v2=5	v3=0	v4=6	v5=-1
u1=0	3	5[20]	3	6[15]	0
u2=1	5	6	1[39]	7[14]	0[7]
u3=-3	1[27]	4	2	3[13]	0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

Выбираем максимальную оценку свободной клетки (1;1):3

Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[+]	5[20]	3	6[15][-]	0	35
2	5	6	1[39]	7[14]	0[7]	60
3	1[27][-]	4	2	3[13][+]	0	40
Потребности	27	20	39	42	7

Цикл приведен в таблице (1,1; 1,4; 3,4; 3,1; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	3[15]	5[20]	3	6	0	35
2	5	6	1[39]	7[14]	0[7]	60
3	1[12]	4	2	3[28]	0	40
Потребности	27	20	39	42	7

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

	v1=3	v2=5	v3=-1	v4=5	v5=-2
u1=0	3[15]	5[20]	3	6	0
u2=2	5	6	1[39]	7[14]	0[7]
u3=-2	1[12]	4	2	3[28]	0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

Выбираем максимальную оценку свободной клетки (2;2):6

Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[15][+]	5[20][-]	3	6	0	35
2	5	6[+]	1[39]	7[14][-]	0[7]	60
3	1[12][-]	4	2	3[28][+]	0	40
Потребности	27	20	39	42	7

Цикл приведен в таблице (2,2; 2,4; 3,4; 3,1; 1,1; 1,2; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 1) = 12. Прибавляем 12 к объемам грузов, стоящих в плюсовых клетках и вычитаем 12 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	3[27]	5[8]	3	6	0	35
2	5	6[12]	1[39]	7[2]	0[7]	60
3	1	4	2	3[40]	0	40
Потребности	27	20	39	42	7

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

	v1=3	v2=5	v3=0	v4=6	v5=-1
u1=0	3[27]	5[8]	3	6	0
u2=1	5	6[12]	1[39]	7[2]	0[7]
u3=-3	1	4	2	3[40]	0

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты составят:

F(x) = 3*27 + 5*8 + 6*12 + 1*39 + 7*2 + 0*7 + 3*40 = 366

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

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

0	25	41	55	65	75	80	85
0	30	52	76	90	104	116	125
0	50	68	82	92	100	107	112
0	61	80	93	100	106	112	116

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

f1	f2	f3	f4	xi
0	0	0	0	0
25	30	50	61	100
41	52	68	80	200
55	76	82	93	300
65	90	92	100	400
75	104	100	106	500
80	116	107	112	600
85	125	112	116	700

I этап. Условная оптимизация.

1-ый шаг. k = 4.

e3	u4	e4 = e3 - u4	f4(u4)	F*4(e4)	u4(e4)
100	0	100	0
	100	0	61	61	100
200	0	200	0
	100	100	61
	200	0	80	80	200
300	0	300	0
	100	200	61
	200	100	80
	300	0	93	93	300
400	0	400	0
	100	300	61
	200	200	80
	300	100	93
	400	0	100	100	400
500	0	500	0
	100	400	61
	200	300	80
	300	200	93
	400	100	100
	500	0	106	106	500
600	0	600	0
	100	500	61
	200	400	80
	300	300	93
	400	200	100
	500	100	106
	600	0	112	112	600
700	0	700	0
	100	600	61
	200	500	80
	300	400	93
	400	300	100
	500	200	106
	600	100	112
	700	0	116	116	700

2-ый шаг. k = 3.

e2	u3	e3 = e2 - u3	f3(u3)	F*3(e2)	F2(u3,e2)	F*3(e3)	u3(e3)
100	0	100	0	61	61	61	0
	100	0	50	0	50
200	0	200	0	80	80
	100	100	50	61	111	111	100
	200	0	68	0	68
300	0	300	0	93	93
	100	200	50	80	130	130	100
	200	100	68	61	129
	300	0	82	0	82
400	0	400	0	100	100
	100	300	50	93	143
	200	200	68	80	148	148	200
	300	100	82	61	143
	400	0	92	0	92
500	0	500	0	106	106
	100	400	50	100	150
	200	300	68	93	161
	300	200	82	80	162	162	300
	400	100	92	61	153
	500	0	100	0	100
600	0	600	0	112	112
	100	500	50	106	156
	200	400	68	100	168
	300	300	82	93	175	175	300
	400	200	92	80	172
	500	100	100	61	161
	600	0	107	0	107
700	0	700	0	116	116
	100	600	50	112	162
	200	500	68	106	174
	300	400	82	100	182
	400	300	92	93	185	185	400
	500	200	100	80	180
	600	100	107	61	168
	700	0	112	0	112

3-ый шаг. k = 2.

e1	u2	e2 = e1 - u2	f2(u2)	F*2(e1)	F1(u2,e1)	F*2(e2)	u2(e2)
100	0	100	0	61	61	61	0
	100	0	30	0	30
200	0	200	0	111	111	111	0
	100	100	30	61	91
	200	0	52	0	52
300	0	300	0	130	130
	100	200	30	111	141	141	100
	200	100	52	61	113
	300	0	76	0	76
400	0	400	0	148	148
	100	300	30	130	160
	200	200	52	111	163	163	200
	300	100	76	61	137
	400	0	90	0	90
500	0	500	0	162	162
	100	400	30	148	178
	200	300	52	130	182
	300	200	76	111	187	187	300
	400	100	90	61	151
	500	0	104	0	104
600	0	600	0	175	175
	100	500	30	162	192
	200	400	52	148	200
	300	300	76	130	206	206	300
	400	200	90	111	201
	500	100	104	61	165
	600	0	116	0	116
700	0	700	0	185	185
	100	600	30	175	205
	200	500	52	162	214
	300	400	76	148	224	224	300
	400	300	90	130	220
	500	200	104	111	215
	600	100	116	61	177
	700	0	125	0	125

4-ый шаг. k = 1.

e0	u1	e1 = e0 - u1	f1(u1)	F*1(e0)	F0(u1,e0)	F*1(e1)	u1(e1)
100	0	100	0	61	61	61	0
	100	0	25	0	25
200	0	200	0	111	111	111	0
	100	100	25	61	86
	200	0	41	0	41
300	0	300	0	141	141	141	0
	100	200	25	111	136
	200	100	41	61	102
	300	0	55	0	55
400	0	400	0	163	163
	100	300	25	141	166	166	100
	200	200	41	111	152
	300	100	55	61	116
	400	0	65	0	65
500	0	500	0	187	187
	100	400	25	163	188	188	100
	200	300	41	141	182
	300	200	55	111	166
	400	100	65	61	126
	500	0	75	0	75
600	0	600	0	206	206
	100	500	25	187	212	212	100
	200	400	41	163	204
	300	300	55	141	196
	400	200	65	111	176
	500	100	75	61	136
	600	0	80	0	80
700	0	700	0	224	224
	100	600	25	206	231	231	100
	200	500	41	187	228
	300	400	55	163	218
	400	300	65	141	206
	500	200	75	111	186
	600	100	80	61	141
	700	0	85	0	85

Поясним построение таблиц и последовательность проведения расчетов. Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 4-го шага столбцы 5 и 6 отсутствуют). В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

Этап II. Безусловная оптимизация.

Из таблицы 4-го шага имеем F*1(e0 = 700) = 231. То есть максимальный доход всей системы при количестве средств e0 = 700 равен 231

Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 700) = 100

При этом остаток средств составит:

e1 = e0 - u1

e1 = 700 - 100 = 600

Из таблицы 3-го шага имеем F*2(e1 = 600) = 206. То есть максимальный доход всей системы при количестве средств e1 = 600 равен 206

Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 600) = 300

При этом остаток средств составит:

e2 = e1 - u2

e2 = 600 - 300 = 300

Из таблицы 2-го шага имеем F*3(e2 = 300) = 130. То есть максимальный доход всей системы при количестве средств e2 = 300 равен 130

Из этой же таблицы получаем, что 3-му предприятию следует выделить u*3(e2 = 300) = 100

При этом остаток средств составит:

e3 = e2 - u3

e3 = 300 - 100 = 200

Последнему предприятию достается 200

Итак, инвестиции в размере 700 необходимо распределить следующим образом:

1-му предприятию выделить 100

2-му предприятию выделить 300

3-му предприятию выделить 100

4-му предприятию выделить 200

Что обеспечит максимальный доход, равный 231

Анализ доходности и риска финансовых операций

Даны четыре операции Q1, Q2, Q3, Q4. Найдите средние ожидаемые доходы и риски ri операций. Нанесите точки (, ri) на плоскость, найдите операции, оптимальные по Парето. С помощью взвешивающей формулы найдите лучшую и худшую операции.

Взвешивающая формул:(Q) = 2- r.

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

Q1	:	2	6	8	22	Q2	:	0	4	8	32
		1/2	1/4	1/5	1/20			1/2	1/4	1/8	1/8
Q3	:	-6	-4	-2	10	Q4	:	0	8	12	24
		1/2	1/4	1/8	1/8			1/4	1/4	1/3	1/6

Математическое ожидание случайной величины и её дисперсия в случае, когда эта величина представляет собой доходность финансовой операции, соответственно являют собой среднюю ожидаемую доходность и квадрат риска.

Q1	:	2	6	8	22
	р	1/2	1/4	1/5	1/20
	ожидаемая доходность	риск
Q1	5	48	5,421791
Q2	6	140	1,801961
Q3	-3	35	-11,099
Q4	10.04	161,44	12,29293

Рис. 4

транспортный задача динамический программирование

Анализ по Парето и по заданному критерию показывает, что наилучшим вариантом является операция , а наихудшим - .

Размещено на Allbest.ru