运筹学课程设计报告

长 春 工 业 大 学

课程设计报告

课程设计名称     运筹课程设计   

专        业 信息管理与信息系统

班        级           

学 生 姓 名         

指 导 教 师　　          

20##年7月12日

课 程 设 计 任 务 书

运筹学课程设计报告

组    别：第十八组

设计人员：

设计时间：20##年6月27日---20##年7月12日

1.设计进度

本课程设计时间分为两周：

第一周（20##年6月29日----20##年7月5日）：建模阶段。

此阶段各小组根据给出的题目完成模型的建立。

主要环节包括：

1.1 6月29日上午：发指导书；按组布置设计题目；说明进度安排。

1.2 6月29日下午至7月1日：各小组审题，查阅资料，进行建模前的必要准备(包括求解程序的编写与查找)。

1.3 7月4日至5日：各个小组进行建模，并根据题目及设计要求拟定设计提纲，指导教师审阅；同时阅读，理解求解程序，为上机求解做好准备。

第二周（20##年7月6日---7月12日）：上机求解，结果分析及答辩。

主要环节包括：

1.4 7月6日至7月7日：上机调试程序

1.5 7月8日：完成计算机求解与结果分析。

1.6 7月11日：撰写设计报告。

1.7 7月12日：设计答辩及成绩评定。

2.设计题目

第十六题、某城市自来水的水源地为A、B、C三个水库，分别由地下管道把水送往该市所辖甲、乙、丙、丁四个区。唯一的例外是C水库与丁区没有地下管道。由于地理位置的差别，各水库通往各区的输水管道经过的涵洞、桥梁、加压站和净水站等设备各不相同，因此该公司对各区的引水管理费（元/千吨）各不相同（见下表）。但是对各区自来水的其他管理费均为45元/千吨，而且对各区用户都按统一标准计费，单价为90元/千吨。目前水库将临枯水期，该公司决策机构正考虑如何分配现有供水量的问题。首先，必须保证居民生活用水和某些重要机关、企业、事业单位用水的基本需求，各区的这部分用水量由下表的“最低需求”行表示，但是拥有一个独立水源的丙区这部分水量可自给自足，无须公司供给。其次，除乙区外，其他三个区都已向公司申请额外再分给如下水量（千吨/天）：甲区：20；丙区：30；丁区要求越多越好，无上限。这部分水量包含于“最高需求”行中。

该公司应如何分配供水量，才能在保障各区最低需求的基础上获利最多？并按要求分别完成下列分析：

（1）水库B供应甲区的引水管理费（元/千吨）在何范围内变化时最优分配方案不变？

（2）水库A的供水量在何范围内变化时最优基不变？

（3）乙区的日供水量为80千吨时的最优分配方案。

3.建模过程：

3.1 设定变量

设X_ij表示从第i个水库输水到第j个区的供水量, 其中i=1、2、3（1、2、3分别代表A、B、C三个水库）；j=1、2、3、4（1、2、3、4分别表示甲、乙、丙、丁四个区）

    设Z为总的饮水管理费;

设Y表示公司的获利。

3.2 根据题意推理

A水库到甲区的饮水管理费为：16X₁₁

    A水库到乙区的饮水管理费为：13X₁₂

A水库到丙区的饮水管理费为：22X₁₃

A水库到丁区的饮水管理费为：17X₁₄

B水库到甲区的饮水管理费为：14X₂₁

    B水库到乙区的饮水管理费为：13X₂₂

B水库到丙区的饮水管理费为：19X₂₃

B水库到丁区的饮水管理费为：15X₂₄

C水库到甲区的饮水管理费为：19X₃₁

    C水库到乙区的饮水管理费为：20X₃₂

C水库到丙区的饮水管理费为：23X₃₃

A水库的供水量为：X₁₁+X₁₂+X₁₃+X₁₄≤50

B水库的供水量为：X₂₁+X₂₂+X₂₃+X₂₄≤60 

C水库的供水量为：X₃₁+X₃₂+X₃₃≤50

甲区的最低需求为：X₁₁+X₂₁+X₃₁≥30

乙区的最低需求为：X₁₂+X₂₂+X₃₂≥70 

丁区的最低需求为：X₁₄+X₂₄≥10

甲区的最高需求为：X₁₁+X₂₁+X₃₁≤50

乙区的最高需求为：X₁₂+X₂₂+X₃₂≤70 

丙区的最高需求为：X₁₃+X₂₃+X₃₃≤30

则得该问题的LP问题为：

