Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
11
Добавлен:
24.03.2015
Размер:
29.18 Кб
Скачать

Вопрос № 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, система

ограничений представляет собой систему уравнений, а целевая функция

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

Соседние файлы в папке математическое моделирование