Question

运筹学一道题目 整数规划求解答

运筹学一道题目 求解答
某公司假期安排员工出去爬山，有甲、乙、丙、丁四家旅行社可供选择，正值黄金周各家旅行社都只剩一部车可用，其车辆使用费分别为1000元/车、2000元/车、2500元/车和1500元/车，各车分别坐60人、80人、100人、55人。各旅行社拥有不同程度的优惠门票，分别为每人... 展开
整数规划 有步骤吗
某公司假期安排员工出去爬山，有甲、乙、丙、丁四家旅行社可供选择，正值黄金周各家旅行社都只剩一部车可用，其车辆使用费分别为1000元/车、2000元/车、2500元/车和1500元/车，各车分别坐60人、80人、100人、55人。各旅行社拥有不同程度的优惠门票，分别为每人22元、19元、17元和21元。公司现有190人，问如何安排可使公司花费最少

Answer 1

解：设乘坐甲车的人数为X1,乙X2,丙X3,丁X4。

yi={1，选择该旅行社；0，不选择该旅行社}

minZ=1000y1+2000y2+2500y3+1500y4+22X1+19X2+17X3+21X4.

s.t.  x1+x2+x3+x4≥190

x1≤60y1

x2≤80y2

x3≤1000y3

x4≤55y4.

然后用运筹学计算器计算得出答案~

哎，我们考试题，网上查不到正确答案，自己打的，希望可以帮到你。

Answer 2

我觉得这个问题分成两个规划步骤。
设选择一旅行社的事件为Xi,i∈{1,2,3,4}，Xi∈{0,1}
则60x1+80x2+100x3+55x4>=190，再利用分支定界法求出每个可能解。
第二阶段计算费用。但是题目表述不是很清楚：优惠门票是优惠乘车人次还是车上总共座位的人数还是全部的190人，不知道它是什么意思。所以这部分门票优惠你需要自己确定了，假设它是S
求minw=1000x1+2000x2+2500X3+1500x4-S

Answer 3

用混合型整数规划，设yi为0-1变量（选择该旅行社的时候为1，不选择的时候为0），xi为四家旅行社所乘的人数，根据人数、门票等设置约束条件，注意不要忘记添加xi<=my，其中m是充分大的正数。