1、.四、把下列線性規劃問題化成標準形式： 2、minZ=2x1-x2+2x3 五、按各題要求。建立線性規劃數學模型1、某工廠生產A、B、C三種產品，每種產品的原材料消耗量、機械臺時消耗量以及這些資源的限量，單位產品的利潤如下表所示：根據客戶訂貨，三種產品的最低月需要量分別為200，250和100件，最大月銷售量分別為250，280和120件。月銷售分別為250，280和120件。 問如何安排生產計劃，使總利潤最大。2、某建筑工地有一批長度為10米的相同型號的鋼筋，今要截成長度為3米的鋼筋90根，長度為4米的鋼筋60根，問怎樣下料，才能使所使用的原材料最省?1 某運輸公司在春運期間需要24小時晝夜

2、加班工作，需要的人員數量如下表所示： 起運時間 服務員數 26 610 10一14 1418 1822 222 4 8 10 7 12 4每個工作人員連續工作八小時，且在時段開始時上班，問如何安排，使得既滿足以上要求，又使上班人數最少?五、分別用圖解法和單純形法求解下列線性規劃問題并對照指出單純形迭代的每一步相當于圖解法可行域中的哪一個頂點。六、用單純形法求解下列線性規劃問題： 七、用大M法求解下列線性規劃問題。并指出問題的解屬于哪一類。 八、下表為用單純形法計算時某一步的表格。已知該線性規劃的目標函數為maxZ=5x1+3x2，約束形式為“”，X3，X4為松馳變量表中解代入目標函數后得Z=1

3、0XlX2X3X410b-1fgX32CO115Xlade01(1)求表中ag的值 (2)表中給出的解是否為最優解?（1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=5 （2） 表中給出的解為最優解 第四章 線性規劃的對偶理論五、寫出下列線性規劃問題的對偶問題1minZ=2x1+2x2+4x3 六、已知線性規劃問題 應用對偶理論證明該問題最優解的目標函數值不大于25七、已知線性規劃問題 maxZ=2x1+x2+5x3+6x4其對偶問題的最優解為Yl=4，Y2=1，試應用對偶問題的性質求原問題的最優解。七、用對偶單純形法求解下列線性規劃問題： 八、已知線性規劃問題 (1) 寫出其對偶

4、問題 (2)已知原問題最優解為X=(2，2，4，0)T，試根據對偶理論，直接求出對偶問題的最優解。 W* = 16第七章 整數規劃一、填空題1用分枝定界法求極大化的整數規劃問題時，任何一個可行解的目標函數值是該問題目標函數值的下界。2在分枝定界法中，若選Xr=43進行分支，則構造的約束條件應為X11，X12。3已知整數規劃問題P0，其相應的松馳問題記為P0，若問題P0無可行解，則問題P。無可行解。4在0 - 1整數規劃中變量的取值可能是_0或1。5對于一個有n項任務需要有n個人去完成的分配問題，其 解中取值為1的變量數為n個。6分枝定界法和割平面法的基礎都是用_線性規劃方法求解整數規劃。7若在

5、對某整數規劃問題的松馳問題進行求解時，得到最優單純形表中，由X。所在行得X1+17x3+27x5=137，則以X1行為源行的割平面方程為_X3X50_。8在用割平面法求解整數規劃問題時，要求全部變量必須都為整數。9用割平面法求解整數規劃問題時，若某個約束條件中有不為整數的系數，則需在該約束兩端擴大適當倍數，將全部系數化為整數。10求解純整數規劃的方法是割平面法。求解混合整數規劃的方法是分枝定界法_。11求解01整數規劃的方法是隱枚舉法。求解分配問題的專門方法是匈牙利法。 12在應用匈牙利法求解分配問題時，最終求得的分配元應是獨立零元素_。13.分枝定界法一般每次分枝數量為2個.二、單選題 1整

6、數規劃問題中，變量的取值可能是D。A整數B0或1C大于零的非整數D以上三種都可能 2在下列整數規劃問題中，分枝定界法和割平面法都可以采用的是A 。A純整數規劃B混合整數規劃C01規劃D線性規劃 3下列方法中用于求解分配問題的是D_。A單純形表B分枝定界法C表上作業法D匈牙利法三、多項選擇1下列說明不正確的是ABC。A求解整數規劃可以采用求解其相應的松馳問題，然后對其非整數值的解四舍五入的方法得到整數解。B用分枝定界法求解一個極大化的整數規劃問題，當得到多于一個可行解時，通常任取其中一個作為下界。C用割平面法求解整數規劃時，構造的割平面可能割去一些不屬于最優解的整數解。D用割平面法求解整數規劃問

