Имя материала: Исследование операций в экономике

Автор: И.Н. Мастяева

2.4. анализ решения злп на основе отчётов ms excel

 

Рассмотрим следующую ЗЛП:

 

f (x) =7,5х1+3х2+6х3+12х4—»max 2хі+х2+0,5х3+4х4 < 2400 х1+5х2+3х3 < 1200

3хі+6х3+х4 < 2000

Хі,2,3,4 ^0.

 

Начнём с отчёта результатов. Приведём его вид:

|ДІ     В    |       С         |           D         I           Е          |           F          |           G         |           Н         L

 

1

Целевая ячейка (Максим

 

 

 

 

7

Ячейка

Имя

Исходно

Результат

 

 

в

JGJ4

ЦФ

0,000

7884,296

 

 

9 10 11

Изменяемые ячейки

 

 

 

 

12

Ячейка

Имя

Исходно

Результат

 

 

13

JBJ4

продуктА

0,000

8,800

 

 

14

JCI4

продуктВ

0,000

148,760

 

 

15

JDJ4

продукте

0,000

152,066

 

 

16

JEI4

продукти

0,000

543,802

 

 

17 16 19

Ограничения

 

 

 

 

20

Ячейка

Имя

Значение

формула

Статус

Разница

21

JFJ12

ограничение!

2400,000 $F$12<=$H$12

связанное

0

22

JFJ13

ограничение!

1200,000 JF$13<=$H$13

связанное

0

23

JFJ14

ограничение!

I    2000,000 $F$14<=$H$14

связанное

0

24

ЇВЇ4

продуктА

0,000 JBt4>=0

связанное

0,000

25

JCJ4

продуктВ

146,760 JC(4>=0

не связан.

148,760

27

JDI4

продукте

152,066 IDt4>=0

не связан.

152,066

JEJ4

продукти

543,802 JEt4>=0

не связан.

543,802

 

Единственное, что здесь следует прокомментировать, это статус ресурсов. Т.к. все ограничения на ресурсы являются связанными, то это говорит о том, что все ресурсы были использованы. Другими словами, все ресурсы являются дефицитными.

I     |Д|    В    |        С        |      D      |      Е      |           F          |        G        |        Н        I      I |

7          Результ.   Нормир.    Целевой     Допустимое Допустимое

8          Ячейка            Имя     значение стоимость Коэффициент Увеличение Уменьшение

1Г    $Bt4     продуктА          8,800        -0,062         7,5  0,061983471        1Е+30

Ю_      КІА     продуктВ           148,760         0,000                   3              7,5 0,391304348

jj_        $Dt4     продукте           152,866         0,000                   6             31,8 0,178571429

Г2_    ЦЕН     продуктР        543,802           0,000   12        1,5 0,135135135

14        Ограничения

15        Результ.   Теневая   Ограничение Допустимое Допустимое

16        Ячейка            Имя     значение     Цена     Правая часть Увеличение Уменьшение

ТГ        $F$12    ограничение!     2400,000         2,628               2400            1840 2193,333333

ГВ_    HFS13    ограничение!!     1200,000 0,074   1200   10966,66667 782,6086957

^9_    $Ft14    ограничение!!!    2000,000    0,744   2000    1500    920

Рассмотрим отчёт по устойчивости:

Нормированная стоимость (часто, редуцированная стоимость, от английского: cost reduction - уменьшение затрат) представляет собой дополнительные двойственные переменные. Они показывают, насколько по модулю уменьшится целевая функция при принудительном выпуске единицы данной продукции. В нашем примере нормированная стоимость по продукту А не равна нулю. Следовательно, если мы будем принудительно выпускать единицу продукта А, то целевая функция уменьшится на 0,062. Другими словами, выпуск продукта А является нерентабельным (неприбыльным).

Допустимое увеличение показывает, насколько максимально можно увеличить коэффициент целевой функции (цену продукта), чтобы структура оптимального плана осталась прежней. Допустимое уменьшение, наоборот, показывает, насколько можно максимально уменьшить коэффициент ЦФ, чтобы осталась прежней структура оптимального плана. Например, в нашей задаче, чтобы выпуск продукта А оставался нерентабельным, максимально допустимое увеличение его цены составляет приблизительно 0.06. Допустимое же уменьшение представляет собой огромное число. Это понятно, т.к., ещё больше уменьшив цену нерентабельного продукта, сделать его рентабельным невозможно.

Теневая цена в отчётах Excel представляет собой двойственные переменные. Они показывают, как изменится целевая функция при изменения запаса ресурса на единицу. Понятно, что если ресурс использован полностью, то теневая цена этого ресурса положительна. Например, если мы увеличим запас ресурса I на единицу, то ЦФ возрастёт на 2,628 (ресурс I является самым приоритетным). Допустимое увеличение и уменьшение показывают границы, в которых могут изменяться ресурсы, чтобы структура оптимального решения, т.е. номенклатура выпускаемой продукции, остались без изменений.

Рассмотрим последний отчёт - отчёт по пределам:

 

 

А| В

С I

D ІЕ

F

G |Н

I

J I

к I

4

5

 

 

 

 

 

 

 

 

7

Ячейка

Имя

значение

 

 

 

 

 

І

SGJ4

ЦФ

7884,298

 

 

 

 

 

11

 

Изменяемое

 

Нижний

Целевое

Верхний

Целевое

 

12

Ячейка

Имя

значение

предел

результат

предел

результат

 

13

ЇВЇ4

продукгА

0,000

0,000

7884,233

0,000

7884,298

 

14

ICJ4

продукгВ

148,700

0,000

7438,017

148,760

7884,298

 

15

ШИ

продукте

152,066

0,000

6971,901

152,066

7884,298

 

16

ЇЕЇ4

продуктО

543,802

0,000

1358,673

543,802

7884,298

 

 

 

В отчёте указаны значения ЦФ при выпуске данного типа продукции на нижнем и верхнем пределах. Так, значение ЦФ 6971,901 соответствует тому, что продукт С не выпускается.

Отчёты Excel обеспечивают всей необходимой информацией для проведения полного анализа линейной модели.

Домашнее задание 2. 1.

 

Решить с помощью MS Excel следующие задачи (варианты 1-5, 610).

1-5.Для приготовления четырех видов продукции (A, B, C, D) используют три вида сырья. Ресурсы сырья, норма его расхода на единицу продукции и цена продукции заданы в соответствующей таблице.

Определите план выпуска продукции из условия максимизации его стоимости.

Определите статус, ценность каждого ресурса и его приоритет при решении задачи увеличения запаса ресурсов.

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

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

На сколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?

На сколько можно снизить запас каждого из ресурсов, чтобы это не привело к уменьшению прибыли?

Определите изменение стоимости продукции и количество выпускаемых изделий при увеличении второго вида сырья на Z единиц.

Определите оптимальное решение задачи для случая, когда вектор ресурсов задан в виде в -строки.

Определите интервалы изменения цен на каждую продукцию, при которых сохраняется оптимальный план.

продукции, чтобы сделать На сколько нужно снизить затраты каждого вида сырья на единицу производство нерентабельного изделия рентабельным?

На сколько нужно изменить запас каждого из дефицитных ресурсов, чтобы прибыль возросла на 20\%?

6-і0.Из 4 видов кормов необходимо составить рацион, в состав которого должно входить не менее ві ед. вещества А, в2 ед. вещества В и в3 ед. вещества С. Количество единиц вещества, содержащегося в і кг корма каждого вида, указано в соответствующей таблице. В ней же приведена цена і кг корма каждого вида.

Составьте рацион, содержащий не менее нужного количества указанных питательных веществ и имеющий минимальную стоимость.

Определите, все ли виды кормов входят в рацион, ценность дополнительной единицы каждого питательного вещества и его приоритет при решении задач уменьшения стоимости рациона.

Определите суммарную стоимостную оценку питательных веществ в единице каждого корма, использование какого вида корма нерентабельно.

Содержание какого из питательных веществ превышает заданный минимальный уровень и на сколько?

Определите максимально возможное уменьшение содержания каждого из питательных веществ в рационе, при котором структура рациона остается без изменений.

На сколько уменьшится стоимость рациона и используемое количество кормов при снижении минимального уровня потребления питательного вещества В до Z ед.

Определите интервал изменения цен на каждый вид корма, при котором сохраняется структура рациона.

Возможно ли сделать выгодным использование корма, не вошедшего в рацион.

На сколько увеличится стоимость рациона при принудительном включении в рацион 1 кг нерентабельного вида корма.

На сколько нужно снизить минимальный уровень потребления каждого из питательных веществ, чтобы уменьшить стоимость рациона на 10\%?.

6.

9.

і0.

2.5. Двойственный симплекс-метод (Р-метод)

Пример 2.9. Рассмотрим следующую ЗЛП:

 

min(2Xi + 4Х2 )

Х1 + Х2 > 3

Х1 + 3 Х2 > 6 Х1 + 2 Х2 < 3

Хі,2 > 0

 

Приведем рассматриваемую ЗЛП к каноническому виду

 

max (-2 Х1 -4 Х2 )

Х1 +   Х2 - S1 = 3

Х1 + 3 Х2 - S2 = 6 Х1 + 2 Х2 - S3 = 3

X, > 0,      j = ГД,    S, > 0,    j =1,3.

 

(2.28)

или

max (-2 Х1 -4 Х2 )

3 Х1 -   Х2 + S1 = - 3

4 Х1 - 3 Х2 + S2 = -6

Х1 + 2 Х2+ S3 = 3

 

 

(2.29)

 

> 0,      j = 1,2,    S, > 0,    i = 1,3. Рассмотрим расширенную матрицу системы линейных уравнений

(2.29):

 

 

(-3

-1

1

0

0

- 31

P (°) =

- 4

-3

0

1

0

- 6

 

v 1

2

0

0

1

3,

 

Матрица P(0) содержит единичную подматрицу порядка 3 и , следовательно, определяет базисное решение

An«0) = (-3; -6; 3);      N (0)= (3; 4; 5)

системы уравнений , причем Cn(0) =( 0,0,0). Так как элементы ( n + 1 = 6 )-го столбца матрицы системы P(0) не являются неотрицательными, то она не является К-матрицей ЗЛП. Вычислим симплекс-разности матрицы P(0):

Подпись: неотрицательными, то базисное решение AN"' = (-3; -6; 3) не являющееся планом ЗЛП, является «лучшим», чем оптимальный план.A(f = (Cn(0),а?) - С, =-Cj > 0,      j = 1,5

7

Так    как    все    симплекс-разности матрицы то   базисное  решение   XN(0) =

 

 

P

 

(0)

 

являются

 

При решении задачи симплекс-методом текущее базисное решение является опорным планом, но неоптимальным. Эти соображения позволяют построить метод решения определенного класса ЗЛП. В этом методе, называемом двойственным симплекс-методом, на каждой итерации обеспечивается выполнение условия оптимальности текущего базисного решения, не являющегося планом. Критерием окончания процесса итераций является получение опорного плана (неотрицательных свободных членов системы уравнений), который будет являться и оптимальным.

 

Определение P-матрицы ЗЛП.

 

Определение. Р-матрицей КЗЛП будем называть расширенную матрицу системы линейных уравнений, равносильной исходной системе, содержащую единичную подматрицу порядка m на месте n первых столбцов, все симплекс разности которой неотрицательны.

Очевидно, что всякая Р-матрица ЗЛП определяет некоторое базисное решение системы уравнений (2.29) (см.пример 2.9)

Определение. Базисное решение системы линейных уравнений (2.29), определяемое Р-матрицей, называется псевдопланом ЗЛП.

 

Условия перехода от одной P-матрицы ЗЛП к другой.

 

Пусть известна Р-матрица P(S) ЗЛП (2.28), определяющая псевдоплан

—        —(S)   (S)

Xn<s)= b  ; N

Условия перехода от матрицы P(S) к матрице      P(S+1) составляют

содержание теоремы і.

Теорема 1. Пусть bS )< 0 и в l -й строке матрицы            P( S) есть хотя бы

