Пример построения канонической формы

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

Для численного решения задачи ЛП требуется предварительно привести ее к каноническому виду:

(1)

………………………

Каноническая форма (КФ) (1) задачи характеризуется следующими тремя признаками:

― однородная система ограничений в виде системы уравнений;

― однородные условия неотрицательности, распространяющиеся на все переменные, участвующие в задаче;

― минимизация (максимизация) целевой функции.

Известно, что для произвольной задачи ЛП можно построить эквивалентную ей каноническую задачу ЛП (эквивалентность двух задач означает, что оптимальному решению одной задачи соответствует оптимальное решение другой)[1,2,3].

Пример построения канонической формы

Привести задачу к КФ на минимум:

(2)

В данной задаче (2) нарушены все три признака КФ.

1. Начнем с преобразования смешанной системы ограничений в систему уравнений. Для этого введем в первое и второе ограничения неотрицательные переменные y1, y2, которые называются дополнительными или слабыми. В результате система ограничений запишется в следующем виде:

(3)

2. Условия неотрицательности в (3) не выполняются только для переменной x2. Для приведения задачи к однородным условиям неотрицательности можно воспользоваться двумя приемами.

Первый прием. Представим переменную x2 в виде разности двух неотрицательных переменных: После преобразования системы ограничений и целевой функции получим задачу

(4)

Второй прием. Найдем из какого-либо уравнения (4) переменную x2. Пусть из первого уравнения . Подставим это выражение во все уравнения и в целевую функцию, исключив таким образом переменную x2 из задачи. Получим

(5)

3. Переход к задаче минимизации целевой функции L в задаче (5) осуществляется путем введения новой функции из равенства

в первом случае,

во втором случае.








Дата добавления: 2017-09-19; просмотров: 944;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.