Реферат: Математическое программирование 2

1. Общая задача линейного программирования (ЗЛП):

Здесь (1) называется системой ограничений , ее матрица имеет ранг r £ n, (2) - функцией цели (целевой функцией). Неотрицательное решение (х₁ ⁰ , x₂ ⁰ , ... , x_n ⁰ ) системы (1) называется допустимым решением (планом) ЗЛП. Допустимое решение называется оптимальным, если оно обращает целевую функцию (2) в min или max (оптимум).

2. Симплексная форма ЗЛП. Для решения ЗЛП симплекс - методом необходимо ее привести к определенной (симплексной) форме:

(2`) f+c_r+1 x_r+1 + ... + c_s x_s + ... + c_n x_n = b₀ ® min

Здесь считаем r < n (система имеет бесчисленное множество решений), случай r = n неинтересен: в этом случае система имеет единственное решение и если оно допустимое, то автоматически становится оптимальным.

В системе (1`) неизвестные х<sub>1</sub> , х<sub>2</sub> , ... , х<sub>r</sub> называются базисными (каждое из них входит в одно и только одно уравнение с коэффициентом +1), остальные х<sub>r+1</sub> , ... , x<sub>n</sub> - свободными. Допустимое решение (1`) называется базисным (опорным планом), если все свободные неизвестные равны 0, а соответствующее ему значение целевой функции f(x₁ ⁰ , ... , x_r ⁰ ,0, ... ,0) называется базисным.

В силу важности особенностей симплексной формы выразим их и словами:

а) система (1`) удовлетворяет условиям :

1) все ограничения - в виде уравнений;

2) все свободные члены неотрицательны, т.е. b_i ³ 0;

3) имеет базисные неизвестные;

б) целевая функция (2`) удовлетворяет условиям :

1) содержит только свободные неизвестные;

2) все члены перенесены влево, кроме свободного члена b₀ ;

3) обязательна минимизация (случай max сводится к min по формуле max f = - min(-f)).

3) Матричная форма симплекс-метода. Симплексной форме ЗЛП соответствует симплекс - матрица :

1 0 ... 0 ... 0 a_1,r+1 ... a_1s ... a_1n b₁

0 1 ... 0 ... 0 a_2,r+1 ... a_2s ... a_2n b₂

.................................................................

0 0 ... 1 ... 0 a_i,r+1 ... a_is ... a_in b_i

.................................................................

0 0 ... 0 ... 1 a_r,r+1 ... a_rs ... a_rn b_r

0 0 ... 0 ... 0 c_r+1 ... c_s ... c_n b₀

Заметим, что каждому базису (системе базисных неизвестных ) соответствует своя симплекс - матрица , базисное решение х = (b₁ ,b₂ , ... ,b_r , 0, ... ,0) и базисное значение целевой функции f(b₁ ,b₂ , ... ,b_r , 0, ... ,0) = b₀ (см. Последний столбец !).

Критерий оптимальности плана . Если в последней (целевой) строке симплекс-матрицы все элементы неположительны, без учета последнего b₀ , то соответствующий этой матрице план оптимален,

т.е. с_j £ 0 (j = r+1, n) => min f (b₁ , ... ,b₂ ,0, ... ,0) = b₀ .

Критерий отсутствия оптимальности. Если в симплекс-матрице имеется столбец (S-й), в котором последний элемент с_s > 0, a все остальные элементы неположительны, то ЗЛП не имеет оптимального плана, т.е. с_s > 0, a_is £ 0 ( i= 1,r ) => min f = -¥.

Если в симплекс-матрице не выполняются оба критерия, то в поисках оптимума надо переходить к следующей матрице с помощью некоторого элемента a_is > 0 и следующих преобразований (симплексных):

1) все элементы i-й строки делим на элемент a⁺ _is ;

2) все элементы S-го столбца, кроме a_is =1, заменяем нулями;

3) все остальные элементы матрицы преобразуем по правилу прямоугольника, что схематично показано на фрагменте матрицы и дано в формулах:

a_kl ` = a_kb a_is - a_il a_ks = a_kl - a_il a_ks ;

a_is a_is

b_k ` = b<sub>k</sub> a<sub>is</sub> - b<sub>i</sub> a<sub>ks</sub> ; c<sub>l</sub> ` = c_l a_is - c_s a_il

a_is a_is

Определение . Элемент a_is ⁺ называется разрешающим, если преобразование матрицы с его помощью обеспечивает уменьшение (невозрастание) значения, целевой функции; строка и столбец, на пересечении которых находится разрешающий элемент, также называются разрешающими.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--