目录
一、填空题
二、计算题
线性规划问题及其数学模型
线性规划模型的标准型及其转化
线性规划问题的图解法
单纯形法
单纯形法的表格形式
大M法
两阶段法
由线性规划问题转化为其对偶模型
对偶问题的最优解和最优值
由对偶问题最优解找原问题最优解和最优值
影子价格
对偶单纯形法
灵敏度分析
运输问题及其解法
目标规划的数学模型
目标规划问题求解
一、填空题❃运筹学的工作程序:分析和表述问题、建立模型、求解模型和优化方案、测试模型及对模型进行必要的修正、建立对解的有效控制、方案的实施。
❃
❃
❃不可行解:最终表的基变量中含人工变量; 如:
❃无限界解 如:
❃退化解:LP问题的基本可行解中非零变量的个数少于约束 条件数,也就是有基变量的取值为0。 如:
❃多重解:有非基变量的检验数等于0。 如:
❃满足非负约束条件的基本解为基可行解
❃对偶理论基本性质: 对称定理:对偶问题的对偶是原问题。 弱对偶性定理:若和分别是原问题(1)及对偶问题(2)的可行解,则有 最优性定理:若和分别是(1)和(2)的可行解,且有,则,分别是(1)和(2)的最优解 对偶定理(强对偶性):若原问题有最优解,那么对偶问题也有最优解,且两者的目标函数值相等 互补松弛性:若分别是原问题(1)及对偶问题(2)的可行解,分别为(1),(2)的松弛变量,则为最优解。
❃从若对偶性判断: ①极大化问题(原问题)的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。 ②极小化问题(对偶问题)的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。 ③若原问题可行,但其目标函数值无界,则对偶问题无可行解。 ④若对偶问题可行,但其目标函数值无界,则原问题无可行解。 ⑤若原问题有可行解而其对偶问题无可行解,则原问题目标函数值无界。 ⑥若原问题无可行解,则其对偶问题具有无界解或无可行解。
❃影子价格的经济意义: ① 影子价格是一种边际价格 ② 影子价格是一种机会成本 ③ 在生产过程中如果某种资源未得到充分利用时,该种资源的影子价格为零;又当资源的影子价格不为零时,表明该种资源在生产中已耗费完毕。
二、计算题 线性规划问题及其数学模型❃
❃
❃ 解:
线性规划模型的标准型及其转化❃ 例:
❃ 解:
线性规划问题的图解法❃
❃ 解:
单纯形法❃ 解:
❃
单纯形法的表格形式❃ 解:
❃ 解:
大M法❃ 解:
两阶段法❃
由线性规划问题转化为其对偶模型❃ max→min遵循:内同外异;min→max遵循内异外同。
对偶问题的最优解和最优值❃ 解:
由对偶问题最优解找原问题最优解和最优值❃ 解:
影子价格❃ 解:
对偶单纯形法❃ 解: 区别:单纯形表格法是先求最大,再求最小,其中为b与主列相除,迭代即可 对偶单纯形法是找b最小值作为主行,再求最小,其中为分别与主行负元素相除。
灵敏度分析❃ 解:
❃ 解:
❃ 解:
❃ 解: 则其最优解和最优值为:
运输问题及其解法❃
解:
❃
解:
❃
解:
❃ 解:
目标规划的数学模型❃ 解:
目标规划问题求解❃
解:
❃
解: