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

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

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

Обозначения

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

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

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

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

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

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

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

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

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

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

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

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

x_j – j-тая переменная.

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

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

или

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

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

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

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

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

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

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

• Каноническая задача;
• Производственная задача;
• Общая прямая задача линейного программирования;
• Общая двойственная задача линейного программирования;
• Задачи транспортного типа;
• Задача целочисленного программирования;
• Задача о рюкзаке;
• Задача распределения средств;
• Задача замены оборудования.

Ссылки

• Юдин Д.Б., Гольштейн Е.Г. Линейное программирование., М.,1963.
• Участник:Logic-samara