Материал: Основы математического моделирования. курс лекций. Перова А.В

x i1 ... x im bi , i 1, n ;

x ij 0 , i 1, n , j 1, m .

Для формализации данной постановки в виде задачи линейного программирования введем новую переменную:

Тогда окончательный вид математической модели задачи:

n

aijxij yk j 0,j 1,m

y max i 1

m

xij bi ,i 1, n

j 1

ЛЕКЦИЯ 6 МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

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

65

1.Для перехода от задачи максимизации к задаче минимизации целевую функцию необходимо умножить на –1.

2.Переменные, на которых не наложено ограничение неотрицательности, заменяются во всех ограничениях и в целевой функции разностью двух неотрицательных переменных

xj = uj- wj uj, wj 0.

3.Переход к ограничениям с неотрицательными правыми частями осуществляется умножением левой и правой частей ограничений с отрицательными правыми частями на –1. При этом знаки соответствующих неравенств меняются на противоположные.

4.Переход от ограничений-неравенств к ограничениямравенствам производится путем введения дополнительных неотрицательных переменных. При этом если знак неравенства

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

ничение-неравенство ai1x1 + ai2x2 +…+ ainxn bi преобразуется в ограничение-равенство

ai1x1 + ai2x2 +…+ ainxn + xn+1 = bi (xn+1 0),

где xn+1 – дополнительная переменная, xn+1 0. Ограничение-неравенство:

ai1x1 + ai2x2 +…+ ainxn bi

преобразуется в ограничение-равенство следующим образом:

ai1x1 + ai2x2 +…+ ainxn - xn+1 = bi (xn+1 0)

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

Рассмотрим ЗЛП в канонической форме:

66

n

F C j x j min;

Вектор X = (x1,…, xn), удовлетворяющий системе огра-

ничений ЗЛП, называется допустимым решением или планом.

План, X*=(x1*,…,xn*), при котором целевая функция принимает оптимальное значение, называется оптимальным. Перепишем ЗЛП в векторной форме.

n

F C j x j min ;

j 1

n

Ai x j B, i 1, m;

j 1

x j 0, j 1,n,

где A1,…,An – m-мерные вектор-столбцы, составленные из коэффициентов при переменных в системе ограничений:

B – вектор-столбец свободных членов системы ограничений:

j 1

но независима. Так как векторы Аj являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше, чем m. Симплексный метод решения ЗЛП основан на переходе от одного опорного плана к другому, при котором значение целевой

67

функции убывает. Указанный переход возможен, если известен какой-нибудь исходный опорный план. Такой план можно легко указать, если ЗЛП записана в форме:

F c1x1 c 2 x 2 c n x n min;

x1 a1m 1x m 1 a1n x n b1 ; x 2 a 2m 1x m 1 a 2n x n b 2 ;

x m a mm 1x m 1 a mn x n b m ;

x j 0, j 1, n.

Векторная форма данной задачи имеет вид:

n

F c j x j min ;

j 1

A 1 x 1 A 2 x 2 A m 1 x m 1 A n x n B;

Переменные, которые входят только в одно уравнение системы ограничений с коэффициентом равным 1, называют базисными переменными (в рассматриваемом примере это переменные x1… xm). Остальные переменные называются свободными. Тогда, приравнивая базисные переменные соответствующим правым частям ограничений, а свободные переменные нулю, получим опорный план X = (b1, b2,…, bm,0 ,…,0), определяемый системой единичных векторов, А1,…, Аm , которые образуют базис m-мерного пространства.

68

Для удобства расчетов в симплексном методе все данные по задаче заносят в симплекс-таблицу (табл. 5).

В верхнюю строку таблицы заносятся коэффициенты при всех переменных в целевой функции. В первом столбце таблицы записываются базисные переменные в той последовательности, в которой они входят в систему ограничений, во втором – коэффициенты целевой функции при базисных переменных, в третьем – правые части всех ограничений, в последующих столбцах – коэффициенты при соответствующих переменных в системе ограничений.

В нижней строке таблицы записываются оценки по каждой переменной, определяемые следующим образом:

m

j c iaij cj. Очевидно, что для базисных переменных

i 1

оценки равны нулю.

На каждой итерации симплекс-метода осуществляется вывод из базиса какой-либо переменной и включение в него другой переменной с соответствующим пересчетом элементов таблицы. Перед решением задачи ее необходимо привести к канонической форме.

Основные шаги симплекс – метода:

1.Определение начального опорного плана.

2.Составление симплекс-таблицы.

m

3. Вычисление оценок j c i a ij c j .

i 1

69