"The task of the direct-sales representative" is among combinatorial tasks. The finite decision represents a cycle. It is the task also belongs to the class of the transport task or the task about optimal resource allocation. But it it is impossible to solve a simplex a method.
The algorithm of its decision consists in search of all cycles.
Error in what not all cycles are considered.
The code more low visually shows the decision of the classical transport task. Such task can be solved and a combinatorial method and a simplex.
In the task we have three points of departure and four assignments. The task consists in a choice of a route with the least expenses. GUI the interface visually shows a choice of cycles in the table. Demonstration is presented in the form of slow animation.
On the termination of iterations it is possible to look at the graph of ways.
Probably, it will help to solve a problem.
Comments in Russian. If there will be questions, will be glad to help. ---------------
Create a file - linearAlgebraGIn and copy there the following code. ------------------
function linearAlgebraGIn(arg)
global Mtemp CC
C = {['ba'] [5] [10] [20] [15]; [10] [8 Inf] [3 Inf] [5 Inf] [2 Inf]; [15] [4 Inf] [1 Inf] [6 Inf] [7 Inf]; [25] [1 Inf] [9 Inf] [4 Inf] [3 Inf]};
% матрица результатов
Mtemp =C;
if nargin == 0;
initialize
elseif arg == 0
action(Mtemp)
elseif arg == 1
ResultGraph(CC)
%elseif arg < 0
% setmode(arg)
else
initialize(arg);
end
end
function initialize % инициализация исходных параметров
global Mtemp
%---------------------------
% графический интерфейс
figNumber=figure( ...
'Visible','on', ...
'NumberTitle','of', ...
'Name','Linear - programming, metod of optimization');
axes( ...
'Units','normalized', ...
'Position',[-0.5 0.4 1.7 0.57])
colormap(Cool);
%set(figNumber, 'Renderer', 'OpenGL');
%set(figNumber,'DoubleBuffer','on')
% Set up the MiniCommand Window
top=0.30;
left=0.05;
right=0.70;
bottom=0.05;
labelHt=0.05;
spacing=0.005;
% First, the MiniCommand Window frame
frmBorder=0.02;
frmPos=[left-frmBorder bottom-frmBorder ...
(right-left)+2*frmBorder (top-bottom)+2*frmBorder];
uicontrol( ...
'Style','frame', ...
'Units','normalized', ...
'Position',frmPos, ...
'BackgroundColor',[0.50 0.50 0.50]);
% Then the text label
labelPos=[left top-labelHt (right-left) labelHt];
uicontrol( ...
'Style','text', ...
'Units','normalized', ...
'Position',labelPos, ...
'BackgroundColor',[0.50 0.50 0.50], ...
'ForegroundColor',[1 1 1], ...
'String','Info Window');
% Then the editable text field
fval=SimplexResult(Mtemp);
strcat('Simplex result =',num2str(fval))
mcwPos=[left bottom (right-left) top-bottom-labelHt-spacing];
mcwHndl=uicontrol( ...
'Style','edit', ...
'HorizontalAlignment','left', ...
'Units','normalized', ...
'Max',20, ...
'BackgroundColor',[1 1 1], ...
'Position',mcwPos, ...
'String',strcat('Simplex result =',num2str(fval)));
%====================================
% Information for all buttons
labelColor=[0.8 0.8 0.8];
top=0.95;
bottom=0.05;
left=0.75;
yInitLabelPos=0.90;
left=0.75;
labelWid=0.20;
labelHt=0.05;
btnWid=0.20;
btnHt=0.05;
% Spacing between the label and the button for the same command
btnOffset=0.003;
% Spacing between the button and the next command's label
spacing=0.05;
%====================================
% The CONSOLE frame
frmBorder=0.02;
yPos=0.05-frmBorder;
frmPos=[left-frmBorder yPos btnWid+2*frmBorder 0.9+2*frmBorder];
h=uicontrol( ...
'Style','frame', ...
'Units','normalized', ...
'Position',frmPos, ...
'BackgroundColor',[0.50 0.50 0.50]);
% The PLOT TYPE command popup button
btnNumber=1;
yLabelPos=top-(btnNumber-1)*(btnHt+labelHt+spacing);
labelStr=' Optimization type';
labelList=' Combinatoric classic| Combinatoric optimization';
cmdList=str2mat( ...
' 1 ',' 2 ');
% Generic label information
labelPos=[left yLabelPos-labelHt labelWid labelHt];
uicontrol( ...
'Style','text', ...
'Units','normalized', ...
'Position',labelPos, ...
'BackgroundColor',labelColor, ...
'HorizontalAlignment','left', ...
'String',labelStr);
% Generic popup button information
btnPos=[left yLabelPos-labelHt-btnHt-btnOffset btnWid btnHt];
hndl1=uicontrol( ...
'Style','popup', ...
'Units','normalized', ...
'Position',btnPos, ...
'String',labelList, ...
'UserData',cmdList);
%====================================
uicontrol('Style', 'text','BackgroundColor',[1 1 0], 'String', 'Number Iteration', 'Units','normalized',...
'Position', [left bottom+4*btnHt+spacing btnWid 0.5*btnHt]);
h_angle = uicontrol('Style', 'edit','FontWeight','bold','FontSize',[10],'String', '0', 'Units','normalized',...
'Position', [left bottom+2*btnHt+spacing btnWid 2*btnHt], 'Tag','PlotText');
callbackStr='set(gca,''Userdata'',-1)';
% The close button.
%callbackStr='ResultGraph @Mtemp';
stopHndl= uicontrol( ...
'Style','pushbutton', ...
'Units','normalized', ...
'Position',[left 7*bottom btnWid 2*btnHt], ...
'String','Show resylt graph', ...
'Callback', 'linearAlgebraGIn(1)');
%set(stopHndl,'Enable','off');
%---------------------------
% исходная матрица
%C = {['ba'] [5] [10] [20] [15]; [10] [8 0] [3 0] [5 0] [2 0];[15] [4 0] [1 0] [6 0] [7 0];[25] [1 0] [9 0] [4 0] [3 0]};
%global Mtemp
C=Mtemp;
for i = 2 : 4 % цикл по пунктам отправления
for j =2 : 5 % цикл по пунктам назначения
C {i, j}=num2str(C {i, j});
end
end
cellplot(C)
hold on; % транспонирует график
%[x,y] = ginput(1)
%-------------------
tempMin=0;
temp=0;
tempSum=0;
%action(Mtemp,C)
callbackStr='action(''Mtemp'',''C'')';
startHndl=uicontrol(...
'style','pushbutton', ...
'units','normalized', ...
'position',[left bottom btnWid 2*btnHt], ...
'string','Start', ...
'callback', 'linearAlgebraGIn(0)');
% Uncover the figure
hndlList=[mcwHndl h_angle stopHndl startHndl hndl1];
set(gcf,'Visible','on', ...
'UserData',hndlList);
end % function
function Mtemp= action(Mtemp)
CG=Mtemp; % сохраняем таблицу перед преобразованием
% конвертируем в строку для вывода на экран
[m,n]=size (Mtemp)
for i = 2 : m % цикл по пунктам отправления
for j =2 : n % цикл по пунктам назначения
Mtemp {i, j}=num2str(Mtemp {i, j});
%C {i, j}=num2str(C {i, j});
end
end
Mtemp=CG;
drawnow
cla
cellplot(Mtemp)
hold on; % транспонирует график
hndlList=get(gcf,'UserData');
set(hndlList(1),'String','Wait...');
[m,n]=size (Mtemp)
%m = 4; % количество пунктов оправления
%n = 5; % количество пунктов назначения
Jtemp = 0; % временный индекс
for i = 2 : m % цикл по пунктам отправления (по строкам матрицы)
for k = 2:n % получаем значения элементов c строки матрицы
V{k-1} = Mtemp{i,k}(1);
end
[tempMin,J] = min( [V{1:4}]); % 1. В первой строке матрицы С=(сij) отыскиваем наименьший элемент. Пусть это будет элемент с(1,j1).
temp=min (Mtemp {i, 1},Mtemp {1, J+1} ); % минимальное значение для пункта отправки и потребления
if Mtemp {1, J+1} > SumCol(J+1,i,Mtemp) % проверим, есть ли потребность в данном пункте?
Mtemp{i,J+1}(2)= temp; % 2. Полагаем x(1,j1)= min(a1, bj1).
end %if
if Mtemp {i, 1} > Mtemp {1, J+1}
% 3. Если a1 > bj1 отыскиваем в этой же строке второй наименьший элемент с(1,j2)
%и полагаем x(1,j2)= min(a1 - x(1, j1), bj2).
while Mtemp {i, 1}~= SumRow(i,n,Mtemp)% 4. Эти шаги продолжаем, пока не удовлетворим первое условие a1 = x(1,1j) + x(1,2j)+...+ x(1, nj).
V{J}= Inf;
Jtemp =J;
[tempMin,J] = min( [V{1:4}]); % отыскиваем в этой же строке второй наименьший элемент с(1,j2)
if (Mtemp {i, 1}- SumRow(i,n,Mtemp))== Mtemp {1, J+1}
% 5. Если на некотором шаге этого процесса окажется, что остаток от a1
% точно равен соответствующему b(jk), то
% положив x(1,jk)равным этому остатку x(1, jk) = b(jk)
Mtemp{i,J+1}(2)= (Mtemp {i, 1}- SumRow(i,n,Mtemp));
% 6. Полагаем следующее по величине значение переменной x(1, jk+1)=0 (выбранный нуль - дополняет набор до ациклического )
V{J}= Inf;
Jtemp =J;
[tempMin,J] = min( [V{1:4}]);
% 7. В столбцы соответствующие уравнения которых (потребности пунктов потребления) b1 = x(1i,1) + x(2i,1)+...+ x(mi, 1)
% полностью удовлетворены нули не записываются.
if SumCol(J+1,i,Mtemp) ~= Mtemp {1, J+1} %
Mtemp{i,J+1}(2)=0;
end %if
elseif Mtemp {1, J+1} > SumCol(J+1,i,Mtemp) && Mtemp{i,Jtemp+1}(2) ~= Inf % только если есть потребность в данном пункте, и была в предыдущем
Mtemp{i,J+1}(2)=min (Mtemp {i, 1} - Mtemp{i,Jtemp+1}(2),Mtemp {1, J+1} ); %и полагаем x(1,j2)= min(a1 - x(1, j1), bj2).
elseif Mtemp {1, J+1} > SumCol(J+1,i,Mtemp) && Mtemp{i,Jtemp+1}(2) == Inf % только если есть потребность в данном пункте и не было в предыдущем.
Mtemp{i,J+1}(2)=min (Mtemp {i, 1},Mtemp {1, J+1}- SumCol(J+1,i,Mtemp));%и полагаем x(1,j2)= min(a1 , b(i,j2) - SumCol (b(i,j2))).
end %if
end % while
end %if
end % конец цикла по пунктам отправления
CG=Mtemp; % сохраняем таблицу перед преобразованием
% конвертируем в строку для вывода на экран
for i = 2 : m % цикл по пунктам отправления
for j =2 : n % цикл по пунктам назначения
Mtemp {i, j}=num2str(Mtemp {i, j});
%C {i, j}=num2str(C {i, j});
end
end
cellplot(Mtemp)
hold on; % транспонирует график
Mtemp=CG;
%if tempMin==Inf
%text(0,0,'Error! No solve!','FontSize',18,'Color','r')
%end
%cellplot(C)
% выводим на экран граф
%G=[
%0 0 0 0 0 0 0 0 0 0 0 0;
%0 0 0 0 0 0 0 0 0 0 0 0;
%0 0 0 0 0 0 0 0 0 0 0 0;
%0 0 0 0 0 0 1 0 0 0 0 0;
%0 0 0 0 0 1 0 0 0 0 0 0;
%0 0 0 0 1 0 1 0 0 0 0 0;
%0 0 0 1 0 1 0 0 0 0 1 0;
%0 0 0 0 0 0 0 0 0 0 0 0;
%0 0 0 0 0 0 0 0 0 0 0 0;
%0 0 0 0 0 0 0 0 0 0 0 0;
%0 0 0 0 0 0 1 0 0 0 0 1;
%0 0 0 0 0 0 0 0 0 0 1 0 ;
%];% матрица смежности
%V=[1 4; 2 4; 3 4; 4 4;
% 1 3; 2 3; 3 3; 4 3;
% 1 2; 2 2; 3 2; 4 2;
%];% координаты вершин
[m,n] = size(CG); % размер исходного массива
% Вначале преобразуем матрицу, удалив из нее информационные строки
CT= cell(m-1,n-1);
for i = 1:m-1
for j = 1:n-1
CT{i,j}=CG{i+1,j+1};
end
end
[m,n] = size(CT); % размер исходного массива
% Теперь вектор (аналог всов вершин)
%vwieght =cell(1,m*n); % можно не объявлять
%vwieght =[1:m*n];% можно и так
c=1; % счетчик
for i = 1:m
for j = 1:n
vwieght{c}=CT{i,j};
vwieghtX{c}=CT{i,j}(2);
c=c+1;
end
end
% Теперь создание матрицы смежности (adjacency matrix)
[m,n] = size(vwieght); % размер исходного вектора
[J] = find( [vwieghtX{1:n}]==0); % находим нулевой элемент
for i = m:n % обнуляем массив
for j = m:n
AM(i,j)=0;
end
end
[J] = find( [vwieghtX{1:n}]~=Inf); % находим индексы x выбранных яччеек (узлов)
for i = m:n
if vwieght{i}(2)~= Inf
for j = i+1:n
if vwieght{j}(2)~= Inf && vwieght{j}(2)==0
AM(i,j)=1;
AM(j,i)=1;
break;
elseif vwieght{j}(2)~= Inf && vwieght{j}(2)~=0 && i> J(1) % нуль элемент
%обычно служит для дополнения и вернее всего(на данный момент уверенности
% конечно нет) следует после первого в цепи выбранного элемента
AM(i,j)=1;
AM(j,i)=1;
break;
end % if
end
end % if
end
V=[1.5 2-0.2; 2.5 2-0.2; 3.5 2-0.2; 4.5 2-0.2; % из -за включения режима hold переворачиваем граф
1.5 3-0.2; 2.5 3-0.2; 3.5 3-0.2; 4.5 3-0.2;
1.5 4-0.2; 2.5 4-0.2; 3.5 4-0.2; 4.5 4-0.2;
];% координаты вершин
n= 1:12; % количество вершин
gplot(AM(n,n),V,'-bo');
axis off
for j = 1:12, text(V(j,1),V(j,2), int2str(j),'FontSize',15); end
pause(1.9);
%text(1,4.3,['Result=', int2str(20)], 'HorizontalAlignment','center', 'BackgroundColor',[.7 .9 .7],'FontSize',15);
%text(4,4.3,['Simplex result=', num2str(SimplexResult(Mtemp))], 'HorizontalAlignment','center', 'BackgroundColor',[.7 .9 .7],'FontSize',15);
% форматируем матрицу для вывода в информационное окно
Cfor=Mtemp
[m,n]=size (Cfor)
stc=[]
stv=[]
for i = 1 : m % цикл по пунктам отправления
for j =1 : n % цикл по пунктам назначения
if i==1 && j>1
Cfor {i, j}=num2str(Cfor {i, j});
stc= strcat(stc,'[',Cfor{i,j},' ]')
else
Cfor {i, j}=num2str(Cfor {i, j});
stc= strcat(stc,'[',Cfor{i,j},']')
end
end
stv=strvcat(stv, stc)
stc=[]
end
set(hndlList(1),'ForegroundColor','b')
set(hndlList(1),'FontWeight',' bold')
stv=strvcat(stv, strcat('Simplex result =',num2str(SimplexResult(Mtemp))))
set(hndlList(1),'String',stv);
%strcat('Simplex result =',num2str(fval))
%set(hndlList(1),'ForegroundColor','k')
%set(hndlList(1),'FontWeight','normal')
%---------------------
% оптимизируем по классической схеме
hndlList=get(gcf,'UserData'); % берем данные из массива
OptimizationType= get(hndlList(5),'Value');% тип оптимизации
if OptimizationType==1
combClassic(Mtemp)
elseif OptimizationType==2
combOptimization(Mtemp)
end
end % function
function tempSum= SumCol(k,i,Mtemp)
tempSum=0;
for b = 2: i % суммируем данные в столбце
if Mtemp{b,k}(2) ~= Inf
tempSum=tempSum+Mtemp{b,k}(2);
end
end
%------------------------------
end %function
function tempSum= SumRow(k,n,Mtemp)
tempSum=0;
for b = 2: n % суммируем данные в строке
if Mtemp{k, b}(2) ~= Inf
tempSum=tempSum+Mtemp{k, b}(2);
end
end
%------------------------------
end %function
Create file - ResultGraph and copy there the following code.
function ResultGraph(arg)
%arg = {['ba'] [5] [10] [20] [15];
% [10] [8 Inf] [3 Inf] [5 Inf] [2 10];
% [15] [4 5] [1 10] [6 0] [7 Inf];
% [25] [1 Inf] [9 Inf] [4 20] [3 5]};
figNumber=figure( ...
'Visible','on', ...
'NumberTitle','of', ...
'Name','Linear - programming, result graph',...
'Color',[1.0 1.0 1.0],...
'Toolbar', 'none');
axes( ...
'Units','normalized', ...
'Position',[0.1 0.3 0.8 0.59])
[m,n] = size(arg); % размер исходного массива
% Вначале преобразуем матрицу, удалив из нее информационные строки
CT= cell(m-1,n-1);
for i = 1:m-1
for j = 1:n-1
CT{i,j}=arg{i+1,j+1};
end
end
[m,n] = size(CT); % размер исходного массива
AM=zeros(m+n,m+n);
for i = 1:m
AM(:)=0
for j = 1:n
if CT{i,j}(2)~= Inf %&& vwieght{j}(2)==0
AM(i,j+n-1)=1;
AM(j+n-1,i)=1;
TT{i}=AM
end % if
end
end
% из -за включения режима hold переворачиваем граф
V=[2 2-0.5; 2 3-0.5; 2 4-0.5;
3 1.5; 3 2.5; 3 3.5; 3 4.5; ];% координаты вершин
n= 1:m+n; % количество вершин
hold on
%subplot(2,1,1);
%for i = 1:m
gplot(TT{1}(n,n),V,'-og');
gplot(TT{2}(n,n),V,'-ob');
gplot(TT{3}(n,n),V,'-om');
%end
%gplot(AM(n,n),V,'-og');
axis off
label=['a1'; 'a2'; 'a3'; 'b1'; 'b2'; 'b3'; 'b4']
for j = n, text(V(j,1),V(j,2), label(j,1:end),'FontSize',15); end
Push button "Start", watch of iterations, after the optimization termination push the button "Show reesult graph". From the falling out menu select algorithm of optimization - "combinatoric classic | combinatoric opntimization"
