【正文】 如果變量表示第種產(chǎn)品期內(nèi)產(chǎn)量相對于前期產(chǎn)量的增加值，則的取值范圍為，稱取值不受約束，或無約束。剛上述線性規(guī)劃問題的數(shù)學(xué)模型可表示為：上述模型的簡寫形式為用向量形式表達(dá)時，上述模型可寫為：式中；；；用矩陣和向量形式來表示可寫為：稱為約束方程組（約束條件）的系數(shù)矩陣。這時此例數(shù)學(xué)模型可表示為 由此例可以看出，規(guī)劃問題的數(shù)學(xué)模式型由三個要素組成：⑴變量，或稱決策變量，是問題中要確定的未知量，它用以表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制；⑵目標(biāo)函，它是決策變量的函數(shù)，按優(yōu)化目標(biāo)分別在這個函數(shù)前加上或；⑶約束條件，指決策變量取值時受到的各種資源條件的限制，通常表達(dá)為含決策變量的等式或不等式。問該公司應(yīng)制造兩種家電各多少件，使獲取的利潤為最大。2．1．1線性問題的數(shù)學(xué)模型例1：美佳公司計劃制造Ⅰ，Ⅱ兩種家電產(chǎn)品。第2章線性規(guī)劃問題本章主要介紹線性規(guī)劃本身和一系列相關(guān)性質(zhì)問題，并相應(yīng)舉出一些簡單的例子更好的闡述了線性規(guī)劃問題。本文共分為四章。這也將成為未來企業(yè)生產(chǎn)與管理的普遍方法。隨著經(jīng)濟(jì)社會的發(fā)展，線性規(guī)劃在資源配置和企業(yè)管理方面發(fā)揮著獨特的作用。林海明早在1996年就立足于較強(qiáng)的普及性，從經(jīng)濟(jì)常識的角度來認(rèn)知線性規(guī)劃問題的解法，初步論述這一問題；熊福力、張曉東等在2004年作了《基于利潤最大化的油田開發(fā)非線性規(guī)劃》一文，他們根據(jù)油田開發(fā)的實際情況，將油田和利潤細(xì)分為幾個部分，以獲得最大利潤為目標(biāo)，建立了油田開發(fā)的數(shù)學(xué)模型；吳海華和王志江在《關(guān)于影子價格作為企業(yè)資源配置依據(jù)的探討》根據(jù)線性規(guī)劃模型資源影子價格的經(jīng)濟(jì)意義，討論了在企業(yè)以收入最大化和利潤最大化兩種情況下，影子價格作為企業(yè)資源配置依據(jù)時存在的問題。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。用這種方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形法所用時間的1/50。 　　1979年蘇聯(lián)數(shù)學(xué)家L. G. Khachian提出解線性規(guī)劃問題的橢球算法，并證明它是多項式時間算法。 　　線性規(guī)劃的研究成果還直接推動了其他數(shù)學(xué)規(guī)劃問題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。 　　50年代后對線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。 　　,開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。 　　《生產(chǎn)組織與計劃中的數(shù)學(xué)方法》一書中提出線性規(guī)劃問題，也未引起重視。線性規(guī)劃問題的難點表現(xiàn)在三個方面：一是將實際問題抽象為線性規(guī)劃模型；二是線性約束條件和線性目標(biāo)函數(shù)的幾何表征；三是線性規(guī)劃最優(yōu)解的探求。引 言線性規(guī)劃主要用于解決生活、生產(chǎn)中的資源利用、人力調(diào)配、生產(chǎn)安排等問題，它是一種重要的數(shù)學(xué)模型．簡單的線性規(guī)劃指的是目標(biāo)函數(shù)含兩個自變量的線性規(guī)劃，其最優(yōu)解可以用數(shù)形結(jié)合方法求出。涉及更多個變量的線性規(guī)劃問題不能用初等方法解決。線性規(guī)劃的發(fā)展史法國數(shù)學(xué)家 －普森分別于1832和1911年獨立地提出線性規(guī)劃的想法，但未引起注意。 　　──單純形法，為這門學(xué)科奠定了基礎(chǔ)。 　　，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎。例如。由于數(shù)字電子計算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規(guī)劃問題。 　　?，F(xiàn)已形成線性規(guī)劃多項式算法理論。隨著經(jīng)濟(jì)的發(fā)展，關(guān)于線性規(guī)劃在企業(yè)中的應(yīng)用越來越廣泛。胡徐勝、劉娟和汪發(fā)亮在《最優(yōu)控制在汽車企業(yè)利潤最大化中的應(yīng)用》一文中從汽車企業(yè)職工結(jié)構(gòu)角度出發(fā)，研究在企業(yè)提供職工工資總量不超過某一限定值的情況下,如何分配汽車企業(yè)中普通職工與高級職工的比例來達(dá)到實現(xiàn)汽車企業(yè)利潤最大化的目標(biāo)。在企業(yè)的各項管理活動中，例如計劃、生產(chǎn)、運輸、技術(shù)等問題，從各種限制條件的組合中，通過對實際數(shù)據(jù)的分析處理和數(shù)學(xué)模型的建立，選擇出最為合理的計算方法，建立線性規(guī)劃模型從而求得最佳結(jié)果，給出了更多的決策參考信息。 不單如此，企業(yè)現(xiàn)如今更著重于對各種條件組合中限制條件作局部調(diào)整以達(dá)到對獲得利潤的一種控制，而這恰恰也是線性規(guī)劃問題中靈敏度分析所研究的對象。在第一章，介紹本文的背景和線性規(guī)劃的發(fā)展?fàn)顩r；在第二章，介紹線性規(guī)劃本身和一系列相關(guān)性質(zhì)問題及企業(yè)利潤最大化數(shù)學(xué)模型的基礎(chǔ)知識；在第三章，介紹利用線性規(guī)劃建立企業(yè)利潤最大化數(shù)學(xué)模型；最后，求解模型最優(yōu)解。本章主要借鑒于胡運權(quán)、郭耀煌等編著，清華大學(xué)出版社出版的《運籌學(xué)教程（第二版）》的內(nèi)容。已知各制造一件時分別占用的設(shè)備A，B的臺時、調(diào)試工序及每天可用于這兩種家電的能力、各售出一件時的獲利情況，如表1所示。表1項目ⅠⅡ每天可用能力設(shè)備A（h）0515設(shè)備B（h）6224調(diào)試工序（h）113利潤（元）21 對上例用和分別表示美佳公司制造家電Ⅰ和Ⅱ的數(shù)量。假定線性規(guī)劃問題中含個變量，分別用（）表示，在目標(biāo)函數(shù)中的系數(shù)為（通常稱為價值系數(shù)），的取值受項 資源的限制，用（）表標(biāo)第種資源的擁有量，用表示變量取值為1個單位時所消耗或含有的第種資源的數(shù)理量，通常稱為技術(shù)系數(shù)或工藝系數(shù)。 變量的取值一般配為非負(fù)，即；從數(shù)學(xué)意義上可以有。2．1．1．2線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)是問題的標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式的線性規(guī)劃模型中，目標(biāo)函數(shù)為求極大值，約束條件全為等式，約束條件右端常數(shù)項全為非負(fù)值，變量的取值全為非負(fù)值。1）目標(biāo)函數(shù)為求極小值，即為：因為求等價于求，令，即化為：2）約束條件的右端項時，只需將等式或不等式兩端同乘（1），則等式右端項必大于零。當(dāng)約束條件為“≤”時，如，可令，得，顯然。和是新加上去的變量，取值均為非負(fù)，加到原約束條中去的變量其目的是使不等式轉(zhuǎn)化為等式，其中稱為松弛變量，一般配稱為剩余變量，但也有稱松弛變量的。4）取值無約束的變量是。5）對的情況，令，顯然。否則稱這組向量在F上線性無關(guān)。若A的n個列向量中有r個線性無關(guān)（），而所有個數(shù)大于r的列向量組都線性相關(guān)，則稱數(shù)r為矩陣A的列秩。矩陣A的列秩與行秩一定相等，它也稱為矩陣A的秩。若B是A中mm非奇異子矩陣（即可逆矩陣，有），則稱B是線性規(guī)劃問題的一個基，B是由A中m個線性無關(guān)的系數(shù)列向量組成的。l 線性規(guī)劃若有最優(yōu)解，一定可在可行域頂點上得到。 ②對約束條件含≥或＝號時，可構(gòu)造人工基，人為產(chǎn)生一個單位矩陣，用大法或兩階段法獲得初始基可行解。若存在某個非基變量的檢驗數(shù)為零時，線性規(guī)劃問題有無窮多最優(yōu)解；當(dāng)所有非基變量的檢驗數(shù)均嚴(yán)格小于零時，線性規(guī)劃問題具有唯一最優(yōu)解。 ③當(dāng)存在某些非變量的檢驗數(shù)大于零，需要找個一個新的基可行解，即要進(jìn)行基變換。 設(shè)～為基變量，～為非基變量基100001002）計算檢驗數(shù)進(jìn)行最優(yōu)性檢驗。3）換基。4）通過初等行變換將系數(shù)矩陣中變量對應(yīng)列變換為第個元素為1的單位列向量，用代為新的基變量，列出新的單純形表，回到第二步驟。令非基變量等于零，即找到一個初始基可行解以此列出初始單純形表記作表2如下：表221000基01505100024[6]2010051100121000因表中有大于零的檢驗數(shù)，故表中基可行解不是最優(yōu)解。將列除以的同行數(shù)字得，由此6為主元素，作為標(biāo)志對主元素6加上方括號[ ]，主元素所在行基變量為換出量。2．2．3對偶單純形法2．2．3．1單純形法計算的矩陣描述對稱形式線性規(guī)劃問題的矩陣表達(dá)式加上松弛變量后為： (1)上式中為松弛變量，為單位矩陣。設(shè)迭代若干步后，基變量為，在初始單純形表中的系數(shù)矩陣為。 表5項目非基變量基變量00當(dāng)?shù)舾刹?，基變量為時，則該步的單純形表中由系數(shù)組成的矩陣為。故當(dāng)基變量為時，新的單純形表具有表6形式。4）若初始矩陣中變量的系數(shù)向量為迭代后為，則有 （2）5）當(dāng)為最優(yōu)解時，在表6中應(yīng)有 （3） （4） 因的檢驗數(shù)可寫為 （5） 故(3)～(5)式可重寫為 （6） （7）稱為單純乘子，若令 則（6）、（7）式可改寫為 （8） 看出