2. Алгебраическая формулировка задачи линейного программирования

Определение:

Задача математического программирования L(x) min ( или max), x называется задачей линейного программирования, если функция L линейно зависит от xR , множество  задано в R системой из конечного числа ограничений и каждое из ограничений есть неравенство вида:

ai1 x1 + ai2 x2 + ... + ain xn =bi (i= 1, ... ,k)

или как неравенство вида:

ai1 x1 + ai2 x2 + ... + ain xn <= bi (i= k+1, ... , m)

Линейную функцию переменного x = ( x1, x2, ... , xn) R записывают ввиде:

L(x) = c1 x1+ c2 x2 + ... + cn xn , где сjR (j= 1, ... , n) -некоторые коэффициенты.

Правила преобразования линейных моделей

Правило 1: Переход от максимизации к минимизации

В линейном программировании любая задача максимизации может быть сведена к эквивалентной задаче минимизации ( и наоборот), если одновременно с изменением “знака” оптимизации произвести изменение знаков перед всеми коэффициентами в выражении для целевой функции.

n

Так ,например, максимизация  сjxj эквивалентна минимизации j=1

n

 (-сj ) xj. Если при этом V - оптимальное значение линейной формы j=1

n n

 (-сj ) xj, V - оптимальное значение линейной формы сjxj.

j=1 j=1

Правило 2: Переход к эквивалентной системе неравенств Каждое из неравенств, фигурирующих в модели линейного програм

мирования , можно записать в инверсивной форме, если учесть, что

n n

ajxj <= b эквивалентно ( - aj) xj >= - b

j=1 j=1

Например:

1 x1 -1 x2 <= -4 эквивалентно неравенству

-1x1 -1x2 >= 4

Правило3: Обращение неравенства в равенство

Любое фигурирующее в линейной модели неравенство можно определить в виде равенства, если ввести в рассмотрение новую неотрицательную переменную. Это достигается следующим образом:

n n

 аjxj<=b можно записать в виде  ajxj+1s=b, где s>=0, (2)

j=1 j=1

n n

 аjxj>=b можно записать в виде  ajxj-1t=b, где t->=0, (3)

j=1 j=1

Переменную типа s в (2) принято называть остаточной переменной, а переменную типа t в (3) обычно называют избыточной переменной.

Правило 4: Обращение равенства в неравенство

Любое линейное уравнение, а также любую систему линейных уравнений можно представить в виде некоторой совокупности линейных неравенств с помощью одного дополнительного ограничителя.

n

Систему уравнений  ajxj = bi ( i=1,2,...m ) (4)

j=1

n n

можно записать в виде  ajxj <= bi ( i = 1,2,...m ),  jxj <= , (5)

j=1 j=1

m m

где j= -  aij, = -  bi (6)

i=1 i=1

Таким образом, при m=1 соотношения (5) сводятся к

n n

 a1xj <= b1, -  1xj <= b1, (7)

j=1 j=1

Пример: Рассмотрим систему уравнений:

1x + 1x2 = 1,

2x1 - 4x3 = -5.

С помощью формул (5) и (6) нетрудно показать, что эта система эквивалентна следующей системе неравенств:

1x1 + 1x2 <= 1,

2x1 - 4x3 <= -5,

-3x1 - 1x2 + 4x3 <= 4.

Правило 5 : Переход от переменных, не имеющих ограничения в знаке, к неотрицательным переменным

Когда для некоторого j значение переменной xj, фигурирующей в той или иной линейной модели, не ограничено в знаке, в процессе нахождения численного решения оказываются полезными следующие два типа преобразований. Преобразование первого типа заключается в следующем:

1.Выбирается одно из ограничений, содержащее переменную xj и записанное в виде равенства ( т.е. в виде линейного уравнения). Это всегда можно сделать(возможно после обращения неравенства в равенство).

2. Выбранное уравнение разрешается относительно xj и полученный результат подставляется во все остальные линейные ограничения, а также в выражение для целевой функции.

3.Производится упрощение путем приведения подобных членов.

Например: Предположим, что в соотношении (1) переменная x1 не ограничена в знаке. Тогда [после обращения (1) в равенство]

1 n

x1=  ( b1 -  a1j xj ). (8)

a1 j=2

Правую часть соотношения (8) требуется теперь подставить вместо x1 всюду, где только эта переменная фигурирует в модели. Легко убедиться, что полученные в результате такой подстановки соотношения сохраняют линейный характер и содержат все переменные, кроме x1.

В процессе нахождения оптимального решения на соотношение, полученное в результате решения относительно xj выбранного вначале уравнения можно не обращать внимания. Это соотношение позволит вычислить xj после того, как будет получено решение для остальных переменных.

Преобразование второго типа состоит в том, что xj полагается равным разности двух неотрицательных переменных и затем эта разность подставляется вместо переменной xj всюду, где она фигурирует. Другими словами полагается:

x j = xj’ - xj” , где xj’ >= 0 и xj” >= 0. (9)

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

Преобразование третьего типа, тесно связано с рассуждениями, с помощью которых были получены соотношения (4)-(6), заключается в добавлении к каждой переменной xj’ не имеющей ограничений в знаке, одной и той же неотрицательной переменной z с последующим обращением

xj = xj’ - z, где xj >= 0 и z >= 0. (I)

Пусть переменная xj для j=1,2, ... , k<=n не ограничена в знаке. Тогда ограничения

n

 aij x j = bi (i=1,2, ... , m) (II)

j=1

преобразуются к виду

k n

 aij x j ’ +  aij x j - i z = bi (i=1,2, ... , m), (III)

j=1 j=k+1

где k

i = aij (i=1,2, ... , m). (IV)

j=1

Правило 6: Переход от переменных, значения которых ограничены снизу, к неотрицательным переменным

Когда xj ограничена снизу некоторой константой bj  0, возможен переход к следующей формулировки задачи линейного программирования, в которой вместо xj фигурирует неотрицательная переменная xj ’. Это достигается с помощью преобразования .

xj  bj + xj’, где xj’>=0, (10)

и последующей подстановкой xj’ всюду где она фигурирует.