При нахождении оптимального варианта искомыми величинами являются интенсивность выполнения отдельных работ У и- Диапазон изменения этих величин от У п до У .4Х. Изменение интенсивности выполнения работ специализированной бригадой достигается путем введения сменности или добавлением (исключением) технологических звеньев. В качестве исходного (базисного) решения сетевой модели может быть принят вариант строительства КС и НС при минимальной интенсивности выполнения всех работ сетевого графика, то есть вариант, соответствующий минимальной численности рабочих и минимальной величине затрат на передислокацию строительно-монтажных подразделений. В этом случае продолжительность строительства КС и НС, как правило, больше директивного срока. В связи с большим количеством решений сетевой модели простой их перебор невозможен даже с применением современных ЭВМ. Для уменьшения числа рассматриваемых решений сетевой модели могут быть использованы оценки изменения продолжительности выполнения процессов [4]. [c.66]
Найденные в результате решения подзадач (2.30) значения относительных оценок "с- анализируются совместно с относительными оценками остальных небазисных переменных. Последующие процедуры определения столбца, выводимого из базиса, ввода в базис нового столбца и преобразования базисного решения аналогичны стандартной симплекс-процедуре. [c.31]
Процедура решения задачи (2.28) может быть модифицирована в зависимости от объема располагаемой исходной информации. Например, при частично известном базисном решении или известном решении задачи с фиксированными параметрами удается упростить схему вычислений. При этом особое внимание необходимо уделить возможности сокращения числа подзадач, решаемых на каждой итерации. [c.31]
Столбец Rjr заменяется столбцом Rs, и осуществляется соответствующее преобразование базисного решения. Возврат к процедуре 4. [c.33]
Исходная задача (2.28) в результате фиксации варьируемых векторов RJ на некоторых- номинальных значениях К° может быть приведена к обычной задаче линейного программирования с фиксированными параметрами. Далее стандартной симплекс-процедурой осуществляется решение задачи с фиксированными параметрами. На f-й итерации выявляется несовместность системы ограничений (2.28) при номинальных значениях Rj = Rj. В этом случае базисное решение 1- итерации [c.33]
Осуществляются замена столбца Rjr столбцом Ks и соответствующее преобразование базисного решения. [c.34]
Рассмотренный случай, когда в качестве исходного базисного решения задачи (2.28) рассматривается решение задачи (2.34), имеет ряд преимуществ по сравнению с общим случаем. Основные из них заранее гарантируется оптимальность решения значительно сокращаются объем вычислений и затраты машинного времени облегчается контроль результатов расчета. Однако по сравнению с линейными задачами с фиксированными параметрами объем вычислений остается все же достаточно большим. В связи с этим целесообразно модифицировать процедуры 2 и 4. [c.34]
Второй способ. В результате решения подзадачи вида (2.30) определяется значение относительной оценки 7,- для варьируемого столбца с минимальным индексом / (подзадачи заранее упорядочиваются в порядке возрастания /). Если с= < О, то осуществляется переход к решению следующей подзадачи и т. д. Если s = =Ъ > 0, то вектор столбца R s претендует на ввод в базис и для последующих столбцов на данной итерации подзадачи не решаются. Затем определяется столбец, подлежащий выводу из базиса, и осуществляются замена и соответствующее преобразование базисного решения. В данном случае на начальной стадии число подзадач, решаемых на каждой итерации, значительно меньше nl, однако по мере приближения к оптимуму число решаемых подзадач постепенно возрастает. [c.34]
Формируется смешанное" базисное решение, включающее известные компоненты вектора X, искусственные и дополнительные переменные. [c.35]
Разобьем матрицы А, X и С на подматрицы (клетки) в соответствии с принятым базисным решением - исходным (или опорным) планом. [c.74]
Задача (5.8) решается симплекс-методом. Для этого находим базисное решение (5.8). [c.200]
Допустимой симплекс-таблице соответствует точка минимума, если все коэффициенты целевой функции неотрицательны. Тогда минимальное значение целевой функции равно Y . Если критерий не выполнен, т.е. не все коэффициенты целевой функции положительны, то следует перейти от одного допустимого базисного решения к соседнему допустимому, в котором множество базисных и свободных переменных изменены на один элемент. В невырожденном случае этому геометрически соответствует переход от одной вершины к другой вдоль ребра ОДР (обе вершины принадлежат одному ребру). Этот процесс называется симплекс-шагом или заменой базиса. Рассмотрим это на примере. [c.202]
Поскольку целевая функция линейна, Рк показывают, насколько изменится значение целевой функции при изменении к-тл переменной на единицу, т.е. характеризуют чувствительность целевой функции к изменению л. Если все коэффициенты целевой функции неотрицательны (ркт + > О,. .., Рк > 0), то минимальное значение целевой функции равно Q0. Если критерий не выполнен, т.е. не все коэффициенты целевой функции неотрицательны, то следует перейти от одного допустимого базисного решения к соседнему, т.е. такому, в котором множества базисных и свободных переменных изменены на один элемент. Этот процесс называют симплекс-шагом или заменой базиса. Опишем последовательно его этапы. [c.271]
Примеры практического применения итерационных методов см. в ст. "Базисное решение", "Симплексный метод". [c.137]
Разработан целый ряд вычислительных приемов, позволяющих решать на ЭВМ задачи линейного программирования, насчитывающие сотни и тысячи переменных, неравенств и уравнений. Среди них наибольшее распространение приобрели методы последовательного улучшения допустимого решения (см. Симплексный метод, Базисное решение), а также декомпозиционные методы решения крупноразмерных задач, методы динамического программирования и др. Сама разработка и исследование таких методов — развитая область вычислительной математики. [c.172]
Понятие М. используется в геометрической интерпретации задач линейного программирования множество допустимых решений задачи является выпуклым М., базисное решение или опорный план — одной из его вершин. (См. Вершина допустимого многогранника). [c.198]
Найти любое допустимое базисное решение [c.322]
Последующий материал, посвященный анализу оптимального решения в задаче Канторовича, существенно использует симплекс-процедуру перехода от начального допустимого базисного решения к оптимальному решению. В связи с этим необходимо напомнить табличный метод нахождения оптимального решения в задаче линейного программирования. Среди множества реализаций симплекс-процедуры выберем ту, которая, во-первых, в явном виде разделяет базисные и свободные переменные и позволяет в последней симплекс-таблице выделить так называемую матрицу эффективности, а во-вторых, хорошо приспособлена для решения на ЭВМ. [c.65]
Заполненная таким образом табл. 2.3 соответствует матрице коэффициентов (2.13) при новом составе базисных и свободных переменных. Отметим попутно, что а ю > 0, так как й 00 является произведением положительных чисел а, 0 (в силу допустимости предыдущего базисного решения) и а., (в силу процедуры выбора [c.71]
Так как решаемая задача — задача на максимум, то соотношения (2.20) показывают, что начальное базисное решение является допустимым, но не оптимальным (коэффициенты при хр х2 и х3 в выражении для с не являются неотрицательными числами). [c.72]
В следующих таблицах представлена формальная процедура поиска оптимального решения с использованием симплекс-процедуры, основанной на выделении ведущих столбца и строки и пересчете коэффициентов матрицы нового базисного решения. [c.124]
Смежные вершины (крайние точки) отличаются только одной переменной в каждой группе свободных и базисных переменных. Все допустимые вершины определяются, как все неотрицательные базисные решения системы линейных уравнений (1.6). [c.448]
Расширенную матрицу системы линейных уравнений, которая определяет неотрицательное базисное решение исходной системы, будем называть К-матрицей. [c.448]
В данном диапазоне изменения запаса сырья S переменные Х, Хь Хъ остаются базисными и определяют оптимальное базисное решение. В этом случае остаются неизменными виды производственной деятельности. [c.451]
Замечание Если одновременно и столбец и строка удовлетворяют ограничениям, очередная переменная, включаемая в базисное решение, обязательно имеет нулевое значение. [c.484]
СПРОСА И ПОТРЕБЛЕНИЯ 107 Аналоговое моделирование 45 АНАЛОГОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ 145 Аппаратное МО 150 АППРОКСИМАЦИЯ ПРОИЗВОДСТВЕННО - ТЕХНОЛОГИЧЕСКИХ ВОЗМОЖНОСТЕЙ 89 Ассортиментный набор 57 Базисная точка 126 БАЗИСНОЕ РЕШЕНИЕ 116 БАЙТ 145 БАЛАНСОВЫЙ МЕТОД 75 БАНК ДАННЫХ 132 БАРОМЕТРЫ В ЭКОНОМИКЕ 90 БЕЗУСЛОВНЫЙ СТАТИСТИЧЕСКИЙ ПРОГНОЗ 90 БИБЛИОТЕКА СТАНДАРТНЫХ [c.156]
Базисное решение задачи линейного программирования 215, 220 [c.424]
Можно заметить, что искомое решение сетевой модели находится между рассмотренными базисными решениями. При этом базисный вариант-П удовлетворяет заданному ограничению по срокам строительства, а базисный варигнт I не может быть принят в качестве допустимого решения по продолжительности строительства. [c.76]
В отличие от метода Данцига — Вульфа, в котором производственные возможности отдельных предприятий представляются в виде линейной комбинации всех базисных решений х (s= , М ), в аппроксимаци-онных моделях выпуклые многогранники ооычно задаются на базе ограниченного множества опорных плановых решений. Ограниченность числа рассматриваемых в аппроксимационных моделях вариантов позволяет сократить размерность задач и объем обрабатываемой информации. [c.25]
Существуют различные методы определения опорных способов производства. В качестве опорных способов в аппроксимационных моделях используются 1) базисные или оптимальные базисные решения, определенные в результате решения серии экстремальных задач с неагрегированными переменными, параметрами и способами производства 2) опорные планы, оцененные экспертным путем 3) статистически обоснованные и имевшие прецедент плановые решения. [c.25]
БАЗИСНОЕ РЕШЕНИЕ (опорный план) [basi solution] — термин линейного программирования, одно из допустимых решений, находящихся в вершинах области допустимых решений, либо (если линия уровня параллельна одному из отрезков границы области) Б.р. — весь этот отрезок (см. рис. Л.2 к ст. "Линейное программирование"). Оно является решением системы линейных ограничений, которое нельзя представить в виде линейной комбинации никаких других решений. [c.26]
ВЕРШИНА ДОПУСТИМОГО МНОГОГРАННИКА [ orner point] (области допустимых решений в задачах линейного программирования) — точка пересечения линейных ограничений (напр., на рис. Л. 1 к ст. "Линейное программирование"). Поскольку множество допустимых решений в задаче линейного программирования всегда выпукло, вершинная точка является крайней точкой множества, и она может быть принята за допустимое базисное решение задачи. [c.47]
ВЫРОЖДЕННАЯ ЗАДАЧА [degenerate problem] — задача линейного программирования, в которой при разложении вектора ограничений В (обозначения см. в ст. "Линейноепрограммирование") по некоторому базису а]х. ... ат по крайней мере один коэффициент оказывается равным нулю. Такая ситуация затрудняет решение задачи симплексным методом, вызывая явление "зацикливания", при котором одно и то же множество базисных решений будет периодически повторяться, а оптимальный план никогда не будет достигнут. [c.59]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]
СИМПЛЕКСНАЯ ТАБЛИЦА (СИМПЛЕКС-ТАБЛИЦА) [simplex table] — матрица, служащая средством перебора допустимых базисных решений (невырожденной) задачи линейного программирования при ее решении симплексным методом. Образуется из матрицы коэффициентов системы уравнений линейного программирования, приведенной к "канонической форме"75 последовательное ее преобразование по т.н. симплексному алгоритму позволяет за ограниченное количество шагов (итераций) получать искомый результат — план, обеспечивающий экстремальное значение целевой функции. [c.322]
СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (симплекс-метод) [simplex method] — вычислительная процедура, основанная на принципе последовательного улучшения решений — перехода от одной базисной точки (см. Базисное решение) к другой, для которой значение целевой функции больше (эти операции фиксируются в симплексной таблице). Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов (за исключением т.н. вырожденной задачи, при которой возможно явление "зацикливания", т.е. многократного возврата к одному и тому же положению). Название метод получил от термина " -мерный симплекс". Геометрическая интерпретация метода состоит в последовательном движении по верши) шм симплекса. [c.322]
По виду коэффициентов матрицы (2.13) легко судить, является ли найденное базисное решение допустимым и, если оно допустимо, то будет ли оптимальным. Действительно, замечая, что столбец коэффициентов ай (/ 0) представляет собой базисное решение, соответствующее базису tv...,tm, а строка коэффициентов aoj (/ 0) представляет собой взятые с обратным знаком коэффициенты при свободных переменных в выражении для с, приходим к выводу, что базисное решение, соответствующее базису /iv..,fm, допустимо, если аю > 0 (в нашем случае это действительно так аю - bt > 0). Если, кроме того, av> 0, то это базисное решение является и оптимальным, так как линейная форма (2.11) принимает наибольшее значение, равное ат, при равенстве нулю свободных переменных (в нашем случае это условие не выполняется, так как все элементы первой строки матрийы (2.13) неположительны). Таким образом, матрица (2.13) ет допустимому базисному решению, но не оптимальному. [c.68]
БАЗИСНОЕ РЕШЕНИЕ — термин линейного программирования. Так называют одно из допустимых решений, находящихся в вершинах области допустимых решений (рис. 10 к статье Линейное программирование ). Почему оно базисное Дело в том, что при решеиии задачи линейного программирования можно поступить так найти любое из вершинных решений, на обязательно оптимальное, и принять №0 за исходный пункт расчетов. Оно и будет базисным. Если окажется, что оно и оптимальное, расчет на том закопчен. Если нет—последовательно проверяют, не будут ли оптимальными соседние вершинные точки ту из них, в которой план эффективнее, принимают снова за исходную точку, и так, последовательно проверяя на оптимальность аналогичные вершины, приходят к искомому оптимуму. На этом принципе строится так называемый симплекс—метод решения задач линейного программирования. [c.116]
Осп. понятием, связанным с МПУ, является понятие допустимого базисного решения (опорного плана). Т. к. в обычной задаче Л. п. количество переменных превышает количество уравнений для их определения, то имеется свобода в выборе значений нек-рого количества переменных. При задании базисного решения псе переменные делятся на базисные и иобазпсные, причём последние полагаются равными 0. Значения базисных церемонных находятся решением системы ограничений задачи. Количество базисных переменных таково, чтобы это решение существовало п было единственным. [c.357]