Наряду с (4.64) рассмотрим задачу выпуклого программирования с линейными ограничениями [c.133]
Среди математических методов наиболее разработаны методы линейного программирования. Слово линейное определяет математическую сущность метода, которая заключается в том, что с его помощью решают задачи с линейными связями и ограничениями, т.е. если выразить задачу в математической форме, то в ней все неизвестные будут в первой степени. [c.134]
На первом шаге решается задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. Если полученное оптимальное решение оказывается целочисленным, то оно является также решением исходной задачи. В противном случае следует ввести дополнительные ограничения, порождающие (вместе с исходными ограничениями) новую задачу линейного программирования, решение которой оказывается целочисленным и совпадает с оптимальным решением исходной целочисленной задачи. [c.466]
Машина Оптимум-2 (рис. 3.5) предназначена для решения транспортной задачи линейного программирования в общей постановке транспортной задачи с дополнительными ограничениями на время перевозок транспортной задачи с частично заменяемыми продуктами и неоднородной транспортной задачи позволяет определить [c.133]
В 1—2 рассматриваются стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. В 1 оператор вероятности применяется к каждой строке ограничений в отдельности, а в 2 — одновременно к совокупности всех ограничений. В обоих параграфах рассматриваются такие распределения случайных параметров условий, при которых эквивалентные детерминированные задачи оказываются задачами выпуклого программирования. Параграф 3 посвящен построению эквивалентных детерминированных моделей для общей одноэтапной стохастической задачи с вероятностными ограничениями, порожденной, вообще говоря, нелинейной моделью математического программирования. В 4 рассматриваются две простые, но представляющие интерес для приложений частные модели стохастических задач, в которых решения определяются в детерминированных векторах. Параграфы 5—6 посвящены стохастическим моделям оценки невязок с детерминированными оптимальными планами. В 5 рассматривается классификация таких моделей. В 6 исследуются условия, при которых соответствующие детерминированные эквивалентные задачи являются задачами выпуклого программирования. Ясно, что только в таких случаях можно говорить о конструктивных методах решения задачи. [c.62]
В связи с изложенными соображениями о трудностях, возникающих при анализе задач стохастического программирования с вероятностными ограничениями, представляет интерес предложенный в [246] приближенный подход к выбору решения подобных задач. Здесь предполагается, что принимающему решение в условиях неполной информации важно во что -бы то вди стало сократить вероятность чрезвычайного события, связанного с превышением целевой функцией некоторого порога. Вероятность этого события так же, как и вероятности выполнения ограничений, может быть оценена сверху с помощью неравенства Чебышева или различных его модификаций. Таким образом, вместо минимизации вероятности соблюдения некоторого неравенства (например, вероятности того, что линейная форма не превысит заданный порог) предлагается минимизировать верхнюю границу этой вероятности. Вместо ограничений снизу вероятностей некоторых событий (например, соблюдения неравенств со случайными коэффициентами) предлагается ограничить снизу верхние границы этих вероятностей. Можно указать случаи, когда границы,. получаемые с помощью неравенства Чебышева или его модификаций, оказываются недостаточно эффективными. Кроме того, детерминированные экстремальные задачи, получаемые при замене вероятностного показателя качества решения и вероятностных ограничений их оценками, могут оказаться невыпуклыми задачами. Тем не менее указанный приближенный подход, не требующий информации о распределении случайных параметров условий, может в ряде случаев, как об этом свидетельствуют примеры, рассмотренные в (246], оказаться полезным для оценки решения трудоемких стохастических задач с вероятностными ограничениями. [c.70]
В п. 1.2 рассмотрена линейная стохастическая задача с вероятностными ограничениями, в которых случайными были только независимые между собой составляющие вектора Ь. Эквивалентная детерминированная задача (1.5) — (1.7) в этом случае оказалась линейной. Несколько сложнее обстоит дело в том случае, когда вероятностное ограничение задано в форме (б), даже если при этом отдельные компоненты вектора b независимы между собой. Эквивалентная детерминированная задача в этом случае формулируется следующим образом. Требуется вычислить детерминированные векторы х и g(x) (или х и 5), при которых [c.71]
Таким образом, детерминированная задача, эквивалентная стохастической задаче с вероятностными ограничениями, в которой случайные составляющие вектора Ъ независимы между собой и распределены по экспоненциальному закону, оказывается задачей. линейного программирования. [c.73]
В предыдущих параграфах рассмотрены частные стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. Специфика стохастического характера условий позволила в каждом из рассмотренных случаев построить эквивалентную детерминированную задачу. Ниже приводится достаточно общий прием построения детерминированного эквивалента для широкого класса задач стохастического программирования, решение которых определяется среди детерминированных векторов. [c.74]
По аналогии с тремя формами записи области определения линейных стохастических задач с вероятностными ограничениями приведем три формы записи вероятностных условий для общего случая [c.74]
В литературе исследуются и (при некоторых предположениях относительно распределения случайных параметров условий задачи) решаются задачи с безусловными вероятностными ограничениями, в которых решающие правила заранее предполагаются линейными. Решение многоэтапных стохастических задач с безусловными ограничениями при достаточно общих предположениях относительно допустимых решающих правил требует преодоления серьезных теоретических и вычислительных трудностей. В ряде случаев исследование упрощается при сведении задачи с безусловными статистическими ограничениями к эквивалентной стохастической задаче с условными статистическими ограничениями. [c.201]
Если, кроме того, составляющие векторов i детерминированы, то многоэтапная стохастическая задача с вероятностными ограничениями сведется к задаче линейного программирования с блочно-треугольной матрицей условий [c.239]
Отметим, что многоэтапные задачи стохастического программирования не являются тривиальными обобщениями двухэтапных задач. Многие результаты, справедливые для двухэтапных задач общего вида, неверны для многоэтапных. Например, оптимальные решающие правила линейных двухэтапных задач с вероятностными ограничениями — кусочно-линейные функции от некоторых случайных параметров условий задачи. Для многоэтапных задач это утверждение, вообще говоря, неверно [70]. [c.256]
Наличие универсальных эффективных методов решения задач линейного программирования, носящих ясно выраженный алгоритмический характер (характер четкого предписания), позволяет успешно программировать и реализовать их решение на ЭВМ. Имеется большой набор программ для этой цели, дающих возможность решать задачи с числом ограничений порядка 100 и более и с сотнями и тысячами переменных (способов). Решение требует несколько минут (иногда часов) машинного времени. Задачи меньшего объема теми же методами успешно решаются вручную с применением настольных счетных машин. [c.35]
Иногда считают, что в модель допустимо вводить любое число переменных и благодаря этому можно учесть все многообразие ингредиентов. Однако такая гипотеза о потенциальной осуществимости получения и ввода любого объема информации и расчета модели любой размерности очень далека от действительности. Несмотря на эффективность методов решения (особенно линейных задач) и высокие технические характеристики современных ЭВМ, и на них затруднительно получать обозримое решение и осуществлять анализ задач с числом ограничений, превышающим несколько сотен. [c.172]
Первое выражение называется целевой функцией (равно произведению прибыли на единицу продукта с,- на выпуск этого продукта Xj). Остальные уравнения составляют линейные ограничения, которые означают, что расход сырья, полуфабрикатов, качество продукции, мощности, т. е. исходные ресурсы, не должны превышать заранее установленных величин / /. Коэффициенты а,7 — постоянные величины, показывающие расход ресурса на /-и продукт. Задача может быть решена при неотрицательности переменных и при числе неизвестных большем, чем число ограничений. Если последнее условие не удовлетворяется, то задача является несовместной. [c.127]
Первое выражение называется целевой функцией. Оно определяется произведением прибыли на единицу продукции С,- на выпуск каждого ее вида Xj. При этом п — количество видов продукции, включаемых в план. Остальные уравнения характеризуют линейные ограничения, которые означают, что расход сырья, полуфабрикатов, производственных мощностей, т.е. потребляемые ресурсы, не должны превышать заранее установленных величин bf, а качество продукции должно быть не ниже требований стандартов. Коэффициенты а у — постоянные величины, показывающие расход ресурсов / на у -й продукт. Задача может быть решена при неотрицательности переменных и при числе неизвестных большем, чем число ограничений. Если последнее условие не удовлетворяется, то задача является несовместной. [c.18]
Зависимость отдельных составляющих целевой функции от числа пунктов разгрузки, включенных в какой-либо вариант внешнего транспортного обеспечения и условно рассматриваемых как непрерывные функции в области целочисленных величин числа пунктов разгрузки пгв, представлена на рис. 27. Как видно из рисунка, с увеличением числа пунктов разгрузки возрастают суммарные затраты на их организацию и уменьшаются транспортные расходы по доставке труб к месту работ. Следовательно, целевая функция как сумма указанных составляющих имеет экстремум при некотором значении числа пунктов разгрузки. Учитывая нелинейную зависимость функционала и его отдельных составляющих от числа вводимых пунктов разгрузки и искомых переменных, для решения поставленной задачи не могут быть применены классические методы математического программирования (например,. линейного). Как известно из курса высшей математики, математическое программирование — область математики, разрабатывающая теорию и методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных. Само название программирование взято из линейного программирования, где оно обычно обозначает распределение наилучшим образом ограниченных ресурсов для достижения поставленных целей. Следовательно, термин программирование здесь можно заменить термином планирование . [c.145]
Легко заметить, что эта задача отличается от транспортной задачи лишь наличием величин Кц в ограничениях одного из типов (отсюда и одно из названий такой задачи — -задача). Для обобщенной транспортной задачи также разработаны алгоритмы решения, более эффективные, чем алгоритмы решения общей задачи линейного программирования. Транспортная задача проще обобщенной транспортной задачи с точки зрения алгоритма ее решения с помощью ЭВМ, а обобщенная транспортная задача проще общей задачи линейного программирования. При построении моделей их стараются сформулировать так, чтобы свести проблему к возможно более простой задаче. Конечно, такое сведение не должно осуществляться за счет искажения существенных черт изучаемой экономической системы. [c.152]
Можно доказать и более общее утверждение о свойствах двойственных переменных. При описании метода множителей Лагранжа для задач с ограничениями типа равенств мы показали, что множитель Лагранжа равен производной критерия по правой части равенства. Этим же свойством множители Лагранжа обладают и в задачах линейного программирования [c.56]
Линейное программирование — система математических методов анализа и решения задач отыскания экстремума (минимума или максимума) линейной функции при линейных ограничениях. Используется в экономике в задачах, связанных с ограничениями по ресурсам. [c.534]
Ситуации такого рода, требующие максимизации или минимизации заданного линейного выражения зависимости от различных линейных ограничений, или сдержек, могут быть разрешены с помощью линейного программирования. В данной главе представлены базовые приемы решения задач линейного программирования с помощью графических и других аналитических средств. [c.261]
При решении задачи можно выбрать метод экстраполяции оценок переменных для каждого шага поиска — линейная или квадратичная (для задач с нелинейной целевой функцией), метод численного дифференцирования для целевой функции — прямые или центральные разности (для задач с нелинейной целевой функцией), метод поиска — метод Ньютона (требуется много оперативной памяти) или метод сопряженных градиентов (больше итераций). Основным ограничением модели является максимальное число переменных — 200. Несколько оптимизационных моделей на одном листе можно сохранять и загружать по мере необходимости. [c.457]
Исходная задача (2.28) в результате фиксации варьируемых векторов RJ на некоторых- номинальных значениях К° может быть приведена к обычной задаче линейного программирования с фиксированными параметрами. Далее стандартной симплекс-процедурой осуществляется решение задачи с фиксированными параметрами. На f-й итерации выявляется несовместность системы ограничений (2.28) при номинальных значениях Rj = Rj. В этом случае базисное решение 1- итерации [c.33]
Одной из подобных постановок, учитывающих структурные и технологические особенности основного производства НПП, является задача с построчными вероятностными ограничениями, порожденная моделью линейного программирования [43] [c.57]
Рассматриваемая стохастическая задача при этом преобразуется в детерминированную задачу выпуклого программирования с линейной целевой функцией и квадратичными ограничениями. [c.69]
По аналогии с рассмотренным выше случаем, введя условие viv = = М -[ (aiv-aiv) (fi - < /,/,) , учитывающее корреляцию между aiv и Vi , при 7 >0,5 и нормальном распределении случайных параметров стохастической задачи получим детерминированный аналог с линейной целевой функцией и квадратичными ограничениями [c.70]
В постановке (3.74)-(3.79) искомыми (оптимизируемыми) величинами в подзадачах (3.75) — (3.79) являются компоненты векторов -/Г,, и К — случайные величины a iv и . При формировании подзадач эти величины в ограничениях вида (3.77), (3.78) оказываются только в правой части, что обеспечивает линейный вид их детерминированных аналогов. При линейном виде функции H(aiv), описывающей параметрические связи, в соответствии с рассмотренными в [47] случаями детерминированный аналог задачи (3.74) —(3.79), в отличие от (3.73), после соответствующих преобразований может быть представлен в виде задачи обобщенного линейного программирования, решение которого осуществляется на базе известного алгоритма [16]. [c.72]
В идеальном варианте предварительная обработка должна дать такой набор признаков, чтобы задача оказалась линейно отделимой, — классификация после этого существенно упрощается. К сожалению, это редко удается сделать. Как правило, в нашем распоряжении имеется лишь ограниченный набор образцов, и часть из них используется для проведения границ, разделяющих классы ( построение классификатора ). Качество классификатора по отношению к имеющимся примерам измеряется оценкой. При последующей работе классификатора с новыми образцами происходит обобщение. Возможные способы оценить способность к обобщению мы рассмотрели в предыдущей главе. [c.44]
В некоторых случаях условие целочисленности переменных имеет принципиальное значение и позволяет исследовать новый класс моделей. В разделе "Использование целочисленных переменных в задачах линейного программирования" мы рассмотрим такие типы моделей. Однако следует иметь в виду, что добавление этого ограничения исключает использование эффективных методов решения задач линейного программирования (которые будут упомянуты в следующих разделах). Задача с целочисленными переменными гораздо более сложна для исследования, а алгоритмы ее решения гораздо менее универсальны и эффективны. [c.46]
Так, в линейном программировании поочередное использование прямых методов и проверки необходимых условий оптимальности составляет суть описанных выше способов последовательного улучшения плана, симплекс-метода и др. В нелинейном программировании пока еще не созданы столь универсальные способы решения задач. Конечный алгорифм имеется лишь для задачи квадратичного программирования, т. е. задачи с линейными ограничениями и целевой функцией, задаваемой полиномом второй степени. Поэтому, рассматривая общую задачу нелинейного программирования, приходится демонстрировать по отдельности методы первого и методы второго направления. [c.100]
Методы линейного программирования. Первые исследования по постановке и разработке методов решения линейных оптимизационных задач были проведены в тридцатые годы Л. В. Канторовичем. В 1939 г. им была опубликована книга Математические методы организации и планирования производства , в которой впервые был ш сдложен эффективный метод решения задач оптимизации для моделей с линейными ограничениями и линейным критерием. Однако достоинство книги состояло не только в этом — в пей было показано, что модели экономических систем широкого класса могут быть достаточно точно построены на основе использования линейных соотношении. В дальнейшем эти идеи получили широкое распространение, и в настоящее время липейиые модели и методы оптимизации в таких моделях составляют основу, на которой базируется исследование прикладных экономических задач. [c.50]
Чувилина А. Я. Программа решения на ЭВМ М-20 модифицированного симплекса для линейных задач с двусторонними ограничениями на переменные.— В кн. Руководство к использованию программ решения задач линейного программирования на ЭВМ М-20 и БЭСМ-4. Под ред. А. А. Тюни-на. Новосибирск. 1970, с. 140—154 (Ротапринт). [c.141]
Во многих задачах управления в условиях неполной информации, свя занных с повторяющимися ситуациями, нет необходимости в том, чтобы ограничения задачи удовлетворялись при каждой реализации случая (или, как говорят, при каждой реализации состояния природы). Затраты на накопление информации или другие затраты, обеспечивающие исключение невязок в условиях задачи, могут превышать достигаемый при этом эффект. Часто конкретное содержание задачи требует лишь, чтобы вероятность попадания решения в допустимую область превышала некоторое заранее заданное число а>0. В тех случаях, когда возможные невязки в отдельных ограничениях вызьшают различный ущерб, целесообразно дифференцированно подходить к разным условиям. Чтобы уравновесить ущерб, определяемый невязками в разных условиях задачи, естественно ограничить снизу вероятность выполнения каждого из них различными числами а >0. Обычно аг>]/2- Подобные постановки задач стохастического программирования называются моделями с вероятностными ограничениями. Если коэффициенты линейной формы сх задачи детерминированы, то показатель 1 качества (1.1) является в то же время и целевой функцией задачи с вёроятност-ными ограничениями. Если компоненты вектора с случайны , TQ в качестве целевой функции задачи с вероятностными ограничениями обычно выбирают математическое ожидание линейной формы (1.1) или вероятность превышения линейной формой сх некоторого фиксированного порога. [c.9]
При линейных ограничениях выбор показателя качества идентификации в виде положительно определенной квадратичной формы (6.14) вполне оправдан. Модели квадратичного стохастического программирования поддаются конструктивному анализу. Учет нелинейных ограничений вида (6.15)-—(6.17) приводит к евылуклой и несвязной области допустимых планов. Исследование задач с. такими ограничениями связано с большими вычислительными трудностями независимо от выбора целевого функционала. В таких задачах выбор критерия качества иденти- фикации определяется главным образом содержательными соображениями. Трудности, связанные с упрощением вычислительной процедуры, отходят здесь на второй план. [c.49]
Приведем некоторые классы линейных стохастических задач с вероятностными ограничениями, для которых детерминированные эквива- [c.70]
Настоящая глава посвящена многоэтапным стохастическим задачам с условными ограничениями и априорными решающими правилами. Качественный анализ таких задач связан с существенно большими трудностями, чем исследование стохастических задач с апостериорными решающими правилами. В общем случае для задач с априорными решающими правилами несправедливы теоремы двойственности, подобные тем, которые доказаны в предыдущей главе для задач с апостериорными решениями. Во многих случаях детерминированные эквиваленты задач с априорными решающими правилами оказываются многоэкстремальными моделями. Трудности, с которыми сопряжено исследование таких моделей, вынуждают сузить диапазон рассматриваемых задач по сравнению с кругом задач, обсуждаемых в предыдущей главе. Мы ограничимся здесь1 главным образом линейными задачами с условными вероятностными ограничениями. [c.233]
Т. о., при реализации МПУ на каждой итерации процесса требуется находить решения двух систем лппеитых уравнений порядка т (для базисных неременных н для оценок). Способ, к-рым эти решения находятся, п является основной отличит, чертой различных вычислит, вариантов МПУ. Напр., в методе потенциалов для трансп. задачи переменные, входящие в систему, последовательно выражаются друг через друга по рекуррентным формулам. Др. широкий класс задач, в к-рых использование специфики ограничений значительно расширяет возможности числ. методов,— это задачи с блочными ограничениями, где переменные разбиваются на группы, имеющие собств. групповые ограничения. Системы линейных ограничений в таких задачах допускают более эффективные методы решения. [c.357]
Методы линейного программирования разработаны для проблем оптимизации, затрагивающих линейные функции пригодности или расходов с линейными ограничениями параметров или входных переменных. Линейное программирование обычно используется для решения задач по распределению активов. В мире трейдинга одно из возможных применений линейного программирования СОСТОИТЕ поиске оптимального размещения денежных средств в различные финансовые инструменты для получения максимальной прибыли. Если оптимизировать прибыль с учетом возможного риска, то применятьлинейные методы нельзя. Прибыль с поправкой нариск не является линейной функцией весов различных инвестиций в общем портфеле, здесь требуются другие методы, к примеру генетические алгоритмы. Линейные модели редко бывают полезны при разработке торговых систем и упоминаются здесь исключительно в ознакомительных целях. [c.59]
Шер А.П. Решение задачи математического программирования с линейной целевой функцией в размытых ограничениях //Автоматика и телемеханика 1980г.,№7// [c.50]
В этом разделе мы рассмотрим решение задачи линейного программирования с помощью графических методов. Необходимо отметить, что такой метод имеет практический смысл только при рассмотрении двух неизвестных переменных (например, х и у), и он непригоден при решении задач с более, чем двумя неизвестными. Так, если руководитель производства Стенлюкс захочет определиться по количеству трех и более различных моделей холодильников, то в этом случае графический метод применять нельзя. Аналогично, аналитик по инвестициям Вили-Макен не сможет пользоваться графическим методом при оптимизации портфеля из более чем двух акций. То есть вы видите, что графический метод крайне ограничен. Однако он дает полезное представление о том, как вести поиск оптимальных решений, что может оказать помощь при анализе более сложных задач с большим количеством переменных. [c.266]
Известно, что если расширенная матрица условий (5.1) имеет линейно зависимые строки, то задача ЛП, как правило, некорректна. Напомним, что такой задачей ЛП является транспортная задача с замкнутой системой ограничений [93 j. Для задач ЛП общего вида в связи с этим заметим, что ввиду приближенного задания исходных данных условие независимости строк матрицы А практически непроверяемо. [c.144]
Предлагаемый порядок оперативного планирования рассчитан на широкое применение электронно-вычислительной техники. Разработанные экономико-математические модели могут быть реализованы на ЭВМ по стандартным программам. На первом этапе планирования в Главном вычислительном центре АСУнефтеснаб РСФСР предлагается решать сетевую транспортную задачу линейного программирования с дополнительными ограничениями, на втором этапе в кустовых вычислительных центрах этой организации — многопродуктовую транспортную задачу линейного программирования в матричной постановке. [c.33]
Анализ математической модели задачи показывает, что данная задача относится к задачам нелинейного программирования, а именно к задаче отыскания экстремума нелинейной се-парабельной функции при линейных ограничениях. Для решения задач размещения и развития отрасли используются в основном приближенные методы. Нами предлагается решать задачу с помощью последовательных приближений. На каждом шаге алгоритма (для зафиксированных значений грузооборота неф- [c.47]
Однако количество угловых точек области допустимых планов растет очень резко с ростом числа переменных и особенно числа ограничений. Так, для небольшой задачи линейного программирования с 20 переменными и 10 ограничениями число угловых точек составляет около 30 млн., а для задачи с 10 переменными и 20 ограничениями это число может достигать 47 трлн. (47 х 1012). Чтобы сосчитать значения целевой функции во всех этих точках, компьютеру, выполняющему миллион арифметических операций в секунду, потребуется около года непрерывной работы. Вместе с тем ваш персональный компьютер, используя надстройку "Поиск решения" MS-Ex el, решит такую задачу за доли секунды. Дело, разумеется, в том, что MS-Ex el использует эффективные алгоритмы решения задач. Эти алгоритмы не перебирают все угловые точки подряд, а, начав с любой из них, выбира- [c.60]
Теперь, чтобы превратить задачу об оптимальном плане с учетом постоянных издержек в задачу целочисленного линейного программирования, необходимо заменить "логическую" связь значений 7 иХ4 еще одним линейным условием. Фактически речь идет о том, что если оптимизационный алгоритм "согласен" положить 7= 1 и уменьшить прибыль Р на величину F = 400 у.е., то ограничений на производство "Белки" нет (Х4 > 0). Если же алгоритм "желает" положить 7 = 0, то ему придется отказаться от производства "Белки" (Х4 = 0). Такое своеобразное "мигающее" ограничение наХ4, которого нет, если 7= 1, и которое появляется, если 7= 0, можно записать в виде линейного неравенства следующим образом [c.104]