[求助]救火啊！！~~女朋友急要的
<Palign=left>基本要求：１．问题的重叙 ２．合理的假设 ３．符号的说明 <p></p></P><Palign=left>４．建立模型 ５．模型的求解 ６．评价与推广<p></p></P>
<Palign=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>
<TABLEcellSpacing=0 cellPadding=0 border=1>
<TR >
<TDvAlign=top width=44>
<Palign=left><p> </p></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>1<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>2<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>3<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>4<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>5<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>6<p></p></SUB></FONT></P></TD>
<TDwidth=44>
<Palign=left><FONT face="Times New Roman">C<SUB>7<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>8<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>9<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>10<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>11<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">C<SUB>12<p></p></SUB></FONT></P></TD></TR>
<TR >
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">T<SUB>1<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD></TR>
<TR >
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">T<SUB>2<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">1<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">6<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">1<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD></TR>
<TR >
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">T<SUB>3<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD></TR>
<TR >
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">T<SUB>4<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD></TR>
<TR >
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">T<SUB>5<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">1<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">2<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD></TR>
<TR >
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">T<SUB>6<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">5<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD></TR>
<TR >
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">T<SUB>7<p></p></SUB></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">4<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">3<p></p></FONT></P></TD>
<TDvAlign=top width=44>
<Palign=left><FONT face="Times New Roman">0<p></p></FONT></P></TD></TR></TABLE>
<Palign=left>表中数字<FONT face="Times New Roman">P<SUB>ij</SUB></FONT>表示教师<FONT face="Times New Roman">i</FONT>必<st1:PersonName w:st="on" ProductID="须">须</st1:PersonName>教授班级<FONT face="Times New Roman">j</FONT>的课时数<FONT face="Times New Roman">.<SUB><p></p></SUB></FONT></P>
<Palign=left><FONT face="Times New Roman">(1) </FONT>一天必须分成多少课时才能满足要求<FONT face="Times New Roman">?<p></p></FONT></P>
<Palign=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> 哪位大虾救我啊 提供一点我的想法：试试建立0-1规划模型，并且用一下“八皇后问题算法”。也许最大匹配算法也能行 <P>楼上的，又没有具体的过程？</P>
<P>我什么都不懂啊!</P>
<P>能给个过程吗?随便都行！</P>
我是这样想的
<P>设每天分n个课时,k表示一个星期内的第几个课时,p(i)(j)(k)表示第i个教师第k个课时是否给第j个班级上课. 取值为0,1.</P><P>约束条件 </P>
<P>1) 对j求和P(i)(j)(k) <=1 表示同一个教师在同一个课时只能给一个班级上课</P>
<P>2)对i求和P(i)(j)(k)<=1 表示一个班级一个课时只能有一个教师上课</P>
<P>3)对k求和（从1到5n）P(i)(j)(k) = Pij 课时总数与所给的矩阵对应</P>
<P>从n=1开始在上面的约束条件中搜索可行解，知道找到可行解，便可得到n,也就是每天的最少课时数</P> <P>谢谢楼上的</P> 具体的算法就是“N后问题”，可在网上搜一下，很多的。 <P>谢谢了</P>
<P>第一问已经搞定了，可第二问又该怎么做啊?</P> <P>设每天分m个课时,l表示第l个教室,p(i)(j)(k)(l)表示第i个教师第k个课时是否在第l个教室给第j个班级上课. 取值为0,1.</P>
<P>约束条件 </P>
<P>1) 对j求和P(i)(j)(k)(l)<=1 表示同一个教师在同一个课时同一个教室只能给一个班级上课</P>
<P>2)对i求和P(i)(j)(k)(l)<=1 表示一个班级一个课时同一教室只能有一个教师上课</P>
<P>3）对l求和(从1到m)P(i)(j)(k)(l)<=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编辑过]
<P>谢谢不交作业,</P>
<P>我先去试试,有问题再来请教.</P>
页:
[1]
2