線性規劃范文

導語：如何才能寫好一篇線性規劃，這就需要搜集整理更多的資料和文獻，歡迎閱讀由公務員之家整理的十篇范文，供你借鑒。

篇1

關鍵詞：基本問題；平面區域；約束條件；目標函數；雙變量；轉化化歸

線性規劃的研究內容可歸納為兩個方面：一是系統的任務已定，如何合理籌劃，精細安排，用最少的資源（人力、物力和財力）去實現這個任務；二是資源的數量已定，如何合理利用、調配，使任務的完成數最多.

“線性規劃”在知識的整合、解題思路的拓展、方法的遷移等方面都有其鮮明的特點，有著豐富的思想內涵. 挖掘題中條件，不失時機地運用“線性規劃”的思想方法解題，將使我們觀察思考問題的立意更高，視野更加開闊.

“線性規劃”問題的教學現狀

在中學教材中，稱求目標函數在線性約束條件下的最大值或最小值的問題為線性規劃問題. “線性規劃”的教學分為三個層次：

（1）二元一次不等式表示的平面區域；

（2）二元一次不等式組表示的平面區域；

（3）線性目標函數在約束條件下的最值.

只含有兩個變量的簡單線性規劃問題可用圖解法來解決.

例如：設實數x，y滿足0≤x≤1，0≤y≤2，2y-x≥1，則z=2y-x+4的最大值是__________.

上述問題可轉化為一個平面區域與一條直線在有公共點的前提下，結合z的幾何意義來求解.

具體教學過程中，學生感覺有困難的部分是作圖環節，體現在速度慢，不夠準確. 如何準確有效地作出所需圖形，應給予學生充分的指導、訓練和體驗. 學生作圖時會出現過于細致的問題，如逐步描繪坐標系刻度；又或出現過于輕率的問題，連圖形的形狀和基本特征都無法抓住.這兩個問題都使解題的速度和準確性大打折扣.

當然，線性規劃是一個比較深入的課題，教材中也介紹了更多變量的線性規劃問題，可引導學生進一步學習.

線性規劃問題的考查特點與趨勢

1. 轉化成基本線性規劃問題

常規考題考查知識與技能，但還需要學生有一定的轉化和化歸意識，命題者會在行文敘述、符號變化、算式特征等方面設置一定障礙，需要解題者對得到的信息加工出熟悉的數學模型.

例1 （江蘇2013年9題）拋物線y=x2在x=1處的切線與兩坐標軸圍成三角形區域為D（包含三角形內部和邊界）. 若點P（x，y）是區域D內的任意一點，則x+2y的取值范圍是__________.

分析：本題以拋物線的切線為背景，以文字敘述的方式提供了可行區域，題中曲線切線利用導數可得.

解決：求導得y′=2x，切線方程為y=2x-1 ，轉化為等價的基本問題：約束條件為x≥0，y≤0，y≥2x-1，目標函數z=x+2y. 作出圖形，易知z的取值范圍為-2，.

例2 設實數x，y滿足3≤xy2≤8，4≤≤9，則的最大值是__________.

分析：如何將其化歸成基礎問題，找到未知問題和基本題之間的橋梁是破解的關鍵.

解法一：整體代換，令xy2=m，=n，

那么==，轉化為等價問題：約束條件為3≤m≤8，16≤N≤81.目標函數為z=，z幾何意義為對應區域內動點與坐標原點連線的斜率，易得最大值為27.

解法二：將除法轉變為和或差，題中代數式兩邊都取以2為底的對數，令log2x=A，log2B=y. 轉化為等價問題：約束條件為log23≤A+2B≤3，2≤2A-B≤2log23，目標函數為z=3A-4B，可行區域如圖，容易求得z的最大值為3log23，那么=2z的最大值是27.

圖2

點評：解法一采用了整體換元，解法二采用了取對數化積為和、化除為差，通過轉化和化歸轉化成已經解決過的基本問題.

2. 線性規劃問題的拓展延伸

（1）線性規劃問題中目標函數的拓展

熟悉線性規劃基本題還遠遠不夠，深刻把握它的數學特點和數學思想，在實際處理問題中將未知問題轉化為基本題才更重要. 那么該類問題的基本特點是什么，常見問題是什么？只有清楚這些，我們才能在實際處理過程中及時、敏銳地轉化問題，達到解決問題的目的.

以下提供最常見的基本類型；

約束條件：實數x，y滿足y≤x，y≥0，2x-y≤2，可行區域如圖3.

圖3

目標函數（1）：z=3x+y的最大值是__________，z的幾何意義即直線y=-3x+z的縱截距；

目標函數（2）：z=的最大值是__________，z的幾何意義即可行區域內動點P（x，y）與點（-1，0）所連直線的斜率；

目標函數（3）：z=的最大值是__________，z的幾何意義即可行區域內動點P（x，y）與點（0，1）之間的距離.

與線性規劃相關的問題普遍具有一些基本特征，主要表現為已知條件是含“雙變量”的不等關系，目標任務為代數式的最值或取值范圍問題. 可解決的目標函數也不一定是線性代數式，可以為其他類型.常見的可以為乘積或比值形式、二次或根式形式，甚至可以用向量等給出的代數式. 也不一定拘泥于目標函數的最值問題，也可成為以可行區域為背景的面積、向量、概率等問題.

（2）線性規劃問題中約束條件的拓展

我們可以將它的數學思想拓展得更寬. 約束條件不一定要是線性約束條件，相應的平面區域也可以為直線、圓、曲線等構成的復合形態.

例如：實數x，y滿足x2+y2=1，則x+y的最大值是__________.

此題可行區域可認為是圓，可視為曲線圓與直線x+y=m有公共點. 由此看來，約束條件的給出有了更大的空間，線性規劃這個知識點也更容易滲透到其他數學知識點中.

例3 若a>0，b>0且+=1，則a+2b的最小值為__________.

分析：題目涉及兩個變量的等量關系，可以考慮減元處理，已由代數式整理得a=-b++1，結合基本不等式解決a+2b的最小值；也可以考慮其幾何意義，視作以b為自變量的函數，那么P（b，a）為函數圖象上的每一個點.

圖4

解決：a=-b++1，令z=a+2b，z表示此直線的縱截距.當直線與曲線相切時z最小，此時a′=-2.求導a′=-1-，所以b=，a=-++1=+，所以a+2b=+.

例4 （江蘇2012年14題）已知正數a，b，c滿足：5c-3a≤b≤4c-a，clnb≥a+clnc，則的取值范圍是__________.

分析：此題和基本問題的相似度極高，已知條件含有3個變量，而且目標函數為比值形式，有明確的幾何意義. 由代數式clnb≥a+clnc的邏輯計算知ln≥，由此得到轉化的突破口，可轉化為兩個變元.

圖5

解決：已知兩個不等式同除c得到5-3≤≤4-，ln≥.記=x，=y，

轉化為等價問題：

約束條件為x，y>0，5-3x≤y≤4-x，lny≥x？圳y≥ex，目標函數k==.

作出圖形，利用導數求出曲線y=ex過坐標原點的切線為y=ex，發現切點T（1，e）在可行區域內. 綜上，直線y=kx過C點時k最大，與曲線y=ex相切于點T時k最小. 所求取值范圍為[e，7].

圖6

點評：三變量的問題轉化為兩變量問題，該問題的解決具有一定的代表性.由已知代數式還可以考慮同除a或b進行轉化，不是每一個轉化都適合，但有些轉化又是相通和可行的，因此求解時需要一定的嘗試和觀察.

3. 線性規劃問題的知識遷移

有些數學問題并無明顯的線性規劃痕跡，卻也可以轉化成線性規劃的基本問題，比如解析幾何、函數、數列等含有多個變量的數學問題可采用線性規劃的方法來求解. 以下試題立足于課本，但高于課本，題目充分體現了命題教師的高瞻遠矚，而反過來又對高中的教學提出更高要求.

例5 （江蘇2011年14題）設集合A=（x，y）≤（x-2）2+y2≤m2，x，y∈R，B={（x，y）2m≤x+y≤2m+1，x，y∈R}，若A∩B≠，則實數m的取值范圍是__________.

分析：兩集合為點集，交集非空.思考難度超越課本，類比線性規劃，將其轉化為兩個平面區域有公共點，同時本題的計算量大.

解決：集合A對應區域為D1，集合B對應區域為D2，D2容易認識為兩平行直線確定的帶狀區域. 由區域D1非空可知m2≥，求得m≤0或m≥.

（1）m=0區域D1收縮為一點，容易判斷不滿足要求；

（2）m≠0區域D1又分為兩種情況，當m0時表示兩個同心圓確定的環形區域.不論哪種情況，要滿足題意，只需要保證圓（x-2）2+y2=m2和直線x+y=2m或直線x+y=2m+1其中之一有公共點. 圓心到兩直線距離分別為d1和d2，且d1=，d2=. 所以d1≤r=m或d2≤r=m，容易解得m∈1-，2+，綜合以上分析，實數m的取值范圍是，2+.

點評：問題描述采用了幾何語言，解決思路和線性規劃有類似之處，同時解析幾何背景很強，充分考查了直線和圓的位置關系，而且分析時利用分類討論細化，處理時又不討論集中解決，思維跳躍度很大.

例6 已知a，b為常數，a≠0，函數f（x）=a+ex. 若f（2）

分析：此題僅僅從表象上看到已知條件對變量a，b作了限制，與線性規劃知識點的相關性相當隱蔽. 該題目變量的關系相互依賴性較強，關鍵從已知條件合理的抽離出最有效約束條件.

圖7

解決：由f（2）

點評：g（x）=ax2+bx-b≥0恒成立分析較難，考慮不等式成立的必要條件攻克了這個難點，根據代數式的依存關系得到約束條件，畫出圖形，所求面積視為兩個三角形面積差.

以上可以看出這些問題和教材中很多知識點綜合，都需要學生具備良好的知識遷移能力. 包括高考在內的眾多考題都或多或少地含有線性規劃知識或思想的若干部分，這樣的考題都具備一定的難度，成為命題的熱點題型，在考試中層出不窮.

教學感悟與思考

篇2

新教材增加的簡單線性規劃內容,不僅給傳統的高中數學注入了新鮮的“血液”,而且給學生提供了學數學,用數學的實踐機會。線性規劃問題是教材中重點內容,也是高考中熱點。線性規劃問題主要考查在線性約束條件下,求可行域的面積或確定形狀;求線性目標函數的取值范圍、最值(如直線斜率,兩點間的距離,點到直線的距離、范圍等)或取最值時點的坐標。線性約束條件是由不等式(組)或方程(組)來表示的,因此線性規劃必然與不等式、方程、函數等知識聯系密切,而“在知識網絡交匯點設計問題,促進學科內知識的交融和滲透”正好是新課程高考命題的求新點和切入點。高中階段學習的線性規劃具有工具性、應用性,同時也滲透了化歸、數形結合的數學思想,為學生今后解決實際問題提供了一種重要的解題方法――數學建模法。

一、面積問題

1、(全國卷)在坐標平面上,不等式組y≥x-1y≤-3x+1所表示的平面區域的面積為_________。

解析:原不等式組去掉絕對值后轉化為兩個不等式組,畫出平面區域,根據三角形面積公式求得答案。

二、最值問題

2、(全國卷)若x,y滿足約束條件x+y≥0x-y+3≥00≤x≤3則z=2x-y的最大值為____________。

解析:z=2x-y的幾何意義是斜率為2的直線的縱截距的相反數,在坐標平面上畫出可行域,可得結果。

x,y滿足x-y-2≤0x+2y-4>02y-3≤0則的最大值是________。

3、(江西)設實數

解析:在坐標平面上畫出可行域z==的幾何意義是兩點O(0,0)A(x,y)連線的斜率,畫圖可知,在點(1, )時z最大,故所求最大值為。

4、教材第二冊(上)第99頁 第5題

解析:由問題的形式聯想到兩點間距離公式,從而利用線性規劃的思想去解決。上述幾題中的約束條件是以不等式的形式出現,有時以方程形式給出,如教材第二冊(上)第99頁 第6題

方法提煉:

①解決線性規劃問題,首先找到線性約束條件,畫出可行域;線性約束條件可能是關于x、y的不等式(組)或方程(組)。

②其次要確定目標函數(多是二元函數)理解它的幾何意義;如:截距問題,斜率 ,兩點間距離,點到直線距離。

篇3

毋庸置疑，數學規劃領域的重大突破總是始于線形規劃。提到線性規劃算法，人們最先想到的是單純形法和內點法。單純形法是實際應用中使用最普遍的一種線性規劃算法，而研究者們已證明在最壞的情況下單純形法的計算復雜度是指數級的，內點算法的計算復雜度是多項式時間的。把兩種算法相提并論，要么是這兩種算法都已經非常完備，要么都有需改進之處。顯然不屬于前者，即兩者都有需要改進之處。幾十年來，研究者通過不斷努力，在兩種算法的計算上都取得相當的進展。

1數學模型

線性規劃問題通常表示成如下兩種形式:標準型、規范型。

設jj(2…，n)是待確定的非負的決策變量；認2…，n)是與決策變量相對應的價格系數；K2…mj=l2…n)是技術系數；b(i12…，m)是右端項系數；

線性規劃是運籌學最基本、運用最廣泛的分支，是其他運籌學問題研究的基礎。在20世紀50年代

到60年代期間，運籌學領域出現許多新的分支：非線性規劃（nonlinearprogranming、商業應用（crnxmereialpplieation、大尺度方法(laresealemeh-Qd)隨機規劃（stochasticPKgiamniig)、整數規劃(ntegerprogramming)、互補轉軸理論（amplmentaiyPivotheor)多項式時間算法（polynomialtjneagatm)等。20世紀70年代末，上述分支領域都得到了極大發展，但是卻都不完善。而且數學規劃領域中存在許多Nfkhard問題，如TP問題，整數規劃問題等。這些問題的基本模型都可以寫成線性規劃形式，因此通過對線性規劃算法的進一步研究，可以進一步啟發及推動數學規劃領域內其他分支的發展。

2邊界點算法

由于單純形法與基線算法都是在可行集的邊界上取得最優值，故合稱單純形法與基線法為邊界點算法。單純形法是線性規劃使用最早也是目前實際應用中最流行和求解新型規劃問題最有效的算法之一。它實施起來相當簡單特別對中小規模問題效果顯著。單純形法最早是由Damzg于1947年夏季首先提出來的。1953年Dantzig為了改進單純形法每次迭代中積累起來的進位誤差，提出改進單純形法12。1954年美國數學家CELmH3針對對偶問題提出一種在數學上等價于用改進單純形法求解的對偶線形規劃。1974年CuretN41提出了求解一般線性規劃問題的原對偶單純形法，該算法與對偶單純形法類似，但是原對偶單純形法允許我們從一個非基礎對偶可行解開始算法求解。

1972年Klee等舉例證明了單純形算法的時間復雜性有可能是指數型。1973年，Jeoslowoi和Zdeh7又分別進一步指出常用的對偶單純形法、原一對偶單純形法等都是指數級的。

