Cтраница 3
Однако описанный выше алгоритм удобен для граничных задач, содержащих только один параметр. О, возникает дополнительная трудность при обработке результатов вычислений, в частности, при построении упомянутых выше кривых. А именно, эта трудность заключается в том, что В и С являются в действительности функциями от В и С и поэтому линии уровня В не совпадают с линиями уровня В. Иначе говоря, когда мы решаем преобразованную задачу Коши, то задаем значения В и С, а не В и С, и поэтому до завершения вычислений мы не знаем, какая пара значений В ч С будет соответствовать решению. [31]
Применение подходящих преобразований к геометрическим объектам часто может быть вызвано стремлением преобразовать исходную задачу к некоторой эквивалентной ей задаче. В одних случаях точки d - мерного пространства отображаются в точки этого же пространства, в других случаях преобразование отображает / г-мерные многообразия в ( а - 1 - k) - мерные многообразия. Имеется важный класс преобразований последнего типа, известных под названием полярное или двойственное преобразования, которые в последнее время с большим успехом были использованы в ряде приложений. Главная причина этого успеха состоит в том, что преобразованная задача более непосредственно воздействует на интуицию и, следовательно, в большей степени способствует созданию эффективного алгоритма. [32]
Пусть в задаче линейного программирования ограничения имеют вид равенств, а переменные неотрицательны; тогда, если ограничений меньше, чем переменных, естественно использовать строчную таблицу, а в других случаях - столбцовую таблицу. Поэтому, если исходная задача содержит свободные переменные, большей частью бывает удобнее решать двойственную к ней задачу. Прежде чем записать двойственную задачу, полезно в исходной освободиться от ограничений в виде равенств, поскольку они будут порождать свободные переменные в двойственной задаче. Для этой цели обычно используется техника преобразования линейной программы с ограничениями-равенствами в линейную программу с ограничениями-неравенствами, после чего переходят к двойственной задаче. Преобразованная и исходная задачи должны быть эквивалентны в том смысле, что оптимальные значения их целевых функций равны и можно из преобразованной задачи восстановить величины переменных исходной задачи. [33]
Как было отмечено ранее, использование Z в условии 2 является более общим, чем использование целевой функции. Одним из существенных составных элементов сходимости является то, что процедура должна давать улучшение. Условие 2а требует улучшения на каждой итерации алгоритма до достижения подходящей точки. Мы можем интерпретировать функцию Z как преобразователь, который показывает продвижение алгоритма. Во многих алгоритмах для измерения их продвижения используется целевая функция /, и в этом случае f Z. Некоторые же алгоритмы решают задачу НЛП, преобразовывая ее в другую задачу, и при этом Z может быть рассмотрена как целевая функция преобразованной задачи. Вообще с увеличением Z алгоритм приближается к подходящей точке. [34]