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