Исследование операций в экономике
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
>
.
Строка А4:
, , , ,
.
Строка А6 остается без изменений, т.к. там и так .
Получили еще одно решение задачи: х1 = х5 = 0, т.к. векторов А1, А5 нет в базисе первой итерации, и х2 = 5, х3 = 3, х4 = 11 х6 = 21, т.к. векторы А2, А3, А4 и А6 находятся в базисе и им соответствуют значения плана В (5; 3; 11; 21), значит, задача обладает новым опорным планом Х=(0; 5; 3; 11; 0; 21).
Рассчитаем строку оценок для каждого столбца А1, А2, А3, А4, А5, А6:
?1 = 0*1+ 0*2+3*0+0*3 - 2 = -2
?2 = 0*0+ 0*0+3*1+0*0 - 3 = 0
?3 = 0*1+ 0*0+3*0+0*0 - 0 = 0
?4 = 0*0+ 0*1+3*0+0*0 - 0 = 3
?5 = 0*(-3)+ 0*(-1)+3*1+0*0 - 0 = 0
?6 = 0*0+ 0*0+3*0+0*1 - 0 = 0
Найденный опорный план Х=(0; 5; 3; 11; 0; 21) не является оптимальным, так как среди оценок есть отрицательные. Переход к новому опорному плану осуществим, введя в базис новой симплекс-таблицы (итерация II) вектор А1, имеющий наименьшую отрицательную оценку ?1 = - 2.
Определим вектор, выходящий из базиса нулевой симплекс-таблицы:
,
т.е. вектор А3 следует вывести из базиса.
Строка А3 будет направляющей строкой, столбец А1 - направляющим столбцом, и на пересечении их будет находиться разрешающий элемент а31 = 1. В новой симплекс-таблице (итерация II) в базисе место вектора А3 занимает вектор А1, а векторы А2, A4 и А6 остаются на своих местах. Столбец А1, соответствующий направляющему столбцу, записывается всегда так: на месте разрешающего элемента пишется единица, а все остальные элементы этого столбца - нули. Заполнение столбцов А2, А3, А4, А5, А6 и В производим с помощью формул (а31 = 1 - разрешающий элемент).
№ итерацииБазисcjПлан230000Оценка QciА1А2А3А4A5A6IIА1231010-30А40500-21505/5А2350100105/1А601200-309112/9F(X)=2*3+3*5=21-101000
Получили еще одно решение задачи: х3 = х5 = 0, т.к. векторов А3, А5 нет в базисе первой итерации, и х1 = 3, х2 = 5, х4 = 5, х6 = 12, т.к. векторы А1, А2, А4 и А6 находятся в базисе и им соответствуют значения плана В (3; 5; 5; 12), значит, задача обладает новым опорным планом Х=(3; 5; 0; 5; 0; 12).
Рассчитаем строку оценок для каждого столбца А1, А2, А3, А4, А5, А6:
?1 = 2*1+ 0*0+3*0+0*0 - 2 = 0
?2 = 2*0+ 0*0+3*1+0*0 - 3 = 0
?3 = 2*1+ 0*(-2)+3*0+0*(-3) - 0 = 1
?4 = 2*0+ 0*1+3*0+0*0 - 0 = 0
?5 = 2*(-3)+ 0*5+3*1+0*9 - 0 = -6+3= -3
?6 = 2*0+ 0*0+3*0+0*1 - 0 = 0
Найденный план Х=(3; 5; 0; 5; 0; 12) не является оптимальным, так как среди оценок есть отрицательные. Переход к новому опорному плану осуществим, введя в базис новой симплекс-таблицы (итерация III) вектор А5, имеющий наименьшую отрицательную оценку ?5 = - 3.
Определим вектор, выходящий из базиса нулевой симплекс-таблицы:
,
т.е. вектор А4 следует вывести из базиса. Строка А4 будет направляющей строкой, столбец А5 - направляющим столбцом, и на пересечении их будет находиться разрешающий элемент а25 = 5.
В новой симплекс-таблице (итерация III) в базисе место вектора А4 занимает вектор А5, а векторы А1, A2 и А6 остаются на своих местах. Столбец А5, соответствующий направляющему столбцу, записывается всегда так: на месте разрешающего элемента пишется единица, а все остальные элементы этого столбца - нули. Заполнение столбцов А1, А2, А3, А4, А6 и В производим с помощью формул (а25 = 5 - разрешающий элемент).
№ итерацииБазисcjПлан230000Оценка QciА1А2А3А4A5A6IIА12610-1/53/500А50100-2/51/510А234012/5-1/500А603003/5-9/501F(X)=2*6+3*4=24004/53/500
Получили еще одно решение задачи: х3 = х4 = 0, т.к. векторов А3, А4 нет в базисе первой итерации, и х1 = 6, х2 = 4, х5 = 1, х6 = 3, т.к. векторы А1, А2, А5 и А6 находятся в базисе и им соответствуют значения плана В (6; 4; 1; 3), значит, задача обладает новым опорным планом Х=(6; 4; 0; 0; 1; 3).
Рассчитаем строку оценок для каждого столбца А1, А2, А3, А4, А5, А6:
?1 = 2*1+ 0*0+3*0+0*0 - 2 = 0
?2 = 2*0+ 0*0+3*1+0*0 - 3 = 0
?3 = 2*(-1/5)+ 0*(-2/5)+3*2/5+0*(3/5) - 0 = 4/5
?4 = 2*3/5+ 0*1/5+3*(-1/5)+0*(-9/5) - 0 = 0
?5 = 2*0+ 0*1+3*0+0*0 - 0 = -6+3= 0
?6 = 2*0+ 0*0+3*0+0*1 - 0 = 0
Новый план Х=(6; 4; 0; 0; 1; 3) - оптимальный, так как в строке оценок ?j нет отрицательных значений.
Находим оптимум целевой функции:
max f() = 2 x1 + 3x2 = 2*6 + 3*4 = 24.
Найдем двойственные оценки.
Расширенная матрица коэффициентов при неизвестных в системе ограничений исходной задачи аij и свободных членов bi; коэффициенты целевой функции:
Транспонируя данную матрицу, получим коэффициенты для системы ограничений двойственной задачи:
В результате получим искомую двойственную задачу:
Для нахождения оценок у1, у2, у3, y4 используем вторую теорему двойственности.
Проверим, как удовлетворяется система функциональных ограничений оптимальным планом
Поскольку третье и четвертое ограничение в (*) выполняется как строгое неравенство, то у3 =0 и y4=0. Так как х1>0, х2> 0, то оба неравенства из двойственной задачи выполняются как равенства:
,
,
Т.е.
Вычислим значение целевой функции двойственной задачи:
Z(1, 0, 1, 0)= 18*4/5+16*3/5+5*0+21*0=(72+48)/5=24.
оптимум линейный программирование двойственный симплексный
По первой теореме двойственности мы можем утверждать, что действительно найдены оптимальные значения двойственных переменных.
Экономико-математический анализ оптимальных решений базируется на свойствах двойственных оценок.
. Величина двойственной оценки того или иного ресурса показывает насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на одну единицу (двойственные оценки измеряют эффективность малых приращения объемов ресурсов в конкретных условиях данной задачи).
В задаче увеличение ресурса I вида на 1 ед. привело бы к росту максимальной суммы прибыли на