Реферат: Исследование операций

.……………………………………

a_m1 x₁ +a_m2 x₂ +…+a_mj x_j +…+a_mn x_n b_n

x_j 0; j=1,n; i=1,m;

Z=C₁ x₁ +C₂ x₂ +…+C_j x_j +…+C_n x_n max (min);

2) Второй канонический вид:

a₁₁ x₁ +a₁₂ x₂ +…+a_1j x_j +…+a_1n x_n +y₁ =b₁

a₂₁ x₁ +a₂₂ x₂ +…+a_2j x_j +…+a_2n x_n +y₂ =b₂

………………………………………

a_i1 x₁ +a_i2 x₂ +…+a_ij x_j +…+ a_in x_n +y_i =b_i

.………………………………………

a_m1 x₁ +a_m2 x₂ +…+a_mj x_j +…+a_mn x_n +y_m =b_n

x_j 0; j=1,n; i=1,m;

Z=C₁ x₁ +C₂ x₂ +…+C_j x_j +…+C_n x_n max (min);

Чтобы решить задачу линейного программирования необходимо привести ее к каноническому виду.

Теоремы линейного програмирования:

Теорема 1. Множество допустимых решений основной задачи линейного программирования выпукло .

Теорема 2. Линейная функция задачи линейного программирования достигает своего экстремального значения в крайней точке множества решений .

При решении системы ограничений могут возникнуть следующие случаи:

1) Система ограничений несовместна, поэтому отыскать оптимальное решение невозможно (рис. 1.1).

2) Система ограничений имеет единственное решение ( рис. 1.2).

3) Система ограничений имеет конечное число решений (имеется замкнутая область допустимых решений). Оптимальное решение отыскивается среди решений, принадлежащих данной области(рис. 1.3).

4) Система ограничений имеет бесчисленное множество решений (рис. 1.4).

Рис. 1.1 Рис. 1.2Рис. 1.3 Рис. 1.4

C

a b