文档介绍：1-3 单纯形法
方便、有效、通用
图解法的局限性?
1947年美国数学家丹捷格()提出的单纯形法提供了方便、有效的通用算法求解线性规划。
一、单纯形法的基本思想 1、顶点的逐步转移
LP可行域
基本可行解
根据线性规划问题的可行域是凸集(凸多边形或凸多面体),若LP有最优解,就一定可以在可行域的顶点上找到。
于是,若LP只有唯一最优解,这个最优解所对应的点一定是可行域的一个顶点;若LP有多个最优解,那么肯定在可行域的顶点中可以找到至少一个最优解。
顶点转移的依据?
:
(1) 第一个(顶点) 基本可行解怎么找?
(2)如何决定一个基本可行解是不是最优解——最优判断标准是什么?
(3)如果不是最优,怎么从一个基本可行解向下一个基本可行解转移——转移方法?
第二步:寻求初始可行基,确定基变量
对应的基变量是 x3,x4,x5;
第三步:写出初始基本可行解和相应的
目标函数值
两个关键的基本表达式:
①用非基变量表示基变量的表达式
②用非基变量表示目标函数的表达式
请解释结果的经济含义——
不生产任何产品,资源都没有被利用( x3=8,x4=16,x5=12),两种产品的总利润为0!