求解線性規劃的演算法
Ⅰ 線性規劃這類問題應該怎麼解題
用MATLAB優化工具箱解線性規劃
命令：x=linprog（c，A，b）
命令：x=linprog（c，A，b，Aeq,beq）
注意：若沒有不等式： 存在，則令A=[ ]，b=[ ]. 若沒有等式約束, 則令Aeq=[ ], beq=[ ].
命令：[1] x=linprog（c，A，b，Aeq,beq, VLB，VUB）
[2] x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0）
注意：[1] 若沒有等式約束, 則令Aeq=[ ], beq=[ ]. [2]其中X0表示初始點
4、命令：[x,fval]=linprog(…)
返回最優解x及x處的目標函數值fval.
例1
解 編寫M文件小xxgh1.m如下：
c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6];
A=[0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08];
b=[850;700;100;900];
Aeq=[]; beq=[];
vlb=[0;0;0;0;0;0]; vub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
例2 解: 編寫M文件xxgh2.m如下：
c=[6 3 4];
A=[0 1 0];
b=[50];
Aeq=[1 1 1];
beq=[120];
vlb=[30,0,20];
vub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub
例3 （任務分配問題）某車間有甲、乙兩台機床，可用於加工三種工件。
假定這兩台車床的可用台時數分別為800和900，三種工件的數量分別為400、
600和500，且已知用三種不同車床加工單位數量不同工件所需的台時數和加工
費用如下表。問怎樣分配車床的加工任務，才能既滿足加工工件的要求，又使
加工費用最低
解 設在甲車床上加工工件1、2、3的數量分別為x1、x2、x3，在乙車床上
加工工件1、2、3的數量分別為x4、x5、x6。可建立以下線性規劃模型：
編寫M文件xxgh3.m如下:
f = [13 9 10 11 12 8];
A = [0.4 1.1 1 0 0 0
0 0 0 0.5 1.2 1.3];
b = [800; 900];
Aeq=[1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1];
beq=[400 600 500];
vlb = zeros(6,1);
vub=[];
[x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)
例4．某廠每日8小時的產量不低於1800件。為了進行質量控制，計劃聘請兩種不同水平的檢驗員。一級檢驗員的標准為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標准為：速度15小時/件，正確率95%，計時工資3元/小時。檢驗員每錯檢一次，工廠要損失2元。為使總檢驗費用最省，該工廠應聘一級、二級檢驗員各幾名？
解 設需要一級和二級檢驗員的人數分別為x1、x2人,
編寫M文件xxgh4.m如下：
c = [40;36];
A=[-5 -3];
b=[-45];
Aeq=[];
beq=[];
vlb = zeros(2,1);
vub=[9;15];
%調用linprog函數：
[x,fval] = linprog(c,A,b,Aeq,beq,vlb,vub)
結果為：
x =
9.0000
0.0000
fval =360
即只需聘用9個一級檢驗員。
4．控制參數options的設置
Options中常用的幾個參數的名稱、含義、取值如下:
(1) Display: 顯示水平.取值為』off』時,不顯示輸出; 取值為』iter』時,顯示每次迭代的信息;取值為』final』時,顯示最終結果.默認值為』final』.
(2) MaxFunEvals: 允許進行函數評價的最大次數,取值為正整數.
(3) MaxIter: 允許進行迭代的最大次數,取值為正整數
控制參數options可以通過函數optimset創建或修改。命令的格式如下：
(1) options=optimset(『optimfun』)
創建一個含有所有參數名,並與優化函數optimfun相關的默認值的選項結構options.
（2）options=optimset(『param1』,value1,』param2』,value2,...)
創建一個名稱為options的優化選項參數,其中指定的參數具有指定值,所有未指定的參數取默認值.
(3)options=optimset(oldops,『param1』,value1,』param2』,
value2,...)
創建名稱為oldops的參數的拷貝,用指定的參數值修改oldops中相應的參數.
例：opts=optimset(『Display』,』iter』,』TolFun』,1e-8)
該語句創建一個稱為opts的優化選項結構,其中顯示參數設為』iter』, TolFun參數設為1e-8.
用Matlab解無約束優化問題
一元函數無約束優化問題
常用格式如下：
（1）x= fminbnd (fun,x1,x2)
（2）x= fminbnd (fun,x1,x2 ，options)
（3）[x，fval]= fminbnd（...）
（4）[x，fval，exitflag]= fminbnd（...）
（5）[x，fval，exitflag，output]= fminbnd（...）
其中（3）、（4）、（5）的等式右邊可選用（1）或（2）的等式右邊。
函數fminbnd的演算法基於黃金分割法和二次插值法，它要求目標函數必須是連續函數，並可能只給出局部最優解。
例1 求 在0<x<8中的最小值與最大值
主程序為wliti1.m:
f='2*exp(-x).*sin(x)';
fplot(f,[0,8]); %作圖語句
[xmin,ymin]=fminbnd (f, 0,8)
f1='-2*exp(-x).*sin(x)';
[xmax,ymax]=fminbnd (f1, 0,8)
運行結果：
xmin = 3.9270 ymin = -0.0279
xmax = 0.7854 ymax = 0.6448
例2 對邊長為3米的正方形鐵板，在四個角剪去相等的正方形以製成方形無蓋水槽，問如何剪法使水槽的容積最大？
先編寫M文件fun0.m如下:
function f=fun0(x)
f=-(3-2*x).^2*x;
主程序為wliti2.m:
[x,fval]=fminbnd('fun0',0,1.5);
xmax=x
fmax=-fval
運算結果為: xmax = 0.5000,fmax =2.0000.即剪掉的正方形的邊長為0.5米時水槽的容積最大,最大容積為2立方米.
2、多元函數無約束優化問題
標准型為：min F(X)
命令格式為:
（1）x= fminunc（fun,X0 ）；或x=fminsearch（fun,X0 ）
（2）x= fminunc（fun,X0 ，options）；
或x=fminsearch（fun,X0 ，options）
（3）[x，fval]= fminunc（...）；
或[x，fval]= fminsearch（...）
（4）[x，fval，exitflag]= fminunc（...）；
或[x，fval，exitflag]= fminsearch
（5）[x，fval，exitflag，output]= fminunc（...）；
或[x，fval，exitflag，output]= fminsearch（...）
說明:
• fminsearch是用單純形法尋優. fminunc的演算法見以下幾點說明：
[1] fminunc為無約束優化提供了大型優化和中型優化演算法。由options中的參數LargeScale控制：
LargeScale=』on』(默認值),使用大型演算法
LargeScale=』off』(默認值),使用中型演算法
[2] fminunc為中型優化演算法的搜索方向提供了4種演算法，由
options中的參數HessUpdate控制：
HessUpdate=』bfgs』（默認值），擬牛頓法的BFGS公式；
HessUpdate=』dfp』，擬牛頓法的DFP公式；
HessUpdate=』steepdesc』，最速下降法
[3] fminunc為中型優化演算法的步長一維搜索提供了兩種演算法，
由options中參數LineSearchType控制：
LineSearchType=』quadcubic』(預設值)，混合的二次和三
次多項式插值；
LineSearchType=』cubicpoly』，三次多項式插
• 使用fminunc和 fminsearch可能會得到局部最優解.
例3 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)
1、編寫M-文件 fun1.m:
function f = fun1 (x)
f = exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);
2、輸入M文件wliti3.m如下:
x0 = [-1, 1];
x=fminunc(『fun1』,x0);
y=fun1(x)
3、運行結果:
x= 0.5000 -1.0000
y = 1.3029e-10
例4 Rosenbrock 函數 f（x1，x2）=100（x2-x12）2+(1-x1)2
的最優解（極小）為x*=（1，1），極小值為f*=0.試用
不同演算法（搜索方向和步長搜索）求數值最優解.
初值選為x0=（-1.2 , 2）.
1. 為獲得直觀認識，先畫出Rosenbrock 函數的三維圖形,
輸入以下命令：
[x,y]=meshgrid(-2:0.1:2,-1:0.1:3);
z=100*(y-x.^2).^2+(1-x).^2;
mesh(x,y,z)
2. 畫出Rosenbrock 函數的等高線圖,輸入命令：
contour(x,y,z,20)
hold on
plot(-1.2,2,' o ');
text(-1.2,2,'start point')
plot(1,1,'o')
text(1,1,'solution')
3.用fminsearch函數求解
輸入命令:
f='100*(x(2)-x(1)^2)^2+(1-x(1))^2';
[x,fval,exitflag,output]=fminsearch(f, [-1.2 2])
運行結果:
x =1.0000 1.0000
fval =1.9151e-010
exitflag = 1
output =
iterations: 108
funcCount: 202
algorithm: 'Nelder-Mead simplex direct search'
4. 用fminunc 函數
(1)建立M-文件fun2.m
function f=fun2(x)
f=100*(x(2)-x(1)^2)^2+(1-x(1))^2
(2)主程序wliti44.m
Rosenbrock函數不同演算法的計算結果
可以看出，最速下降法的結果最差.因為最速下降法特別不適合於從一狹長通道到達最優解的情況.
例5 產銷量的最佳安排
某廠生產一種產品有甲、乙兩個牌號，討論在產銷平衡的情況下如何確定各自的產量，使總利潤最大. 所謂產銷平衡指工廠的產量等於市場上的銷量.
符號說明
z(x1,x2)表示總利潤；
p1，q1，x1分別表示甲的價格、成本、銷量；
p2，q2，x2分別表示乙的價格、成本、銷量；
aij，bi，λi,ci（i，j =1，2）是待定系數.
基本假設
1．價格與銷量成線性關系
利潤既取決於銷量和價格，也依賴於產量和成本。按照市場規律，
甲的價格p1會隨其銷量x1的增長而降低，同時乙的銷量x2的增長也
會使甲的價格有稍微的下降，可以簡單地假設價格與銷量成線性關系，
即： p1 = b1 - a11 x1 - a12 x2 ，b1，a11，a12 > 0，且a11 > a12；
同理， p2 = b2 - a21 x1- a22 x2 ，b2，a21，a22 > 0
2．成本與產量成負指數關系
甲的成本隨其產量的增長而降低,且有一個漸進值,可以假設為
負指數關系,
總利潤為： z(x1,x2)=(p1-q1)x1+(p2-q2)x2
若根據大量的統計數據,求出系數b1=100,a11=1,a12=0.1,b2=280,
a21=0.2,a22=2,r1=30,λ1=0.015,c1=20, r2=100,λ2=0.02,c2=30,則
問題轉化為無約束優化問題：求甲,乙兩個牌號的產量x1，x2，使總利潤z最大.
為簡化模型,先忽略成本,並令a12=0,a21=0,問題轉化為求:
z1 = ( b1 - a11x1 ) x1 + ( b2 - a22x2 ) x2
的極值. 顯然其解為x1 = b1/2a11 = 50, x2 = b2/2a22 = 70,
我們把它作為原問題的初始值.
模型求解
1.建立M-文件fun.m:
function f = fun(x)
y1=((100-x(1)- 0.1*x(2))-(30*exp(-0.015*x(1))+20))*x(1);
y2=((280-0.2*x(1)- 2*x(2))-(100*exp(-0.02*x(2))+30))*x(2);
f=-y1-y2;
2.輸入命令:
x0=[50,70];
x=fminunc(『fun』,x0),
z=fun(x)
3.計算結果:
x=23.9025, 62.4977, z=6.4135e+003
即甲的產量為23.9025,乙的產量為62.4977,最大利潤為6413.5.
Ⅱ 線性規劃的求解方法有哪些
求解線性規劃問題的基本方法是單純形法,已有單純形法的標准軟體,可在電子計算機上求解約束條件和決策變數數達 10000個以上的線性規劃問題。為了提高解題速度,又有改進單純形法、對偶單純形法、原始對偶方法、分解演算法和各種多項式時間演算法。
Ⅲ 運籌學 圖解法求解線性規劃問題
用圖解法求解兩個變數的線性規劃問題，是一種簡單、快捷而明了的方法。求解思路，根據各約束條件繪出可行解區域，再根據目標函數確定其有效解，並求出其極值。
題1：x1=1.2；x2=0.2；min z=2*1.2+2*0.2=3
題3：x1=1.36；x2=2；max z=5*1.36+6*2=18.8
Ⅳ 高中的線性規劃問題的步驟是怎樣
[bz]蔡德錦 線性規劃 網路網盤資源
鏈接：https://pan..com/s/1znmI8mJTas01m1m03zCRfQ?pwd=1234
求解線性規劃問題的基本方法是單純形法,已有單純形法的標准軟體,可在電子計算機上求解約束條件和決策變數數達 10000個以上的線性規劃問題。為了提高解題速度,又有改進單純形法、對偶單純形法、原始對偶方法、分解演算法和各種多項式時間演算法。
Ⅳ 線性規劃整數解有簡便方法嗎
整數線性規劃的解法總結
0-1整數線性規劃是整數線性規劃的特殊情況，在實際中有著廣泛的應用。雖然變數的取值只有兩個，但此類問題的求解卻意外的困難，下面把有關的一些解法總結一下。
1.窮舉法
把所有可能的解一一代入，然後比較滿足約束的解，使目標函數最達到最優的解是最優解。這不失為一種方法，但不是一種好方法。如果問題規模大，則無法在可接受的時間內求得最優解。這也是求解整數規劃的困難所在。
2.隱枚舉法I
是窮舉法的改進，其思路是先給出一個可行解，然後代入目標函數算出函數值得到一個上界（如果求最小值）或下界（如果是求最大值）。然後一一檢驗其它的解，如果該解大於上界或小於下界，則不用檢驗可行性，因為它不可能是最優解，否則的話就要檢驗可行性，如果是可行解，則修改上界或下界，繼續檢驗其它的解，否則不用修改上界或下界，直接檢驗其它的解。這種方法通過上界或下界來控制是否需要進行可行性檢驗，提高了效率。但是，要找可行解也得花一定的時間，當約束和變數較多時，工作量異常的大，退一步來說，即使可行解比較容易找到，但其產生的上界太大，或是下界太小，則其過濾的效果也不明顯。這是這種方法的缺陷。
3.隱枚舉法II
這種方法先把問題轉化成標准型，然後按照分枝定界法的思想，盡量少的檢驗可行解來尋找最優解。這種方法比較麻煩，我在這里也描述不清楚，過幾天理解透了再來寫這一部分。
4.隱枚舉法III
這是在程冬時，張聲年在江西電力職業技術學院學報上發表的一篇文章《關於0-1型整數規劃的若干問題》中提出來的，大致的思路是：把所有可能的解都代入目標函數算出值，然後把這些目標函數值進行排序，如果是求最大值，則降序排列，如果是求最小值則升序排列。然後按這個順序一個一個的檢驗對應的解的可行性，當碰到第一個可行解時即得到最優解，因為其它的解不會優於此解了。這種方法的缺陷也是明顯的，如果變數為N個，則需求2的N次個目標函數值，然後還要進行排序，這又是項工作量很大的工作，再一個就是，如果排序結果是把可行解排在最後一個，那還是得進行2的N次方次檢驗。
4.啟發式演算法
遺傳演算法，蟻群演算法等都可歸於此類。這都是隨機演算法，說白了就是聽天由命，即使算出了最優解你也不知道是不是最優解，因為此類演算法的收斂性都只是依概率收斂的，真正在算的過程中是否已得到最優只有上帝知道。啟發式演算法是萬不得已的情況下才使用的，我們用這種方法只能保證得到的解比其它方法得到的好，但不一定就說得到了最優了。
0-1規劃的求解方法還在研究之中，也許你會發現一個有效的演算法。
Ⅵ 線性規劃問題的解題步驟
解決簡單線性規劃問題的方法是圖解法，即藉助直線（線性目標函數看作斜率確定的一族平行直線）與平面區域（可行域）有交點時，直線在y軸上的截距的最大值或最小值求解，它的步驟如下：
（1）設出未知數，確定目標函數。
（2）確定線性約束條件，並在直角坐標系中畫出對應的平面區域，即可行域。
（3）由目標函數稱為該線性規劃問題的可行解。
（2）可行解集/可行解域：滿足約束條件的可行解的全體稱為可行解集，在平面上，所有可行解的點的集合稱為可行解域。
（3）最優解：在可行解集中，使目標函數達到最優值的可行解稱為最優解。
網路-線性規劃
Ⅶ 單純形法計算線性規劃的步驟
單純形法計算線性規劃的步驟：
（1）把線性規劃問題的約束方程組表達成典範型方程組，找出基本可行解作為初始基可行解。
（2）若基本可行解不存在，即約束條件有矛盾，則問題無解。
（3）若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變數取代某一基變數，找出目標函數值更優的另一基本可行解。
（4）按步驟3進行迭代,直到對應檢驗數滿足最優性條件(這時目標函數值不能再改善)，即得到問題的最優解。
（5）若迭代過程中發現問題的目標函數值無界，則終止迭代。
用單純形法求解線性規劃問題所需的迭代次數主要取決於約束條件的個數。現在一般的線性規劃問題都是應用單純形法標准軟體在計算機上求解，對於具有10^6個決策變數和10^4個約束條件的線性規劃問題已能在計算機上解得。
Ⅷ 請問多目標線性規劃的常用求解演算法有哪些呢
多目標決策方法
多目標決策方法是從20世紀70年代中期發展起來的一種決策分析方法。決策分析是在系統規劃、設計和製造等階段為解決當前或未來可能發生的問題，在若干可選的方案中選擇和決定最佳方案的一種分析過程。在社會經濟系統的研究控制過程中我們所面臨的系統決策問題常常是多目標的，例如我們在研究生產過程的組織決策時，既要考慮生產系統的產量最大，又要使產品質量高，生產成本低等。這些目標之間相互作用和矛盾，使決策過程相當復雜使決策者常常很難輕易作出決策。這類具有多個目標的決策總是就是多目標決策。多目標決策方法現已廣泛地應用於工藝過程、工藝設計、配方配比、水資源利用、環境、人口、教育、能源、企業高速武器系統設計和評價、經濟管理等領域。
多目標決策主要有以下幾種方法：
（1）化多為少法：將多目標問題化成只有一個或二個目標的問題，然後用簡單的決策方法求解，最常用的是線性加權和法。
（2）分層序列法：將所有目標按其重要性程度依次排序，先求出第一個最重要的目標的最優解，然後在保證前一目標最優解的前提下依次求下一目標的最優解，一直求到最後一個目標為止。
（3）直接求非劣解法：先求出一組非劣解，然後按事先確定好的評價標准從中找出一個滿意的解。
（4）目標規劃法：對於每一個目標都事先給定一個期望值，然後在滿足系統一定約束條件下，找出與目標期望值最近的解。
（5）多屬性效用法：各個目標均用表示效用程度大小的效用函數表示，通過效用函數構成多目標的綜合效用函數，以此來評價各個可行方案的優劣。
（6）層次分析法：把目標體系結構予以展開，求得目標與決策方案的計量關系。
（7）重排序法：把原來的不好比較的非劣解通過其他辦法使其排出優劣次序來。
（8）多目標群決策和多目標模糊決策等。
Ⅸ 解線性規劃數學模型有哪些方法
模型建立：
從實際問題中建立數學模型一般有以下三個步驟；
1.根據影響所要達到目的的因素找到決策變數；
2.由決策變數和所在達到目的之間的函數關系確定目標函數；
3.由決策變數所受的限制條件確定決策變數所要滿足的約束條件。
線性規劃難題解法
所建立的數學模型具有以下特點：
1、每個模型都有若干個決策變數（x1，x2，x3……，xn），其中n為決策變數個數。決策變數的一組值表示一種方案，同時決策變數一般是非負的。
2、目標函數是決策變數的線性函數，根據具體問題可以是最大化或最小化，二者統稱為最優化。
3、約束條件也是決策變數的線性函數。
當我們得到的數學模型的目標函數為線性函數，約束條件為線性等式或不等式時稱此數學模型為線性規劃模型。
例：
生產安排模型：某工廠要安排生產Ⅰ、Ⅱ兩種產品，已知生產單位產品所需的設備台時及A、B兩種原材料的消耗，如表所示，表中右邊一列是每日設備能力及原材料供應的限量，該工廠生產一單位產品Ⅰ可獲利2元，生產一單位產品Ⅱ可獲利3元，問應如何安排生產，使其獲利最多？
解：
1、確定決策變數：設x1、x2分別為產品Ⅰ、Ⅱ的生產數量；
2、明確目標函數：獲利最大，即求2x1+3x2最大值；
3、所滿足的約束條件：
設備限制：x1+2x2≤8
原材料A限制：4x1≤16
原材料B限制：4x2≤12
基本要求：x1，x2≥0
用max代替最大值，s.t.（subject to 的簡寫）代替約束條件，則該模型可記為：
max z=2x1+3x2
s.t. x1+2x2≤8
4x1≤16
4x2≤12
x1，x2≥0
解法
求解線性規劃問題的基本方法是單純形法，已有單純形法的標准軟體，可在電子計算機上求解約束條件和決策變數數達 10000個以上的線性規劃問題。為了提高解題速度，又有改進單純形法、對偶單純形法、原始對偶方法、分解演算法和各種多項式時間演算法。對於只有兩個變數的簡單的線性規劃問題，也可採用圖解法求解。這種方法僅適用於只有兩個變數的線性規劃問題。它的特點是直觀而易於理解，但實用價值不大。通過圖解法求解可以理解線性規劃的一些基本概念。