第一章线性规划-模型和图解法

1、线性规划与单纯形法，线性规划与单纯形法，线性规划问题及其数学模型图解法原理单纯形法计算步骤，第一节线性规划问题及其数学模型首先，提出问题，线性规划主要解决如何利用现有有限资源使预期目标达到最佳。工厂应该在计划期间安排生产甲、乙产品(假设产品销售良好)。如表1.1所示，考虑到单位产品的利润以及劳动力、设备和原材料的消耗，工厂应该如何安排生产以实现利润最大化？表1-1，问题需要一个计划(生产多少产品A；生产了多少产品B)，让该工厂生产的产品A和产品B的产量分别为，并确定决策变量，表1-1。制定计划的目标是什么？工厂获得的利润可以表示为：问题的目标：确定目标函数，使利润最大化，表1-1，计划的制定受

2、到以下现实条件的限制：人力资源(劳动力)的限制，设备工作时间的限制，以及原材料资源的限制。此外，决策变量的值不应为负，即确定约束条件，其中目标函数，综上所述，我们得到了该问题的数学模型，并建立了该问题的线性规划模型。1.确定决策变量。决策变量是模型要确定的未知量，也是模型最重要的参数。它用来表明计划中以数量表示的计划和措施可以由决策者决定和控制。2.确定目标函数是将决策者追求的目标表示为决定线性规划优化方向的决策变量的函数。它是线性规划的重要组成部分。3确定约束。这些约束可以用包含决策变量的方程或不等式来表示。美佳公司计划生产两种家用电器。表1-2显示了每台设备制造时占用的表时和调试程序，这两

3、种家用电器的日生产能力，以及每台设备销售时的利润。询问公司应该生产多少件两种家用电器才能使利润最大化。表1-2，它的数学模型是：营养需求的喂养营养：Va是至少700克每天，Vb是至少30克每天，VC是200克每天。有五种饲料，一起使用。饲料成分如下：问：我们应该如何混合饲料以降低成本？上课练习，确定决策变量：设定抓取饲料Ix1kg饲料2公斤。饲料IIIx3kg的目标函数确定如下：minZ=2x1 7x2 4x3 9x4 5x5。约束条件确定如下：3x 12 x 36 x 418 x 5700 x 10.5 x 20.2 x 32 x 40.5 x 5300.5 x 1 x 20.2 x 32

4、x 40.8 x 5=200 x 150，x260，x350，x470。X540 x10、x20、x30、x40、x50、营养要求、剂量要求和非负约束。综上所述，得到以下数学模型：plant 1: productingalumiframandhardware plant 2: productingwoodframesplant 3: productinglassandassembletheproducts，product 1:8 ftglassdoorwithalumiframproduct 2:4 ft6 ft2 hungwood-frame window，Dataneededtobegat

5、hered:1 numberofhoursofproductiontimeavailablespeekineachplantforthesenewproducts，2 numberofhoursofproductiontimeusedineachplanforeachbatchch问题，它的数学模型是：例3:捷运公司计划在未来四个月的四月租用仓库堆放物料。众所周知，每月所需的仓库面积列于下表1-3。仓库的租赁费用取决于合同期限。合同期限越长，折扣越大。具体数字见表1-4。租赁仓库的合同可以在每月初办理，每份合同都规定了租赁的面积和期限。因此，工厂可以根据需要在任何月初处理租赁合同。每次可以签订

6、一份合同，也可以签订几份不同租赁区域和租赁期限的合同。尽量确定公司签订租赁合同的最佳决策，以尽量降低租赁成本。，表1-3，表1-4，单位：100m2，单位：人民币/100m2，表1-2和表1-3，单位：100m2，单位：人民币/100m2，解决方案：假设在i(i=1，2，3，4)月初，MRT签署租赁期限为j(j=1，2，3，4)个月的仓库区域合同(100m2)。经过以上讨论，我们得到了如下的线性规划模型：目标函数，约束，每个问题都有一组变量称为决策变量，一般每个问题都有一组决策变量需要满足的约束线性等式或不等式。对于每组决策变量的值：代表一个决策方案。一般来说，决策变量的值必须是非负的，即2。

7、线性规划问题的数学模型都有一个关于决策变量的线性函数目标函数。该目标函数需要在约束条件下最大化或最小化。我们称约束和目标函数是决策变量线性规划的线性函数的规划问题。有时，线性规划问题也简称为线性规划，它的数学模型是：如果是这样，线性规划问题可以写成矩阵和向量的形式；当用vector表示时，上述模型可以写成：和三。线性规划问题的标准形式是：线性规划问题数学模型的标准形式是：其中线性规划问题的常数项和标准形式的特征是：寻找目标函数的最大值；约束是等式；决策变量是非负的。下面分析如何规范线性规划问题：如果目标函数是，则引入一个新的目标函数，那么的最小值是的最大值，也就是说，因此目标函数被转换为：(2

8、)如果约束条件是不等式，则在两种情况下讨论：增加松弛变量，增加剩余变量，以及(3)对于非负决策变量的要求，在两种情况下讨论：解：引入一个新的目标函数， 因此，原始的线性规划问题被转换成标准形式：例2将线性规划问题转换成标准形式。 例3将线性规划问题转化为标准形式。剩余变量，例4将线性规划问题转换成标准形式。在课堂上练习，将线性规划问题转化为标准形式。我们得到例4的标准形式如下：1.2线性规划问题的图解法，1.2线性规划的图解法，所谓图解法就是在平面直角坐标上画出各约束条件的允许变化范围，并通过图上的运算方法得到最优解和目标函数值。线性规划问题有一个解，这意味着可以找到一组满足所有约束的xj(j

9、=1，2，n)，这组xj被称为问题的可行解。通常，线性规划总是包含多个可行解，所有可行解的集合称为可行域。用图解法求解时，可行域清晰可见。使目标函数值在可行域内最优的可行解称为最优解。对于没有可行解的线性规划问题，这个问题叫做不可解，而图解法的背景知识是从中学知识中知道的：y=ax b是一条直线。同样地(如果Z值是固定的)，Z=70 x1 120 x2，x2=-70/120 x1 Z/120也是一条直线，而x2=-70/120 x1 Z/120也是一组平行等值线。1.2.1图解方法步骤：1。建立直角坐标系；2.根据约束条件描述可行区域；3.制作目标函数的轮廓；4.求解最优和最优目标函数值。一个

10、工厂需要三种资源来生产两种产品。众所周知，每种产品的利润、每种资源的限制和每种产品的资源消耗系数如下：问题：如何安排生产计划以获得最大利润？例1图示法。9080604020、020406080100、x1、x2、9x14x2360、4x15x2200、3x10x10x2300、Z=70 Mazz=70x 1120 x 29 x1 4x 23604 x 15 x 22003 X10 x 2300 x 10 x 20、最优解(20，24)、Z=4280、可行域、课堂实践，用图解法解决下列线性规划问题，1)，3)，2)，1.2.2解决方案的几种可能结果，1。无限最优解。2.独特的最佳解决方案。2.无界解。3.没有解决方案或没有可行的解决方案。解的可能性，多重最优解：无限个最优解唯一的最佳解决方案：只有一个最佳点。无界解：线性规划问题的可行域是无界的，这使得目标函数无限增加且无界。(缺乏必要的约束)，解决的可能性，没有可行的解决方案：如果约束是矛盾的，可行域是一个空集。受图解法启发的解的可能性只能用于求解只有两个变量的线性规划问题，但其解的思想和在几何中直观获得的一些概念判断对单纯形法有很大启示。1.当解决线性规划问题时，解是：唯一的最优解。无限多个最优解；无界解；没有可行的解决办法。2.如果线性规划问题存在可行解，那么可行域就是凸集。3