Решение тестовых задач линейного программирования в Matlab

Решение задачи линейного программирования (ЗЛП) (2.1)-(2.2) покажем на примере:

max F= 4x1 + 5x2 + 9x3 + 11x4. (2.3)

при ограничениях

1x1 + 1x2 + 1x3 + 1x4 £ 15, (2.4)

7x1 + 5x2 + 3x3 + 2x4 £ 120, (2.5)

3x1 + 5x2 +10x3+15x4 £ 100, (2.6)

x1³0, x2 ³0, x3 ³ 0, x4 ³ 0. (2.7)

В этой за­даче формулируется следующее: требуется найти неотрицательное решение x1,…,x4, в системе неравенств (2.4)-(2.7) такое, при котором функция F принимает мак­симальное значение.

Покажем это в системе Matlab в соответствии с алгоритмом решения ЗЛП (Симплекс-методом).

Пример 1. (Решение ЗЛП (2.2)-(2.7) с первым критерием)

Для решения ЗЛП в системе Matlab формируется сначала исходные данные в виде m-файла (см. Приложение к разделу 2.2):

целевая функция в виде вектора: f = [-4. -5. -9. -11.];

матрица линейных ограничений:

a = [1. 1. 1. 1.;

7. 5. 3. 2.;

3. 5. 10. 15.];

вектор, содержащий ограничения (bi): b=[15. 120. 100.];

ограничения равенства: Aeq=[]; Beq=[];

вектор начальных условий: X0=[0. 0. 0. 0.];

вектор, содержащий нижний (bl) и верхний (bu) пределы изменения переменных (xj): bl = [0.0 0.0 0.00]; bu = [40.0 40.0 40.0];

вектор начальных условий: x0 = [0. 0. 0. 0.]. Примечание, если используется нижняя и верхняя граница bl, bu, то x0 не используется.

Решение ЗЛП представляет обращение к функции linprog, решающей задачу линейного программирования:

[x1, F1]=linprog(f1,a,b,Aeq,Beq, bl, bu,x0),

где x1 - вектор неизвестных переменных; f1 – величина целевой функции.

В результате решения получим: оптимальные значения переменных:

x1=X ={x1=7.14, x2=0, x3=7.85, x4=0};

оптимальное значение целевой функции: F1=f =99.286.

Проверка F1x1=f1*x1 подтверждает этот результат.

Пример 2.(Решение ЗЛП (5.3.1)-(5.3.5) со вторым критерием:

max F= 2x1 + 10x2 + 6x3 + 20x4. (2.8)

Аналогично решается ЗЛП в системе Matlab и с другими критериями, например: f2=[0. -2. -10. -6. -20.].

[x2,F2]=linprog(f2,a,b,Aeq,beq,x0)

В результате решения получим: оптимальные значения переменных:

x2=X ={x1=0, x2=12.5, x3=0, x4=2.5};

оптимальное значение целевой функции: F2=f =175.

Проверка: F2x2=f2*x2

Пример 3. (Решение двойственной ЗЛП (5.3.1)-(5.3.5)).

Двойственная ЗЛП в системе Matlab решается с исходными данными, представленными в примере 1.

[y1,g1]=linprog(b,-a',f1,Aeq,Beq,y0,[],[],OPTIONS).

В результате решения получим: оптимальные значения переменных: y1=Y ={y1=1.8571, y2=0, y3=0.7143};

оптимальное значение целевой функции: g1=g =99.286.

Проверка: G2y2=g2*y2

Приложение к разделу 5.2.2.М-файл решения ЗЛП.

% The primal problem in standard form is

% min f'*x such that A*x = b, x >= 0.

% The dual problem is

% max b'*y such that A'*y + s = f, s >= 0.

f1=[-4. -5. -9. -11.]; f2=[-2. -10. -6. -20.];

a=[1. 1. 1. 1.; 7. 5. 3. 2.; 3. 5. 10. 15.];

b=[15. 120. 100.]; Aeq=[]; beq=[];

x0=zeros(4,1);

lb=[0. 0. 0. 0.];

ub=[40. 40. 40. 40.]; %,exitflag,output,lambda

[x1,F1]=linprog(f1,a,b,Aeq,beq,x0)

F1x1=f1*x1

[x2,F2]=linprog(f2,a,b,Aeq,beq,x0)

F2x2=f2*x2

%***************************************

disp('Dvoystvenay Zadacha');

%lengthX=length(x1)

y0=zeros(3,1);

OPTIONS=optimset('Display','final','GradObj','on')

% ,...'TolFun',20,'TolPCG',20,'TolX',20) %,'TypicalX','on')

[y,g1]=linprog(b,-a',f1,Aeq,beq,y0,[],[],OPTIONS)%LB,UB,X0,OPTIONS

%lengthY=length(y)

g1y=b*y

Наши рекомендации