MinZ=16 X₁₁+13X₁₂+22X₁₃+17X₁₄+14X₂₁+13X₂₂+19X₂₃+15X₂₄+19X₃₁+20X₃₂+23X₃₃

X₁₁+X₁₂+X₁₃+X₁₄≤50        

  X₂₁+X₂₂+X₂₃+X₂₄≤60       

  X₃₁+X₃₂+X₃₃≤50       

  X₁₁+X₂₁+X₃₁≥30

  X₁₂+X₂₂+X₃₂=70

  X₁₄+X₂₄≥10       

   X₁₁+X₂₁+X₃₁≤50

  X₁₃+X₂₃+X₃₃≤30          

X_ij≥0,i=1,2,3,4 ;j=1,2,3,4

3.3 计算机求解前的手工数据准备

3.3.1数学模型数据准备

将原问题第一、二、三、四、六、七、八个约束条件添加松弛变量X₁、X₂ 、X₃、X₄、X₅、X₆、X₇；    

将原问题第四、五、六个约束条件添加人工变量X₈、X₉、X₁₀；

将问题化为标准形式：

MaxZ=-[16X₁₁+13X₁₂+22X₁₃+17X₁₄+14X₂₁+13X₂₂+19X₂₃+15X₂₄+19X₃₁+20X₃₂+ 23X₃₃]

X₁₁+X₁₂+X₁₃+X₁₄+X₁=50        A水库的供水量

    X₂₁+X₂₂+X₂₃+X₂₄+X₂=60        B水库的供水量

    X₃₁+X₃₂+X₃₃+X₃=50            C水库的供水量

  X₁₁+X₂₁+X₃₁-X₄+X₈=30            甲区的最低需求

    X₁₂+X₂₂+X₃₂+X₉=70            乙区的最低需求

    X₁₄+X₂₄-X₅+X₁₀=10                丁区的最低需求

     X₁₁+X₂₁+X₃₁+X₆=50            甲区的最高需求

    X₁₃+X₂₃+X₃₃+X₇=30            丙区的最高需求

X_ij≥0,X_r≥0,i=1,2,3,4 ;j=1,2,3,4;r=1,2,3,4,5,6,7,8

3.3.2 Lindo 6.1数据准备

在模型编译框内输入原模型的程序规范模式如下：

Min 16X11+13X12+22X13+17X14+14X21+13X22+19X23+15X24+19X31+ 20X32+23X33

SUBJECT TO

X11+X12+X13+X14<=50

X21+X22+X23+X24<=60

X31+X32+X33<=50

X11+X21+X31>=30

X12+X22+X32=70

X14+X24>=10

X11+X21+X31<=50

X13+X23+X33<=30

END

4．程序功能介绍

4.1总体介绍

此问题求解过程，分别运用了C语言和LINDO数学建模软件进行分析。 C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言。C语言有一个突出的优点就是适合于多种操作系统；也适用于多种机型。C语言具有强大的绘图能力，可移植性好，并具备很强的数据处理能力，因此适于编写系统软件，三维，二维图形和动画，它也是数值计算的高级语言。该程序通过C语言编写，表现了运筹学中的如何求解线性规划问题的最优解的方法，该程序运行过程中需要人工输入需要求解的目标函数类型，决策变量的个数、变量的系数、约束条件的个数、约束条件的符号以及变量系数、不等式右端项等。通过输入的数据确定原问题，以及原问题的标准形式，接着程序自行判断是否加入人工变量，进行二阶段法的第一阶段，迭代得出第一阶段的最优表，然后接着进行第二阶段，继续自行迭代，最后得出最优解及最优值。并通过LINDO软件进行灵敏度分析。该程序可以用于解决生活中的运筹学线性规划问题。主要包括研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。当然，随着客观实际的发展，运筹学的许多内容不但研究经济和军事活动，有些已经深入到日常生活当中去了。运筹学可以根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，已达到最好的效果。可用电子计算机来处理成千上万个约束条件和变量的大规模线性规划问题，从解决技术问题的最优化，到工业、农业、商业、交通运输业以及决策分析部门都可以发挥作用。从范围来看，小到一个班组的计划安排，大至整个部门，以至国民经济计划的最优化方案分析，它都有用武之地，具有适应性强，应用面广，计算技术比较简便的特点。

LINDO是一种专门用于求解数学规划问题的软件包。由于LINDO执行速度很快、易于方便输入、求解和分析数学规划问题。因此在数学、科研和工业界得到广泛应用。LINDO主要用于解线性规划、非线性规划、二次规划和整数规划等问题。也可以用于一些非线性和线性方程组的求解以及代数方程求根等。LINDO中包含了一种建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。

4.2程序流程图

4.2.1 第一阶段程序流程图

图1 第一阶段程序流程图

4.2.2 第二阶段程序流程图

图2 第二阶段程序流程图

4.3数据录入

4.3.1 首先选择目标函数类型，注意：输入1代表求max,输入2代表求min;

4.3.2 输入变量个数后，输入变量的系数，注意此处的变量系数是指目标函数中的变量系数；

4.3.3 输入约束条件个数后，选择约束条件符号，注意：输入1代表等于，输入2代表大于等于，输入3代表小于等于；

4.3.4；输入A，注意此处的变量系数是指约束条件中的变量系数；

4.3.5 在进行每步的输入时，一定要按步骤，当输入的数据量大时，注意一定要按照顺序依次输入；

4.4程序运行

由于程序使用的是C语言编写的应用程序，因此整个程序运行输入比较简单，只要准确无误的输入数据，一般都可得到最优解与最优基。程序运行过程如下：

4.4.1 点击运行之后，提示选择目标函数类型，输入1求max,输入2求min；

4.4.2 按回车后，提示输入变量个数，然后依次输入变量系数，每输一个变量按回车一次，然后输入Y确定，如果输入数据错误，则输入N返回重新输入；

4.4.3按回车后，提示输入约束条件个数，然后选择约束条件符号，接着输入约束条件中的变量系数以及右端项值，输入Y确定，同理将所有的约束条件输入；

4.4.4所有的数据输入完毕之后，窗口显示所有输入数据组成的原问题方程组，显示如下图 3：

图3

4.4.5同时程序自动生成原问题的辅助LP问题方程组，如图4：

            

 图4

4.4.6按回车后，程序进行第一阶段迭代迭代，得到第一阶段的结果，得出第二阶段的原问题，如图5：

                                 图5

     4.4.7 按回车后，程序进行第二阶段迭代，迭代后得到最优值和最优解，如图6：

  

 5.结果分析思路：

5.1 参数C的变化

5.1.1 问题（1）中水库B供应甲区的饮水管理费的变化属于LP问题模型中参数C的变化，而此问题中C是基变量X₂₁的系数，则：

    先确定基变量系数变化范围，基变量系数变化影响所有非基变量的检验数和目标函数值。如果Cj的变化范围在基变量Cj增量的变化范围之内则其最优解、最优值均不变；反之如果Cj的变化范围超出基变量Cj增量的变化范围，则需要重新迭代求出最优值。

5.1.2 问题（2）中水库A的供水量变化和问题（4）中乙区供水量的变化都属于LP问题模型中参数b的变化

    根据max{-bi/βir | βir>0}<=b<=min{-bi/βir | βir<0} 确定b的变化范围。

如果b的变化在该范围之内最优基不变最优解变化，最优解由公式X_B=B^-1b求得。

如果b的变化超出该范围最优基最优解均发生变化，重新计算C_BB^-1b、B-1b代入最优表中重新迭代。

5.2问题分析

通过对题目的正确理解和分析，依据题意可以得到在保证各区最低供水量的基础上运费最低，也就是获利最大的模型，以这个模型为基础，可以得到公司分配供水量的最优决策方案。然后通过灵敏度分析（1）水库B供应甲区的引水管理费（元/千吨）在何范围内变化时最优分配方案不变（2）水库A的供水量在何范围内变化时最优基不变（3）乙区的日供水量为80千吨时的最优分配方案。

5.3计算机的求解结果及分析

5.3.1 数据录入，输入变量个数以及变量系数和约束条件个数，依次输入约束条件中变量的系数，以及右端常数项的值，输入确定并回车后可得最优解和最优值。如图 7：

                                   图 7

     由图可知，最优分配供水量方案为：X₁₂=50，X₂₁=30，X₂₂=20，X₂₄=10，其余变量的值为0；即A水库输水到乙区50千吨，B水库输入到甲区30千吨，到乙区20千吨，到丁区10千吨。 此时Min Z=1480，即最低总的饮水管理费为1480元，则最大获利为：Y=（90-45）*（50+30+20+10）-1480=3470（元）

5.4灵敏度分析

