Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

Общая прямая задача линейного программирования

Материал из Циклопедии
Перейти к навигации Перейти к поиску

Общая прямая задача — это задача линейного программирования с ограничениями всех видов и с переменными всех видов. Симметричная ей задача — Общая двойственная задача линейного программирования.

Обозначения[править]

n – число переменных;

1, 2, .., n1 – номера неотрицательных переменных;

n1+1, n1+2, …, n2 – номера переменных без ограничений;

n2+1, n2+2, …, n – номера неположительных переменных;

m – число ограничений;

1, 2, .., m1 – номера ограничений вида ;

m1+1, m1+2, …, m2 – номера ограничений вида =;

m2+1, m2+2,…,m – номера ограничений вида ;

aij – коэффициент в i-том ограничении перед j-той переменной;

cj – коэффициент в целевой функции перед j-той переменной;

bi – значение границы в i-том ограничении;

xjj-тая переменная.

Математическая модель[править]

Математическая модель общей прямой задачи имеет следующий вид:

ОПЗ01.PNG

или

ОПЗ02.JPG

Построение симметричной задачи[править]

Введём дополнительные переменные:

yii-тая переменная, i=1, 2, .., m.

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

ОПЗ03.PNG

Симметричная задача[править]

Математическая модель общей двойственной задачи имеет следующий вид:

ОДЗ01.JPG

Другие задачи:[править]


Ссылки[править]

  • Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.