Формирование оптимальной инвестиционной программы с учетом риска и бюджетного ограничения сводится к задаче линейного целочисленного программирования с булевыми переменными. [c.182]
В качестве фиктивных переменных обычно используются дихотомические (бинарные, булевы) переменные, которые принимают всего два значения О или 1 (например, значение такой переменной Z по фактору пол Z = О для работников-женщин и Z]=l — для мужчин). [c.116]
Решение. Введем обозначения i и у — номера пунктов выезда и въезда ij — время переезда из пункта i в пункт /. t в общем случае может быть не равно времени переезда в обратном направлении ttj tji (например, когда один пункт на вершине горы, а другой — у ее подножия). Введем булевы переменные [c.111]
ЗАДАЧИ С БУЛЕВЫМИ ПЕРЕМЕННЫМИ [c.128]
С помощью булевых переменных можно решать самые различные по содержанию задачи, в которых надо что-то выбирать из имеющихся различных вариантов. [c.128]
С помощью булевых переменных можно накладывать дополнительные логические связи между вариантами. Например, требуется, чтобы четвертый вариант был принят только в том случае, если принят второй а если же второй вариант не принят, то и четвертый не должен быть принят. Это условие можно записать так 52 = Ь или в форме записи ограничений 52 - 54 = 0. [c.129]
Введение булевых переменных дает возможность обеспечить выпуск изделий в кратном заданном количестве. Так, для подлокотников х может принимать следующие значения если в результате решения будет получено 82i = 1, а остальные 622 = 833 = 24 = 0, то х = 2 если 622 = 1, а остальные 821 = 823 = = 824 = 0, то х2 = 4 и т. д. [c.131]
Для решения задачи с учетом дополнительных условий мы ввели еще семь переменных и четыре ограничения. Если бы требовалось определить выпуск спинок, подлокотников и ножек для одного изделия (комплекта), то можно было бы записать х2 = 2х xs = 4xi и не вводить дополнительные ограничения и булевы переменные. [c.131]
Пусть, далее г/qj — булева переменная, равная единице, если для производства изделия q-ro наименования принимает- [c.107]
Во многих случаях решение экономических задач возможно только в их дискретной постановке, только в вариантной -форме. Такие задачи можно разделить на два класса задачи с неделимостями и задачи с логическими (булевыми) переменными. [c.123]
К задачам с булевыми переменными относятся задачи выбора наилучших вариантов проектов (задачи по выбору оптимальных вариантов конструкций новых изделий, технологических процессов их производства, вариантов организации производства и т. п.), вариантов развития и размещения производства в отрасли и т. д. Особенно большое распространение задачи с булевыми переменными получили в последнее время. Новым и многообещающим направлением использования моделей с булевыми переменными является использование их при решении проблемы совершенствования теории и практики сравнительной экономической эффективности новой техники. Современные исследования в области решения этой [c.123]
Предположим, что для производства нового изделия оказались возможными два варианта проекта конструкции. Для первого варианта проекта конструкции оказались возможными три варианта проекта технологического процесса, для второго — два варианта. Известно, что фонды времени на выполнение работ по разработке проектов конструкции и технологических процессов строго лимитированы. Задача заключается в отыскании вариантов проектов конструкции и технологического процесса производства нового изделия, минимизирующих суммарные приведенные затраты на его проектирование и изготовление и удовлетворяющих условию ограниченности фондов времени на выполнение работ по проектированию. В действительности же наиболее реальной является многовариантная задача с большим количеством ограничивающих условий. Однако для того, чтобы избавиться от сложностей реальной экономической задачи по выбору проектных вариантов новой техники, учитывая, что общность рассуждений при этом не теряется, для исследования проблемы нелинейности в моделях с булевыми переменными взята такая тривиальная задача. [c.124]
Рассматриваемую задачу можно математически записать в виде линейной и нелинейной модели с булевыми переменными. Для составления линейной целочисленной модели возможны два пути. Первый путь заключается в том, что для каждого этапа проектирования (для этапа разработки проекта конструкции и для этапа разработки технологических процессов производства нового изделия) вводится свой массив булевых переменных. Для этапа разработки проекта конструкции вводятся булевы переменные z/t и г/2, которые равны единице, если выбираются соответственно первый или второй вариант проекта конструкции. Для этапа разработки технологических [c.124]
Ясно, что значение булевых переменных второго этапа зависит от значений булевых переменных первого этапа. Действительно, если выбран первый вариант проекта конструкции, то на втором этапе не всякая булева переменная может быть равна единице. В этом и проявляется связь-булевых переменных обоих этапов проектирования. Точнее, для осуществления первого варианта проекта конструкции не может быть выбран любой из пяти разработанных вариантов технологических процессов. Эта зависимость очень сильно усложняет задачу и отличает ее от обычных многоэтапных задач, в которых булевы переменные одного этапа не зависят рассмотренным образом от булевых переменных другого этапа. Примером таких моделей могут служить хорошо изученные модели развития и размещения производства. [c.125]
Для того, чтобы отразить тот факт, что при z/i= l могут равняться единице уц либо у , либо г/13 придется ввести новые переменные zu, z , zi3, 221, 222, связывающие булевы переменные обоих этапов. Булева переменная г (если /=il, то t=l, 2, 3, если /= 2, то =11, i2) равна единице лишь в том случае, если одновременно выполняются равенства У)=Л и у =. Во всех остальных случаях булева переменная гц равна нулю. Для составления модели введем еще следующие обозначения i, С2 — затраты на разработку первого и второго вариантов [c.125]
Булева переменная уц равна единице, если для производства нового изделия выбран /-и вариант проекта его конструкции и 1-й вариант технологического процесса его производства. В этом случае линейная модель выбора вариантов будет такой. [c.127]
Точных методов решения целочисленных нелинейных задач в настоящее время еще нет. Однако эти задачи можно свести к линейным целочисленным. Наша нелинейная модель, например, сводится к первой линейной модели следующим" образом. Вводятся булевы переменные [c.129]
В экономико-математической модели (4,24) — (4.31) булева переменная z/qj равна единице только в том случае, когда для производства изделия q-то наименования принимается /-и проектный вариант конструкции. [c.151]
Неравенство (4.26) означает, что общие затраты времени конструкторского отдела на выполнение работ и-го вида не должны превышать /Vu). Это неравенство обусловлено ограниченностью сроков разработки проектов конструкций изделий и ограниченностью числа конструкторов. Булева переменная г/qji равна единице в случае, если для производства изделия 9-го наименования по /-му проектному варианту конструкции будет принят i-й проектный вариант технологических процессов. [c.151]
Среди разработанных в монографии экономико-математических моделей, являющихся задачами дискретного программирования, часть представляет собой одноэтапные экономико-математические модели-задачи целочисленного линейного программирования, часть — многоэтапные, целочисленного нелинейного программирования. iB качестве переменных взяты булевы переменные. [c.187]
Точных методов решения целочисленных нелинейных задач в настоящее время нет. Однако нелинейные целочисленные задачи можно свести, к линейным целочисленным [122]. Сведем, например, задачу (4.24) — (4.31) к задаче целочисленного линейного программирования. Для этого любое произведение булевых переменных, входящее в условия задачи, необходимо заменить одной новой булевой переменной, а к системе ограничений экономико-математической модели добавить два линейных неравенства соответственно для каждой вновь вводимой булевой переменной. >В нашем случае [c.193]
Под моделью с нелинейностью второго порядка понимается такая модель, в которой имеются произведения двух булевых переменных. Если имеются произведения трех булевых переменных, то имеем модель с нелинейностью третьего порядка. [c.199]
Всего существует 402 типа булевых функций четырех переменных, к которым сводится все множество из 65536 функций. [c.101]
Задачи с булевыми переменными [c.20]
ПЕРЕМЕННЫЕ Целые, булевы хП ОГРАНИЧЕНИЯ - xi2 xi3 Лев. часть Знак Прав, часть [c.21]
Вид окна "Поиск решения" для задачи с булевыми переменными, [c.21]
Переменные, получающие значения 1 пли 0, носят название булевых переменных в честь английского математика Дж. Буля (1815—1864). [c.143]
В частном случае искомая переменная х, в результате решения может принимать не любое целое значение, а только одно из двух 0 либо 1. Чтобы такие переменные отличать от обычных, будем их вместо Xj обозначать 57-. И это уже будет означать, что в результате решения задачи 6 - может быть равным или О, или 1, то есть всегда 5 [0 1]. Такие переменные обычно называют булевыми в честь предложившего их английского математика Джорджа Буля (1815-1864). [c.128]
Кроме рассмотренного, существует другой путь составления линейной модели расматриваемой задачи. Этот путь заключается в том, что подсчитывается общее число проектных вариантов и каждому из них ставится в соответствие булева переменная. Схематично это выглядит следующим образом [c.127]
Но одно, а, может быть, во многих случаях и решающее обстоятельство позволяет думать, что применение нелинейных целочисленных моделей, с точки зрения приближенных методов их решения, предпочтительней, чем применение линейных моделей. Дело в том, что во второй линейной модели двухэтап-ная задача по выбору вариантов переводится в одноэтапную, так как вводится один массив булевых переменных. Этим самым подрывается возможность применения для ускорения сходимости приближенных методов различных эвристических приемов. В первой линейной модели, хотя и вводятся массивы булевых переменных для обоих этапов технической подготовки изводства, из-за промежуточного массива булевых переменных Zji, имеющих тот же смысл, что и во второй линейной модели, применение эвристических приемов затруднено. Ибо если для переменных у и уц можно сформулировать некоторые эвристические правила, то для переменных гц, служащих для связи переменных у и у — вряд ли. Бесспорно также, что. и размерность первой линейной модели значительно превосходит размерность нелинейной модели. [c.130]
В настоящее время разработаны две группы таких методов [60]. Первую группу составляют методы отсечения (метод целочисленных форм и др.). (Вторую — комбинаторные методы (метод ветвей и границ, аддитивный алгоритм и др.). Наибольшее распространение при решении задач с булевыми переменными получил аддитивный алгоритм Балаша. Для реализации этого метода на ЭВМ разработаны программы. Одна из таких программ, получившая широкое распространение, разработана 3. В. Коробковой [62]. Для того, чтобы воспользоваться этой программой, необходимо задачу целочисленного линейного программирования привести к виду [c.188]
В связи с тем, что модели задачи выбора наилучших проектных вариантов относятся к классу задач дискретного программирования с булевыми переменными, непосредственно воспользоваться одним из рассмотренных декомпозиционных алгоритмов не представляется возможным. Однако сама идея разбиения большой модели на ряд подмоделей и получения ее решения из решений этих подмоделей может быть использована для выбора наилучших проектных вариантов новых изделий. Наиболее приемлем в данном отношении алгоритм, предложенный А. Г. Аганбегяном, К. А. Багриновским и А. Г. Гранбергом [7]. [c.190]