|
x,j может принимать только два значения: либо 0, либо 1, причем Hi % Xjj = 1 для Vi j=l при выполнении следующих ограничений: MNj Z Еапк1 < Akl для V к для VI (4.10) i=lj=l где k номер ресурса; 1 год вложения. Задача (4.9) при ограничениях (4.10) является задачей целочисленного программирования. Если в полученном оптимальном наборе Ху=1, то это означает, что j-ый вариант i-oro проекта входит в оптимальный набор, если же x,j=O, то не входит. В настоящее время единый эффективный подход к решению задач целочисленного программирования отсутствует. Предлагается следующий метод решения поставленной задачи. Решим задачу (4.9) с ограничениями (4.10) при отсутствии требования на целочисленность Xjj. с помощью симплекс-метода. Полученный нецелочисленный план округляем до целочисленного по правилу, когда наибольшему значению Хц. данной i-й программы придадим значение, равное 1, а остальные переменные этого проекта заменим на нулевые значения. При постановке полученного таким способом целочисленного плана в ограничениях (4.10) может получиться два случая: случай, когда все ограничения выполняются, и случай, когда некоторые из ограничений (4.10) не выполняются. Если ограничения (4.10) выполняются, то полученный целочисленный план является допустимым. Покажем, что в общем случае значение целевой функции (4.9) при нецелочисленном плане является верхней границей для множества значений целевой функции при целочисленных планах. Действительно, при решении целочисленной задачи с помощью симплексметода оптимальный план отыскивается на множестве GH действительных неотрицательных значений переменных. Множество Gu целочисленных значений переменных, на котором ищется решение целочисленной задачи, является подмножеством множества GH т.е. Gn О GH и, следовательно, оптимальный целочисленный 265 |
♦ 88 Решим задачу (10) с ограничениями (11) при отсутствии требования на целочисленность Хц. с помощью симплекс-метода. Полученный нецелочисленный план округляем до целочисленного по правилу, когда наибольшему значению Х у. данной i-ой программы придадим значение, равное 1 , а остальные переменные этого проекта заменим на нулевые значения. При постановке полученного таким способом целочисленного плана в ограничениях ( 1 1 ) может получиться два случая: 1 ) случай, когда все ограничения (1 1 ) выполняются; 2 ) случай, когда некоторые из ограничений (1 1 ) не выполняются. Если ограничения (11) выполняются, то полученный целочисленный план является допустимым. Покажем, что в общем случае значение целевой функции (I) при нецелочисленном плане является верхней границей для множества значений целевой функции при целочисленных планах. Действительно, при решении целочисленной задачи с помощью симплекс-метода оптимальный план отыскивается на множестве G„ действительных неотрицательных значений переменных. Множество Gu целочисленных значений переменных, на котором ищется решение целочисленной задачи, является подмножеством множества GHт.е. Gu с G„ и, следовательно, оптимальный целочисленный план не может придать целевой функции значение большее, чем значение при оптимальном нецелочисленном плане. Если же значения переменных оптимального плана, полученного для нецелочисленной задачи, являются целочисленными, это означает, что значение целевой функции в этом случае является точной верхней границей множества значений целевой функции целочисленной задачи. При втором случае, когда некоторые из ограничений (11) не выполняются, возможны два способа поведения. 1. Значения правых частей ограничений (11) Akj корректируются с учетом полученного решения. При этом может оказаться, что незначительное увеличение некоторых Аы в ограничениях (11) приведет к существенному увеличению значения целевой функции. При этом, если первоначальные ограничения носили в какой-то степени волевой (ориентировочный) характер, то теперь появляется возможность их обоснованной корректировки. |