解答運籌學整數(shù)規(guī)劃作業(yè)課件

4.1試利用0-1變量對下列各題分別表示成一般線性約束條件

x1+x2≤2或2x1+3x2≥5變量x只能取值0、3、5或7中的一個若x1≤2，則x2≥1，否則x2≤4以下四個約束條件中至少滿足兩個：

x1+x2≤5，x1≤2，x3≥2，x3+x4≥6

x1+x2≤2或2x1+3x2≥5b)變量x只能取值0、3、5或7中的一個若x1≤2，則x2≥1，否則x2≤4d)以下四個約束條件中至少滿足兩個：x1+x2≤5，x1≤2，x3≥2，x3+x4≥6試為該廠建立一個生產(chǎn)上述6種規(guī)格包裝箱各多少個的決策的數(shù)學模型，即滿足該廠對6種規(guī)格包裝箱的需求，又使總的費用為最小4.3某鉆井隊要從以下10個可供選擇的井位中確定5個鉆井探油，目的使總的鉆探費用最小。若10個井位代號為S1,S2，…S10，相應的鉆探費用為c1,c2,…,c10，并且井位的選擇上要滿足下列條件：或選擇S1和S7，或選擇鉆探S8選擇了S3或S4就不能選S5，或反過來也一樣在S2、S6、S9、S10中最多只能選兩個或選擇S1和S7，或選擇鉆探S8設(shè)選擇第sj個井位不選擇第sj個井位選擇了S3或S4就不能選S5，或反過來也一樣在S2、S6、S9、S10中最多只能選兩個第一步：找出效率矩陣每行的最小元素，并分別從每行中減去最小元素，有第二步：找出矩陣每列的最小元素，再分別從每列中減去，有

－2－2＋24.5已知下列五名運動員各種姿勢的游泳（各為50m）如表4.8所示。試問如何從中選拔一個4×50m混合泳的接力隊，使預期的比賽成績?yōu)樽詈萌硕嗍律?，添加虛擬的的“事”，對應系數(shù)矩陣為：標準形式，使用匈牙利法解之：第一步：找出效率矩陣每行的最小元素，并分別從每行中減去最小元素，有第二步：找出矩陣每列的最小元素，再分別從每列中減去，不變第三步：用最少的直線覆蓋所有“0”，得-1.6-1.6-1.6-1.6+1.6-0.9-0.9-0.9+0.9第四步：圈“0”4.6分配甲、乙、丙、丁四個人去完成A、B、C、D、E五項任務，每個人完成各項任務的時間如表4.9所示、由于任務數(shù)多于人數(shù)，故考慮：任務E必須完成，其他4項中可任選3項完成其中有一人完成兩項，其他每人完成一項試分別確定最優(yōu)分配方案，使完成任務的總時間最少-4-4-4+4+4-1-1+1其中有一人完成兩項，其他每人完成一項由于所有任務都必須由甲、乙、丙、丁完成，所以假想的人的效率應該對每項工作而言，都是完成它的最好的人，而不能假設(shè)為0值。所以構(gòu)造的效率矩陣為：-4-4-4＋4-1-1-1+14.8用分枝定界法求解下列整數(shù)規(guī)劃問題LPx1=3.5,x2=1.8Z(0)＝5.30x1≤3x1≥4LP1x1=3,x2=2Z(1)＝5LP2x1=4,x2=1.2Z(2)＝5.2x2≤1x2≥2LP3x1=4.17,x2=1Z(3)＝5.17LP4無可行解×x