這就讓人們產生兩個疑問:①是否存在單純形法的某種改型，用它求解線性規劃問題是多項式時算法。

對于問題①，研究者們對單純形法采用了一系列改進技術如數據的預處理方法、更好的退化性處理、更好的局部價格向量計算、原一對偶最速下降邊算法的應用、更快和更穩定的矩陣分解、更好的Cach存貯的應用、以及階段1和階段2的組合算法等。但是仍未能從理論上證明線形規劃算法是多項式時間的。

近年來國內也出現了一批致力于線形規劃算法研究的學者，但是國內學者的研究主要集中在對單純形法的突破研究上，如基線法|8_'最鈍角原理1111等。

最鈍角及投影主元標算法都是針對單純形算法存在退化現象就如何選擇最優入基、離基做出的一系列研究及改進。退化現象是單純形法一直以來需解決的難題，為了克服退化問題許多學者提出了有限主元規則：擾動法、字典序規則、Blad規則1171等，其中Bind規則由于其簡單而備受關注，但是這些有限主元規則的實際應用方面并不令人滿意，甚至都不能和Dantzg規則相比。1990年，潘平奇教授在文獻[11]給出了線性規劃問題最優基的一個啟發式刻畫特征:最鈍角原理。最鈍角原理是引人反映目標梯度與約束梯度夾角大小的“主元標”乍為確定變量進基優先性的依據，潘教授的數值試驗11819表明此規則明顯優于Bland規則。然而潘的方法僅適用于只含不等式約束的線性規劃問題。為便于求解標準線性規劃問題，許多學者在其基礎上又提出了對偶主元標法。由于對偶主元標法是利用嚴格互補松弛來推導過度的，針對這一問題，又有學者提出了投影主元標法。

除此之外還有一系列最鈍角原理在非人工變量兩階段算法1M21及虧基情況下的應用研究。這些研究表明，最鈍角原理是克服單純形法退化的一種有效方法。

基線算法的概念是1996年阮國楨教授提出來的1891，這種算法是單純形法的發展，名字由來一方面是相對單純形法（基點法）提出，另一方面是使用

基線算法的主要思想是：

其中疋FTX1;eRbERm為一個m階單位矩陣。n是問題的維數，m是約束個數。把目標函數v=ff作為一個約束，看作參數。

Stef!以任意：>0所對應的變量作為進基變量，則x所在的列與單位矩陣一起構成了一個可行基B改寫八=[N馬，相應地改寫X為[xrxo’，x為非基變量，x為基變量。于是方程組AX=[vb’可以寫成Nx+Bx^Evl]’=a0+^0VStep求B1，以B1左乘，得B^1N^N+3B=B1[v]’=礦a0+B1⑷v

(2.1)

令a=B1a。，p=B-1仏則式（21河寫作

Sep對任意巨{01，…，m}，令aA^vs0

計算出當前基線表對應的可行值區間[J-”。若h

…，n-L貝IJv為最優值，或者轉SteP4

Sep旋轉基表，更新BaP旋轉基表時通常只使用有限軟上界行的負可旋主元。對于負可旋主元的選擇主要實現方法有：最大負主元算法[221，行列最好主元算法[231,保硬主元算法[24251等。

基線算法操作簡單迭代次數少，求解速度快。相對單純形法來說，單純形法最多能搜索與當前極點相鄰的n個極點，而基線算法能搜索11個二維面，這是基線算法能夠快速求解LP問題的關鍵所在。

發展至今，基線算法已有其對偶算法[271，群部分算法['目標規劃[29301,錐上算法[311等一整套的理論基礎和一系列具體的快速實現算法12632,圍繞著是否存在著多項式的基線算法，在計算復雜度方面作深入的研究將對線性規劃的發展具有十分深遠的意義。

3割平面法

線性規劃算法中割平面思想的應用主要是指橢球法。1979年Khanchiaii33!改進Yudin和Nan-

ovski等[34]為凸規劃開發的橢球法，獲得了一個求解線形規劃的多項式時間算法:橢球法。對問題②做出了明確回答。不同于單純形法從一個基礎可行解開始迭代，橢球法的特點是求解過程的每一階段都有一個以某一點為中心的橢球，迭代是從一個包含最優解的較大的橢球迭代到包含最優解的較小的橢球直至逼近最優解。

為線性規劃問題式（1.2)的規模。其中，lg]是以2為底的對數，「?]表示剛剛大于括號值的整數。則橢球法的時間復雜度為OML)

Khachiar橢!球法的主要思想是：

根據線性規劃的強對偶定理，線性規劃問題式(1.2)可以轉為下列求可行域問題：

2)從球開始，這個球大到包括式（3l1)的所有可行集X不斷構造一系列橢球，第k次迭代的橢球為Ek檢驗橢球中心&是否滿足約束條件；若滿

足則停止，否則利用割平面球的半橢球$Ek=EH

{aTA構造新的橢球更新橢球Ek+1為包含半橢球的最小體積橢球。按照這種算法下去直到橢球中心位于目標集內，橢球中心即為問題式（31)的解;否則橢球體積太小以至不含問題式（31)的可行解。

由于Khachiarn橢球法從構造包含可行域的大

的橢球出發，初始橢球體積有可能是天文數字，而且KhanCir橢球法利用K-K-T條件將原規劃問題轉

化為可行域求解問題，擴大了求解規模的同時加入了等式約束，使得可行集體積為零。雖然求解時，對等式進行攝動，可行集體積仍然很小。初始橢球體積太大，最終橢球（包含可行集的最小橢球）體積又幾乎為零，算法可能需要經過非常大的迭代步數才能收斂。而且如果對偶問題無界則原問題不可行，因此當計算結果無解時不能判斷是原問題無界呢還是原問題不可行。

不少研究者從加大每次迭代后橢球縮小比出發，提出了許多KhanCirn橢球法的改進算法:深切害J(deepeus)35-37、替代切割（surrogatecuts)381、

平行切割（paUMeus)|39-411等。最新成果是楊德莊等人提出的新的橢球法142,其優點在于引入目標束不等式及目標不等式組成，與原橢球法相比一方面大大縮小了算法求解規模，另一方面擴大了可行集的體積。而且新算法中可行集切割及目標切割交替進行，加速了橢球體積的縮小。不過令人失望的是即使最好的橢球法實施在計算上都難以與已有的單純形法相比。因此，實際中很少作為一般方法使用1431。

然而線性規劃的其他解法如單純形法、內點法都需要從一個基礎解出發，然后確定迭代方向、迭代步長，因此每次迭代都需要計算目標函數和所有約束函數。而橢球法的計算則簡單得多，理論上來說橢球法對于約束條件多的問題更有效。

4內點法

1984年KamarH441提出了一個比Khanchian法好的多項式時間算法的內點法，稱為Kamaikar法。由于該法引用了非線性規劃中的牛頓投影，因此又稱K_aka牧影法。

K_aka袪的提出在線性規劃領域具有極大的理論意義。與橢球法不同，這個新算法不僅在最壞情況下在時間復雜度上優于單純形法，在大型實際問題中也有潛力與單純形法競爭。

這一方法的提出掀起了一股內點法的研究熱潮。鑒于Kamaka?法的難讀性，一些研究學者?對Kamaika袪進行了適度的修改，使其簡便易讀。然而直接用該方法編程解題的測試表明，與目前基于單純形法的商用軟件相比，并沒有明顯的優勢1491。因此很多研究者在Kamarka法的基礎上深入研究并提出了各種修正內點法方法：仿射尺度法，對數障礙函數法，路徑跟蹤法算法等。

