Общая ЗЛП. Канонический вид ЗЛП
2.1. Общая ЗЛПформулируется в виде (1.2). Другими словами, ЗЛП в общем виде ставится как (1.2). Таким образом, имея дело с ЗЛП, мы будем иметь дело с линейной системой. В теории линейных систем x1, x2, …, xn мы называли неизвестными. В оптимизации функции f(x1, x2, …, xn) они выступают в качестве переменных. Поэтому к ним мы будем применять этот термин. От этого их суть не меняется: необходимо найти (неизвестные) переменные x1, x2, …, xn, при которых целевая функция f(x1, x2, …, xn) достигает экстремума. Также, мы сохраняем терминологию линейных систем: основная и расширенная матрица, совместные системы, ранг системы, базисное решение и т.д. Так же, будем считать, что ранг r системы совпадает с числом m уравнений и неравенств: r=m. Канонический вид ЗЛП Если в системе ограничений задачи (1.2) присутствуют только уравнения, а свободные члены в системе ограничений задачи являются неотрицательными, то говорят, что задача имеет канонический вид. Согласно 1.2.2 первой части, любая смешанная система приводится к системе уравнений добавлением дополнительных неотрицательных переменных со знаком «+» в неравенства типа «≤» и со знаком «-» в неравенства типа «≥». Поэтому для приведения к каноническому виду задачи линейного программирования поступаем следующим образом: 1) Если в системе ограничений задачи имеется ограничение с отрицательной правой частью, то умножаем его на -1. 2) Добавляем в каждое неравенство дополнительные неотрицательные переменные: со знаком «+» в неравенства типа «≤» и со знаком «-» в неравенства типа «≥». Таким образом, 2.2.1. ОЗЛП (1.2) приводится к каноническому виду
c1x1+c2x2+…+cnxn®max(min) 2.2.2. ЗЛП (1.4) приводится к каноническому виду c1x1+c2x2+…+cnxn®max А также 2.2.1. ЗЛП (1.5) приводится к каноническому виду c1x1+c2x2+…+cnxn®min В любом случае можно считать, что ЗЛП имеет канонический вид c1x1+c2x2+…+cnxn®max(min) (2.1) Если A=(aij) - матрица системы ограничений задачи, X=(x1, x2, …, xn)T - столбец переменных, B=(b1, b2, …, bn)T - столбец свободных членов системы ограничений и C=(c1, c2, …, cn) - вектор коэффициентов целевой функции, то задачу (2.1) можно записать в матричной форме: CX®max(min) AX=B, X≥O. Обозначим через A1, A2, …, An соответственно 1-й, 2-й, …, n-й столбцы матрицы A. Тогда задачу (1.6) можно записать в векторной форме: CX®max(min) A1x1+A2x2+…+Anxn=B, X≥O. 2.3. Упражнение. Привести к каноническому виду задачи линейного программирования из предыдущих заданий 1) - 3), выписать их матрицы ограничений, столбцы свободных членов, векторы условий, векторы коэффициентов целевых функций, и записать задачи в матричной и векторной формах. Решение. 1г) 4x1+x2®min(max) Правая часть первого неравенства - отрицательная. Поэтому первое неравенство умножаем на -1: Теперь все неравенства ограничений имеют тип «£». Поэтому во все эти неравенства вводим дополнительные неотрицательные переменные, соответственно x3, x4, x5: Таким образом, канонический вид задачи - следующий: 4x1+x2 ® max Матрица ограничений (выписываем для канонического вида): , - столбец свободных членов, A1= , A2 = , A3= , A4= , A5= - векторы условий, (4, 1, 0, 0, 0) - вектор коэффициентов целевой функции, × = , ³O - матричная форма записи задачи, x1+ x2+ x3+ x4+ x5= - - векторная форма записи задачи.
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1532)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |