Cтраница 4
Точные методы решения задач целочисленного линейного программирования основаны на временном отказе от требования целочисленное переменных. В этих задачах отбрасывается условие целочисленности переменных и решается обычная задача линейного программирования. После нахождения оптимального плана задачи линейного программирования могут представиться два случая. [46]
Геометрически прозрачная идея метода отсечения принадлежит, по-видимому, Данцигу. Предлагается вначале пренебречь требованием целочисленности переменных и вместо целочисленной линейной задачи решить соответствующую ей непрерывную задачу линейного программирования. Может оказаться, что оптимальный план задачи линейного программирования удовлетворяет также условиям целочисленности. Тогда он является одновременно и решением задачи целочисленного программирования. Если же на первом шаге получено нецелочисленное решение, то к исходным линейным ограничениям задачи добавляется новое линейное неравенство. Оно формируется а основании следующих соображений. Полученное нецелочисленное решение не должно удовлетворять новому неравенству, а любой целочисленный план ( е только оптимальный) заведомо удовлетворяет ему. [47]
Полученная матрица С называется приведенной. Она обладает тем свойством, что в каждой ее строке и столбце имеется по крайней мере один нуль. Процесс, позволяющий из неотрицательной матрицы С получить приведенную неотрицательную матрицу С, называется приведением. Оптимальный план задачи о коммивояжере с матрицей С явля - ется оптимальным и для задачи о коммивояжере с матрицей С. [48]
Наряду с возможностями нахождения решения различных задач использование ППП ЛП2 позволяет проводить анализ полученного решения. Этот анализ может быть самым широким, что определяется пользователем. Например, можно определить, в каких интервалах могут изменяться коэффициенты целевой функции задачи, так чтобы данная задача имела один и тот же оптимальный план. Далее, можно выявить устойчивость оптимального плана задачи относительно изменения свободных членов системы ограничений, а также других параметров задачи. [49]
После заполнения новой симплекс-таблицы просматривают элементы ( т 1) - и строки. Если все г / - с / 0, то новый опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то, используя описанную выше последовательность действий, находят новый опорный план. Этот процесс продолжают до тех пор, пока либо не получают оптимальный план задачи, либо не устанавливают ее неразрешимость. [50]