仿射比例調節法又分為原（Ptme)仿射比例調節法和對偶（Dua)方射比例調節法。原仿射比例調節法是從原問題出發，用一個仿射變換代替投影變換，把坐標系從一個非負象限不是單純形）映射到其本身。該法1967年由前蘇聯學者Dkii5(0提出，但他的工作直到Bame1]等人再次研究該法后才被 法，另一方面作了完全的收斂性的證明。此外，1989年AdleP等發表了從原問題的對偶問題出發的對偶仿射比例調節法。

1986年G1531等人第一次把用于非線性規劃的對數障礙函數法用于線性規劃，并證明了對數障礙函數法和Kamarka投影法是等價的。以后的研究表明kamaikaf法實際上是廣義對數障礙函數法的一個特殊情形。由于其計算方面的優越性，因此該法得到更多的研究和發展，該法也分為原對數障礙函數法和對偶對數障礙函數法。

原對偶（PrimaDua)各徑跟蹤法，實際上是原對偶障礙函數法，是MeidG19M541年提出的。他將包含對數障礙函數問題的障礙參數的唯一的最優解所構成的曲線稱為一條路徑或中心軌跡，當障礙參數趨近零時，中心軌跡的極限即為原問題的最優解。Kojma55'等最早（1987)提出收斂的算法，之后其他研究者對算法作了進一步的改進。為了找到起始可行解算法都要引進人工變量和附加約束條件，分別以適當的大數作系數和右端值，但算法對這些大數的選擇很敏感易導致算法中數值的不穩定性。因此LustiTi等考慮使這些大數同時變為無窮大時坐標增量的“極限可行方向”該方向只改變了求最優解的方向，并不改變確定軌跡中心的方向，因而問題解法成為不可行問題原對偶牛頓法，其優點是對初始解不必引入人工變量。該法也可用類似形式應用于不可行原問題或對偶問題的方法中[57581。該法還便于處理有界變量問題。然而這個方法的計算復雜性尚未確知，沒有一般收斂的算法的證明。此外，在方法的改進方面，出現了全面收斂不可行內點算法和預計改正法。

勢函數下降法有基于Gezaga等人提出的原勢函數下降法和Ye等人提出的原對偶勢函數下降法,計算復雜性都達到較好指標。前者算法包含了兩個搜索方向，且所有仿射變換方法都采用了最速下降方向。這方面的改進還有Kajmm等的原對偶勢函數下降法等。由于上述勢函數下降法的各種算法是基于一系列嚴格的可行解上，方法都要求說是難以做到的。顯然直接采用不可行內點算法是最好的解決辦法，因而Y，eTOdd和Misunol994年提

出了構建“齊次自對偶問題”的方法，該齊次自對偶問題的解則可以用Kajjna等的原對偶勢函數下降法來解出。

在20世紀90年代內點法理論發展成一個相當成熟的原理。這一時期，對內點法理論的一個主要貢獻來自YENesterov和八SNmirovski兩位數學家[69。他們創建的Self-Cocrdant函數理論，使基于對數障礙函數的線性規劃內點法很容易推廣到更為復雜的優化問題上，如非線性凸規劃、非線性互補、變分不等式、半定優化以及二階錐優化等。目前自協調函數形式主要有：對數函數和商函數形式。

今天，內點法的研究熱點主要轉向于半定優化、半定互補、非凸優化及組合優化問題上。

5自協調函數理論

自協調函數可謂是線性規劃算法研究的一個重大突破，也是我們后續研究的重點。自協調函數理論又名自協調障礙函數理論，為解線性和凸優化問題提供了多項式時間內點算法。根據自協調障礙函數的參數就可以分析內點算法的復雜性。

自協調函數定義：

一個凸函數fR-R對定義域內的任意x滿足Lf"(x)<2f(x3/2,我們就稱它為自協調函數。如果函數(Rn-R對于任意直線滿足自協調條件，我們稱函數§(9是自協調函數。

自協調函數理論的關鍵是算法的復雜性由自協調函數的兩個參數決定，只要這兩個參數可以推導出，則可求得算法的復雜性。

然而目前常用的自協調函數形式只有對數障礙函數形式:負對數函數：f=一Igx及負商函數加上負對數函數：f=xgx^lgP]。

最近CReas等m指出有些內核函數盡管沒有全局自協調性，卻能在局部自協調。而且，CR?s

部值 也可以較好的求得算法的復雜性。基于CRQ0S的思想，金正靜等1711提出了一個局部自協調函數，其形式如下

自協調函數理論的提出，為我們分析算法復雜性帶來了極大的便利。然而以上的自協調函數形式都要求核函數為正，這為我們的研究帶來了極大的限制。那么自協調函數是否存在不要求核函數為正的形式為我們研究自協調函數提供了方向。

6結束語

除了邊界點算法，橢球法，內點法，線性規劃還有有效集法等經典算法、楊德莊教授的新算法及遺傳算法，神經網絡等求解線性規劃的智能計算方法，有興趣者可參看有關文獻。

篇4

2.了解線性規劃問題的圖象法，并能用線性規劃的方法解決一些簡單的實際問題。

教學重點

1.二元一次不等式(組)表示的平面區域;

2.應用線性規劃的方法解決一些簡單的實際問題。

教學難點

線性規劃在實際問題的應用

高考展望

1.線性規劃是教材的新增內容，高考中對這方面的知識涉及的還比較少，但今后將會成為新高考的熱點之一;

2.在高考中一般不會單獨出現，往往都是隱含在其他數學內容的問題之中，就是說常結合其他數學內容考查，往往都是容易題

知識整合

1.二元一次不等式(組)表示平面區域：一般地，二元一次不等式在平面直角坐標系中表示直線某一側所有點組成的__________。我們把直線畫成虛線以表示區域_________邊界直線。當我們在坐標系中畫不等式所表示的平面區域時,此區域應___________邊界直線，則把邊界直線畫成____________.

2.由于對在直線同一側的所有點，把它的坐標代入，所得到實數的符號都__________，所以只需在此直線的某一側取一個特殊點，從的_________即可判斷>0表示直線哪一側的平面區域

3.二元一次不等式組是一組對變量x,y的__________，這組約束條件都是關于x,y的一次不等式，所以又稱為_____________;

4.(a,b是實常數)是欲達到最大值或_________所涉及的變量x,y的解析式，叫做______________。由于又是x,y的一次解析式，所以又叫做_________;

5.求線性目標函數在_______下的最大值或____________的問題，統稱為_________問題。滿足線性約束條件的解叫做_________，由所有可行解組成的集合叫做_________。分別使目標函數取得____________和最小值的可行解叫做這個問題的___________.

典型例題

例1.(課本題)畫出下列不等式(組)表示的平面區域，

1)2)3)

4)5)6)

例2.

1)畫出表示的區域，并求所有的正整數解

2)畫出以A(3，-1)、B(-1，1)、C(1，3)為頂點的的區域(包括各邊)，寫出該區域所表示的二元一次不等式組，并求以該區域為可行域的目標函數的最大值和最小值。

例3.1)已知，求的取值范圍

2)已知函數，滿足求的取值范圍

例4(04蘇19)制定投資計劃時，不僅要考慮可能獲得的盈利，而且要考慮可能出現的虧損。某投資人打算投資甲、乙兩個項目，根據預測，甲、乙項目可能的最大盈利率分別為100%和50%，可能的最大虧損率為30%和10%，投資人計劃投資金額不超過10萬元，要求確保可能的資金虧損不超過1.8萬元，問投資人對甲、乙兩個項目各投資打算多少萬元，才能使可能的盈利最大?

例5.某人承攬一項業務，需做文字標牌4個，繪畫標牌6個，現有兩種規格原料，甲種規格每張3m，可做文字標牌1個，繪畫標牌2個;乙種規格每張2m，可做文字標牌2個，繪畫標牌1個,求兩種規格的原料各用多少張，才能使總的用料面積最小?