5.4.1根据结果分析当目标函数的变量系数在什么变化范围内时，最优基不变。

    VARIABLE    CURRENT       ALLOWABLE      ALLOWABLE

                   COEF          INCREASE         DECREASE

      X11        16.000000         INFINITY         2.000000

      X12        13.000000         0.000000          INFINITY

      X13        22.000000         INFINITY         22.000000

      X14        17.000000         INFINITY         2.000000

      X21        14.000000         2.000000          14.000000

      X22        13.000000         7.000000          0.000000

      X23        19.000000         INFINITY         19.000000

      X24        15.000000         2.000000          15.000000

      X31        19.000000         INFINITY         5.000000

      X32        20.000000         INFINITY         7.000000

      X33        23.000000         INFINITY         23.000000

   其中各列表头释义为，CURRENT  COEF：初始目标函数系数；ALLOWABLE INCREASE：允许变量系数增加的范围；ALLOWABLE  DECREASE：允许变量系数减少的范围。则当目标函数的系数C在 [初始目标函数的系数-允许变量系数减少的范围，初始目函数的系数+允许变量系数增加的范围] 内变化时，最优基不变，最优解也不变，由于目标函数的系数发生改变了，所以最优值有可能改变。

5.4.2根据结果分析约束条件右端项在什么范围内变化时，最优基不变

ROW     CURRENT       ALLOWABLE      ALLOWABLE

                   RHS          INCREASE         DECREASE

        2       50.000000        20.000000          0.000000

        3       60.000000         INFINITY         0.000000

        4       50.000000         INFINITY         50.000000

        5       30.000000         0.000000          30.000000

        6       70.000000         0.000000          20.000000

        7       10.000000         0.000000          10.000000

        8       50.000000         INFINITY         20.000000

        9       30.000000         INFINITY         30.000000

   其中各列表头释义为，CURRENT  RHS：初始约束条件右端项的值；ALLOWABLE  INCREASE：允许b值增加的范围；ALLOWABLE  DECREASE：允许b值减少的范围当约束条件右端项的值在 [初始约束条件右端项的值-允许b值减少的范围，初始约束条件右端项的值+允许b值增加的范围] 内变化时最优基不变，最优解不变。

5.5原问题分析

5.5.1水库B供应甲区的引水管理费（元/千吨）在何变化范围时最优分配方案不变

解：因为水库B供应甲区的饮水管理费为C₂₁，由上列计算结果可得允许变量系数增加的范围为[0，2]，允许变量系数减少的范围[0，14]，所以水库B供应甲区的饮水管理费在[0,16]范围内变化时最优基不变。

5.5.2 水库A的供水量在何范围内变化时最优基不变

解：因为水库A的供水量年是第1个约束条件的右端项，即该问题求的是b1的变化范围，由上列计算结果可得b1变化范围为[0,20]，所以水库A的供水量在[50，70]范围内变化时最优基不变。

5.5.3乙区的日供水量为80千吨时的最优分配方案

   解：：因为乙区的日供水量是第5个约束条件的右端项，将b5改为80然后用Lindo 6.1进行求解得最小总的饮水管理费用minZ= 1660.000，变量取值为X₁₂=50，X₂₁=30，X₂₂=20，X₂₄=10，X₃₁=10，其余变量的值为0；

6.创新内容

6.1运用Lindo 6.1进行灵敏度分析，适用于任何类型的题型，计算容量大，使用这种方法进行计算可以提高计算的准备度，加快计算速度，具有较强的说服力和适应能力，有效地检验计算结果的准备性。除题中问题外，还可可解决其他所有相关的灵敏度分析问题。

6.2 水库B供应丁区的引水管理费（元/千吨）在何范围内变化时最优分配方案不变

解：因为水库B供应乙区的饮水管理费为C₂₄，由上列计算结果可得允许变量系数增加的范围为[0，2]，允许变量系数减少的范围[0，15]，所以水库B供应丁区的饮水管理费在[0,17]范围内变化时最优基不变。

6.3水库A供应乙区的引水管理费（元/千吨）在何范围内变化时最优分配方案不变

解：因为水库A供应甲区的饮水管理费为C₁₂，由上列计算结果可得允许变量系数增加的范围为[0，0]，允许变量系数减少的范围[0，+∞]，所以水库A供应乙区的饮水管理费只有保持不变才能保证最优基不变。

6.4 甲区的最高需求水量为60千吨时的最优分配方案

解：：因为甲区的最高需求水量是第7个约束条件的右端项，将b7改为60然后用Lindo 6.1进行求解得最小总的饮水管理费用minZ= 1660.000，变量取值为X₁₂=50，X₂₁=30，X₂₂=20，X₂₄=10，X₃₁=10，其余变量的值为0；

7.课程设计总结