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

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

Таким образом, целевая функция (2.9) вместе с ограничениями (2.11), (2.17) и (2.18) представляет собой экономико-математическую модель задачи необходимо найти такие значения темпов выполнения работ сетевой операционной модели (количества добавляемых на процессы технологических звеньев), которые обеспечивают строительство объекта в плановые сроки при минимуме затрат на передислокацию строительно-монтажных подразделений. Данная задача относится к классу нелинейных задач целочисленного программирования. Даже в упрощенном варианте организации строительства без учета сменности работ решение задачи представляет определенную трудность. [c.50]

Экономико-математические методы должны также широко применяться при определении мест размещения и оптимальной мощности перевалочных нефтебаз. Эту задачу можно отнести к многоступенчатой задаче целочисленного программирования, состоящей из нескольких звеньев. С одной стороны, здесь должны быть учтены добыча нефти и ее транспорт к потребителям, с другой стороны, транспорт и хранение нефтепродуктов при их продвижении от НПЗ к потребителям. [c.82]

Формирование оптимальной инвестиционной программы с учетом риска и бюджетного ограничения сводится к задаче линейного целочисленного программирования с булевыми переменными. [c.182]

Решение задачи осуществляется методами линейного целочисленного программирования. Однако сложность заключается в том, [c.182]

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

Линейное программирование позволяет глубоко проанализировать задачу, и все же оно предполагает те же пять допущений, о которых говорилось выше при обсуждении метода анализа вклада в расчете на единицу ограничивающего фактора, а именно наличие определенности линейность функции затрат линейность функции выручки равенство объема реализации объему выпуска и независимость продуктов. Кроме того, мы предположили, что продукты делимы, т.е. можно произвести и продать нецелое их количество, что не всегда соответствует действительности. (Это предположение в неявной форме было присуще и методике анализа вклада/релевантных затрат на единицу ограничивающего фактора.) Данные недостатки преодолеваются в более совершенных методах анализа, например, в нелинейном или целочисленном программировании. Но даже и такие методы не полностью гарантируют точность результатов, а их чрезмерная сложность может помешать их пониманию и эффективному использованию. [c.376]

Следует отметить, что если требуется округлять решения, то это потенциально несет в себе некоторые осложнения. Например, есть случаи, когда оптимальные целочисленные решения могут достаточно отличаться от решений, полученных стандартным методом линейного программирования. Мы больше не будем останавливаться на этом вопросе, так как это находится вне рамок данного пособия и связано с применением методов целочисленного программирования . [c.282]

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

Обычно управленческие решения принимаются в одной из двух возможных ситуаций или в условиях относительной определенности, или в условиях крайней неопределенности. В табл. 16.1 схематично представлены модели, сгруппированные по степени сложности и характеру переменных решаемых задач. Обычно количественная оценка принятия решений в условиях относительной определенности сводится к максимизации или минимизации некоторых целей (например, к максимизации прибыли и минимизации рисков), и при этом лицо, принимающее решение, должно рассмотреть и возможные ограничения (например, ограничения производственных мощностей или финансовых ресурсов), которые усложняют достижение намеченных целей. Модели линейного и целочисленного программирования поэтому являются наиболее распространенными способами решения масштабных задач такого бизнеса. В этих моделях используются математические методы для определения максимальных или минимальных значений какого-то объективного результата, зависящего от комплекса некоторых субъективных ограничений. [c.254]

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

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

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

В задачах целочисленного программирования неизвестные могут принимать только целочисленные значения. [c.104]

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

Т. Целочисленное программирование и потоки в сетях. - М. Мир, 1974. - [c.219]

К такому виду может быть легко сведена любая задача целочисленного программирования. [c.188]

Нахождение точек излома функции менее всего поддается механизации расчета. Это в значительной мере объясняется тем, что потребное количество рабочих при каждом ритме определяется одновременно с закреплением рабочих за операциями. Задача же закрепления операций за рабочими в общем случае может быть сформулирована как задача целочисленного программирования, решение которой связано. со значительными трудностями. [c.78]

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

Применение методов линейного и целочисленного программирования [c.155]

Приведенная математическая модель формирования производственной программы относится к классу моделей целочисленного линейного программирования с векторным критерием оптимальности (с упорядоченными по важности компонентами — частными критериями). Она имеет сравнительно небольшое число общих ограничений (не считая ограничения сверху на переменные). Это позволяет эффективно применить к ней точные методы целочисленного программирования. Ввиду того, что значения отличных от нуля переменных объемов производства изделий в большинстве случаев значительно превосходят единицу, для нахождения приближенно оптимального плана модели можно применять методы линейного программирования с последующим округлением значений нецелочисленных переменных в оптимальном плане. Для непосредственного применения стандартных алгоритмов оптимизации общую модель удобнее преобразовать в рабочую модель. [c.326]