例6.某人上午時乘摩托艇以勻速V海里/小時從A港出發到相距50海里的B港駛去，然后乘汽車以勻速W千米/小時自B港向相距300km的C市駛去，應該在同一天下午4點到9點到達C市。設汽車、摩托艇所需時間分別為小時，如果已知所要經費P=(元)，那么V、W分別是多少時走得最經濟?此時需花費多少元?

鞏固練習

1.將目標函數看作直線方程,z為參數時，z的意義是()

A.該直線的縱截距B。該直線縱截距的3倍

C.該直線的橫截距的相反數D。該直線縱截距的

2。變量滿足條件則使的值最小的是()

A.(B。(3，6)C。(9，2)D。(6，4)

3。設式中變量和滿足條件則的最小值為()

A.1B。-1C。3D。-3

4。(05浙7)設集合A={是三角形的三邊長}，則A所表示的平面區域(不含邊界的陰影部分)是()

5。在坐標平面上，不等式組所表示的平面區域的面積為()

A。B。C。D。2

6.(06全國ⅰ14)設，式中變量和滿足下列條件則的最大值為__________________;

篇5

1.常規問題

例1 （2012?山東）設變量x，y滿足約束條件x+2y≥2，

2x+y≤4，

4x-y≥-1，則目標函數z=3x-y的取值范圍是（ ）

A.[-32，6] B.[-32，-1]

C.[-1，6] D.[-6，32]

解析 作出不等式組表示的可行域，如圖1陰影部分所示，作直線3x-y=0，并向上、下平移，由圖可得，當直線過點A時，z=3x-y取最大值；當直線過點B時，z=3x-y取最小值.由x+2y=2，

2x+y=4，解得A（2，0）；由2x+y=4，

4x-y=-1，解得B（12，3）.

所以zmax=3×2-0=6，zmin=3×12-3=-32.所以z=3x-y的取值范圍是[-32，6].

2.非線性目標函數問題

例2 （2011?廣東）已知平面直角坐標系xOy上的區域D由不等式組0≤x≤2，

y≤2，

x≤2y給定.若M（x，y）為D上的動點，點A的坐標為（2，1）則z=OM?OA的最大值為（ ）.

A.42 B.32 C.4 D.3

解析 如圖2作出區域D，目標函數z=2x+y過點B（2，2）時取最大值，故z的最大值為2×2+2=4，

故選C.

例3 （2012?北京）設不等式組0≤x≤2，

0≤y≤2表示的平面區域為D，在區域D內隨機取一個點，則此點到坐標原點的距離大于2的概率是（ ）.

A.π4 B.π-22 C.π6 D. 4-π4

解析 如圖3所示，正方形OABC及其內部是不等式組所表示的區域D，且區域D的面積為4，而陰影部分表示的是區域D內到坐標原點的距離大于2的區域.因此滿足條件的概率是4-π4.

3.含參的線性規劃問題

例4 （2011?湖南）設m>1，在約束條件y≥x，

y≤mx，

x+y≤1下，目標函數z=x+my的最大值小于2，則m的取值范圍為.

解析 目標函數z=x+my可變為y=-

1mx+zm.

因為m>1，所以-1

如圖4，當目標函數經過點P（1m+1，mm+1）時取最大值，

所以1m+1+mm+11，得1

4.平面區域問題

例5 （2013安徽）在平面直角坐標系中，O是坐標原點，兩定點A，B滿足

|OA|=|OB|=OA?OB=2，則點集{P|OP=λOA+μOB，|λ|+|μ|≤1，λ，μ∈R}所表示的區域的面積是（ ）.

A.22 B.23 C.42 D.43

解析 若A，B，C三點共線，P是線外一點，則PA=λPB+μPC，其中λ+μ=1.

在本題中，OA?OB=|OA||OB|cosθ=4cosθ=2θ=π3.

建立直角坐標系，設A（2，0），B（1，3）.則當λ≥0，μ≥0，λ+μ≤1時，P在三角形OAB內（含邊界）.

根據對稱性，所求區域的面積S=4×三角形OAB的面積=43.

A.2a B.12a C.4a D.4a

解析 如果用常規方法，顯然比較麻煩，有點“小題大做”了.由于直線的位置沒有特殊要求，因此可選取一個特殊位置，在此位置處求1p+1q的值即可.

篇6

關鍵詞：線性規劃思想；解題；應用

中圖分類號：G427 文獻標識碼：A文章編號：1992-7711（2012）03-076-2

線性規劃問題以二元一次不等式所表示的平面區域內容為基礎，它將代數與幾何，數學與實際巧妙地聯系起來，線性規劃實際上就是以數學知識為工具，來研究在一定的人、財、物、時、空等資源條件下，如何精打細算巧妙安排以最少的資源來取得最大的經濟效益。然而中學所學的線性規劃只是規劃論中極小的一部分，但這部分內容體現了數學的工具性、應用性，同時滲透了化歸、數形結合的思想，并且為學生今后解決實際問題提供了一種重要的解題方法――數學模型法，所以掌握好這部分內容非常重要。

一、線性規劃的內涵

線性規劃是數學規劃的一部分，它研究目標函數在約束條件下的最大值和最小值問題，即要尋找既滿足約束條件又使得目標函數達到最優的解，要一下子處理可能比較困難，于是提出“可行解”這一概念，將求解線性規劃的問題分解為兩步，第一步先求“可行解”，第二步再求“最優解”。從而分散了難點，找到了解決問題的方法。雖然中學所學的線性規劃只是規劃論中極小一部分，但這部分內容體現了數學的工具性、應用性，同時滲透了化歸、數形結合的思想，能夠將實際問題轉化為數學問題，抽象解決一些簡單的線性規劃應用問題的基本思路和主要方法。

二、線性規劃思想解題

利用線性規劃的思想解題主要是依據給定的條件，把整個題目的有關約束條件和所求目標函數用數學關系和邏輯關系表示出來，運用化規，數形結合等思想，主要通過圖解法的方法求解，得出最優解和最優目標函數值。下面舉例說明幾種用的線性規劃的方法在實際解題中的應用。

(一)向量問題轉化為線性規劃問題

向量是平面幾何的基礎，線性規劃作為連接點巧妙地將幾何問題與代數問題聯結起來。

例1 已知在平面直角坐標系中，O(0,0)，M(1,12)，N(0,1)，Q(2,3)，動點P(x,y)滿足不等式0≤OP•OM≤1，0≤OP•ON≤1，則W=OP•OQ的最大值是多少？

分析 因為O(0,0)，M(1,12)，N(0,1)，Q(2,3)，所以 0≤OP•OM≤1,0≤OP•ON≤1，0≤x+12y 圖1

≤1,0≤y≤1，W=OP•OQ=2x+3y。

本例轉化為在線性的約束條件

x+12y≤1,0≤y≤1,x+12y≥0

下，求線性目標函數W=OP•OQ=2x+3y的最大值題。可作出如圖的可行域，顯然在點T的坐標是最優解。

由

x+12y=1,y=1

得

T(12,1),

所以

Wmax=2×12+3×1=4。

注 本題將平面向量與線性規劃巧妙地結合起來，真正體現了在知識交匯點處命題的高考指導思想。解決這類問題的關鍵是將已知的不等式組準確地轉化為二元一次不等式組并準確畫圖，然后求最值。

(二)三角問題轉化為線性規劃問題

求解三角形個數問題，常規解法是根據三角形三邊關系，利用分類計數原理求解，而用線性規劃方法求解，則別具一格［2］。

例2 三邊長均為整數，且最大邊長為11的三角形個數為多少？ 圖2

解 設三角形另兩邊長分別x,y(x,y∈N*),

根據題意得

x+y>11,x≤11,y≤11,x≥y,x,y∈N*

轉化為在此約束條件下求整數點的問題，

如圖所示可得 1+3+5+7+9+11=36，

故三角形的個數為36個。

注 本題巧妙地將線性規劃問題運用到三角形的問題中，體現了線性規劃廣泛運用的特點。求解這類題目關鍵是利用三角形兩邊之和大于第三邊的關系，轉換為標準的線性規劃問題，其中，在求整數可行解時，也就是可行域中橫坐標和縱坐標都是整數的點，可先畫出滿足線性規劃約束條件的平面區域，然后再找整數點。

(三)與函數或不等式結合,求取值范圍問題

函數與不等式是高中數學的基本知識點，求取值范圍也是常見地類型，結合函數或不等式的性質，運用數形結合的思想把問題轉化為線性規劃的問題解決，即形象又直觀［3］。

例3 已知f(x)=ax2+bx，且1≤f(－1)≤2，2≤f(1)≤4，求f(－2)的取值范圍。

分析 對這個問題，可以用f(－1)，f(1)表示f(－2)，再由f(－1)，f(1)的范圍，結合不等式的性質求出f(－2)的取值范圍。我們可以轉化為線性規劃問題求解。 圖3

解 1≤f(－1)≤2,2≤f(1)≤4,得1≤a－b≤2,2≤a+b≤4。(1)

目標是求f(-2)=4a－2b的取值范圍。

作出線性約束條件（1）下的可行域四邊形ABCD，

如圖3A(2,0),B(3,1),C(52,32),D(32,12)不難得到，

當直線4a－2b= f(-2)經過點B和D 時，

f(－2)分別取得最大值最小值10和5。

所以 f(-2)∈［5,10］。

注 對于這個問題，很多學生常犯如下錯誤:由題設

1≤a－b≤2,2≤a+b≤4,

得

32≤a≤3,0≤b≤32。 (2)

又因f(-2)=4a－2b，所以3≤f(－2)≤12。

線性規劃中的可行域可以直觀形象地幫助我們可看到此種解法的錯誤之處。作出（2）式表示的可行域如圖4，可清楚地看到圖3中的可行域是圖4的一部分，即由（1）到（2）后范圍擴大了。

(四)線性規劃在函數問題中的應用

對于某些與函數有關的問題，若善于利用已知條件構造線性約束條件，將問題換為線性規劃問題求解，有時能起到事半功倍的效果。

例4 已知函數f(x)=x3+ax2+bx+c在區間［－1,2］上是減函數，求a+b的最大值。

分析 根據線性規劃思想，可視t=a+b為目標函數，再由已知條件可知a,b的約束條件，即由f(x)=x3+ax2+bx+c在區間［－1,2］上是減函數，得出目標函數的可行域。這樣，求a+b的最大值就轉化為在可行域中求目標函數的最大值。

圖4

解 由題意知f′(x)=3x2+2ax+b,在［－1,2］恒有f′(x)≤0，

則

f′(－1)≤0,f′(2)≤0

即

3－2a+b≤0,12+4a+b≤0。

令t=a+b，其中a,b滿足上述約束條件，作出這個約束條件下的可行域,如圖5所示，當直線t=a+b 過點 A(－32,－6)時，tmax=－152。

容易驗證:a=－32,b=－6 時，f(x)在區間［－1,2］上是減函數，所以a+b的最大值為－152。

注 本例題由函數的單調性，運用導數列出不等式即得出目標函數的可行域，將本例轉化為求解目標函數的最大值，若直接運用函數的性質求解，顯得繁瑣且容易將范圍擴大,因此，運用線性規劃思想求解此類最值問題時既簡捷又方便。

(五)與解析幾何結合，求參數的范圍問題

線性規劃體現的是數形結合的思想，理解了這一點，則賦予了線性規劃知識更廣泛、更深刻的意義。在線性約束條件下，凡結論具有一定的幾何意義的問題均可類比解決。

例5 已知線段AB的端點為A(1,3)、B(5,2)，若動直線l:x+ty=－1t與線段AB相交，求參數t的取值范圍。

圖5

分析 直線l可化為x+ty+1t=0。因線段AB與直線l有公共點。

由線性規劃知識得

(1+3t+1t)(5+2t+1t)≤0,

而 t2>0，所以化為

(3t2+t+1)(2t2+5t+1)≤0。

又3t2+t+1=3(t+16)2+1112>0,

所以再化為

2t2+5t+1≤0,

解得

－5－174≤t≤－5+174。

注1 直角坐標系內有兩點P1(x1,y1),P2(x2,y2)直線l:Ax+By+C=0，直線l和線段P1P2有公共點的充要條件是(Ax1+By1+C)(Ax2+By2+C)≤0。

注2 按傳統解法是從直線斜率出發，由動直線引出定點，通過對直線系探討等決與線段有公共點的問題。而本題難以確定動直線所過定點，傳統方法無法用上。現在利用線性規劃知識構建不等式，就可以使問題得到圓滿解決。

(六)概率問題轉化為線性規劃問題

概率是中學數學教材中新增內容，它在理論與實際生活中都有重要意義，在求解某些概率問題的過程中，若思路受阻，或很難找到突破口，可以借助坐標和一系列的等價變換，將一次試驗可能結果的全體用某一圖形的面積G來代替，然后將所求事件包含的結果數以線性約束條件的形式展現出來，若其相應的可行域的面積為g，則所求事件的概率為gG。

例6 兩人相約9點到10點在同一地點會面，早到的人要等另一個人20分鐘才能離開，試求兩人會面的概率。

分析 以x,y分別代表兩人到會面地點的時刻，則兩人會面的充要條件為

|x－y|≤20,x,y∈［0,60］,即x－y≤20,y－x≤20,0≤x≤60,0≤y≤60

在直角坐標系中畫出x,y的可行域（如圖6的陰影部分）。顯然兩人可能到達的時間為圖中正方形內（含邊界）的點，陰影部分表示能會面的點，從而可利用其面積之比得概率為:P=602－12×40×40×2602=59。

注 這是一道幾何概率問題，用線性規劃的思想可直觀簡捷的求解這類問題。本例題中有明確的不等式關系，可將其概括成不等式組，畫可行域，用線性規劃的思想解題。

線性規劃是數學規劃中理論較完整，方法較成熟，應用廣泛的一個分支，它能解決許多方面的實際問題。它是直線方程的一個簡單應用，也是數形結合數學思想的很好體現。文章是在了解線性規劃的意義，以及線性約束、線性目標函數、可行解、可行域、最優解等概念，并且熟練掌握線性規劃的圖解法的基礎上，運用數形結合的思想解決有關向量、函數、不等式、解析幾何等方面的問題，使解決這些問題變得更加簡便，同時也有助于數學思維能力的提高。

［參考文獻］

［1］教育部.普通高中數學課程標準(實驗).人民教育出版社,2003.

［2］吳成強.線性目標函數最優解的探求.中學生理科月刊,2003（5）.

篇7

[關鍵詞]非線性規劃 懲罰函數法 磨光法

一、引言

懲罰函數法是求解約束型非線性規劃的有效算法之一。但對具有不等式約束的非線性規劃問題,常用的簡單罰函數法存在缺陷。由于一般的簡單罰函數在可行域邊界點上不可微,因此給求解無約束優化問題的編程計算帶來不方便。近年來,關于處理不可微優化問題的算法很多,但大多數算法是引入次梯度的迭代算法,理論推導復雜,局限性比較大,編程計算仍然不便。受文獻[1-2]利用磨光參數處理不可微點技術的啟發,提出求解約束型非線性規劃的磨光懲罰函數法。文獻[1]利用磨光參數獲得了非光滑最優控制的差分解,文獻求解了具有互補約束條件的優化問題,同樣引進了磨光參數將不可微點近似處理為可微函數,逐步逼近真解。磨光懲罰函數法的基本思想是,在簡單罰函數法的基礎上利用磨光參數將非光滑罰函數近似為光滑函數,進一步采用可微函數的常規算法獲得包含磨光參數的近似解,通過逐步細磨獲得最優解。該方法避開了罰函數的不可微性,使編程求解更加初等化,簡單化。

二、簡單罰函數法和磨光參數

考慮具有不等式約束的非線性規劃問題:

Min f(x) (1)

(2)

其中f(x),gi(x)是Rn上的連續的可微函數。實現這類約束問題求解的途徑是由目標函數和約束函數組成輔助函數,把原來的約束問題轉換成為極小化輔助函數的無約束問題。

定義輔助函數為下列形式:

是滿足下列條件的連續函數

其中,的典型取法為,其中β≥1均為給定的常數,通常取為2。構造增廣目標函數,得到外點罰函數算法[4-5](SUMT)。

算法1:(SUMT)

三、磨光罰函數法及其收斂性

值得說明的是,算法2:(S- SUMT)得到的解對應的目標值與算法1(SUMT)得到的解對應的目標值相同,但最優解不一定相同。然而,如果問題(1)(2)的解唯一,則兩算法得到的最優解相同。

四、數值例子

考慮約束型非線性規劃問題

五、結束語

由算例可以看出隨著磨光參數的減小,在同樣的懲罰因子下,其解逐步趨近于精確解。因此本文提出的磨光罰函數法(S- SUMT)是可執行的,有效的。更重要的是該算法避開了簡單罰函數不可微的缺陷,使得原問題連續可微,有利于編程實現。

參考文獻:

[1]Xiaojun Chen. Finite difference smoothing solutions of nonsmooth constrained optimal control problem[J].Numerical Functional Analysis and Optimization, 2005,26(1):49-68.

[2]Xinmin Hu, Daniel Ralph. Convergence of a penalty method for mathematical programming with complementarity constraints[J].Journal of Optimization and application,2004,123(2):365-390.

[3]Scholtes,S. Convergence Properties of a Regularization scheme for Mathematical Programs with Complementarity Constraints[J].SIAM Journal on Optimization,2001,11(4):918-936.

篇8

關鍵詞：線性規劃 ；移動Agent

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2011)28-6967-02

