Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Целочисленное программирование





Достаточно часто встречаются условия, когда модели планирования содержат целочисленные переменные. Например:

1. Использование оборудования. Переменными Х можно обозначить единицы оборудования, которые должны функционировать в течение планового периода, описываемого моделью. Если каждая единица оборудования имеет большую мощность и высокую стоимость (например, автоматический винторезный станок, океанский танкер или 150-дюймовая бумагорезная машина), то дробное значение X, скажем 10/3, может и не иметь смысла (т. е. оказаться нереализуемым) в рамках реальной задачи принятия решения. В таком случае на значения х приходится наложить требование целочисленности.

2. Размеры партий. При разработке некоторых производственных планов на значения X могут накладываться ограничения вида X ≥ 0 или X ≥ L. Так, например, величина X может представлять собой количество определенных изделий, которое нужно выпустить в течение периода t, а L — минимально возможный размер партии этих изделий. Подобное условие является примером ограничения вида «или — или», его можно формально ввести в модель, используя целочисленные переменные.

3. Решения типа «да — нет». Может возникнуть необходимость определения ситуаций │А С этой целью на переменные X накладываются ограничения х = 1 или х =0, соответствующие решениям «принять» или «отвергнуть». Это можно считать основной причиной, объясняющей, почему целочисленное программирование играет столь важную роль в организационных решениях.

Общий алгоритм решения задач целочисленного программирования должен исключать необходимость явного перебора всех допустимых альтернатив. Требуются методы, обеспечивающие частичный перебор сравнительно небольшого числа допустимых вариантов и неявный перебор всех остальных. Напомним, что симплексный метод, применяемый для решения обычных задач линейного программирования, обладает именно такими характеристиками.

Аналогично в рекуррентных соотношениях, используемых в методе динамического программирования, применяют принцип оптимальности, позволяющий устранить необходимость перебора всех допустимых решений. Эффективность этих методов оптимизации, основанных на частичном переборе, оправдывает постановку вопроса о поиске аналогичных подходов к решению задач целочисленного программирования.

 

Существующие методы решения:

1. Методы отсекающих плоскостей (методы отсечения). Предложено несколько вариантов этого подхода к решению целочисленных задач. Один из них, излагаемый в следующем разделе, предназначен для полностью целочисленной модели. Исходным моментом является оптимальное решение соответствующей задачи линейного программирования, полученной в результате отбрасывания условий целочисленности. На каждой итерации добавляется линейное ограничение, удовлетворяющее целочисленному решению исходной задачи, но исключающее текущее нецелочисленное решение. Вычислительный процесс прекращается, как только будет достигнуто любое целочисленное решение. Сходимость обеспечивается за конечное, но иногда очень большое число итераций.

2. Методы, возврата. В этой группе методов также имеются различные модификации. Первый метод, названный методом «ветвей и границ», изложен [4, разд. 13.5] и предназначен для решения частично целочисленных задач. Как и в методе отсечения, решение задачи начинается с отыскания оптимального решения соответствующей регулярной задачи линейного программирования. Затем формируется семейство связанных, но различных задач линейного программирования.

Существуют и другие подходы к решению целочисленных задач, которые хотя и не гарантируют отыскания оптимального решения, тем не менее в ряде частных случаев позволяют его находить,

а нередко дают решения, близкие к оптимальному. Один из таких подходов заключается в использовании случайной выборки допустимых решений с последующим улучшением каждого попавшего в выборку решения в случае, когда возможность улучшения соответствующего решения удается достаточно просто обнаружить.

В ряде практических ситуаций такие методы отыскания решений оказались достаточно эффективными.

 

Date: 2016-05-14; view: 401; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию