一道课程设计的题目，希望大家帮帮忙

Matrix

某公司需要招聘甲、乙两种工人，其工作可分为1、2、3三大类，每类工作可有两种工人小组完成，小组组成见下表。已知甲、乙两种工人的工资分别为每小时10元和5元，他们每周都工作40小时，但实际作出的等效生产小时数分别为40小时和30小时。为完成生产进度，该公司每周需完成的生产小时数分别为：第1类工作，10000消失；第2类工作，1500小时；第3类工作，20000小时。由于劳动力缺乏，甲种工人不能多于500个，乙种工人不能多于800个。试确定使总劳动力费用最少时工厂应招聘的工人数。并按要求分别完成下列分析：（1）第1类工作每周需完成的生产小时数在何范围内变化时最优基不变？（2）甲种工人的招聘数量在何范围内变化时最优基不变？（3）乙种工人的工资在何范围内变化时最优招聘方案不变？

- _/ P, `* X' }1 A# v( \( S3 e* {

工作小组人数及类型构成

+ F1 T$ o+ ?8 C! g# Q# \! r

小组 甲种工人人数 乙种工人人数 工作类型

4 M* e2 F# O# B; \

1 1 0 (1)

2 1 2 (1)

5 A9 I4 G0 L0 R; u+ |

3 1 0 (2)

W1 c5 D, o9 U' M

4 0 1 (2)

7 P) U1 O" I# s0 ~, r. k8 [

5 0 5 (3)

6 1 3 (3)

) K" G! \) e6 [' O J% Q" z

[此贴子已经被作者于2004-6-25 17:59:26编辑过]

ilikenba

设：需要1-6类工人小组分别为x1,x2,x3,x4,x5,x6个。
则上述的问题等价为下面的线性规划问题！
  min  10*(x1+x2+x3+x6)+5*(2*x2+x4+5*x5+3*x6)
! T5 N+ B& `2 a; y! l5 \8 u1 J# k# x  s.t. (x1+x2)*40+2*x2*30>=10000
& Y, n& s. u2 k& R2 j2 [/ I5 X. M       x3*40+x4*30>=1500
       x6*40+5*x5*30+3*x6*30>=20000
# M" F& b8 z" I- i       x1+x2+x3+x6<=500
, i) V* o* B9 A3 _  t3 p4 @4 D       2*x2+x4+5*x5+3*x6<=800
这是一个线性规划问题！可以用单纯型法求解！关于后面的三个题目，也很简单！通常的
0 o3 p% v  Z2 L; _9 d. g& K. G0 X, R线性规划书都有方法的例子！很简单！

scarlett

这个问题还需要流程图和上机调试的程序，大家帮帮忙

[em01]

风雨同行

以下是引用ilikenba在2004-6-29 14:11:14的发言： ! j: s5 _# S& X# |设：需要1-6类工人小组分别为x1,x2,x3,x4,x5,x6个。 则上述的问题等价为下面的线性规划问题！ 9 W0 O3 T! T, c, U0 j$ \6 K min 10*(x1+x2+x3+x6)+5*(2*x2+x4+5*x5+3*x6) 0 U% ^" @+ t9 o" M s.t. (x1+x2)*40+2*x2*30>=10000 * \1 y3 g. I, V x3*40+x4*30>=1500 3 L+ S6 H7 [, G3 ^! O x6*40+5*x5*30+3*x6*30>=20000 # d, o9 Z3 U9 {, G x1+x2+x3+x6<=500 / l4 m' I- x5 q6 J% O 2*x2+x4+5*x5+3*x6<=800 这是一个线性规划问题！可以用单纯型法求解！关于后面的三个题目，也很简单！通常的 ' R* i0 }+ g& U/ ^( ?- P线性规划书都有方法的例子！很简单！

9 u% N: ]2 e% F. r

不是这么简单的，这个是整数线性规划，可是个NP完全问题啊。

lckboy

这是整数线性规划啊，n维的向量都是非负整数啊，用分支定界法求解。不如干脆用Lingo或者Matlab求解啊，什么都不用想了

ilikenba

有理！应该用分枝定界法！或者就是类似穷举类型的树搜索算法！

lvbin19830207

用Lingo或者Matlab求解

lvbin19830207

min  10*(x1+x2+x3+x6)+5*(2*x2+x4+5*x5+3*x6)
  s.t. (x1+x2)*40+2*x2*30&gt;=10000
# P7 J$ G( u. q; Y       x3*40+x4*30&gt;=1500
" h8 h. y6 B, K       x6*40+5*x5*30+3*x6*30&gt;=20000
       x1+x2+x3+x6&lt;=500
       2*x2+x4+5*x5+3*x6&lt;=800

zhanfeng

有一道数学建模题目“降落伞的选择”和它类似！先用matlab求出数值解，它可能不是整数，若此可再用分值定界法选出整数解.

chz0829

太ＥＡＳＹ了