运筹与决策最优解问题.docVIP

A库货物12吨，B库货物8吨，分别按7吨，8吨，5吨调运给甲，乙，丙三个商店，从A库 到商店甲，乙，丙，每吨运费分别为8元，6元，9元，从B库到甲，乙，丙三店运费分别为3元，4元，5元，问如何调度，才能使两库货物到三个商店的运费最少。 设从A库运到商店甲，乙，丙分别为X11、X12、X13，设从B库运到商店甲，乙，丙分别为X21、X22、X23。 则有目标方程min Z=8*X11+6*X12+9*X13+3*X21+4*X22+5*X23 条件：X11+X12+X13=12（A库货物12吨） X21+X22+X23=8（B库货物12吨） X11+X21=7（甲商店7吨） X12+X22=8（乙商店8吨） X13+X23=5（丙商店5吨） 求解方程可得X11=0、X12=8、X13=4，X21=7、X22=0、X23=1，总费用为110元，最小。如下所示。 甲 乙 丙 A 0 8 4 B 7 0 1 法二：从运费来看，甲仓库8元，6元，9元，乙仓库3元，4元，5元。6比8和9少2和3，而3比4和5少1和2，从最小值出发，首先分配给6元得乙商店全值8吨，那么乙商店已满，甲仓库还剩4吨。 但是剩下8元、9元和3元和5元对比，9比8大1，5比3大2，从最小值出发， 把甲剩下的4吨给丙，那么5元得吨数就少，总费用小。然后得到如下结果： 甲 乙 丙 A 0 8 4 B — — — 根据守恒，填完B仓库这一列，即得到结果。 运筹学期末复习总结（二）线性规划问题求解 (2011-01-07 00:05:11) 标签： 宋体 可行解 最优解 图解法 线性规划 教育 分类： 学习 第一部分 线性规划问题的求解 ? 一、两个变量的线性规划问题的图解法： ㈠概念准备： 定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。 定义：达到目标的可行解为最优解。 ㈡图解法： 图解法采用直角坐标求解：x1——横轴；x2——竖轴。 1、将约束条件（取等号）用直线绘出； 2、确定可行解域； 3、绘出目标函数的图形（等值线），确定它向最优解的移动方向； 注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。 4、确定最优解及目标函数值。 ㈢参考例题：（只要求下面这些有唯一最优解的类型） 例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示： ? 品 产 耗 消 备 设 ? A B C 利润 （万元） 甲 乙 3 5 9 9 5 3 70 30 有效总工时 540 450 720 —— 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？ （此题也可用“单纯形法”或化“对偶问题”用大M法求解） ? 解：设x1、x2为生产甲、乙产品的数量。 ? ⑴ max z = 70x1+30x2 ? ? ⑵ s.t. ? ? ⑸、⑹ ⑷ ⑶ ? ? 可行解域为oabcd0，最优解为b点。 由方程组 解出x1=75，x2=15 ∴X*= =（75，15）T ∴max z =Z*= 70×75+30×15=5700 ? 例2：用图解法求解 ? ⑴ max z = 6x1+4x2 ? ? ⑵ s.t. ? ? ⑸、⑹ ⑷ ⑶ ? 解： ? 可行解域为oabcd0，最优解为b点。 由方程组 解出x1=2，x2=6 ∴X*= =（2，6）T ∴max z = 6×2+4×6=36 ? 例3：用图解法求解 ? ⑴ min z =－3x1+x2 ? s.t. ? ⑵ ⑶ ⑷ ⑸ ⑹、⑺ ? 解： ? 可行