线性规划课件

线性规划1一、线性规划的引出经济活动中的最优化问题1.最优放牧时间问题（？）2.电器销售中最优保修期问题（？）3.制造业中原材料最省问题（？）第一节线性规划的假设与应用2一、线性规划的引出线性规划（LinearProgramming，LP）是一种用来解决目标函数和约束条件都为线性的最优化问题的方法。求线性目标函数在线性约束条件下的最大值最小值问题，统称线性规划。目标函数：最大化或者最小化目标函数与约束条件都是线性的，即可以用直线表示。第一节线性规划的假设与应用3

企业在追求利润最大化、成本最小化或者期铜目标的过程中，会面临很多约束。如果只有一项约束条件，就可以通过传统办法解决（前两章的内容），例如，在给定的成本约束（等成本线）下实现产出的最大化（即达到给定的等产量线），企业应该在等产量线和等成本线的切点处生产。但是在实际中，企业经常面临着多种约束。第一节线性规划的假设与应用4

例如，在短期或者经营时间段内，企业也许不能雇佣到具有特定专业技能的工人，或者获得更多的某一种原材料，或者必须购买先进的设备，也许受到合同协议的约束要提供最低数量的某种产品，只能在最小数量的小时内让工人劳动，服从某些污染等。在这些约束条件下的最优化问题，传统方法是失效的，而可以应用线性规划方法。第一节线性规划的假设与应用5二、线性规划的应用1、最优流程选择2、最优产品组合3、满足最低产量需求4、长期生产能力计划5、具体应用：第一节线性规划的假设与应用6三、线性规划的求解方法四种方法：1、图解法2、代数法3、单纯形法（矩阵求解）4、计算机求解第一节线性规划的假设与应用7四、线性规划的有关概念

x，y的不等式(或方程)组成的不等式组称为x，y的约束条件。关于x，y的一次不等式或方程组成的不等式组称为x，y的线性约束条件。欲达到最大值或最小值所涉及的变量x，y的解析式称为目标函数。关于x，y的一次目标函数称为线性目标函数。求线性目标函数在线性约束条件下的最大值或最小值问题称为线性规划问题。满足线性约束条件的解（x，y）称为可行解。所有可行解组成的集合称为可行域。使目标函数取得最大值或最小值的可行解称为最优解。第一节线性规划的假设与应用8第二节线性规划的图解法解题的一般过程：依题意,画区域,再把直线来平移,寻找最优在哪里。步骤：

（1）画：画出线性约束条件所表示的可行域；（2）移：在线性目标函数所表示的一组平行线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；（3）求：通过解方程组求出最优解；9第二节线性规划的图解法例1：某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表示：III资源总量设备原材料A原材料B1402048台时16kg12kg

该厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？10第二节线性规划的图解法解：设x1，x2分别表示计划期内产品I、II的产量，依题意可得如下线性规划模型：

目标函数maxz=2x1+3x2

约束条件11108642-2-4-4-224A(4,2)

.....B(2,3)

可行集z=2x1+3x212例2：实际应用

某家具厂有方木料9m3,五合板600m3，准备加工成书桌和书橱，已知每张书桌要方木料0.1m3，五合板2m3，生产每个书橱要方木料0.2m3，五合板1m3，出售一张书桌可获利80元，出售一张书橱可获利120元，如果只安排生产书桌可获利多少，如果只安排生产书橱，可获利润多少？怎样安排生产可使所得利润最大？第二节线性规划的图解法13由上表可知：（1）只生产书桌，用完五合板了，可生产书桌600÷2=300张,可获利润:80×300=24000元,但木料没有用完。（2）只生产书橱，用完方木料，可生产书橱90÷0.2=450张,可获利润120×450=54000元,但五合板没有用完。

产品

资源

书桌（张）

书橱（张）

资源限额

m3

方木料m3

0．1

0．2

90

五合板m3

2

1

600

利润

（元）

80

120

14