青岛大学2009年数学建模竞赛选拔赛AB组试题

haibiantingtao

如题
青岛大学数学建模竞赛题目
A题：放射治疗的治疗方案设计
放射治疗是肿瘤治疗的重要手段。放射线虽然能杀死肿瘤细胞，但对人体的功能器官和组织也会造成严重伤害。因此，现代放射治疗通常通过调节放射线的强度分布，使得通过肿瘤的射线剂量达到设计要求，而通过肿瘤周围的功能器官和健康组织的射线尽可能少。
放疗的放射线是通过线性加速器产生的，放射线发射窗口是边长10cm
8 [- n& I, S& P的正方形，发射的射线是均匀的，剂量的大小通过调整放射的时间长短来控制。由于肿瘤的形状和肿瘤细胞活性分布以及周围功能器官的分布的不规则性，放射区域通常应该是不规则的几何形状，剂量分布也不均匀，我们利用设计剂量矩阵来描述这种情况。下面是一个设计剂量矩阵的例子：

file:///D:/Temp/msohtml1/01/clip_image002.gif
( G6 J; w  ~! f3 B; t2 u其中我们将射线发射窗口分解成file:///D:/Temp/msohtml1/01/clip_image004.gif个小窗口。file:///D:/Temp/msohtml1/01/clip_image006.gif表示在file:///D:/Temp/msohtml1/01/clip_image008.gif位置小窗口的放射剂量为设计剂量的40%。为了实现几何形状的调整，放疗机的射线发射窗口装有特殊金属做成的左右挡条。为了实现放射剂量的不均匀，通常把设计剂量矩阵分解成由0和1组成的矩阵的和。如上述矩阵可以分解为

	file:///D:/Temp/msohtml1/01/clip_image012.gif		file:///D:/Temp/msohtml1/01/clip_image013.gif		file:///D:/Temp/msohtml1/01/clip_image014.gif

file:///D:/Temp/msohtml1/01/clip_image016.gif
=20´
+
+20´
& s) j4 _* d0 Y4 y, C7 X+ k! C
* c, S5 \) I( D8 i. K$ }1 K* }

) d. i2 g  E- Y9 L

	file:///D:/Temp/msohtml1/01/clip_image019.gif		file:///D:/Temp/msohtml1/01/clip_image020.gif

. z. R* b6 g, H
) G5 S: w* j, D& ]1 ~# u! r: a
+20´
+20´


) `0 {* Y7 M( ~
/ _- O2 |9 K2 w分解成的4个基本矩阵称为形状矩阵。其中由0组成的灰色条状部分由左右档条遮挡形成，即0表示射线不穿过，1表示穿过。上述分解可以解释为：设计剂量由在上述4个不同形状的射线发射窗口各照射20个时间单位而实现。
上述分解可以由放疗机上的计算机控制系统实现。由于设备的设计要求，形状矩阵必须满足以下条件：
! i7 I/ I4 w5 y  l9 ]（1）
左右档条不能重叠，即一个小窗口不能被左右档条同时覆盖；
（2）
形状矩阵的每一行的1连续排列，1之间没有0；（即左右档条之间没有遮挡）
/ X" V7 `# ]& J7 M, U) }, H7 d（3）
* p4 M4 w9 j( n( R: o5 G在相邻的行中，左右档条不能交叠，即：左档条的右端不能超过右档条的左端。
file:///D:/Temp/msohtml1/01/clip_image021.gif
  z8 s' T1 I5 v) G; t
9 F1 U+ w) e0 K9 O0 r$ }1 U( sfile:///D:/Temp/msohtml1/01/clip_image023.gif
file:///D:/Temp/msohtml1/01/clip_image025.gif
7 Q& N0 p2 R9 p
0 F5 e1 F1 ~5 D, a不合要求

合乎要求
* F& {5 |/ N! \7 u! Q, s4 i6 ?' x（4）
0 l) I- g9 G; o+ F4 }, M5 u" S每个形状矩阵中的1组成联通的区域，不能分为两个孤立的区域。

& N) {+ ]8 f" Z+ p) q; d* K另外，设在放疗时，更换一次形状矩阵需要时间T。
4 H" Y, R7 W3 j- _  M由于在治疗过程中，病人必须固定在放疗机上不动，因此，为了减轻患者的不适，应尽可能使得放疗的总时间短一些。
' ^( {7 {0 ?5 e8 ^有以下问题需要解决：
! ^# h/ w& |  R8 N（1）
9 B& T% W; b/ ^  G设计治疗方案，即将一个设计剂量矩阵分解成形状矩阵的和。分解应使得放射和更换形状矩阵的总时间尽可能少；
（2）
; `# ?/ n6 R6 \" n( N" [对一个大型复杂的设计剂量矩阵，往往需要分解成许多不同的形状矩阵。如果我们限制形状矩阵的最大个数为K，则分解往往是近似的。请设计相应的治疗方案，使得分解尽可能精确且放射和更换形状矩阵的总时间尽可能少；
4 E  V: r* D! I, Z1 j5 n- Z5 H（3）
利用你的模型和算法对下面的设计剂量矩阵进行分解：（对第2问设不同形状矩阵最大个数为9）
/ L1 e! q, Z/ S+ z5 I( M4 a
file:///D:/Temp/msohtml1/01/clip_image027.gif


# B5 n4 ~, |  xB题：邮票裁切的最优方案设计
邮票裁切问题可以这样叙述：一张有m´n张邮票的连张（m行n列）最少经过多少次裁切可以裁成m´n个单张？由于每次裁切只裁切一个连张的某一条边，是一个1分2的过程，因此每次裁切恰好分出一张连张或单张，从而裁成mn个单张需要m´n-1次。
现在我们把问题扩展一下：在裁切时允许沿某一个方向（当然是邮票的边沿线）折叠后裁切。(如图：细线表示折叠的邮票连张，粗线表示裁切)。在允许折叠时，裁切的次数会大大减少。为了裁切的简便和准确，不允许将不同的连张叠在一起裁切。

file:///D:/Temp/msohtml1/01/clip_image028.gif

6 p5 ~; p' O4 K& z3 k( K
8 L" ^. J. U. B6 k- j( W5 O) r

请考虑以下问题：
（1）考虑1´n的邮票连张，按照新的裁切规则，最少裁切多少次，可以裁成n个单张？证明你的结论并给出相应的裁切方案。
（2）对于m´n的邮票连张, 最少裁切多少次，可以裁成n个单张？证明你的结论并给出实现最小裁切次数的裁切方案。
0 i3 T0 \! v/ Z, x8 |6 J（3）能否将最小裁切次数S(m,n)写成简洁的函数形式？
（4）如果对折叠次数进行限制，如每次切割最多切割s层，模型应该怎样修改？

黄淑芬

炸矩阵图都不可见啊？