Реферат: Линейное программирование, решение задач симплексным методом

b_mn

: (-a_rs )

которая получается по правилам 1 – 5 ОЖИ с тем лишь изменением, что правила 2 и 3 меняются ролями:

1) остальные элементы разрешающей строки остаются без изменения

2) остальные элементы разрешающего столбца меняют лишь свои знаки

Рассмотрим систему

2X₁ + 3X₂ – 5X₃ = 16 = b₁ ,

3X₁ - 2X₂ + 4X₃ = 36 = b₂ ,

5X₁ + 7X₂ – 11X₃ = 44 = b₃ .

Запишем ее в виде таблицы

	-x1	-x2	-x3
b1 =	-2	-3	5
b2 =	-3	2	-4
b3 =	-5	-7	11

и произведем один шаг МЖИ с разрешающим элементом “2”

	-x1	-b2	-x3
b1 =	-13	3	-2
x2 =	-3	1	-4
b3 =	-31	7	-6

: 2

Экстремумы линейной функции

Пусть рассматривается общая задача линейного програм­мирования. В основе вычислительных методов ЛП лежит следующая фундаментальная теорема.

Теорема. Если задача линейного программирования име­ет оптимальное решение

(в ограниченной области всегда, а в неограниченной области в зависимости от ограниченности функции Z), то оно совпадает по крайней мере с одним из опорных решений системы ограничительных уравнений.

Согласно этой теореме вместо исследования бесконечно­го множества допустимых решений с целью нахождения сре­ди них искомого оптимального решения, необходимо иссле­довать лишь конечное число опорных решений.

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

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

1. С помощью ЖИ найдем все опорные решения систе­мы.

a₁₁ x₁ + a₁₂ x₂ + … + a_1n x_n = b₁ ,

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

a_k1 x₁ + a_k2 x₂ + … + a_kn x_n = b_k ,

a_k+1,1 x₁ + a_k+1,2 x₂ + … + a_k+1n x_n ≤ b_k+1 ,

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

a_m1 x₁ + a_m2 x₂ + … + a_mn x_n ≤ b_m .

2. Вычислим для каждого из них значение функции Z, определяемое соотношением.

Z = c₁ x₁ + c₂ x₂ + … + c_n x_{n .}

3. Выберем из них экстремальное Z.

Следует отметить, что может оказаться очень большое число опорных решений, поэтому нужно производить упо­рядоченный перебор опорных решений, добиваясь на