最小费用问题——lingo求解的三种常见解法

喜欢ヅ旅行 2022-12-04 05:25 185阅读 0赞

# 最小费用问题 #

## 方法一 系数矩阵0-1规划法 ##

### 代码 ###

由于没有lingo类型的代码涂色格式，我先给个截图，也许会看的清晰一些  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center]

model:
    
    sets:
    node/1..6/;
    road(node,node)/1,2,1,3,2,4,2,5,3,4,3,5,4,6,5,6/:w,f;
    endsets
    
    data:
    w=2,1,5,3,4,3,0,0;
    enddata
    
    n=@size(node);
    
    min=@sum(road(i,j):w(i,j)*f(i,j));
    
    @for(node(i)|i#ne#1 #and# i#ne#n:
    	@sum(road(i,j):f(i,j))=@sum(road(j,i):f(j,i))
    );
    
    @sum(road(i,j)|i#eq#1:f(i,j))=1;
    @sum(road(j,i)|i#eq#n:f(j,i))=1;

### 运行结果 ###

![‘’][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 2]

## 方法二 动态规划 ##

### 代码 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 3]

model:
    
    sets:
    node/1..6/:L;
    road(node,node)/1,2,1,3,2,4,2,5,3,4,3,5,4,6,5,6/:c;
    endsets
    
    data:
    c=2,1,5,3,4,3,0,0;
    enddata
    
    L(1)=0;
    
    @for(node(i)|i#gt#1:
    	L(i)=@min(road(j,i)|j#ne#i:L(j)+c(j,i))
    );
    
    
    end

### 运行结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 4]

## 方法三 邻接矩阵法 ##

### 代码 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 5]

model:
    
    sets:
    node/1..6/:L;
    road(node,node):a,w;
    endsets
    
    data:
    a=
    0,1,1,0,0,0,
    0,0,0,1,1,0,
    0,0,0,1,1,0,
    0,0,0,0,0,1,
    0,0,0,0,0,1,
    0,0,0,0,0,0;
    w=
    9,2,1,9,9,9,
    9,9,9,5,3,9,
    9,9,9,4,3,9,
    9,9,9,9,9,0,
    9,9,9,9,9,0,
    9,9,9,9,9,9;
    enddata
    
    L(1)=0;
    @for(node(i)|i#ne#1:
    	L(i)=@min(road(j,i)|j#ne#i #and# a(j,i)#ne#0:
    		L(j)+w(j,i)));
    
    end

### 运行结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/93dc5e3ec6094837ad394ea6779ffa62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/c819dbb0637e4a6f802f0f226670bb2c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/50c5d090a2104571ae61f8714d386fff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/f198b0206e73472f98c35ab8092f94f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/80df97922c8a400fba2829176436ae26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/6fea9995d6de4ef982ac1f271df8f73e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/6cf3977843cd476da30dc30277ba68b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTYzMjcw_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/43373f41b532412c8c003ef6c61cf109.png