Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

Х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, обозначающие время простоя соответственно токарного станка и станка-автомата, могут принимать дробные значения. Для поиска оптимального целочисленного решения воспользуемся методом Гомори для частично целочисленных задач.

1. МЕТОД ГОМОРИ ДЛЯ ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ

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

Ограничения составляются по финальной симплекс-таблице, в которой получено оптимальное нецелочисленное решение. При этом на первоначальную систему ограничений накладывается новое ограничение по следующей формуле:

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

Добавим к нашей финальной симлекс-таблице строку и столбец, соответствующие построенному ограничению и новой базисной переменной Х9:

Рекомендуем скачать другие рефераты по теме: банковские рефераты, контрольные 1 класс.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата