Cтраница 4
Описанный выше алгоритм нахождения множества всех Л - близких решений применяется в аппрок-симационно - комбинаторном методе. В этом методе реализуется основная идея комбинаторных методов: выделяется множество G С G, содержащее оптимальное решение исходной задачи (1.1.1); множество G G исключается из дальнейшего рассмотрения. Изложим, следуя [43], основные понятия этого метода. [46]
Процесс ветвления продолжается до тех пор, пока не будет получено в одной из ветвей целочисленное решение. Пусть задача ЗЛП-4 ( рис. 12.1) имеет целочисленное решение. Обозначим / - значение функции на первом целочисленном решении: / / ( / Соответствующее целочисленное решение включается в множество X возможных оптимальных решений исходной задачи. [47]
Кроме того, можно получить при решении этой новой, физически нереализуемой задачи такую схему ТС, которая не будет одновременно многократно использовать одни и те же потоки. Следовательно, в соответствии с условием ( VI, 17) и ( VI18) рассматриваемая новая расширенная задача является граничной по отношению к исходной проектной задаче. Некоторое физически реализуемое решение граничной задачи, которое будет удовлетворять условию минимума приведенных затрат, является искомым оптимальным решением исходной задачи. [48]
Другой возможный тип ограничений - это требование целочисленности решения, причем ац и а4 - предполагаются целыми. При наличии такого требования обычно проводится подбор дополнительных к (4.3) ограничений типа неравенств, так чтобы решение получалось целочисленным. Например, на каждом шаге вводится ограничение, отсекающее от многогранника некоторую его часть, не исключая при этом его целочисленных точек, а плоскость дополнительного ограничения проходит хотя бы через одну целочисленную точку. Через конечное число шагов исходная задача сводится к задаче, решение которой является целочисленным и в то же время оптимальным решением исходной задачи. [49]
В последнем случае, если Q I 2пл, то с помощью линейной зависимости оптимальных значений переменных Л - за-дачи от X в промежутке АьА Хй 1 возьмем такое X, при котором для соответствующей Я-задачи будет Q2QM - Следует обратить внимание еще на такую возможность. Здесь Яь-0 и Xft O - предельные значения, вычисленные соответственно слева и справа от ЯА. В этом случае нужно взять такую комбинацию ХаХ ( Кь. О), QaQ ( xh - 0) ( 1 - a) Q ( Xft - fO), 0а1 ( при любом а это оптимальное решение прямой л-задачи с Я-Я), для которой 22фпл - Выше было показано, что оптимальное решение Я-задачи, для которого условие (3.26) выполняется как равенство, является оптимальным решением исходной задачи. [50]
Так как при решении новой расширенной задачи возможна одновременное многократное использование одних и тех же потоков, то величина приведенных затрат на выполнение задания по рекуперации тепла технологических потоков будет ниже, чем она могла бы быть при нахождении оптимального решения исходной проектной задачи. Кроме того, можно получить при решении этой новой, физически нереализуемой задачи такую схему ТС, которая не будет одновременно многократно использовать одни и те же потоки. VI, 17) и (VI.18) рассматриваемая новая расширенная задача является граничной по отношению к исходной проектной задаче. Некоторое физически реализуемое решение граничной задачи, которое будет удовлетворять условию минимума приведенных затрат, является искомым оптимальным решением исходной задачи. [51]