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

Версия 05:21, 14 января 2016

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

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

Обозначения

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

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