2.4. анализ решения злп на основе отчётов ms excel
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 единиц.
Определите оптимальное решение задачи для случая, когда вектор ресурсов задан в виде в -строки.
Определите интервалы изменения цен на каждую продукцию, при которых сохраняется оптимальный план.
продукции, чтобы сделать На сколько нужно снизить затраты каждого вида сырья на единицу производство нерентабельного изделия рентабельным?
 |
 |
Составьте рацион, содержащий не менее нужного количества указанных питательных веществ и имеющий минимальную стоимость.
Определите, все ли виды кормов входят в рацион, ценность дополнительной единицы каждого питательного вещества и его приоритет при решении задач уменьшения стоимости рациона.
Определите суммарную стоимостную оценку питательных веществ в единице каждого корма, использование какого вида корма нерентабельно.
Содержание какого из питательных веществ превышает заданный минимальный уровень и на сколько?
Определите максимально возможное уменьшение содержания каждого из питательных веществ в рационе, при котором структура рациона остается без изменений.
На сколько уменьшится стоимость рациона и используемое количество кормов при снижении минимального уровня потребления питательного вещества В до Z ед.
Определите интервал изменения цен на каждый вид корма, при котором сохраняется структура рациона.
Возможно ли сделать выгодным использование корма, не вошедшего в рацион.
На сколько увеличится стоимость рациона при принудительном включении в рацион 1 кг нерентабельного вида корма.
На сколько нужно снизить минимальный уровень потребления каждого из питательных веществ, чтобы уменьшить стоимость рациона на 10\%?.
 |
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):
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) | |
Обсуждение Исследование операций в экономикеКомментарии, рецензии и отзывы 2.4. анализ решения злп на основе отчётов ms excel: Исследование операций в экономике, И.Н. Мастяева, 2003 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Рекомендовано Учебно-методическим объединением по образованию в области статистики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 061700 «Статистика» и другим экономическим специальностям.
|