求一指派问题的MATLAB程序

clear all；

C=[2 15 13 410 4 14 159 14 16 137 8 11 9]%效率矩阵C

n=size(C,1)%计算C的行列数n

C=C(:)%计算目标函数系数，将矩阵C按列排成一个列向量即可。

A=[]B=[]%没有不等式约束

Ae=zeros(2*n,n^2)%计算等约束的系数矩阵a

for i=1:n

for j=(i-1)*n+1:n*i

Ae(i,j)=1

end

for k=i:n:n^2

Ae(n+i,k)=1

end

end

Be=ones(2*n,1)%等式约束右端项b

Xm=zeros(n^2,1)%决策变量下界Xm

XM=ones(n^2,1)%决策变量上界XM

[x,z]=linprog(C,A,B,Ae,Be,Xm,XM)%使用linprog求解

x=reshape(x,n,n)%将列向量x按列排成一个n阶方阵

disp('最优解矩阵为:')%输出指派方案和最优值

Assignment=round(x)%使用round进行四舍五入取整

disp('最优解为:')

z

其实题目是不够全的 需要指出是否四个人必须要分别翻译四种语言 还有指派时间指的是加起来还是最长的那个 这里按照每人必须对应一个语言 指派时间是加起来算

model:

sets:

person/1..4/

language/1..4/

translate(person,language):time,x

endsets

data:

time=

2 15134

104 14 15

9 14 16 13

7 8 119

enddata

min=@sum(translate:time*x)

@for(person(i):@sum(language(j):x)=1)

@for(language(j):@sum(person(i):x)=1)

@for(translate:@bin(x))

end

指派问题，丙不能完成D任务，则给以非常的完成时间，比如100000给它，这样就不会选择丙去执行D。优化目标是总的时间最小，约束条件是每人最多完成一项任务，每项任务至少由一个人完成。用LINGO，程序见附件，得到的结果如下 ：

Global optimal solution found.

Objective value:                              19.00000

Objective bound:                              19.00000

Infeasibilities:                              0.000000

Extended solver steps:                               0

Total solver iterations:                             0

Model Class:                                      PILP

Total variables:                     16

Nonlinear variables:                  0

Integer variables:                   16

Total constraints:                    9

Nonlinear constraints:                0

Total nonzeros:                      48

Nonlinear nonzeros:                   0

                              Variable           Value        Reduced Cost

                         TIME( JIA, A)        7.000000            0.000000

                         TIME( JIA, B)        2.000000            0.000000

                         TIME( JIA, C)        9.000000            0.000000

                         TIME( JIA, D)        7.000000            0.000000

                          TIME( YI, A)        4.000000            0.000000

                          TIME( YI, B)        2.000000            0.000000

                          TIME( YI, C)        7.000000            0.000000

                          TIME( YI, D)        5.000000            0.000000

                        TIME( BING, A)        4.000000            0.000000

                        TIME( BING, B)        2.000000            0.000000

                        TIME( BING, C)        3.000000            0.000000

                        TIME( BING, D)        100000.0            0.000000

                        TIME( DING, A)        10.00000            0.000000

                        TIME( DING, B)        6.000000            0.000000

                        TIME( DING, C)        9.000000            0.000000

                        TIME( DING, D)        10.00000            0.000000

                   ASSIGNMENT( JIA, A)        0.000000            7.000000

                   ASSIGNMENT( JIA, B)        1.000000            2.000000

                   ASSIGNMENT( JIA, C)        0.000000            9.000000

                   ASSIGNMENT( JIA, D)        0.000000            7.000000

                    ASSIGNMENT( YI, A)        1.000000            4.000000

                    ASSIGNMENT( YI, B)        0.000000            2.000000

                    ASSIGNMENT( YI, C)        0.000000            7.000000

                    ASSIGNMENT( YI, D)        0.000000            5.000000

                  ASSIGNMENT( BING, A)        0.000000            4.000000

                  ASSIGNMENT( BING, B)        0.000000            2.000000

                  ASSIGNMENT( BING, C)        1.000000            3.000000

                  ASSIGNMENT( BING, D)        0.000000            100000.0

                  ASSIGNMENT( DING, A)        0.000000            10.00000

                  ASSIGNMENT( DING, B)        0.000000            6.000000

                  ASSIGNMENT( DING, C)        0.000000            9.000000

                  ASSIGNMENT( DING, D)        1.000000            10.00000

                                   Row    Slack or Surplus      Dual Price

                                     1        19.00000           -1.000000

                                     2        0.000000            0.000000

                                     3        0.000000            0.000000

                                     4        0.000000            0.000000

                                     5        0.000000            0.000000

                                     6        0.000000            0.000000

                                     7        0.000000            0.000000

                                     8        0.000000            0.000000

                                     9        0.000000            0.000000

---