Общая двойственная задача линейного программирования
Общая двойственная задача — это задача симметричная общей прямой задаче линейного программирования, с ограничениями всех видов и с переменными всех видов.
Обозначения[править]
Введём обозначения:
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-том ограничении;
yi – i-тая переменная.
Математическая модель[править]
Математическая модель общей двойственной задачи имеет следующий вид:
или
Построение симметричной задачи[править]
Введём дополнительные переменные:
xj – j-тая переменная, j=1, 2, .., n.
Соответствия ограничений и переменных двойственной и прямой задач имеют следующий вид:
Симметричная задача[править]
Математическая модель общей прямой задачи имеет следующий вид:
Другие задачи:[править]
- Каноническая задача;
- Производственная задача;
- Общая прямая задача линейного программирования;
- Классическая транспортная задача;
- Распределительная задача;
- Задача о назначениях;
- Транспортная задача с промежуточными пунктами;
- Трёхиндексная транспортная задача;
- Задача целочисленного программирования;
- Задача о рюкзаке.
Ссылки[править]
- Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
- Участник:Logic-samara