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

Материал из ALL
Перейти к: навигация, поиск

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

Обозначения

Введём обозначения:

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

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

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

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

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

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

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

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

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

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

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

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

Математическая модель

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

ОДЗ01.JPG

или

ОДЗ02.JPG

Построение симметричной задачи

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

xjj-тая переменная, j=1, 2, .., n.

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

ОДЗ03.JPG

Симметричная задача

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

ОПЗ01.JPG

Другие задачи:

Ссылки