数学规划

  • 时间:
  • 浏览:
  • 来源:互联网

人生第一个数学规划

时间分配问题

有T天时间(1)可用于安排复习J门课程,每天只能复习一门课程(3),每门课程至少复习一天(2)

用t天时间复习第j门课程可使该门课程提高Pjt

如何制定复习计划可使所有课程提高的总分尽可能大

具体实例

有7天时间可用于安排复习4门课程,每天只能复习一门课程,每门课程至少复习一天

第j门课程复习天数t与可能提高分数Pij之间的关系:
( P j t ) 4 × 4 = ( 3 5 6 7 5 5 6 9 2 4 7 8 6 7 9 9 ) (P_{jt})_{4\times4}=\begin{pmatrix} 3 & 5 & 6 & 7 \\ 5 & 5 & 6 & 9 \\ 2 & 4 & 7 & 8 \\ 6 & 7 & 9 & 9 \\ \end{pmatrix} (Pjt)4×4=3526554766797989
如何制定复习计划可使所有课程提高的总分尽可能大

具体求解

决策变量:
x j t = { 1 , 花 t 天 复 习 第 j 门 课 0 , 其 他 x_{jt}= \begin{cases} 1,\quad 花t天复习第j门课\\ 0,\quad 其他 \end{cases} xjt={1,tj0,
求解:
m a x ∑ j = 1 4 ∑ t = 1 4 P j t x j t s . t . ∑ j = 1 4 ∑ t = 1 4 x j t t = 7 ( 1 ) ∑ t = 1 4 x j t t ≥ 1 j = 1 , 2 , 3 , 4 ( 2 ) ∑ t = 1 4 x j t = 1 j = 1 , 2 , 3 , 4 ( 3 ) x j t = 0 , 1 t = 1 , 2 , 3 , 4 j = 1 , 2 , 3 , 4 max \qquad\sum_{j=1}^{4}\sum_{t=1}^{4}P_{jt}x_{jt}\\ s.t.\qquad\sum_{j=1}^{4}\sum_{t=1}^{4}x_{jt}t=7\qquad (1)\\ \sum_{t=1}^{4}x_{jt}t\geq1\qquad j=1,2,3,4\qquad (2)\\ \sum_{t=1}^{4}x_{jt} = 1\qquad j=1,2,3,4\qquad (3)\\ x_{jt}=0,1\qquad t=1,2,3,4\qquad j=1,2,3,4 maxj=14t=14Pjtxjts.t.j=14t=14xjtt=7(1)t=14xjtt1j=1,2,3,4(2)t=14xjt=1j=1,2,3,4(3)xjt=0,1t=1,2,3,4j=1,2,3,4

( P j t ) 4 × 4 = ( 3 5 6 7 5 5 6 9 2 4 7 8 6 7 9 9 ) (P_{jt})_{4\times4}=\begin{pmatrix} 3 & 5 & 6 & 7 \\ 5 & 5 & 6 & 9 \\ 2 & 4 & 7 & 8 \\ 6 & 7 & 9 & 9 \\ \end{pmatrix} (Pjt)4×4=3526554766797989

用python-pulp库求解如下

import pulp
def reviewproblem(P,courses,days):
  #确定为最大化问题
  lp=pulp.LpProblem('review problem',sense=pulp.LpMaximize)
  #设定决策变量,整数型,取值0,1
  x=[[pulp.LpVariable(f'x{i}{j}',lowBound=0,upBound=1,cat=pulp.LpInteger) 
  for j in range(courses)] for i in range(courses)]
  #展开二维数组
  flatten = lambda x:[y for l in x for y in flatten(l)] if type(x) is list else [x]
  #添加目标函数
  lp += pulp.lpDot(flatten(P),flatten(x))
  #添加约束条件
  #约束(1)
  lp += pulp.lpDot(flatten([[i for i in range(1,courses+1)] for j in range(courses)]),flatten(x)) == 7
  for j in range(courses):
    #约束(2)
    lp += pulp.lpDot(list(range(1,courses+1)),x[j]) >= 1
    #约束(3)
    lp += sum(x[j]) == 1
  #求解问题
  lp.solve()
  return {'objective':pulp.value(lp.objective),'var':[[pulp.value(x[i][j])for j in range(courses)] for i in range(courses)]}
if __name__=="__main__":
  #目标函数的系数Pij
  P=[[3,5,6,7],[5,5,6,9],[2,4,7,8],[6,7,9,9]]
  #调用函数
  res = reviewproblem(P,4,7)
  #输出结果
  print("所有课程提高的总分最大为:")
  print(res['objective'])
  print("变量取值为:")
  print(res['var'])

输出如下:

所有课程提高的总分最大为:

23.0

变量取值为:

[[0.0, 1.0, 0.0, 0.0], [1.0, 0.0, 0.0, 0.0], [0.0, 0.0, 1.0, 0.0], [1.0, 0.0, 0.0, 0.0]]

本文链接http://www.dzjqx.cn/news/show-617097.html