Точные методы решения задач целочисленного программирования можно классифицировать как методы отсечений и комбинаторные методы. [c.466]
Известны различные методы решения целочисленных задач линейного программирования методы отсечений, метод ветвей и границ, метод Беллмана. Эффективность того или иного метода зависит от конкретных условий целочисленной задачи линейного программирования. [c.219]
Метод отсечения для целочисленных задач линейного программирования [c.219]
Отметим, что возникновение новых ограничений в модели может произойти и на третьем шаге процедуры. Для этого необходимо ввести шаг За, аналогичный по смыслу шагу 2а. Таким образом, в процедуре (схема ее изображена на рис. 6.20) возникает несколько петель обратной связи, которые позволяют преодолеть сложности, связанные с недостаточной развитостью методов моделирования экономических систем. Подчеркнем еще раз, что эта процедура основана на принципе отсечения нереализуемых вариантов в исходном варианте основной модели организационные ограничения учтены не были они постепенно вносятся в модель при обсуждении получаемых решений. При этом нереализуемые варианты постепенно отбрасываются, а модель все более точно описывает реальную ситуацию. [c.335]
Определение весов факторов и отсечение факторов с малым весом (метод главных компонент). [c.226]
Критерий приемлемости. Этот критерий обычно применяют вместе с методом внутренней нормы прибыли. Он служит для сравнения внутренней нормы прибыли с необходимой нормой, известной также как ставка отсечения. [c.352]
Представим себе ситуацию, в которой ставка отсечения проекта равна необходимой норме прибыли как для инвесторов, так и для кредиторов. (Методы ее измерения рассмотрены в гл. 15.) Существует общее согласие относительно того, что инфляция оказывает влияние на стоимость ценных бумаг. Как мы уже говорили в гл. 3, эта зависимость далека от простой и нестабильна во времени. Ключевой момент в этих рассуждениях состоит в том, что если в соответствии с критерием приемлемости, а именно, необходимой нормой прибыли, имеет место премия, связанная с инфляционными ожиданиями, то рассчитанные величины денежных потоков тоже должны отражать инфляцию. Инфляция влияет на эти потоки по-разному. Если у компании денежный приток от реализации продукции, то величина этого потока зависит от ожидаемых цен. Что касается денежных оттоков, то инфляция оказывает воздействие как на ожидаемый уровень заработной платы, так и ожидаемые материальные затраты. Заметим, что будущая инфляция не влияет на амортизационные отчисления по существующим активам. Объем этих отчислений известен со всей определенностью уже после приобретения активов. Влияние инфляционных ожиданий на денежные притоки и оттоки изменяется в зависимости от сущности проекта. В некоторых случаях денежные притоки увеличиваются за счет роста цен и растут быстрее денежных оттоков в других случаях имеет мест обратное явление. Независимо от характеристик этой зависимости она служит важной частью оценки денежных потоков. В противном случае возникают изменения, описанные выше. [c.373]
Если в результате применения двойственного симплекс-метода решение оказывается целочисленным, то процесс решения исходной задачи завершен. В противном случае необходимо ввести новое отсечение на базе полученной таблицы и вновь воспользоваться двойственным симплекс-методом. Если на некоторой итерации при использовании двойственного симплекс-метода обнаружится отсутствие допустимого решения, то рассматриваемая задача не имеет допустимого целочисленного решения. [c.469]
Как производится построение отсечения при решении целочисленной линейной задачи методом ветвей и границ [c.157]
В настоящее время разработаны две группы таких методов [60]. Первую группу составляют методы отсечения (метод целочисленных форм и др.). (Вторую — комбинаторные методы (метод ветвей и границ, аддитивный алгоритм и др.). Наибольшее распространение при решении задач с булевыми переменными получил аддитивный алгоритм Балаша. Для реализации этого метода на ЭВМ разработаны программы. Одна из таких программ, получившая широкое распространение, разработана 3. В. Коробковой [62]. Для того, чтобы воспользоваться этой программой, необходимо задачу целочисленного линейного программирования привести к виду [c.188]
Некоторые из них не связаны непосредственно с алгоритмом симплексного метода, как, например, метод потенциалов для решения транспортной задачи другие же в качестве составных элементов используют вычислительные процедуры симплексного метода. В качестве примера последних можно привести метод Гомори (метод отсечений) для решения задач линейного целочисленного программирования. [c.524]
Название методы отсечений связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами. Метод отсекающих плоскостей, разработанный Р. Гомори, используется при решении полностью целочисленных задач. [c.466]
Методы отсечений опираются на следующее утверждение если ослабление задачи (9.47)— (9.50) имеет нецелочисленное оптимальное о-порное решение а°, то существует [c.219]
Для решения целочисленной задачи линейного программирования (9.47) — (9.50) методом отсечений необходимо вьшолнить ряд последовательных шагов. На каждом шаге решается задача линейного программирования если эта задача оказывается неразрешимой, то и исходная целочисленная задача является неразрешимой. [c.221]
Техника расчленения . Этот способ применяется главным образом для улучшения осязаемых объектов. Суть его заключается в разложении изучаемого объекта на составные части и анализе основных качеств, особенностей или свойств каждой части в отдельности. При этом у каждой части изучается форма, размеры, химический состав, прочность, внешний вид и т. д. с точки зрения возможной замены, отсечения или добавления. Док-тир Роберт П. Кроуфорд, будучи еще профессором университета в штате Небраска, разработал этот технический прием и сделал его составным элементом своего исключительно продуктивного способа обучения творческим методам. Его монография Техника творческого мышления стала настольной книгой по данному вопросу. [c.728]
Осуществление структурной перестройки экономической системы с созданием условий для ускоренного развития отраслей и предприятий, лучше адаптированных к циклическому изменению техники и потребностей общества, и отсечения тех производственных единиц, которые мешают процессу постоянного и необходимого обновления. Данная общеэкономическая задача нередко декларируется, но редко выполняется, так как подменяется другими, более прозаическими и прагматическими целями именно на уровне государства. Так, глобальная проблема уменьшения ресур-сопоглощения убыточными (например, в силу отсталости технологии) организациями автоматически обостряет текущую проблему занятости населения, которую сложно решить радикальными, краткосрочными методами. Именно использование по отношению к решению проблемы занятости населения традиционной стратегии не позволяет радикально решать глобальную задачу. [c.113]
Заменим решение исходной целочисленной задачи линейного программирования на многоугольнике решением ряда задач линейного программирования на многоугольниках ( , ( 2, Qa,... Здесь ( = Q. Многоугольники эти таковы, что множество целых точек в них одно и то же. Таким образом, понятно, что если оптимальный план задачи линейного программирования на многоугольнике Qs удовлетворяет условию целочисленности, то он является и оптимальным целочисленным планом исходной задачи. Процесс решения на этом заканчивается. Если же на многоугольнике Qs оптимальный план не удовлетворяет условию целочисленности, то происходит переход к < а+1 путем добавления одного правильного отсечения (на рис. 15 прямая АВ). Это вновь добавленное неравенство гарантирует, что оптимальный план, в котором не выполнялось условие целочисленности, заведомо не будет даже допустимым планом в последующих задачах. Ну, а множества целых точек это неравенство не сужает. Иными словами, правильные отсечения позволяют выбрасывать заведомо ненужные точки многоугольника ограничений, не теряя при этом нужных точек. Такая идея и лежит в основе метода Гомори. Ему удалось предложить алгориф-мический процесс построения правильных отсечений, не использующий ни рисунка, ни каких-либо других интуитивных соображений, что сделало бы его непригодным для решения многомерных задач. Кратко опишем этот алгорифм. [c.112]
Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать новые дополнительные ограничения (правильные отсечения) и переходить от текущего псевдоплана к новому оптимальному плану. [c.147]
Задачи с неделимостями. Экстремальные комбинаторные задачи. Задачи с разрывными целевыми функциями. Правильное отсечение. Метод Гомори. Методы ветвей и границ. [c.157]
Какой принцип используется для построения правильного отсечения в методе Гомори [c.157]
Применительно к внутреннему рынку некоторая практика уже существует. Анализ продажи преимущественно неконтрольных пакетов акций посредством публичного предложения (данные 2004 г.) показал, что 47% выставленных пакетов (из 525 объявленных) не нашли покупателей. При этом 62% из общего числа проданных данных способом пакетов были реализованы по минимально возможной при данном способе цене - цене отсечения, составляющей половину начальной цены несостоявшегося аукциона. Количество объектов, проданных по максимально возможной цене - цене предложения, равной начальной цене несостоявшегося аукциона, составило 17%. Указанный метод приватизации относится (в терминологии Минэкономразвития и ФАУФИ) к вторичным (по отношению к аукционам и спецаукционам) методам, предназначенным для реализации низколиквидных активов за счет снижения цены в процессе продажи. Заложено здесь и внутреннее противоречие, связанное с тем, что публичное предложение, как правило, используется для наиболее ликвидных активов. [c.419]
В данной работе исследуется возможность построения индекса цен (индекса "базовой инфляции") для России, который бы более подходил для оценки денежной политики, чем индекс потребительских цен. Этот индекс получен применением к российским данным метода усеченного среднего, который рассматривает данные в разрезе определенного момента ( ross-se tion). Мы выяснили, что одномоментные распределения приростов отдельных цен имеют существенно утяжеленные хвосты. В этой ситуации обычное выборочное среднее не является хорошей оценкой центральной тенденции с точки зрения эффективности и робастности. Отсечение 50-100% наблюдений приводит к большому выигрышу в эффективности. Кроме того, показано, что усеченное среднее является менее волатильным, чем официальный индекс потребительских цен. [c.2]