reforef.ru 1

Агентство по образованию Российской Федерации


Северо-Западный государственный заочный технический университет


КОНТРОЛЬНАЯ РАБОТА
По дисциплине «Математические основы теории систем»


Выполнила: Игонькина Н.С.

Курс:3

Семестр: 6

Факультет:ИСА А и У

Форма обучения: заочная

Специальность: 220201

Шифр:6420309032

Проверил: Пашкин В.Я.
Санкт-Петербург

2008 год

Задача1. Решить симплекс-методом следующую задачу линейного программирования

Z=2X1+3X2+0X3+6X4->max

2X1+3X2+3X3+2X4≤8

X1+2X2+3X3+5X4≤10

X i≥0; i=1,4

Признак оптимальности плана:

Целевая функция принимает max значение, когда все элементы целевой строки в столбцах свободных переменных положительно.

Алгоритм нахождения оптимального решения симплекс-метода:

  1. В симплекс-таблицу записывается основание матрицы- это коэффициенты при неизвестных в системе уравнений.


  2. Подсчитываются значения элементов целевой строки.

  3. Полученный опорный план проверяется на оптимальность, если план не оптимальный, то выбирается генеральный столбец, который показывает какая переменная переводится из свободной в базисную при переходе к новому опорному плану.
  4. Определяются элементы столбца Q. По наименьшему элементу в столбце выбирается ключевая строка. Она определяет переменную, которая переводится из базисной в свободную.


  5. Находим генеральный элемент

  6. Строится новая симплекс-таблица.

  7. Новые элементы бывшие в ключевой строке находятся делением прежних элементов на генеральный столбец.

  8. Новые элементы матрицы считаются по специальному общему правилу.

  9. Новый опорный план проверяется на оптимальность.

Перепишем исходную задачу в нормальной форме, не содержащую неравенств.


Z=2X1+3X2+0X3+6X4+0X5+0X6->max (1)

2X1+3X2+3X3+2X4+0X5=8 (2)

X1+2X2+3X3+5X4+0X6=10 (3)

X i≥0; i=1,4

Находим начальный опорный план.

X1= X2= X3= X4=0 тогда из (2) и (3) получим, X5=8, X6=10.

Для этого опорного плана запишем симплекс таблицу , в которой С –строка коэффициентов при переменных в целевой функции (1), Вх- столбец базисных переменных, А0-столбец свободных членов, А1-А4 –столбцы коэффициентов в (2) и (3) соответственно при переменных X1,….. ,X4. (см. Таблица1)


Таблица1.


 Сi

 C

0

2

3

0

6

0

0

Q




Bx

A0

A1

A2

A3

A4

A5

A6

 

0

X5

8

2

3

3

2

1

0

4

0

X6

10

1

2

2

5

0

1


2

 



0

-2

-3

0

-6

0

0

 


Элементы строки ∆ вычисляются по формуле:

j=СiAij-Cj

Где i, j –номера переменных и, соответственно строк и столбцов в симплекс-таблице, Aij-элемент таблицы, стоящий на пересечении i-ой строки и j-го столбца.

∆0= С5А506А600 =0*8+0*10-0=0


∆1= С5А516А611=0*2+0*1-2= -2

∆2= С5А526А622 =0*3+0*2-3= -3

∆3= С5А536А633 =0*3+0*2-0=0

∆4= С5А546А644 =0*2+0*5-6= -6

∆5= С5А556А655 =0*1+0*0-0=0

∆6= С5А66А666 =0*0+0*1-0=0
Поскольку строка ∆ симплекс-таблицы содержит отрицательные элементы , то решение не является оптимальным. Необходимо перейти к новой симплекс-таблице. Найдем разрешающий столбец и строку.

Q5=8/2=4; Q6=10/5=2 => Разрешающий элемент равен А64=5.

Таблица 2.


 Ci

 C

0

2

3

0

6

0

0

Q




Bx

A0

A1

A2

A3

A4

A5

A6

 

6

Х5

4

1,6

2,2

2,2

0

1

-0,4

0

0

Х4

2

1/5

2/5

2/5

1

0

1/5

2

 




24

7 3/5

10 1/5

