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

Посмотреть архив целиком

15



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

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


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



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




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

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





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

Курс 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-го вида на производственную программу

1+0х2+8х3+7х4316

Затраты ресурсов 2-го вида на производственную программу

1+2х2+5х34216

Затраты ресурсов 3-го вида на производственную программу

1+6х2+3х3+2х4199

Имеем

1+0х2+8х3+7х4316

1+2х2+5х34216 (1)

1+6х2+3х3+2х4199

где по смыслу задачи

х1≥0, х2≥0, х3≥0, х4≥0. (2)

Получена задача на нахождение условного экстремума. Для ее решения систему неравенств (1) при помощи дополнительных неизвестных х5, х6, х7 заменим системой линейных алгебраических уравнений

1+0х2+8х3+7х45=316 (I)

1+2х2+5х3+ х46=216 (II) (3)

1+6х2+3х3+2х47=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

Все ∆j0

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 наши затраты составят

1+3у2+5у3≥31

Аналогично, во 2-м столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции 2-го вида

2+6у3≥10

Аналогично, в 3-м столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции 3-го вида

1+5у2+3у3≥41

Аналогично, в 4-м столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции 4-го вида

12+2у3≥29

Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить

316у1+216у2+199у3

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

У=(у1, у2, у3)

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

f=316у1+216у2+199у3

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

1+3у2+5у3≥31

2+6у3≥10

1+5у2+3у3≥41

12+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у12+2у3-29)=0

Учитывая, что в решении исходной задачи х1>0, x3>0

Поэтому

1+3у2+5у3-31=0

1+5у2+3у3-41=0

Учтем, что 2-й ресурс был избыточным и, согласно теореме двойственности, его двойственная оценка равна нулю у2=0

Имеем систему уравнений

1+3у2+5у3-31=0

1+5у2+3у3-41=0

Решим систему:

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