大学线性规划

摘要本文研究的是线性规划的可行点算法，一个由线性规划的内点算法衍生而来的算法．线性规划的内点算法是一个在线性规划的可行域内部迭代前进的算法．有各种各样的内点算法，但所有的内点算法都有一个共同点，就是在解的迭代改进过程中，要保持所有迭代点在可行域的内部，不能到达边界．当内点算法中的迭代点到达边界时，现行解至少有一个分量取零值．根据线性规划的灵敏度分析理论，对线性规划问题的现行解的某些分量做轻微的扰动不会改变线性规划问题的最优解．故我们可以用一个很小的正数赋值于现行锯中等于零的分量，继续计算，就可以解出线陛规划问题的最优解．这种对内点算法的迭代点到达边界情况的处理就得到了线性规划的可行点算法．它是一个在可行域的内部迭代前进求得线性规划的最优解的算法．在此算法中，只要迭代点保持为可行点．本文具体以仿射尺度算法和原始一对偶内点算法为研究对象，考虑这两种算法中迭代点到达边界的情况，得到相对应的’仿射尺度可行点算法’和’原始．对偶可行点算法，．在用理论证明线性规划的可行点算法的可行性的同时，我们还用数值实验验正了可行点算法在实际计算中的可行性和计算效果．关键词：线性规划，仿射尺度算法，原始一对偶内点算法，内点，可行点算法，步长可行点．ＡｂｓｔｒａｃｔｄｅｒｉｖｅｄＴｈｉｓＤａｐｅｒｆｏｃｕｓｅｓｏｎａｆｅａｓｉｂｌｅｐｏｉｎｔａｌｇｏｒｉｔｈｍｆｏｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ，ａｎａｌｇｏｒｉｔｈｍｆｒｏｍｔｈｅｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｆｏｒｌｉｎｅｚａ＂ｐｒｏｇｒａｍｍｉｎｇ．ＴｈｅｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｆｉｎｄｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｂｙｓｅａｒｃｈｉｎｇｗｉｔｈｉｎｔｈｅｆｅａｓｍｌｅＴｅ譬ｉｏｎｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ．ＴｈｅｒｅａｒｅａＵｋｉｎｄｓｏｆｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｌｒｍａｌｌｔｈｅｆｏｒｌｉｎｅａｒｐｒｏｇｒａｍｎｆｉｎｇ．Ｂｕｔａｌｌｔｈｅｓｅｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｓｈａｒｅａｓｐｅｃｉａｌｉｔｙ，ｗｈｉｃｈｉｓｓｏｌｕｔｉｏｎ｜ｔｅｒａｔｉｖｅＤｏｉｎｔｓｃａｎｎｏｔｒｅａｃｈｔｈｅｂｏｕｎｄｓＡｃｃｏｒｄｉｎｇｔｏｔｈｅｓｅｎｓｉｔｉｖｉｔｙｔｈｅｏｒｙ，ｔｈｅｏｐｔｉｍａｌｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｗｉｌｌｎｏｔｂｅｃｈａｎｇｅｄｂｙｌｉｔｔｌｅｄｉｓｔｕｒｂａｎｃｅｓｏｆｔｈｅｐｒｅｓｅｎｔｓｏｌｕｔｉｏｎ·ＳｏＷｅｌｅｔｔｈｅ｛ｘｊＩｚＪ＝ｏ，Ｊ＝１，２，－··）ｎ）ｅｑｕａｌａｖｅｒｙｓｍａｌｌｐｏｓｉｔｉｖｅｎｕｎｌｂｅｒ，ｇｏｏｎｗｉｔｈｔｈｅｃｏｍｐｕｔａｔｉｏ“一ａｎｄｔｈｅｎｗｅｇｅｔｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ．Ａｌｌｔｈｅｓｅｌｅａｄｔｏｔｈｅｄｅｖｅｌｏｐｍｅｎｔ。

