Контрольная работа по предмету "Прикладная математика"

№1 Задача ЛП

Предприятие может производить 4 вида продукции (продукция 1,2,3,4) при использовании 3-х видов ресурсов (ресурс I,II,III).

Известен вектор объемов ресурсов:

      128

В=  130

      142

 

Известна техническая матрица затрат ресурсов:

 

         2 4 5 3

А=     3 0 4 1

         3 5 0 2 

 

Известна удельная прибыль для каждого вида продукции:

 

С= (34 32 28 36)

 

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

 

 

Пусть х1, х2, х3, х4 – количество продукции 1,2,3,4.

Очевидно, что х1,2,3,4≥0

Затраты ресурсов не должны превышать имеющихся объемов:

Для ресурса I:

2х1+4х2+5х3+3х4 ≤ 128

Для ресурса II:

3x1+…+4x3+x4 ≤ 130

Для ресурса III:

3х1+5х2+…+2х4 ≤ 142

Условие максимальности прибыли

Z= 34x1+32x2+28x3+36x4 → max

 

 

Математическая модель имеет вид:

Z= 34x1+32x2+28x3+36x4 → max

2х1+4х2+5х3+3х4 ≤ 128

3x1+…+4x3+x4 ≤ 130

3х1+5х2+…+2х4 ≤ 142

х1,2,3,4 ≥ 0

х1,2,3,4 - ?

Это задача Линейного программирования, приведем ее к основному виду, для этого добавим к каждому неравенству балансовую переменную х5, х6, х7. Модель примет вид:

Z= 34x1+32x2+28x3+36x4 → max

2х1+4х2+5х3+3х4+х5 = 128

3x1+…+4x3+x4+х6 = 130

3х1+5х2+…+2х4+х7 = 142

х1,2,3,4,5,6,7  ≥ 0

х1,2,3,4,5,6,7 - ?

 

 

 

 

 

 

 

 

 

 

 

 

 

Эта задача решается методом симплекс-таблицы

хб	h	x1     x2    x3    x4     x5       x6      x7	Примечание
x5 x6 x7	128 130 142	2       4       5       3       1         0        0    3       0       4       1       0         1        0    3       5       0       2       0         0        1	х4 - в базис min(128/3, 130/1, 142/2), min 128/3
Z	0	-34     -32    -28     -36    0         0        0	x5 – из базиса
x4 x6 x7	128/3 262/3 170/3	2/3    4/3     5/3     1     1/3        0        0 7/3   -4/3     7/3     0    -1/3        1        0 5/3    7/3   -10/3    0    -2/3        0        1	х1 – в базис min(128/3:2/3,262/3:7/3,170/3:5/3) min 34(170/3:5/3)
Z	1536	-10     16     32       0     12         0         0	x7 – из базиса
x4 x6 x1	20 8 34	0      2/5      3       1     3/5        0     -2/5   0    -23/5     7       0     3/5        1     -7/5   1      7/5     -2       0    -2/5        0      3/5
Z	1876	0     30       12      0        8        0         6

 

Оптимальный план найдет, т.к. все числа в нижней строке не отрицательны.

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

х1* = 34, х2* = 0, х3* = 0, х4* = 20

Максимальная прибыль

Z= 1876

Остатки ресурсов х5*=0, х6*=8, х7*=0

Узкие места – ресурс I и ресурс II

 

 

 

 

 

 

Проверка

h=Q-1В

             3/5  0  -2/5       128

Q-1В =  3/5   1  -7/5   *  130

           -2/5   0   3/5       142

 

3/5*128+0*130+(-2/5)*142=20

3/5*128+1*130+(-7/5)*142=8

-2/5*128+0*130+3/5*142=34

Проверка выполнена успешно.

 

Графическое решение 

Продукция х2, х3 не производится по оптимальному плану, вычеркнем из таблицы соответствующие два столбца:

 

34  32  28  36

2    4    5    3  128

3    0    4    1  130

3    5    0    2   142

 

Модель примет вид:

Z= 34x1+36x4 → max

2х1+3х4 ≤ 128

3x1+x4 ≤ 130

3х1+2х4 ≤ 142

х1,4  ≥ 0

х1,4 - ?

 

 

 

1)2х1+3х4=128

х1=0       х4=42 2/3

х1=64     х4=0

 

2) 3х1+х4=130

х1=0             х4=130

х1=43 1/3     х4=0

 

3) 3х1+2х4=142

х1=0       х4=71

х1=47 1/3     х4=0

 

 

 

 

 

 

 

 

График 1

 

 

 

 

 

 

Точка В – крайняя (образована прямыми 1 и 3)

1. 2х1+3х4=128 │*3
2. 3х1+2х4=142 │*2

6х1+9х4=384

6х1+4х4=284

                 5х4=100

                  х4=20

         2х1+3*20=128

          х1=34

    z=34*34+36*20=1876

Ответ:  х1*=34, х4*=20, z=1876

 

 

 

 

 

 

 

 

№2 Двойственная задача и задача о расшивке «узких мест»

 

Исходные данные

34  32  28  36

2    4    5    3  128

3    0    4    1  130

3    5    0    2  142

 

1. Задача двойственная задаче №1 имеет вид:

2y1+3y2+3y3 ≥ 34

4y1+…+5y3 ≥ 32

5y1+4y2+… ≥ 28

3y1+y2+2y3 ≥ 36

 

При этом

f=128y1+130y2+142y3 при условии что

y1,2,3 ≥ 0

y1,2,3  - ?

 

Из второй теоремы двойственности следует, что

х1(2y1+3y2+3y3 - 34)=0        y1(2x1+4x2+5x3+3x4-128)=0

х2(4y1+…+5y3 – 32)=0         y2(3x1+…+4x3+x4-130)=0

х3(5y1+4y2+… - 28)=0          y3(3x1+5x2+…+2x4-142)=0

х4(3y1+y2+2y3 – 36)=0

 

Из первой задачи известно, что х1>0 и х2>0, тогда

2y1+3y2+3y3 - 34=0

3y1+y2+2y3 – 36=0

 

Также известно, что ресурс II избыточен, тогда y2=0. Получаем систему:

2y1+3y3 - 34=0

3y1+2y3 – 36=0

 

2y1+3y3 - 34=0│*3

3y1+2y3 – 36=0│*2

6y1+9y3 - 102=0

6y1+4y3 – 72=0

       5y3 – 30=0

        y3=6

2y1+3*6 - 34=0

y1=8

Двойственные оценки ресурсов

y1*=8   y2*=0   y3*=6

 

2. Задача о расшивке «узких мест»

При выполнении оптимальной производственной программы первый и третий ресурс используются полностью, т.е. образуют "узкие места производства"

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

W=8t1+6t3

Вектор Т (t1,0,t3), t2=0 т.к. y2=0

20          3/5  0  -2/5            t1          0

8       *    3/5  1  -7/5     *      0     *    0

34         -2/5  0   3/5            t3          0

 

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

 

t1             128

0    ≤ 1/3  130

t3             142  , причем t1 ≥ 0, t3 ≥ 0

 

 

 

-3/5t1+2/5t3 ≤ 20

-3/5t1+7/5t3 ≤ 8

2/5t1-3/5t3 ≤ 34

t1 ≤ 128/3   t3 ≤ 142/3

 

Задача решается графически

1) -3/5t1+2/5t3 = 20

t1=0     t3=50

t1= -33 1/3     t3=0

 

2) -3/5t1+7/5t3 = 8

t1=0     t3=5 5/7

t1= -13 1/3     t3=0

 

3) 2/5t1-3/5t3 = 34

t1=0     t3= -56 2/3

t1= 85     t3=0

 

График 2

 

 

Точка В – крайняя

t1=128/3=42 2/3

 -3/5*128/3+7/5t3 = 8

t3=24

 

 

Программа расшивки имеет вид:

t1=42 2/3; t2=0; t3 = 24

Прирост прибыли W=8*128/3+6*24=485 1/3

 

 

 

 

 

 

Сводка результатов

cj	34	32	28	36	bi	x4+i	yi	ti
	2	4	5	3	128	0	8	42 2/3
aij	3	0	4	1	130	8	0	0
	3	5	0	2	142	0	6	24
xj	34	0	0	20	1876			485 1/3
Dj	0	30	12	0

 

 

 

№4 Задача распределения капитальных вложений

 

Производственное объединение состоит из 4-х предприятий (n=4), общая сумма капитальных вложений равно 700 тыс. руб. (b=700), выделяемые предприятиям суммы кратны 100 тыс. руб. Значение функции fj(xj) приведены в таблице 1.

Табл. 1.

хj	0	100	200	300	400	500	600	700
f1(xj)	0	12	20	26	37	41	44	45
f2(xj)	0	16	27	37	44	48	50	56
f3(xj)	0	10	16	21	24	27	29	30
f4(xj)	0	11	19	25	29	32	33	33

 

 

 

 

 

 

 

 

 

 

 

 

Таб. 2

x - x2		0	100	200	300	400	500	600	700
x2	F1(x-x2) F2(x2)	0	12	20	26	37	41	44	45
0	0	0	12	20	26	37	41	44	45
100	16	16*	28*	36	42	53	57	60
200	27	27	39*	47	53	64	68
300	37	37	49*	57*	63	74
400	44	44	56	64*	70*
500	48	48	60	68
600	50	50	62
700	56	56

 

 

Табл. 3.

x	0	100	200	300	400	500	600	700
F2(x)	0	16	28	39	49	57	64	70
x2(x)	0	100	100	200	300	300	400	400

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Табл. 4

x - x3		0	100	200	300	400	500	600	700
х3	F2(x-x3) F3(x3)	0	16	28	39	49	57	64	70
0	0	0	16*	28*	39*	49	57	64	70
100	10	10	26	38	49*	59*	67*	74*
200	16	16	32	44	55	65	73
300	21	21	37	49	60	70
400	24	24	40	52	63
500	27	27	43	55
600	29	29	45
700	30	30