暑假社會實踐報告(超市)及數(shù)學(xué)建模之線性規(guī)劃

兩年前遙望象牙塔走過獨木橋的我們踏進大學(xué)的校門，轉(zhuǎn)眼間一年半的大學(xué)生活在歡聲笑語中結(jié)束。一年半的大學(xué)生活雖沒有高中那種披星戴月的壓抑但也讓我放松不下來。大學(xué)生活是愜意的，走進大學(xué)校門面對那么多優(yōu)秀的學(xué)長學(xué)姐以及同級同學(xué)我開始緊張，緊張如何在優(yōu)秀的人群中脫穎而出緊張畢業(yè)后該干什么。暑假，回到家當大學(xué)帶給我的那份興奮及愜意漸漸退去的時候，我意識到不能再享受無憂無慮的生活，看似平靜而快樂的學(xué)校生活其實也隱藏著“危機”——就業(yè)的危機。因此對將來的那種緊張感越來越強烈。大學(xué)是溝通校園與社會的橋梁，使我們進去社會前必須充實自己的“深加工廠”。最終我們要面臨社會和市場的無情競爭和淘汰，僅僅依靠校園里的知識是遠遠不夠的。于是我開始考慮如何在寒假充實自己學(xué)到在學(xué)校學(xué)不到的東西。同學(xué)們都在努力通過各種機會鍛煉自己我也不能落后。如何才能更好的感受就業(yè)現(xiàn)狀？經(jīng)過考慮后我根據(jù)自己的時間及自身實際情況找了一份促銷的工作，雖然只有短短的15天，但我覺得受益匪淺，基本達到了自己的目的。短短的工作讓我體會到了就業(yè)的壓力，自己能力的欠缺以及社會的艱辛，同時也感到無比的快樂，一種在學(xué)校自由天地?zé)o法體會到的“愉快”。促銷是一種很好的工作體驗，通過人與人的溝通可以了解一些與我們專業(yè)相關(guān)的知識，用我們的所學(xué)與實際相結(jié)合從來達到自己的目的。（一）工作概述接到超市負責(zé)人電話的時候是8月1號，他們讓我下午去超市找工作負責(zé)人報道，并且了解一些超市的工作制度及上下班時間，下午去見了負責(zé)人知道了自己上班的具體安排，比如：上班期間要穿工作服，工作期間不能與其他工作人員說話，不準擅自離開工作崗位，隨即給我們介紹了即將促銷的產(chǎn)品的價格和功效，適合什么樣的消費者等一些介紹，負責(zé)人像個大姐姐，我向她說明了自己是個學(xué)生，并且也保證會努力工作。在這15天中接觸了形形色色的顧客，大部分顧客是友善的。當然也有難纏的，喜歡刁難人的顧客。因為有針對性的去推銷產(chǎn)品，所以我的銷售額要比其他顧客高，我們的產(chǎn)品是德芙巧克力，因為農(nóng)歷七月七日是情人節(jié)所以我們加大了對德芙巧克力的宣傳，如果單純的向顧客介紹巧克未免顯得太老套，所以我們這樣，可以曾送迷你情侶小玩具，以及將單個巧克力組成花形加大對顧客的吸引力。情人節(jié)那天銷量突破四萬三，負責(zé)人獎勵我們200塊錢及一盒巧克力，拿著自己掙的錢，心里有種說不出的滿足感。（二）應(yīng)具備的素質(zhì)通過這半個月和不同的人打交道我總結(jié)出作為一名服務(wù)人員應(yīng)具備的一些素質(zhì)：一．充分了解自己所銷售的產(chǎn)品。只有了解自己的產(chǎn)品在顧客詢問時你才能做出相應(yīng)的回答，如果不事先了解自己的產(chǎn)品，在顧客詢問時自己就不會給顧客想要的信息，從而得不到顧客的信任。二．微笑面對每一位顧客。對人友善肯定會得回報。表現(xiàn)友善最好的方法就是微笑，微笑是人類共有的語言。不管從事什么行業(yè)，都應(yīng)該將微笑作為習(xí)慣。面對微笑的人給人一種親近而友善的感覺，微笑是人的一種本能，無需成本也無需努力，但它使人感到舒適，樂于接受你。相當于面無表情的人，顧客當然喜歡跟面帶微笑的打交道，更何況，顧客就是上帝。三．良好的服務(wù)態(tài)度。包括熱情待人，耐心回答顧客的詢問，不能對顧客不理不睬，不能對顧客的詢問不耐煩，而應(yīng)該耐心回答顧客的詢問。四．具有隨機應(yīng)變的能力。要具有隨機應(yīng)變的能力是因為在促銷過程中會遇到千奇百怪的人和事，如果沒有隨機應(yīng)變的能力只拘泥于一般的原則有可能但只交易失敗給自己帶來不必要的麻煩。因此，一定要有隨機應(yīng)變的能力。（三）工作體會以上幾點是我這個半個月總結(jié)出來的經(jīng)驗，也是我做促銷員的一點收獲。公司只配一個促銷員在超市里，所以客流量不是很多的時候，我就會和超市的阿姨們多了解一下一些超市的人流量主要是在哪個年齡段，這樣在促銷的時候就會有針對性，針對每個年齡段的顧客進行促銷。還有超市的理貨員沒有及時上貨或者沒有擺好貨物，我要是有時間就會幫他們擺好，因為超市不大理貨員也不多，要是他們?nèi)ツ秘浕蛘叱燥埖臅r間，只有少部分人員在超市里，我也會幫忙照看，如果顧客不知道擺放的貨物在哪里我也會指引他們?nèi)ツ盟麄冃枰呢浳?。畢竟我也算超市的一本分了。我們的形象就是超市的形象，在超市里主管就像是一個大姐，對待人特別好，剛進去我不太熟悉超市的一些概況，她就會耐心的帶我轉(zhuǎn)一圈了解超市的流程。她說自己也是從新人一步一步走上來的，所以特別了解我們學(xué)生。主管打拼這么多年，她在做事方面積累了不少經(jīng)驗。所以在工作過程中碰到一些自己不懂的我就會請教她。她經(jīng)常說的一句話就是“你是大學(xué)生是接受高等教育的”在學(xué)校讀書的時候，你應(yīng)該充分利用課余時間多學(xué)習(xí)，不斷充實自己，提高自己。你還年輕，年輕人就該吃得苦中苦，方為人上人啊。而且年輕時不吃苦，老了會更辛苦。確實，不愧是過來人說的話，將簡單而精辟，我最喜歡最后那句“年輕時不吃苦，嘮了會更辛苦”。這句話我覺得可以算金玉良言了，也在某種程度上給我指明了一種方向。我工作的最后一天主管還特地找我聊了一夏天，她說“一個人在讀書的時候最重要的是學(xué)習(xí)，但是學(xué)習(xí)之余也要多接觸社會，增長見識，鍛煉自己，應(yīng)該多利用放假時間出來接觸社會，了解社會。這些話我聽在耳里記在心里。最令我開心的是我的工作得到了認可主管還說以后假期還想在那工作就回去。（四）結(jié)論短短半個月的社會實踐讓我看到了一些在學(xué)?？床坏降臇|西，也學(xué)到了一些在學(xué)校學(xué)不到的知識。我想我只有抓住有利時機參與各種形式的社會實踐活動，認識社會，認識自己的社會位置，明確自己的使命，激發(fā)自己的學(xué)習(xí)熱情，調(diào)整和完整自己的知識結(jié)構(gòu)，戰(zhàn)勝各種困難和挫折，鍛煉意志和毅力，這些應(yīng)該是這次實踐活動最大的收獲。我相信，只要我堅持著自己的信念不動搖，不端積累經(jīng)驗鍛煉自己提高自己，就算是面對嚴峻的就業(yè)壓力我也會創(chuàng)造出屬于自己的樂園！我蓄勢待發(fā)?。?！第一章線性規(guī)劃§1線性規(guī)劃在人們的生產(chǎn)實踐中，經(jīng)常會遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大經(jīng)濟效益的問題。此類問題構(gòu)成了運籌學(xué)的一個重要分支—數(shù)學(xué)規(guī)劃，而線性規(guī)劃(LinearProgramming簡記LP)則是數(shù)學(xué)規(guī)劃的一個重要分支。自從1947年G.B.Dantzig提出求解線性規(guī)劃的單純形方法以來，線性規(guī)劃在理論上趨向成熟，在實用中日益廣泛與深入。特別是在計算機能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了，已成為現(xiàn)代管理中經(jīng)常采用的基本方法之一。1.1線性規(guī)劃的實例與定義例1某機床廠生產(chǎn)甲、乙兩種機床，每臺銷售后的利潤分別為4000元與3000元。生產(chǎn)甲機床需用機器加工，加工時間分別為每臺2小時和1小時；生產(chǎn)乙機床需用三種機器加工，加工時間為每臺各一小時。若每天可用于加工的機器時數(shù)分別為機器10小時、機器8小時和機器7小時，問該廠應(yīng)生產(chǎn)甲、乙機床各幾臺，才能使總利潤最大？上述問題的數(shù)學(xué)模型：設(shè)該廠生產(chǎn)臺甲機床和乙機床時總利潤最大，則應(yīng)滿足（目標函數(shù)）(1)s.t.（約束條件）（2）這里變量稱之為決策變量，（1）式被稱為問題的目標函數(shù)，（2）中的幾個不等式是問題的約束條件，記為s.t.(即subjectto)。由于上面的目標函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題?？傊?，線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標函數(shù)最大或最小的問題。在解決實際問題時，把問題歸結(jié)成一個線性規(guī)劃數(shù)學(xué)模型是很重要的一步，但往往也是困難的一步，模型建立得是否恰當，直接影響到求解。而選適當?shù)臎Q策變量，是我們建立有效模型的關(guān)鍵之一。線性規(guī)劃的Matlab標準形式線性規(guī)劃的目標函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號可以是小于號也可以是大于號。為了避免這種形式多樣性帶來的不便，Matlab中規(guī)定線性規(guī)劃的標準形式為其中和為維列向量，、為適當維數(shù)的矩陣，、為適當維數(shù)的列向量。例如線性規(guī)劃的Matlab標準型為1.3線性規(guī)劃問題的解的概念一般線性規(guī)劃問題的標準型為(3)s.t.(4)可行解滿足約束條件（4）的解，稱為線性規(guī)劃問題的可行解，而使目標函數(shù)（3）達到最小值的可行解叫最優(yōu)解?？尚杏蛩锌尚薪鈽?gòu)成的集合稱為問題的可行域，記為。1.4線性規(guī)劃的圖解法圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理。我們先應(yīng)用圖解法來求解例1。對于每一固定的值，使目標函數(shù)值等于的點構(gòu)成的直線稱為目標函數(shù)等位線，當變動時，我們得到一族平行直線。對于例1，顯然等位線越趨于右上方，其上的點具有越大的目標函數(shù)值。不難看出，本例的最優(yōu)解為，最優(yōu)目標值。從上面的圖解過程可以看出并不難證明以下斷言：（1）可行域可能會出現(xiàn)多種情況?？赡苁强占部赡苁欠强占?，當非空時，它必定是若干個半平面的交集（除非遇到空間維數(shù)的退化）。既可能是有界區(qū)域，也可能是無界區(qū)域。（2）在非空時，線性規(guī)劃既可以存在有限最優(yōu)解，也可以不存在有限最優(yōu)解（其目標函數(shù)值無界）。（3）若線性規(guī)劃存在有限最優(yōu)解，則必可找到具有最優(yōu)目標函數(shù)值的可行域的“頂點”。上述論斷可以推廣到一般的線性規(guī)劃問題，區(qū)別只在于空間的維數(shù)。在一般的維空間中，滿足一線性等式的點集被稱為一個超平面，而滿足一線性不等式（或）的點集被稱為一個半空間（其中為一維行向量，為一實數(shù)）。若干個半空間的交集被稱為多胞形，有界的多胞形又被稱為多面體。易見，線性規(guī)劃的可行域必為多胞形（為統(tǒng)一起見，空集也被視為多胞形）。在一般維空間中，要直接得出多胞形“頂點”概念還有一些困難。二維空間中的頂點可以看成為邊界直線的交點，但這一幾何概念的推廣在一般維空間中的幾何意義并不十分直觀。為此，我們將采用另一途徑來定義它。定義1稱維空間中的區(qū)域為一凸集，若及，有。定義2設(shè)為維空間中的一個凸集，中的點被稱為的一個極點，若不存在及，使得。定義1說明凸集中任意兩點的連線必在此凸集中；而定義2說明，若是凸集的一個極點，則不能位于中任意兩點的連線上。不難證明，多胞形必為凸集。同樣也不難證明，二維空間中可行域的頂點均為的極點（也沒有其它的極點）。1.5求解線性規(guī)劃的Matlab解法單純形法是求解線性規(guī)劃問題的最常用、最有效的算法之一。這里我們就不介紹單純形法，有興趣的讀者可以參看其它線性規(guī)劃書籍。下面我們介紹線性規(guī)劃的Matlab解法。Matlab中線性規(guī)劃的標準型為基本函數(shù)形式為linprog(c,A,b)，它的返回值是向量的值。還有其它的一些函數(shù)調(diào)用形式（在Matlab指令窗運行helplinprog可以看到所有的函數(shù)調(diào)用形式），如：[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)這里fval返回目標函數(shù)的值，LB和UB分別是變量的下界和上界，是的初始值，OPTIONS是控制參數(shù)。例2求解下列線性規(guī)劃問題解（=1\*romani）編寫M文件c=[2;3;-5];a=[-2,5,-1];b=-10;aeq=[1,1,1];beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1))value=c'*x（=2\*romanii）將M文件存盤，并命名為example1.m。（=3\*romaniii）在Matlab指令窗運行example1即可得所求結(jié)果。求解線性規(guī)劃問題解編寫Matlab程序如下：c=[2;3;1];a=[1,4,2;3,2,0];b=[8;6];[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))1.6可以轉(zhuǎn)化為線性規(guī)劃的問題很多看起來不是線性規(guī)劃的問題也可以通過變換變成線性規(guī)劃的問題來解決。如：規(guī)劃問題為其中，和為相應(yīng)維數(shù)的矩陣和向量。要把上面的問題變換成線性規(guī)劃問題，只要注意到事實：對任意的，存在滿足，事實上，我們只要取，就可以滿足上面的條件。這樣，記，，從而我們可以把上面的問題變成例5其中。對于這個問題，如果我們?nèi)?，這樣，上面的問題就變換成此即我們通常的線性規(guī)劃問題?！?運輸問題(產(chǎn)銷平衡)例6某商品有個產(chǎn)地、個銷地，各產(chǎn)地的產(chǎn)量分別為，各銷地的需求量分別為。若該商品由產(chǎn)地運到銷地的單位運價為，問應(yīng)該如何調(diào)運才能使總運費最??？解：引入變量，其取值為由產(chǎn)地運往銷地的該商品數(shù)量，數(shù)學(xué)模型為s.t.顯然是一個線性規(guī)劃問題，當然可以用單純形法求解。對產(chǎn)銷平衡的運輸問題，由于有以下關(guān)系式存在：其約束條件的系數(shù)矩陣相當特殊，可用比較簡單的計算方法，習(xí)慣上稱為表上作業(yè)法（由康托洛維奇和希奇柯克兩人獨立地提出，簡稱康—希表上作業(yè)法）。§3指派問題3.1指派問題的數(shù)學(xué)模型例7擬分配人去干項工作，每人干且僅干一項工作，若分配第人去干第項工作，需花費單位時間，問應(yīng)如何分配工作才能使工人花費的總時間最少？容易看出，要給出一個指派問題的實例，只需給出矩陣，被稱為指派問題的系數(shù)矩陣。引入變量，若分配干工作，則取，否則取。上述指派問題的數(shù)學(xué)模型為s.t.(5)(5)的可行解既可以用一個矩陣表示，其每行每列均有且只有一個元素為1，其余元素均為0，也可以用中的一個置換表示。(5)的變量只能取0或1，從而是一個0-1規(guī)劃問題。一般的0-1規(guī)劃問題求解極為困難。但指派問題并不難解，其約束方程組的系數(shù)矩陣十分特殊（被稱為全單位模矩陣，其各階非零子式均為），其非負可行解的分量只能取0或1，故約束可改寫為而不改變其解。此時，指派問題被轉(zhuǎn)化為一個特殊的運輸問題，其中，。3.2求解指派問題的匈牙利算法由于指派問題的特殊性，又存在著由匈牙利數(shù)學(xué)家Konig提出的更為簡便的解法—匈牙利算法。算法主要依據(jù)以下事實：如果系數(shù)矩陣一行（或一列）中每一元素都加上或減去同一個數(shù)，得到一個新矩陣

