Целочисленные задачи линейного программирования

С учетом сказанного задача коммивояжера принимает вид целочисленной задачи линейного программирования  [c.140]


Опишите схему решения целочисленной задачи линейного программирования методом ветвей и границ.  [c.157]

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

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

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


Если допустимое множество целочисленной задачи линейного программировании является конечным множеством, то это комбинаторная оптимизационная задача. Классическим примером комбинаторной оптимизационной задачи наряду с задачами о загрузке корабля и о распределении капиталовложений между проектами является задача о коммивояжере.  [c.218]

Если в целочисленной задаче линейного программирования отбросить требование о целочисленное неизвестных, то получим задачу линейного программирования, которая называется ослаблением исходной целочисленной задачи.  [c.218]

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

Известны различные методы решения целочисленных задач линейного программирования методы отсечений, метод ветвей и границ, метод Беллмана. Эффективность того или иного метода зависит от конкретных условий целочисленной задачи линейного программирования.  [c.219]

Метод отсечения для целочисленных задач линейного программирования  [c.219]

Дана полностью целочисленная задача линейного программирования  [c.219]

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

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


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

Задача линейного программирования решается без учета целочисленности. Далее рассматривают одну из переменных Xj, на которую накладывают ограничение целочисленности, но которая получила дробное значение. На основе полученного решения составляют дополнительные ограничения  [c.127]

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

Суть этого алгоритма [92] состоит в соединении основной схемы итеративного алгоритма решения соответствующей нецелочисленной задачи с идеей доводки его до целочисленного методом случайного поиска. Итеративный алгоритм, основанный на идее известного метода Брауна— Робинсона решения матричных игр, дает возможность получить приближенное решение задачи линейного программирования при небольших затратах машинного времени. Проведенные эксперименты доказывают, что в применении к некоторым классам задач линейного программирования итеративные алгоритмы могут конкурировать с симплексными [92].  [c.190]

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

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

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

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

Сформулированная математическая задача отличается от задачи линейного программирования только последним условием целочисленности. Однако наличие этого условия позволяет (в данном конкретном случае) легко решить задачу перебором. Действительно, как ограничение по стоимости, так и ограничение по площади показывают, что х < 4. Значит, х может принимать лишь одно из пяти значений 0, 1, 2, 3, 4. " >  [c.175]

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

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

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

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

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

Для решения задач дискретного программирования применяется ряд способов. Самый простой — решение обычной задачи линейного программирования с проверкой полученного результата на целочисленность и округление его до приближенного целочисленного решения. Скажем, получилось у вас, что надо построить полторы домны, выбираете либо одну, либо две. Точно так же не 3,8 автомобиля, а 4 и т. д.  [c.118]

Реальные задачи линейного программирования насчитывают тысячи переменных, для их решения разработаны сложные математические алгоритмы. Задачи линейного программирования, в которых нормативы объемов ресурсов или коэффициенты целевой функции содержат случайные элементы, называют задачами линейного стохастического программирования. Когда же одна или несколько независимых переменных могут принимать только целочисленные значения, они представляют собой задачи линейного целочисленного программирования.  [c.510]

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

