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

Министерство общего и профессионального образования

Российской Федерации

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ

ИНСТИТУТ ЗАОЧНОГО ОБУЧЕНИЯ

Контрольная работа

по дисциплине «Прикладная математика»

Специальность Бухгалтерский учет и аудит

Курс 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

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

Оптимальная производственная программа:

х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

Программа