Целочисленного линейного

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

Целочисленное программирование применяется в тех же случаях, что и линейное, но дополнительно требуется, чтобы хг> х2, • •-, х„ были числами целыми (например, люди, станки, машины и т. д.). Решение методами целочисленного программирования с помощью ЭВМ требует в несколько раз больших затрат машинного времени, чем использование линейного программирования.

Сложные управленческие задачи Линейное и целочисленное программирование Анализ моделей принимаемых решений

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

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

8.5. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

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

76.^ Т. Целочисленное программирование и потоки в сетях. - М.: Мир, 1974. -

1.3.2. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ 16

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

В работе было применено целочисленное программирование для определения мест расположения производственных мощностей заводов по розливу пропана. Предложенная конфигурация этих заводов обеспечила экономию более 1 млн. долл. по сравнению с первоначальным планом компании SSLPG.

При наличии ограничений на ресурсы (финансовых, производственных мощностей, трудовых и т. д.), которые доступны предприятию, задача выбора набора проектов, которые приносят наибольший доход, может быть решена методами математического программирования и в самой общей постановке может быть сведена к задаче целочисленного программирования [2]. Когда денежные потоки проектов и другие параметры проектов не меняются в зависимости от принятия или отказа от проектов из рассматриваемого набора, задача может быть сведена к задаче целочисленного линейного программирования. Этот случай является практически наиболее важным. Формулировка задачи выбора оптимального набора проекта в линейном случае выглядит следующим образом [35]. Необходимо найти максимум функции L, который имеет смысл ЧТС от реализации предприятием оптимального набора проектов:

При решении задачи целочисленного линейного программирования используются специальные методы, которые широко известны и описаны в литературе [2].

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

видно, что размерность второй линейной модели значительно меньше размерности первой. 'Кроме того, часто при решении целочисленных линейных моделей бывает необходимо приведение их к специальному виду, что достигается введением дополнительного числа ограничений и переменных. Размерность линейных моделей в этих случаях еще более возрастает. Однако размерность второй модели будет расти медленней. Исходя из этих обстоятельств и из того, что размерность линейных целочисленных задач, которые можно решить точ-нъши методами,,, невелика, с точки зрения применения таких методов решения, вторая линейная модель, конечно, предпочтительней. То же самое можно сказать и с позиции использования приближенных методов решения задач целочисленного линейного программирования.

Что касается нелинейных целочисленных задач, то для их решения известен пока что один приближенный метод решения— метод случайного перебора (метод Монте-Карло). Для приближенного решения задач целочисленного линейного программирования сейчас известен целый ряд приближенных ме-

тодов (итеративный метод, разработанный Пятецким-Шапиро, Волконским, Левиной .и Поманским [93, 60]; случайный поиск с локальной оптимизацией [60]; метод случайного перебора и др.)- Судить об эффективности всех этих методов можно пока что на основании машинных экспериментов. Однако опыт приближенного решения задач целочисленного линейного программирования, а тем более нелинейных целочисленных задач, еще невелик и потому ответить на поставленный выше вопрос о преимуществах и недостатках линейных и нелинейных целочисленных моделей с позиции применения к их решению приближенных методов не представляется возможным.

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

Точные методы решения задач целочисленного линейного программирования основаны на временном отказе от требования целочисленное™ переменных. В этих задачах отбрасывается условие целочисленности переменных и решается обычная задача линейного программирования. После нахождения оптимального плана задачи линейного программирования могут представиться два случая.

1. Все компоненты оптимального плана — неотрицательные целые числа. В этом случае полученный план будет являться оптимальным и для соответствующей задачи целочисленного линейного программирования.

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

В настоящее время разработаны две группы таких методов [60] . Первую группу составляют методы отсечения (метод целочисленных форм и др.). (Вторую — комбинаторные методы (метод ветвей и границ, аддитивный алгоритм и др.). Наибольшее распространение при решении задач с булевыми переменными получил аддитивный алгоритм Балаша. Для реализации этого метода на ЭВМ разработаны программы. Одна из таких программ, получившая широкое распространение, разработана 3. В. Коробковой [62]. Для того, чтобы воспользоваться этой программой, необходимо задачу целочисленного линейного программирования привести к виду:

Навигация

Главная

Новое

Акционер Америка Агрессивность