Заменим решение исходной целочисленной задачи линейного программирования на многоугольнике решением ряда задач линейного программирования на многоугольниках ( , ( 2, Qa,... Здесь ( = Q. Многоугольники эти таковы, что множество целых точек в них одно и то же. Таким образом, понятно, что если оптимальный план задачи линейного программирования на многоугольнике Qs удовлетворяет условию целочисленности, то он является и оптимальным целочисленным планом исходной задачи. Процесс решения на этом заканчивается. Если же на многоугольнике Qs оптимальный план не удовлетворяет условию целочисленности, то происходит переход к < а+1 путем добавления одного правильного отсечения (на рис. 15 прямая АВ). Это вновь добавленное неравенство гарантирует, что оптимальный план, в котором не выполнялось условие целочисленности, заведомо не будет даже допустимым планом в последующих задачах. Ну, а множества целых точек это неравенство не сужает. Иными словами, правильные отсечения позволяют выбрасывать заведомо ненужные точки многоугольника ограничений, не теряя при этом нужных точек. Такая идея и лежит в основе метода Гомори. Ему удалось предложить алгориф-мический процесс построения правильных отсечений, не использующий ни рисунка, ни каких-либо других интуитивных соображений, что сделало бы его непригодным для решения многомерных задач. Кратко опишем этот алгорифм.  [c.112]

Если допустимое м-ножество и ограничено, то исходная оптимизационная задача сводятся к целочисленной задаче линейного программирования  [c.218]

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

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

Для решения целочисленной задачи линейного программирования (9.47) — (9.50) методом отсечений необходимо вьшолнить ряд последовательных шагов. На каждом шаге решается задача линейного программирования если эта задача оказывается неразрешимой, то и исходная целочисленная задача является неразрешимой.  [c.221]

Зачастую к определяемым величинам в задаче линейного программирования предъявляют требование целочисленности, исходя из смысла переменной. Это может быть целое число станков, вагонов, числа работающих. Решение этих задач значительно сложнее. Типовыми алгоритмами их решения являются методы Гомори и Балаша.  [c.123]

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

Таким образом, в ряде случаев совершенно необходимо получить целочисленные значения переменных решения. Как уже отмечалось выше, надстройка "Поиск решения" MS-Ex el позволяет легко ввести требование целочисленности переменных. Однако необходимо ясно осознавать, что введение такого ограничения означает отказ от использования эффективных методов решения задач линейного программирования, если переменные целые "По-  [c.98]

Надстройка "Поиск решения" MS-Ex el позволяет легко ввести требование целочисленности переменных. Однако введение такого ограничения означает отказ от использования эффективных методов решения задач линейного программирования и делает невозможным получение информации об устойчивости решения и о теневых ценах.  [c.110]

Почему так получилось Дело в том, что введенное дополнительное ограничение превратило нашу задачу о назначениях (по существу транспортную задачу) в обычную задачу линейного программирования. Для такой задачи специализированные "транспортные" методы решения неприменимы. А как указывалось раньше, только они обеспечивают целочисленные решения без введения явных требований целочисленности. Получившуюся общую ЛП-задачу MS-Ex el решают с помощью обычного симплекс-метода, а он отнюдь не гарантирует целочисленности переменных решения.  [c.141]

ГОМОРИ СПОСОБ — прием, с помощью которого задачи линейного программирования приводятся к целочисленному виду.  [c.117]

Анализ модели обычно производится с помощью методов и алгоритмов решения условных экстремальных задач или посредством статистич. моделирования. К числу наиболее широко применяемых в И. о. методов относится линейное программирование. Модели, приводящие к задачам линейного программирования, глубоко изучены, имеются эффективные алгоритмы и стандартные программы для ЭВМ, позволяющие решать задачи, содержащие тысячи ограничений и десятки тысяч переменных. Как правило, анализ моделей И. о. с помощью методов линейного программирования позволяет не только получить оптимальное решение, но и сделать онредел. качеств, выводы по организации операции. Эти выводы базируются на теории двойственности (объективно-обусловленные оценки) и принципах декомпозиции. Если целевая функция или ограничения модели исследуемой операции не могут быть достаточно точно описаны с помощью линейных функций, для её анализа используются др. методы математического программирования. Модели, в к-рых по смыслу операции все переменные или их часть могут принимать лишь конечное число различных значений, изучаются методами целочисленного или дискретного программирования, в частности, сюда относится большое число нла-ново-производств. операций, укладывающихся в схему т. н. задач календарного планирования и теории расписаний. Это задачи, связанные с нахождением последовательности обработки определ. числа изделий с помощью фиксированной системы машин, характеристики к-рых заданы. При этом должны быть соблюдены опродел. технологич. требования, к-рые по большей части выделяют допустимые последовательности обработки каждой детали на различных машинах. Задачи теории расписаний часто встречаются во внутризаводском планировании, особенно на мапшностроит. предприятиях. Модели, описывающие протяжённые во времени операции, цель к-рых достигается лишь с их окончанием, а осуществление может быть разделено на этапы, время начала и завершения к-рых должно быть согласовано, исследуются методами сетевого  [c.74]

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

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

: [c.179]    [c.136]    [c.221]    [c.449]