Cтраница 2
Поэтому, если начинать решение из одной и той же исходной точки, будут получены одни и те же промежуточные значения хь как для исходной, так и для модифицированной задачи. Целесообразно подчеркнуть: использование одной и той же исходной точки означает, что J0 удовлетворяет уравнению ( 6.49 а), если применяется исходная формулировка. [16]
Как только это будет сделано, можно решать модифицированную задачу линейного программирования любым обычным методом, и полученное базисное оптимальное решение автоматически будет целочисленным. Представленный ниже целочисленный алгоритм обладает следующими свойствами: 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конечное число шагов создается достаточное количество дополнительных ограничений для того, чтобы оптимальное решение модифицированной задачи было целочисленным; 3) дополнительные ограничения ( гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязательно находящуюся внутри выпуклой оболочки; 4) к. Следует подчеркнуть, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область сократится до размеров выпуклой оболочки. [17]
Такой же подход применим и к решению некоторых задач динамического программирования, как, например, к задаче распределения ресурсов, приведенной в разд. Соответственно для решения модифицированной задачи может быть использовано рекуррентное соотношение динамического программирования для одной переменной, состояния. Однако если значения управляющих переменных должны быть целочисленными, то окончательное решение, найденное с помощью указанного подхода, может оказаться не более чем приближенным решением исходной: адачи. [18]
Более общие задачи программирования сравнительно мало отличаются от классических задач Эйлера-Лагранжа о нахождении минимумов функций конечного числа действительных переменных при наличии ограничений. Разница состоит в том, что кроме ( или вместо) ограничений типа равенств вводятся ограничения-неравенства. Соответствующая модификация вариационной задачи Лагранжа с ограничениями, а также правило множителей Лагранжа для этой модифицированной задачи были получены Валентайном около 30 лет назад. Ясно также, что Лагранж и его последователи хорошо понимали, какие изменения повлечет за собой введение ограничений типа неравенств. В этом случае единственное различие, появляющееся из-за ограничения-неравенства g ( х) 0, состоит в том, что для точек х, в которых g ( x) 0, сила реакции направлена наружу и, следовательно, отвечающий этому ограничению множитель должен иметь соответствующий знак. Конечно, в точке, где g ( x) 0, это ограничение не порождает никакой силы реакции. [19]
Введение такого вспомогательного запирающего барьера не меняет сколько-нибудь заметно ф внутри ядра или внутри потенциального барьера, окружающего ядро, поскольку г з мало внутри вспомогательного запирающего барьера. Таким образом, состояние с комплексным собственным значением может быть ассоциировано с реальным дискретным состоянием модифицированной задачи. [20]
Остановимся на дополнительных трудностях, которые могут возникнуть при решении внутренних задач. Дело в том, что в каждом случае нагрузка, приложенная к телу, оказывается, вообще говоря, несамоуравновешенной и, следовательно, краевая задача - неразрешимой. Для устранения этих трудностей наиболее просто тогда ввести в какой-либо точке силу и момент, компенсирующие неуравновешенность внешней нагрузки, и решать полученные модифицированные задачи. Из условия равновесия тела в целом будет следовать, что в окончательном решении ( после суммирования) введенные вспомогательные слагаемые взаимно уничтожаются. [21]
Остановимся на дополнительных трудностях, которые могут возникнуть при решении внутренних задач. Дело в том, что в каждом случае нагрузка, приложенная, к телу, оказывается, вообще говоря, несамоуравновешенной и, следовательно, краевая задача - неразрешимой. Для устранения этих трудностей наиболее просто тогда ввести в какой-либо точке силу и момент, компенсирующие неуравновешенность внешней нагрузки, и решать полученные модифицированные задачи. Из условия равновесия тела в целом будет следовать, что в окончательном решении ( после суммирования) введенные вспомогательные слагаемые взаимно уничтожаются. [22]
Критерии I и II остаются при этом без изменений; подстановка типа ( 3) или ( 4) производится по мере необходимости на различных этапах итерационного процесса. Читателю предоставляется возможность продемонстрировать эффективность такого алгоритма самостоятельно. Вычислительный процесс можно начать, выбрав в качестве пробного решения модифицированной задачи ( за счет введения для переменных ограничений сверху) оптимальное решение ( которое предполагается конечным) соответствующей задачи, в которой значения переменных не ограничены сверху, причем такое решение, которое не удовлетворяет дополнительным ограничениям, накладываемым на управляемые переменные. [23]