математическое моделирование / Вопрос 42
.docВопрос № 42. Формы записи задач линейного программирования.
4.1 Общая форма задачи линейного программирования
Задана система m линейных ограничений с n переменными:
a11x1 + a12x2 +… + a1nxn ≤ (≥) b1,
a21x1 + a22x2 +… + a2nxn ≤ (≥) b2,
…………………... ... ... ... ... ... ...,
ak1x1 + ak2x2 +… + aknxn ≤ (≥) bk,
ak+1,1x1 + ak+1,2x2 +… + ak+1,nxn = bk+1,
ak+2,1x1 + ak+2,2x2 +… + ak+2,nxn = bk+2,
… … … … … … … ... ... ... ... ... ... ...,
am1x1 + am2x2 +… + amnxn = bm,
где: x1 ≥ 0, x2 ≥ 0,…, xn ≥ 0,
а линейная функция Z = c1x1 + c2x2 +… + cnxn → mаx (min).
Необходимо найти переменные x1, x2,…, xn, которые удовлетворяют
системе ограничений и приводят целевую функцию к максимальному или
минимальному значению.
В общей форме задачи линейного программирования система
ограничений включает в себя как равенства, так и неравенства, а целевая
функция может стремиться как к максимуму, так и к минимуму.
4.2 Стандартная форма задачи линейного программирования
Задача линейного программирования, представленная в форме:
a11x1 + a12x2 +… + a1nxn ≤ (≥) b1,
a21x1 + a22x2 +… + a2nxn ≤ (≥) b2,
… … … … … … … … … ... ...,
am1x1 + am2x2 +… + amnxn ≤ (≥) bm,
где: x1 ≥ 0, x2 ≥ 0,…,xn ≥ 0,
а линейная функция Z = c1x1 + c2x2 +… + cnxn→ mаx (min), называется
стандартной формой задачи линейного программирования.
Особенность данной формы состоит в том, что в ней система ограничений
состоит из одних неравенств, переменные решения являются
неотрицательными, а целевая функция может стремиться как к максимуму, так и
к минимуму.
4.3 Каноническая форма задачи линейного программирования
Форма, в которой Z = c1x1 + c2x2 +… + cnxn→ mаx,
a11x1 + a12x2 +… + a1nxn = b1,
a21x1 + a22x2 +… + a2nxn = b2,
… … … … … … … … … ...,
am1x1 + am2x2 +… + amnxn = bm,
все переменные неотрицательные: x1 ≥ 0, x2 ≥ 0,…, xn ≥ 0, система
ограничений представляет собой систему уравнений, а целевая функция
стремится к максимуму, называется канонической формой задачи линейного программирования.