Решение тестовых задач линейного программирования в 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