КУРСОВОЙ ПРОЕКТ учебной дисциплины ПРИКЛАДНАЯ МАТЕМАТИКА.

СОДЕРЖАНИЕ

ЗАДАНИЕ 1
ЗАДАНИЕ 2
ЗАДАНИЕ 4
ЗАДАНИЕ 8
ЗАДАНИЕ 15

КУРСОВОЙ ПРОЕКТ учебной дисциплины ПРИКЛАДНАЯ МАТЕМАТИКА.

x 1 (4y1 + 4y2 + 2y3 - 60) = 0 y1 (4x1 +2x2 +4x3 + x4 - 180) = 0
x 2 (2y1 + + 4y3 - 12) = 0 y2 (4x1 +2x2 + 2x4 - 160) = 0
x 3 (4y1 +2y2 + 3y3 - 44) = 0 y3 (2x1 +4x2 +3x3 - 109) = 0
x 4 ( y1 +2y2 - 17) = 0
Ранее было найдено, что в решении исходной задачи х1>0, x3>0. Поэтому
4y1 + 4y2 + 2y3 - 60 = 0
4y1 + 2y2 + 3y3 - 44 = 0
Если же учесть, что третий ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю
у3=0,
то приходим к системе уравнений
4y1 + 4y2 - 60 = 0
4y1 + 2y2 - 44 = 0
откуда следует
у1=7, у2=8.
Таким образом, получили двойственные оценки ресурсов
у1=7; у2=8; у3=0,(4)
причем общая оценка всех ресурсов равна 2540.
Заметим, что решение (4) содержалось в последней строке последней симплексной таблицы исходной задачи.
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
4*35 + 2*0 + 4*10 + 1*0 = 180 = 180
4*35 + 0*0 + 2*10 + 2*0 = 160 = 160
2*35 + 4*0 + 3*10 + 0*0 = 100 < 109
1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1>0).
2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y3 = 0.
Неиспользованный экономический резерв ресурса 3 составляет 9 (109-100).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.
Обоснование эффективности оптимального плана.
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
4*7 + 4*8 + 2*0 = 60 = 60
2*7 + 0*8 + 4*0 = 14 > 12
4*7 + 2*8 + 3*0 = 44 = 44
1*7 + 2*8 + 0*0 = 23 > 17
1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0).
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x2 = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (14 - 12 = 2) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.
3-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 3-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x3>0).
4-ое ограничение выполняется как строгое неравенство, т.е. ресурс 4-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x4 = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (23 - 17 = 6) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.
Влияние запасов ресурсов на оптимальное решение прямой задачи.
Величина двойственной оценки показывает, на сколько возрастает значение целевой функции F(x) при увеличении дефицитного ресурса на единицу.
Анализ устойчивости оптимального плана.
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.
Пусть каждое значение параметра целевой функции изменится на ∆ сi. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.
1-ый параметр целевой функции может изменяться в пределах:
где в знаменателе коэффициенты столбцов свободных переменных в оптимальном плане (коэффициенты структурных сдвигов, элементы обратной матрицы к базису оптимального плана).
-14 ≤ Δс1 ≤ 16
Таким образом, 1-параметр может быть уменьшен на 14 или увеличен на 16
Интервал изменения равен:
[60-14; 60+16] = [46;76]
Если значение c1 будет лежать в данном интервале, то оптимальный план не изменится.
2-ый параметр целевой функции может изменяться в пределах:
-16 ≤ Δс2 ≤ 28
Таким образом, 2-параметр может быть уменьшен на 16 или увеличен на 28
Интервал изменения равен:
[12-16; 12+28] = [-4;40]
Если значение c2 будет лежать в данном интервале, то оптимальный план не изменится.
Найдем интервалы устойчивости ресурсов.
1-ый запас может изменяться в пределах:
-20 ≤ Δb1 ≤ 9
Таким образом, 1-ый запас может быть уменьшен на 20 или увеличен на 9
Интервал изменения равен:
[180-20; 180+9] = [160;189]
2-ый запас может изменяться в пределах:
-18 ≤ Δb2 ≤ 20
Таким образом, 2-ый запас может быть уменьшен на 18 или увеличен на 20
Интервал изменения равен:
[160-18; 160+20] = [142;180]
В оптимальный план не вошла основная переменная x3, т.е. ее не выгодно использовать. Определим максимально возможное значение в рамках полученных двойственных оценок:
3-ый запас может изменяться в пределах:
0 ≤ x3 ≤ 10
ЗАДАНИЕ 4
Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб., по исходным данным, приведенным в приложении 3 (выделяемые суммы кратны 100 тыс.).
хj
100
200
300
400
500
600
700
f1 (xj)
28
42
51
57
61
64
66
f2 (xj)
20
27
30
31
32
32
33
f3 (xj)
8
26
37
47
53
58
61
f4 (xj)
5
20
29
36
41
45
47
Решение:
Динамическое программирование - это вычислительный метод для решения задач управления определенной структуры. Данная задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.
Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fi(xi) прирост мощности или прибыли на j-м предприятии, если оно получит xi рублей капитальных вложений. Требуется найти такое распределение (x1,x2, ... , xn) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли
z = f1(x1) + f2(х2) + ... + fn(xn)
при ограничении по общей сумме капитальных вложений
x1 + x2 + ... + xn = b
причем будем считать, что все переменные xj принимают только целые неотрицательные значения
xj = 0, или 1, или 2, или 3, ...
Функции fj(xj) мы считаем заданными, заметив, что их определение - довольно трудоемкая экономическая задача.
Воспользуемся методом динамического программирования для решения этой задачи.
Введем параметр состояния и определим функцию состояния. За параметр состояния  примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk() определим как максимальную прибыль на первых k предприятиях, если они вместе получают  рублей. Параметр  может изменяться от 0 до b. Если из  рублей k-е предприятие получит xk рублей, то каково бы ни было это значение, остальные  - xk рублей естественно распределить между предприятиями от первого до (К-1)-го так, чтобы была получена максимальная прибыль Fk-1( - xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1( - xk). Надо выбрать такое значение xk между 0 и , чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению
Fk()=max{fk(xk) + Fk-1(-xk)}
0  xk  
для k = 2, 3, 4, ... , n . Если же k=1, то
F1() = f1()
Рассмотрим конкретный пример. Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 1, где, например, число 58 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 58 тыс. руб.
Таблица I
хj
100
200
300
400
500
600
700
f1 (xj)
28
42
51
57
61
64
66
f2 (xj)
20
27
30
31
32
32
33
f3 (xj)
8
26
37
47
53
58
61
f4 (xj)
5
20
29
36
41
45
47
Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями F1( - x2) = f1(- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение . Заполняем таблицу 3.
Продолжая процесс, табулируем функции F3(), () и т.д. В табл. 6 заполняем только одну диагональ для значения = 700. Наибольшее число на этой диагонали:
Zmax = 109 тыс. руб.,
причем четвертому предприятию должно быть выделено
х*4 = 4 (700) = 0 тыс. руб.
На долю остальных трех предприятий остается 700 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено
x*3 = 3 (700-x*4) = 3 (700) = 400 тыс. руб.
Продолжая обратный процесс, находим
x*2 = 2 (700 - x*4 - x*3) = 2 (300) = 100 тыс. руб.
На долю первого предприятия остается
x*1 = 700 - x*4 - x*3 - x*2 = 200 тыс. руб.
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:
x*1 =200; x*2 =100; x*3 = 400; x*4 = 0.
Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 109 тыс. руб.
Проверим выполнение равенства
f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = z max
42+20+47=109
Таблица 2
 - x2
0 100 200 300 400 500 600 700
x2
F1( - x2)
f2(x2)
0 28 42 51 57 61 64 66
0 28* 42 51 57 61 64 66
100
20
20 48* 62* 71* 77 81 84
200
27
27 55 69 78* 84* 88*
300
30
30 58 72 81 87
400
31
31 59 73 82
500
32
32 60 74
600
32
32 60
700
33
33 .
Таблица 3

0 100 200 300 400 500 600 700
F2()
0 28 48 62 71 78 84 88
()
0 0 100 100 100 200 200 200
Таблица 4
 - x3
0 100 200 300 400 500 600 700
x3
F2( - x3)
f3(x3)
0 28 48 62 71 78 84 88
0 28* 48* 62* 71 78 84 88
100
8
8 36 56 70 79 86 92
200
26
26 54 74* 88* 97 104
300
37
37 65 85 99* 108
400
47
47 75 95 109*
500
53
53 81 101
600
58
58 86
700
61
61 .

Таблица 5

0 100 200 300 400 500 600 700
F3()
0 28 48 62 74 88 99 109
()
0 0 0 0 200 200 300 400
Таблица 6
 - x4
0 100 200 300 400 500 600 700
x4
F3( - x4)
f4(x4)
0 28 48 62 74 88 99 109
109*
100
5
104
200
20
108
300