1、第五章 整數規劃1. 整數規劃模型2. 純整數規劃的割平面法3. 最優分配問題*(1.5,3.33)TX *(1,3)TX *(2,3)TX *(1,4)TX *(2,4)TX 四舍四舍五入五入原線性規劃規劃可行域原線性規劃規劃可行域整數規劃規劃可行域是什整數規劃規劃可行域是什么樣的？么樣的？如果有如果有60個變量，四舍五入的工作量有個變量，四舍五入的工作量有260次，計算機無法求解次，計算機無法求解IP，記為整數規劃4.1 整數規劃模型4.1 整數規劃模型硬約束，軟約束，書上硬約束，軟約束，書上135頁頁通過引入0，1變量，將非線性問題轉化為線性問題 作業： P204：1， 2，3（1），第

2、5題，第7題整數規劃建模（二）5.4最優分配問題最優分配問題B1Bj.BnaiA11Ai1.An1bj111看193頁di784118每行減每行減去去diuj每列減去每列減去uj( )( )( )( )( )( )( )( )( )( )( )( )5.2 純整數規劃的割平面法純整數規劃的割平面法 純整數規劃的算法本課程介紹兩類：純整數規劃的算法本課程介紹兩類： 割平面法割平面法 （基礎算法）（基礎算法） 分支定界法（實用算法）分支定界法（實用算法）1. 割平面法基本思想記（AIP）的可行域為KAIP。若將（AIP）中要求變量為整數這個約束去掉，則得到相應的線性規劃（LP），記（LP）的可行域

3、為KLP LP0最優解X1=（9/2,7/2）T第一次割平面后LP1最優解X2=（32/7,3）T第二次割平面后LP2最優解X3=（4,3）T總結思想總結思想2.如何尋找割平面-柯莫利割 （1）數學記號2217722372222227770 xxxx 2.如何尋找割平面-柯莫利割 （1）數學記號容易出錯22?722?7222222777 674P149頁，記號2.如何尋找割平面-柯莫利割2.如何尋找割平面-柯莫利割請看書150頁，然后回答問題。2.如何尋找割平面-柯莫利割如何在單純形表中找柯莫利割如何在單純形表中找柯莫利割注意：通常選擇非整數部注意：通常選擇非整數部分大的行來做割平面。分大的行

4、來做割平面。請同學做第二行的割平面。用什么方法求解TP?看書P154注意：篩掉的松弛變量只能是柯莫利割的松弛變量！P153 作業：204頁8（1）對柯莫利割的說明P155總結5.2 純整數規劃的算法純整數規劃的算法 純整數規劃的算法本課程介紹兩類：純整數規劃的算法本課程介紹兩類： 割平面法割平面法 分支定界法分支定界法 5.4 分支定界法 引例：某區舉行初中數學競賽，1#，2# ， 3#三個重點中學參加，三個學校分別派出3個，2個，2個重點班的同學參賽。現在已知各個集合內的最高分數、得分人姓名和性別情況，見圖。 問采用何種方法能夠得知參賽女同學中的最高分數？ 5.4 分支定界法還可以再分還可以

5、再分 方法一：全部枚舉 方法二：隱含枚舉 松弛問題Bi的求解有現成答案或者簡單算法。5.3.1 0-1背包問題背包問題 單位重量的價值最大的物品優先選取單位重量的價值最大的物品優先選取物品號xj重量價值1 #2 #3 #4 #5 #6 #7 #合計單位重量的價值最大的物品優先選取單位重量的價值最大的物品優先選取160頁最后一段，為什么求解比較容易？K是松弛問題的一棵樹。是松弛問題的一棵樹。單位重量的價值最大的物品優先選取單位重量的價值最大的物品優先選取物品號xj重量價值1 #02 #3 #4 #5 #6 #7 #合計單位重量的價值最大的物品優先選取單位重量的價值最大的物品優先選取物品號xj重量

6、價值1 #12 #3 #4 #5 #6 #7 #合計誰先進行分支？單位重量的價值最大的物品優先選取單位重量的價值最大的物品優先選取物品號xj重量價值1 #02 #3 #04 #5 #6 #7 #合計單位重量的價值最大的物品優先選取單位重量的價值最大的物品優先選取物品號xj重量價值1 #02 #3 #14 #5 #6 #7 #合計是是K0最優值的下界。對其他分支進行比較。最優值的下界。對其他分支進行比較。如為如為213還要繼續清查嗎？還要繼續清查嗎？ 作業：206頁10 樹，表格要畫整數規劃作業112312312312312331max1502201901500200018003218002200031600,1,2,320,1,2,30 11,2,3jjjjjjzxxxyyyxxxxxxxxxxMyjyxjyj且為整數， ， 5.4 分支定界法4.3.2 分支定界法分支定界法 12(4,)5T12(5,)7T1K2K問：問：-61是是K。 的上界還是下界？的上界還是下界？問：關系問：關系120120KKKKKK(4,2)T5(,3)2T35(,1)6T(5,1)T6(6,)7T7K是什么形狀？是什么形狀？6(6,)