13 1/5

-6

6

-2 2/5

 


При этом новые элементы для i=6 равны:

А60 = А60 / А64 = 10/5=2;

А61 = А61 / А64 = 1/5;

А62 = А62 / А64 = 2/5;

А63 = А63 / А64 = 2/5;

А64 = А64 / А64 = 5/5=1;

А65 = А65 / А64 = 0/5=0;

А66 = А66 / А64 = 1/5;

а новые элементы строки i=5 равны:

А50 = А50 - А60* A54/ А64 = 8-10*2/5=4;

А51 = А51 - А61* A54/ А64 = 2-1*2/5=1,6;

А52 = А52 - А62* A54/ А64 = 3-2*2/5=2,2;

А53 = А53 - А63* A54/ А64 = 3-2*2/5=2,2;


А54 = А54 - А64* A54/ А64 = 2-5*2/5=0;

А55 = А55 - А65* A54/ А64 =1-0*2/5=1;

А56 = А50 - А60* A54/ А64 = 0-1*2/5= -0.4;

Введя в базис переменную X4 вместо Х6 и заново вычислив строку ∆, получим новую симплекс-таблицу. (см. Таблицу 2)

∆0= С5А504А400 =6*4+6*0-0=24

∆1= С5А514А411=6*1.6+0*1/5-2=7 3/5

∆2= С5А524А422 =6*2.2+0*2/5-3= 10 1/5

∆3= С5А534А433 =6*2.2+0*2/5-0=13 1/5

∆4= С5А544А444 =6*0+0*1-6= -6

∆5= С5А554А456 =6*1+0*0-0=6

∆6= С5А564А465= 6*(-0.4)+0*1/5-0= - 2 2/5


Строка ∆ симплекс-таблицы содержит отрицательные элементы , то решение не является оптимальным.

Q5=4/0=0; Q6=2/1=2 => Разрешающий элемент равен А44=1.

Таблица 3.


 Ci

 C

0

2

3

0

6

0

0

Q




Bx

A0

A1

A2

A3

A4

A5

A6

 

6

Х4

4


1 3/5

2 1/5

2 1/5

0

1

- 2/5

-10

6

Х4

2

1/5

2/5

2/5

1

0

1/5

10

 



36

8 4/5

12 3/5

15 3/5

0

6

-1 1/5

 


При этом новые элементы для строки i=4 равны:

А40 = А40 / А44 = 2;

А41 = А41 / А44 = 1/5;

А42 = А42 / А44 = 2/5;

А43 = А43 / А44 = 2/5;


А44 = А44 / А44 = 1;

А45 = А45 / А44 = 0;

А46 = А46 / А44 = 1/5;

Новые элементы для строки i=5 равны:

А50 = А50 - А40* A54/ А44 = 4-2*0/1=4;

А51 = А51 - А41* A54/ А44 = 1,6-1/5*0/1=1 3/5;

А52 = А52 - А42* A54/ А44 = 2,2-2/5*0/1=2 1/5;

А53 = А53 - А43* A54/ А44 = 2,2-2/5*0/1=2 1/5;

А54 = А54 - А44* A54/ А44 = 0-1*0/1=0;

А55 = А55 - А45* A54/ А44 =1-0*0/1=1;

А56 = А50 - А46* A54/ А44 = -0,4-1/5*0/1= -2/5;

Введя в базис переменную X4 вместо Х5 и заново вычислив строку ∆, получим новую симплекс-таблицу. (см. Таблицу 3)


∆0= С4А404А400 =6*4+6*2-0=36

∆1= С4А414А411=6*1 3/5+6*1/5-2=8 4/5

∆2= С4А424А422 =6*2 1/5+6*2/5-3= 12 3/5

∆3= С4А434А433 =6*2 1/5+6*2/5-0=15 3/5

∆4= С4А444А444 =6*0+6*1-6= 0

∆5= С4А456А456 =6*1+0*6-0=6

∆6= С4А464А465= 6*(-2/5)+6*1/5-0= - 1 1/5
Строка ∆ симплекс-таблицы содержит отрицательные элементы, то решение не является оптимальным.

