運籌學(xué)習題解答（chap4 整數(shù)規(guī)劃與分配問題）

1、第四章 整數(shù)規(guī)劃與分配問題一、建立下列問題的數(shù)學(xué)模型1、P143, 4.1 利用01變量對下列各題分別表示成一般線性約束條件(a) 或；(b) 取值0,3,5,7中的一個；(c) 變量或等于0，或；(d) 若，則，否則；(e) 以下四個約束條件中至少滿足兩個：。解：(a) 設(shè)（i=1,2）,M為任意大正數(shù)。則有 (b) 設(shè)，則原條件可表示為 (c) 設(shè)，則原條件可表示為 (d)（i=1,2）,M為任意大正數(shù)。 則有(e)設(shè)，則原條件可表示為：2、P143, 4.2 某鉆井隊要從以下10個可供選擇的井位確定5個鉆井探油，目的是使得總的鉆探費用最小。若10個井位代號為，相應(yīng)的鉆探費用為，并且井位的

2、選擇要滿足下列條件：（1）或選擇和，或選擇；（2）選擇了或就不能選擇，反過來也一樣；（3）在中最多只能選兩個。請建立該問題的數(shù)學(xué)模型。解：設(shè)，則 目標函數(shù)是： 約束條件： 3、P145, 4.10 東方大學(xué)計算機實驗室聘用4名大學(xué)生（代號1,2,3,4）和2名研究生（代號5,6）值班。已知各學(xué)生從周一至周五每天可安排的值班時間及每人每小時報酬見下表所示。學(xué)生代號酬金(元/h)每天可安排的值班時間(h)周一周二周三周四周五110.060607210.00606339.94830549.855640510.830460611.306244實驗室每天開放時間為8:00AM10:00PM,共14小時。

3、開放時間內(nèi)需要有一名學(xué)生值班。規(guī)定大學(xué)生每周值班時間是815小時，研究生是712小時，每次值班不小于2小時。又每名學(xué)生每周值班次數(shù)不得多于三次，每天值班人員中至少有一名研究生，每天值班人數(shù)不超過3人。試為該實驗室安排一張人員值班表，使得總酬金支出為最少。請建立該問題的數(shù)學(xué)模型。解：設(shè) 表示學(xué)生i在周j的值班時間。表示學(xué)生i在周j的最多可值班時間。則目標函數(shù)： 每天開放14小時 大學(xué)生值班8-15小時 研究生值班7-12小時 每周不超過3次 每天不超過3人 每天有一研究生 值班不超過每人可安排的時間 為0-1變量。4、P147, 4.15 需生產(chǎn)2000件某種產(chǎn)品，該種產(chǎn)品可利用A，B，C，D設(shè)

4、備中的任意一種加工，已知每種設(shè)備的生產(chǎn)準備結(jié)束費用，產(chǎn)品的單件成本，每種設(shè)備限定的最大加工數(shù)量如下表所示。請建立使得生產(chǎn)總成本最小的優(yōu)化模型。設(shè)備準備結(jié)束費用（元）生產(chǎn)成本（元/件）生產(chǎn)能力（件）A100020900B980241000C800161200D700281600解：設(shè)在A，B，C，D上加工的產(chǎn)品數(shù)量分別為。，建立模型如下：二、求解下列指派問題1、P143, 4.3（a）某指派問題的效率矩陣如下，請用匈牙利法求最優(yōu)解。解： 所以最優(yōu)解為取值為1，其他為0。最優(yōu)效率21。2、P143, 4.3（a）某指派問題的效率矩陣如下，請用匈牙利法求最優(yōu)解。解： 所以最優(yōu)指派為：，其余均為0，最

5、有效率是12。3、 已知下列五名運動員各種泳姿的50米游泳成績?nèi)缦卤?單位：秒)，請從中選拔出一個450m的混合泳接力隊，使預(yù)期比賽成績?yōu)樽詈?。趙錢張王周仰泳3732383735蛙泳4333423441蝶泳3328383033自由泳2926292831 解：用匈牙利法求解如下：所以最優(yōu)解為，其余均為0，即仰泳-周，蛙泳-王，蝶泳-錢，自由泳-趙，張落選。最好成績是35+34+29+28=126秒。-13分4、P144, 4.6 分配甲、乙、丙、丁去完成A、B、C、D、E五項任務(wù)，每人完成任務(wù)所需的時間（單位：小時）如下表所示?，F(xiàn)要求任務(wù)E必須完成，其它4項可任選3項完成；試確定最優(yōu)分配方案，使得完成任務(wù)的總時間最少。ABCDE甲2529314237乙393