Использование целочисленных переменных в ЛП-задачах [c.98]
Помимо рассмотренных вполне очевидных случаев, в которых необходимо введение условия целочисленности, существует и другая область использования целочисленных переменных в ЛП-задачах. Весьма часто на практике возникают задачи, когда требуется решить, какие элементы из большого их набора нужно выбрать, чтобы оптимизировать целевую функцию и удовлетворить заданным ограничениям, а какие отбросить. Этот класс задач по-английски называют задачами типа "go/no go", что по-русски соответствует дилемме "брать/не брать". Часто также о подобных задачах говорят как о задачах "загрузки вещевого мешка", имея в виду следующую "туристическую" аналогию. Имеется множество предметов, которые вы хотели бы взять в поход, но все они не входят в вещевой мешок. Вы приписываете каждой вещи определенную величину ценности и пытаетесь заполнить мешок наиболее ценными вещами, удовлетворяя одновременно ограничения по суммарному объему и весу содержимого мешка. [c.100]
Задачи Л.п., в которых нормативы (или коэффициенты), объемы ресурсов (константы ограничений) или коэффициенты целевой функции содержат случайные элементы, называются задачами линейного стохастического программирования когда же одна или несколько независимых переменных могут принимать только целочисленные значения, то перед нами задача линейного целочисленного программирования. В экономике широко применяются линейно-программные методы решения задач размещения производства (см. Транспортная задача), расчета рационов для скота (см. Задача диеты), наилучшего использования материалов (см. Задача о раскрое), распределения ресурсов по работам, которые надо выполнять (см. Распределительная задача) и т.д. [c.172]
Однако в ряде задач целочисленные значения переменных решения являются обязательными. Например, в мини-кейсе об оптимальном использовании ресурсов кондитерской фабрики, оставшихся перед ее длительной остановкой на реконструкцию, число пакетиков конфет разного типа, конечно, должно быть целым. Пусть решается вопрос о покупке нескольких различных типов станков в количествах, которые должны, с одной стороны, минимизировать издержки завода-покупателя, а с другой - обеспечить необходимые требования по выпуску продукции. Если при этом модель выдает рекомендацию купить 2,13 штуки станка первого типа, 3,435 - второго и 0,67 - третьего, ясно, что такая рекомендация неприемлема. [c.98]
Рассмотрим одну из целочисленных моделей. Предельным проявлением целочисленности является использование в модели булевых переменных — единицы и нуля. Логически это соответствует выбору между да и нет . Это в свою очередь требует заранее сформулировать те варианты производственной программы, варианты развития производственных мощностей, варианты стратегии экономического поведения, которые и будут в дальнейшем подвергнуты анализу и отбору. Таким образом, содержание задачи в данном случае состоит в следующем принять или отвергнуть варианты из их заранее известного, сформированного набора. Причем целиком принять или целиком отвергнуть (частичные решения запрещены) каждый из них. Соответствующую модель принято называть вариантной, ибо она построена на основе заранее известных, заданных вариантов и ее содержанием будет являться сортировка таких вариантов на эффективные, принятые в оптимальный план, и неэффективные, т. е. отвергнутые. [c.31]
Вариантные расчеты могут проводиться также при варьировании элементов самой модели изменении критерия оптимальности, добавлении новых ограничений на ресурсы или на способы их использования, расширении множества вариантов, введении в модель условий целочисленного или вероятностного характера, изменении некоторых переменных, решении задачи разными методами и т. д. Эти расчеты во многих случаях осуществляются для повышения обоснованности решения, особенно если оно является весьма важным. Но чаще они применяются для отработки самих моделей, проверки их соответствия реальной действительности. Кроме того, вариантные расчеты используются при отсутствии точных методов поиска оптимального решения модели. [c.123]
Более широкие возможности имеет пакет Стохастическая оптимизация", созданный на базе ППП Линейное программирование в АСУ" (ППП ЛП АСУ) [102]. ППП ЛП АСУ предназначен для решения и анализа задач линейного программирования (ЛП), нелинейного программирования (НЛП) с нелинейными функциями сепарабельного вида, целочисленного программирования (ЦП) и задач специальной узкоблочной структуры. Размерность решаемых задач составляет для ЛП до 16000 строк, для ЦП — до 4095 целочисленных переменных и 60000 строк для задач узкоблочной структуры. Пакет может быть использован также для решения задач стохастического программирования (СТП) при построчных вероятностных ограничениях. В последнем случае необходимо предварительно построить детерминированный аналог. [c.179]
Таким образом, в ряде случаев совершенно необходимо получить целочисленные значения переменных решения. Как уже отмечалось выше, надстройка "Поиск решения" MS-Ex el позволяет легко ввести требование целочисленности переменных. Однако необходимо ясно осознавать, что введение такого ограничения означает отказ от использования эффективных методов решения задач линейного программирования, если переменные целые "По- [c.98]
Надстройка "Поиск решения" MS-Ex el позволяет легко ввести требование целочисленности переменных. Однако введение такого ограничения означает отказ от использования эффективных методов решения задач линейного программирования и делает невозможным получение информации об устойчивости решения и о теневых ценах. [c.110]
Существует эвристический подход к решению задач целочисленного программирования (ЗЦП), основанный на решении ЗЦП как задачи Л П. Использование процедур округления нецелочисленного оптимального решения задачи ЛП дает возможность пблучать приближенное оптимальное целочисленное решение. Например, если в оптимальном решении двумерной задачи ЛП значения переменных х и Xi оказались равными 3,5 и 4,4 соответственно, то в качестве кандидатов на роль приближенного целочисленного оптимального решения необходимо рассмотреть точки (3 4), (4 4), (4 5), (3 5), полученные в результате округления. Заметим, однако, что истинное оптимальное целочисленное решение может не совпадать ни с одним из четырех, указанных выше. [c.465]
Смотреть страницы где упоминается термин ИСПОЛЬЗОВАНИЕ ЦЕЛОЧИСЛЕННЫХ ПЕРЕМЕННЫХ В ЛП-ЗАДАЧАХ
: [c.519] [c.129]Смотреть главы в:
Методы оптимизации управления для менеджеров -> ИСПОЛЬЗОВАНИЕ ЦЕЛОЧИСЛЕННЫХ ПЕРЕМЕННЫХ В ЛП-ЗАДАЧАХ