设今年计划修建砖混、壁板、大模住宅各为x 1,x 2,x 3 m2, z 为总面积，则本问题的数学模型为:⎪⎪⎩⎪⎪⎨⎧≥≤++≤≤++≤++≤++++=0,,40000035.0003.00045.0147000210.0150000180.0190.0110.020000025.0030.0012.0110000120.0135.0105.0.3213211321321321321x x x x x x x x x x x x x x x x t s x x x Maxz 注：前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。

Tx x X ),(21=)12,7(=C Tb )300,200,360(=⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=1035449A 回顾例1.1的模型，其中表示决策变量的向量；表示产品的价格向量；表示资源限制向量；问题：为什么A 称为技术系数矩阵？表示产品对资源的单耗系数矩阵。

凸集不是凸集所谓凸集是指：集中任两点的连线仍属此集。

凸集问题：本性质有何重要意义？单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B. Dantzig）提出。

尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。

⎪⎩⎪⎨⎧≥≤+≤+≤++=0,3001032005436049..1272121212121x x x x x x x x t s x x Maxz ⎪⎩⎪⎨⎧≥=++=++=++0,,,,300 10320054360 49..54321521421321x x x x x x x x x x x x x x t s 练习1.3 请将例1.1的约束化为标准型则约束化为易见，增加的松弛变量的系数恰构成一个单位阵I 。

⎩⎨⎧≥≤0..X b AX t s ⎩⎨⎧≥=+0,..s s X X b IX AX t s ⎩⎨⎧≥≥0..X b AX t s ⎩⎨⎧≥=−0,..s s X X b IX AX t s 问题：松弛变量在目标中的系数为何？一般地，记松弛变量的向量为X s ，则（3）自由变量x j进行变量替换：x j = x j '-x j ' ' ，其中x j '、x j ' ' ≥0——0。

线性规划大学毕业论文线性规划是一种优化方法，可应用于许多领域中的决策问题。

它通过确定一组变量的最佳取值，以满足一组约束条件和最大（或最小化）某个线性目标函数。

线性规划在工程、经济学、运筹学和管理科学等领域中都有广泛的应用。

在大学毕业论文中，线性规划可以用来解决一些实际问题。

例如，在运输领域，我们可能需要确定一条最佳路径来最小化航空公司运输成本；在生产计划中，我们可以通过线性规划来优化生产和资源利用率；在金融领域，我们可以使用线性规划来确定最佳的投资组合，以最大化收益或最小化风险。

为了说明线性规划的工作原理，让我们用一个简单的例子来解释。

假设我们有两种产品，产品A和产品B，每个产品所需的生产时间和材料如下：- 产品A需要2小时的生产时间和1个单位的材料- 产品B需要3小时的生产时间和2个单位的材料公司目标是最大化利润，而利润可以通过销售单个产品的利润和每个产品的销售数量来计算。

假设产品A的利润为5美元，产品B的利润为8美元。

此外，我们还有以下的约束条件：- 我们每天最多有10小时的生产时间可用- 我们只有15个单位的材料可用我们可以使用线性规划来确定该如何分配生产时间和材料，以最大化该公司的利润。

我们可以将每个产品的生产数量表示为变量x和y（x表示产品A的生产数量，y表示产品B的生产数量）。

然后，我们可以设置目标函数为利润的总和，即：最大化 5x + 8y接下来，我们需要考虑约束条件。

首先，由于每天最多有10小时的生产时间可用，我们必须满足以下不等式条件：2x + 3y ≤ 10此外，由于只有15个单位的材料可用，我们还必须满足以下不等式条件：x + 2y ≤ 15最后，由于生产数量不能为负数，我们还需要添加以下约束条件：x ≥ 0y ≥ 0将这些条件形成的数学模型进行求解，我们可以得到最佳的生产数量。

通过使用线性规划方法，我们可以确定出最佳的生产计划，以最大化该公司的利润。

总的来说，线性规划在解决实际问题时非常有用。

大学数学易考知识点线性规划与最优化方法线性规划与最优化方法（Linear Programming and Optimization Methods）是大学数学中的一门重要知识点，它在实际问题中有着广泛的应用。

本文将介绍线性规划的基本概念和应用，以及常用的最优化方法。

一、线性规划的基本概念1.1 线性规划的定义线性规划是一种数学建模方法，通过建立数学模型，利用线性关系来描述问题的约束条件和目标函数，从而找到使目标函数达到最大或最小值的最优解。

1.2 线性规划的基本元素线性规划包括约束条件、目标函数和决策变量三个基本元素。

约束条件描述了问题的限制条件，目标函数描述了问题的优化目标，决策变量表示问题中需要决策的变量。

1.3 线性规划的标准形式线性规划的标准形式可以表示为：```max/min z = c₁x₁ + c₂x₂ + ... + cₙxₙsubject toa₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ≥ 0```其中，c₁, c₂, ..., cₙ为目标函数的系数，a₁₁, a₁₂, ..., aₙₙ为约束条件中的系数，b₁, b₂, ..., bₙ为约束条件中的常数，并且x₁, x₂, ..., xₙ为决策变量。

二、线性规划的解法与应用2.1 线性规划的解法线性规划有多种解法，常见的有图解法和单纯形法。

图解法适用于二维平面的线性规划问题，通过构建约束条件的直线和目标函数的等值线，找到最优解。

单纯形法是一种迭代算法，通过不断调整基变量和非基变量的取值，找到使目标函数达到最大或最小值的最优解。

2.2 线性规划的应用线性规划在实际问题中有广泛的应用，例如生产计划、资源分配、运输问题等。

通过建立合适的线性规划模型，可以有效地解决这些问题，优化资源的利用，提高生产效率。

课程名称：运筹学授课班级：XX年级XX班授课时间：2课时授课教师：XX一、教学目标1. 知识目标：（1）理解线性规划的基本概念和数学模型。

（2）掌握线性规划问题的标准形式和约束条件。

（3）学会使用单纯形法求解线性规划问题。

2. 能力目标：（1）培养学生运用线性规划解决实际问题的能力。

（2）提高学生的逻辑思维和数学建模能力。

3. 情感目标：（1）激发学生对运筹学的兴趣。

（2）培养学生严谨求实的科学态度。

二、教学内容1. 线性规划的基本概念2. 线性规划问题的数学模型3. 线性规划问题的标准形式4. 线性规划问题的约束条件5. 单纯形法求解线性规划问题三、教学过程第一课时1. 导入新课（1）介绍线性规划在各个领域的应用，激发学生的学习兴趣。

（2）提出本节课的学习目标。

2. 线性规划的基本概念（1）介绍线性规划的定义、特点和应用。

（2）举例说明线性规划在实际问题中的应用。

3. 线性规划问题的数学模型（1）讲解线性规划问题的目标函数和约束条件。

（2）举例说明如何将实际问题转化为线性规划问题。

4. 线性规划问题的标准形式（1）介绍线性规划问题的标准形式。

（2）讲解如何将线性规划问题转化为标准形式。

第二课时1. 线性规划问题的约束条件（1）讲解线性规划问题的约束条件类型。

（2）举例说明如何处理线性规划问题的约束条件。

2. 单纯形法求解线性规划问题（1）介绍单纯形法的基本原理和步骤。

（2）举例说明如何使用单纯形法求解线性规划问题。

3. 案例分析（1）选取实际案例，引导学生运用所学知识进行分析。

（2）让学生分组讨论，共同解决问题。

4. 总结与回顾（1）总结本节课所学内容，强调重点和难点。

（2）布置课后作业，巩固所学知识。

四、教学评价1. 课堂表现：观察学生的课堂参与度和学习积极性。

2. 课后作业：检查学生对所学知识的掌握程度。

3. 案例分析：评估学生运用线性规划解决实际问题的能力。

五、教学资源1. 教材：《运筹学》2. 教学课件3. 实际案例4. 在线资源（如网络课程、学术论文等）六、教学反思本节课通过理论讲解、案例分析等方法，帮助学生掌握线性规划的基本概念、数学模型和求解方法。

实验课题：（一）线性规划问题1.用lingo求解下列线性规划问题：2. 某班男同学30人、女同学20人，植树。

工作效率（个/人、天）如下表。

如何安排，植树最多？3.某牧场饲养一批动物，平均每头动物至少需要 700g 蛋白质、30g 矿物质和100g 维生素。

现有A、B、C、D、E五种饲料可供选用，每千克饲料的营养成分(单位：g)与价格(单位：元/kg)如下表所示：试求能满足动物生长营养需求又最经济的选用饲料方案。

4.在以色列，为分享农业技术服务和协调农业生产，常常由几个农庄组成一个公共农业社区。

在本课题中的这个公共农业社区由三个农庄组成，我们称之为南方农庄联盟。

南方农庄联盟的全部种植计划都由技术协调办公室制订。

当前，该办公室正在制订来年的农业生产计划。

南方农庄联盟的农业收成受到两种资源的制约。

一是可灌溉土地的面积，二是灌溉用水量。

这些数据由下表给出。

注：英亩-英尺是水容积单位，1英亩-英尺就是面积为1英亩，深度为1英尺的体积；1英亩-英尺≈1233.48立方米。

南方农庄联盟种植的作物是甜菜、棉花和高粱，这三种作物的纯利润及耗水量不同。

农业管理部门根据本地区资源的具体情况，对本联盟农田种植规划制定的最高限额数据由下表给出。

三家农庄达成协议：各家农庄的播种面积与其可灌溉耕地面积之比相等；各家农庄种植何种作物并无限制。

所以，技术协调办公室面对的任务是：根据现有的条件，制定适当的种植计划帮助南方农庄联盟获得最大的总利润，现请你替技术协调办公室完成这一决策。

对于技术协调办公室的上述安排，你觉得有何缺陷，请提出建议并制定新的种植计划。

5．有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下表所示：前舱中舱后舱最大允许载重量（t）2000 3000 1000容积（m3）4000 5400 1000现有三种货物待运，已知有关数据如下表所示：商品数量（件）每件体积（m3/件）每件重量（t/件）运价（元/件）A 600 10 8 1000B 1000 5 6 700C 800 7 5 600又为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。

第六章 线性规划及其解的实现线性规划是目前应用最广泛的一种系统优化方法，它的理论和方法已十分成熟，可以应用于生产计划、物质调运、资源优化配置、地区经济规划等许多实际问题.线性规划最早由前苏联学者L V Kantorovich 于1939年提出，但他的工作当时并未为人所熟知.直到1947年，美国学者G B Danzing 提出求解线性规划最有效的算法-----单纯性算法后，才引起数学家、经济学家和计算机工作者的重视，并迅速发展成为一门完整的学科而得到广泛的应用.利用线性规划建立数学模型也是中国大学生数学建模竞赛中最常用的方法之一.优化模型的一般形式为T n Xx x x X X f z ),,,(),(min 21 == (1)m i X g t s i ,,2,1,0)(.. =≤ (2)其中)(x f 称为目标函数，)(X g i 称为约束条件.只满足式(2)的X 称为可行解；同时满足式(1)、式(2)两式的解*X X =称为最优解.由式(1)、式(2)组成的模型属于约束优化，若只有式(1)就是无约束优化.一般情况下，优化问题都是有约束的，但是如果最优解不是在可行域的边界上，而是在可行域的内部，那么就可以用无约束优化作比较简单的处理.若f ，i g 均为线性函数，优化模型式(1)、式(2)称为线性规划，否则称为非线性规划. 本章主要对线性规划问题及其解的实现作简要介绍.§6.1 线性规划模型形式及其性质线性规划是运筹学的一个重要分支，应用很广.线性规划问题可以描述为求一组非负变量，这些非负变量在一定线性约束的条件下，使一个线性目标函数取得极小(或极大)值的问题.1、线性规划的标准形式目标函数 n n x c x c x c z +++= 2211m in约束条件 ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=+++=+++=+++0,,,2122112222212111212111n mn mn m m n n n n x x x bx a x a x a b x a x a x a b x a x a x a这里n x x x ,,,21 是变量，i ij i b a c ,,都是已知常数，且0≥i b ，约束条件常用..t s 表示.线性规划用矩阵表示就是T n x x x X cX z ),,,(,min 21 ==T n n m ij b b b b n m a A x b AX t s ),,,(),()(,0,..21 =≤=≥=⨯.2、线性规划的一般形式 目标函数 n n x c x c x c z +++= 2211m in约束条件 ⎪⎪⎩⎪⎪⎨⎧+++++++++mn mn m m n n n n b x a x a x a b x a x a x a b x a x a x a )()()(22112222212*********式中的( )可以是关系符号：≤≥=<>,,,,中的任意一个.3、线性规划化为标准形的方法 把线性规划化为标准形：(1)目标函数一律化为求极小(如果是求极大，则利用)m in(m ax z z -⇔化为求极小).(2)对约束条件中b Ax ≤的不等式，利用加入松弛变量的方法化为等式.如果原约束条件中有""b ≥形式的约束，可以在不等式两边同时加负号化为""b -≤的形式.(3)标准形中一般要求0≥i x .如果某个i x 无此约束，可以引入两个新变量''',i i x x ，令'''i i i x x x -=，0,'''≥i i x x ；如果原来的约束为i i l x ≥，可以令i i i l x x -='，0'≥i x .4、线性规划的基本性质 线性规划有以下基本性质：1）若存在可行域，可行域必为凸集； 2）基可行解对应于可行域的顶点；3）若有最优解，必在可行域的顶点取得.§6.2 线性规划问题的数学模型及其解的基本概念1、线性规划问题的数学模型例1 (生产计划问题)某工厂生产甲、乙两种产品，甲产品每生产一件需耗黄铜2kg 、3个工作日、两个外协件，每件可获利润60元；乙产品每生产一件需耗黄铜4kg 、1个工作日、不需外协件，每件可获利润30元，该厂每月可供生产用的黄铜320kg ，总工作日180个，外协件100个.问应怎样安排生产才能使工厂的利润最高？分析问题，建立数学模型.问题：怎样安排生产，即甲、乙两种产品各生产多少才能使工厂的利润最高？用1x ，2x 分别表示甲、乙两种产品生产的件数，该厂追求的目标是获取最高利润，用数学表达式表示为：213060m axx x f +=.由于生产甲、乙产品的件数要受到生产能力的约束，即 黄铜约束：3204221≤+x x ，工作日约束：180321≤+x x ， 外协件约束：10021≤x ， 非负约束：0,21≥x x .这样，该厂生产计划问题就归结为如下数学模型：⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤++=.0,,1002,1803,32042..,3060max 211212121x x x x x x x t s x x f例2 (运输问题)计划由三个粮站1A ，2A ，3A 运输某种粮食至三个加工厂1B ，2B ，3B ，三个粮站的供应量和三个加工厂的需求量以及各供应地至需求地的单位运输价(元/t)如表1所示，试作出运费最省的调运计划方案.表 1问题：如何调运，才能使运费最省？设ij x 表示第i 个粮站到第j 个加工厂的粮食数量(单位：3,2,1,,=j i t )，则总运费3332312322211312112050603040709080120x x x x x x x x x f ++++++++=.从各粮站运出的粮食数量不能超过供应量，20131211=++x x x ，30232221=++x x x ，50333231=++x x x ，同时还要保证各加工厂的需要，25312111=++x x x ，50322212=++x x x ，25332313=++x x x ，而运输量应满足0≥ij x .则上述运输问题的数学模型为⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥=++=++=++=++=++=++++++++++=.0255025503020..2050603040709080120min 332313322212312111333231232221131211333231232221131211ij x x x x x x x x x x x x x x x x x x x t s x x x x x x x x x f从上述两个例子可以看出，虽然两个问题的具体内容和性质不同，但它们都属于优化问题，它们的数学模型都有相同的数学形式，即在一定的线性等式或不等式的条件下，使某一线性函数达到最大(或最小).所谓线性规划问题的数学模型是将实际问题转化为一组线性不等式获等式约束下求线性目标函数的最小(大)值问题.2、解的基本概念对于线性规划问题的标准形式..min ≥==x b Ax t s cx z 其中系数矩阵A 是行满秩的，即)()(n m m A R ≤=，并引入列向量),,2,1(n j P j =表示系数矩阵的列向量.满秩约束条件的解称为线性规划问题的可行解，可行解的全体}0,|{≥==x b Ax x D 称为线性规划问题的可行域.满足目标函数的可行解称为线性规划问题的最优解.系数矩阵A 的任意一个m 阶的可逆方阵B 称为线性规划问题的一个基.显然，A 最多有mn C 个基.基B 中的任意一列向量j P 称为基向量.系数矩阵A 中除基B 外的其余m n -个列向量称为非基向量.显然，选择的基不同，与基对应的非基向量也不尽相同.与基向量j P 对应的变量j x 称为基变量.与非基向量j P 对应的变量j x 称为非基变量.为叙述方便，不妨假设基B 是阵A 的前m 列构成的，即),,,(21m P P P B =，如若不然，则可通过调整变量顺序达到此目的.按上述定义，),,2,1(m j x j =为基变量，),,2,1(n m m j x j ++=为非基变量，记T m B x x x X ),,,(21 =，T n m m N x x x X ),,,(21 ++=，),,,(21n m m P P P N ++=那么约束条件可用分块矩阵表示为b X X N B N B =⎪⎪⎭⎫ ⎝⎛),(令0=N X ，由b BX B =得b B X B 1-= (3) 称⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛=-01b B X X X N B为对应于基B 的基解.很显然，由于m B R =)(，即0||≠B ，所以式(3)的解是惟一的.即对应于某个基的基解是惟一的，从而一个线性规划问题最多有mn C 个基解.若基解满足0≥x ，则称基解为基可行解。

第四章 线性规划问题的计算机求解4.1 有以下线性规划数学问题： max Z=2x l +3 x 2 S.T. x l + x 2≤10 2x l + x 2≥4x l +3 x 2≤24 2x l + x 2≤16x l 、 x 2≥01、 用EXCEL 线性规划求解模板求解该数学模型。

2、 本问题的最优解是什么？此时最大目标函数值是多少？3、 四个约束条件中，哪些约束条件起到了作用？各约束条件的剩余量或松弛量及对偶价格是多少？4、 目标函数中各变量系数在什么范围内变化时，最优解不变？5、 确定各给定条件中的常数项的上限和下限。

解： 1、2、最优解：（3，7），最优值：273、 可变单元格约束对于求最大化的问题，对偶价格=阴影价格松弛量/剩余量对偶价格x l+ x2≤10 0 1.52x l+ x2≥4 9 0x l+3 x2≤24 0 0.52x l+ x2≤16 13 0 因第一、第三个约束条件的松弛量/剩余量为0 ，所以这两个约束条件起到了约束作用。

4、目标函数中各变量系数1≤C1≤32≤C1≤65、常数项8≤b1≤9.2无限≤b2≤1318≤b3≤3013≤b4≤无限4.2 有以下线性规划数学问题：min f=8x l+3 x2S.T. 500x l+100 x2≤12000005x l+4 x2≥60000100x l≥300000x l 、x2≥01、用EXCEL线性规划求解模板求解该数学模型。

2、本问题的最优解是什么？此时最大目标函数值是多少？3、各约束条件的剩余量或松弛量及对偶价格是多少？分别解释其含义。

4、目标函数中各变量系数在什么范围内变化时，最优解不变？5、确定各给定条件中的常数项的上限和下限。

解：本问题无解。

4.3 有以下线性规划数学问题：max Z=x l+2 x2+3 x3- x4S.T. x l+2 x2+3 x3≤152x l+ x2+5 x3≤20x l+2 x2+ x3+ x4≤10x l 、x2、x3、x4≥01、用EXCEL线性规划求解模板求解该数学模型。

课时：2课时教学目标：1. 了解运筹学的基本概念、研究对象和方法；2. 掌握线性规划的基本原理和求解方法；3. 能够运用线性规划解决实际问题。

教学重点：1. 线性规划的基本原理；2. 线性规划的求解方法。

教学难点：1. 线性规划问题的建模；2. 线性规划问题的求解。

教学过程：一、导入1. 介绍运筹学的基本概念和研究对象；2. 引入线性规划，说明其在实际生活中的应用。

二、基本概念1. 运筹学：是一门研究如何合理地使用人力、物力和财力等资源，以达到最佳效果的学科；2. 线性规划：是运筹学的一个重要分支，主要研究线性目标函数在一系列线性约束条件下的最优解。

三、线性规划的基本原理1. 目标函数：线性规划中的目标函数为线性函数，表示为f(x) = c1x1 + c2x2 + ... + cnxn，其中c1, c2, ..., cn为常数，x1, x2, ..., xn为决策变量；2. 约束条件：线性规划中的约束条件为线性不等式或等式，表示为Ax ≤ b或Ax = b，其中A为系数矩阵，x为决策变量，b为常数向量。

四、线性规划的求解方法1. 图解法：适用于二维线性规划问题；2. 单纯形法：适用于高维线性规划问题。

五、案例分析1. 引入一个实际案例，如生产问题、运输问题等；2. 对案例进行分析，建立线性规划模型；3. 运用线性规划求解方法求解案例，得出最优解。

六、总结与作业1. 总结本节课所学内容，强调线性规划的基本原理和求解方法；2. 布置作业，要求学生运用所学知识解决实际问题。

教学反思：1. 在讲解线性规划的基本原理和求解方法时，注意与实际生活相结合，提高学生的学习兴趣；2. 在案例分析环节，尽量选取具有代表性的案例，让学生更好地理解线性规划的应用；3. 在作业布置环节，注意难度适中，让学生在完成作业的过程中巩固所学知识。

《线性规划》教学大纲课程简介：线性规划是数学教育本科专业必修的一门主要专业基础课，它是近六十年来才逐步发展起来的一门新兴的数学课程，具有广泛的应用背景。

目前，线性规划已广泛应用于工业、农业、商业、国防、交通运输、能源、水利、经济、管理决策等众多领域，它可以解决各行业中的最优计划、最优分配、最优管理、最优决策等最优问题。

通过本课程的学习，使学生掌握线性规划的主要模型、基本理论、主要算法和实际应用，学会解决线性规划模型的求解问题、线性规划对偶理论、运输问题、分配问题等，从而为学生今后进一步深造打基础以及提高学生运用所学知识解决实际问题的能力。

一、教学目标1、知识水平教学目标线性规划课程的教学，应使学生系统掌握线性规划基本模型的功能和特点，熟悉其建模条件、步骤及相应的技巧，能根据实际背景抽象出适当的线性规划模型，着重掌握线性规划基本模型的建立、求解方法以及基本原理，并为学习其他应用数学课程如运筹学打下基础。

2、能力培养目标通过线性规划课程教学,应注意培养学生以下能力：（1）掌握线性规划的基本概念、基本定理与分析方法，掌握线性规划的主要模型；（2）掌握线性规划基本模型的功能和特点，熟悉其建模条件、步骤及相应的技巧，能根据实际背景抽象出适当的线性规划模型；（3）熟练掌握各种模型特别是确定性模型的求解方法，并能对求解结果作简单分析。

（4）掌握与基本模型有关的基本概念及基本原理，做到思路清晰、概念明确；（5）具有初步运用线性规划的思想和方法，去分析解决实际问题的能力和创新思维与应用的能力。

3、素质培养目标通过线性规划课程教学,应注重培养学生以下素质：培养学生利用数学知识及相关专业知识建立数学模型分析、解决实际问题的能力，并从中培养和提高学生的创新意识、创新能力及综合应用能力。

二、教学重点与难点1、教学重点：线性规划的基本模型、基本理论、基本方法。

2、教学难点：线性规划单纯形法、对偶问题、灵敏度分析、平衡运输问题的表上作业法、分配问题等。

第一章线性规划与单纯形法1．线性规划问题的数学模型(1)一般形式(2)标准型式]2．数学模型化为标准型(1)若目标函数实现最小化，则min z=-max z'(令z'=-z)(2)若约束方程为不等式，则若约束方程为“≤”不等式左端+松驰变量(≥0)=右端若约束方程为“≥”不等式左端-剩余变量(≥0)=右端(3)若存在取值无约束的变量x k(1≤k≤咒)，则在标准型中x k=x'k-x"k(其中x k=x'，x"k≥0)3．线性规划的解线性规划问题：(1)可行解：满足约束条件②和③的解X=(x1，x2，…，x n)T。

(2)最优解：使目标函数①达到最大值的可行解。

(3)基：设A为约束方程组②的m×n阶系数矩阵，设n＞m，其秩为m，B 为矩阵A中的一个m×m阶的满秩子矩阵，则称B为线性规划问题的一个基。

不失一般性，设B中每一个列向量P j(j=1，2，…，m)称为基向量，与基向量PJ对应的变量x j称为基变量。

除基变量以外的变量为非基变量。

(4)基本解：在约束方程组②中，令所有非基变量x m+1=x m+2=…=x n=0，此时方程组②有唯一解X B=(x1，x2，…，x m)T，将此解加上非基变量取0的值有X=(x1，x2，…，x m，0，0…，0)T，称X为线性规划问题的基本解。

(5)基本可行解：满足非负条件③的基本解。

(6)可行基：对应于基本可行解的基。

4．初始基可行解的确定(1)直接从A中观察到存在一个初始可行基。

(2)对所有约束条件是“≤”形式的不等式，可利用化为标准型的方法，在每个约束条件左端加上一个松弛变量，这m个松弛变量就构成一个基变量，则对应的m个向量组成的单位矩阵B就是线性规划问题的一个可行基。

(3)对所有约束条件是“≥”形式的不等式以及等式约束情况，采用人造基的方法。

即对不等式约束的左端减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束的左端再加上一个非负的人工变量。

第四章 线性规划问题的计算机求解4.1 有以下线性规划数学问题： max Z=2x l +3 x 2 S.T. x l + x 2≤10 2x l + x 2≥4x l +3 x 2≤24 2x l + x 2≤16x l 、 x 2≥01、 用EXCEL 线性规划求解模板求解该数学模型。

2、 本问题的最优解是什么？此时最大目标函数值是多少？3、 四个约束条件中，哪些约束条件起到了作用？各约束条件的剩余量或松弛量及对偶价格是多少？4、 目标函数中各变量系数在什么范围内变化时，最优解不变？5、 确定各给定条件中的常数项的上限和下限。

解： 1、2、最优解：（3，7），最优值：273、 可变单元格约束对于求最大化的问题，对偶价格=阴影价格松弛量/剩余量对偶价格x l+ x2≤10 0 1.52x l+ x2≥4 9 0x l+3 x2≤24 0 0.52x l+ x2≤16 13 0 因第一、第三个约束条件的松弛量/剩余量为0 ，所以这两个约束条件起到了约束作用。

4、目标函数中各变量系数1≤C1≤32≤C1≤65、常数项8≤b1≤9.2无限≤b2≤1318≤b3≤3013≤b4≤无限4.2 有以下线性规划数学问题：min f=8x l+3 x2S.T. 500x l+100 x2≤12000005x l+4 x2≥60000100x l≥300000x l 、x2≥01、用EXCEL线性规划求解模板求解该数学模型。

2、本问题的最优解是什么？此时最大目标函数值是多少？3、各约束条件的剩余量或松弛量及对偶价格是多少？分别解释其含义。

4、目标函数中各变量系数在什么范围内变化时，最优解不变？5、确定各给定条件中的常数项的上限和下限。

解：本问题无解。

4.3 有以下线性规划数学问题：max Z=x l+2 x2+3 x3- x4S.T. x l+2 x2+3 x3≤152x l+ x2+5 x3≤20x l+2 x2+ x3+ x4≤10x l 、x2、x3、x4≥01、用EXCEL线性规划求解模板求解该数学模型。