Проверяемый текст
[стр. 266]

план не может придать целевой функции значение больше, чем значение при оптимальном нецелочисленном плане.
Если же значения переменных оптимального плана, полученного для нецелочисленной задачи, являются целочисленными,
то это означает, что значение целевой функции в этом случае является точной верхней границей множества значений целевой функции целочисленной задачи.
Если получился второй случай, когда некоторые из ограничений (4.10) не выполняются, то возможны два способа поведения.
Первый способ поведения состоит в том, что значения правых частей ограничений (4.10) Аш корректируются с учетом полученного решения.
При этом может оказаться, что незначительное увеличение некоторых
Ау в ограничениях (4.10) приведет к существенному увеличению значения целевой функции.
И если первоначальные ограничения носили в какой-то степени волевой (ориентировочный) характер, то теперь появляется возможность их обоснованной корректировки.
Второй способ поведения заключается в том, что значения Ад не корректируются, а подыскиваются целочисленные значения переменных Xjj удовлетворяющие ограничениям (4.10).
Естественно предположить (это подтверждают и практические расчеты), что значение экономической эффективности, найденное путем округления нецелочисленного плана в целочисленный, незначительно отличается от значения целевой функции оптимального целочисленного плана.
Кроме того, важным является то обстоятельство, что с помощью решения нецелочисленной задачи находится оценка сверху для значения целевой функции оптимального целочисленного плана.
Существующее отрицательное отношение к применению симплекс-метода для решения такого рода задач не обосновано, т.к.
отмечаемая неустойчивость решения относится к плану, а не к значению целевой функции.
По значению целевой функции решение, как правило, оказывается устойчивым, т.е.
при различных способах округления и различных планах получаемых при этом значениях целевой функции оказываются достаточно близкими.

266
[стр. 88]

♦ 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) приведет к существенному увеличению значения целевой функции.
При этом, если первоначальные ограничения носили в какой-то степени волевой (ориентировочный) характер, то теперь появляется возможность их обоснованной корректировки.


[стр.,89]

89 2.
Значения Aw не корректируются, а подыскиваются целочисленные значения переменных Ху удовлетворяющие ограничениям (1 1 ).
Естественно предположить (это подтверждают и практические расчеты), что значение экономической эффективности, найденное путем округления нецелочисленного плана в целочисленный, незначительно отличается от значения целевой функции оптимального целочисленного плана.
Кроме того, важным является то обстоятельство, что с помощью решения нецелочисленной задачи находится оценка сверху для значения целевой функции оптимального целочисленного плана.
Существующее отрицательное отношение к применению симплекс-метода для решения такого рода задач не обосновано, т.к.
отмечаемая неустойчивость решения относится к плану, а не к значению целевой функции.
По значению целевой функции решение, как правило, оказывается устойчивым, т.е.
при различных способах округления и различных планах получаемых при этом значениях целевой функции оказываются достаточно близкими.

Зачастую получаемый таким способом план вообще совпадает с оптимальным или, отличаясь от него, обеспечивает близкое значение целевой функции.
#

[Back]