Based on Mobile Agent of Linear Programming model

HE Bin

(Computer Science Dept. of Ningxia University, Yinchuan 750021, China)

Abstract: This article discusses a mobile agent based on linear programming solving solutions to improve the calculation efficiency, has the nice practical significance.

Key words: linear programming; mobile agent

1 緒論

整數線性規劃問題的求解已廣泛的應用到工程實踐中。傳統的求解整數線性規劃方法有：枚舉法、割平面法以及分枝定界法。其中分枝定界法是最為常用的方法[1]。

分枝定界法是20世紀60年代初期由Land Doid 和Dakin等人提出的，是一種系統化的解法，以一般線性規劃的單純形法解得最佳解，然后將非整數值的解分割成最接近的兩個整數，分列條件，加入原問題中，如此分枝成兩個子問題分別求解，這樣便可求得目標函數值的上界或下界，從其中尋得可行解。 可見本算法能較快的求得最佳解，且平均速度快，但要存儲很多葉子結點的限界和對應的耗費矩陣，花費很多內存空間，計算效率較低。本文探討一種基于演化agent的解決方案。

2 基于移動Agent的整數線性規劃

移動agent是具有移動性的智能agent，能夠自行決定在網絡的各個節點之間移動，代表其他實體（人或其他agent）進行工作的一種軟件實體。移動Agent技術是分布式技術與Agent技術相結合的產物，它除了具有agent最基本的特性：自主性、反應性、能動性、通信性以外，還具有移動性[2]。這些特有的屬性和技術優勢使其在諸多領域得到了科學的應用，特別適合于解決傳統方法中代價過于昂貴，或者解決不了的問題。

