Алгоритмы, применяемые при этом (итеративные алгоритмы методов последовательного улучшения плана), можно разделить на три класса [c.137]
Разработан целый ряд вычислительных приемов, позволяющих решать на ЭВМ задачи линейного программирования, насчитывающие сотни и тысячи переменных, неравенств и уравнений. Среди них наибольшее распространение приобрели методы последовательного улучшения допустимого решения (см. Симплексный метод, Базисное решение), а также декомпозиционные методы решения крупноразмерных задач, методы динамического программирования и др. Сама разработка и исследование таких методов — развитая область вычислительной математики. [c.172]
Итеративные алгоритмы методов последовательного улучшения плана 137 [c.468]
Методы последовательного улучшения допустимого решения (МПУ) 26, 196 [c.473]
Существование решения этой задачи подтверждается теоремами существования и единственности, утверждающими, что при некоторых разумных ограничениях из любой начальной точки х0 идет в начало координат оптимальная траектория, и притом только одна. Точное решение этой задачи неизвестно. Вместе с тем существуют достаточно удобные приближенные методы последовательных улучшений начальных значений. [c.88]
Решение этой задачи основано на методе последовательного улучшения начального решения. Из приведенных в таблице данных ясно, что один из маршрутов неприемлем и не используется, так как стоимость доставки единицы продукции чрезмерно высока (160 руб.). Для дальнейшего решения задачи необходимо установить начальное распределение. Оно может быть получено двумя способами а) если оно сделано опытным аналитиком и работниками. транспортной службы, то может быть достаточно близким к оптимуму б) использованием правила северо-западного угла . [c.196]
За прошедшие годы существенно развилась вычислительная техника. Внедрение электронно-вычислительных машин выдвинуло теперь на первый план вопросы автоматизации решения задач о рациональном раскрое. В первом издании эти вопросы освещались с учетом вычислительных возможностей тех лет, хотя необходимые алгоритмы для разработки машинных вычислительных программ уже содержались в книге. Отметим, в частности, метод последовательного улучшения плана раскроя, центральный для решения задач линейного программирования на ЭВМ, и метод построения шкалы индексов, по существу предвосхитивший метод рекуррентных соотношений динамического программирования. [c.3]
ПЕРВЫЙ МЕТОД НАХОЖДЕНИЯ МАКСИМАЛЬНО ЭКОНОМНОГО ПЛАНА РАСКРОЯ. (Метод последовательного улучшения раскройного плана) [c.37]
Знание отдельных наиболее благоприятных раскроев дает возможность попробовать сразу составить весьма экономный план и затем, в случае надобности, перейти к методу последовательных улучшений. [c.60]
Индексы преобладающих заготовок. Пусть из общего списка заготовок несколько заготовок — преобладающие — нужны в значительно большем количестве, чем все остальные. Допустим мысленно, что мы отдельно раскроим только преобладающие заготовки и определим их индексы и отдельно раскроим остальные заготовки и тоже определим их индексы, а затем разрешим применение смешанных раскроев и будем изменять план по общему методу последовательных улучшений плана раскроя ( 4 гл. I). [c.104]
Так как задача раскроя рулонного материала, по существу, сводится к основным задачам 1 и 2 ( 3 гл. I), то к этой задаче могут быть применены общие методы, изложенные в гл. I . Например, общий метод последовательных улучшений плана раскроя принимает в случае рулонного материала следующий вид [c.138]
Пользуясь общим методом последовательных улучшений раскройного плана ( 5 гл. I), составить план раскроя листов 3000 X 2100 X 6 мм на следующие комплекты заготовок [c.169]
В распоряжении вычислительных центров, как правило, имеются стандартные программы для решения на ЭВМ задач линейного программирования. По существу большинство из них реализует методы, эквивалентные описанному в этой книге методу последовательного улучшения плана. В зарубежной литературе он известен под названием модифицированного симплекс-метода. Упомянем публикации программ [c.222]
Один из выводов метода последовательных улучшений состоит в том, что этот список вовсе не обязателен для решения задачи ( ). Задачу часто можно решить, так и не узнав всей матрицы (ац) и даже числа N искомых неизвестных. Ведь в окончательном решении могут быть приняты равными нулю все Xi, кроме нескольких (не более чем п шт.), и только эти несколько xi достаточно найти. [c.224]
Метод последовательного улучшения плана. Он состоит в том, что в план вводится более эффективный неиспользуемый ранее способ, за счет которого достигается увеличение выпуска продукции. Находится же этот способ в процессе определения оценок. Последовательно применяя такие улучшения, приходят к наилучшему плану. [c.19]
Для того чтобы лучше понять, каков эффект метода последовательного улучшения плана, дадим такое пояснение. Представьте себе, что из урны, в которой имеется миллион шаров с произвольными номерами, вы хотите извлечь шар с наибольшим номером. Чтобы этого добиться, вам придется чуть ли не 1000000 раз вытаскивать шары из урны, не возвращая их назад. Времени это, конечно, займет очень много. Допустим теперь, что вам помогает... волшебник и после очередного извлечения он уничтожает шары в урне с номерами, меньшими [c.19]
Так вот, метод последовательного улучшения плана и выполняет функции этого волшебника. После того как вычислена значение целевой функции в какой-нибудь вершине, из дальнейшего рассмотрения исключаются все вершины, дающие худшие значения целевой функции, и переход производится непременно к лучшей вершине. [c.20]
В качестве иллюстрации рассмотрим применение метода последовательного улучшения плана к нашей задаче о раскрое. [c.20]
Применение описанных методов улучшения плана чередуется с проверкой условий оптимальности, т. е., получив новый план, мы прежде всего, определяя оценки, выясняем, не оптимален ли он. Если да, то решение заканчивается. Если же нет, то снова применяется метод последовательного улучшения плана. Доказано, что с помощью этого метода за конечное число улучшений можно прийти от любого допустимого плана [c.21]
Использование теоремы двойственности и связанного с ней признака оптимальности допустимого плана лежит в основе большинства эффективных методов решения задач линейного программирования. В 2 было продемонстрировано решение задачи о раскрое с помощью метода последовательного улучшения плана. Близко к нему примыкает симплекс-метод, разработанный американским математиком. Дж. Данцигом. Здесь мы приведем лишь краткое описание этого метода. [c.31]
Заметим, что описанный ранее метод последовательного улучшения плана более эффективен, чем симплекс-метод, если число переменных в задаче превосходит число ограничений. [c.35]
Описанный вариант симплекс-метода не является единственным. На практике обычно употребляется более совершенный вариант — модифицированный симплекс-метод, связанный с использованием двойственной задачи (оценок) и по существу близкий к описанному выше методу последовательного улучшения плана. [c.35]
Экстремальные задачи, в которых либо ограничения, либо целевая функция (случай, который мы рассматриваем ), л иба и то и другое нелинейны, называются задачами нелинейного программирования. К сожалению, пока не имеется общих методов, подобных методу последовательного улучшения плана или симплекс-методу в линейном программировании, которые позволяли бы решать любые задачи нелинейного программирования. Поэтому мы сможем указать на возможность решения лишь для некоторых, впрочем, весьма важных частных случаев. [c.72]
Так как в основе метода последовательного улучшения плана лежит использование о. о. оценок и, кроме того, роль этих оценок чрезвычайно велика как в теоретических вопросах математического программирования, так и в вопросах его практического использования, целесообразно более подробно остановиться на изучении их свойств. [c.22]
Использование о. о. оценок лежит в основе не только метода последовательного улучшения плана, о котором мы говорили выше, но и многих других методов решения задач линейного программирования. В качестве примера упомянем метод корректировки оценок, Исходными в этом случае являются приближенные значения оценок, по которым находятся наиболее рентабельные (при этих оценках) способы. Из этих способов формируется план, лишь частично соответствующий заданию или, на языке математики, удовлетворяющий только некоторым ограничениям, т. е. план, кото- [c.24]
Рассмотрим теперь процесс формирования оптимального плана транспортной задачи. Возьмем конкретный числовой пример и, применив метод последовательного улучшения, детально покажем, как строится такой план. [c.49]
Симплекс-метод — метод последовательного улучшения плана. [c.79]
По аналогии с другими методами последовательного улучшения плана очередной поток получается за счет ввода в него одной дуги и вывода другой. Если условия критерия оптимальности нарушаются сразу для нескольких дуг, то для ввода имеет смысл выбрать ту, на которой достигается максимальное отклонение цены от разности потенциалов соединяемых вершин. Пусть для ввода выбрана некоторая дуга dl = (s, /), направленная из вершины s в вершину t. Из правил построения потенциалов следует, что в остове существуют две цепи, одна из которых соединяет базовую вершину /0, потенциал которой был принят равным нулю, с s, а другая — /0 с t. Если дополнить остов дугой df, образуется единственный цикл. Построенный [c.126]
Если мы имеем дело с моделями линейного программирования, то задача при этом бывает поставлена таким образом, что необходимо определить значения переменных при наличии в модели уравнений и неравенств, имеющих численное значение коэффициентов при переменных. В результате решения указанных уравнений получается оптимальный план, к которому можно подойти методами последовательного улучшения начального плана, уточнения оценок или сокращения невязок. [c.31]
Метод последовательного улучшения плана следует отнести к методам первой группы, в которых оптимальный план достигается цри движении по опорным планам, составленным для прямой задачи. [c.184]
В тех случаях, когда при решении задач начальный план составляют с учетом ограничений, обусловленных в задаче, а затем путем последовательных улучшений исходного плана приходят к удовлетворению условий целевой функции, мы имеем дело с методами последовательного улучшения плана. [c.184]
Метод последовательного улучшения плана складывается из следующих этапов, необходимых для решения задач способа вычислений опорного плана установления критерия, позволяющего проверить оптимальность плана на каждом шаге способа, позволяющего получить план, более близкий к оптимальному. [c.184]
Если в методе последовательного улучшения плана приближение к максимуму линейной формы происходит снизу. то в методе последовательного уточнения оценок приближение к оптимуму осуществляется сверху. [c.186]
При решении задач методами, относимыми к группе методов последовательного улучшения плана, задается исходный план производства, путем его анализа устанавливается его оптимальность или пути его улучшения. Для оптимального плана производства определяется система оценок производственных факторов, называемая планом цен. [c.187]
Здесь нами построена последовательность вершип x(l x(z х(3) таких, что каждые два соседних элемента последовательности являются соседними вершинами множества допустимых решений, причем при движении вдоль последовательности значение критерия возрастает. В последней точке достигается максимум. Подобные методы, основанные на последовательном переходе от одной вершины к другой, соседней с большим (или в крайнем случае не меньшим) значением критерия, получили название методов последовательного улучшения допустимого решения. Их использование определяется следующими преимуществами. Во-первых, переход в соседнюю вершину требует значительно меньшего объема вычислений, чем поиск некоторой [c.52]
В базис z-задачи вводится вектор р , для которого соответствующий коэффициент линейной формы (9) равен <ть= (С, xv . ) Дальнейшее решение z-задачи проводится по правилам второго алгоритма метода последовательного улучшения плана. Таким образом, из приведенной схемы видно, что решение рассматриваемой задачи сводится к многократному решению однопродук-товых задач. [c.67]
Вычислительным методом для решения такой задачи служит типовой алгоритм методов линейного программирования, в том числе симплексного метода, т. е. метода последовательного улучшения производственной программы с помощью итерирования. За исходную точку расчетов принимается некоторый план производства по каждому изделию и затем в последовательном порядке изменяются значения прироста переменных. [c.266]
Следует отметить тот принципиальный вывод, что рассмотренный на этом примере метод последовательных улучшений готового раскройного плана при наличии перечня воможных раскроев (роль этого перечня в данном случае играла табл. 2) дает возможность строго определенными математическими операциями заведомо дойти до максимально экономного раскройного плана. При "этом основная операция состоит в решении несложных систем уравнений первой степени. [c.41]
С. Каримбердиева. Метод последовательного улучшения плана.— Тр. по вычисл. матем. и технике. Работы молодых ученых. Ташкент, 1962. [c.222]
Метод последовательного улучшения плана состоит в том, что в план вводится более эффективный неиспользо-вавпшйся ранее способ, за счет которого достигается увеличение выпуска продукции. Этот способ находят в процессе определения оценок. Последовательно вводя такие способы, улучшают план до тех пор, пока не получат оптимальный план. [c.19]
Классическим методом решения ЗЛП стал симплекс-метод, получивший также в литературе название метода последовательного улучшения плана, разработанный в 1947г. американским математиком Джорджем Данцигом. [c.33]