9299.net
大学生考试网 让学习变简单
当前位置:首页 >> 工学 >>

第二章第1节图解法求解线性规划问题_图文

第二章第1节图解法求解线性规划问题_图文


第二章 第1节 图解法求解线性规划问题
一、线性规划问题的提出 二、图解法求解线性规划问题

一、线性规划问题的提出
获利50, 例1:工厂每生产一单位产品 获利 ,产品 :工厂每生产一单位产品1获利 2获利 获利100元,资源限制条件如下表所示,如 获利 元 资源限制条件如下表所示, 何组织生产,获利最多。 何组织生产,获利最多。
产品1 产品1 设备 原料A 原料A 原料B 原料B 1 2 0 产品2 产品2 1 1 1 资源限制 300台时 300台时 400kg 250kg

符合“数学建模”的特征。 ? 目标函数——利润 ? 资源限制条件——材料和设备 ? 决策变量——产品的生产数量。 maxZ=50x1+100x2 x1+x2≤300(设备约束) 2x1+x2≤400(材料约束) X2 ≤250 x1,x2≥0

什么是线性规划模型? 什么是线性规划模型?
数学模型中包括三个条件:目标函数、约束 条件和决策变量。 (1)决策变量( x1 ,x2 ,… ,xn ), 每一组值表示一个方案。 (2)决策变量的线性函数形式写出目标函数, 确定最大化或最小化目标。 (3)用一组决策变量的线性等式或不等式表 示解决问题过程中必须遵循的约束条件。

线性规划模型的一般形式
目标函数: 目标函数: Max (Min) z = c1 x1 + c2 x2 + … + cn xn 约束条件: 约束条件:

a11 x1 + a12 x2 + … + a1n xn ≤ ( =, ≥ )b1 a21 x1 + a22 x2 + … + a2n xn ≤ ( =, ≥ )b2

…… …… am1 x1 + am2 x2 + … + amn xn ≤ ( =, ≥ )bm 决策变量: 决策变量: x1 ,x2 ,… ,xn ≥ 0

二、图解法求解线性规划问题
? 对于只有两个决策变量的线性规划问题, 对于只有两个决策变量的线性规划问题, 两个决策变量的线性规划问题 可以在平面直角坐标系上作图表示线性规 划问题的有关概念,并求解。 划问题的有关概念,并求解。 ? 适用范围很小,引出求解线性规划问题的 适用范围很小, 一些规律。 一些规律。

主要步骤
1、分别取决策变量X1 , X2 为坐标向量建立 分别取决策变量X 直角坐标系。每个约束条件都代表一个半平 直角坐标系。 面。 x x
2 2

X2≥0 X1≥0

X1=0 X2=0

x1

x1

对每个不等式(约束条件) 对每个不等式(约束条件),先取其等式在坐 标系中作直线,然后确定不等式所决定的半 标系中作直线, 平面。 平面。
300

200

x1+x2=300

100

100

200

300

x1+x2≤300

主要步骤
2、合并各个半平面的交集部分,找到线性规 合并各个半平面的交集部分, 划问题的可行域。 划问题的可行域。
x2

2x1+x2=400

x2=250 x1+x2=300

x2=0

x1=0 图2-1

x1

3、平行移动目标函数值线,直到目标函数值 取得最优值或者无法达到。
x2

A z=10000=50x1+100x2

B C z=27500=50x1+100x2 z=20000=50x1+100x2 D x1

z=0=50x1+100x2

E

图2-2

图解法观察的结论——针对线性规 图解法观察的结论——针对线性规 —— 划问题的解
1、如果线性规划有最优解,则一定有一个可 行域的顶点对应一个最优解; 2、无穷多个最优解。 3、无界解。即可行域的范围延伸到无穷远, 目标函数值可以无穷大或无穷小。 4、无可行解。可行域为空域,不存在满足约 束条件的解,当然也就不存在最优解。

线性规划问题解的几种情况
? 存在最优解 唯一最优解 和 无穷多最优解 ? 不存在最优解 无界解 和 无最优解


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com