один отрицательный элемент. Тогда одного шага метода Жордана-Гаусса можно построить новую Р-матрицу P(м), выбрав направляющий элемент из условия

д( s ) А(5)

°{S) =—7^ = min—(2 30) - a7)    *& - of) (2.30)

Су<0

Замечание 1. Если в матрице P нет b( S )< 0, то определяемый ею псевдоплан является решением ЗЛП.

Теорема 2. Пусть ЦS )< 0 и в 1-й строке матрицы P( S) нет ни одного

отрицательного элемента. Тогда множество планов Р ЗЛП (2.28) пусто.

Замечание 2. При переходе от матрицы P( S) к матрице P(S+і) целевая функция изменяется в соответствии с формулой

(S)

f( XN(S+1)) = f ( XN(S)) + d(S)bS = f ( XN(S)) +   bf (2.3і)

UIK откуда следует, что

f ( Xn(s+1)) < f ( Xn(s)), (2.32) так как ЪS)< 0 и aK) < 0. Из неравенства (2.32) следует, что при

переходе от одного псевдоплана к другому значение целевой функции f (x) не возрастает.

Алгоритм Р-метода.

 

Будем считать, что известна исходная Р-матрица P(0) задачи линейного программирования, определяющая исходный псевдоплан

X^0) = (Ъ(0),Ъ20),...,ъ<°>) ,

N(0) = (N(0), N 20),..., Ni0)).

 

В методе последовательного уточнения оценок последовательно

строят   Р-матрицы   P(1), P(2).., P(S),    ...    задачи линейного

программирования, пока не получат Р-матрицу задачи линейного программирования, определяющую ее оптимальный план.

Рассмотрим алгоритм S-й итерации метода последовательного уточнения оценок. В начале S-й итерации имеем Р-матрицу P( S-1) задачи линейного программирования, определяющую псевдоплан

             — (S-1)          (S-1)

XN(S-1)= Ъ    , N . Шаг 1. Найдем номер l из условия

Ъ( S-1) = min Ъ( S

1<i < m

Шаг 2. Если ЪS-1) > 0, то псевдоплан

             —(S-1)           (S-1)

Xn{ s-1)= Ъ1    , N является оптимальным опорным планом, а

f ( Xn(s-1) ) = (CNS-1), Xn(s-1)) _ есть     оптимальное   значение  линейной   формы   f (x), иначе переходим к шагу 3. Шаг 3. Если

a(S-1) > 0,   j = ,

то задача линейного программирования не имеет решения ( множество планов Р пусто), иначе переходим к шагу 4.

Шаг 4. Вычисляем для столбцов aj    матрицы P(S-1) (j * N(si = 1,

2, .. .,m) симплекс-разности A(S-1) и находим номер К из условия

А(S-1) Г А(5-1)

Направляющий элемент на S-й итерации метода есть элемент Шаг 5. Вычисляем компоненты вектора N :

a

(S-1)

1K

NS) = N(S-1), i = 1, m , i * і , NS) = K

