OR-03-补充运输问题对偶物理意义.pdf

Introduction to Operations Research 1 Huangang Wang Tsinghua University 运输问题对偶变量的物理意义 11 1 1 min s t 1 1 0 1 1 mn ijij ij n iji j m ijj i ij c x xaim xbjn ximjn Introduction to Operations Research 2 Huangang Wang Tsinghua University 运输问题对偶变量的物理意义 11 1 1 min s t 1 1 0 1 1 mn ijij ij n iji j m ijj i ij c x xaim xbjn ximjn 对偶变量 1 1 i j im jn Introduction to Operations Research 3 Huangang Wang Tsinghua University 运输问题对偶变量的物理意义 11 1 1 min s t 1 1 0 1 1 mn ijij ij n iji j m ijj i ij c x xaim xbjn ximjn 首选不考虑产销是否平衡 分析对偶变量物理意 义首先遇到的难题是 对 和 无非负性限制 对偶变量 1 1 i j im jn i j Introduction to Operations Research 11 1 1 min s t 1 1 0 1 1 mn ijij ij n iji j m ijj i ij c x xaim xbjn ximjn 4 Huangang Wang Tsinghua University 将等式约束放松 Introduction to Operations Research 11 1 1 min s t 1 1 0 1 1 mn ijij ij n iji j m ijj i ij c x xaim xbjn ximjn 5 Huangang Wang Tsinghua University 将等式约束放松 产量有限 满足需求 Introduction to Operations Research 6 Huangang Wang Tsinghua University 如上线性规划问题等价于 11 1 1 min s t 1 1 0 1 1 mn ijij ij n iji j m ijj i ij c x xaim xbjn ximjn 对偶变量 1 1 i j im jn Introduction to Operations Research 7 Huangang Wang Tsinghua University 如上线性规划问题等价于 11 1 1 min s t 1 1 0 1 1 mn ijij ij n iji j m ijj i ij c x xaim xbjn ximjn 对偶变量 1 1 i j im jn 11 max nm jjii ji ba 对偶问题的目标函数 约束条件 1 10 i ji j ij c imjn Introduction to Operations Research 8 Huangang Wang Tsinghua University 对偶问题的物理解释 11 max s t 0 1 1 nm jjii ji jiij ij ba c imjn 货物在销地与产地售价差最大 销地与产地单价差受限于运费 Introduction to Operations Research 9 Huangang Wang Tsinghua University 对偶问题的物理解释 11 max s t 0 1 1 nm jjii ji jiij ij ba c imjn 某公司在A B两地有销售部 货物在A地滞销 在 B地供不应求 如何规划A B两地货物价格 才能 使得该公司所获总体利益最大化 货物在销地与产地售价差最大 销地与产地单价差受限于运费 Introduction to Operations Research 10 Huangang Wang Tsinghua University 对偶问题的物理解释 11 max s t 0 1 1 nm jjii ji jiij ij ba c imjn 某公司在A B两地有销售部 货物在A地滞销 在 B地供不应求 如何规划A B两地货物价格 才能 使得该公司所获总体利益最大化 对应物理问题为 某物流公司发现B地的货物短缺 而A地滞销 如何安排运输以便在满足B地需求前 提下使总运费最小化 货物在销地与产地售价差最大 销地与产地单价差受限于运费 Introduction to Operations Research 11 Huangang Wang Tsinghua University 原运输问题与松弛问题之间的关系 11 1 1 min s t 1 1 0 1 1 mn ijij ij n iji j m ijj i ij c x xaim xbj