ЗАДАЧА О РАСКРОЕ — частный случай задач о комплексном использовании сырья, сводящихся к методу лилейного программирования. [c.120]
Задача о комплексном использовании сырья 120 ЗАДАЧА О НАЗНАЧЕНИЯХ 119 ЗАДАЧА О РАСКРОЕ 120 Задача об оптимальном составе [c.158]
ОБЩИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ О РАСКРОЕ [c.11]
Но не только раскрой мерного проката, труб, полос и т. п. требует решения таких задач. Как это будет показано в 3 гл. III, при решении весьма распространенной задачи о раскрое листов на прямоугольные заготовки оказывается полезным предварительно решить некоторую вспомогательную задачу, являющуюся по своей постановке задачей раскроя мерного линейного материала. При этом для решения основной задачи существенно знать не только раскройный план, но и окончательные индексы, получающиеся при решении вспомогательной задачи. [c.52]
Примитивность линейного раскроя позволяет использовать приемы, упрощающие описанные в гл. I общие методы. В следующих трех параграфах указываются дополнительные приемы для решения задачи о раскрое, которые не имеют общего характера, а специально относятся к раскрою мерных линейных материалов по длине. [c.52]
Решим, например, еще раз задачу о раскрое в условиях примера 6. По-видимому, заготовок с индексом 0 в этом случае не будет. [c.57]
Индексы полос. Теперь остановимся на некоторых свойствах тех индексов, которые получатся при окончательном и точном решении задачи о раскрое на прямоугольные заготовки. [c.105]
Пример 7.7. Задача о раскрое или о минимизации обрезков. [c.198]
Задача о раскрое. Обсуждение и решение [c.8]
Например, в задаче о раскрое допустимый план может быть построен так. Возьмем раскрой, в котором имеется заготовка первого вида. Это всегда возможно, так как каждая заготовка получается хотя бы при одном раскрое. Применим этот способ раскроя к такому числу листов, чтобы получилось нужное число заготовок первого типа. Возможно, при этом получится и некоторое число заготовок второго типа. Если их достаточно, то допустимый план уже найден, если же нет, то увеличим их количество до необходимого с помощью раскроя, в котором имеется вторая заготовка. Получившееся количество листов материала и примененные способы раскроя определяют допустимый план. Если бы заготовок было больше, чем две, то, продолжая последовательно удовлетворять требования по заготовкам каждого типа, мы также пришли бы в конце концов к допустимому плану. [c.19]
В качестве иллюстрации рассмотрим применение метода последовательного улучшения плана к нашей задаче о раскрое. [c.20]
Использование теоремы двойственности и связанного с ней признака оптимальности допустимого плана лежит в основе большинства эффективных методов решения задач линейного программирования. В 2 было продемонстрировано решение задачи о раскрое с помощью метода последовательного улучшения плана. Близко к нему примыкает симплекс-метод, разработанный американским математиком. Дж. Данцигом. Здесь мы приведем лишь краткое описание этого метода. [c.31]
Замечание второе. Рассмотренная задача может быть дана и в другой интерпретации. Стержень длиной 83 требуется раскроить на заготовки длиной /i = 24, /2=22, /з=16, /4=10, оценки которых равны соответственно V5=96, Va=85, Уз=50, V<=20, чтобы суммарная оценка полученных заготовок оказалась наибольшей. Очевидно, что мы можем воспользоваться описанным выше методом решения. На той же идее основано нахождение плоских раскроев . Сочетая метод динамического программирования с линейным программированием, можно получить полностью автоматизированное решение задачи о раскрое, [c.67]
Сделав эти предварительные замечания, перейдем к рассмотрению конкретной задачи о раскрое. Листы материала размером 6-13 ма нужно раскроить так, чтобы получились заготовки двух типов 800 шт. заготовок типа А (4 -5 м2) и 400 шт. типа В (2 -3 м2), израсходовав при этом как можно меньше материала. (Для решения такой задачи, конечно, не нужна специальная теория. Но эта задача используется в книге как пример, на котором разъясняются методы линейного программирования.) [c.11]
Например, в задаче о раскрое допустимый план может быть построен так. Возьмем способ раскроя, при котором [c.18]
Рассмотрим применение этого метода к нашей задаче о раскрое. Допустим, что в качестве начального выбран план, использующий первый и четвертый способы раскроя (см. табл. 1). В нем число листов материала, раскраиваемого каждым из этих способов, составляет (округленно) хг = 267, а я4 — 11. Прежде всего убедимся в том, что этот план допустимый, т. е. удовлетворяет поставленным ограничениям. Для этого подставим в него цифры из табл. 1. Получим 3-267 = 801 > 800 1 -267 + 13-11 = = 410 > 400. Допустимость плана подтверждена. [c.20]
Для многих производств типичным является комплексный (совместный) выпуск нескольких видов продукции ри использовании одного и того же исходного сырья и ресурсов нефтепереработка, плавка полиметаллических руд, разведение мясо-молочного скота и т. д. Во всех этих случаях можно получать конечные продукты в различных пропорциях, подобно тому, как при разных способах раскроя меняются соотношения в числе заготовок. Ясно, что во всех этих случаях применима та же математическая модель, которая использовалась в задаче о раскрое. Па ее основе могут быть решены задачи выбора производственных способов, позволяющих получить продукцию нужного состава с наименьшими затратами. [c.25]
Задачи, которые представлены в обоих примерах, могут быть описаны с помощью математических моделей, подобных той, что использовалась в задаче о раскрое. Это показывает, что анализ задачи имеет гораздо большее значение и более широкую область применений, чем может показаться на первый взгляд. [c.26]
При анализе линейно-программной задачи о раскрое было установлено, что с оптимальным планом связаны и им обусловлены определенные оценки для каждого вида продукции и исходного ресурса (в рассмотренном примере 16 — для листа, 5 и 1 — соответственно для каждой заготовки). Остановимся подробнее на смысле этих оценок, так как помимо их значения как средства установления оптимальности плана и его нахождения они сами по себе играют очень большую роль. [c.26]
Рассмотрение этой проблемы будем вести на примере той же задачи о раскрое, которая исследовалась в предыдущем параграфе. Поставим вопрос об оценках заготовок, точнее, установим, какой расход материала связан с каждой заготовкой. Даже если уже рассчитан оптимальный план, ответить на этот вопрос не так просто. Расходуя лист материала, мы получаем заготовки того и другого [c.26]
Первый принципиальный вывод состоит в том, что хотя цены выступают реально в сфере обмена, они определяются условиями, которые складываются в производстве. И математической модели задачи о раскрое нет различных собственников, между которыми мог бы происходить обмен, и все экономические процессы осуществляются на основе единого хозяйственного плана, но все же в этой модели естественным образом возникли цены (оценки), и не только возникли, а оказались полезными и даже необходимыми. [c.29]
Мы встретимся дальше с построением и характеристикой о. о. оценок в различных экономических задачах и их использованием. Здесь же будет показана роль этих оценок в одной конкретной задаче, где их экономический смысл выступает более отчетливо, нежели в задаче о раскрое. [c.30]
Во-вторых, возможна другая интерпретация рассмотренной задачи. Стержень длиной 83 ед. нужно раскроить на такие заготовки /t = 24, /2 = 22, 13 = 16, 1 = 10 оценки заготовок равны соответственно FI = 96, Vz = 85, F3 = 50, F4 = 20 требуется, чтобы суммарная оценка полученных заготовок оказалась наибольшей. Для решения подобной задачи, не опираясь на динамическое программирование, в свое время был применен метод, аналогичный вышеописанному. Сочетая метод динамического программирования с линейным программированием, можно добиться полной автоматизации решения задачи о раскрое. [c.94]
Рассмотрим задачу о раскрое в общей математической постановке. [c.288]
Первооткрыватель Л.п. — советский ученый, академик, лауреат Ленинской, Государственной и Нобелевской премий Л.В. Канторович. В 1939 г. он решил математически несколько задач о наилучшей загрузке машин, о раскрое материалов с наименьшими расходами, о распределении грузов по нескольким видам транспорта и др., при этом разработав универсальный метод решения этих задач, а также различные алгоритмы, реализующие его. Л.В. Канторович впервые точно сформулировал такие важные и теперь широко принятые экономико-математические понятия, как оптимальность плана, оптимальное рас- [c.173]
За прошедшие годы существенно развилась вычислительная техника. Внедрение электронно-вычислительных машин выдвинуло теперь на первый план вопросы автоматизации решения задач о рациональном раскрое. В первом издании эти вопросы освещались с учетом вычислительных возможностей тех лет, хотя необходимые алгоритмы для разработки машинных вычислительных программ уже содержались в книге. Отметим, в частности, метод последовательного улучшения плана раскроя, центральный для решения задач линейного программирования на ЭВМ, и метод построения шкалы индексов, по существу предвосхитивший метод рекуррентных соотношений динамического программирования. [c.3]
С теоретической стороны этот вопрос разработан чрезвычайно мало. Кроме некоторых работ, связанных со стремлением максимизировать объемный выход досок при лесопилении, можно упомянуть известную задачу о плотнейшем расположении кругов на плоскости, равносильную вопросу о раскрое большого листа на равные круглые заготовки. Тонкое исследование, посвященное раскрою ткани, принадлежит П. Л. Чебышеву [387], однако предметом этого исследования является не экономия материала, а задача точного покрытия кривой поверхности выкройками из ткани. , [c.5]
Книга состоит из четырех глав и приложения. В гл. I излагается постановка задачи о нахождении наиболее рационального плана раскроя и общие методы ее решения, иллюстрируемые простейшими примерами. В следующих главах даются приемы ее решения, приспособленные специально к случаю раскроя линейных материалов (гл. II) и раскроя листового материала на прямоугольные и круглые заготовки (гл. III). В этих главах изложены также практические указания, которые проиллюстрированы в основном примерами чисто производственного характера. Общие результаты гл. I могут быть использованы и при раскрое листовых материалов на комплекты различных фасонных заготовок, поскольку с помощью этих методов и в этом случае вопрос о составлении всего раскройного плана сводится только к отысканию раскроев одного листа. [c.9]
К последнему выводу можно прийти проще если в готовом плане сохранить лишь раскрои, состоящие только из преобладающих заготовок, то максимальная экономичность оставшегося частичного плана подтверждается теми же индексами, что и в основном плане. Поскольку же комплектность преобладающих заготовок будет при этом близка к исходной, то и индексы должны быть близки к тем, которые получатся при решении задачи о самостоятельном раскрое преобладающих заготовок. [c.105]
Порядок расчета. На этих рассуждениях основывается следующий прием приближенного решения задачи о наилучшем раскрое [c.110]
ЗАДАЧА О РАСКРОЕ [ ut problem, trim problem] — частный случай задач о комплексном использовании сырья, обычно сводящихся к методу линейного программирования. [c.102]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]
ЗАДАЧА О РАСКРОЕ ( ut problem) - частный случай задач о комплексном использовании сырья, обычно решаемых методами программирования линейного или программирования целочисленного Решение 3 о р помогает с миним отходами производства использовать заготовки при их раскрое Постановку 3 о р в общем виде можно сформулировать так требуется найти минимум линейной формы, выра-,жающей число израсходованных листов материала (прутков и т п ) по всем способам их раскроя См также Кратные размеры материалов [c.70]
РАСКРОЙ (материалов) (materials utting) — технол процесс получения деталей и заготовок из листовых материалов (стекло, фанера, металл и др) Р производится с учетом наиболее рационального использования площади листа и минимизации отходов производства См также Задача о раскрое, Кратные размеры материалов [c.214]
Выработанный математиками метод решения задачи о раскрое помогает с наименьшими отходами использовать прутки и листы металла, листы стекла, картона и других материалов при раскрое их на заданное колнче- i ство деталей различных размеров. [c.120]
Следует, наконец, заметить, что индексы имеют и простой геометрический смысл. Вернемся для пояснения этого к графику (см. рис. 2), которым мы иллюстрировали решение задачи о раскрое на заготовки двух размеров в условиях примера 2. Нетрудно видеть, что отношение индексов 3/2 есть абсолютная величина углового коэффициента прямой A3At, а сами индексы совпадают с коэффициентами уравнения этой прямой, которое записывается как Зл- + 2[c.29]
Вернемся к задаче о раскрое и поставим вопрос об оценках заготовок. Точнее говоря, установим, какой расход материала связан с каждой заготовкой. Даже если мы уже располагаем оптимальным планом, ответить на него не так просто. Расходуя лист материала, мы получаем заготовки того и другого вида, но совсем не ясно, какую долю листа следует отнести к одной заготовке, какую — к другой, совсем не очевидно, как обоснованно разделить затраты между ними. Мы постараемся показать, что такое обоснованное, оправданное распределение дают именно полученные выше оценки. В согласии с этими оценками (16 5 1) следует считать, что расход на заготовку есть 5/i6 листа, а расход на заготовку В — /ie листа. Персым подтверждением правильности такого подхода является то, что при обоих используемых раскроях расход на полученные заготовки (3-5/i6 + Yi6=l 2 5/i6+6/i6= 1) согласуемся с расходом одного листа. Далее, если мы пожелали бы увеличить число заготовок А, оставляя число заготовок В неизменным, достаточно было бы увеличить на 6 число листов, раскраиваемых по способу Ali, и уменьшить на один число листоз, раскраиваемых по способу А12 число заготовок А возросло бы на 6 3—2 -1 = 16 штук, а число заготовок В действительно осталось бы неизменным 6 1—1 6 = 0, т. е. за счет дополнительных 5 листов мы получили бы 16 заготовок А — на каждую было бы израсходовано 5Дб листа. Аналогично можно было бы проверить возможность увеличения числа заготовок В с расходом Vie листа на каждую. Таким образом, по необходимому расходу материала эти заготовки соотносятся как 5 1. Легко проверить также, что, изменяя число листов, раскраиваемых по способам MI и М2 (оставляя общее число листов неизменным), мы можем увеличить число заготовок А за счет заготовок В в соотношении 1 5, т. е. соотношение оценок является вполне реальным, мы имеем возможность обменивать (заменять) заготовки в плане в указанном соотношении (с сохранением оптимальности плана). [c.23]
В СССР становление и развитие НОТ неразрывно связаны с именем В. И. Ленина, который обосновал необходимость для Советской власти организации труда на научной основе, определил основные задачи НОТ, раскрыл ее преимущества по сравнению с капиталистической рационализацией. Во всякой социалистической революции, — подчеркивал В. И. Ленин. — после того как решена задача завоевания власти пролетариатом... выдвигается необходимо на первый план коренная задача создания высшего, чем капитализм, общественного уклада, именно повышение производительности труда, а в связи с этим (и для этого) его высшая организация (Ленин В. И. Поли. собр. соч. Т. 36. С. 187). Ленинские положения о роли НОТ при социализме предопределили главные направления как теоретических разработок, так и практической деятельности масс по совершенствованию организации труда на научной основе. [c.152]
Экономичность раскроя обычно зависит от квалификации и практич. опытности работников. Технология раскроя сравнительно редко регламентируется спец. технич. документацией в виде раскройных карт (гл. обр. в массовом произ-ве). При разработке Р. л. м. р. необходимо всемерно использовать резервы экономии материалов путем сокращения отходов. При нарезке прямоугольных заготовок задача может быть решена мате-матич. методами (см. Раскрой материалов оптимальный). Однако такие методы для раскроя криволинейных заготовок еще не созданы. В 1878 великий русский математик П. Л. Чебышев посвятил оригинальное исследование раскрою ткани, решая задачу наиболее точного покрытия кривой поверхности плоскими выкройками. В геометрии давно разрабатывается задача о наиболее плотном расположении кругов на плоскости хотя общее решение этой задачи не найдено, выработан нек-рый практич. подход к уплотнению расположения кругов на плоскости. Определен также подход к выкраиванию нек-рых других видов криволинейных заготовок из прямоугольных листов. [c.402]
В процессе систематической организации строительного производства решаются многообразные задачи с использованием методов теории массового обслуживания, теории игр, математического программирования и других методов. К ним относятся задачи о выборе целесообразного количества погрузочно-разгрузочных средств (например, автосамосвалов, отвозящих грунт от одноковшового экскаватора), обслуживающего персонала (бригад слесарей, занятых обслуживанием и ремонтом строительной техники), численности контролеров ОТК, работников аппарата управления задачи о выборе оптимальных смесей (например, составов бетонов и растворов), оптимальном раскрое длинномерных погонажных, листовых и рулонных материалов (например, металлопроката, лесоматериалов, стекла и т.д.), задача о рюкзаке , состоящая в выборе оптимального набора предметов при загрузке контейнеров, и др. На каждой стадии организации используются свои специфические способы. [c.292]
Смотреть страницы где упоминается термин Задача о раскрое
: [c.102] [c.465] [c.70] [c.109] [c.9] [c.49]Популярный экономико-математический словарь (1973) -- [ c.120 ]