2.1 agent模型

定義一個agent，它是具有目標、動作、通信等行為功能的復合體，用符合T表示。agent的行為描述如下：

1）復制

一個agent T可以復制成兩個子agent T1、T2，我們稱T為父agent。它的兩個子agent與其具有同樣的目標，但所處的問題環境有所改變。

2）動作

Agent會根據其所處的問題環境不停地計算其目標，直到成功或者到達中止條件。

3）通信

設環境E中是agent T的計算環境，那么agent T會在這個環境中進行計算，直到達到其目標，如果目標不能達到，agent T會復制成agent T1、T2來繼續計算其目標，此時環境E也會被分成E1 、E2（E的兩個子環境），它們就分別是T1、T2的計算環境。

T1、T2分別在E1、E2中計算其目標，如果它們的計算達到目標，則將計算結果發送給agent T，否則將會繼續復制，繼續計算下去。

2.2 求解算法

這個算法的基本思想是：將松弛問題Q作為agent T的目標和計算環境，T首先按單純形法來求解，如果計算的結果有最佳整數值，則問題得到求解。否則，T將復制成兩個子agent T1、T2分別對應與兩個子問題B1、B2繼續求解，如此下去，以獲得問題的最優整數解。算法可描述如下：

1）首先把整數線性規劃問題中得目標函數以及約束條件作為agent T的目標和環境賦給它，并且定義變量p（p首先不賦予值）；

2）agent T首先求解松弛問題，如果松弛問題的最優解全為整數，那么把這些最優解賦值給p，轉去執行（6），如果松弛問題沒有可行解，就直接轉去執行6），否則將執行下一步；

3）若在求解過程中某個變量xi的解為分數值kj，那么就分別求得小于 kj下的最大整數[kj]和大于的最小整數[kj]+1，agent T 將復制成兩個子agent T1、T2。這兩個子agent的計算目標與agent T相同，但其環境分別為原來T的計算環境加上約束條件xi=[kj]+1。

4）agent T1、T2 分別在其所處的環境里計算它們的目標，如果最優整數解已求出，則若p沒有值，那么將最優整數解賦值給p，否則，p min（p，最優值）；

5）當T1、T2 中有非整數可行解者Tj 時，如果p沒有值或所得的非整數可行解小于p，那么將Tj 的解賦值給T，轉到（3）繼續執行；

6）如果p已有值，則輸出p，否則就輸出此整數線性規劃問題沒有可行解。

2.3 模型的實現

可選用日本IBM公司開發的Aglet平臺，該平臺是目前最為成功和全面的移動平臺[3]。Aglet系統可以根據需要創建agent T ；復制agent T1、T2，將它們分派到各自的環境中執行；也能執行暫停、清除。

2.4 算法的時間復雜度

在微機上，采用一般的單純形法來求解整數線性規劃問題，其時間復雜度為O (n)；而用本文的模型進行求解，它的時間復雜度為O (log n)，可見實現的時間復雜度較低。

3 結束語

通過編程實現，本文探討的模型取得了很好的效果。Agent可以同時復制，故求解過程具有并行性；并且程序實現的時間復雜度較低，求解過程基于目標驅動，提高了計算效率。

參考文獻：

[1] 張干宗.線性規劃[M].武漢:武漢大學出版社,2007.

篇9

關鍵詞：非線性規劃；企業營銷；Lingo

中圖分類號：F274 文獻標志碼：A 文章編號：1673-291X（2016）04-0059-02

一、非線性規劃數學模型

