變量取整數的規劃稱為整數規劃.所有變量都取整數的規劃稱為純整數規劃，部分變量取整數的規劃稱為混合整數規劃.在線性規劃問題中，如果所有的變量都隻能取值0或1.這樣的線性規劃問題稱為（純）0—1整數規劃問題.如果一個線性規劃問題中，有的變量是連續變量，而另一些變量是0—1變量，這樣的問題稱為混合0—1規劃問題.
1. 背包問題
例4一隻背包最大裝載重量為50公斤.現有三種物品，每種物品數量無限.每種物品每件的重量、價值如下表所示：
表54
物品1物品2物品3
重量（公斤/件）104120
價值（元/件）177235
要在背包中裝入這三種物品各多少件，使背包中的物品價值最高.
設裝入物品1，物品2和物品3各為x1，x2，x3件，由於物品的件數必須是整數，因此背包問題的線性規劃模型是一個整數規劃問題：
maxz=17x1+72x2+35x3〖1〗
s.t.10x1+41x2+20x3≤50
x1,x2,x3≥0,x1,x2,x3是整數
這個問題的最優解是：x1=1件,x2=0件,x3=2件,最高價值為：z=87元.
例5一個登山隊員，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相器材、通信器材等.每種物品的重量和重要性係數如表所示.設登山隊員可攜帶的最大重量為25kg,試選擇該隊員所應攜帶的物品.
表55
序號1234567
物品食品氧氣冰鎬繩索帳篷照相器材通信設備
重量/kg55261224
重要性係數201518148410
解：引入0—1變量xi,xi=1表示應攜帶物品i，xi=0表示不應攜帶物品I，i=1,2,…,7
maxz=20x1+15x2+18x3+14x4+8x5+4x6+10x7
5x1+5x2+2x3+6x4+12x5+2x6+4x7≤25
xi=0或1,i=1,2,…,7
比較每種物品的重要性係數和重量的比值，比值大的物品首先選取，直到達到重量限製，上述問題就是一個標準的整數規劃問題，由分枝定界法，解得：X=（x1，x2，x3，x4，x5，x6，x7）=（1,1,1,1,0,1,1），Z=81