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

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