运筹学之(对偶理论)English.ppt

* 表2.3.1 对偶单纯型法的单纯型表(min) 答：最优解为x1=14, x3=8, x2=x4=0, OBJ=14 习 题 学而时习之，不亦乐乎 — 《论语》 * 用单纯形法求解 1 Min Z =2x1+3x2+x3 x1+4x2+3x2≥8 3x1+2x2 ≥6 x1 , x2 , x3 ≥0 2 Max Z=10x1+15x2+12x3 5x1+3x2+ x3 ≤ 9 -5x1+6x2+15x3≤15 2x1+ x2 + x3 ≥5 x1 , x2 , x3 ≥ 0 * 作业 4 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下： 设司机乘务人员分别在各时间区段一开始上班，并连续8小时工作，问该线路至少配备多少司机乘务员，列出该问题的线性规划模型，用计算机求解该问题。 班次 时间 所需人数 1 2 3 4 5 6 6：00 ~ 10：00 10：00 ~ 14：00 14：00 ~ 18：00 18：00 ~ 22：00 22：00 ~ 2：00 2：00 ~ 6：00 60 70 60 50 20 30 * 作业 5 某厂生产三种产品，ⅰ、ⅱ、ⅲ，每种产品要经过A、B两道工序，设该厂有两种设备能完成A工序，用A1、A2表示；有三种设备可完成B工序，用B1、B2、B3表示，产品ⅰ可在AB任何一种设备上加工；产品ⅱ可在任何A设备上加工，但完成B工序时只能在B1上加工；产品ⅲ只能在A2、B2上加工。 各设备的单件工时、原材料费、产品价格，各设备有效台时及满负荷操作时机床设备的费用如下表所示，问如何安排生产工厂利润最大。 * 设 备 产 品 设备有效台时 (小时) 设备台时总费用 (千元) Ⅰ Ⅱ Ⅲ A1 A2 B1 B2 B3 5 7 6 4 7 10 9 8 12 11 6,000 10,000 4,000 7,000 4,000 300 321 250 783 200 材料费（千元/件） 售 价（千元/件） 0.25 1.25 0.35 2.00 0.50 2.80 * 思考 1 任何线性规划问题存在并具有唯一的对偶问题。 2 对偶问题的对偶一定是原问题； 3 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解； 4 若线性规划问题的原问题有无穷多解，则其对偶问题一定具有无穷多最优解。 * 习题6 1 写出线性规划问题的对偶问题（清华2.3） （1）min z=2x1+2x2+4x3 (2) 2x1+3x2+5x3≥2 2x1+x2+7x3 ≤3 x1+4x2+6x3 ≤5 x1,x2,x3 ≥0 * 任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义 * Weak duality property: lf x is a feasible solution for the primal problem and y is a feasible solution for the dual problem, then Cx ≤ yb. * Strong duality property: If x* is an optimal solution for the primal problem y* is an optimal solution for the dual problem, then Cx* = y*b * Complementary-solutions property: At each iteration, the simplex method simultaneously identifies a CPF solution x for the primal problem and a complementary solution y for the dual problem (found in row 0, the coefficients of the slack variables), where