Создан заказ №1914044
6 апреля 2017
Построить двойственную задачу Если прямая задача разрешима то найти оптимальное решение двойственной задачи
Как заказчик описал требования к работе:
здравствуйте. нужно сделать задания по предмету методы оптимальных решений придерживаясь правил решения автора данного учебника. задания: 45, 145, 545, 645, 745.
Фрагмент выполненной работы:
Построить двойственную задачу. Если прямая задача разрешима, то найти оптимальное решение двойственной задачи, применяя первую теорему двойственности. Сравнить значения функций, соответствующих оптимальным планам X*=(x1,x2,…,xn) и Y*=(y1,y2,…,yn).
3. Решить графическим методом двойственную задачу и, применяя условия дополняющей нежесткости, найти оптимальное решение прямой задачи. Сравнить результат с результатом, полученным симплекс-методом. (работа была выполнена специалистами author24.ru)
-10 -6 42 => min
-5 -2 7 ≥ 9
2 3 -6 ≤ 7
Решение:
Перейдем от неравенств к равенствам, прибавляя к левым частям неотрицательные дополнительные переменные x4 и x5 (напомним, что дополнительным переменным в целевой функции соответствуют нулевые коэффициенты):
min→fx=-10x1-6x2+42x3+Mx6
-5x1-2x2+7x3-x4=92x1+3x2-6x3+x5=7
xj≥0, j=1,5
Преобразованную систему ограничений запишем в векторной форме:
A1x1+A2x2+A3x3+A4x4+A5x5=B,
где А1=-52, А2=-23, А3=7-6, А4=-10, А5=01, В=97
Исходный единичный базис состоит из векторов А4, А5; ему соответствует опорный план
X0=(x1=0, x2=0,x3=0, x4=-1, x5=1)
Составляем симплекс-таблицу для первой итерации (таблица 1.3). В шапке таблицы расположены коэффициенты целевой функции: с1=-10, с2=-6, с3=42, с4=0, с5=0. В столбец «i» запишем номера строк 1, 2, m+1).
Базисные векторы А6, А5 находятся в столбце «АБ», причем базисный вектор занимает ту строку, в которой находится его единица в единичной базисной матрице. В столбец «СБ» занесем коэффициенты целевой функции при базисных переменных с4=0, с5=0. В столбцах «АБ» и «СБ» m+1-я строка не заполняется.
В рабочей части таблицы первые две строки заполняются исходными данными. В столбец «B» запишем базисные компоненты опорного плана - x4=-1, x5=1. Столбцы «Aj» (j=1,5) заполним коэффициентами разложения j –го вектора по векторам базиса.
Вычислим текущее значение функции f0=СБ, X0=0*(-1)+0*1=0 и поместим его в m+1-ю строку столбца «B». Остальные столбцы m+1-й строки заполним оценками:
γ1=СБ, X1-c1=0*1+0*3+10=10
γ2=СБ, X2-c2=0*-2+0*3+6=6
γ3=СБ, X3-c3=0*-6+0*7-42=-42
γ4=СБ, X4-c4=0*1+0*0-0=0
γ5=СБ, X5-c5=0*0+0*1-0=0
Из уравнений выражаем искусственные переменные:
x6=9+5x1+2x2-7x3+x4которые подставим в целевую функцию:
Fx=-10x1-6x2+42x3+M(9+5x1+2x2-7x3+x4)→min
или
Fx=-10+5Mx1+-6+2Mx2+42-7Mx3+Mx4+9M→min
Таблица 1.3
i AБ СБ В -10 -6 42 0 0 0
А1 А2 А3 А4 А5 А6
1 А6 0 9 -5 -2 7 -1 0 1
2 А5 0 7 2 3 -6 0 1
m+1
9M 10-5M 6-2M -42+7M -M 0 0
После заполнения таблицы 1.3 опорный план проверяем на оптимальность. Для этого просматриваем элементы m+1-й строки.
Как видим, для данного опорного решения есть отрицательные оценки: γ1=7, γ2=-6. Решение не оптимально. В столбцах с отрицательными оценками имеются положительные коэффициенты разложения, поэтому нет оснований утверждать, что целевая функция не ограничена сверху на допустимом множестве.
Переходим к новому опорному решению (первая итерация). В базис вводим вектор A1, т. к. он соответствует наименьшей оценке
γ1=minjγj=minjγ1=7,γ2=-6=7
Далее столбец А1 будем называть разрешающим.
Для определения вектора, подлежащего исключению из базиса, находим отношение элементов столбца «B» к положительным элементам разрешающего столбца. Строка, в которой это отношение окажется минимальным
ε01=min97,-=97,
объявляется разрешающей. В нашем случае минимальное отношение оказалось во второй строке, поэтому вектор A5 подлежит исключению из базиса.
Элемент х11=3, который находится на пересечении разрешающей строки и разрешающего столбца, является разрешающим.
Пересчитываем рабочую часть таблицы по формулам (2.37), (2.38), (2.40) и (2.41). Например:
x2,0'=97, x1,0'=7*7-9*(-6)7=1037, f1=0-(9*(-42+7M)7=54,
x2,2'=-57, x2,1'=2*7-(-5)*(-6)7=-167,
Таблица 1.4
i AБ СБ В 5 2 -7 0 0 0
А1 А2 А3 А4 А5 А6
1 А3 0 9/7 -5/7 -2/7 1 -1/7 0 1/7
2 А5 0 103/7 -16/7 9/7 0 -6/7 1 6/7
m+1
54 -20 -6 0 -6 0 6-M
Проверяем, является ли этот план оптимальным, для чего просмотрим (m+1)-ю строку таблицы 1.5. В данной строке среди оценок γ''1 нет отрицательных. Найденный опорный план является оптимальным и
fxmax=-10*0-6*0+42*97=54
На основании оценок можно заключить, что оптимальный план единственный, т. к...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
200 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
7 апреля 2017
Заказ завершен, заказчик получил финальный файл с работой
5
Построить двойственную задачу Если прямая задача разрешима то найти оптимальное решение двойственной задачи.docx
2019-04-12 11:11
Последний отзыв студента о бирже Автор24
Общая оценка
4.6
Положительно
Есть небольшие замечания от преподавателя,в целом все хорошо,Автор сделал все быстро,отвечала быстро на все вопросы и пожелания,рекомендую к работе
Хочешь такую же работу?
300 ₽
