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

Государственный Университет Управления

 

Институт управления

в машиностроительной промышленности

 

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

 

Курсовая работа по дисциплине

“Прикладная математика”

 

 

Выполнил: студент группы маш II-3,

Шерстобитов А. В.

Проверил: Онищенко А. М.

 

Москва, 2001

Содержание

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

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

Задача о "расшивке узких мест производства" 6

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

4. Динамическое программирование. Распределение капитальных вложений 11

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

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

8. Задача о кратчайшем пути 18

9. Задача о назначениях 19

14. Матричная модель производственной программы предприятия 20

15. Принятие решений в условиях неопределенности 21

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

17. Задача формирования оптимального портфеля ценных бумаг 25

 

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

 

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

Теперь представим себе, что возникла новая ситуация. Знакомый предприниматель, занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у₁ рублей за каждую единицу первого ресурса, у₂ руб – второго, у₃ руб – третьего. Возникает вопрос: при каких ценах у₁, у₂, у₃ мы можем согласиться с предложением.

Величины у₁, у₂, у₃ принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.

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

 

4 0 8 7 316

A = 3 2 5 1 B= 216 C= (31 10 41 29)

5 6 3 7 199

 

Для производства единицы продукции первого вида необходимо затратить, как видно из матрицы А, 4 единицы ресурса первого вида, 3 единицы ресурса второго вида и 5 единиц третьего (элементы первого столбца матрицы). В ценах у₁, у₂, у₃ затраты составят 4у₁ + 3у₂ + 5у₃, т.е. столько заплатит предприниматель за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 31 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше

4у₁ + 3у₂ + 5у₃ ³ 31

 

Аналогично, во втором столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции второго вида. Эти затраты составят 2у₂ + 6у₃, а на рынке за единицу продукции второго вида мы получили бы прибыль 10 рублей. Поэтому перед предпринимателем ставится условие

5у₁ + 4у₃ ³ 10

и так далее по всем видам продукции.

За все имеющиеся у нас ресурсы нам должны заплатить 316у₁ + 216у₂ + 199у₃ рублей. При поставленных нами условиях предприниматель будет искать такие значения величин у₁, у₂, у₃, чтобы эта сумма была как можно меньше. Здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.

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

 

y (у₁, y₂, y₃)

 

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

 

W= 316y₁ + 216y₂ +199y₃ (1)

 

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

4у₁ + 3у₂ + 5у₃ ³ 31

5у₁ + 4у₃ ³ 10 (2)

8у₁ + 5у₂ + 3у₃ ³ 41

7у₁ + 1у₂ + 7у₃ ³ 29

 

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

 

y₁ 0, y₂ 0, y₃ 0 (3)

 

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

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

пары двойственных задач необходимо и достаточно выполнение условий

 

23 (4у₁ + 3у₂ + 5у₃ – 31) = 0

0 (5у₁ + 4у₃ – 10) = 0

28 (8у₁ + 5у₂ + 3у₃ – 41) = 0

0 (7у₁ + 1у₂ + 7у₃ – 29) = 0

 

Так как x₁ > 0 и x₃ > 0, то

y₁ (4*23 +8*28 - 316) = 0

y₂ (3*23 +5*28 - 216) = 0

y₃ (5*23 + 3*28 - 199) = 0

 

4y₁ + 3y₂ + 5y₃ = 31

8y₁ + 5y₂ + 3y₃ = 41

y₂=0

 

откуда следует у₁=4, у₃=3.

 

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

 

у₁=4; у₂=0; у₃=3, (4)

 

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

Решение (4) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка второго ресурса у₁=4 показывает, что добавление одной единицы 1-го ресурса обеспечит прирост прибыли в 4 единицы.

 

 

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

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

H + Q ^-1T 0.

Задача состоит в том, чтобы найти вектор T (t₁, 0, t₃), максимизирующий суммарный прирост прибыли

W = 4t₁ + 3t₃ (1)

 

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

 

(2)

 

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

 

t₁ 316

0 <=1/3* 216 (3)

t₃ 199

 

По смыслу задачи t₁ ³ 0, t₃ ³ 0

 

 

28 + 1/28*t₁ ³ 0

7 - 4/7*t₁ - 1/7*t₃ ³ 0

23 –3/28*t₁ + 2/7 t₃ ³ 0

t₁ £ 316/3

t₃ £ 199/3

 

t₁ ³ -784

4/7*t₁ + 1/7*t₃ £ 7

–3/28*t₁ + 2/7 t₃ ³ 23

t₁ £ 316/3

t₃ £ 199/3

t₁ ³ 0, t₃ ³0

 

Находим координаты точки А(t1,t2). t₁ = 0, t₂ =49, и прирост прибыли составляет 0*4+49*3=147 рублей.

 

cj					b	x4+i	yi	ti
aij							-3/28
						2/7
xj
Dj

 

 

Таблица 1

xj
f1 (x1)
f2 (x2)
f3 (x3)
f4 (x4)

 

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

Продолжая процесс, табулируем функции F₃(x), (x) и т.д. В табл. 6 заполняем только одну диагональ для значения x= 700. Наибольшее число на этой диагонали:

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

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

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

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

x^*₃ = ₃ (700-x^*₄) = ₃ (700) = 200 тыс. руб.

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

x*₂ = ₂ (700 - x*₄ - x*₃) = ₂ (500) = 300 тыс. руб.

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

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

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

