Как решить задачу линейного программирования с помощью симплексного алгоритма

Я решаю следующую задачу линейного программирования, используя функцию linprog

%Objective Function
     %X1    X2    X3    X4    X5    X6    X7    X8    X9    X10   X11   X12   X13   X14   X15   X16   X17   X18
f = [0.669 0.654 0.503 0.683 0.670 0.673 0.749 0.655 0.660 0.583 1.243 0.639 2.024 2.156 1.672 0.473 0.139 0.687];

A = [];   b = [];   %Sin restricciones de desigualdad

%Restricciones de igualdad son:
     %X1  X2    X3   X4   X5   X6   X7   X8   X9   X10  X11   X12  X13  X14  X15  X16  X17  X18
Aeq=[0.1 0.12 0.335 0.15 0.18 0.19 0.12 0.15 0.15 0.15   0   0.15 0.11  0   0.13  0     0  0.46; %Nitrogeno
     0.3 0.24   0   0.03 0.05 0.04 0.27 0.03 0.24 0.15   0    0   0.52 0.52  0    0     0    0 ; %Fosforo
     0.1 0.12   0   0.31 0.15 0.19 0.08 0.2  0.12 0.15  0.50  0    0   0.34 0.44  0     0    0 ; %Potasio
      0    0    0    0    0    0    0    0    0    0     0   0.26  0    0    0    0    0.50  0 ; %Calcio
      0    0    0    0   0.06  0    0    0    0    0     0    0    0    0    0   0.17   0    0]; %Magnesio


beq = [285.71 ; %Demanda nutricional de Nitrogeno (kg/ha)
       305.33 ; %Demanda nutricional de Fosforo (kg/ha)
          450 ; %Demanda nutricional de Potasio (kg/ha)
       262.50 ; %Demanda nutricional de Calcio (kg/ha)
        41.50]; %Demanda nutricional de Magnesio (kg/ha)

%Limite inferior
lb = zeros(18,1);   
%Limite superior
ub = inf(18,1);        

x = linprog(f, A, b, Aeq, beq, lb, ub, options)

Solucion_optima = f*x

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

options = optimoptions('linprog','Algorithm','dual-simplex');

Итак, у меня есть симплексный алгоритм

iterM=100;

In=size(Aeq,1);

Xsol=[Aeq eye(In) beq
    f zeros(1,In) 0];

for iter=1:1:iterM
    fin=Xsol(end,1:end-1)<0;
    if fin==0
        break
    end
[a,c]=min(Xsol(end,:));

Xre=Xsol(:,end)./Xsol(:,c);

i=Xre<=0;

d=Xre;
d(i)=inf;

[beq,f]=min(d);

Xsol(f,1:end)=Xsol(f,1:end)/Xsol(f,c);

for i=1:1:size(Xsol,1)

    if i~=f
        Xsol(i,:)=Xsol(i,:)-(Xsol(i,c)*Xsol(f,:));
    end
end

end

for i=1:1:size(f,2)
    d=logical(Xsol(:,i));
    X(i,1)=Xsol(d,end)
end

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


person John Doe    schedule 08.11.2018    source источник
comment
Вы ищете окончательную симплексную таблицу для полученного решения (базовое допустимое решение)? Непонятно, что вы просите. Пожалуйста, отредактируйте вопрос, чтобы было понятнее, что вы ищете.   -  person SecretAgentMan    schedule 09.11.2018
comment
Это итоговая таблица симплекса для полученного решения.   -  person John Doe    schedule 09.11.2018
comment
Если симплекс-алгоритм решает (задача допустима и ограничена), то он завершается на базовом допустимом решении. Я считаю, что это решение (крайняя точка) обеспечивается выходом. Когда вы говорите финальный стол, вы имеете в виду формат таблицы?   -  person SecretAgentMan    schedule 09.11.2018
comment
Таблицу можно получить, взяв inv(B)*A, где B — конечный базис (некоторые из столбцов матрицы ограничений A).   -  person SecretAgentMan    schedule 09.11.2018
comment
Если это то, что я имею в виду, вы можете создать ответ с решением   -  person John Doe    schedule 09.11.2018
comment
Я не уверен, что ты имеешь в виду. Зачем нужен финальный стол? Какова цель этого? Вам нужно снижение затрат? Вам нужно двойное решение?   -  person SecretAgentMan    schedule 09.11.2018
comment
Мне нужно снижение затрат, двойное решение и теневые цены   -  person John Doe    schedule 09.11.2018
comment
Смотрите ответ, который я только что опубликовал ... не стесняйтесь комментировать ответ для уточнения.   -  person SecretAgentMan    schedule 09.11.2018


Ответы (1)


На основании OP, в котором говорится: «Мне нужны сниженные затраты, двойное решение и теневые цены».

1) Двойственное решение — теневые цены. Теневые цены — это решение двойственности.

2) Окончательная симплексная таблица — не единственный способ достичь заявленных целей (хотя и сработает).

Двойное решение (теневые цены)
Вы можете получить двойное решение через [x,fval,exitflag,output,lambda] = linprog(___). lambda — это двойное решение; см. документацию и примеры MATLAB для linprog (ссылка). В документации эти множители называются множителями Лагранжа.

Снижение затрат
Снижения затрат можно добиться как с двойным решением, так и без него. Если f - коэффициенты целевой функции (затраты), то приведенные затраты = f'- p'*A при записи ЛП в стандартной форме A*x=b. Если кто-то еще знает лучший способ получить снижение затрат на выходе, пожалуйста, напишите. Я пытался избежать первичной формулы, чтобы не вытаскивать индекс основных переменных.

Четкая ссылка на это:
Bertsimas, Dimistris, and Tsitsiklis, John N. 1997. Introduction to Linear Optimization, Athena Scientific & Dynamic Ideas, LLC, Белмонт, Массачусетс. стр. 148

person SecretAgentMan    schedule 08.11.2018
comment
В лямбда это показывает мне следующую лямбда = структура с полями: нижняя: [18×1 двойной] верхний: [18×1 двойной] eqlin: [5×1 двойной] ineqlin: [] - person John Doe; 09.11.2018
comment
@SebastianSalazar, прости меня, я не понимаю, о чем ты спрашиваешь. Что случилось? - person SecretAgentMan; 09.11.2018
comment
Если это для школьных занятий и вы привыкли к представлению стандартной формы A*x=b, то решите с верхними границами = +inf и нижними границами = -inf и вместо этого поместите границы в A (не забудьте добавить в задачу переменные резерва, если вы не позволю linprog сделать это за тебя) Тогда вывод был бы более привычным. - person SecretAgentMan; 09.11.2018