Существует много частных способов (например, способ Фогеля, методы потенциалов, дифференциальных рент, способ Лебедева — Тихомирова, венгерский метод и др.), а также универсальных методов (например, алгоритм симплекс-метода) решения задач линейного программирования с такого рода условиями. Представляет интерес, как сам результат вычисления, так и его интерпретация. [c.246]
Данциг Дж. (Вуд М.) 1947 Разработали универсальный алгоритм решения задач линейного программирования (названный Дж. Данцигом симплекс-методом). [11] [c.53]
Симплекс-метод (аналитическое решение задач линейного программирования) — это алгоритм формального пересчета вариантов решения задачи с последовательным движением к оптимальному решению. Каждый шаг алгоритма расчетов улучшает предыдущее решение. [c.122]
В четвертой главе выясняется, каким образом производить учет не одного сообщения об относительной важности критериев, а целого набора такого рода сообщений. Сначала подробно разбирается случай двух сообщений. В частности, выясняется, что при определенных значениях числовых коэффициентов относительной важности вполне возможен случай, когда один критерий важнее другого, а тот, в свою очередь, важнее первого. В этой же главе изучается вопрос непротиворечивости произвольного набора информации об относительной важности критериев. Приведены три утверждения, с помощью которых всегда можно проверить является ли определенный набор информации противоречивым или нет. Далее исследуется вопрос учета произвольного набора количественной информации об относительной важности критериев и предлагается отличный от упомянутого ранее так называемый алгоритмический подход. Для случая конечного множества возможных решений формулируется алгоритм этого подхода, использующий симплекс-метод решения канонической задачи линейного программирования. [c.13]
Заметим также, что если "Запасы" поставщиков и "Заказы" потребителей выражены целыми числами, то и все перевозки в оптимальном плане, как очевидно из самого метода решения задачи, будут целыми. Напомним, что общие алгоритмы решения ЛП-задач (например, симплекс-метод) отнюдь не гарантируют получения целочисленных решений, даже если во всех ограничениях фигурируют целые числа. [c.126]
Введение в транспортную задачу или в задачу о назначениях не свойственных им дополнительных ограничений приводит к тому, что эффективные "транспортные" методы решения таких задач (метод "северо-западного угла", циклические перестановки и т.п.) перестают быть применимыми. В этом случае задача будет решаться с помощью общих алгоритмов решения ЛП-задач (например, симплекс-методом). Помимо того что эти методы менее эффективны, они не могут гарантировать целочисленного решения, которое обычно предполагается в транспортной задаче и абсолютно необходимо в задаче о назначениях. Прямо е требование [c.143]
Перейдя к вектору — g, получим вторую точную грань Р, соответствующую данному набору индексов М. В настоящее время разработано большое число алгоритмов точного решения задачи Л. Все они объединяются общим термином симплекс-метод, однако различают прямые и двойственные варианты симплекс-метода. С этими двумя вариантами связаны две основные качественные идеи, в той или иной мере лежащие в основании большинства алгоритмов как точного, так и приближенного решения задачи линейного программирования. [c.419]
Подход к задаче управления предельно-допустимыми выбросами загрязняющих веществ с позиций эколого-экономической оценки причин, вызывающих сверхнормативное загрязнение, позволил применить для ее решения метод линейного программирования, в частности симплекс-алгоритм, и получить значения коэффициентов нормирования выбросов, несущих эколого-экономическую информацию. [c.290]
Для решения задачи (нахождения оптимальных коэффициентов нормирования Х ) применим симплекс-алгоритм /1/, который удобно табулируется и решается за конечное число базисов. [c.291]
В заключение настоящего пункта обобщим изложенные вопросы и приведем схему алгоритма симплекс-метода для решения задачи максимизации. Она включает однократно выполняемый 0-этап и повторяемый конечное число раз 1-этап (стандартную итерацию). [c.40]
Прямое решение задачи детерминированного эквивалента, в котором условные вероятности повторно вычисляются на каждом шаге для всех информационных траекторий. Программы для решения задач линейного и квадратичного программирования очень большой размерности имеются в наличии и способны решать задачи, используя соответственно стандартные алгоритмы линейного программирования (т.е. симплекс-метод и метод внутренней точки) и квадратичного программирования (итеративный алгоритм, или на основе метода внутренней точки). [c.35]
В соответствии с теоремой 4.12 проверка справедливости соотношения у >м У" сводится к решению канонической задачи линейного программирования (4.27). Это решение может быть осуществлено с помощью известного алгоритма симплекс-метода. Такой способ проверки соотношения у1 >м у" удобен при создании общего алгоритма построения оценки сверху в случае конечного множества возможных векторов Y. Если же требуется решить задачу невысокой размерности вручную , то более удобным оказывается использование следующего результата, который представляет собой частный случай теоремы 4.12, установленный в ходе доказательства этой теоремы. [c.127]
Транспортная задача и задача о назначениях - это частные задачи линейного программирования. Для них в принципе могут быть использованы общие методы решения ЛП-задач (например, симплекс-метод). Однако даже для относительно простых транспортных задач и задач о назначениях характерно большое число переменных решения. Для транспортных задач, имеющих практическое значение, применение таких общих методов может стать неэффективным. Вместе с тем особенности структуры данных и ограничений транспортной задачи обусловливают возможность применения специальных высокоэффективных алгоритмов ее решения. [c.118]
Задача (15) является стандартной задачей линейного программирования, имеющей, однако, специфическое происхождение она возникла при сеточной аппроксимации непрерывной задачи типа линейного программирования (7)— (9). Поэтому, например,. /V > m (в расчетах автора N 10а- 103, т 1- -10). Решение ее стандартными методами, например, симплекс-методом, может привести к неоправданно большим затратам машинного времени в этих алгоритмах фундаментальную роль играют т-мерные грани — множества точек (т+1)-мерного пространства. [c.170]
Применение алгоритмов симплекс-метода и других традиционных методов для решения рассматриваемой задачи невозможно [c.211]
Сформированный выше алгоритм симплекс-метода можно применять лишь в том случае, если выделено первое допустимое решение, т. е. исходная задача линейного программирования приведена к виду [c.220]
По смыслу многих задач требуется, чтобы значение неизвестных в оптимальном плане выражались целыми числами. К ним относятся задачи, у которых переменные величины означают количество единиц неделимой продукции, например, распределение производственных заданий между предприятиями, раскрой материалов, загрузка оборудования, распределение судов по линиям, самолетов по рейсам, а также задачи по производству неделимой продукции. Если единица составляет малую часть всего объема производства, то оптимальное решение находят обычным симплекс-методом, округляя его до целых единиц,, исходя из смысла задачи. В противном случае округление может привести к решению, не удовлетворяющему системе ограничений (особенно, если значения неизвестных выражены малыми числами). Поэтому для нахождения оптимального целочисленного решения нужен особый алгоритм. [c.386]
Становление современного математического аппарата оптимальных экономических решений началось в 40-е годы, благодаря первым работам Н. Винера, Р. Беллмана, С. Джонсона, Л. Канторовича. Задача линейного программирования впервые математически сформулирована Л. В. Канторовичем в 1939 г. на примере задачи раскроя материалов для Ленинградского фанерного треста. В 1947 г. Дж. Данциг предложил универсальный алгоритм решения задач линейного программирования, названный им симплекс-методом. В 1941 г. Хичкок и независимо от него в 1947 г. Купсман формулируют транспортную задачу, в 1945 г. Стиглер — задачу о диете. В 1952 г. было проведено первое успешное решение задачи линейного программирования на ЭВМ Sea в Национальном бюро стандартов США. [c.102]
Рассмотренный метод оптимизации производственной программы. НПЗ в постановке (2)—(9)-реализован на ЭВМ М-22 . Ниже приводится общая схема вычисления по данному методу. Условия (4)—(8) формируются в виде отдельного. информационного массива. Он используется только при решении вспомогательной задачи (12). Основой предлагаемой вычислительной схемы является алгоритм мультипликативного симплекс-метода, к которому стыкуются алгоритмы решения вспомогательной задачи и усреднения. Для решения вспомогательнбй задачи может использоваться основная программа. Однако в связи/с ее небольшими размерами был разработан и реализован на ЭВМ более экономный прямой алгоритм симплекс метода с верхними ограничениями на переменные. Следует отметить, что предлагаемый подход может реализован и другой вычислительной схемой, отличной от приводимой ниже. Ее отличие состоит в том, что алгоритм решения вспомогательной задачи.подключается только после получения оптимального решения, основной задачи. Практическая проверка обеих вычислительных схем не показала существенного преимущества ни одной из них. [c.100]
При некоторых наборах исходных данных стандартные программы, использующие симплекс-метод, могут не давать решения (из-за погрешностей вычислений и представления данных). Алгоритм OMBI обеспечивает решение задачи во всех случаях. [c.136]
Проведенные преобразования системы ограничений D q позволили явно выделить сопряженный базис, образуемый столбцами с номерами 1,. .., т, п+1, и соответствующий ему псевдоплан (alf. .., dm, 0,. .., О, 4dJ), т. е. для решения задачи (Д(< ),/) может быть применен алгоритм двойственного симплекс-метода. Практически вычислительный процесс для данного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис. 4.5. [c.155]
СИМПЛЕКСНАЯ ТАБЛИЦА (СИМПЛЕКС-ТАБЛИЦА) [simplex table] — матрица, служащая средством перебора допустимых базисных решений (невырожденной) задачи линейного программирования при ее решении симплексным методом. Образуется из матрицы коэффициентов системы уравнений линейного программирования, приведенной к "канонической форме"75 последовательное ее преобразование по т.н. симплексному алгоритму позволяет за ограниченное количество шагов (итераций) получать искомый результат — план, обеспечивающий экстремальное значение целевой функции. [c.322]
Процедуры поиска решения в Ex el используют симплекс-метод, алгоритмы нелинейной оптимизации и метод ветвей и границ для решения линейных и целочисленных задач с ограничениями. [c.211]
Б. Н. М и х а л е в. Программа мультипликативного алгоритма симплекс-метода.-— В сб. Программа для решения эконом.-матем. задач на ЭВМ Минск-22 . М., ВНИИЭСХ, 1967. [c.223]
Какую роль играет алгоритм двойственного симплекс-метода при решении целочисленной линейной задачи методом Гомори [c.157]
Смотреть страницы где упоминается термин Симплекс-алгоритм решения задачи ЛП
: [c.270] [c.134] [c.103] [c.137] [c.171] [c.425] [c.438]Смотреть главы в:
Экономико-математические модели и методы -> Симплекс-алгоритм решения задачи ЛП