Решение оптимизационной задачи линейного программирования - (курсовая)
p>Так как все коэффициенты E-строки таблицы 7положительные, то оптимальное решение найдено. Оптимальный план состоит в том, чтобы токарный станок работал над деталями типа38 часов за смену, то есть всю рабочую смену, и не работал над деталями типа 1 и 2 вообще. Станок-автомат должен работать за смену 2, 67 часа над деталями типа 1 и 5, 33 часа над деталями типа 2 и не должен работать над деталями типа 3. При этом за смену будет выпускаться максимально возможное количество комплектов деталей, а именно 40 комплектов. Ни один из станков не будет простаивать.5. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ
В окончательной симплекс-таблице, содержащей оптимальное решение, содержится не только само оптимальное решение, но и другая информация. На основе последней симплекс-таблицы решаются задачи анализа на чувствительность - определение влияния изменений в исходных данных задачи на оптимальное решение. Интерпретация симплекс-таблицы и анализ на чувствительность полностью зависят от содержательного смысла конкретной задачи. В нашем случае мы имеем дело с задачей о распределения ресурсов, а именно ресурсов времени.
5. 1. СТАТУС РЕСУРСОВ
По статусу ресурсы делятся на дефицитные и недефицитные. Если некоторый ресурс при реализации оптимального плана расходуется полностью, он называется дефицитным, если не полностью - недефицитным.
Статус ресурсов определяется по значениям остаточных переменных Х7 и Х8, введенных в исходную систему ограничений для приведения ее к стандартной форме. Эти переменные означают остатки ресурсов при реализации оптимального плана. Ни одна из остаточных переменных не входит в оптимальное решение, т. е. их значения равны нулю. Это означает, что токарный станок и станок-автомат использовались все выделенное для их работы время, т. е. запасы времени работы станков являются дефицитными ресурсами. Увеличение запасов дефицитных ресурсов позволяет увеличить значение целевой функции, а снижение этих запасов приводит к уменьшению целевой функции.
5. 2. ЦЕННОСТЬ РЕСУРСОВ
Ценность ресурса - это величина увеличения значения целевой функции при увеличении запасов данного ресурса на единицу (или соответственно величина уменьшения целевой функции при снижении запаса ресурса). Другое название этой величины - теневая (скрытая) цена. В симплекс-таблице, соответствующей оптимальному решению, теневые цены содержатся в E-строке и представляют собой коэффициенты при остаточных переменных, соответствующим остаткам ресурсов. Таким образом, ценность времени работы токарного станка и станка-автомата соответственно равна по 2, 5 комплекта деталей. Другими словами, если запас времени работы токарного станка увеличить (уменьшить) на 1 час, то количество производимых комплектов деталей увеличится (уменьшится) на 2, 5 единицы, и, аналогично, если увеличить (уменьшить) время работы станка-автомата станка на 1 час, то количество комплектов увеличится (уменьшится) на 2, 5 комплекта.
5. 3. АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ К ИЗМЕНЕНИЯМ ПРАВЫХ ЧАСТЕЙ ОГРАНИЧЕНИЙ
Для анализа решения на чувствительность к изменению запасов времени работы станков (без изменения других исходных данных задачи) используются коэффициенты из столбцов остаточных переменныхХ7 и Х8 (соответственно для токарного станка и станка-автомата) в последней симплекс-таблице. Например, если запас времени работы токарного станка изменился на d часов и стал равен 8+d часов, то новое оптимальное решение находится по следующим формулам:
Х3 = 8 + 1*d
X6 = 0 – 0, 5*d
X4 = 2, 67 + 0, 17*d
X5 = 5, 33 + 0, 33*d
E = 40 + 2, 5*d
При составлении этих формул использовали коэффициенты из столбца остаточной переменнойХ7 в последней симплекс-таблице. По содержательному смыслу эти формулы означают изменение времени работы токарного станка или станка-автомата над каждой из деталей в сутки при изменении запаса дефицитного ресурса. ФормулаE = 40 + 2, 5*d означает изменение количества производимых комплектов деталей в сутки. Например, если время работы токарного станка станет не 8, а 6 часов в сутки, т. е. уменьшится на 2 часа (d=-2), то базисные переменные, а также целевая функция примут следующие значения:
Х3 = 6; Х6 = 1; Х4 = 2, 33; Х5 = 4, 67; Е = 35.
Все остальные переменные равны нулю (они не являются базисными). Как видно, из-за уменьшения запаса времени работы токарного станка уменьшилось время работы этого станка над деталями типа 3, но вместе с тем увеличилось время работы станка-автомата над этими же деталями. Так как станок-автомат стал работать за смену 1 час над деталями третьего типа, то он уменьшил свое время работы над деталями типа 1 и 2 (ранее он отдавал все свое время на обработку только этих деталей). И, очевидно, что если время работы токарного станка уменьшилось, то уменьшится и количество комплектов деталей, производимых в сутки.
Таким образом, для исследования влияния изменения запаса ресурса на оптимальное решение нет необходимости решать задачу заново (с новым ограничением). Для нахождения оптимального решения достаточно по окончательной симплекс-таблице исходной задачи составить уравнения и подставить в них величину изменения запаса ресурса (значение d).
Изменение запасов ресурсов (т. е. правых частей ограничений) может привести к недопустимости оптимального базиса, найденного для исходной задачи. Так как на все переменные, используемые в задаче, накладывается требование неотрицательности, допустимый диапазон изменения запаса ресурса (т. е. диапазон допустимых значений d) находят из системы неравенств. Таким образом, допустимый диапазон изменения запаса времени работы токарного станка, при котором состав переменных в базисе оптимального решения не изменяется, находится из условия: Х3 = 8 + 1*d > 0
Х6 = 0 – 0, 5*d > 0
Х4 = 2, 67 + 0, 17*d > 0
Х5 = 5, 33 + 0, 33*d > 0
Решив данную систему неравенств, получим, что –8 < d < 0. Таким образом, базис оптимального решения будет состоять из переменных (Х3, Х6, Х4, Х5), если запас времени работы токарного станка будет находиться в диапазоне от 0 до 8часов. Выход значения d за границы этого диапазона приведет к недопустимости найденного нами оптимального решения, так как минимум одна из базисных переменных окажется отрицательной, и для того, чтобы найти оптимальное решение, нам придется решать задачу заново.
Аналогично выполняется анализ на чувствительность к изменению запаса времени работы станка-автомата.
5. 4. АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ К ИЗМЕНЕНИЯМ КОЭФФИЦИЕНТОВ ЦЕЛЕВОЙ ФУНКЦИИ
В данной задаче коэффициенты целевой функции имеют сложный физический смысл, поэтому анализ на чувствительность к изменению ее коэффициентов производить не будем.
ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ЦЕЛОЧИСЛЕННОГО РЕШЕНИЯ
Данная задача по своему содержанию является частично целочисленной. Переменные X1 , X2 , X3 , X4 , X5 , X6 , обозначающие время работы определенного станка над деталями определенного типа, должны принимать целые значения. В то же время, переменныеХ7 , Х8, обозначающие время простоя соответственно токарного станка и станка-автомата, могут принимать дробные значения. Для поиска оптимального целочисленного решения воспользуемся методом Гомори для частично целочисленных задач.
МЕТОД ГОМОРИ ДЛЯ ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ
Метод Гомори для нахождения целочисленного решения относится к большой группе методов, называемых методами отсечений. Эти методы основаны на введении в задачу дополнительных ограничений, позволяющих учесть требование целочисленности. Основная идея методов отсечений состоит в том, что на полученное оптимальное нецелочисленное решение накладывается дополнительное ограничение, которое делает это решение недопустимым, но и не отсекает ни одного целочисленного решения от области допустимых решений. Ограничения составляются по финальной симплекс-таблице, в которой получено оптимальное нецелочисленное решение. При этом на первоначальную систему ограничений накладывается новое ограничение по следующей формуле: L1*W1 + L2*W2 + … +Ln*Wn ? {Bi} , где
Aij, если Aij? 0 и Wj может быть дробной, (1) ({Bi}*Aij)/({Bi}-1), если Aij{Bi} и Wi должна быть целой, (4) j=1, …, n
где Wn – небазисная переменная;
Bi - базисная переменная, имеющая максимальную дробную часть ( дробная часть числа–это разность между этим числом и максимальным целым числом, не превосходящим его);
Aij –коэффициент, стоящий на пересечении строки i-ой базисной переменной и столбца j-ой небазисной переменной;
Далее полученное ограничение приводится к стандартному виду: -L1*W1 - L2*W2 - … -Ln*Wn + Sr = -{Bi}
где r – номер итерации алгоритма.
Здесь Sr –неотрицательная остаточная переменная, не имеющая никакого содержательного смысла; в оптимальном целочисленном решении эта переменная оказывается равной нулю.
В нашем случае переменная, имеющая максимальную дробную часть – это Х4 ({2, 67}=0, 67), она должна быть целой, переменные Х7 и Х8 могут быть дробными, переменные Х1 и Х2должны быть целыми, поэтому, согласно выше приведенной формуле, составим новое дополнительное ограничение. Так как все коэффициенты на пересечениях базисной переменнойХ4 и небазисных переменных Х1 , Х2 , Х7 , Х8 ? 0 (0, 44? 0, 0, 11? 0, 0, 17? 0), то коэффициенты при переменных Х1 и Х2 рассчитали по формуле (3): L1={0, 44}=0, 44, L2={0, 11}=0, 11, а коэффициенты при переменных Х7 и Х8 рассчитали по формуле (1): L3=0, 17, L4=0, 17. {В4}={Х4} = {2, 67} = 0, 67. Ограничение будет иметь вид: 0, 44Х1 + 0, 11Х2 + 0, 17Х7 + 0, 17Х8 ? 0, 67
Можно убедиться, что это ограничение сделало наше оптимальное решение недопустимым ( если подставить Х1=0, Х2=0, Х7=0, Х8=0, - значения переменных, полученных в оптимальном нецелочисленном решении, то получим 0? 0, 67 – неверно).
Приведя ограничение к стандартному виду, имеем:
-0, 44Х1 - 0, 11Х2 - 0, 17Х7 - 0, 17Х8 + Х9 = -0, 67
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
