用表格法解线性规划问题线性规划问题的标准形式.pptx

线性规划中的有关概念线性规划中的有关概念名 称意 义线性约束条件线性约束条件线性约束条件线性约束条件线性目标函数线性目标函数线性目标函数线性目标函数线性规划问题线性规划问题线性规划问题线性规划问题可行解可行解可行解可行解可行域可行域可行域可行域最优解最优解最优解最优解关于决策变量的一组一次不等式关于决策变量的一组一次不等式关于决策变量的一组一次不等式关于决策变量的一组一次不等式(或方程或方程或方程或方程)欲求得最大值或最小值的关于决策变量的欲求得最大值或最小值的关于决策变量的欲求得最大值或最小值的关于决策变量的欲求得最大值或最小值的关于决策变量的一次函数一次函数一次函数一次函数满足线性约束条件的解满足线性约束条件的解满足线性约束条件的解满足线性约束条件的解在线性约束条件下求线性目标函数最大值在线性约束条件下求线性目标函数最大值在线性约束条件下求线性目标函数最大值在线性约束条件下求线性目标函数最大值或最小值的问题或最小值的问题或最小值的问题或最小值的问题约束条件所表示的平面区域约束条件所表示的平面区域约束条件所表示的平面区域约束条件所表示的平面区域可行域中使目标函数取得最大值或最小值可行域中使目标函数取得最大值或最小值可行域中使目标函数取得最大值或最小值可行域中使目标函数取得最大值或最小值的可行解的可行解的可行解的可行解第1页/共14页解线性规划问题：解线性规划问题：xyo可行域如图：可行域如图：把把zx0.5y变形为变形为y2x2z，它表示在它表示在y轴上的截距为轴上的截距为2z的一组直线的一组直线由图可知，当直线经过可行域上的点由图可知，当直线经过可行域上的点M时，时，y轴上截距轴上截距2z最大，最大，得得z最大最大 M由方程组由方程组 求得求得M点的坐标为点的坐标为(2,2)，则则max z3第2页/共14页解线性规划问题的步骤：（2）移：在线性目标函数所表示的一组平行 线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；（3）求：通过解方程组求出最优解；（4）答：作出答案（1）画：画出线性约束条件所表示的可行域；第3页/共14页求函数求函数zxy在平面区域在平面区域 的取值范围的取值范围 xOyABC第4页/共14页 根据前面问题可知：线性规划问题有不同的形式根据前面问题可知：线性规划问题有不同的形式目标函数有求最大值的，也有求最小值的；目标函数有求最大值的，也有求最小值的；约束条件可能是约束条件可能是“”，也可能是，也可能是“”为了便于统一讨论，需要规定线性规划问题的标准形式为了便于统一讨论，需要规定线性规划问题的标准形式第5页/共14页 根据前面问题可知：线性规划问题有不同的形式根据前面问题可知：线性规划问题有不同的形式目标函数有求最大值的，也有求最小值的；目标函数有求最大值的，也有求最小值的；约束条件可能是约束条件可能是“”，也可能是，也可能是“”为了便于统一讨论，需要规定线性规划问题的标准形式为了便于统一讨论，需要规定线性规划问题的标准形式线性规划线性规划问题的标准形式问题的标准形式:第6页/共14页 线性规划问题的标准形式的特点：线性规划问题的标准形式的特点：(1)目标函数为最大值形式；目标函数为最大值形式；(2)约束条件用等式表示；约束条件用等式表示；(3)约束条件等式右侧非负；约束条件等式右侧非负；(4)决策变量非负决策变量非负线性规划线性规划问题的标准形式问题的标准形式:第7页/共14页 如果线性规划问题不是标准形式怎么办？如果线性规划问题不是标准形式怎么办？(1)对于目标函数，对于目标函数，如果是如果是 则令则令 就得到就得到第8页/共14页人工变量 如果线性规划问题不是标准形式怎么办？如果线性规划问题不是标准形式怎么办？(2)对于约束条件中的不等式，对于约束条件中的不等式，如果是如果是“”，如果是如果是“”，松弛变量 由于人工变量并不产由于人工变量并不产由于人工变量并不产由于人工变量并不产生效益，规定其在目标生效益，规定其在目标生效益，规定其在目标生效益，规定其在目标函数中的系数为函数中的系数为函数中的系数为函数中的系数为0 0则在左端加上一个变量使其成为等式；则在左端加上一个变量使其成为等式；则在左端减去一个变量使其成为等式则在左端减去一个变量使其成为等式第9页/共14页 如果线性规划问题不是标准形式怎么办？如果线性规划问题不是标准形式怎么办？(3)对于约束条件，对于约束条件，如果是如果是 则在不等式（或等式）两边同乘以则在不等式（或等式）两边同乘以1第10页/共14页 将下列线性规划问题化为标准形式：将下列线性规划问题化为标准形式：解：解：用变量用变量x1,x2分别取代分别取代 x,y，在约束条件中分别加入人工变量在约束条件中分别加入人工变量x3,x4，令令 ,哪些地方哪些地方不符合要求不符合要求？不等式不等式2x4y7两边同乘以两边同乘以1，得得第11页/共14页 将下列线性规划问题化为标准形式：将下列线性规划问题化为标准形式：第12页/共14页线性规划问题的标准形式的特点：线性规划问题的标准形式的特点：(1)目标函数为最大值形式；目标函数为最大值形式；(2)约束条件用等式表示；约束条件用等式表示；(3)约束条件等式右侧非负；约束条件等式右侧非负；(4)决策变量非负决策变量非负线性规划线性规划问题的标准形式问题的标准形式:第13页/共14页谢谢您的观看！第14页/共14页