数学建模案例作业
作业1 商人过河问题
三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行（六个人都会划船）。随从们密谋，无论何时，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的决定权掌握在商人手中。商人们怎样才能安全渡河？
示意图如下： 随从：
商人： 一、状态变量
一次决策S k =(x k , y k ) k =1, 2, 3 表示第k 次渡河时，此岸的商人数，随从数. 最初 S 0=(3, 3) (0≤x k , y k ≤3且为整数）
S ={(3, 3), (3, 2), (3, 1), (3, 0), (2, 3), (2, 2), (2, 1), (2, 0), (1, 3), (1, 2), (1, 1), (1, 0), (0, 3), (0, 2), (0, 1), (0, 0)}
要安全过河，需保证彼岸此岸都安全，及随从数不能大于商人数，所以安全的情况有10种，即S ={(3, 3), (3, 2), (3, 1), (3, 0), (2, 2), (1, 1), (0, 3), (0, 2), (0, 1), (0, 0)}② 二、决策变量
设d k =(u k , v k ) (0≤u k , v k ≤2且1≤u k +v k ≤2) 表示第k 次渡河时，船上的商人数和随从数 D ={(2, 0), (1, 1), (0, 2), (1, 0), (0, 1)}
与状态变量相结合，安全的情况有三种，即 D ={((1, 1), (0, 2), (0, 1)}③ 三、状态转移方程
奇数次（此案到彼岸）S k +1=S k -d k 偶数次（彼岸到此案）S k +1=S k +d k 即S k +1=S k +(-1) k d k ① 数学建模：
由①确定的转移方程下，经过n 次决策，将初始状态转移到最终状态S n =(0, 0) . 每次的决策取自③式，每次到达的状态在②中. 图解法：
①从右上角移到左下角，每次最多移两步；
②奇数次渡河往左下方，偶数次渡河往右下方。 建立平面直角坐标系如图：
S n 过河方案：从A 点S 0=(3, 3) 出发到D 点S n =(0, 0) 结束
① 小船一次最多能载两人，所以每次最多移动两个格子
② 由此岸即彼岸时人员减少，即奇数遍时向左下方行走；有彼岸及此岸时人员增加，即偶
数遍时向右上方行走。 第一步：从A 点S 0=(3, 3) 到C 点S c =(3, 1) , 即小船载着两个随从去彼岸； 第二步：从C 点Sc =(3, 1) 到B 点Sb =(3, 2) ，即一个随从划船回到此岸； 第三步：从B 点Sb =(3, 2) 到D 点Sd =(3, 0) , 即小船载着两个随从去彼岸； 第四步：从D 点Sd =(3, 0) 到C 点Sc =(3, 1) ，即一个随从划船回到此岸； 第五步：从C 点Sc =(3, 1) 到F 点Sf =(1, 1) , 即小船载着两个商人去彼岸；
第六步：从F 点Sf =(1, 1) 到E 点Se =(2, 2) ，即小船载着一个随从一个商人回到此岸； 第七步：从E 点Se =(2, 2) 到I 点Si =(0, 2) , 即小船载着两个商人去彼岸； 第八步：从I 点Si =(0, 2) 到H 点Sh =(0, 3) ，即小船载着一个商人回到此岸； 第九步：从H 点Sh =(0, 3) 到G 点Sh =(0, 1) ，即小船载着两个商人到彼岸； 第十步：从G 点Sh =(0, 1) 到I 点Si =(0, 2) ，即小船载着一个商人到此岸； 第十一步：从I 点Si =(0, 2) 到O 点Si =(0, 0) ，即所有人都到了彼岸。
编程：
#include
void show(int s) {
printf("{m:%d, s:%d} %s {m:%d, s:%d}\n",
(s>>4)&3, (s>>1)&3, (s&1? "~!":"!~"),(s>>10)&3, (s>>7)&3); }
int search(int * ss, int es) {
const int m[] = {0x7E , 0xFC , 0x3F0, 0x7E0, 0x46E }; static char f[0x40]; int s, c, t, i;
if (*ss == es) return 1; f[*ss & 0x3F ] = 1;
for (i = 0; i
t = s = *ss + (*ss & 1 ? -m[i] : m[i]) ^ 1; if ((t & 0x1248) != 0x1248) continue ;
t |= ((s >> 4 & 3) ? 0 : 0x30) | ((s >> 10 & 3) ? 0 : 0xC00); if (((t - ((t & 0x186)
c = search(ss + 1, es);
if (c > 0){ f[*ss & 0x3F ] = 0; return c + 1;} }
f[*ss & 0x3F ] = 0; return 0; } int main() {
int ss[16] = {0x127E }, es = 0x1FC9, c, i;
c = search(ss, es);
for (i = 0; i
作业2 椅子的不平的地面上能够放平吗？ 假设1：椅子腿的长是一样的，只考虑地面不平。不妨设椅子有4条腿与地面有4个接触点，
4个点的连线组成一个长方形（其余情况类似）
假设2：地面虽然是不平的，但没有台阶，地面的高度是连续起伏变化的，将地面看作一张连续曲面。
假设3：椅子的高度相对地面是连续的，椅子在地面上放稳与否至少有3条腿着地。 注：稳
条腿着地与地面距离“0”
计算与地面的4个距离
数学建模：
设椅子与地面的接触点为A,B,C,D ，4点连线组成一个长方形，如图建立坐标系。
①4②A,B,C,D4个距离中有一个不为“0”
将椅子绕原点旋转θ角，A,B,C,D →A',B',C',D'. 不同的角度θ，代表了椅子在地面上不同的位置，相应的椅子腿与地面的距离都是θ的函数. 问题：是否存在一个角θ，当将椅子旋转θ角后，对应的4个腿与地面的距离都是0.
设f (θ) 表示将椅子旋转θ角后，A,C 两点与地面的距离之和. g (θ) 表示将椅子旋转θ角后，B,D 两点与地面的距离之和. 由假设3，对任意θ，都有f (θ) g (θ) =0
由假设2，f (θ) ，g (θ) 都是θ的连续函数，θ∈[0, 2π]
不妨设f (0) =0(A.C两点着地) ，则g (0) >0（B.D 两点中有一点不着地）
模型：设f (θ), g (θ) 都是θ∈[0, 2π]的连续函数，满足对任意θ∈[0, 2π]都有f (θ) g (θ) =0 且f (0) =0，g (0) >0
求证：存在一个θ∈[0, 2π]，使得f (θ) =g (θ) =0
证明：令F (θ) =f (θ) -g (θ) ，其中f (θ) ，g (θ) 在[0, 2π]连续 ∵F (0) =f (0) -g (0)
将椅子旋转π，F (π) =g (0) -f (0) >0 ∴F (0) F (π)
由零点定理，至少存在一点θ∈(0, π) ，使得F (θ) =0 又∵f (θ) g (θ) =0，∴f (θ) =g (θ) =0
作业3 线性规划问题
加工奶制品的生产计划 1桶牛奶：
方案①12小时，生产3公斤A 1，获利24元/公斤
方案②8小时，生产4公斤A 2，获利16元/公斤
每天：50桶牛奶，时间480小时，至多加工100公斤A 1 制订生产计划，使每天获利最大.
·35元可买到1桶牛奶，买吗？若买，每天最多买多少？ ·可聘用临时工人，付出的工资最多是每小时几元？ ·A 1的获利增加到30元/ 公斤，应否改变生产计划？
利润仅与售出奶制品A 1，A 2的数量有关. 设每天用X 1，X 2桶牛奶生产A 1，A 2 . Z=72X1+64X2 ② ⎧x 1+x 2≤50⎪
⎪12x 1+8x 2≤480
① ⎨
3x ≤100⎪1⎪⎩x 1, x 2≥0
数学建模： max 72x1+64x2 st
2) x1+x2
程序运行结果截图：
作业4 最有解问题
甲乙丙丁四人将一份中文说明书译成英、日、德、俄四种文字，分别记作A,B,C,D 。他们将中文说明书译成不同语言所需时间如下表。每人能且仅能翻译一种文字，
每种文字能且
仅能由一人去翻译。如何分派任务，可使总时间最小？
解：
⎛215134⎫ ⎪1041415 ⎪A =
9141613⎪ ⎪ 78119⎪⎝⎭
从矩阵A 中取出4个数之和达到最小，每行每列能取仅能取1个. 所有元素的和，每个元素之前乘上1个0-1变量 ⎧0
x ij =⎨（1表示安排第i 人完成第j 项工作，否则为0）
⎩1
数学建模： min Z =
∑∑a
i =1j =1
44
ij x ij =2x 11+15x 12+ +9x 44
⎧x 11+x 12+x 13+x 14=1⎪
⎪x 21+x 22+x 23+x 24=1⎪x 31+x 32+x 33+x 34=1⎪
⎪x 41+x 42+x 43+x 44=1⎪
st ⎨x 11+x 21+x 31+x 41=1 ⎪x +x +x +x =1
223242
⎪12
⎪x 13+x 23+x 33+x 43=1⎪
⎪x 14+x 24+x 34+x 44=1⎪x ij =0or 1, i , j =1, 2, 3, 4⎩
int 20
程序运行结果截图：
匈牙利算法：（相对概念） ⎛215134⎫
⎪1041415 ⎪A =
9141613⎪ ⎪ 78119⎪⎝⎭
定理1:把一个指派问题的效应矩形A 中的每行（列）元素减去一个数，得到一个新的效益矩阵B ，则A 与B 对应的指派问题有相同的最优解
定理2：B 中位于不同的行（列）的“0”元素的个数等于用直线将B 中的所有“0”元素划去（平行、铅直）
所有的直线的最少的条数
⎛013112⎫ ⎪ 601011⎪
对行各减去行的最小值，A = 可见，前两列划去，后两列没有0. 对列各减
0574⎪ ⎪ 0142⎪⎝⎭ ⎛01370⎫
⎪6069 ⎪
去列的最小值，A = 先划去第一列，再划去第二列，第三列同时划去第四行，
0532⎪ ⎪ 0100⎪⎝⎭
第四列同时划去第一行取x 14=x 22=x 31=x 43=1 即甲→D ，乙→B ，丙→A ，丁→C.
⎛21097⎫ ⎪ 154148⎪A ' =
13141611⎪ ⎪ 415139⎪⎝⎭每一行减去每行的最小值 ⎛0 11A ' =
2 0⎝⎛0 11A ' =
2 0⎝⎛0 11A ' =
2 0⎝
875⎫
⎪
0104⎪350⎪
⎪
1195⎪⎭每一列减去每列的最小值 8031180311
250403025⎫⎪4⎪0⎪⎪5⎪⎭3⎫⎪2⎪0⎪⎪3⎪⎭
第一、三、四行同时减去2，同时，第一、二列同时加上2.
数学建模案例作业
作业1 商人过河问题
三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行（六个人都会划船）。随从们密谋，无论何时，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的决定权掌握在商人手中。商人们怎样才能安全渡河？
示意图如下： 随从：
商人： 一、状态变量
一次决策S k =(x k , y k ) k =1, 2, 3 表示第k 次渡河时，此岸的商人数，随从数. 最初 S 0=(3, 3) (0≤x k , y k ≤3且为整数）
S ={(3, 3), (3, 2), (3, 1), (3, 0), (2, 3), (2, 2), (2, 1), (2, 0), (1, 3), (1, 2), (1, 1), (1, 0), (0, 3), (0, 2), (0, 1), (0, 0)}
要安全过河，需保证彼岸此岸都安全，及随从数不能大于商人数，所以安全的情况有10种，即S ={(3, 3), (3, 2), (3, 1), (3, 0), (2, 2), (1, 1), (0, 3), (0, 2), (0, 1), (0, 0)}② 二、决策变量
设d k =(u k , v k ) (0≤u k , v k ≤2且1≤u k +v k ≤2) 表示第k 次渡河时，船上的商人数和随从数 D ={(2, 0), (1, 1), (0, 2), (1, 0), (0, 1)}
与状态变量相结合，安全的情况有三种，即 D ={((1, 1), (0, 2), (0, 1)}③ 三、状态转移方程
奇数次（此案到彼岸）S k +1=S k -d k 偶数次（彼岸到此案）S k +1=S k +d k 即S k +1=S k +(-1) k d k ① 数学建模：
由①确定的转移方程下，经过n 次决策，将初始状态转移到最终状态S n =(0, 0) . 每次的决策取自③式，每次到达的状态在②中. 图解法：
①从右上角移到左下角，每次最多移两步；
②奇数次渡河往左下方，偶数次渡河往右下方。 建立平面直角坐标系如图：
S n 过河方案：从A 点S 0=(3, 3) 出发到D 点S n =(0, 0) 结束
① 小船一次最多能载两人，所以每次最多移动两个格子
② 由此岸即彼岸时人员减少，即奇数遍时向左下方行走；有彼岸及此岸时人员增加，即偶
数遍时向右上方行走。 第一步：从A 点S 0=(3, 3) 到C 点S c =(3, 1) , 即小船载着两个随从去彼岸； 第二步：从C 点Sc =(3, 1) 到B 点Sb =(3, 2) ，即一个随从划船回到此岸； 第三步：从B 点Sb =(3, 2) 到D 点Sd =(3, 0) , 即小船载着两个随从去彼岸； 第四步：从D 点Sd =(3, 0) 到C 点Sc =(3, 1) ，即一个随从划船回到此岸； 第五步：从C 点Sc =(3, 1) 到F 点Sf =(1, 1) , 即小船载着两个商人去彼岸；
第六步：从F 点Sf =(1, 1) 到E 点Se =(2, 2) ，即小船载着一个随从一个商人回到此岸； 第七步：从E 点Se =(2, 2) 到I 点Si =(0, 2) , 即小船载着两个商人去彼岸； 第八步：从I 点Si =(0, 2) 到H 点Sh =(0, 3) ，即小船载着一个商人回到此岸； 第九步：从H 点Sh =(0, 3) 到G 点Sh =(0, 1) ，即小船载着两个商人到彼岸； 第十步：从G 点Sh =(0, 1) 到I 点Si =(0, 2) ，即小船载着一个商人到此岸； 第十一步：从I 点Si =(0, 2) 到O 点Si =(0, 0) ，即所有人都到了彼岸。
编程：
#include
void show(int s) {
printf("{m:%d, s:%d} %s {m:%d, s:%d}\n",
(s>>4)&3, (s>>1)&3, (s&1? "~!":"!~"),(s>>10)&3, (s>>7)&3); }
int search(int * ss, int es) {
const int m[] = {0x7E , 0xFC , 0x3F0, 0x7E0, 0x46E }; static char f[0x40]; int s, c, t, i;
if (*ss == es) return 1; f[*ss & 0x3F ] = 1;
for (i = 0; i
t = s = *ss + (*ss & 1 ? -m[i] : m[i]) ^ 1; if ((t & 0x1248) != 0x1248) continue ;
t |= ((s >> 4 & 3) ? 0 : 0x30) | ((s >> 10 & 3) ? 0 : 0xC00); if (((t - ((t & 0x186)
c = search(ss + 1, es);
if (c > 0){ f[*ss & 0x3F ] = 0; return c + 1;} }
f[*ss & 0x3F ] = 0; return 0; } int main() {
int ss[16] = {0x127E }, es = 0x1FC9, c, i;
c = search(ss, es);
for (i = 0; i
作业2 椅子的不平的地面上能够放平吗？ 假设1：椅子腿的长是一样的，只考虑地面不平。不妨设椅子有4条腿与地面有4个接触点，
4个点的连线组成一个长方形（其余情况类似）
假设2：地面虽然是不平的，但没有台阶，地面的高度是连续起伏变化的，将地面看作一张连续曲面。
假设3：椅子的高度相对地面是连续的，椅子在地面上放稳与否至少有3条腿着地。 注：稳
条腿着地与地面距离“0”
计算与地面的4个距离
数学建模：
设椅子与地面的接触点为A,B,C,D ，4点连线组成一个长方形，如图建立坐标系。
①4②A,B,C,D4个距离中有一个不为“0”
将椅子绕原点旋转θ角，A,B,C,D →A',B',C',D'. 不同的角度θ，代表了椅子在地面上不同的位置，相应的椅子腿与地面的距离都是θ的函数. 问题：是否存在一个角θ，当将椅子旋转θ角后，对应的4个腿与地面的距离都是0.
设f (θ) 表示将椅子旋转θ角后，A,C 两点与地面的距离之和. g (θ) 表示将椅子旋转θ角后，B,D 两点与地面的距离之和. 由假设3，对任意θ，都有f (θ) g (θ) =0
由假设2，f (θ) ，g (θ) 都是θ的连续函数，θ∈[0, 2π]
不妨设f (0) =0(A.C两点着地) ，则g (0) >0（B.D 两点中有一点不着地）
模型：设f (θ), g (θ) 都是θ∈[0, 2π]的连续函数，满足对任意θ∈[0, 2π]都有f (θ) g (θ) =0 且f (0) =0，g (0) >0
求证：存在一个θ∈[0, 2π]，使得f (θ) =g (θ) =0
证明：令F (θ) =f (θ) -g (θ) ，其中f (θ) ，g (θ) 在[0, 2π]连续 ∵F (0) =f (0) -g (0)
将椅子旋转π，F (π) =g (0) -f (0) >0 ∴F (0) F (π)
由零点定理，至少存在一点θ∈(0, π) ，使得F (θ) =0 又∵f (θ) g (θ) =0，∴f (θ) =g (θ) =0
作业3 线性规划问题
加工奶制品的生产计划 1桶牛奶：
方案①12小时，生产3公斤A 1，获利24元/公斤
方案②8小时，生产4公斤A 2，获利16元/公斤
每天：50桶牛奶，时间480小时，至多加工100公斤A 1 制订生产计划，使每天获利最大.
·35元可买到1桶牛奶，买吗？若买，每天最多买多少？ ·可聘用临时工人，付出的工资最多是每小时几元？ ·A 1的获利增加到30元/ 公斤，应否改变生产计划？
利润仅与售出奶制品A 1，A 2的数量有关. 设每天用X 1，X 2桶牛奶生产A 1，A 2 . Z=72X1+64X2 ② ⎧x 1+x 2≤50⎪
⎪12x 1+8x 2≤480
① ⎨
3x ≤100⎪1⎪⎩x 1, x 2≥0
数学建模： max 72x1+64x2 st
2) x1+x2
程序运行结果截图：
作业4 最有解问题
甲乙丙丁四人将一份中文说明书译成英、日、德、俄四种文字，分别记作A,B,C,D 。他们将中文说明书译成不同语言所需时间如下表。每人能且仅能翻译一种文字，
每种文字能且
仅能由一人去翻译。如何分派任务，可使总时间最小？
解：
⎛215134⎫ ⎪1041415 ⎪A =
9141613⎪ ⎪ 78119⎪⎝⎭
从矩阵A 中取出4个数之和达到最小，每行每列能取仅能取1个. 所有元素的和，每个元素之前乘上1个0-1变量 ⎧0
x ij =⎨（1表示安排第i 人完成第j 项工作，否则为0）
⎩1
数学建模： min Z =
∑∑a
i =1j =1
44
ij x ij =2x 11+15x 12+ +9x 44
⎧x 11+x 12+x 13+x 14=1⎪
⎪x 21+x 22+x 23+x 24=1⎪x 31+x 32+x 33+x 34=1⎪
⎪x 41+x 42+x 43+x 44=1⎪
st ⎨x 11+x 21+x 31+x 41=1 ⎪x +x +x +x =1
223242
⎪12
⎪x 13+x 23+x 33+x 43=1⎪
⎪x 14+x 24+x 34+x 44=1⎪x ij =0or 1, i , j =1, 2, 3, 4⎩
int 20
程序运行结果截图：
匈牙利算法：（相对概念） ⎛215134⎫
⎪1041415 ⎪A =
9141613⎪ ⎪ 78119⎪⎝⎭
定理1:把一个指派问题的效应矩形A 中的每行（列）元素减去一个数，得到一个新的效益矩阵B ，则A 与B 对应的指派问题有相同的最优解
定理2：B 中位于不同的行（列）的“0”元素的个数等于用直线将B 中的所有“0”元素划去（平行、铅直）
所有的直线的最少的条数
⎛013112⎫ ⎪ 601011⎪
对行各减去行的最小值，A = 可见，前两列划去，后两列没有0. 对列各减
0574⎪ ⎪ 0142⎪⎝⎭ ⎛01370⎫
⎪6069 ⎪
去列的最小值，A = 先划去第一列，再划去第二列，第三列同时划去第四行，
0532⎪ ⎪ 0100⎪⎝⎭
第四列同时划去第一行取x 14=x 22=x 31=x 43=1 即甲→D ，乙→B ，丙→A ，丁→C.
⎛21097⎫ ⎪ 154148⎪A ' =
13141611⎪ ⎪ 415139⎪⎝⎭每一行减去每行的最小值 ⎛0 11A ' =
2 0⎝⎛0 11A ' =
2 0⎝⎛0 11A ' =
2 0⎝
875⎫
⎪
0104⎪350⎪
⎪
1195⎪⎭每一列减去每列的最小值 8031180311
250403025⎫⎪4⎪0⎪⎪5⎪⎭3⎫⎪2⎪0⎪⎪3⎪⎭
第一、三、四行同时减去2，同时，第一、二列同时加上2.