Это решение задачи представим в виде таблицы (симплекс-таблицы) (табл. 8.3). Эта таблица в условном виде повторяет систему условий задачи. [c.122]
Допустимой симплекс-таблице соответствует точка минимума, если все коэффициенты целевой функции неотрицательны. Тогда минимальное значение целевой функции равно Y . Если критерий не выполнен, т.е. не все коэффициенты целевой функции положительны, то следует перейти от одного допустимого базисного решения к соседнему допустимому, в котором множество базисных и свободных переменных изменены на один элемент. В невырожденном случае этому геометрически соответствует переход от одной вершины к другой вдоль ребра ОДР (обе вершины принадлежат одному ребру). Этот процесс называется симплекс-шагом или заменой базиса. Рассмотрим это на примере. [c.202]
Для перехода к новой симплекс-таблице необходимо поменять местами х, и х4, а все элементы разрешающей строки умножаем на элемент [c.203]
Задача линейного программирования канонического вида может быть записана в виде симплекс-таблицы [c.270]
Для нашего примера симплекс-таблица примет вид [c.271]
Задача задана в каноническом виде. Запишем соответствующую симплекс-таблицу [c.273]
В последней таблице все коэффициенты целевой функции неотрицательны. Следовательно, в точке х = 2, 2 = 2, Хз = 6, х = 0, Х5 = 0, д% = 0, xi = 2, xg =3 целевая функция принимает минимальное значение Q0 = -(-38) 38. (Переменным, индекс которых стоит в верхней строчке, приписывается значение 0 это свободные переменные. Каждое из переменных, индекс которого стоит в левом столбце, приравнивается числу, записанному в правом столбце той же самой строки — это базисные переменные.) Коэффициенты, стоящие в последней строке итоговой симплекс-таблицы, показывают, насколько изменится оптимальное значение целевой функции при изменении значения соответствующей переменной х на единицу, т.е. представляют собой "теневые цены". Например, уменьшение д на единицу приведет к уменьшению оптимального значения на 2. [c.275]
Сильная аксиома выявленного предпочтения 15 Сильный оптимум 249 Символическая модель ПО, 321 Симплекс 321 Симплексная таблица (симплекс-таблица) [c.487]
Последующий материал, посвященный анализу оптимального решения в задаче Канторовича, существенно использует симплекс-процедуру перехода от начального допустимого базисного решения к оптимальному решению. В связи с этим необходимо напомнить табличный метод нахождения оптимального решения в задаче линейного программирования. Среди множества реализаций симплекс-процедуры выберем ту, которая, во-первых, в явном виде разделяет базисные и свободные переменные и позволяет в последней симплекс-таблице выделить так называемую матрицу эффективности, а во-вторых, хорошо приспособлена для решения на ЭВМ. [c.65]
В табл. 2.2 в левом верхнем углу каждой клетки находятся коэффициенты ау предыдущей симплекс-таблицы (в нашем случае — [c.69]
Приведем последнюю симплекс-таблицу коэффициентов, да--, ющую оптимальное решение задачи в этом случае. [c.74]
Раскройте экономическое содержание базисных и свободных переменных последней симплекс-таблицы. [c.80]
Рассмотрим подробно экономическое содержание коэффици- ентов в симплекс-таблицах от начального плана (табл. 3.1(й)) к промежуточному (табл. 3.1(6)) и далее к окончательному (табл. 3. l(e)). H [c.82]
Для заданного в исходной модели вектора наличного запаса ресурсов В = (20, 180, 32) значение целевой функции с°=62,3 тыс. т суммарной добычи условного топлива. В случае указанного выше изменения вектора ресурсов на величину Д5 = (10,0, —10) получено изменение оптимального плана добычи торфа — на величину Дх = 75 тыс. т и угля — на величину AxJ =27,5 тыс. т. Определим величину, на которую изменился критерий оптимальности А с° = 0,25 (-75) + 1,2 27,5 = 14,25 (тыс. т условного топлива). Таким образом, экономический эффект от указанного изменения вектора ресурсов оказывается положительным. Оценим данный результат с позиций двойственных оценок ресурсов. Исходя из последней симплекс-таблицы 3.1 (в) (значений коэффициентов пер- вой строки), двойственная оценка оборотных средств предприятия равна 2,075 т усл. топлива/руб., двойственная оценка трудовых ресурсов — 0,65 т усл. топлива/чел.-ч, а двойственная оценка ресурсов электроэнергии — нулевая (так как переменная х4 находится среди базисных переменных исходной задачи, являющейся по определению прямой). [c.89]
Рассмотрим вектор X °, в который входят свободные переменные из последней симплекс-таблицы. Вектор ° формируют те неэффективные виды продукции, производство которых в оптимальном плане невыгодно. Однако в ряде случаев может оказаться необходимым их производство (например, корректировка плана в конце года) или целесообразен анализ альтернативных планов выпуска. Для производства новой продукции, задаваемой конкретными значениями вектора X °, потребуются ресурсы (в размере А°-Х °), что [c.89]
Выше мы проследили связь между двойственными оценками ресурсов и значением критерия оптимальности. Остановимся на этом еще раз. Итак, коэффициенты первой строки последней симплекс-таблицы (см. табл. 3.1(в)) показывают размер изменения критерия оптимальности (суммарной добычи условного топлива) от изменения в плане соответствующей переменной на единицу. В частности, у3=0,65 показывает, что один неиспользованный чел. -ч уменьшит суммарную добычу условного топлива на 0,65 т. Равным образом такое уменьшение суммарной добычи произойдет и при сокращении величины выделенных трудовых ресурсов на один чел. -ч. Наоборот, дополнительное выделение одного чел. -ч увеличит суммарную добычу условного топлива в таких же размерах, т. е. на 0,65 т. [c.95]
Для этого выпишем из целевой строки последней симплекс-таблицы двойственные оценки технологических способов [c.128]
Каким образом из последней симплекс-таблицы, содержащей оптимальный план, можно получить матрицу коэффициентов замены для неинтенсивных технологических способов [c.129]
К (°) определяет исходный опорный план. Это вершина А на рис. 1.3. Приведем решение рассмотренной выше задачи в симплекс-таблице (табл. 1.6) [c.448]
Из последней итерации симплекс-таблицы можно получить информацию относительно оптимального плана, статуса сырья, ценности сырья, чувствительности базиса к изменению запасов сырья и вариациям коэффициентов целевой функции. [c.449]
Оптимальное решение. Используя данные симплекс-таблицы, основные результаты можно представить в следующем виде [c.449]
Это обусловливает наличие альтернативных оптимальных решений. Любая точка отрезка ВС представляет собой альтернативный оптимум, причем в каждой из этих точек целевая функция имеет одно и то же оптимальное Значение. Приведем решение задачи в симплекс-таблице (табл. 1.7). [c.454]
Замечание. По мере выхода искусственных переменных из базиса вычисления в соответствующих клетках симплекс-таблицы не проводятся. [c.457]
Составление исходной матрицы симплекс-таблицы. [c.125]
Рассчитаем индексную строку в симплекс-таблице, соответствующей первому варианту плана. Например, для столбца констант [c.127]
После заполнения матрицы симплекс-таблицы можно приступить к ее анализу. [c.127]
Анализ симплекс-таблицы. Для проверки оптимальности очередного варианта плана служит индексная строка. При решении задачи на максимум целевой функции вариант решения считается оптимальным, если все элементы индексной строки положительны. При решении задачи на минимум целевой функции индексная строка не должна содержать положительных чисел. В случае оптимальности очередного варианта плана решение задачи заканчивается и исследуется полученный результат. Если очередной вариант плана не оптимален, приступают к [c.127]
Составление улучшенного варианта плана. Первый шаг при получении второй симплекс-таблицы сводится к заполнению строки, которая вводится вместо выводимой из плана и называется главной. Для получения всех элементов главной строки необходимо каждый элемент ключевой строки разделить на ключевое число. [c.128]
Производные числа для новой симплекс-таблицы определяются по такому правилу. Выбирают любое число [c.128]
Например, производные числа столбца х второй симплекс-таблицы рассчитывают так [c.129]
Алгоритм составления очередной симплекс-таблицы включает следующие операции [c.129]
Правило 1. Если в ключевом столбце имеется нуль, то строка, в которой находится этот нуль, остается неизменной в следующей симплекс-таблице (например, строки W1 и 1/2в табл. 22.2,22.3). [c.131]
Правило 3. Если ключевая строка содержит нуль, то столбец, в котором он находится, останется неизменным в следующей симплекс-таблице (например, столбцы 3. х4, Wi, W2, U2 в табл. 22.2, 22.3). [c.131]
Достаточно решить задачу (11.37), решение задачи (11.38) находится в строке двойственных оценок на последней итерации симплекс-таблицы. [c.232]
Данная таблица называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы. [c.216]
В последней строке симплекс-таблицы находят наименьший положительный элемент, не считая свободного члена. Столбец, со- [c.216]
После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной, и наоборот. Симплекс-таблица преобразована следующим образом (табл. 7.6). [c.217]
Преобразование симплекс-таблицы [c.218]
Составим симплекс-таблицу (табл. 7.7). [c.219]
В симплекс-таблице, соответствующей системе (7.44), после того как /min = 0, а все у,- - свободные, вычеркивают строку для /min и столбцы для у, и решают задачу для исходной линейной формы [c.222]
Составим симплекс-таблицу (табл. 7.9) [c.222]
Заполним следующую симплекс-таблицу (табл. 7.10) [c.223]
СИМПЛЕКСНАЯ ТАБЛИЦА (СИМПЛЕКС-ТАБЛИЦА) [simplex table] — матрица, служащая средством перебора допустимых базисных решений (невырожденной) задачи линейного программирования при ее решении симплексным методом. Образуется из матрицы коэффициентов системы уравнений линейного программирования, приведенной к "канонической форме"75 последовательное ее преобразование по т.н. симплексному алгоритму позволяет за ограниченное количество шагов (итераций) получать искомый результат — план, обеспечивающий экстремальное значение целевой функции. [c.322]
Смотреть страницы где упоминается термин Симплекс-таблица
: [c.202] [c.69] [c.80] [c.450] [c.129] [c.131] [c.217]Справочник по математике для экономистов (1987) -- [ c.195 ]