Шаг 6. Производим один шаг метода Жордана-Гаусса с направляющим элементом  a'K-1). Вычисляем    элементы Р-матрицы

P(S) методом Жордана-Гаусса. Присваиваем переменной алгоритма S значение S+1 и переходим к шагу 1.

Решение    задач Р-методом.

 

Так как компоненты псевдоплана Xn(x> =( 3/2, 3/2, 3/2) являются неотрицательными, то Xn(1> является оптимальным опорным планом ЗЛП (2.28). Итак,

Х*=( 3/2, 0, 3/2, 0, 3/2) и min f (Х)=3. Пример 2.10. Решим ЗЛП:

max f (x) = - Х1 + 2Х2 -2 Х1 +   Х2 > 2

Х1 + 2 Х2 < 4 (2.33) Х1 + 4 Х2 > 4

Х1,2 >0

Приведем рассматриваемую ЗЛП к каноническому виду max f (Х)= (- Х1 + 2 Х2 )

- 2 Х1 +  Х2 - S1 = 2

Х1 + 2 Х2 + S2 = 4

Х1 + 4 Х2 - S3 = 4

Xj > 0,    j = 1,2,   s, > 0,   i = 1,3.

или

max f (X)= (- Х1 + 2 Х2 )

(2.34)

2 Х1 - Х2 + S1 = - 2

Х1 + 2 Х2 + S2 = 4

i = 1,3.

- Х1 - 4 Х2 + S3 = - 4

Xj > 0,    j = 1,2,   s, > 0,

Расширенная матрица

ґ 2   - і   і   0    0   - 2^

Л(0) =    і    2   0   і      0 4

v- і    4   0   0   і   - 4у

системы линейных уравнений (3.42) не являются Р-матрицей рассматриваемой ЗЛП, так как

( 2)       (- Г)

А(0)=(0, 0, 0)

+ і = і > 0 , А(20)=(0, 0, 0)

2 = -2 < 0.

v 4У

Следовательно, к решению ЗЛП (3.4і) не применим Р-метод.

Пример 2.іі.

min f (x) = ( 6 Хі + 3Х2 ) -3 Хі +   Х2 > і 2 Хі - 3 Х2 > 2

Хі,2 > 0

j =і,2.

Решение. Приведем задачу к каноническому виду f(Х)= (- 6 Хі - 3 Х2 ) -- max 3 Хі -   Х2 + Sl = - і - 2 Хі + 3 Х2 + S2 = - 2

Xj > 0,    j = ід,   Sj > 0,

(0)

Так как расширенная матрица

P

( 3   - і   і   0   - і)

- 2    3   0   і   - 2

 

(2.35)

системы линейных уравнений рассматриваемой задачи является Р-матрицей ( А(і0) = 6 >0; А(20) = 3 >0 ), то задачу можно решить Р-методом. Решение задачи ведем в симплексной таблице.

 

 

 

 

 

-6

-3

0

0

N(s)

C - «

C N

 

X N

al(s)

a2(s)

a3(s)

a4(s)