對實際非線性規劃問題做定量分析，首先要選定適當的目標變量和決策變量，并建立起目標變量與決策變量之間的函數關系，即目標函數，并建立約束條件。非線性規劃問題的一般數學模型可表述為求未知量x1，x2...，xn，使滿足約束條件：

gi（x1，...，xn）≥0，i=1，...，m

hj（x1，...，xn）=0，j=1，...，p

并使目標函數f（x1，...，xn）達到最小值（或最大值）。其中gi（x1，...，xn）和hj（x1，...，xn）均是定義在n維向量空間Rn上的某子集D（定義域）上的實值函數，且f（x1，...，xn）、gi（x1，...，xn）、hj（x1，...，xn）中至少有一個是非線性函數。記x=（x1，...，xn），則上述模型可以簡記為：

minf（x）或maxf（x）

s.t.gi（x）≥0，i=1，...，mhj（x）=0，j=1，...，p

定義域D中滿足約束條件的點稱為問題的可行解，全體可行解所組成的集合稱為問題的可行集。對于一個可行解x*，如果存在x*的一個領域，使目標函數在x*處的函數值f（x*）不大于（或不小于）該領域中任何其他可行解處的函數值，則稱x*為問題的局部最優解，如果f（x*）不大于（或不小于）一切可行解處的目標函數值，則稱x*為該模型的整體最優解。

二、應用舉例

（一）案例介紹

宏宇電器公司計劃生產三類10種小家電，其中包括：熱水壺（1.5升、1.8升、2升）、豆漿機（0.9升、1.1升、1.3升）、電飯煲（2升、2.5升、3升、3.5升）。三類小家電的年最大生產能力分別為：熱水壺5萬個、豆漿機6.5萬個、電飯煲6.2萬個。制定使公司利潤最大的的生產、銷售方案（數據來源：2010年東北三省數學建模聯賽A題）。

（二）案例求解

公司的收入和支出來自計劃內銷售和計劃外銷售兩部分，公司所承擔的計劃內成本應該根據計劃內的產品數量占總產品數量的比值確定，即：

公司承擔的生產成本=總成本×

公司利潤的表達式：

公司總利潤=已簽約合同的銷售額+意向簽約合同的銷售額+計劃外營銷部上繳利潤-計劃內成本-經費

第1種小家電的銷售額與訂購量的函數關系為：

f1（x）=-0.26713x2+11.418x+1.3873

同理可以得到，第2至10種家電銷售額與其訂購量的函數關系。記fi（x）為第i種小家電的銷售額，i=1，2，...，10，x代表訂購量。

同理，記gi（y）為計劃外銷售第i種小家電營銷部向企業繳納的利潤，i=1，2，...，10，y代表銷售量；記mi（z）為第種小家電的經費，i=1，2，...，10，z代表產量；記ni（y）為第種小家電的經費，i=1，2，...，10，y代表銷售量；記ni（y）為第i種小家電的經費，i=1，2，...，10，y代表產量。

1.每個產品的訂購量不能超過客戶的最大意向簽約量。xij≤Mij，其中xij代表第j個顧客對第i種小家電的訂購量，i=1，2，...，10，j=1，2，3，4，5，Mij代表第j個客戶對第i種產品的最大簽約量。

2.計劃外產品的訂購量不能超過其最大可能訂購量。xi6≤Ni6，其中xi6代表計劃外的第i種小家電的訂購量，i=1，2，...，10，Ni6代表計劃外第i種產品的最大可能訂購量。

3.所有產品的訂購量均不能為負數。xij≥0，i=1，2，...，10，j=1，2，3，4，5，6。

4.各類產品的訂購量不能與超過其最大生產能力。∑3 i=1∑6 j=1xij≤12，∑6 i=4∑6 j=1xij≤20，∑3 i=7∑6 j=1xij≤19。

運用Lingo軟件得到最大值t=697.33萬元，目標函數取得最大值時的各變量取值。為使公司利潤達到最大時的生產方案為：1至10種小家電分別對應的生產數量（千件）為：11.59、24.54、13.87、14、29、20、12、24.3、14.3、8.4。

篇10

回答 含參線性規劃問題一般可分為兩類，一類是約束條件含參，另一類是目標函數含參. 這兩類問題的解題原理是相同的，關鍵是理解參數的本質，并認清參數變化對直線位置產生的影響.下面，我們就以提問中的問題為例進行分析.

我們首先想到作出直線x+3y-3=0，2x-y-3=0與x-my+1=0，確定可行域.但怎么確定含參直線x-my+1=0的具置呢？令y=0，解得x=-1，可知直線x-my+1=0必過定點（-1，0）.當m≠0時，直線x-my+1=0的斜率k=≠0；當m=0時，直線x-my+1=0的斜率不存在，故直線x-my+1=0可看作繞定點（-1，0）旋轉且不與x軸重合的動直線，參數m就是控制直線x-my+1=0的位置的關鍵要素.當參數m變化時，不等式組x+3y-3≥0，2x-y-3≤0，x-my+1≥0表示的可行域也會隨之變化.

在解題時，我們不妨以靜制動，先設m為一個任意的常數，作出一個確定的可行域，然后以動馭靜，讓含參直線旋轉起來，在旋轉中尋找滿足“x+y的最大值為9”的參數m.

如圖1所示，在直角坐標系中作出直線l1：x+3y-3=0，l2：2x-y-3=0，l3：x-my+1=0的圖象.

注意：過點（-1，0）作直線l3：x-my+1=0的圖象（以虛線表示）時，可以對參數m取任一常數.

記不等式組x+3y-3≥0，2x-y-3≤0，x-my+1≥0所表示的平面區域為Ⅰ（如圖1所示）. 把條件“x+y的最大值為9”等價轉化為不等式x+y≤9，作直線l4：x+y=9的圖象，記不等式x+y≤9所表示的平面區域為Ⅱ.判斷平面區域Ⅰ與平面區域Ⅱ的位置關系.由題意可知x+y的最大值為9，所以平面區域Ⅰ應恒在平面區域Ⅱ的下方.

在圖1中，平面區域Ⅰ不恒在平面區域Ⅱ的下方. 將直線l3：x-my+1=0繞定點（-1，0）沿逆時針方向旋轉，平面區域Ⅰ不恒在平面區域Ⅱ的下方，不滿足題意.如圖2所示，將直線l3繞定點（-1，0）沿順時針方向旋轉，使平面區域Ⅰ恒在平面區域Ⅱ的下方，但此時x+y的最大值小于9，所以直線l3的位置也不滿足題意.

由此可見，要使x+y=9成立，區域Ⅰ和區域Ⅱ的交點必須在直線x+y=9上.

繼續旋轉直線l3：x-my+1=0.如圖3所示，當它經過直線l1：x+3y-3=0與l4：x+y=9的交點A（12，-3）時，平面區域Ⅰ不恒在平面區域Ⅱ的下方，所以也不符合題意.

綜上所述，如圖4所示，當直線l3：x-my+1=0過直線l2：2x-y-3=0與l4：x+y=9的交點B（4，5）時，平面區域Ⅰ恒在平面區域Ⅱ的下方，且x+y取到最大值9，滿足題意.

由l3：x-my+1=0過點（4，5），可解得m=1.

在約束條件含參的線性規劃問題中，參數的本質就是控制含參直線位置的關鍵要素.我們可以先給參數取任意一個常數，即先把含參問題看成一個不含參問題，這樣就能大致作出約束條件所表示的平面區域.再把已知最值的線性目標函數轉化為一個不等式，作出該不等式表示的平面區域.根據題意平移或旋轉含參直線的位置，并判斷這兩個平面區域的位置關系，求出參數值.