Cтраница 4
Условие ( 9) представляет собой линейное ограничение, которое должно выполняться при любом допустимом решении исходной задачи. Если а00 С 0 в условии ( 9), то можно рассматривать ( 9) как производящую строку и получить из нее отсечение Гомори, как это делалось в § 13.1. Если использовать отсечение Гомори как ведущую строку и произвести итерацию ( линейное преобразование небазисных переменных), то после подстановки в ( 7) и ( 8) новых небазисных переменных получим новые ограничения и целевую функцию. Соответственно будет получена новая линейная часть в ( 9), которая рассматривается как производящая строка, если а0о в ней отрицательно. В дальнейшем будет показано, что этот процесс является конечным. [46]
Условие ( 9) представляет собой линейное ограничение, которое должно выполняться при любом допустимом решении исходной задачи. Если а00 С 0 в условии ( 9), то можно рассматривать ( 9) как производящую строку и получить из нее отсечение Гомори, как это делалось в § 13.1. Если использовать отсечение Гомори как ведущую строку и произвести итерацию ( линейное преобразование небазисных переменных), то после подстановки в ( 7) и ( 8) новых небазисных переменных получим новые ограничения и целевую функцию. Соответственно будет получена новая линейная часть в ( 9), которая рассматривается как производящая строка, если а0о в ней отрицательно. В дальнейшем будет показано, что этот процесс является конечным. [47]
Гомори - сначала руководитель группы, затем управляющий отделом, а ныне вице-президент IBM по исследовательской работе - находил способы поддержать мою работу еще тогда, когда она была не более чем игрой, и сейчас продолжает оказывать мне любую помощь, какая бы ни потребовалась. [48]
Если задачу раскроя сформулировать так чтобы исходные варианты раскроя uijh в системе уравнений ( 2) не были известны заранее, то это соответствует задаче нелинейного целочисленного программирования. Однако для решения такой задачи отсутствует строгий математический метод. Гомори, возможно без составления всех исходных вариантов раскроя при помощи динамического программирования, суть которого заключается в следующем. [49]
К числу таких относится задача о составлении графика выпуска сотен видов продукции при Г12 ( мес. Однако в подобных ситуациях чрезвычайно сложно решать задачу ( 12) - ( 15), так как матрица условий этой задачи будет иметь большое число строк и столбцов. Дзелинский и Гомори [10] рассмотрели вариант использования метода разложения Данцига - Вулфа для решения подобной задачи. [50]
Если сохранять все строки, соответствующие слабым переменным Гомори, то эти слабые переменные могут становиться базисными, после того как они были небазисными. Если слабая переменная Гомори вошла в базис с неотрицательным значением, то соответствующая строка представляет собой неравенство, справедливое при текущем решении, и эта строка может быть вычеркнута. Если слабая переменная Гомори становится базисной с отрицательным значением, соответствующую строку следует использовать в качестве ведущей. Если сохранять все строки, соответствующие всем отсечениям Гомори, то, вообще говоря, потребуется меньшее число дополнительных ограничений, однако увеличение таблицы много более неприятно, чем введение лишних дополнительных ограничений. [51]