x*₁ =200; x*₂ =300; x*₃ = 200; x*₄ = 0.

Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 20 + 37 + 27 = 84 тыс. руб.

f₁(x*₁) + f₂(x*₂) + f₃(x*₃) + f₄(x*₄) = z _max

Другим решением может служить распределение x*₁ =100; x*₂ =300; x*₃ = 200; x*₄ = 100. Оно получается, если в таблице 6 4-му предприятию выделить 100 тыс. руб. Прирост прибыли в этом случае составит также 84 тыс. руб (10 + 27 + 37 + 10).

Таблица 2

	x - x2	0 100 200 300 400 500 600 700
x2	F1(x - x2) f2(x2)	0 10 20 30 38 43 49 52
0		0 10 20 30 38 43 49 52
		13 23 33 43 51 56 62
		25 35 45 55 63 68
		37 47 57 67 75
		47 57 67 77
		55 65 75
		61 71
		66.

 

Таблица 3

x	0 100 200 300 400 500 600 700
F2(x)	0 13 25 37 47 57 67 77
` (x)	0 100 200 300 300 300 300 400

 

Таблица 4

	x - x3	0 100 200 300 400 500 600 700
x3	F2(x - x3) f3(x3)	0 13 25 37 47 57 67 77
0		0 13 25 37 47 57 67 72
		16 29 41 53 63 73 83
		27 40 52 64 74 84
		37 50 62 74 84
		44 57 69 81
		48 61 73
		50 63
		49.

 

Таблица 5

x	0 100 200 300 400 500 600 700
F3(x)	0 16 29 41 53 64 74 84
` (x)	0 100 100 100 100 200 200 200

 

Таблица 6

	x - x4	0 100 200 300 400 500 600 700
x4	F3(x - x4) f4(x4)	0 16 29 41 53 64 74 84
		41.

 

 

Задача о кратчайшем пути

 

Необходимо найти кратчайший путь между пунктами 0 и 8.

 

 

7 11

 

6 10 9

 

7 9

11 5 3

 

 

12 13

 

X₀ = 0

X₁ = +¥ = 3

X₂ = +¥ = 6

X₃ = +¥ = 12

X₄ = +¥ = 13

6 + 7

3 + 11

X₅ = +¥ = 15

3 + 12

X₆ = +¥ = 16

7 + 12

6 + 10

X₇ = +¥ = 18

13 + 5

X₈ = +¥ = 21

12 + 11

16 + 9

13 + 9

13 + 5 + 3

15 + 13

 

Таким образом, кратчайшее расстояние между двумя пунктами 0 и 8 = 6 + 7 + 5 + 3 = 21
9. Задача о назначениях

 

Исходные данные предложены самостоятельно. Необходимо решить задачу о назначениях.

Проект “изготовление мебели”

 

X₁ = 0

 

X₂ = +¥

3 часа

 

X₃ = +¥

2 часа

3 часа

 

X₄ = +¥

4 + 3 часа

 

X₅ = +¥

7 + 5 часов

 

На изготовление одной единицы мебели необходимо потратить 7 + 5 = 12 часов.

 

Составим матрицу рисков.

Имеем q1=0;q2=16;q3=32;q4=40. Следовательно, матрица рисков есть

 

 

Принятие решений в условиях полной неопределенности.

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

 

Правило Вальда (правило крайнего пессимизма). Рассматривая -e решение будем полагать, что на самом деле ситуация складывается самая плохая, т.е. приносящая самый малый доход . Выберем решение с наибольшим . Итак, правило Вальда рекомендует принять решение , такое что

Так, в вышеуказанном примере, имеем a1=0; a2= -6; a3=0; a4= -6. Теперь из этих чисел находим максимальное. Правило Вальда рекомендует принять 1-е или 3-е решение.

 

Правило Сэвиджа (правило минимального риска). При применении этого правила анализируется матрица рисков . Рассматривая -e решение будем полагать, что на самом деле складывается ситуация максимального риска

Выберем решение с наименьшим . Итак, правило Сэвиджа рекомендует принять решение , такое что

Так, имеем b1=22; b2=33; b3=0; b4=26 Теперь из этих чисел находим минимальное. Это – 0. Значит правило Сэвиджа рекомендует принять 3-е решение.

 

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

где . Значение выбирается из субъективных соображений. Если приближается к 1, то правило Гурвица приближается к правилу Вальда, при приближении к 0, правило Гурвица приближается к правилу "розового оптимизма". При правило Гурвица рекомендует:

½(0)+1/2*22=11

½(-6)+1/2*33=13,5

½(0)+1/2*0=0

½(-6)+1/2*26=10 2-е решение.

 

Государственный Университет Управления

 

Институт управления

в машиностроительной промышленности

 

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

 

Курсовая работа по дисциплине

“Прикладная математика”

 

 

Выполнил: студент группы маш II-3,

Шерстобитов А. В.

Проверил: Онищенко А. М.

 

Москва, 2001

Содержание

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

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

Задача о "расшивке узких мест производства" 6

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

4. Динамическое программирование. Распределение капитальных вложений 11

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

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

8. Задача о кратчайшем пути 18

9. Задача о назначениях 19

14. Матричная модель производственной программы предприятия 20

15. Принятие решений в условиях неопределенности 21

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

17. Задача формирования оптимального портфеля ценных бумаг 25