Выполнение теоремы об оценке. Подготовка исходной симплексной таблицы к проведению анализа устойчивости двойственных оценок

Страницы работы

5 страниц (Word-файл)

Фрагмент текста работы

Аннотация лекции. Лекция посвящена теории двойственности в линейном программировании. Рассмотрен пример решения сопряженных задач и проиллюстрировано выполнение третьей теоремы двойственности.

5.6.4 Выполнение теоремы об оценке

В условиях задачи сказано, что недельный рацион должен содержать не менее 4, но не более 6 г кальция; не менее 110 г белка; не более 25 г клетчатки; и этой смеси должно быть ровно 500 г. Предположим, что эти величины могут меняться. Чтобы узнать, на сколько при этом изменится оптимальная стоимость рациона, в соответствии с третьей теоремой двойственности надо воспользоваться теневыми ценами y1-5, которые соответствуют ограничениям прямой задачи. Но для этого вначале следует провести анализ устойчивости теневых цен.

Обозначим изменение минимального содержания кальция b1;  максимального - ∆b2; минимального содержания белка - b3; максимального содержания клетчатки - b4, а массы смеси – b5 (все эти величины измеряются в граммах). Теперь в таблице 17 вместо свободных членов (b1, b2; b3; b4; b5) следует подставить свободные члены (b1 + ∆b1, b2 + ∆b2; b3 + ∆b3; b4 + ∆b4; b5 + ∆b5), т.е. (4 + ∆b1, 6 + ∆b2; 44 + ∆b3; 25 + ∆b4; 0,5 + ∆b5). 

Однако, если мы просто заполним диапазон ячеек электронной таблицы D3:D7 этими выражениями, программа Microsoft Excel не сможет осуществить никаких вычислений над ними, поскольку эти ячейки станут текстовыми. Чтобы избежать этого, вставим перед столбцом Е еще пять столбцов. Теперь столбец свободных членов будет занимать 6 столбцов электронной таблицы (D, E, F, G, H, I). В столбце E запишем коэффициент, который будет умножен на b1, в столбце F – коэффициент при b2, и т.д., в столбце I – коэффициент при b5, а в D – то слагаемое в выражении для свободного члена, которое ни на что не умножается (т.е. прежнее значение свободного члена). Результат представлен в таблице 22. 

Теперь новые значения свободных членов, т.е. новый столбец B, записанный в диапазоне D3:I7 электронной таблицы, необходимо подвергнуть тем же линейным преобразованиям, которым подвергались ограничения прямой задачи в таблицах 17-19. Для этого нужно выделить диапазон ячеек D8:D37 и скопировать его на диапазон Е8:I 37. В результате этого новые столбцы симплексных таблиц будут пересчитаны по тем же формулам, что и столбец D. Результаты вычислений приведены в последней строке таблицы 22 и в таблице 23. Заголовки столбцов в таблице 23 отредактированы.

Таблица 22 – Подготовка исходной симплексной таблицы к проведению анализа устойчивости двойственных оценок

A

B

C

D

E

F

G

H

I

J

K

L

M

N

1

0

0

0

0

0

2

N

xб

cб

B

∆b1

∆b2

∆b3

∆b4

∆b5

x1

x2

x3

x4

x5

3

1

2

3

4

5

у1 x5 у2 x7 у3

1

0

1

0

1

4

6

44

25

0,5

1

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

1

380

380

0

0

1

1

1

90

20

1

2

2

50

80

1

-1

0 0

0

0

0

1 0

0

0

4

5

6

7

8

m+1

48,5

1

0

1

0

1

381

92

53

-1

0

Из таблицы 23 видно, что во второй симплексной таблице теперь базисная искусственная переменная у1 = 3,511 + b1 - 0,011b3 (см. строку 10 электронной таблицы); а не

3,511, как в таблице 17. Базисная переменная x5 = 5,511 + ∆b2 - 0,011∆b3 (см. строку 11 электронной таблицы); а не 5,511, как в таблице 17, и т.д. 

Оптимальный план прямой задачи примет вид Х* = (0,011 - 0,011∆b3 + ∆b5; 0,489 + + 0,011∆b3; 0; 0,711 - ∆b1 - 4,211∆b3 + 380∆b5; 1,289 + ∆b2 + 4,211∆b3 - 380∆b5; 0; 15,222 -

- 0,022∆b3 + ∆b4), оптимум будет равен 7,378 + 0,122∆b3 + 4∆b5