Q5=4/(-2/5)=-10; Q6=2/(1/5)=10 => Разрешающий элемент равен А46=1/5.

Таблица 4

Ci


 C

0

2

3

0

6

0

0

Q




Bx

A0

A1

A2

A3

A4

A5

A6

 

0

Х4

8

2

3

3

2

1

0

 

6

Х6

10

1

2

2

5

0

1

 

 



60

4

9

12

24

0

6


 
При этом новые элементы для строки i=4 равны:

А40 = А40 / А46 = 10;

А41 = А41 / А46 = 1/5;

А42 = А42 / А46 = 2/5 / (1/5)=2;

А43 = А43 / А46 = 2/5 / (1/5)=2;

А44 = А44 / А46 = 1/(1/5)=5;

А45 = А45 / А46 = 0;

А46 = А46 / А46 = 1;

Новые элементы для первой строки i=4 равны:

А40 = А40’ - А40* A46’/ А46 = 4-2* (-2/5)/(1/5)=8;

А41 = А41’ - А41* A46’/ А46 = 1 3/5-1/5*(-2/5)/(1/5)=2;

А42 = А42’ - А42* A46’/ А46 = 2 1/5-2/5*(-2/5)/(1/5)=3;

А43 = А43’ - А43* A46’/ А46 = 2 1/5-2/5*(-2/5)/(1/5)=3;

А44 = А44’ - А44* A46’/ А46 = 0-1*(-2/5)/(1/5)=2;


А45 = А45’ - А45* A46’/ А46 =1-0*(-2/5)/(1/5)=1;

А46 = А46 - А46* A46’/ А46 = -2/5-1/5*(-2/5)/(1/5)= 0;

Введя в базис переменную X4 вместо Х6 и заново вычислив строку ∆, получим новую симплекс-таблицу. (см. Таблицу 4)

∆0= С4А406А600 =0*8+6*10-0=36

∆1= С4А416А611=0*2+6*1-2=4

∆2= С4А426А622 =0*3+6*25-3= 9

∆3= С4А436А633 =0*3+6*2-0=12

∆4= С4А446А644 =0*2+6*5-6= 24

∆5= С4А456А656 =0*1+6*0-0=0

∆6= С4А466А665= 0*0+6*1-0= 6

Таблица 4 соответствует оптимальному решению. При этом целевая функция имеет значение z= ∆=60.


Задача 2. Методом динамического программирования решить задачу целочисленного программирования:

Z=X12+ X22->max

6X1+5X2≤30 (4)

X1, X2= 0,1,2…..

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

∆1(ξ)=max f1(x1)

