Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Каноническая форма задач ЛП




Задача ЛП представлена в канонической форме, если в ее модели все функциональные условия имеют вид равенств и все переменные ограничены по знаку. Направление цели не имеет существенного значения, для однозначности канонического представления будем иметь в виду максимизацию критерия. Модель задачи:

Векторно-матричные представления: L = max

или

С– вектор коэффициентов целевой функции; Aj - векторы условий, j= В– вектор ограничений (свободных членов); А– матрица условий; Х– вектор переменных; – число переменных в канон. форме, >= числа переменных в исходной модели

Любую задачу ЛП можно привести к каноническому виду. Возможны 3 случая несоответствия исходной модели каноническому представлению.

1.Если в исходной постановке критерий минимизируется, то изменив знак критерия на обратный, приходим к задаче максимизации, т.е. если то

2.В исходной модели есть неравенства. При этом способ преобразования зависит от знака неравенства. В случае неравенства очевидно, что разность правой и левой части будет неотрицательной и неизвестной величиной, которую можно принять за новую переменную: Отсюда получаем следующее равенство: Аналогично при неравенстве Новая переменная (дополнительная, >=0)- разность левой и правой части и равенство записывается в виде

3.Некоторые переменные исходной модели не имеют ограничения на знак. Исключение таких переменных производится следующим способом.

Пусть – переменная, которая может иметь любой знак. Введем две неотрицательные переменные и во всей модели заменяем их разностью:

Таким образом, последние два случая преобразования к каноническому виду приводят к увеличению числа переменных, и поэтому всегда

Исходная модель: Каноническая модель:

 







Дата добавления: 2015-04-19; просмотров: 251. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2020 год . (0.002 сек.) русская версия | украинская версия