Задачи 1,2,4,5

1. Для производства двух видов изделий A и B используется три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется 2 час, оборудование второго типа – 1 час, оборудование третьего типа – 3 часа. Для производства единицы изделия В оборудование первого типа используется 2 час, оборудование второго типа – 2 часа, оборудование третьего типа – 1 час. На изготовление всех изделий предприятие может использовать оборудование первого типа не более, чем 48 часа, второго типа не более, чем 38 часов, третьего типа не более, чем 45 часов. Прибыль от реализации готового изделия А составляет 2 денежных единиц, а изделия В – 3 денежных единиц. Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу графическим и аналитическим симплексным методом.

1) графический;

f(x)=2x1+3x2→max

{■(2x_1 +2x_2 ≤48@x_1 +2x_2 ≤38@3x_1 +x_2 ≤54@x_1 ,x_2 ≥0)┤

Строим на координатной плоскости границы области допустимых решений, которые являются прямыми. Закрашиваем область

допустимых решений в соответствии с неравенствами. Прямую 2x1+3x2=С двигаем в направлении градиента целевой

функции {2;3} до крайних точек области допустимых решений, где достигается наибольшее значение;

{■(2x_1 +2x_2 =48@x_1 +2x_2 =38)┤ ⇒ {■(x_1 =10@x_2 =14)┤ ⇒ x^* = (10;14) ;f (x^* ) =62→max

2) симплекс метод;

f(x)=2x1+3x2→max

{■(2x_1 +2x_2 ≤48@x_1 +2x_2 ≤38@3x_1 +x_2 ≤54@x_1 ,x_2 ≥0)┤

Сводим систему неравенств к системе уравнений, вводя новые переменные:

{■(2x_1 +2x_2 +x_3 =48@x_1 +2x_2 +x_4 =38@3x_1 +x_2 +x_5 =54@x_1 ,x_2 ,x_3 ,x_4 ,x_5 ≥0)┤

Переносим в симплекс таблицу коэффициенты системы уравнений, а коэффициенты целевой функции с противоположным знаками будут оценками. Выделяем синим цветом ведущий столбец с наименьшей отрицательной оценкой, а ведущую строку – с наименьшим отношение элемента опорного решения к элементу ведущего столбца. Общий элемент ведущих строки и столбца, выделенный красным, будет ведущим элементом. Делим элементы ведущей строки на ведущий элемент, с помощью элементарных преобразований делаем элементы ведущего столбца нулевыми кроме ведущего элемента, умножая и складывая строки ведущего элемента и остальных строк. Повторяем эти преобразования, пока есть отрицательные оценки;

X x1 x2 x3 x4 x5 x* ⇒ X x1 x2 x3 x4 x5 x* ⇒ X x1 x2 x3 x4 x5 x*

x3 2 2 1 0 0 48 x3 1 0 1 -1 0 10 x1 1 0 1 -1 0 10

x4 1 2 0 1 0 38 x2 1/2 1 0 1/2 0 19 x2 0 1 -1/2 1 0 14

x5 3 1 0 0 1 54 x5 5/2 0 0 -1/2 1 35 x5 0 0 -5/2 2 1 10

f -2 -3 0 0 0 0 f -1/2 0 0 3/2 0 57 f 0 0 1/2 1 0 62

x*=(10;14), F(x*)=62→max

2. Имеются три пункта отправления Ai однородного груза и пять пунктов Bi его назначения. На пунктах Ai, груз находится в количестве ai единиц соответственно. В пункты Bi требуется доставить соответственно bi единиц груза. Тарифы на перевозку груза между пунктами отправления и назначения приведены в матрице D. Составить план перевозок, при котором общие затраты на перевозку грузов будут минимальными. Указание: для решения задачи использовать методы минимальной стоимости и потенциалов.

A={50;30;70}; B={20;30;50;30;20};

C= (■(9&5&7&1&9@7&6&4&8&4@5&3&4&9&9))

∑^3_(i=1)▒A_i - ∑^5_(j=1)▒B_j =0⇒задача сбалансированная

Строим опорный план, используя метод северо-западного угла:

B1 B2 B3 B4 B5 Ai

A1 920 530 70 1 9 50

A2 7 6 430 8 4 30

A3 5 3 420 930 920 70

Bj 20 30 50 30 20 150

X_0 = (■(20&30&0&0&0@0&0&30&0&0@0&0&20&30&20))

F(X0)=20·9+30·5+0·7+30·4+20·4+30·9+20·9=980

Пусть u1=0.

u1+v1=9

u1+v2=5

u1+v3=7

u2+v3=4

u3+v3=4

u3+v4=9

u3+v5=9 ⇒ u1=0,u2=-3,u3=-3,

v1=9,v2=5,v3=7v4=12,v5=12, ⇒ α14=1-(0+12)=-11

α15=9-(0+12)=-3

α21=7-(-3+9)=1

α22=6-(-3+5)=4

α24=8-(-3+12)=-1

α25=4-(-3+12)=-5

α31=5-(-3+9)=-1

α32=3-(-3+5)=1

B1 B2 B3 B4 B5 Ai ⇒ B1 B2 B3 B4 B5 Ai

A1 920 530 7-0 1+ 9 50 A1 920 530 7 10 9 50

A2 7 6 430 8 4 30 A2 7 6 430 8 4 30

A3 5 3 4+20 9-30 920 70 A3 5 3 420 930 920 70

Bj 20 30 50 30 20 150 Bj 20 30 50 30 20 150

X_1 = (■(20&30&0&0&0@0&0&30&0&0@0&0&20&30&20))

F(X1)=20·9+30·5+0·1+30·4+20·4+30·9+20·9=980

Пусть u1=0.

u1+v1=9

u1+v2=5

u1+v4=1

u2+v3=4

u3+v3=4

u3+v4=9

u3+v5=9 ⇒ u1=0,u2=8,u3=8,

v1=9,v2=5,v3=-4v4=1,v5=1, ⇒ α13=7-(0-4)=11

α15=9-(0+1)=8

α21=7-(8+9)=-10

α22=6-(8+5)=-7

α24=8-(8+1)=-1

α25=4-(8+1)=-5

α31=5-(8+9)=-12

α32=3-(8+5)=-10

B1 B2 B3 B4 B5 Ai ⇒ B1 B2 B3 B4 B5 Ai

A1 9-20 530 7 1+0 9 50 A1 9 530 7 120 9 50

A2 7 6 430 8 4 30 A2 7 6 430 8 4 30

A3 5+ 3 420 9-30 920 70 A3 520 3 420 910 920 70

Bj 20 30 50 30 20 150 Bj 20 30 50 30 20 150

X_2 = (■(0&30&0&20&0@0&0&30&0&0@20&0&20&10&20))

F(X2)=30·5+20·1+30·4+20·5+20·4+10·9+20·9=740

Пусть u3=0.

u1+v2=5

u1+v4=1

u2+v3=4

u3+v1=5

u3+v3=4

u3+v4=9

u3+v5=9 ⇒ u1=-8,u2=0,u3=0,

v1=5,v2=13,v3=4v4=9,v5=9, ⇒ α11=9-(-8+5)=12

α13=7-(-8+4)=11

α15=9-(-8+9)=8

α21=7-(0+5)=2

α22=6-(0+13)=-7

α24=8-(0+9)=-1

α25=4-(0+9)=-5

α32=3-(0+13)=-10

B1 B2 B3 B4 B5 Ai ⇒ B1 B2 B3 B4 B5 Ai

A1 9 5-30 7 1+20 9 50 A1 9 520 7 130 9 50

A2 7 6 430 8 4 30 A2 7 6 430 8 4 30

A3 520 3+ 420 9-10 920 70 A3 520 310 420 9 920 70

Bj 20 30 50 30 20 150 Bj 20 30 50 30 20 150

X_3 = (■(0&20&0&30&0@0&0&30&0&0@20&10&20&0&20))

F(X3)=20·5+30·1+30·4+20·5+10·3+20·4+20·9=640

Пусть u3=0.

u1+v2=5

u1+v4=1

u2+v3=4

u3+v1=5

u3+v2=3

u3+v3=4

u3+v5=9 ⇒ u1=2,u2=0,u3=0,

v1=5,v2=3,v3=4v4=-1,v5=9, ⇒ α11=9-(2+5)=2

α13=7-(2+4)=1

α15=9-(2+9)=-2

α21=7-(0+5)=2

α22=6-(0+3)=3

α24=8-(0-1)=9

α25=4-(0+9)=-5

α34=9-(0-1)=10

B1 B2 B3 B4 B5 Ai ⇒ B1 B2 B3 B4 B5 Ai

A1 9 520 7 130 9 50 A1 9 520 7 130 9 50

A2 7 6 4-30 8 4+ 30 A2 7 6 410 8 420 30

A3 520 310 4+20 9 9-20 70 A3 520 310 440 9 9 70

Bj 20 30 50 30 20 150 Bj 20 30 50 30 20 150

X_4 = (■(0&20&0&30&0@0&0&10&0&20@20&10&40&0&0))

F(X4)=20·5+30·1+10·4+20·4+20·5+10·3+40·4=540

Пусть u3=0.

u1+v2=5

u1+v4=1

u2+v3=4

u2+v5=4

u3+v1=5

u3+v2=3

u3+v3=4 ⇒ u1=2,u2=0,u3=0,

v1=5,v2=3,v3=4v4=-1,v5=4, ⇒ α11=9-(2+5)=2

α13=7-(2+4)=1

α15=9-(2+4)=3

α21=7-(0+5)=2

α22=6-(0+3)=3

α24=8-(0-1)=9

α34=9-(0-1)=10

α35=9-(0+4)=5

Отрицательных оценок нет – найдено оптимальное решение.

X^* = (■(0&20&0&30&0@0&0&10&0&20@20&10&40&0&0)) ;F (X^* ) =540→min

4. Для двух предприятий выделено 900 единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от

x единиц средств, вложенных в первое предприятие, равен f1(x)=2x, а доход от y единиц средств, вложенных во второе предприятие, равен f2(y)=y. Остаток средств к концу года составляет g1(x)=0,1x для первого предприятия и g2(y)=0,3y для второго предприятия. Задачу решить методом динамического программирования.

Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.

Обозначим аk=хk+уk – средства, которые распределяются на k – ом шаге как сумма средств по предприятиям.

Суммарный доход от обоих предприятий на k – ом шаге: zk=f1(xk)+f2(ak-xk)=2xk+(ak-xk)=ak+xk

Остаток средств от обоих предприятий на k – ом шаге:

ak+1=g1(xk)+g2(ak-xk)=0,1xk+0,3(ak-xk)=0,3ak-0,2xk

Обозначим zk*(ak) – максимальный доход, полученный от распределения средств аk между двумя предприятиями с k – го шага до конца рассматриваемого периода. Рекуррентные соотношения Беллмана для этих функций:

z_4^* = max┬(0≤x_4 ≤a_4 ) 〖z_k 〗 = max┬(0≤x_4 ≤a_4 ) 〖(a_k +x_k )〗

z_k^* = max┬(0≤x_k ≤a_k ) 〖(z_k +a_(k+1) )〗 = max┬(0≤x_k ≤a_k ) 〖(a_k +x_k +z_(k+1)^* (0,3a_k -0,2x_k ))〗

Проведем оптимизацию, начиная с четвертого шага:

Оптимальный доход равен:

z_4^* (a_4 ) =2 a_4

3-й шаг:

z_3^* (a_3 ) = max┬(0≤x_3 ≤a_3 ) 〖(a_3 +x_3 +2(0,3a_3 -0,2x_3 ))〗 = max┬(0≤x_3 ≤a_3 ) 〖(1,6a_3 +0,6x_3 )〗 =2,2 a_3

2-й шаг:

z_2^* (a_2 ) = max┬(0≤x_2 ≤a_2 ) 〖(a_2 +x_2 +2,2(0,3a_2 -0,2x_2 ))〗 = max┬(0≤x_2 ≤a_2 ) 〖(1,66a_2 +0,56x_2 )〗 =2,22 a_2

1-й шаг:

z_1^* (a_1 ) = max┬(0≤x_1 ≤a_1 ) 〖(a_1 +x_1 +2,22(0,3a_1 -0,2x_1 ))〗 = max┬(0≤x_1 ≤a_1 ) 〖(1,666a_1 +0,556x_1 )〗 =2,232 a_1

Результаты оптимизации:

z_1^* (a_1 ) =2,232 a_1 ; x_1^* = a_1

z_2^* (a_2 ) =2,22 a_2 ; x_1^* = a_2

z_3^* (a_3 ) =2,2 a_3 ; x_1^* = a_3

z_4^* (a_4 ) =2 a_4 ; x_1^* = a_4

Определим количественное распределение средств по годам:

a1=a=900;

a2=0,3a1-0,2x1=90

a3=0,5a2-0,4x2=9

a4=0,5a3-0,4x3=0,9

x1=a4=0,9

Представим распределение средств в виде таблицы:

Предприятие|Год 1 2 3 4

1 900 90 9 0,9

2 900 9 0,9 0,9

При таком распределении средств за 4 года будет получен доход, равный z*=z*1=2,232∙900=2008,8

5. Построить диаграмму и найти максимальный поток и минимальный разрез.

(1;2)→4; (1;5)→7; (2;5)→9; (3;6)→15; (4;7)→7;

(5;3)→16; (5;4)→8; (5;7)→5; (6;4)→7

Шаг Путь min Разрез

1 1-5-4-7 7 {(1;5)}

2 1-2-5-7 4 {(4;7)}

max 12

{(1;5), (4;7)}