2线性规划和单纯形法.pptVIP

第一章 线性规划与单纯形方法 ;复习： 线性规划问题的提出 线性规划模型的特点 线性规划模型的一般形式与标准形式 如何将一般形式化为标准形式;例1.3 将下列问题化成标准型: Min S = -x1+2x2-3x3 s.t. x1+x2+x3 ? 7 x1-x2+x3 ? 2 -3x1+x2+2x3 = 5 x1,x2 ? 0 x3 无非负限制 ; Max S ? = x1-2x2+3x3 ? -3x3 ? s.t. x1+x2+x3 ? -x3 ? +x4 =7 x1-x2+ x3 ? -x3 ? -x5=2 -3x1+x2+2x3 ? -2x3 ? =5 x1, x2 , x3 ?，x3 ?, x4，x5 ? 0;1-2 线性规划的图解法;例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E) 得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500 ; (1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。;（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。;（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。;（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。 ;;线性规划的图解;例1.5 max S=50x1+30x2 s.t. 4x1+3x2 ? 120 2x1+x2 ? 50 x1, x2 ? 0 ;;;;;;;图解法求解步骤;练习： 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 ? 8 4x1 ? 16 4x2 ? 12 x1、 x2 ? 0 ;9 — 8 — 7 — 6 — 5 — 4 — 3 — 2 — 1 — 0 ;9 — 8 — 7 — 6 — 5 — 4 — 3 — 2 — 1 — 0 ;9 — 8 — 7 — 6 — 5 — 4 — 3 — 2 — 1 — 0 ;9 — 8 — 7 — 6 — 5 — 4 — 3 — 2 — 1 — 0 ;9 — 8 — 7 — 6 — 5 — 4 — 3 — 2 — 1 — 0 ;例 某公司由于生产需要，共需要A，B两种原料至少350 吨（A，B两种材料有一定替代性），其中A原料至少购进125 吨。但由于A，B两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？;解：目标函数： Min f = 2x1 + 3 x2 约束条件： s.t. x1 + x2 ≥ 350 x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0 采用图解法。如下图：得Q点坐标（250，1