7、題時，必須首先將原問題的非整數的約束系數及右端常數化為整數。2在求解整數規劃問題時，可能出現的是ABC。A唯一最優解B無可行解 C多重最佳解D無窮多個最優解3關于分配問題的下列說法正確的是_ ABD。A分配問題是一個高度退化的運輸問題B可以用表上作業法求解分配問題 C從分配問題的效益矩陣中逐行取其最小元素，可得到最優分配方案D匈牙利法所能求解的分配問題，要求規定一個人只能完成一件工作，同時一件工作也只給一個人做。4.整數規劃類型包括（ CDE ）A 線性規劃 B 非線性規劃 C 純整數規劃 D 混合整數規劃 E 01規劃5.對于某一整數規劃可能涉及到的解題內容為（ ABCDE ）A 求其松弛問

8、題 B 在其松弛問題中增加一個約束方程 C 應用單形或圖解法D 割去部分非整數解 E多次切割三、名詞1、純整數規劃：如果要求所有的決策變量都取整數，這樣的問題成為純整數規劃問題。2、01規劃問題：在線性規劃問題中，如果要求所有的決策變量只能取0或1，這樣的問題稱為01規劃。3、混合整數規劃：在線性規劃問題中，如果要求部分決策變量取整數，則稱該問題為混合整數規劃。四、用分枝定界法求解下列整數規劃問題：(提示:可采用圖解法) maxZ=40x1+90x2 五、用割平面法求解 六、下列整數規劃問題 說明能否用先求解相應的線性規劃問題然后四舍五入的辦法來求得該整數規劃的一個可行解。答：不考慮整數約束，

9、求解相應線性規劃得最優解為 x1=10/3，x2=x3=0，用四舍五人法時，令x1=3，x2=x3=0，其中第2個約束無法滿足，故不可行。七、若某鉆井隊要從以下10個可供選擇的井位中確定5個鉆井探油。使總的鉆探費用為最小。若10個井位的代號為S1,S2，S10相應的鉆探費用為C1 ,C2 , C10，并且井位選擇要滿足下列限制條件： (1)在s1，s2，S4中至多只能選擇兩個； (2)在S5，s6中至少選擇一個；(3)在s3，s6，S7，S8中至少選擇兩個； 試建立這個問題的整數規劃模型八、有四項工作要甲、乙、丙、丁四個人去完成每項工作只允許一人去完成。每個人只完成其中一項工作，已知每個人完成

10、各項工作的時間如下表。問應指派每個人完成哪項工作，使總的消耗時間最少?工作 人 I 甲乙丙丁151961918237212l22162324181917 第二章 線性規劃問題的基本概念3、本章典型例題分析例： 用單純形法求解 解：先化為標準形式： 把標準形的系數列成一個表基SX1X2X3X4解S1-20-15000X302310600X402101400第一次迭代：調入x1,調出x4基SX1X2X3X4解S10-50104000X30021-1200X1011/201/2200第二次迭代：調入x2,調出x3基SX1X2X3X4解S1005/215/24500X20011/2-1/2100X10

11、10-1/43/4150 4、本章作業見本章練習題3、本章典型例題分析例：寫出下列線性規劃問題的對偶問題解：其對偶問題為：4、本章作業見本章練習題二、寫出下列線性規劃問題的對偶問題：s.t.（1） s.t.（2） 管理運籌學復習一、 考慮下列線性規劃（20分）MaxZ=2X1+3X22X1+ 2X2+X3=12X1+2X2 +X4=84X1 +X5=164X2 +X6=12Xj0（j=1,2,6）其最優單純形表如下：基變量X1X2X3X4X5X6X30001-1-1/40X1410001/40X64000-21/21X220101/2-1/80j000-3/2-1/801） 當C2=5時，求新

12、的最優解2） 當b3=4時，求新的最優解3） 當增加一個約束條件2X1+X212，問最優解是否發生變化，如果發生變化求新解？解當C2=5時4=5/25=1/80所以最優解發生變化基變量X1X2X3X4X5X60X30001-1-1/402X1410001/400X64000-21/215X220101/2-1/80j000-5/21/800X32001201/22X1210010-1/20X58000-4125X23010001/4j000-20-1/4最優解為X1=2，X2=3,Z192）當b3=4時基變量X1X2X3X4X5X60X33001-1-1/402X1110001/400X6-3000-21/213X25/20101/2-1/80j000-3/2-1/800X39/20010-1/212X1110001/400X43/20001-1/4-1/23X27/4010001/4j0000-1/2-3/4此時最優解為X1=1，X2=7/4,Z29/43)增加一個約束條