Таблица 23 – Анализ устойчивости двойственных оценок

A

B

C

D

E

F

G

H

I

J

K

L

9

N

xб

cб

B

∆b1

∆b2

∆b3

∆b4

∆b5

x1

x2

x3

10

1

2

3

4

5

у1 x5 x2 x7 у3

1

0

0

0

1

3,511

5,511

0,489

15,222

0,011

1

0

1

0

0

0

-0,011

-0,011

0,011

-0,222

-0,011

0

0

0

1

0

0

0

0

0

1

380

380

0

0

1

0

0

1

0

0

1,444

1,444 0,556

68,889

0,444

11

0

0

0

0

12

13

14

15

m+1

3,522

1

0

-0,022

0

1

381

0

1,889

16

N

xб

cб

B

∆b1

∆b2

∆b3

∆b4

∆b5

x1

x2

x3

17

1

2

3

4

5

x1 x5 x2 x7 у3

0

0

0

0

1

0,009 2

0,489

15,222

0,002

0,003

-1

0

0

-0,003

0

1

0

0

0

0

0

0,011

-0,222

0

0

0

1

0

0

0

0

0

1

1

0

0

0

0

0

0

1

0

0

0,004 0

0,556

68,889

0,441

18

19

20

21

-0,011

22

m+1

0,002

-0,003

0

-0,011

0

1

0

0

0,441

23

4

15

40

24

N

xб

cб

B

∆b1

∆b2

∆b3

∆b4

∆b5

x1

x2

x3

25

1

2

3

4

5

x1 x5 x2 x7 х3

4

0

15 0

40

0,009 2

0,487

14,93

0,004

0,003 -1

0,003

0,41

-0,006

0

1

0

0

0

0

0

0,025

1,51

-0,025

0

0

0

1

0

-0,009 0

-1,261

-156,34

2,269

1

0

0

0

0

0 0

1

0

0

0

0

0

0

1

26

27

28

29

30

m+1

7,505

-0,179

0

-0,629

0

71,830

0

0

0

31

N

xб

cб

B

∆b1

∆b2

∆b3

∆b4

∆b5

x1

x2

x3

32

1

2

3

4

5

x1 x5 х2 x7 х4

4

0

15

0

0

0,011

1,289

0,489

15,222

0,711

0

0

0 0

-1

0

1

0

0

0

-0,011

4,211

0,011

-0,222

-4,211

0

0

0

1

0

1

-380

0

0

380

1

0

0

0

0

0

0

1

0

0

0,444

-167,444

0,556

68,889

167,444

33

34

35

36

37

m+1

7,378

0

0

0,122

0

4

0

0

-29,889

Полученный ответ будет иметь смысл лишь в том случае, если значения всех переменных будут неотрицательны (т.е. последняя таблица будет допустимой). Поэтому необходимо проверить знак базисных переменных x1,  x5,  х2,  x7,  х4; т.е. определить, при каких изменениях свободных членов они будут неотрицательны. Составим систему неравенств:

0,011 - 0,011∆b3 + ∆b5 ≥ 0

0,489 + 0,011∆b3 ≥ 0

0,711 - ∆b1 - 4,211∆b3 + 380∆b5 ≥ 0

1,289 + ∆b2 + 4,211∆b3 - 380∆b5 ≥ 0

15,222 - 0,022∆b3 + ∆b4 ≥ 0

Чтобы решить эту систему, вначале предположим, что меняется только минимальное содержание кальция, т.е. первый свободный член. Тогда ∆b2  = ∆b3  = ∆b4 = ∆b5 = 0, и система примет вид:

0,011 ≥ 0

0,489 ≥ 0

0,711 - ∆b1 ≥ 0

1,289 ≥ 0

15,222 ≥ 0

Отсюда b1 ≤ 0,711. В первоначальном варианте исходных данных b1 = = 4. Следовательно, двойственная оценка y1 = 0 будет устойчивой лишь при норме мини-

мального содержания кальция от любого значения

Похожие материалы

Информация о работе