После того, как задача сформулирована в терминах линейного программирования, решение ее состоит в применении того или иного расчетного алгоритма. Наиболее распространенными методами решения задач линейного программирования являются симплексный (или метод последовательного улучшения плана), распределительный и индексный. Существует также ряд приближенных методов решения, разработанных для отдельных видов задач (пример решения задачи методом линейного программирования дан ниже). [c.153]
СИМПЛЕКСНЫЙ МЕТОД ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ — наиболее универсальный и распространенный за рубежом метод решения задач линейного программирования. С. м. л. п. довольно сложен по расчетной процедуре, и это затрудняет его использование при ручном счете. Однако известны алгоритмы для решения задач при помощи этого метода на электронных вычислительных машинах, что открывает ему путь для практич. применения. [c.21]
В настоящей главе рассматриваются общие методы решения задач линейного программирования, к которым относятся симплексный метод и метод обратных матриц. Указанными методами может быть решена любая задача линейного программирования. [c.294]
Вторым этапом моделирования экономических процессов является выбор наиболее рационального математического метода для решения задачи. Например, для решения задач линейного программирования известно много методов симплексный, потенциалов и др. Лучшей моделью является не самая сложная и самая похожая на реальное явление или процесс, а та, которая позволяет получить самое рациональное решение и наиболее точные экономические оценки. Излишняя детализация затрудняет построение модели, часто не дает каких-либо преимуществ в анализе экономических взаимосвязей и не обогащает выводов. Излишнее укрупнение модели приводит к потере существенной экономической информации и иногда даже к неадекватному отражению реальных условий. [c.105]
Как мы уже отмечали, графические методы, описанные в предыдущих разделах, приемлемы только в отношении задач с не более чем двумя неизвестными (например, х и у). В большинстве практических ситуаций число неизвестных может быть гораздо большим. Симплексный метод — один из наиболее известных подходов к решению задач линейного программирования через алгебраические методы. Симплексный метод применяется в самых разнообразных компьютерных программах, предназначенных для решений таких задач. [c.279]
Т Определение. Симплексный метод — математический подход к решению задач линейного программирования. Это стандартный метод решения задач с более чем двумя переменными. А [c.279]
Суть этого алгоритма [92] состоит в соединении основной схемы итеративного алгоритма решения соответствующей нецелочисленной задачи с идеей доводки его до целочисленного методом случайного поиска. Итеративный алгоритм, основанный на идее известного метода Брауна— Робинсона решения матричных игр, дает возможность получить приближенное решение задачи линейного программирования при небольших затратах машинного времени. Проведенные эксперименты доказывают, что в применении к некоторым классам задач линейного программирования итеративные алгоритмы могут конкурировать с симплексными [92]. [c.190]
Таким образом, построение календарного графика работы поточной линии с непрерывным регламентом выполнения операций заключается в решении задачи Б". Эта задача является линейно-программистской и, следовательно, может быть решена любым из существующих методов линейного программирования. Особенностью этой задачи является то, что в ней большинство коэффициентов при неизвестных в каждом из неравенств равны нулю. Так, в неравенствах (32), (33) только три коэффициента положительны, в неравенстве (34)—один, а в неравенстве (35) — два. Это обстоятельство упрощает решение задачи и позволяет решать задачи как вручную, так и на электронных вычислительных машинах (ЭВМ) относительно больших размеров. При небольшой размерности (на поточной линии выполняется порядка 10—15 операций) задача может быть решена вручную. При этом работник, имеющий некоторый навык в решении задач линейного программирования, может решить ее примерно за 1—1,5 часа. При решении задач больших размерностей (предмет проходит обработку через 30—50 операций) необходимо использовать ЭВМ. Внедряемая в настоящее время на промышленных предприятиях страны ЭВМ Минск-22 с успехом может использоваться для решения этих задач. Для реализации алгоритма может быть взята стандартная программа решения задач симплексным методом. [c.48]
Решение задач линейного программирования осуществляется с помощью симплексного метода (с использованием, как правило, пакета прикладных программ). При этом реализуются следующие этапы [c.16]
Решение задачи линейного программирования симплексным методом проводится в два этапа. Сначала находится начальное базисное решение, а затем проводится направленный перебор базисных решений для получения оптимального плана. [c.49]
Транспортные задачи обычно связаны с анализом доставки товаров от разных источников по различным направлениям. Так, у предприятия может иметься несколько складов, предназначенных для отправки товаров в различные точки страны. В этом случае необходимо принять решение относительно оптимального способа передвижения этих товаров, с тем чтобы минимизировать затраты, время на перевозку и задействованные при этом ресурсы. Такого рода задача относится к отдельному типу задач линейного программирования. Мы имеем ряд ограничений, скажем, потребности точек назначения и наличие возможностей, и хотим минимизировать затраты. Поэтому мы можем сформулировать транспортную задачу как задачу линейного программирования и далее применить для получения решения симплексный метод. Однако в том, что касается перевозок, ограничения даются в особой форме, и целесообразен упрощенный метод решения. [c.288]
В этой главе мы рассмотрели приемы линейного программирования при решении задач оптимизации. Типичный пример — максимизация прибыли предприятия за счет определения соответствующей номенклатуры производства. Кроме того, задачи линейного программирования могут быть направлены на минимизацию переменных, в частности затрат. Выражение, которое необходимо оптимизировать, называется объективной функцией. Эта функция высчитывается при наличии ряда ограничений. Одна из самых больших трудностей при решении такого рода задач состоит в исходной постановке задачи, когда необходимо определить ограничения, представить их в виде неравенств и выдать выражение объективной функции. При решении простых задач только с двумя переменными можно применить графический метод. Для более сложных задач применяется симплексный метод. [c.304]
Ниже даются постановка основной задачи линейного программирования, описание симплексного метода решения и пример применения этого метода для выбора оптимального варианта размещения наливных станций, грузооборота, прикрепления к ним потребителей. [c.179]
Разработан целый ряд вычислительных приемов, позволяющих решать на ЭВМ задачи линейного программирования, насчитывающие сотни и тысячи переменных, неравенств и уравнений. Среди них наибольшее распространение приобрели методы последовательного улучшения допустимого решения (см. Симплексный метод, Базисное решение), а также декомпозиционные методы решения крупноразмерных задач, методы динамического программирования и др. Сама разработка и исследование таких методов — развитая область вычислительной математики. [c.172]
Р. А. 3 в я г и н а. Программа реализации на М-20 модифицированного симплексного метода для решения общей задачи линейного программирования.— Оптимальное планирование. Новосибирск, 1954, вып. 1. [c.222]
При решении общей задачи линейного программирования симплексным методом для составления исходной программы необходимо, как рассматривалось выше, найти базисное решение. [c.315]
При решении задач симплексным методом линейного программирования моделирование заключается в составлении системы линейных уравнений и неравенств, каждое из которых выражает одно из заданных в условии задачи ограничений в виде функций определяемых переменных. [c.34]
Симплексный метод — один из основных методов линейного программирования. Он универсален и наиболее приспособлен к решению широкого круга экономических задач. С его помощью можно провести оптимизацию производственной программы, и уровня использования производственной мощности, осуществить оптимальную загрузку оборудования, оптимальное составление смесей, оптимальное оперативно-календарное планирование и др. [c.122]
Математическое обеспечение модели основывается на симплексном методе линейного программирования и реализуется пакетом прикладных программ ЭВМ. В расчетах использованы нормативная база и показатели (ограничения) по конкретному производственному объекту. Изложим процедуру оптимизации производственной программы с выделением в ней дополнительного задания в рамках принятого годового плана. В табл. 7 приводится исходная информация решения задачи. [c.64]
За рубежом применяются различные методы Л. п. Большинство авторов считает основным т. н. симплексный метод линейного программирования. Другие методы обычно трактуются как модификация симплексного метода. Однако некоторые из них имеют самостоятельное значение, обладают собственными расчетными приемами и сферой применения. Таков, в частности, распределительный метод линейного программирования, нашедший широкое применение в решении ряда задач. Симплексный и распределительный методы Л. п. основаны на различном подходе к определению отправного варианта и на разных способах изменения значений переменных в процессе улучшения последовательных вариантов. Неодинакова и сфера возможного применения этих 2 методов. Симплексный метод, будучи по технике вычислений несколько более громоздким и сложным, является более универсальным он применим к решению любых задач Л. п. Распределительный метод проще в технич. отношении, но имеет более узкую сферу применения (наиболее часто он применяется для составления оптимальных планов перевозок). [c.398]
Симплексный метод является универсальным методом линейного программирования. Основы этого метода были сформулированы американским ученым Дж. Данцигом в 1949 г. Симплексный метод получил свое название из геометрического толкования одной из первых задач, решенных этим методом. В этой задаче переменные были неотрицательны, а их сумма равнялась единице [c.296]
Задача об использовании оборудования. Ход решения задач симплексным методом рассмотрим на примере загрузки оборудования, который был использован в одной из предыдущих глав, при изложении графического метода линейного программирования. [c.298]
СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (симплекс-метод) [simplex method] — вычислительная процедура, основанная на принципе последовательного улучшения решений — перехода от одной базисной точки (см. Базисное решение) к другой, для которой значение целевой функции больше (эти операции фиксируются в симплексной таблице). Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов (за исключением т.н. вырожденной задачи, при которой возможно явление "зацикливания", т.е. многократного возврата к одному и тому же положению). Название метод получил от термина " -мерный симплекс". Геометрическая интерпретация метода состоит в последовательном движении по верши) шм симплекса. [c.322]
А. А. 3 о т о в а. Решение задач линейного программирования симплексным методом на ЦВМ ( Минск-12 ).— Вопросы вычисл. техники. Ростов-на-Дону, 1965. [c.222]
ВЫРОЖДЕННАЯ ЗАДАЧА [degenerate problem] — задача линейного программирования, в которой при разложении вектора ограничений В (обозначения см. в ст. "Линейноепрограммирование") по некоторому базису а]х. ... ат по крайней мере один коэффициент оказывается равным нулю. Такая ситуация затрудняет решение задачи симплексным методом, вызывая явление "зацикливания", при котором одно и то же множество базисных решений будет периодически повторяться, а оптимальный план никогда не будет достигнут. [c.59]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]
СИМПЛЕКСНАЯ ТАБЛИЦА (СИМПЛЕКС-ТАБЛИЦА) [simplex table] — матрица, служащая средством перебора допустимых базисных решений (невырожденной) задачи линейного программирования при ее решении симплексным методом. Образуется из матрицы коэффициентов системы уравнений линейного программирования, приведенной к "канонической форме"75 последовательное ее преобразование по т.н. симплексному алгоритму позволяет за ограниченное количество шагов (итераций) получать искомый результат — план, обеспечивающий экстремальное значение целевой функции. [c.322]
Некоторые из них не связаны непосредственно с алгоритмом симплексного метода, как, например, метод потенциалов для решения транспортной задачи другие же в качестве составных элементов используют вычислительные процедуры симплексного метода. В качестве примера последних можно привести метод Гомори (метод отсечений) для решения задач линейного целочисленного программирования. [c.524]
РАЗРЕШАЮЩИХ МНОЖИТЕЛЕЙ МЕТОД — один из методов линейного программирования, разработанный в 1939 сов. ученым Л. В. Канторовичем. Является универсальным методом, применимым для решения любых задач линейного программирования. Р. м. м. предвосхитил идеи, положенные Дж. Данцигом в основу известного симплексного метода линейного программирования, разработанного на десятилетие позднее. Р. м. м. был развит Л. В. Канторовичем в ряд методов, применимых для решения различных частных задач линейного программирования. [c.401]
РАСПРЕДЕЛИТЕЛЬНЫЙ МЕТОД ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ — упрощающая модификация более универсального симплексного метода линейного программирования, применимая для решения лишь нек-рого класса задач линейного программирования. Типичным примером задач этого класса являются т. и. транспортная задача линейного программирования (см. Перевозок план оптимальный) и задачи, формально-математически приводимые к той же модели. [c.405]
Е. Д. М я к и ш е в а. Стандартная программа для решения общей задачи линейного программирования симплексным методом с модификацией Г. Зойтендейк (ЭВМ М-20).— Стандартные программы решения задач матем. программирования. Вычисл. центр Московского гос. ун-та, 1964, вып. 3. [c.222]
А. П. М е р е н к О Ё. Решение общей задачи линейного программирования модифицированным симплексным методом, (Библиотека программ для БЭСМ-2М, вып. я-1). М., 1965, [c.223]
П. А. А х м е т о в. Программа мультипликативного алгоритма симплексного метода для решения общих задач линейного программирования (на ЭВМ БЭСМ-ЗМ ).— Стандартные программы. М., 1967. [c.223]
Вычислительным методом для решения такой задачи служит типовой алгоритм методов линейного программирования, в том числе симплексного метода, т. е. метода последовательного улучшения производственной программы с помощью итерирования. За исходную точку расчетов принимается некоторый план производства по каждому изделию и затем в последовательном порядке изменяются значения прироста переменных. [c.266]