Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






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




Будем считать, что задача линейного программирования записана в канонической форме, если ее целевая функция максимизируется, ограничения имеют вид равенств с неотрицательной правой частью и все переменные неотрицательны.

Задача линейного программирования в канонической форме имеет вид:

f = c1x1 + c2x2 +…+ cnxn → max;

 

a11x1 + a12x2 +…+ a1nxn = b1,

a21x1 + a22x2 +…+ a2nxn = b2, (4)

……………………………..

am1x1 + am2x2 +…+ amnxn = bm,

 

xj >= 0 (j= 1, n); bi >= 0 (i= 1, m).

Так как общая задача линейного программирования имеет ограничения не только вида «=», но и «<=», «>=», а целевая функция может либо максимизироваться, либо минимизироваться, то необходимо уметь приводить любые задачи линейного программирования к канонической форме. С этой целью рассмотрим два частных вида задач линейного программирования и покажем, как эти задачи привести к канонической форме.

 

Одна из частных задач линейного программирования может быть представлена моделью:

 

f = c1x1 + c2x2 +…+ cnxn → max;

 
 


a11x1 + a12x2 +…+ a1nxn <= b1,

a21x1 + a22x2 +…+ a2nxn <= b1, (5)

……………………………..

am1x1 + am2x2 +…+ amnxn <= bm,

 

xj >= 0 (j= 1, n), где bi >= 0 (i= 1, m).

 

Левая часть каждого ограничения данной задачи меньше либо равна правой. Для того, чтобы левая часть ограничения была равна правой, необходимо к левой части каждого ограничения прибавить соответственно неотрицательные переменные xn+1, xn+2,…, xn+m. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить ее значение.

 

После приведения к канонической форме задача (5) будет иметь вид:

 

f = c1x1 +…+ cnxn + 0*xn+1 + 0*xn+2 +…+ 0*xn+m → max;

 

 

a11x1 +…+ a1nxn + xn+1 = b1,

a21x1 +…+ a2nxn + xn+2 = b2, (6)

…………………………….

am1x1 +…+ amnxn + xn+m = bm,

 

xj >= 0 (j= 1, n+m).

 

Рассмотрим другой частный вид задачи линейного программирования:

f = c1x1 + c2x2 +…+ cnxn → min;

 

 

a11x1 + a12x2 +…+ a1nxn >= b1,

a21x1 + a22x2 +…+ a2nxn >= b2, (7)

……………………………..

am1x1 + am2x2 +…+ amnxn >= bm,

 

xj >= 0 (j= 1, n),

где bi >= 0 (i= 1, m).

 

Определение минимального значения целевой функции f можно свести к определению максимального значения функции (- f), так как min f = - max (- f).

Для приведения ограничений вида «>=» к ограничениям-равенствам необходимо из левой части каждого ограничения вычесть соответственно неотрицательные переменные xn+1, xn+2,…, xn+m. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить ее значение.



 

После приведения к канонической форме задача (7) будет иметь вид:

 

f = - c1x1 -…- cnxn + 0*xn+1 + 0*xn+2 +…+ 0*xn+m → max;

 

a11x1 +…+ a1nxn - xn+1 = b1,

a21x1 +…+ a2nxn - xn+2 = b2, (8)

…………………………….

am1x1 +…+ amnxn - xn+m = bm,

 

xj >= 0 (j= 1, n+m).

 

Таким образом, если в задаче линейного программирования определяется минимум целевой функции, то такую задачу необходимо свести к определению максимума целевой функции, а все имеющиеся ограничения вида «<=» и «>=» привести к ограничениям-равенствам.

 

Замечание. Требование максимизации целевой функции при приведении задачи к канонической форме не обязательно и выдвигается с целью простоты изложения материала, связанного с решением задач линейного программирования симплекс-методом. Методика решения задач на минимум несколько отличается от методики решения задач на максимум. Поэтому требование максимизации целевой функции дает возможность решать задачу по единому алгоритму.

 


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал