01.function varargout = SimplicialMethod(varargin)
02.% SIMPLICIALMETHOD M-file for SimplicialMethod.fig
03.% SIMPLICIALMETHOD, by itself, creates a new SIMPLICIALMETHOD or raises the existing
04.% singleton*.
05.%
06.% H = SIMPLICIALMETHOD returns the handle to a new SIMPLICIALMETHOD or the handle to
07.% the existing singleton*.
08.%
09.% SIMPLICIALMETHOD('CALLBACK',hObject,eventData,handles,...) calls the local
10.% function named CALLBACK in SIMPLICIALMETHOD.M with the given input arguments.
11.%
12.% SIMPLICIALMETHOD('Property','Value',...) creates a new SIMPLICIALMETHOD or raises the
13.% existing singleton*. Starting from the left, property value pairs are
14.% applied to the GUI before SimplicialMethod_OpeningFcn gets called. An
15.% unrecognized property name or invalid value makes property application
16.% stop. All inputs are passed to SimplicialMethod_OpeningFcn via varargin.
17.%
18.% *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one
19.% instance to run (singleton)".
20.%
21.% See also: GUIDE, GUIDATA, GUIHANDLES
22.% Edit the above text to modify the response to help SimplicialMethod
23.% Last Modified by GUIDE v2.5 29-Apr-2008 21:31:56
24.% Begin initialization code - DO NOT EDIT
25.gui_Singleton = 1;
26.gui_State = struct('gui_Name', mfilename, ...
27. 'gui_Singleton', gui_Singleton, ...
28. 'gui_OpeningFcn', @SimplicialMethod_OpeningFcn, ...
29. 'gui_OutputFcn', @SimplicialMethod_OutputFcn, ...
30. 'gui_LayoutFcn', [] , ...
31. 'gui_Callback', []);
32.if nargin && ischar(varargin{1})
33. gui_State.gui_Callback = str2func(varargin{1});
34.end
35.if nargout
36. [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
37.else
38. gui_mainfcn(gui_State, varargin{:});
39.end
40.% End initialization code - DO NOT EDIT
41.
42.% --- Executes just before SimplicialMethod is made visible.
43.function SimplicialMethod_OpeningFcn(hObject, eventdata, handles, varargin)
44.% This function has no output args, see OutputFcn.
45.% hObject handle to figure
46.% eventdata reserved - to be defined in a future version of MATLAB
47.% handles structure with handles and user data (see GUIDATA)
48.% varargin command line arguments to SimplicialMethod (see VARARGIN)
49.% Choose default command line output for SimplicialMethod
50.handles.output = hObject;
51.% Update handles structure
52.guidata(hObject, handles);
53.% UIWAIT makes SimplicialMethod wait for user response (see UIRESUME)
54.% uiwait(handles.figure1);
55.
56.% --- Outputs from this function are returned to the command line.
57.function varargout = SimplicialMethod_OutputFcn(hObject, eventdata, handles)
58.% varargout cell array for returning output args (see VARARGOUT);
59.% hObject handle to figure
60.% eventdata reserved - to be defined in a future version of MATLAB
61.% handles structure with handles and user data (see GUIDATA)
62.% Get default command line output from handles structure
63.varargout{1} = handles.output;
64.
65.function input_Callback(hObject, eventdata, handles)
66.% hObject handle to input (see GCBO)
67.% eventdata reserved - to be defined in a future version of MATLAB
68.% handles structure with handles and user data (see GUIDATA)
69.% Hints: get(hObject,'String') returns contents of input as text
70.% str2double(get(hObject,'String')) returns contents of input as a double
71.
72.% --- Executes during object creation, after setting all properties.
73.function input_CreateFcn(hObject, eventdata, handles)
74.% hObject handle to input (see GCBO)
75.% eventdata reserved - to be defined in a future version of MATLAB
76.% handles empty - handles not created until after all CreateFcns called
77.% Hint: edit controls usually have a white background on Windows.
78.% See ISPC and COMPUTER.
79.if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
80. set(hObject,'BackgroundColor','white');
81.end
82.
83.% --- Executes on button press in clear.
84.function clear_Callback(hObject, eventdata, handles)
85.% hObject handle to clear (see GCBO)
86.% eventdata reserved - to be defined in a future version of MATLAB
87.% handles structure with handles and user data (see GUIDATA)
88.set(handles.input,'String','0');
89.set(handles.shuchu,'String','0');
90.guidata(hObject,handles);
91.% --- Executes on button press in M.
92.function M_Callback(hObject, eventdata, handles)
93.% hObject handle to M (see GCBO)
94.% eventdata reserved - to be defined in a future version of MATLAB
95.% handles structure with handles and user data (see GUIDATA)
96.in = get(handles.input,'String');
97.B = str2num(in);
98.[x,fval,flag,iteration]=finalsimple(B)
99.result = sprintf('解的状态:\nflag = %d\n(0 唯一解，1 无穷多，2 无界解，3 无解)\n最优解为:\nx = ( %s )\n最优值为:\nfval = %.2f\n单纯形法迭代次数:\niteration = %d\n',flag,num2str(x),fval,iteration);
100.set(handles.shuchu,'String',result);
101.guidata(hObject,handles);
102.
103.% --- Executes on button press in twosteps.
104.function twosteps_Callback(hObject, eventdata, handles)
105.% hObject handle to twosteps (see GCBO)
106.% eventdata reserved - to be defined in a future version of MATLAB
107.% handles structure with handles and user data (see GUIDATA)
108.in = get(handles.input,'String');
109.B = str2num(in);
110.[x,fval1,fval2,flag,iteration]=twosteps(B);
111.result = sprintf('第一阶段:\nfval1 = %.2f\n第二阶段:\n解的状态:\nflag = %d\n(0 唯一解，1 无穷多，2 无界解，3 无解)\n最优解为:\nx = ( %s )\n最优值为:\nfval = %.2f\n单纯形法迭代次数:\niteration = %d\n',fval1,flag,num2str(x),fval2,iteration);
112.set(handles.shuchu,'String',result);
113.guidata(hObject,handles);
114.
复制代码
=========================================
originalsimple.m [原始单纯形法]
01.function [x,fval,flag,iteration]=originalsimple(C,A,b,XB)
02.%原始单纯形法（需直接给出初始的基变量）
03.%Programmed by Liyang(faruto's Studio~!) BNU MATH
04.%Email:liyangbnu@mail.bnu.edu.cn QQ:516667408
05.%last modified 2008.4.27
06.%求解标准型线性规划:max C*X;s.t. A*X=b (b>=0);X>=0;
07.%输入：C是n维行向量，A是m*n的系数矩阵，b是m维列向量，XB承装初始基变量的下标
08.%输出：x最优解（如果有的话），fval最优值，flag解的状态说明，interation求解时的循环次数
09.%flag 最终解的状态说明：
10.%flag = 0 LP converged to a solution x
11.%flag = 1 Inf feasible solutions
12.%flag = 2 LP is unbounded
13.%flag = 3 No feasible point was found
14.
15.[m,n] = size(A);
16.iteration = 0;
17.pflag = 1;
18.while pflag
19. iteration = iteration +1;
20. flag = 0;
21.
22.%%
23. sigma = zeros(1,n);
24. for col = 1:n
25. temp = 0;
26. for row = 1:m
27. temp = temp+C(XB(row))*A(row,col);
28. end
29. sigma(col) = C(col)-temp;
30. end
31.
32.%%
33. if sigma<=0
34. x = zeros(1,n);
35. for row = 1:m
36. x(XB(row)) = b(row);
37. end
38. fval = C*x';
39.
40. for row = 1:m
41. for temp = n+1:n+m
42. if XB(row)==temp && x(temp)~=0
43. flag = 3;
44. pflag = 0;
45. break;
46. end
47. end
48. if flag == 3
49. break;
50. end
51. end
52. if flag == 3
53. break;
54. end
55.
56. for col = 1:n
57. tflag = 0;
58. for row = 1:m
59. if col == XB(row)
60. tflag = 1;
61. break;
62. end
63. end
64. if tflag == 0
65. if sigma(col) == 0
66. flag = 1;
67. pflag = 0;
68. break;
69. end
70. end
71. end
72. if flag == 1
73. break;
74. end
75.
76. if flag == 0;
77. pflag = 0;
78. fval;
79. break;
80. end
81. else
82. for col = 1:n
83. if sigma(col)>0 & A(:,col)<=0
84. flag = 2;
85. pflag = 0;
86. break;
87. end
88. end
89. if flag == 2
90. break;
91. end
92.
93.%%
94. temp = 0;
95. for col = 1:n
96. if sigma(col)>temp
97. temp = sigma(col);
98. intobase = col;%入基变量的下标
99. end
100. end
101.
102. theta = zeros(m,1);
103. for row = 1:m
104. if A(row,intobase)>0
105. theta(row) = b(row)/A(row,intobase);
106. end
107. end
108. temp = Inf;
109. for row = 1:m
110. if theta(row)>0 & theta(row) 111. temp = theta(row); 112. outbase = XB(row);%出基变量的下标 113. outrow = row;%出基变量在基变量中的位置 114. end 115. end 116. 117.%% 118. b(outrow,1) = b(outrow,1)/A(outrow,intobase); 119. A(outrow,:) = A(outrow,:)/A(outrow,intobase); 120. 121. for row = 1:m 122. if row ~= outrow 123. b(row) = b(row) - b(outrow)*A(row,intobase); 124. A(row,:) = A(row,:) - A(outrow,:)*A(row,intobase); 125. 126. end 127. end 128.%% 129. 130. for row = 1:m 131. if XB(row) == outbase; 132. XB(row) = intobase; 133. end 134. end 135. end 136.end 137.%% 138.if flag == 0 139. disp('LP converged to a solution x!'); 140. x; 141. fval; 142.end 143.if flag == 1 144. disp('Inf feasible solutions!'); 145. disp('one of the solutions is:'); 146.end 147.if flag == 2 148. disp('LP is unbounded!'); 149.end 150.if flag == 3 151. disp('No feasible point was found!'); 152.end 02.%原始单纯形法（大M法，无需给出初始基变量） 03.%Programmed by Liyang(faruto's Studio~!) BNU MATH 04.%Email:liyangbnu@mail.bnu.edu.cn QQ:516667408 05.%last modified 2008.4.27 06.%求解标准型线性规划:max C*X;s.t. A*X=b (b>=0);X>=0; 07.%输入：C是n维行向量，A是m*n的系数矩阵，b是m维列向量 08.%输出：x最优解（如果有的话），fval最优值，flag解的状态说明，interation求解时的循环次数 09.%flag 最终解的状态说明： 10.%flag = 0 LP converged to a solution x 11.%flag = 1 Inf feasible solutions 12.%flag = 2 LP is unbounded 13.%flag = 3 No feasible point was found 14.M = 1e5; 15.[m,n] = size(A); 16.A = [A,eye(m)]; 17.for run = 1:1:m 18. C = [C,-M]; 19.end 20.XB = (n+1:n+m);%XB承装初始基变量的下标 21.n = n+m; 22.iteration = 0; 23.while 1 24. iteration = iteration +1; 25. flag = 0; 26. 27.%% 28. sigma = zeros(1,n); 29. for col = 1:n 30. temp = 0; 31. for row = 1:m 32. temp = temp + C(XB(row))*A(row,col); 33. end 34. sigma(col) = C(col)-temp; 35. end 36. 37.%% 38. if sigma<=0 39. 40. x = zeros(1,n); 41. for row = 1:m 42. x(XB(row)) = b(row); 43. end 44. fval = C*x'; 45. 46. for row = 1:m 47. for temp = n-m+1:n 48. if XB(row)==temp && x(temp)~=0 49. flag = 3; 50. x = 0; 51. fval = 0; 52. break; 53. end 54. end 55. if flag == 3 56. break; 57. end 58. end 59. if flag == 3 60. break; 61. end 62. 63. for col = 1:n 64. tflag = 0; 65. for row = 1:m 66. if col == XB(row) 67. tflag = 1; 68. break; 69. end 70. end 71. if tflag == 0 72. if sigma(col) == 0 73. flag = 1; 74. break; 75. end 76. end 77. end 78. if flag == 1 79. x = x(:,1:n-m); 80. break; 81. end 82. 83. if flag == 0; 84. x = x(:,1:n-m); 85. fval; 86. break; 87. end 88. 89. else 90. for col = 1:n 91. if sigma(col)>0 & A(:,col)<=0 92. flag = 2; 93. x = 0; 94. fval = 0; 95. break; 96. end 97. end 98. if flag == 2 99. break; 100. end 101. 102.%% 103. temp = 0; 104. for col = 1:n 105. if sigma(col)>temp 106. temp = sigma(col); 107. intobase = col;%入基变量的下标 108. end 109. end 110. 111. theta = zeros(1,m); 112. for row = 1:m 113. if A(row,intobase)>0 114. theta(row) = b(row)/A(row,intobase); 115. end 116. end 117. temp = Inf; 118. for row = 1:m 119. if theta(row)>0 & theta(row) 120. temp = theta(row); 121. outbase = XB(row);%出基变量的下标 122. outrow = row;%出基变量在基变量中的位置 123. end 124. end 125. 126.%% 127. b(outrow) = b(outrow)/A(outrow,intobase); 128. A(outrow,:) = A(outrow,:)/A(outrow,intobase); 129. 130. for row = 1:m 131. if row ~= outrow 132. b(row) = b(row) - b(outrow)*A(row,intobase); 133. A(row,:) = A(row,:) - A(outrow,:)*A(row,intobase); 134. 135. end 136. end 137. 138.%% 139. for row = 1:m 140. if XB(row) == outbase; 141. XB(row) = intobase; 142. end 143. end 144. end 145.end 146.%% 147.if flag == 0 148. disp('LP converged to a solution x!'); 149. x; 150. fval; 151.end 152.if flag == 1 153. disp('Inf feasible solutions!'); 154. disp('one of the solutions is:'); 155.end 156.if flag == 2 157. disp('LP is unbounded!'); 158.end 159.if flag == 3 160. disp('No feasible point was found!'); 161.end 162. 163. 02.%将普通LP问题标准化至标准型线性规划:max C*X;s.t. A*X=b (b>=0);X>=0; 03.%Programmed by Liyang(faruto's Studio~!) BNU MATH 04.%Email:liyangbnu@mail.bnu.edu.cn QQ:516667408 05.%last modified 2008.4.27 06.%输入：B=[C',0 , +1(-1) 07.% A',b', +1(-1,0)] 08.%其中C'是原问题中目标函数的系数，A'是原问题中约束条件不等号左边的系数矩阵，b'是原问题中不等号右边的约束列向量。 09.%B的第一行倒数第二个元素为0，最后一个元素为+1(或-1)，+1表示原问题的目标函数是求最大值，-1表示原问题的目标函数是求最小值。 10.%B的除第一行外的其他行的最后一个元素为+1(或-1或0)，+1表示该行所对应的不等号为">="，-1表示该行所对应的不等号为"<=",0表示 11.%该行对应的是等式。 12.%输出：经过标准化后的LP问题 13.% C是n维行向量，A是m*n的系数矩阵，b是m维列向量，lp=-1或1（-1表示原LP问题是求最小值，1表示原LP问题是求最大值） 14.[m,n] = size(B); 15.C = B(1,1:n-2); 16.A = B(2:m,1:n-2); 17.b = B(2:m,n-1); 18.lp = B(1,n); 19.sign = B(2:m,n); 20.[m,n] = size(A); 21.if lp == -1 22. C = -C; 23.end 24.for row = 1:m 25. if b(row)<0 26. b(row) = -b(row); 27. A(row,:) = -A(row,:); 28. sign(row) = -sign(row); 29. end 30. if sign(row) == 1 31. P = zeros(m,1); 32. P(row) = -1; 33. A = [A,P]; 34. C = [C,0]; 35. else if sign(row) == -1 36. P = zeros(m,1); 37. P(row) = 1; 38. A = [A,P]; 39. C = [C,0]; 40. else 41. continue 42. end 43. end 44.end 45. 46. 02.%对于一般的LP问题的单纯形法（基于大M法），需使用LPtostandard.m（标准化）,originalsimpleM.m（标准化求解）两个函数 03.%Programmed by Liyang(faruto's Studio~!) BNU MATH 04.%Email:liyangbnu@mail.bnu.edu.cn QQ:516667408 05.%last modified 2008.4. 06.%输入：B=[C',0 , +1(-1) 07.% A',b', +1(-1,0)] 08.%A是一个(m+1)*(n+2)维的矩阵 09.%其中C'是原问题中目标函数的系数，A'是原问题中约束条件不等号左边的系数矩阵，b'是原问题中不等号右边的约束列向量。 10.%A的第一行倒数第二个元素为0，最后一个元素为+1(或-1)，+1表示原问题的目标函数是求最大值，-1表示原问题的目标函数是求最小值。 11.%A的除第一行外的其他行的最后一个元素为+1(或-1或0)，+1表示该行所对应的不等号为">="，-1表示该行所对应的不等号为"<=",0表示 12.%该行对应的是等式。 13.%输出：x最优解（如果有的话），fval最优值，flag解的状态说明，interation求解时的循环次数 14.%flag 最终解的状态说明： 15.%flag = 0 LP converged to a solution x 16.%flag = 1 Inf feasible solutions 17.%flag = 2 LP is unbounded 18.%flag = 3 No feasible point was found 19.[m,n] = size(B); 20.n = n-2; 21.[C,A,b,lp]=LPtostandard(B); 22.[x,fval,flag,iteration]=originalsimpleM(C,A,b); 23.if flag ~= 3 24. x = x(1:n); 25.end 26.if lp == -1 27. x = -x; 28. fval = -fval; 29.end 30. 31.
复制代码==================================
originalsimpleM.m [大M法]
01.function [x,fval,flag,iteration]=originalsimpleM(C,A,b)
复制代码==========================================
LPtostandard.m [将LP问题进行标准化]
01.function [C,A,b,lp]=LPtostandard(B)
复制代码=============================
finalsimple.m
01.function [x,fval,flag,iteration]=finalsimple(B)