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

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

max F= 4x₁ + 5x₂ + 9x₃ + 11x₄. (2.3)

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

1x₁ + 1x₂ + 1x₃ + 1x₄ £ 15, (2.4)

7x₁ + 5x₂ + 3x₃ + 2x₄ £ 120, (2.5)

3x₁ + 5x₂ +10x₃+15x₄ £ 100, (2.6)

x₁³0, x₂ ³0, x₃ ³ 0, x₄ ³ 0. (2.7)

В этой за­даче формулируется следующее: требуется найти неотрицательное решение x₁,…,x₄, в системе неравенств (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.];

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

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

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

вектор, содержащий нижний (bl) и верхний (bu) пределы изменения переменных (x_j): 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 ={x₁=7.14, x₂=0, x₃=7.85, x₄=0};

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

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

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

max F= 2x₁ + 10x₂ + 6x₃ + 20x₄. (2.8)

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

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

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

x2=X ={x₁=0, x₂=12.5, x₃=0, x₄=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 ={y₁=1.8571, y₂=0, y₃=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