f1(x1)= X12, Х1 (ξ) {0,1……[ ξ /А1}, где

[x]- целая часть числа х

А1=6-коэффициэнт при переменной в неравенстве

Сведем результаты к таблице 5,6.



Таблица 5


ξ

x1

f1(x1)

∆1(ξ)

ξ

x1

f1(x1)

∆1(ξ)

ξ

x1

f1(x1)

∆1(ξ)

0

0

 

0

18

0

0

 

28

0

0

 

1

0

0

0

 

1

1

 

 

1

1

 

2

0

0

0

 


2

4

 

 

2

4

 

3

0

0

0

 

3

9

9

 

3

9

 

4

0

0

0

19

0

0

 

 

4

16

16

5

0

0

0

 

1

1

 

26

0

0

 

6

0

0

 

 

2

4

 

 


1

1

 

 

1

1

1

 

3

9

9

 

2

4

 

7

0

0

 

20

0

0

 

 

3

9

 

 

1

1

1

 

1

1

 

 

4

16

16

8

0

0

 

 

2

4

 

27

0

0

 

 


1

1

1

 

3

9

9

 

1

1

 

9

0

0

 

21

0

0

 

 

2

4

 

 

1

1

1

 

1

1

 

 

3

9

 

10

0

0

 

 

2

4

 

 

4

16

16

 

1

1

1

 


3

9

9

28

0

0

 

11

0

0

 

22

0

0

 

 

1

1

 

 

1

1

1

 

1

1

 

 

2

4

 

12

0

0

 

 

2

4

 

 

3

9

 

 

1

1

 

 

3

9

9

 


4

16

16

 

2

4

4

23

0

0

 

29

0

0

 

13

0

0

 

 

1

1

 

 

1

1

 

 

1

1

 

 

2

4

 

 

2

4

 

 

2

4

4

 

3

9

9

 

3

9

 

14


0

0

 

24

0

0

 

 

4

16

16

 

1

1

 

 

1

1

 

30

0

0

 

 

2

4

4

 

2

4

 

 

1

1

 

15

0

0

 

 

3

9

 

 

2

4

 

 

1

1

 


 

4

16

16

 

3

9

 

 

2

4

4

25

0

0

 

 

4

16

 

16

0

0

 

 

1

1

 

 

5

25

25

 

1

1

 

 

2

4

 

 

 

 

 

 

2

4

4

 

3

9

 


 

 

 

 

17

0

0

 

 

4

16

16

 

 

 

 

 

1

1

 

 

 

 

 

 

 

 

 

 

2

4

4

 

 

 

 

 

 

 

 


Таблица 6

X2

30-5X2

∆1(30-5X2)


f2(x2)

f2(x2)+ ∆(30-5X2)

∆2

0

30

25

0

25

25

1

25

16

1

16




2

20

9

2

11





На этом шаге основное рекуррентное соотношение динамического программирования имеет вид:

∆2(ξ)=max [f2(x2)+ ∆( ξ-A2 X22) ], где

f2(x2)= X22 , А2=5, а ξ=В=25

Результаты расчетов по формуле сведем в таблицу 6, в которой графа ∆1 заполнена на основании данных таблицы 5.


Из таблицы 6 видно, что ∆2=25. Следовательно z=25. Поскольку величина ∆2=25 достигается при х2=0, то для переменной х2 оптимально значение х20 . При этом ∆1(25-5х2)= ∆1(30)=25. Причем это значение достигается х10=5
Задача 3. Методом ветвей и границ решить задачу целочисленного линейного программирования:
Z=X1+6X2->max

X1+4X2≤9

4X1+X2≤10

X1,X2=0,1,2….

Шаг 1. Вычисление границы

Пусть G- множество допустимых решений исходных задач. Заменим в этой задаче условие целочисленности на условие неотрицательности x1,x2≥0.


x1=9-4x2

4(9-4x2 )+x2=10

36-16x2+x2=10

-17x2=10-36

-17x2=-26

x2=1,53

x1=9-4*1.53=2.88

x1*=2.88; x2*=1.53

λ (G)= x1* + 6x2*=3+6*1.53=12.18

Решим графически задачу линейного программирования.






Поскольку в векторе х* =(х1*, х2*) обе компоненты не являются целочисленными, то ветвление можно осуществить по любой из них. Произведем ветвление по переменной х1.

Тогда множество G* будет разбито на непересекающиеся подмножества.


G1*={(x1,x2) |(x1,x2)} G*, x1 ≤ [x1*] =2

G2*={(x1,x2)| (x1,x2)} G*, x2 ≤ [x2*]+1 =3

Из рисунка 2 видно, что максимум целевой функции на множестве G* достигается в точке x* ( , ) с целочисленными координатами . При этом величина _________________

является рекордом для множества G1 для множества и следовательно, для множества G=G1G2.

z=z*= х10 = х20=





Задача 4. Графическим методом решить антагонистическую игру, заданную матрицей выигрыша первого игрока.

= | 0 2 2 3 |

| 0 3 3 2 |
Ожидаемые выигрыши первого игрока в ситуациях (x,f), где x=(x, 1-x1) – смешанная стратегия первого игрока, а j –чистая стратегия второго игрока, определяются выражениями:

M (x,1)=x111 + (1-x1)11=0*x1+ 0(1-x1)=0

M (x,2)=x112 + (1-x1)12=2*x1+3(1-x1)=2x1+3-3x1=3-x1

M (x,3)=x113 + (1-x1)13=2*x1+3(1-x1)=2x1+3-3x1=3-x1

M (x,4)=x114 + (1-x1)14=3*x1+(1-x1)*2=3x1+2-2x1=2+x1

которым соответствуют три прямые.






Для оптимальной стратегии второго игрока.