【文章內(nèi)容簡介】 。下面分兩步來證明。（1）不是基可行解不是可行域的頂點(diǎn)。不失一般性，假設(shè)的前個分量為正，故有 （）由引理可知線性相關(guān)，即存在一組不全為零的數(shù)使得有 （）（）式乘上一個不為零的數(shù)得： （）（）+（）得：（）（）得：令 又可以這樣來選取，使得對所有有 由此，又即不是可行域的頂點(diǎn)。 （2）不是可行域的頂點(diǎn)不是基可行解。 不失一般性，設(shè)不是可行域的頂點(diǎn)，因而可以找到可行域內(nèi)另外兩個不同點(diǎn)和，有，或可寫為： 因，故當(dāng)時(shí)，必有 因有 故有 （） （）式（）（）得 因不全為零，故線性相關(guān)，即不是基可行解。 若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。 證明：設(shè)是線性規(guī)劃的一個最優(yōu)解，是目標(biāo)函數(shù)的最大值。若不是基可行解，由定理2知不是頂點(diǎn)，一定能在可行域內(nèi)找到通過的直線上的另外兩個點(diǎn)和。將這兩個點(diǎn)代入目標(biāo)函數(shù)有 因?yàn)槟繕?biāo)函數(shù)的最大值，故有 由此，即有。如果或仍不是基可行解，按上面的方法繼續(xù)做下去，最后一定可以找到一個基可行解，其目標(biāo)函數(shù)值等于，問題得證。單純形法(simplex methods) 一般求解線性規(guī)劃問題，是在可行域中的一個頂點(diǎn)到相鄰的另一個頂點(diǎn)迭代，最后到達(dá)最優(yōu)點(diǎn)。它最主要的理論依據(jù)是可行域它是n維向量空間中Rn中的一個多面凸集。當(dāng)中的最優(yōu)點(diǎn)若存在必定在該凸集的某個定點(diǎn)中到達(dá)。這個頂點(diǎn)對應(yīng)的可行解被稱之為基本可行解。它是一個在很多實(shí)踐例子中打磨出來的算法，當(dāng)然也是用的最多的算法，如今仍然是好的選擇。在大部分的線性規(guī)劃軟件中都可以實(shí)現(xiàn)了此算法。 單純形法的基本思想：先找到一個基本可行解的方案，并且它進(jìn)行鑒別，看是否是最優(yōu)解；如果不是，則按照一定規(guī)則轉(zhuǎn)換為另一改進(jìn)的基本可行解,則進(jìn)行另一個鑒別；若還不是的話，我們就再轉(zhuǎn)換,按這方法重復(fù)進(jìn)行。由于基本可行解的數(shù)量有限，它是由轉(zhuǎn)換限制將能夠獲得最優(yōu)解。如果問題沒有最優(yōu)解的話也可以使用此方法來判別。一般的解決問題的步驟的單純形法可歸納如下：①用約束方程組來表達(dá)線性規(guī)劃問題轉(zhuǎn)化為模型方程，找到基本可行解用來作為初始基本可行解。②如果基本可行解不存在，該約束條件是矛盾的，這個問題是無解的。 ③如果基本可行解存在，從基于最佳條件和可行性條件的初始基本可行的解決方案為出發(fā)點(diǎn)，推出一組變量的非基本變量替換，發(fā)現(xiàn)目標(biāo)函數(shù)值更好的另一個基本可行解 ④通過步驟3進(jìn)行迭代,直到對應(yīng)于檢驗(yàn)數(shù)當(dāng)滿足最優(yōu)性條件時(shí)（當(dāng)目標(biāo)函數(shù)值不能得到改善），則將獲得問題的最優(yōu)解。⑤如果發(fā)現(xiàn)問題的目標(biāo)函數(shù)值無界問題的迭代過程，則終止迭代。需要用單純形法求解線性規(guī)劃問題所需的迭代次數(shù)取決于約束條件的數(shù)量?，F(xiàn)在一般的線性規(guī)劃問題的單純形法標(biāo)準(zhǔn)軟件在計(jì)算機(jī)上求解，對于具有106個決策變量和104個約束條件的線性規(guī)劃問題，我們已經(jīng)能夠在計(jì)算機(jī)上解得。 改進(jìn)單純形法：原來的單純形法是很不經(jīng)濟(jì)的。，以提高累積每個迭代，改進(jìn)單純形法進(jìn)誤差單純形法。其基本步驟和單純形法基本上相同，主要的區(qū)別在于，在連續(xù)的迭代不再根據(jù)高斯消去法，但由舊基直接計(jì)算逆矩陣陣列的新的反向，然后由此確定的數(shù)試驗(yàn)。這可以減少累積誤差的迭代，提高精度，同時(shí)減少在計(jì)算機(jī)上的內(nèi)存量。單純形法是從原始的問題到另一個可行解迭代求解可行通過直到試驗(yàn)直到條件的最佳數(shù)量得到滿足。對偶單純形法是為了滿足對偶可行性條件從逐漸離開迭代搜索通過于原問題的最優(yōu)解。在迭代過程的解決方案仍對偶可行性，使任何不可行性逐漸消失。設(shè)原始問題為min{cx|Ax=b，x≥0}，則其對偶問題為 max{yb|yA≤c}。當(dāng)原始問題的一個基解滿足最優(yōu)性條件時(shí),其檢驗(yàn)數(shù)cBB1Ac≤0。即知y＝cBB1（稱為單純形算子）為對偶問題的可行解。所謂滿足對偶可行性，指其檢查數(shù)量滿足最優(yōu)條件。因此，保持了一個可行的解決方案的前提下一當(dāng)基解成為可行解時(shí)，便也就是最優(yōu)解。第三章 Lingo軟件及其在生產(chǎn)規(guī)劃中應(yīng)用 LINGO簡介 LINGO是Linear Interactive and General Optimizer的縮寫，即“交互式的線性和通用優(yōu)化求解器”，由美國LINDO系統(tǒng)公司（Lindo System Inc.）推出的，可以用來求解非線性規(guī)劃等，也可以解決一些線性和非線性方程中使用，功能十分強(qiáng)大，這是要解決的優(yōu)化模型的最佳選擇。[5]其特色在于內(nèi)置建模語言，提供十多個內(nèi)部功能，可以讓決策變量是整數(shù)（即整數(shù)規(guī)劃，其中包括01整數(shù)規(guī)劃），方便靈活，而且執(zhí)行速度非?？焖伲啽?，EXCEL，數(shù)據(jù)庫和其他軟件進(jìn)行數(shù)據(jù)交換 。[5] 在芝加哥，1980年大學(xué)萊納斯施拉格教授開發(fā)了一個專用的軟件包為解決優(yōu)化問題，后來經(jīng)過多年的不斷完善和擴(kuò)充，并建立LINDO系統(tǒng)商業(yè)化運(yùn)營取得了巨大的成功。具有絕對優(yōu)勢，在優(yōu)化軟件市場，根據(jù)網(wǎng)上提供的公司信息，世界雜志之間“財(cái)富”500強(qiáng)企業(yè)中有一半以上使用這些產(chǎn)品，其中位列世界“財(cái)富”雜志25有23公司在使用這些產(chǎn)品。讀者可以從該公司的主頁了解更多的信息，尤其是該公司的產(chǎn)品可以下載試玩版（DEMO）和大量的應(yīng)用實(shí)例。演示版和基本功能正式版是一樣的，但規(guī)模（決策變量和約束數(shù)目），解決了試用版的問題是嚴(yán)格限制。LINGO的前身是LINDO，LINDO只能求解線性規(guī)劃和二次規(guī)劃(求解二次規(guī)劃時(shí)又較繁瑣的程序轉(zhuǎn)換)，有豐富的結(jié)果分析；后來為了解決非線性規(guī)劃問題，LINDO公司開發(fā)了LINGO， LINGO(包括LINDO)的最大特色在于可以允許決策變量是整數(shù)(甚至01整數(shù))，而且運(yùn)行速度快。LINGO優(yōu)化仍然是一個建模語言，包括許多常用數(shù)學(xué)函數(shù)對調(diào)用用戶的問題，并且可以接受（，數(shù)據(jù)庫文件，...）都在其他數(shù)據(jù)文件優(yōu)化的專業(yè)知識，我們不知道多少用戶可以輕松地創(chuàng)建和投入，切實(shí)解決在實(shí)踐中遇到的分析，大規(guī)模的優(yōu)化問題，一般都能夠快速獲得復(fù)雜的優(yōu)化問題的高品質(zhì)的解決方案。此外，LINGO還提供了一個接口軟件LINDOAPI等開發(fā)工具（如C++，Java等語言），從而使LINGO也方便到用戶的應(yīng)用軟件開發(fā)中去。最后的LINGO提供一個電子表格軟件（一個接口EXCEL，等等）可以直接集成到使用中的電子表格軟件。因?yàn)長INGO完全自包含的功能LINDOLINGO9開始，所以LINDOLINDO公司已從其目錄，這意味著將有軟件LINDO沒有新版了。 LINGO的特點(diǎn)LINGO全稱是Linear INteractive and General Optimizer的縮寫交互式的線性和通用優(yōu)化求解器,它是一套設(shè)計(jì)用來幫助您快速,輕松和有效的構(gòu)建和求解線性,非線性,以及全面的優(yōu)化工具整數(shù)功能模型,其中包括功能強(qiáng)大的建模語言,建立和編輯功能齊全的環(huán)境問題的函數(shù)來讀取和寫入Excel和數(shù)據(jù)庫和一系列完全內(nèi)置的求解程序 [5] 。 運(yùn)行環(huán)境： Win9x/NT/2000/XP/2003 軟件類別：計(jì)算工具/工具軟件/ 國外軟件軟件語言： 英文 Lingo 是使建立和求解線性、非線性和整數(shù)優(yōu)化模型綜合工具更快，更容易，更高效,Lingo 提供強(qiáng)大的語言和快速的求解引擎來求解最優(yōu)化模型[5] 。 簡單的模型表示 Lingo 可以將線性、非線性和整數(shù)問題迅速制定，易于閱讀，并且理解和修改，LINGO的建模語言，允許您使用總結(jié)和下標(biāo)變量在一個更簡單的，直觀的方式來表示模型，非常類似您在使用筆和紙,該模型更加易構(gòu)建，更容易理解，因此也更容易維護(hù) [5] 。 Lingo 建立的模型可以直接從數(shù)據(jù)庫或帶電子表格數(shù)據(jù)來獲得，Lingo也可以同樣的方式求解方案結(jié)果直接輸出到數(shù)據(jù)庫或電子表格，可生成你所選擇的應(yīng)用報(bào)告[5] 。 LINGO擁有一套完整快速的，內(nèi)置求解器來求解線性，非線性（球面amp。非球面的),二次的,二次約束和整數(shù)優(yōu)化問題,您甚至不需要指定或啟動特定的求解器,因?yàn)長INGO會讀取您的方程式并自動選擇合適的求解器[5] 。 您可以在Lingo內(nèi)創(chuàng)建和求解的模型，也可以直接編寫自己的應(yīng)用程序來調(diào)用lingo，用于開發(fā)交互式模型，LINGO也提供了一套完整的建模環(huán)境來構(gòu)建，用于求解和分析模型，對于構(gòu)建turnkey解決方案，DLL和OLE接口LINGO直接提供了可從用戶調(diào)用自己編寫的程序，LINGO也可以直接從Excel宏或數(shù)據(jù)庫應(yīng)用程序中被直接調(diào)用[5] 。 LINGO在產(chǎn)品生產(chǎn)計(jì)劃線性規(guī)劃中應(yīng)用擴(kuò)展 LINGO一般最主要的應(yīng)用范圍包括：生產(chǎn)線規(guī)劃，庫存管理，財(cái)務(wù)金融，資源分配等等。在制造企業(yè)的中期或短期生產(chǎn)計(jì)劃管理中，它往往是被當(dāng)作生產(chǎn)計(jì)劃的優(yōu)化問題：在一個給定的外部需求和生產(chǎn)能力等限制下，按照一定的生產(chǎn)目標(biāo)，來準(zhǔn)備接下來幾個月的生產(chǎn)周期最佳的生產(chǎn)計(jì)劃[3]。庫存管理是定量方法和技術(shù)的最古老的領(lǐng)域之一，是存儲系統(tǒng)，運(yùn)作規(guī)則，以及如何找到一個最佳的科學(xué)存儲策略的性質(zhì)問題的研究，是運(yùn)籌學(xué)的一個重要分支。一般數(shù)學(xué)建模的庫存管理一般分為兩類：一類是確定性模型，它不包含任何隨機(jī)因素，另一種是用隨機(jī)因素的隨機(jī)存儲模型[3]。 本文最主要的用了生產(chǎn)規(guī)劃，利用lingo優(yōu)化模型。第四章 保險(xiǎn)柜年度生產(chǎn)計(jì)劃模型隨著人們生活水平的提高，保險(xiǎn)柜行業(yè)本以為保險(xiǎn)柜產(chǎn)品將成為人們生活的一項(xiàng)必需品，各大保險(xiǎn)柜行業(yè)提高了生產(chǎn)量，據(jù)了解，在歐美等等一些發(fā)達(dá)國家，保險(xiǎn)柜是生活不可缺的一部分，使用比例高達(dá)90%，而在我國比例不到5%，這種差距很明顯的表明了消費(fèi)觀念的巨大差距，而現(xiàn)導(dǎo)致庫存增加，銷售競爭日益上漲，嚴(yán)重影響行業(yè)的資金周轉(zhuǎn)問題。 近年來，保險(xiǎn)柜公司的保險(xiǎn)柜生產(chǎn)經(jīng)營也出現(xiàn)資金周轉(zhuǎn)困難等問題。以至開工不足、庫存增加，然而國內(nèi)保險(xiǎn)柜公司個個出謀劃策，市場競爭日趨激烈，該公司原有的優(yōu)勢逐漸喪失，保險(xiǎn)柜公司未來的發(fā)展面臨前所未有的挑戰(zhàn)。在市場上銷售的比較廣泛，主要用于私人家庭、學(xué)生寢室、公司辦公、由于管理模式的落后，跟不上時(shí)代的需求導(dǎo)致公司越顯蕭條，尤其是隨著經(jīng)