【运筹学】表上作业法 ( 找初始基可行解 | 计算检验数 | 调整运量 )

文章目录

  • 一、运输规划问题
  • 二、找初始基可行解
  • 三、计算检验数
  • 四、调整运量 ( 换基 )
在这里插入图片描述

一、运输规划问题


运输规划问题 :

在这里插入图片描述

二、找初始基可行解


使用最小元素法求得的初始基可行解 :

B

        1
       
      
     
     
      \rm B_1
     
    
   B1​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        2
       
      
     
     
      \rm B_2
     
    
   B2​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        3
       
      
     
     
      \rm B_3
     
    
   B3​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        4
       
      
     
     
      \rm B_4
     
    
   B4​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>产量</p></div></div></th></tr></thead><tbody><tr><td style="text-align:left"><div><div class="table-cell"><p>A
       
       
        1
       
      
     
     
      \rm A_1
     
    
   A1​</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>3
      
     
     
      3
     
    
   3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>11
      
     
     
      11
     
    
   11</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>3
      
     
     
      3
     
    
   3 , 
    
     
      
       
        4
       
      
      
       4
      
     
    4</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>10
      
     
     
      10
     
    
   10 , 
    
     
      
       
        3
       
      
      
       3
      
     
    3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>7
      
     
     
      7
     
    
   7</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>A
       
       
        2
       
      
     
     
      \rm A_2
     
    
   A2​</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>1
      
     
     
      1
     
    
   1 , 
    
     
      
       
        3
       
      
      
       3
      
     
    3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>9
      
     
     
      9
     
    
   9</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>2
      
     
     
      2
     
    
   2 , 
    
     
      
       
        1
       
      
      
       1
      
     
    1</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>8
      
     
     
      8
     
    
   8</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>4
      
     
     
      4
     
    
   4</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>A
       
       
        3
       
      
     
     
      \rm A_3
     
    
   A3​</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>7
      
     
     
      7
     
    
   7</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>4
      
     
     
      4
     
    
   4 , 
    
     
      
       
        6
       
      
      
       6
      
     
    6</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>10
      
     
     
      10
     
    
   10</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>5
      
     
     
      5
     
    
   5 , 
    
     
      
       
        3
       
      
      
       3
      
     
    3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>9
      
     
     
      9
     
    
   9</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>销量</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>3
      
     
     
      3
     
    
   3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>6
      
     
     
      6
     
    
   6</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>5
      
     
     
      5
     
    
   5</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>6
      
     
     
      6
     
    
   6</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p></p></div></div></td></tr></tbody></table></div><figure class=""><span>\rm B_1</span></figure><figure class=""><span>\rm B_2</span></figure><figure class=""><span>\rm B_3</span></figure><figure class=""><span>\rm B_4</span></figure><p>产量</p><figure class=""><span>\rm A_1</span></figure><figure class=""><span>3</span></figure><figure class=""><span>11</span></figure><figure class=""><span>3</span></figure><p> , </p><figure class=""><span>4</span></figure><figure class=""><span>10</span></figure><p> , </p><figure class=""><span>3</span></figure><figure class=""><span>7</span></figure><figure class=""><span>\rm A_2</span></figure><figure class=""><span>1</span></figure><p> , </p><figure class=""><span>3</span></figure><figure class=""><span>9</span></figure><figure class=""><span>2</span></figure><p> , </p><figure class=""><span>1</span></figure><figure class=""><span>8</span></figure><figure class=""><span>4</span></figure><figure class=""><span>\rm A_3</span></figure><figure class=""><span>7</span></figure><figure class=""><span>4</span></figure><p> , </p><figure class=""><span>6</span></figure><figure class=""><span>10</span></figure><figure class=""><span>5</span></figure><p> , </p><figure class=""><span>3</span></figure><figure class=""><span>9</span></figure><p><strong>销量</strong></p><figure class=""><span>3</span></figure><figure class=""><span>6</span></figure><figure class=""><span>5</span></figure><figure class=""><span>6</span></figure><p><strong>使用 最小元素法, 得到初始基可行解 :</strong> </p><figure class=""><span>\begin{cases} \rm x_{13} = 4 \\\\ \rm x_{14} = 3 \\\\ \rm x_{21} = 3 \\\\ \rm x_{23} = 1 \\\\ \rm x_{32} = 6 \\\\ \rm x_{34} = 3 \end{cases}</span></figure><h2 id="f46lc" name="%E4%B8%89%E3%80%81%E8%AE%A1%E7%AE%97%E6%A3%80%E9%AA%8C%E6%95%B0">三、计算检验数</h2><figure class=""><hr/></figure><p><strong>计算检验数 :</strong></p><p>使用闭回路法 , 逐个计算每个非基变量的检验数 ,</p><p>以非基变量为起点 , 出发的格子使用加号 </p><figure class=""><span>+</span></figure><p> , 第二个格子使用减号 </p><figure class=""><span>-</span></figure><p> , 之后的歌词依次使用 加号减号交替 </p><figure class=""><span>+-</span></figure><p> 符号 ;</p><p>计算上述闭回路的运费代数和 ,</p><p>如果代数和 大于等于 </p><figure class=""><span>0</span></figure><p> , 说明当前的非基变量格子取 </p><figure class=""><span>0</span></figure><p> 就是 最优选择 ;</p><p>如果代数和 小于 </p><figure class=""><span>0</span></figure><p> , 说明当前的非基变量格子取 </p><figure class=""><span>0</span></figure><p> 不是最优选择 ;</p><p><strong>这里以计算 </strong></p><figure class=""><span>\rm \sigma_{24}</span></figure><p><strong> 检验数为例 :</strong></p><figure class=""><span>\rm A_{24} +</span></figure><p> , </p><figure class=""><span>\rm A_{23} -</span></figure><p> , </p><figure class=""><span>\rm A_{13} +</span></figure><p> , </p><figure class=""><span>\rm A_{14} -</span></figure><figure class=""><span>\rm \sigma_{24} = ( 1 \times 8 ) - ( 1 \times 2 ) + ( 1 \times 3 ) - ( 1 \times 10 ) = -1</span></figure><p>检验数小于 </p><figure class=""><span>0</span></figure><p> ;</p><p><strong>计算出的 非基变量 检验数使用 蓝色括号字体 写在表格中 :</strong></p><div class="table-wrapper"><table><thead><tr><th style="text-align:left"><div><div class="table-header"><p></p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        1
       
      
     
     
      \rm B_1
     
    
   B1​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        2
       
      
     
     
      \rm B_2
     
    
   B2​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        3
       
      
     
     
      \rm B_3
     
    
   B3​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        4
       
      
     
     
      \rm B_4
     
    
   B4​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>产量</p></div></div></th></tr></thead><tbody><tr><td style="text-align:left"><div><div class="table-cell"><p>A
       
       
        1
       
      
     
     
      \rm A_1
     
    
   A1​</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>3
      
     
     
      3
     
    
   3 , 
    
     
      
       
        (
       
       
        1
       
       
        )
       
      
      
       (1)
      
     
    (1)</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>11
      
     
     
      11
     
    
   11 , 
    
     
      
       
        (
       
       
        2
       
       
        )
       
      
      
       (2)
      
     
    (2)</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>3
      
     
     
      3
     
    
   3 , 
    
     
      
       
        4
       
      
      
       4
      
     
    4</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>10
      
     
     
      10
     
    
   10 , 
    
     
      
       
        3
       
      
      
       3
      
     
    3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>7
      
     
     
      7
     
    
   7</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>A
       
       
        2
       
      
     
     
      \rm A_2
     
    
   A2​</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>1
      
     
     
      1
     
    
   1 , 
    
     
      
       
        3
       
      
      
       3
      
     
    3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>9
      
     
     
      9
     
    
   9 , 
    
     
      
       
        (
       
       
        1
       
       
        )
       
      
      
       (1)
      
     
    (1)</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>2
      
     
     
      2
     
    
   2 , 
    
     
      
       
        1
       
      
      
       1
      
     
    1</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>8
      
     
     
      8
     
    
   8 , 
    
     
      
       
        (
       
       
       
       
        1
       
       
        )
       
      
      
       (-1)
      
     
    (−1)</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>4
      
     
     
      4
     
    
   4</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>A
       
       
        3
       
      
     
     
      \rm A_3
     
    
   A3​</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>7
      
     
     
      7
     
    
   7 , 
    
     
      
       
        (
       
       
        10
       
       
        )
       
      
      
       (10)
      
     
    (10)</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>4
      
     
     
      4
     
    
   4 , 
    
     
      
       
        6
       
      
      
       6
      
     
    6</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>10
      
     
     
      10
     
    
   10 , 
    
     
      
       
        (
       
       
        12
       
       
        )
       
      
      
       (12)
      
     
    (12)</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>5
      
     
     
      5
     
    
   5 , 
    
     
      
       
        3
       
      
      
       3
      
     
    3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>9
      
     
     
      9
     
    
   9</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>销量</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>3
      
     
     
      3
     
    
   3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>6
      
     
     
      6
     
    
   6</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>5
      
     
     
      5
     
    
   5</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>6
      
     
     
      6
     
    
   6</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p></p></div></div></td></tr></tbody></table></div><figure class=""><span>\rm B_1</span></figure><figure class=""><span>\rm B_2</span></figure><figure class=""><span>\rm B_3</span></figure><figure class=""><span>\rm B_4</span></figure><p>产量</p><figure class=""><span>\rm A_1</span></figure><figure class=""><span>3</span></figure><p> , </p><figure class=""><span>(1)</span></figure><figure class=""><span>11</span></figure><p> , </p><figure class=""><span>(2)</span></figure><figure class=""><span>3</span></figure><p> , </p><figure class=""><span>4</span></figure><figure class=""><span>10</span></figure><p> , </p><figure class=""><span>3</span></figure><figure class=""><span>7</span></figure><figure class=""><span>\rm A_2</span></figure><figure class=""><span>1</span></figure><p> , </p><figure class=""><span>3</span></figure><figure class=""><span>9</span></figure><p> , </p><figure class=""><span>(1)</span></figure><figure class=""><span>2</span></figure><p> , </p><figure class=""><span>1</span></figure><figure class=""><span>8</span></figure><p> , </p><figure class=""><span>(-1)</span></figure><figure class=""><span>4</span></figure><figure class=""><span>\rm A_3</span></figure><figure class=""><span>7</span></figure><p> , </p><figure class=""><span>(10)</span></figure><figure class=""><span>4</span></figure><p> , </p><figure class=""><span>6</span></figure><figure class=""><span>10</span></figure><p> , </p><figure class=""><span>(12)</span></figure><figure class=""><span>5</span></figure><p> , </p><figure class=""><span>3</span></figure><figure class=""><span>9</span></figure><p><strong>销量</strong></p><figure class=""><span>3</span></figure><figure class=""><span>6</span></figure><figure class=""><span>5</span></figure><figure class=""><span>6</span></figure><h2 id="fs0f7" name="%E5%9B%9B%E3%80%81%E8%B0%83%E6%95%B4%E8%BF%90%E9%87%8F-(-%E6%8D%A2%E5%9F%BA-)">四、调整运量 ( 换基 )</h2><figure class=""><hr/></figure><p>上述检验数中 , </p><figure class=""><span>\rm \sigma_{24}</span></figure><p> 为负数 , 需要进行换基 , 该非基变量就是入基变量 ;</p><p>该检验数的闭合回路如下 : </p><figure class=""><span>\rm A_{24} +</span></figure><p> , </p><figure class=""><span>\rm A_{23} -</span></figure><p> , </p><figure class=""><span>\rm A_{13} +</span></figure><p> , </p><figure class=""><span>\rm A_{14} -</span></figure><p> ;</p><p>在 </p><figure class=""><span>-</span></figure><p> 符号的基变量中挑选一个最小的 , 作为出基变量 ;</p><p><strong>换基之后的结果如下 :</strong></p><p><strong>经过上述计算后的运费表格如下 :</strong></p><div class="table-wrapper"><table><thead><tr><th style="text-align:left"><div><div class="table-header"><p></p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        1
       
      
     
     
      \rm B_1
     
    
   B1​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        2
       
      
     
     
      \rm B_2
     
    
   B2​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        3
       
      
     
     
      \rm B_3
     
    
   B3​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>B
       
       
        4
       
      
     
     
      \rm B_4
     
    
   B4​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>产量</p></div></div></th></tr></thead><tbody><tr><td style="text-align:left"><div><div class="table-cell"><p>A
       
       
        1
       
      
     
     
      \rm A_1
     
    
   A1​</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>3
      
     
     
      3
     
    
   3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>11
      
     
     
      11
     
    
   11</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>3
      
     
     
      3
     
    
   3 , 
    
     
      
       
        5
       
      
      
       5
      
     
    5</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>10
      
     
     
      10
     
    
   10 , 
    
     
      
       
        2
       
      
      
       2
      
     
    2</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>7
      
     
     
      7
     
    
   7</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>A
       
       
        2
       
      
     
     
      \rm A_2
     
    
   A2​</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>1
      
     
     
      1
     
    
   1 , 
    
     
      
       
        3
       
      
      
       3
      
     
    3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>9
      
     
     
      9
     
    
   9</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>2
      
     
     
      2
     
    
   2</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>8
      
     
     
      8
     
    
   8 , 
    
     
      
       
        1
       
      
      
       1
      
     
    1</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>4
      
     
     
      4
     
    
   4</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>A
       
       
        3
       
      
     
     
      \rm A_3
     
    
   A3​</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>7
      
     
     
      7
     
    
   7</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>4
      
     
     
      4
     
    
   4 , 
    
     
      
       
        6
       
      
      
       6
      
     
    6</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>10
      
     
     
      10
     
    
   10</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>5
      
     
     
      5
     
    
   5 , 
    
     
      
       
        3
       
      
      
       3
      
     
    3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>9
      
     
     
      9
     
    
   9</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>销量</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>3
      
     
     
      3
     
    
   3</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>6
      
     
     
      6
     
    
   6</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>5
      
     
     
      5
     
    
   5</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>6
      
     
     
      6
     
    
   6</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p></p></div></div></td></tr></tbody></table></div><figure class=""><span>\rm B_1</span></figure><figure class=""><span>\rm B_2</span></figure><figure class=""><span>\rm B_3</span></figure><figure class=""><span>\rm B_4</span></figure><p>产量</p><figure class=""><span>\rm A_1</span></figure><figure class=""><span>3</span></figure><figure class=""><span>11</span></figure><figure class=""><span>3</span></figure><p> , </p><figure class=""><span>5</span></figure><figure class=""><span>10</span></figure><p> , </p><figure class=""><span>2</span></figure><figure class=""><span>7</span></figure><figure class=""><span>\rm A_2</span></figure><figure class=""><span>1</span></figure><p> , </p><figure class=""><span>3</span></figure><figure class=""><span>9</span></figure><figure class=""><span>2</span></figure><figure class=""><span>8</span></figure><p> , </p><figure class=""><span>1</span></figure><figure class=""><span>4</span></figure><figure class=""><span>\rm A_3</span></figure><figure class=""><span>7</span></figure><figure class=""><span>4</span></figure><p> , </p><figure class=""><span>6</span></figure><figure class=""><span>10</span></figure><figure class=""><span>5</span></figure><p> , </p><figure class=""><span>3</span></figure><figure class=""><span>9</span></figure><p><strong>销量</strong></p><figure class=""><span>3</span></figure><figure class=""><span>6</span></figure><figure class=""><span>5</span></figure><figure class=""><span>6</span></figure><p><strong>计算当前的总运费 :</strong></p><figure class=""><span>\rm ( 3 \times 5 ) + ( 10 \times 2 ) + ( 1 \times 3 ) + ( 8 \times 1 ) + ( 4 \times 6 ) + ( 3 \times 5 ) = 85</span></figure><p><strong>计算检验数验证 , 是最优解 ;</strong></p>