Таким образом, данная задача принадлежит к классу экономико-математических задач целочисленного программирования с значительным числом вариантов. Например, если число работ равно 20, а на каждую работу может добавлено всего одно технологическое звено при односменной организации работ, то число вариантов решения этой простейшей сетевой модели составляет более 1 миллиона. [c.102]

Иногда Д.п. называется целочисленным. Как видно из приведенных примеров, это не лишено основания, хотя некоторые математики считают такой термин неправильным (так как, строго говоря, дискретное — это не обязательно целочисленное напр., ряд чисел 1,1 1,2 1,3...—дискретный, но не целочисленный). Поэтому правильнее, очевидно, считать целочисленное программирование частным случаем Д.п. [c.88]

Задачи Л.п., в которых нормативы (или коэффициенты), объемы ресурсов (константы ограничений) или коэффициенты целевой функции содержат случайные элементы, называются задачами линейного стохастического программирования когда же одна или несколько независимых переменных могут принимать только целочисленные значения, то перед нами задача линейного целочисленного программирования. В экономике широко применяются линейно-программные методы решения задач размещения производства (см. Транспортная задача), расчета рационов для скота (см. Задача диеты), наилучшего использования материалов (см. Задача о раскрое), распределения ресурсов по работам, которые надо выполнять (см. Распределительная задача) и т.д. [c.172]

Названные выше разнообразные дисциплины отличаются друг от друга видом целевой функции fix) и области М. Напр., если fix) линейна, а М— выпуклый многогранник, имеем задачу линейного программирования если же дополнительно ставится условие, чтобы переменные были целочисленными, то имеем задачу целочисленного программирования если зависимость U отд (т.е. форма f) носит нелинейный характер, то задачу нелинейного программирования. [c.187]

Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к целочисленному программированию. [c.175]

В отличие от задач линейного программирования, в целочисленном программировании управляющие параметры принимают значения из дискретного множества. К целочисленному программированию относятся задачи размещения (производственных объектов), теории расписаний, календарного и оперативного планирования, назначения персонала и т.д. [c.176]

Методы решения задач целочисленного программирования. Расскажем о двух методах решения задач. В соответствии с методом приближения непрерывными задачами сначала решается задача линейного программирования без учета целочисленности, а затем в окрестности оптимального решения ищутся целочисленные точки. [c.177]

Более широкие возможности имеет пакет Стохастическая оптимизация", созданный на базе ППП Линейное программирование в АСУ" (ППП ЛП АСУ) [102]. ППП ЛП АСУ предназначен для решения и анализа задач линейного программирования (ЛП), нелинейного программирования (НЛП) с нелинейными функциями сепарабельного вида, целочисленного программирования (ЦП) и задач специальной узкоблочной структуры. Размерность решаемых задач составляет для ЛП до 16000 строк, для ЦП — до 4095 целочисленных переменных и 60000 строк для задач узкоблочной структуры. Пакет может быть использован также для решения задач стохастического программирования (СТП) при построчных вероятностных ограничениях. В последнем случае необходимо предварительно построить детерминированный аналог. [c.179]

Использование смешанного целочисленного программирования для уменьшения количества смены этикеток на заводе компании "Коорс" по производству алюминиевых пивных банок [c.154]

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

На начальном этапе применение экономико-математических методов характеризовалось разработкой и решением отдельных планово-экономических задач (задач оптимизации формирования производственной программы, использования производственных мощностей и др.). В этом отношении накоплен богатый опыт. Основной оптимизационной моделью подсистемы перспективного планирования являетсямодель выбора вариантов проектов реконструкции и нового строительства, решаемая методами целочисленного программирования. Она дополняется алгоритмической сетью расчета остальных показателей плана, производных по отношению к показателям капитальных вложений и объемов продукции по годам перспективного периода (эти показатели получаются непосредственно решением модели). [c.51]

ГОМОРИ СПОСОБ [Gomory method] — прием, с помощью которого достигается решение линейной задачи целочисленного программирования. Разработан американским математиком Р. Гомори. Состоит в автоматическом введении дополнительных ограничений, приводящих через конечное количество шагов к новой линейной задаче с целочисленным/решением, которое оказывается одновременно оптимальным целочисленным решением исходной задачи (если только она имеет решение). См. также Дискретное программирование. [c.64]

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [mathemati al programming] (см. также Оптимачьное программирование) — раздел математики, который "... изучает методы решения задач на нахождение экстремума функций (показателя качества решения) при ограничениях в форме уравнений и неравенств"40. Оно объединяет различные математические методы и дисциплины исследования операций линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование, геометрическое программирование, целочисленное программирование и др. [c.186]

Смотреть страницы где упоминается термин Целочисленное программирование

Смотреть главы в: