Курсовая работа по прикладной математике
Министерство общего и профессионального образования
Российской Федерации
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ
ИНСТИТУТ ЗАОЧНОГО ОБУЧЕНИЯ
Контрольная работа
по дисциплине «Прикладная математика»
Специальность Бухгалтерский учет и аудит
Курс 2-й
Группа БуиА-6-99/2
Студент
Студенческий билет №
ВАРИАНТ №25
Адрес |
|
|
|
| |
|
| |
|
« » мая 2001г.
Проверил:
____________________/ /
«___»_______________2001г.
Москва 2001г.
Задача №1. Линейная производственная задача.
Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов. Известны технологическая матрица А затрат любого ресурса на единицу каждой продукции, вектор В объемов ресурсов и вектор С удельной прибыли
4 0 8 7 316
А= 3 2 5 1 В= 216 С=(31, 10, 41, 29)
5 6 3 2 199
Найти производственную программу (х1, х2, х3, х4), максимизирующую прибыль
z=31х1+10х2+41х3+29х4
Затраты ресурсов 1-го вида на производственную программу
4х1+0х2+8х3+7х4≤316
Затраты ресурсов 2-го вида на производственную программу
3х1+2х2+5х3+х4≤216
Затраты ресурсов 3-го вида на производственную программу
5х1+6х2+3х3+2х4≤199
Имеем
4х1+0х2+8х3+7х4≤316
3х1+2х2+5х3+х4≤216 (1)
5х1+6х2+3х3+2х4≤199
где по смыслу задачи
х1≥0, х2≥0, х3≥0, х4≥0. (2)
Получена задача на нахождение условного экстремума. Для ее решения систему неравенств (1) при помощи дополнительных неизвестных х5, х6, х7 заменим системой линейных алгебраических уравнений
4х1+0х2+8х3+7х4+х5=316 (I)
3х1+2х2+5х3+ х4+х6=216 (II) (3)
5х1+6х2+3х3+2х4+х7=199 (III)
где дополнительные переменные имеют смысл остатков соответствующих ресурсов, а именно
х5 – остаток сырья 1-го вида,
х6 – остаток сырья 2-го вида,
х7 – остаток сырья 3-го вида.
Среди всех решений системы уравнений (3), удовлетворяющих условию неотрицательности
х1≥0, х2≥0, х3≥0, х4≥0, х5≥0, х6≥0, х7≥0 (4)
надо найти то решение, при котором функция
z=31х1+10х2+41х3+29х4
будет иметь наибольшее значение
Организуем направленный перебор базисных решений при помощи симплекс метода.
Из функции z(x) видно, что наиболее выгодно начать производство с 3-го ресурса.
Найдем ведущее уравнение:
bi 316 216 199 316
min ------- = ----- ----- ----- = -----
ai3>0 8 5 3 8
Примем I-е уравнение за ведущее. Решаем симплекс методом:
| С | Базис | Н | 31 | 10 | 41 | 29 | 0 | 0 | 0 | Поясне-ния |
х1 | х2 | х3 | х4 | х5 | х6 | х7 | ||||
| 0 | х5 | 316 | 4 | 0 | 8 | 7 | 1 | 0 | 0 | |
| 0 | х6 | 216 | 3 | 2 | 5 | 1 | 0 | 1 | 0 | |
| 0 | х7 | 199 | 5 | 6 | 3 | 2 | 0 | 0 | 1 | |
| ∆ | z0-z | 0-z | -31 | -10 | -41 | -29 | 0 | 0 | 0 | |
| 41 | х3 | 39,5 | 1/2 | 0 | 1 | 7/8 | 1/8 | 0 | 0 | |
| х6 | 18,5 | 1/2 | 2 | 0 | -27/8 | -5/8 | 1 | 0 | |
| 0 | х7 | 80,5 | 7/2 | 6 | 0 | -5/8 | -3/8 | 0 | 1 | |
| ∆ | z0-z | 1619,5 | -21/2 | -10 | 0 | 55/8 | 41/8 | 0 | 0 | |
| 41 | х3 | 28 | 0 | -6/7 | 1 | 54/56 | 10/56 | 0 | -1/7 | Все ∆j≥0 |
| 0 | х6 | 7 | 0 | 8/7 | 0 | -23/7 | -4/7 | 1 | -1/7 | |
| 31 | х1 | 23 | 1 | 12/7 | 0 | -10/56 | -6/56 | 0 | 2/7 | |
| ∆ | z0-z | 1861 | 0 | 8 | 0 | 5 | 4 | 0 | 3 |
0Оптимальная производственная программа:
х1=23, х2=0, х3=28, х4=0
Остатки ресурсов:
Первого вида – х5=0;
Второго вида – х6=7;
Третьего вида – х7=0
Максимальная прибыль zmax=1861
Обращенный базис Q-1
10/56 0 -1/7
Q-1= -4/7 1 -1/7
-6/56 0 2/7
х5х6х7
Базис Q
8 0 4
Q= 5 1 3
3 0 5
х3 х6 х1
Самопроверка.
10/56•8+0•5-1/7•3 10/56•0+0•1-1/7•0 10/56•4+0•3-1/7•5 1 0 0
Q-1 •Q= -4/7•8+1•5-1/7•3 -4/7•0+1•1-1/7•0 -4/7•4+1•3-1/7•5 = 0 1 0
-6/56•8+0•5+2/7•3 -6/56•0+0•1+2/7•0 -6/56•4+0•3+2/7•5 0 0 1
 |  |
10/56•316+0•216-1/7•199 28
Q-1 •B= -4/7•316+1•216-1/7•199 = 7
-6/56•316+0•216+2/7•199 23
Задача №2. Двойственная задача.
Предприниматель Петров, занимающийся производством других видов продукции, но с использованием 3-х таких же видов ресурсов, какие имеются у нас, предлагает нам продать ему по определенным ценам все имеющиеся у нас ресурсы и обещает заплатить у1 за каждую единицу 1-го ресурса
у2 за каждую единицу 2-го ресурса
у3 за каждую единицу 3-го ресурса.
В нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имеют вид
4 0 8 7 316
А= 3 2 5 1 В= 216 С=(31, 10, 41, 29)
5 6 3 2 199
для производства единицы продукции 1-го вида мы должны затратить, как видно из матрицы А 4 единицы ресурса 1-го вида, 3 единицы ресурса 2-го вида, 5 единиц ресурса 3-го вида.
В ценах у1, у2, у3 наши затраты составят
4у1+3у2+5у3≥31
Аналогично, во 2-м столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции 2-го вида
2у2+6у3≥10
Аналогично, в 3-м столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции 3-го вида
8у1+5у2+3у3≥41
Аналогично, в 4-м столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции 4-го вида
7у1+у2+2у3≥29
Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить
316у1+216у2+199у3
Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок
У=(у1, у2, у3)
Минимизирующий общую оценку всех ресурсов
f=316у1+216у2+199у3
при условии, что по каждому виду продукции суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции:
4у1+3у2+5у3≥31
2у2+6у3≥10
8у1+5у2+3у3≥41
7у1+у2+2у3≥29
При этом оценки ресурсов не могут быть отрицательными
у1≥0, у2≥0, у3≥0
На основании 2-й основной теоремы двойственности
Х=(х1, х2, х3, х4) и у=(у1, у2, у3)
Необходимо и достаточно выполнения условий
х1(4у1+3у2+5у3-31)=0
х2(2у2+6у3-10)=0
х3(8у1+5у2+3у3-41)=0
х4(7у1+у2+2у3-29)=0
Учитывая, что в решении исходной задачи х1>0, x3>0
Поэтому
4у1+3у2+5у3-31=0
8у1+5у2+3у3-41=0
Учтем, что 2-й ресурс был избыточным и, согласно теореме двойственности, его двойственная оценка равна нулю у2=0
Имеем систему уравнений
4у1+3у2+5у3-31=0
8у1+5у2+3у3-41=0
Решим систему:
4у1+5у3=31
у1=(31-5у3)/4
8((31-5у3)/4)+3у3=41
-7у3=-21
у1=(31-15)/4
откуда следует
у1=4, у3=3
Таким образом, получили двойственные оценки ресурсов
у1=4, у2=0, у3=3
Общая оценка всех ресурсов
f=316у1+216у2+199у3
f=1264+0+597=1861
Задача №2.1. Задача о «расшивке узких мест производства».
При выполнении оптимальной производственной программы 1-й и 3-й ресурсы используются полностью, образуя «узкие места производства». Их необходимо заказать дополнительно.
Пусть Т=(t1, 0, t3) – вектор дополнительных объемов ресурсов.
Так как мы предполагаем использовать найденные двойственные оценки ресурсов, то должно выполняться условие
Н+ Q-1Т≥0
Необходимо найти вектор
Т=(t1, 0, t3)
максимизирующий суммарный прирост прибыли
w=4t1+3t3
28 10/56 0 -1/7 t1 0
7 + -4/7 1 -1/7 · 0 ≥ 0
23 -6/56 0 2/7 t3 0
Предполагаем, что дополнительно можно получить не более 1/3 первоначального объема ресурса каждого вида
t1 316
0 ≤ 1/3 216
t3 199
где t1≥0, t3≥0
10/56t1-1/7t3≥-28
-4/7t1-1/7t3≥-7
-6/56t1+2/7t3≥-23
-10/56t1+1/7t3≤28
4/7t1+1/7t3≤7
6/56t1-2/7t3≤23
t1≤316/3, t3≤199/3
t1≥0, t3≥0
t1 | t3 | |
| I | -156,8 | 0 |
| I | 0 | 196 |
| II | 12,25 | 0 |
| II | 0 | 49 |
| III | 214,66 | 0 |
| III | 0 | -80,5 |
| IV | 105,33 | 0 |
| V | 0 | 66,33 |
Программа расшивки имеет вид
t1=0, t2=0, t3=49
и прирост прибыли составляет
w=4t1+3t3=3∙49=147
Сводка результатов приведена в таблице:
Сj | 31 | 10 | 41 | 29 | b | x4+i | yi | ti |
aij | 4 | 0 | 8 | 7 | 316 | 0 | 4 | 0 |
| 3 | 2 | 5 | 1 | 216 | 7 | 0 | 0 | |
| 5 | 6 | 3 | 2 | 199 | 0 | 3 | 49 | |
xj | 23 | 0 | 28 | 0 | 1861 | 147 | ||
∆j | 0 | 8 | 0 | 5 |
Задача №3. Транспортная задача линейного программирования.
Исходные данные:
31 40 41 49
45 4 5 8 6
60 3 2 5 1
65 5 6 3 2
Общий объем производства ∑аi=45+60+65=170 единиц продукции.
Потребителям требуется ∑bi=31+40+41+49=161 единиц продукции.
Так как продукции производится больше на 9 единиц, чем требуется потребителям, то мы имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом 9 единиц. Для нахождения первого базисного допустимого решения используем правило «северо-западного угла».
b1=31 | b2=40 | b3=41 | b4=49 | b5=9 | ||
a1=45 | 31 | 14 | * | p1=0 | ||
a2=60 | 26 | 34 | p2=-3 | |||
a3=65 | 7 | 49 | 9 | p3=-5 | ||
q1=4 | q2=5 | q3=8 | q4=7 | q5=5 |
Θ=9 z(x1)=31·4+14·5+26·2+34·5+7·3+49·2+9·0=535
b1=31 | b2=40 | b3=41 | b4=49 | b5=9 | ||
a1=45 | 31 | 5 | 9 | p1=0 | ||
a2=60 | 35 | 25 | * | p2=-3 | ||
a3=65 | 16 | 49 | 9 | p3=-5 | ||
q1=4 | q2=5 | q3=8 | q4=7 | q5=5 |
Θ=25 z(x2)=31·4+5·5+35·2+25·5+16·3+49·2+9·0=490
b1=31 | b2=40 | b3=41 | b4=49 | b5=9 | ||
a1=45 | 31 | 5 | 9 | p1=0 | ||
a2=60 | 35 | 25 | p2=-3 | |||
a3=65 | 41 | 24 | p3=-2 | |||
q1=4 | q2=5 | q3=5 | q4=4 | q5= |
z(x3)=31·4+5·5+35·2+25·1+41·3+24·2+9·0=415
Задача №4. Динамическое программирование. Распределение капитальных вложений.
Исходные данные:
xj | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 |
f1(xj) | 0 | 10 | 23 | 30 | 38 | 43 | 49 | 52 |
f2(xj) | 0 | 13 | 25 | 37 | 48 | 55 | 61 | 66 |
f3(xj) | 0 | 16 | 30 | 37 | 44 | 48 | 50 | 49 |
f4(xj) | 0 | 10 | 17 | 23 | 29 | 34 | 38 | 41 |
Для решения используем метод «северо-восточной диагонали».
-x2 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
x2 | 0 | 10 | 23 | 30 | 38 | 43 | 49 | 52 | |
| 0 | 0 | 0 | 10 | 23 | 30 | 38 | 43 | 49 | 52 |
| 100 | 13 | 13 | 23 | 36 | 43 | 51 | 56 | 62 | |
| 200 | 25 | 25 | 35 | 48 | 55 | 63 | 68 | ||
| 300 | 37 | 37 | 47 | 60 | 67 | 75 | |||
| 400 | 48 | 48 | 58 | 71 | 78 | ||||
| 500 | 55 | 55 | 65 | 78 | |||||
| 600 | 61 | 61 | 71 | ||||||
| 700 | 66 | 66 |
| 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
F2( ) | 0 | 13 | 25 | 37 | 48 | 60 | 71 | 78 |
x2( ) | 0 | 100 | 200 | 300 | 200 | 300 | 400 | 500 |
-x3 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
x3 | 0 | 13 | 25 | 37 | 48 | 60 | 71 | 78 | |
| 0 | 0 | 0 | 13 | 25 | 37 | 48 | 60 | 71 | 78 |
| 100 | 16 | 16 | 29 | 41 | 53 | 64 | 76 | 87 | |
| 200 | 30 | 30 | 43 | 55 | 67 | 78 | 90 | ||
| 300 | 37 | 37 | 50 | 62 | 74 | 85 | |||
| 400 | 44 | 44 | 57 | 69 | 81 | ||||
| 500 | 48 | 48 | 61 | 73 | |||||
| 600 | 50 | 50 | 63 | ||||||
| 700 | 49 | 49 |
| 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
F3( ) | 0 | 16 | 30 | 43 | 55 | 67 | 78 | 90 |
x3( ) | 0 | 100 | 200 | 200 | 200 | 200 | 200 | 200 |
-x4 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
x4 | 0 | 16 | 30 | 43 | 55 | 67 | 78 | 90 | |
| 0 | 0 | 0 | 90 | ||||||
| 100 | 10 | 88 | |||||||
| 200 | 17 | 84 | |||||||
| 300 | 23 | 78 | |||||||
| 400 | 29 | 72 | |||||||
| 500 | 34 | 64 | |||||||
| 600 | 38 | 54 | |||||||
| 700 | 41 | 41 |
x4*=x4(700)=0
x3*=x3(700-x4*)=x3(700)=200
x2*=x2(700-x4*-x3*)=x2(700-200)=x2(500)=300
x1*=700-x4*-x3*-x2*=700-0-200-300=200
x1=200
x2=300
x3=200
x4=0
Задача №5. Задача формирования оптимального портфеля ценных бумаг.
Исходные данные:
m0 | m1 | m2 | s1 | s2 |
| 2 | 4 | 6 | 7 | 8 |
Подобные работы: