Табличный симплекс-метод - раздел Информатика, МетодичЕСКИЕ УКАЗАНИЯ по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии Пусть Для Исходной Злп Задано Начальное Дбр, Базис Которого Образуют Первые M...
Пусть для исходной ЗЛП задано начальное ДБР, базис которого образуют первые m столбцов матрицы A. Введем новую переменную z и с помощью элементарных преобразований Жордана-Гаусса преобразуем расширенную систему к диагональной форме относительно переменных z, x1, x2,…, xm:
,
,
Диагональная форма (19) исходной системы ограничений, полученная при помощи преобразований Жордана-Гаусса, совпадает с диагональной формой (13)-(15), полученной матричным способом.
Диагональной форме (19) можно поставить в соответствие следующую таблицу, которая получила название симплекс-таблицы:
Таблица 1
БП
z
x1
…
xm
xm+1
…
xn
Решение
z
…
…
b0
x1
…
a1,m+1
…
a1,n
b1
…
…
…
…
…
…
…
…
…
xm
…
am,m+1
…
am,n
bm
В левом столбце таблицы перечислены базисные переменные. В общем случае в этом столбце таблицы в i-ой строке будет записана переменная (xB)i.
Слева от таблицы указаны базисные переменные.
В общем случае в левом столбце таблицы в i-ой строке будет записана переменная .
Построенная таблица называется симплекс-таблицей. Она содержит всю информацию, необходимую для осуществления одной итерации симплекс-метода. Реализация симплекс-метода с помощью симплекс-таблицы называется табличным симплекс-методом.
По сути, симплекс-метод и табличный симплекс-метод соотносятся между собой как метод и алгоритм.
В дальнейшем столбец будем опускать, так как от итерации к итерации он не изменяется .
НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ... КиЕвский ПолИтехнИчЕСКий Институт... Симплекс метод...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Табличный симплекс-метод
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Формы ЗЛП
Задача математического программирования вида:
называется задачей линейного программирования (ЗЛП).
Основн
Эквивалентность различных форм ЗЛП
Все перечисленные формы ЗЛП являются эквивалентными в том смысле, что простыми преобразованиями задачу, имеющую одну из форм, легко привести к задаче, имеющей одну из оставшихся форм, причем по оп
Решение
Так как первое ограничение имеет знак “≥”, то в левую часть ограничения вводим избыточную переменную s1. Данное ограничение будет иметь вид:
x1 + 2x2
Решение
В этом случае на переменную x2 не накладывается ограничение неотрицательности. Введя две новые неотрицательные переменные x2+≥0, x2–X
Упражнения
1) Укажите, какая из ниже приведенных форм задач является канонической?
а)
б)
Основные свойства ЗЛП
Для ЗЛП справедлива следующая теорема.
Теорема (о существовании решения). Если допустимое множество X ЗЛП не пусто, а значение её конечно, то эта задача имеет решение.
Способ перехода от одного ДБР к другому
Пусть ДБР x0 соответствует преобразованной задаче (13)-(15). Перейдем от него к новому ДБР x1. При этом рассмотрим возможность того, что только одна небазисная переменн
Условие оптимальности ДБР
Определение. Вектор-строка, на которую умножается слева xN в уравнении для ЦФ (13), называется вектором относительных оценок, т.к. он указывает, в какую сторону
М - метод
Вернемся к введенной в примере 11.1 линейной модели.
В первом и во втором уравнениях нет переменных, выполняющих роль остаточных. Поэтому введем в каждое из уравнений по одной искусственно
Двухэтапный метод
Исторически первым появился М-метод, но он имеет существенный недостаток: возможность появления ошибок в вычислениях, обусловленных очень большой величиной коэффициента М.
Например: М=100
Отсутствие допустимых решений
Если ограничения модели одновременно выполняться не могут, то задача не имеет допустимых решений. Такое решение всегда существует, когда все ограничения типа "≤", поскольку введение
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов