线性规划基础知识.ppt

将目标函数转换成极小化，并分别对约束（1）、（2）引进松弛变量x4，x5，得到以下标准形式的线性规划问题： 3.3 变量无符号限制的问题 在标准形式中，每一个变量都有非负约束。当一个变量 没有非负约束时，可以令 ： 其中 即用两个非负变量之差来表示一个无符号限制的变量，当 的符号取决于 和 的大小。 例: 将以下线性规划问题转化为标准形式 x1,x3≥0,x2无符号限制 * * 线性规划 Linear Programming §1 线性规划发展简史 线性规划问题最早是前苏联学者康德洛维奇（L.V. Kantorovich）于1939年提出的。 1952年，美国国家标准局（NBS）在当时的SEAC电子计算机上首次实现单纯形算法。 1976年IBM研制成功功能十分强大、计算效率极高的线性规划软件MPS，后来又发展成为更为完善的MPSX。 线性规划是目前应用最广泛的一种系统优化方法。 LP研究两类问题 一类是当一项任务确定后，如何统筹安排，尽量做到以最少的人力、物力资源去完成。 另一类是已有一定数量的人力、物力资源，如何安排使用它们，使完成的任务（或创造的财富、利润）最多。 §2 线性规划问题 根据实际问题的要求，可以建立线性规划问题数学模型。线性规划问题由目标函数和约束条件两部分组成。 2.1 生产计划问题 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 用线性规划制订使总利润最大的生产计。 设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型： 这是一个典型的利润最大化的生产计划问题。求解这个线性规划，可以得到最优解为： x1=293.6，x2=1500，x3=0，x4=58.84 （件） 最大利润为： z=12734.41（元） 请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。 2.2 配料问题 某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示： 设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T1，T2，T3和T4各多少公斤，使成本最小。 设选用原料T1，T2，T3和T4分别为x1，x2，x3，x4公斤，根据条件，可建立相应的线性规划模型如下： 这是一个典型的成本最小化的问题。这个线性规划问题的最优解是 x1=26.58，x2=31.57，x3=41.84，x4=0（公斤） 最低成本为 z=9549.87（元） 2.3 背包问题 一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示： 要在背包中装入这三种物品各多少件，使背包中的物品价值最高。 设装入物品1，物品2和物品3各为x1，x2，x3件，由于物品的件数必须是整数，因此背包问题的线性规划模型是一个整数规划问题： 这个问题的最优解是：x1=5(件), x2=0(件), x3=0(件), 最高价值为：z=85（元） 2.4 运输问题 设某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地的单位物资运价如下表所示。 设xij为从供应地 Ai 运往需求地 Bj 的物资数量（i=1,2；j=1,2,3），z为总运费，则总运费最小的线性规划模型为： xij≥0 以上约束条件（1）、（2）称为供应地约束，（3）、（4）、（5）称为需求地约束。 这个问题的最优解为： x11=0， x12=30， x13=5（吨）； x21=10, x22=0, x23=15（吨）。 最小运费为：z=275元。 2.5 指派问题 有n项任务由n个人去完成，每项任务交给一个人，每个人都有一项任务。由第i个人去做第j项任务的成本（或效益）为cij。求使总成本最小（或效益最大）的分配方案。 设： 得到以下的线性规划模型： 例如，有张、王、李、赵4位教师