，則以或為系數(shù)矩陣的指派問題具有相同的最優(yōu)指派。例8求解指派問題，其系數(shù)矩陣為解將第一行元素減去此行中的最小元素15，同樣，第二行元素減去17，第三行元素減去17，最后一行的元素減去16，得再將第3列元素各減去1，得以為系數(shù)矩陣的指派問題有最優(yōu)指派由等價性，它也是例7的最優(yōu)指派。有時問題會稍復(fù)雜一些。例9求解系數(shù)矩陣的指派問題解：先作等價變換如下容易看出，從變換后的矩陣中只能選出四個位于不同行不同列的零元素，但，最優(yōu)指派還無法看出。此時等價變換還可進行下去。步驟如下：對未選出0元素的行打；對行中0元素所在列打；對列中選中的0元素所在行打；重復(fù)（2）、（3）直到無法再打為止?？梢宰C明，若用直線劃沒有打的行與打的列，就得到了能夠覆蓋住矩陣中所有零元素的最少條數(shù)的直線集合，找出未覆蓋的元素中的最小者，令行元素減去此數(shù)，列元素加上此數(shù)，則原先選中的0元素不變，而未覆蓋元素中至少有一個已轉(zhuǎn)變?yōu)?，且新矩陣的指派問題與原問題也等價。上述過程可反復(fù)采用，直到能選取出足夠的0元素為止。例如，對例5變換后的矩陣再變換，第三行、第五行元素減去2，第一列元素加上2，得現(xiàn)在已可看出，最優(yōu)指派為?！?對偶理論與靈敏度分析4.1原始問題和對偶問題考慮下列一對線性規(guī)劃模型：s.t.(P)和s.t.(D)稱（P）為原始問題，（D）為它的對偶問題。不太嚴謹?shù)卣f，對偶問題可被看作是原始問題的“行列轉(zhuǎn)置”：原始問題中的第列系數(shù)與其對偶問題中的第行的系數(shù)相同；原始目標函數(shù)的各個系數(shù)行與其對偶問題右側(cè)的各常數(shù)列相同；原始問題右側(cè)的各常數(shù)列與其對偶目標函數(shù)的各個系數(shù)行相同；在這一對問題中，不等式方向和優(yōu)化方向相反?？紤]線性規(guī)劃：把其中的等式約束變成不等式約束，可得它的對偶問題是其中和分別表示對應(yīng)于約束和的對偶變量組。令，則上式又可寫成原問題和對偶的對偶約束之間的關(guān)系：對偶問題的基本性質(zhì)1o對稱性：對偶問題的對偶是原問題。2o弱對偶性：若是原問題的可行解，是對偶問題的可行解。則存在。3o無界性：若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。4o可行解是最優(yōu)解時的性質(zhì)：設(shè)是原問題的可行解，是對偶問題的可行解，當時，是最優(yōu)解。5o對偶定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解；且目標函數(shù)值相同。6o互補松弛性：若分別是原問題和對偶問題的最優(yōu)解，則例10已知線性規(guī)劃問題已知其對偶問題的最優(yōu)解為。試用對偶理論找出原問題的最優(yōu)解。解先寫出它的對偶問題=1\*GB3① =2\*GB3②=3\*GB3③=4\*GB3④=5\*GB3⑤將的值代入約束條件，得=2\*GB3②，=3\*GB3③，=4\*GB3④為嚴格不等式；由互補松弛性得。因；原問題的兩個約束條件應(yīng)取等式，故有求解后得到；故原問題的最優(yōu)解為。4.3靈敏度分析在以前討論線性規(guī)劃問題時，假定都是常數(shù)。但實際上這些系數(shù)往往是估計值和預(yù)測值。如市場條件一變，值就會變化；往往是因工藝條件的改變而改變；是根據(jù)資源投入后的經(jīng)濟效果決定的一種決策選擇。因此提出這樣兩個問題：當這些系數(shù)有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化；或者這些系數(shù)在什么范圍內(nèi)變化時，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變。這里我們就不討論了。參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃是研究這些參數(shù)中某一參數(shù)連續(xù)變化時，使最優(yōu)解發(fā)生變化的各臨界點的值。即把某一參數(shù)作為參變量，而目標函數(shù)在某區(qū)間內(nèi)是這參變量的線性函數(shù)，含這參變量的約束條件是線性等式或不等式。因此仍可用單純形法和對偶單純形法進行分析參數(shù)線性規(guī)劃問題。習(xí)題一1．試將下述問題改寫成線性規(guī)劃問題：2．試將下列問題改寫成線性規(guī)劃問題：3．線性回歸是一種常用的數(shù)理統(tǒng)計方法，這個方法要求對圖上的一系列點選配一條合適的直線擬合。方法通常是先定直線方程為，然后按某種準則求定。通常這個準則為最小二乘法，但也可用其他準則。試根據(jù)以下準則建立這個問題的線性規(guī)劃模型：4．某廠生產(chǎn)三種產(chǎn)品=1\*ROMANI，=2\*ROMANII，=3\*ROMANIII。每種產(chǎn)品要經(jīng)過兩道工序加工。設(shè)該廠有兩種規(guī)格的設(shè)備能完成工序，它們以表示；有三種規(guī)格的設(shè)備能完成工序，它們以表示。產(chǎn)品=1\*ROMANI可在任何一種規(guī)格設(shè)備上加工。產(chǎn)品=2\*ROMANII可在任何規(guī)格的設(shè)備上加工，但完成工序時，只能在設(shè)備上加工；產(chǎn)品=3\*ROMANIII只能在與設(shè)備上加工。已知在各種機床設(shè)備的單件工時，原材料費，產(chǎn)品銷售價格，各種設(shè)備有效臺時以及滿負荷操作時機床設(shè)備的費用如下表，要求安排最優(yōu)的生產(chǎn)計劃，使該廠利潤最大。設(shè)備產(chǎn)品設(shè)備有效臺時滿負荷時的設(shè)備費用(元)=1\*ROMANI=2\*ROMANII=3\*ROMANIII5764710981211600010000400070004000300321250783200原料費(元/件)單價(元/件)0.251.250.352.000.502.805．有四個工人，要指派他們分別完成4項工作，每人做各項工作所消耗的時間如下表：工作工人甲乙丙丁15192619182317212122162324181917問指派哪個人去完成哪項工作，可使總的消耗時間為最??？6．某戰(zhàn)略轟炸機群奉命摧毀敵人軍事目標。已知該目標有四個要害部位，只要摧毀其中之一即可達到目的。為完成此項任務(wù)的汽油消耗量限制為48000升、重型炸彈48枚、輕型炸彈32枚。飛機攜帶重型炸彈時每升汽油可飛行2千米，帶輕型炸彈時每升汽油可飛行3千米。又知每架飛機每次只能裝載一枚炸彈，每出發(fā)轟炸一次除來回路程汽油消耗（空載時每升汽油可飛行4千米）外，起飛和降落每次各消耗100升。有關(guān)數(shù)據(jù)如表所示。要害部位離機場距離（千米）摧毀可能性每枚重型彈每枚輕型彈12344504805406000.100.200.150.250.080.160.120.20為了使摧毀敵方軍事目標的可能性最大，應(yīng)如何確定飛機轟炸的方案，要求建立這個問題的線性規(guī)劃模型。7．用Matlab求解下列線性規(guī)劃問題：s.t.8．用Matlab求解下列規(guī)劃問題：s.t.第二章整數(shù)規(guī)劃§1概論1.1定義規(guī)劃中的變量（部分或全部）限制為整數(shù)時，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。整數(shù)規(guī)劃的分類如不加特殊說明，一般指整數(shù)線性規(guī)劃。對于整數(shù)線性規(guī)劃模型大致可分為兩類：1o變量全限制為整數(shù)時，稱純（完全）整數(shù)規(guī)劃。2o變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。整數(shù)規(guī)劃特點（=1\*romani）原線性規(guī)劃有最優(yōu)解，當自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況：=1\*GB3①原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。=2\*GB3②整數(shù)規(guī)劃無可行解。例1原線性規(guī)劃為其最優(yōu)實數(shù)解為：。=3\*GB3③有可行解（當然就存在最優(yōu)解），但最優(yōu)解值變差。例2原線性規(guī)劃為其最優(yōu)實數(shù)解為：。若限制整數(shù)得：。（=2\*romanii）整數(shù)規(guī)劃最優(yōu)解不能按照實數(shù)最優(yōu)解簡單取整而獲得。1.3求解方法分類：（=1\*romani）分枝定界法—可求純或混合整數(shù)線性規(guī)劃。（=2\*romanii）割平面法—可求純或混合整數(shù)線性規(guī)劃。（=3\*romaniii）隱枚舉法—求解“0-1”整數(shù)規(guī)劃：=1\*GB3①過濾隱枚舉法；=2\*GB3②分枝隱枚舉法。（=4\*romaniv）匈牙利法—解決指派問題（“0-1”規(guī)劃特殊情形）。（=5\*romanv）蒙特卡洛法—求解各種類型規(guī)劃。下面將簡要介紹常用的幾種求解整數(shù)規(guī)劃的方法?！?分枝定界法對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的所有可行解空間恰當?shù)剡M行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復(fù)地分割為越來越小的子集，稱為分枝；并且對每個子集內(nèi)的解集計算一個目標下界（對于最小值問題），這稱為定界。在每次分枝后，凡是界限超出已知可行解集目標值的那些子集不再進一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。在本世紀六十年代初由LandDoig和Dakin等人提出的。由于這方法靈活且便于用計算機求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方法。目前已成功地應(yīng)用于求解生產(chǎn)進度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等。設(shè)有最大化的整數(shù)規(guī)劃問題，與它相應(yīng)的線性規(guī)劃為問題，從解問題開始，若其最優(yōu)解不符合的整數(shù)條件，那么的最優(yōu)目標函數(shù)必是的最優(yōu)目標函數(shù)的上界，記作；而的任意可行解的目標函數(shù)值將是的一個下界。分枝定界法就是將的可行域分成子區(qū)域的方法。逐步減小和增大，最終求到。現(xiàn)用下例來說明：例3求解下述整數(shù)規(guī)劃解（=1\*romani）先不考慮整數(shù)限制，即解相應(yīng)的線性規(guī)劃，得最優(yōu)解為：可見它不符合整數(shù)條件。這時是問題的最優(yōu)目標函數(shù)值的上界，記作。而顯然是問題的一個整數(shù)可行解，這時，是的一個下界，記作，即。（=2\*romanii）因為當前均為非整數(shù)，故不滿足整數(shù)要求，任選一個進行分枝。設(shè)選進行分枝，把可行集分成2個子集：，因為4與5之間無整數(shù)，故這兩個子集的整數(shù)解必與原可行集合整數(shù)解一致。這一步稱為分枝。這兩個子集的規(guī)劃及求解如下：問題：最優(yōu)解為：。問題：最優(yōu)解為：。再定界：。（=3\*romaniii）對問題再進行分枝得問題和，它們的最優(yōu)解為再定界：，并將剪枝。（=4\*romaniv）對問題再進行分枝得問題和，它們的最優(yōu)解為無可行解。將剪枝。于是可以斷定原問題的最優(yōu)解為：從以上解題過程可得用分枝定界法求解整數(shù)規(guī)劃（最大化）問題的步驟為：開始，將要求解的整數(shù)規(guī)劃問題稱為問題，將與它相應(yīng)的線性規(guī)劃問題稱為問題。（=1\*romani）解問題可能得到以下情況之一：（a）沒有可行解，這時也沒有可行解，則停止．（b）有最優(yōu)解，并符合問題的整數(shù)條件，的最優(yōu)解即為的最優(yōu)解，則停止。（c）有最優(yōu)解，但不符合問題的整數(shù)條件，記它的目標函數(shù)值為。（=2\*romanii）用觀察法找問題的一個整數(shù)可行解，一般可取，試探，求得其目標函數(shù)值，并記作。以表示問題的最優(yōu)目標函數(shù)值；這時有進行迭代。第一步：分枝，在的最優(yōu)解中任選一個不符合整數(shù)條件的變量，其值為，以表示小于的最大整數(shù)。構(gòu)造兩個約束條件和將這兩個約束條件，分別加入問題，求兩個后繼規(guī)劃問題和。不考慮整數(shù)條件求解這兩個后繼問題。定界，以每個后繼問題為一分枝標明求解的結(jié)果，與其它問題的解的結(jié)果中，找出最優(yōu)目標函數(shù)值最大者作為新的上界。從已符合整數(shù)條件的各分支中，找出目標函數(shù)值為最大者作為新的下界，若無作用不變。第二步：比較與剪枝，各分枝的最優(yōu)目標函數(shù)中若有小于者，則剪掉這枝，即以后不再考慮了。若大于，且不符合整數(shù)條件，則重復(fù)第一步驟。一直到最后得到為止。得最優(yōu)整數(shù)解?！?型整數(shù)規(guī)劃型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量僅取值0或1。這時稱為變量，或稱二進制變量。僅取值0或1這個條件可由下述約束條件：，整數(shù)所代替，是和一般整數(shù)規(guī)劃的約束條件形式一致的。在實際問題中，如果引入變量，就可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個問題中討論了。我們先介紹引入變量的實際問題，再研究解法。3.1引入變量的實際問題3.1.1投資場所的選定——相互排斥的計劃例4某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個位置（點）可供選擇。規(guī)定在東區(qū)。由三個點中至多選兩個；在西區(qū)。由兩個點中至少選一個；在南區(qū)，由兩個點中至少選一個。如選用點，設(shè)備投資估計為元，每年可獲利潤估計為元，但投資總額不能超過元。問應(yīng)選擇哪幾個點可使年利潤為最大？解題時先引入變量令.于是問題可列寫成：3.1.2相互排斥的約束條件有兩個相互排斥的約束條件或。為了統(tǒng)一在一個問題中，引入變量，則上述約束條件可改寫為：其中是充分大的數(shù)。約束條件或可改寫為如果有個互相排斥的約束條件：為了保證這個約束條件只有一個起作用，我們引入個變量和一個充分大的常數(shù)，而下面這一組個約束條件（1）（2）就合于上述的要求。這是因為，由于（2），個中只有一個能取0值，設(shè)，代入（1），就只有的約束條件起作用，而別的式子都是多余的。3.1.3關(guān)于固定費用的問題（FixedCostProblem）在討論線性規(guī)劃時，有些問題是要求使成本為最小。那時總設(shè)固定成本為常數(shù)，并在線性規(guī)劃的模型中不必明顯列出。但有些固定費用（固定成本）的問題不能用一般線性規(guī)劃來描述，但可改變?yōu)榛旌险麛?shù)規(guī)劃來解決，見下例。例5某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的生產(chǎn)方式投資高（選購自動化程度高的設(shè)備），由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動成本就降低；反之，如選定的生產(chǎn)方式投資低，將來分配到每件產(chǎn)品的變動成本可能增加。所以必須全面考慮。今設(shè)有三種方式可供選擇，令表示采用第種方式時的產(chǎn)量；表示采用第種方式時每件產(chǎn)品的變動成本；表示采用第種方式時的固定成本。為了說明成本的特點，暫不考慮其它約束條件。采用各種生產(chǎn)方式的總成本分別為.在構(gòu)成目標函數(shù)時，為了統(tǒng)一在一個問題中討論，現(xiàn)引入變量，令（3）于是目標函數(shù)（3）式這個規(guī)定可表為下述3個線性約束條件：（4）其中是一個充分小的正常數(shù)，是個充分大的正常數(shù)。（4）式說明，當時必須為1；當時只有為0時才有意義，所以（4）式完全可以代替（3）式。3.2型整數(shù)規(guī)劃解法之一（過濾隱枚舉法）解型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)規(guī)劃的情形一樣，就是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的個組合。對于變量個數(shù)較大（例如），這幾乎是不可能的。因此常設(shè)計一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法（ImplicitEnumeration），分枝定界法也是一種隱枚舉法。當然，對有些問題隱枚舉法并不適用，所以有時窮舉法還是必要的。下面舉例說明一種解型整數(shù)規(guī)劃的隱枚舉法。例6求解思路及改進措施：（=1\*romani）先試探性求一個可行解，易看出滿足約束條件，故為一個可行解，且。（=2\*romanii）因為是求極大值問題，故求最優(yōu)解時，凡是目標值的解不必檢驗是否滿足約束條件即可刪除，因它肯定不是最優(yōu)解，于是應(yīng)增加一個約束條件（目標值下界）：（=3\*romaniii）改進過濾條件。（=4\*romaniv）由于對每個組合首先計算目標值以驗證過濾條件，故應(yīng)優(yōu)先計算目標值大的組合，這樣可提前抬高過濾門檻，以減少計算量?！?蒙特卡洛法（隨機取樣法）前面介紹的常用的整數(shù)規(guī)劃求解方法，主要是針對線性整數(shù)規(guī)劃而言，而對于非線性整數(shù)規(guī)劃目前尚未有一種成熟而準確的求解方法，因為非線性規(guī)劃本身的通用