[求助]救火啊！！~~女朋友急要的

yanghuhan

<  align=left>基本要求：１．问题的重叙　２．合理的假设　３．符号的说明　<p></p></P>
<  align=left>４．建立模型　５．模型的求解　６．评价与推广<p></p></P>
<  align=left>在一所学校里有<FONT face="Times New Roman">7</FONT>位教师和<FONT face="Times New Roman">12</FONT>个班级<FONT face="Times New Roman">,5</FONT>天一周的数学要求由下面的矩阵给出<FONT face="Times New Roman">:<p></p></FONT></P>
<TABLE  cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD  vAlign=top width=44>
<P  align=left><p> </p></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>1<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>2<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>3<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>4<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>5<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>6<p></p></SUB></FONT></P></TD>
<TD  width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>7<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>8<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>9<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>10<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>11<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">C<SUB>12<p></p></SUB></FONT></P></TD></TR>
<TR >
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">T<SUB>1<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD></TR>
<TR >
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">T<SUB>2<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">1<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">6<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">1<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD></TR>
<TR >
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">T<SUB>3<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD></TR>
<TR >
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">T<SUB>4<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD></TR>
<TR >
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">T<SUB>5<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">1<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD></TR>
<TR >
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">T<SUB>6<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD></TR>
<TR >
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">T<SUB>7<p></p></SUB></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TD  vAlign=top width=44>
<P  align=left><FONT face="Times New Roman">0<p></p></FONT></P></TD></TR></TABLE>
<P  align=left>表中数字<FONT face="Times New Roman">P<SUB>ij</SUB></FONT>表示教师<FONT face="Times New Roman">i</FONT>必<st1ersonName w:st="on" ProductID="须">须</st1ersonName>教授班级<FONT face="Times New Roman">j</FONT>的课时数<FONT face="Times New Roman">.<SUB><p></p></SUB></FONT></P>
<P  align=left><FONT face="Times New Roman">(1)    </FONT>一天必须分成多少课时才能满足要求<FONT face="Times New Roman">?<p></p></FONT></P>
<P  align=left><FONT face="Times New Roman">(2)    </FONT>若一张每天<FONT face="Times New Roman">8</FONT>课时的课表已经排出<FONT face="Times New Roman">,</FONT>则需要多少教室<FONT face="Times New Roman">?</FONT><p></p></P>[em06]

yanghuhan

哪位大虾救我啊

myj_8317

提供一点我的想法：试试建立0-1规划模型，并且用一下“八皇后问题算法”。也许最大匹配算法也能行

yanghuhan

<>楼上的，又没有具体的过程？</P>
<>我什么都不懂啊!</P>
<>能给个过程吗?随便都行！</P>

不交作业

<>设每天分n个课时,k表示一个星期内的第几个课时,p(i)(j)(k)表示第i个教师第k个课时是否给第j个班级上课. 取值为0,1.</P>
<>约束条件 </P>
<>1) 对j求和P(i)(j)(k)   &lt;=1 表示同一个教师在同一个课时只能给一个班级上课</P>
<P>2)对i求和P(i)(j)(k)  &lt;=1 表示一个班级一个课时只能有一个教师上课</P>
<P>3)对k求和（从1到5n）P(i)(j)(k) = Pij 课时总数与所给的矩阵对应</P>
<P>从n=1开始在上面的约束条件中搜索可行解，知道找到可行解，便可得到n,也就是每天的最少课时数</P>

yanghuhan

<>谢谢楼上的</P>

myj_8317

具体的算法就是“N后问题”，可在网上搜一下，很多的。

yanghuhan

<>谢谢了</P>
<>第一问已经搞定了，可第二问又该怎么做啊?</P>[em06]

不交作业

<>设每天分m个课时,l表示第l个教室,p(i)(j)(k)(l)表示第i个教师第k个课时是否在第l个教室给第j个班级上课. 取值为0,1.</P>
<>约束条件 </P>
<>1) 对j求和P(i)(j)(k)(l)&lt;=1 表示同一个教师在同一个课时同一个教室只能给一个班级上课</P>
<P>2)对i求和P(i)(j)(k)(l)&lt;=1 表示一个班级一个课时同一教室只能有一个教师上课</P>
<P>3）对l求和(从1到m)P(i)(j)(k)(l)&lt;=1 表示一个班级一个课时同一个教师只能在一间教室上课</P>
<P>4)对k,l求和（k从1到5*8,l从1到m）P(i)(j)(k)(l) = Pij 课时总数与所给的矩阵对应</P>
<P>从m=1开始在上面的约束条件中搜索可行解，直到找到可行解，便可得到m,也就是最少教室数</P>
<P>这个方法也许有点笨，但是编程计算是可以实现的</P>

[此贴子已经被作者于2005-11-2 13:46:31编辑过]

yanghuhan

<>谢谢不交作业,</P>
<>我先去试试,有问题再来请教.</P>