При необходимости точного решения применяют специальные методы, где учитывается, что множество решений любой целочисленной задачи — конечно. Например, в задаче с переменными х, Xz 0 < xi < 4 0 < х, < 5 число возможных решений — 20. Следовательно, возможен полный перебор возможных сочетаний целочисленных х, х2 и выбор наилучшего в смысле целевой функции. Трудоемкость этого метода возрастает с ростом числа переменных и области граничных условий, поэтому в реальных задачах применяют методы, в которых не рассматривают все возможные альтернативы. Распространены методы отсечений и методы возврата, среди которых наиболее известен метод ветвей и границ. [c.127]
Что касается нелинейных целочисленных задач, то для их решения известен пока что один приближенный метод решения— метод случайного перебора (метод Монте-Карло). Для приближенного решения задач целочисленного линейного программирования сейчас известен целый ряд приближенных ме- [c.129]
Точных методов решения целочисленных нелинейных задач в настоящее время нет. Однако нелинейные целочисленные задачи можно свести, к линейным целочисленным [122]. Сведем, например, задачу (4.24) — (4.31) к задаче целочисленного линейного программирования. Для этого любое произведение булевых переменных, входящее в условия задачи, необходимо заменить одной новой булевой переменной, а к системе ограничений экономико-математической модели добавить два линейных неравенства соответственно для каждой вновь вводимой булевой переменной. >В нашем случае [c.193]
Однако не всегда есть смысл сведения нелинейных целочисленных задач к задачам линейным, так как размерность последних получается очень большой и точные методы решения в этом случае неприменимы. [c.194]
Итак, если нет смысла сведения нелинейных целочисленных задач к задачам целочисленного линейного программирования, то необходимо использовать для решения этих задач приближенные методы. [c.194]
Одним из наиболее оправдавших себя на практике методов приближенного решения нелинейных целочисленных задач является метод статистических испытаний (метод Монте-Карло). [c.194]
Математическая модель линейной целочисленной задачи может быть записана следующим образом [c.464]
Игнорируя условия целочисленности, получим X =(1/ 2 0 9/2). Никакое округление компонентов этого плана не дает допустимого решения, так как искомое целочисленное решение х (2 2> 5) Таким образом, для решения целочисленных задач необходимы специальные методы. [c.465]
На первом шаге решается задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. Если полученное оптимальное решение оказывается целочисленным, то оно является также решением исходной задачи. В противном случае следует ввести дополнительные ограничения, порождающие (вместе с исходными ограничениями) новую задачу линейного программирования, решение которой оказывается целочисленным и совпадает с оптимальным решением исходной целочисленной задачи. [c.466]
Дадим геометрическую интерпретацию задачи. На рис. 2.1 показано, что введение двух ограничений позволяет получить новую экстремальную точку с координатами (4 3), в которой достигается оптимум исходной целочисленной задачи. [c.472]
В первом случае, т. е. при изменении вектора 6, достоинства двойственного симплекс-метода очевидны, так как ранее найденный оптимальный базис можно использовать в качестве исходного сопряженного базиса при продолжении решения. Второй случай более подробно будет рассмотрен в гл. 4 при рассмотрении методов решения целочисленных задач. [c.76]
Перечисленные проблемы предопределили необходимость разработки специальных методов решения дискретных и целочисленных задач. Но прежде чем говорить собственно о методах решения, более подробно остановимся на классификации задач дискретного программирования. В литературе, как правило, выделяют следующие классы дискретных оптимизационных задач [c.138]
С учетом сказанного задача коммивояжера принимает вид целочисленной задачи линейного программирования [c.140]
В последующих параграфах мы остановимся на способах решения наиболее известных и хорошо изученных дискретных задач. Излагаемые ниже методы не имеют универсального характера, с каждым из них связаны определенные ограничения и, соответственно, ответ на вопрос о выборе того или иного из них зависит от конкретных особенностей решаемой задачи. Более того, цель изложения состоит в том, чтобы создать у читателя общие представления об основных идеях и подходах, не углубляясь далеко в вычислительные и математические тонкости, которыми буквально изобилуют алгоритмы дискретного программирования. Заметим также, что достаточно эффективный и широко применяемый подход к решению целочисленных задач основан на сведении их к задачам транспортного типа. Это объясняется тем, что если в условиях транспортной задачи значения запасов (а,.) и потребностей ( .) являются целочисленными, то целочисленным будет и оптимальный план. [c.142]
Опишите схему решения целочисленной задачи линейного программирования методом ветвей и границ. [c.157]
Трудности, возникающие в настоящей задаче, типичны для так называемой целочисленной задачи линейного программирования. [c.251]
В целочисленной задаче линейного программирования необходимо, чтобы размеры поставок соответствовали величинам мощности отдельных заводов. [c.251]
В настоящее время в зарубежной литературе разработан алгоритм решения целочисленной задачи, но алгоритм этот очень сложен и при больших матрицах не решается на существующих ЭВМ. Подобные задачи решаются приближенным методом. [c.252]
Эти задачи требуют целочисленного решения. Но следует отметить, что модель формирования годовой производственной программы можно решать и как целочисленную задачу линейного программирования и как обычную задачу линейного программирования (нецелочисленную). Требования целочисленности решений в задачах такого типа обусловлены характером производимой продукции (например, если бы выпускались различные виды ткани, то решение не обязательно должно получаться целочисленным, а в данном случае производятся грохоты, станки и т.п., которые исчисляются в целых единицах). [c.26]
Если есть возможность увеличить (уменьшить) какой-либо из ограничивающих ресурсов на количество, выходящее из допустимых интервалов, то необходимо пересчитать задачу с новыми ограничениями. Это можно сделать очень легко, так как необходимо при всех заданных условиях задачи только поменять, где это необходимо, правые части в ограничениях. Например, если увеличить показатель трудоемкости Т на 6000 н-ч. (3 вариант целочисленной задачи 1, решение которой приведено в приложении 7), то двойственные оценки ограничивающих ресурсов (приведенные в приложении 8) изменятся. [c.34]
Сравнение решений всех трех вариантов целочисленной задачи 1 с внесенными изменениями приведено в таблице 4.6. Из таблицы видно, что отличие оптимальных планов по всем вариантам задачи 1 происходит по следующим видам продукции 9, 12, 13, 15, 17, 19. При этом оптимальные планы в исходном, первом и втором вариантах различаются незначительно, а третий вариант имеет значительные отличия, что объясняется изменениями, выходящими за границы допустимого интервала. [c.34]
Поскольку, вообще говоря, получаются нецелые значения si , требуется перебор 2Л точек — с округлением координат в меньшую и большую стороны. Из них исключаются точки с недопустимым коэффициентом ненадежности, а из оставшихся выбирается связанная с минимальными затратами. Подчеркнем, что истинно оптимальной точки среди полученных округлением координат может и не оказаться. Это относится ко всем решениям целочисленных задач, отыскиваемым округлением вещественных решений. [c.334]
Если допустимое множество целочисленной задачи линейного программировании является конечным множеством, то это комбинаторная оптимизационная задача. Классическим примером комбинаторной оптимизационной задачи наряду с задачами о загрузке корабля и о распределении капиталовложений между проектами является задача о коммивояжере. [c.218]
Если в целочисленной задаче линейного программирования отбросить требование о целочисленное неизвестных, то получим задачу линейного программирования, которая называется ослаблением исходной целочисленной задачи. [c.218]
Целочисленное оптимальное решение ослабления является оптимальным решением и исходной целочисленной задачи, [c.218]
Таким образом, целочисленные задачи линейного программирования образуют специфический класс оптимизационных задач, для решения которых требуются специальные методы. [c.219]
Известны различные методы решения целочисленных задач линейного программирования методы отсечений, метод ветвей и границ, метод Беллмана. Эффективность того или иного метода зависит от конкретных условий целочисленной задачи линейного программирования. [c.219]
Каковы особенности решения в MS Ex el целочисленных задач ЛП [c.24]
Уздемир А.П. Динамические целочисленные задачи оптимизации в [c.100]
Процедуры поиска решения в Ex el используют симплекс-метод, алгоритмы нелинейной оптимизации и метод ветвей и границ для решения линейных и целочисленных задач с ограничениями. [c.211]
Название методы отсечений связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами. Метод отсекающих плоскостей, разработанный Р. Гомори, используется при решении полностью целочисленных задач. [c.466]
Такое ограничение-равенство определяет отсечение Гомори для полностью целочисленной задачи. [c.468]
Преобразуем исходную таблицу путем приписывания к ней строки и столбца, соответствующих построенному отсечению Гомори для полностью целочисленной задачи. [c.469]
Разработан, однако, ряд специальных методов, пригодных именно для такого класса задач. Простейший и наименее точный из них состоит в решении линейной задачи с ограничениями 1—3 с последующим округлением результатов так, чтобы они удовлетворяли и условию 4. Точный метод, дающий оптимальное решение целочисленной задачи, разработан американским математиком Р. Гомори. Хотя принципиальная применимость и даже конечность метода доказана, все же практическая ценность его ограничена, так как с его помощью удается решать лишь задачи не слишком большого объема, даже используя самую современную вычислительную технику. [c.77]
Разработан, однако, ряд специальных методов, пригодных именно для такого класса задач. Простейший и наименее точный из них состоит в решении линейной задачи с ограничениями (1)—(3) и последующим округлением результатов так, чтобы они удовлетворяли и условию (4). Точный метод, дающий оптимальное решение целочисленной задачи, впервые был предложен американским математиком Р. Гомори. [c.110]
Заменим решение исходной целочисленной задачи линейного программирования на многоугольнике решением ряда задач линейного программирования на многоугольниках ( , ( 2, Qa,... Здесь ( = Q. Многоугольники эти таковы, что множество целых точек в них одно и то же. Таким образом, понятно, что если оптимальный план задачи линейного программирования на многоугольнике Qs удовлетворяет условию целочисленности, то он является и оптимальным целочисленным планом исходной задачи. Процесс решения на этом заканчивается. Если же на многоугольнике Qs оптимальный план не удовлетворяет условию целочисленности, то происходит переход к < а+1 путем добавления одного правильного отсечения (на рис. 15 прямая АВ). Это вновь добавленное неравенство гарантирует, что оптимальный план, в котором не выполнялось условие целочисленности, заведомо не будет даже допустимым планом в последующих задачах. Ну, а множества целых точек это неравенство не сужает. Иными словами, правильные отсечения позволяют выбрасывать заведомо ненужные точки многоугольника ограничений, не теряя при этом нужных точек. Такая идея и лежит в основе метода Гомори. Ему удалось предложить алгориф-мический процесс построения правильных отсечений, не использующий ни рисунка, ни каких-либо других интуитивных соображений, что сделало бы его непригодным для решения многомерных задач. Кратко опишем этот алгорифм. [c.112]
Если допустимое м-ножество и ограничено, то исходная оптимизационная задача сводятся к целочисленной задаче линейного программирования [c.218]
В частности, если ослабление окажется транспортной задачей с целочисленным вектором ограничений, то оптимальное решение транспортной задачи (которое при этих условиях всегда можегг быть выбрано целочисленным) будет оптимальным решением исходной целочисленной задачи линейного программирования. [c.219]
В большинстве же случаев ослабление целочисленной задачи линейного программирования имеет только нецелочисленное оптимальное решение, причем если округлить нецелочисленные координаты этого решения, то нельзя получить даже допустимого решения исходной задачи.. С другой стороны, для решения комбинаторной оптимизационной задачи можно попробовать перебрать все допустимые решения этой задачи и выбрать среди них такое, на котором целешая функция принимает наибольшее (наименьшее) значение. Однако встречаются задачи, у которых допустимых решений очень много и перебрать их все практически невозможно. [c.219]