简单的线性规划中可行域的确定

摘要本文研究的是线性规划的可行点算法，一个由线性规划的内点算法衍生而来的算法．线性规划的内点算法是一个在线性规划的可行域内部迭代前进的算法．有各种各样的内点算法，但所有的内点算法都有一个共同点，就是在解的迭代改进过程中，要保持所有迭代点在可行域的内部，不能到达边界．当内点算法中的迭代点到达边界时，现行解至少有一个分量取零值．根据线性规划的灵敏度分析理论，对线性规划问题的现行解的某些分量做轻微的扰动不会改变线性规划问题的最优解．故我们可以用一个很小的正数赋值于现行锯中等于零的分量，继续计算，就可以解出线陛规划问题的最优解．这种对内点算法的迭代点到达边界情况的处理就得到了线性规划的可行点算法．它是一个在可行域的内部迭代前进求得线性规划的最优解的算法．在此算法中，只要迭代点保持为可行点．本文具体以仿射尺度算法和原始一对偶内点算法为研究对象，考虑这两种算法中迭代点到达边界的情况，得到相对应的’仿射尺度可行点算法’和’原始．对偶可行点算法，．在用理论证明线性规划的可行点算法的可行性的同时，我们还用数值实验验正了可行点算法在实际计算中的可行性和计算效果．关键词：线性规划，仿射尺度算法，原始一对偶内点算法，内点，可行点算法，步长可行点．ＡｂｓｔｒａｃｔｄｅｒｉｖｅｄＴｈｉｓＤａｐｅｒｆｏｃｕｓｅｓｏｎａｆｅａｓｉｂｌｅｐｏｉｎｔａｌｇｏｒｉｔｈｍｆｏｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ，ａｎａｌｇｏｒｉｔｈｍｆｒｏｍｔｈｅｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｆｏｒｌｉｎｅｚａ＂ｐｒｏｇｒａｍｍｉｎｇ．ＴｈｅｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｆｉｎｄｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｂｙｓｅａｒｃｈｉｎｇｗｉｔｈｉｎｔｈｅｆｅａｓｍｌｅＴｅ譬ｉｏｎｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ．ＴｈｅｒｅａｒｅａＵｋｉｎｄｓｏｆｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｌｒｍａｌｌｔｈｅｆｏｒｌｉｎｅａｒｐｒｏｇｒａｍｎｆｉｎｇ．Ｂｕｔａｌｌｔｈｅｓｅｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｓｈａｒｅａｓｐｅｃｉａｌｉｔｙ，ｗｈｉｃｈｉｓｓｏｌｕｔｉｏｎ｜ｔｅｒａｔｉｖｅＤｏｉｎｔｓｃａｎｎｏｔｒｅａｃｈｔｈｅｂｏｕｎｄｓＡｃｃｏｒｄｉｎｇｔｏｔｈｅｓｅｎｓｉｔｉｖｉｔｙｔｈｅｏｒｙ，ｔｈｅｏｐｔｉｍａｌｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｗｉｌｌｎｏｔｂｅｃｈａｎｇｅｄｂｙｌｉｔｔｌｅｄｉｓｔｕｒｂａｎｃｅｓｏｆｔｈｅｐｒｅｓｅｎｔｓｏｌｕｔｉｏｎ·ＳｏＷｅｌｅｔｔｈｅ｛ｘｊＩｚＪ＝ｏ，Ｊ＝１，２，－··）ｎ）ｅｑｕａｌａｖｅｒｙｓｍａｌｌｐｏｓｉｔｉｖｅｎｕｎｌｂｅｒ，ｇｏｏｎｗｉｔｈｔｈｅｃｏｍｐｕｔａｔｉｏ“一ａｎｄｔｈｅｎｗｅｇｅｔｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ．Ａｌｌｔｈｅｓｅｌｅａｄｔｏｔｈｅｄｅｖｅｌｏｐｍｅｎｔ。

3．3.3 简单的线性规划问题第1课时简单的线性规划问题(教师用书独具)●三维目标1.知识与技能(1)从实际情境中抽象出一些简单的二元线性规划问题，并能加以解决；(2)了解线性规划的意义以及线性约束条件、线性目标函数、可行解、可行域、最优解等概念，会根据条件建立线性目标函数；(3)了解线性规划的图解法，并会用图解法求线性目标函数的最大(小)值；(4)培养学生观察、联想以及作图的能力，渗透集合、化归、数形结合、等价转化的数学思想．2.过程与方法(1)本节课是以二元一次不等式(组)表示的平面区域的知识为基础，将实际生活问题通过数学中的线性规划问题来解决；(2)考虑到学生的知识水平和消化能力，教师可通过激励学生探究入手，讲练结合，真正体现数学的工具性，同时，借助计算机的直观演示可使教学更富趣味性和生动性．3．情感、态度与价值观(1)结合教学内容，培养学生学习数学的兴趣和“用数学”的意识，激励学生创新；(2)渗透集合、数形结合、化归的数学思想，培养学生“数形结合”的应用数学的意识，激发学生的学习兴趣.●重点、难点重点：线性规划问题的图解法，寻求线性规划问题的最优解．难点：利用图解法求最优解．为突出重点，本节教学应指导学生紧紧抓住化归、数形结合的数学思想方法，将实际问题数学化，代数问题几何化．解决难点的方法是精确作图，利用数形结合的思想将代数问题几何化．(教师用书独具)●教学建议从内容上看，简单的线性规划问题是在学习了不等式、直线方程的基础上展开的，它是对二元一次不等式的深化和再认识、再理解．它是用数学知识解决实际问题，属于数学建模，是初等数学中较抽象的，对学生要求较高，又是必须予以掌握的内容．考虑到学生的认知水平和理解能力，建议教师可以通过激励学生探究入手，讲练结合，培养学生对本节内容的学习兴趣，培养学生数形结合的意识，让学生体味数学的工具性作用．另外，教师还可借助计算机直观演示利用图解法求最优解的过程，增强教学的趣味性和生动性．●教学流程创设问题情境，引导学生了解线性约束条件、线性目标函数、可行域、线性规划问题等概念.⇒结合教材让学生掌握线性规划问题的图解法.⇒通过例1及其变式训练使学生巩固掌握利用图解法求最优解的步骤.⇒通过例2及其变式训练使学生掌握利用线性规划研究字母参数的方法.⇒通过例3及其变式训练使学生掌握求非线性目标函数的最值的方法.⇒归纳整理，进行课堂小结，整体认识本节课所学知识.⇒完成当堂双达达标，巩固所学知识，并进行反馈矫正.(对应学生用书第56页)课标解读1.了解目标函数、约束条件、可行域、最优解等基本概念．2.掌握线性规划问题的求解过程，特别是确定最优解的方法．(重点、难点)可行域约束条件所表示的平面区域，称为可行域.线性规划求线性目标函数在线性约束条件下的最大值或最小值问题，通常称为线性规划问题，上述只含两个变量的简单线性规划问题可用图解法解决.(对应学生用书第56页)线性规划问题设z ＝3x ＋5y ，式中变量x 、y 满足条件⎩⎪⎨⎪⎧x ＋2y ≥3，7x ＋10y ≥17，x ≥0，y ≥0.求z的最小值．【思路探究】【自主解答】 画出约束条件表示的点(x ，y )的可行域， 如图所示的阴影部分(包括边界直线)．把z ＝3x ＋5y 变形为y ＝－35x ＋z 5，得到斜率为－35，在y 轴上的截距为z5，随z 变化的一族平行直线．作直线l ：3x ＋5y ＝0，把直线向右上方平行移至l 1的位置时，直线经过可行域上的点M ，此时l 1：3x ＋5y －z ＝0的纵截距最小，同时z ＝3x ＋5y 取最小值．解方程组⎩⎪⎨⎪⎧x ＋2y ＝3，7x ＋10y ＝17，得M (1,1)．故当x ＝1，y ＝1时，z min ＝8.1．由本例可以看出，解线性规划问题时，一定要注意最优解的对应点是最大值点，还是最小值点．对于目标函数z ＝ax ＋by ，当b >0时，直线截距最大时，z 有最大值，截距最小时，z 有最小值；当b <0时，则相反．2．图解法是解决线性规划问题的有效方法，其关键是利用z 的几何意义求解．平移直线ax ＋by ＝0时，看它经过哪个点(哪些点)时最先接触可行域和最后离开可行域，则这样的点即为最优解，最优解一般是在可行域的边界取得．设变量x ，y 满足约束条件⎩⎪⎨⎪⎧x －y ＋2≥0，x －5y ＋10≤0，x ＋y －8≤0，则目标函数z ＝3x －4y 的最大值和最小值分别为多少．【解】 作可行域如图所示，解⎩⎪⎨⎪⎧x －y ＋2＝0，x ＋y －8＝0得⎩⎪⎨⎪⎧x ＝3，y ＝5，∴A (3,5)．解⎩⎪⎨⎪⎧x ＋y －8＝0，x －5y ＋10＝0得⎩⎪⎨⎪⎧x ＝5，y ＝3，∴B (5,3)．平移直线3x －4y ＝z 可知，直线过A 点时，z 取最小值，过B 点时，z 取最大值． ∴z min ＝3×3－4×5＝－11，z max ＝3×5－4×3＝3.利用线性规划求字母参数的值(或范围)已知x ，y 满足⎩⎪⎨⎪⎧x －4y ＋3≤0，3x ＋5y ≤25，x ≥1，设z ＝ax ＋y (a ＞0)，若当z 取最大值时，对应的点有无数多个，求a 的值．【思路探究】【自主解答】 作出可行域如图所示．由⎩⎪⎨⎪⎧3x ＋5y ＝25，x －4y ＋3＝0，得⎩⎪⎨⎪⎧x ＝5，y ＝2，∴点A 的坐标为(5,2)．由⎩⎪⎨⎪⎧x ＝1，3x ＋5y ＝25，得⎩⎪⎨⎪⎧x ＝1，y ＝4.4，∴点C 的坐标为C (1,4.4)．当直线z ＝ax ＋y (a ＞0)平行于直线AC ，且直线经过线段AC 上任意一点时，z 均取得最大值，此时有无数多点使z 取得最大值，而k AC ＝－35，∴－a ＝－35，即a ＝35.1．本题中，z 取最值时对应的点有无数多个，故这无数多个对应点构成平面区域的一段边界．2．解线性规划问题时一般要结合图形(平面区域)及目标函数的几何意义解题．若x ，y 满足约束条件⎩⎪⎨⎪⎧x ＋y ≥1，x －y ≥－1，2x －y ≤2，目标函数z ＝ax ＋2y 仅在点(1,0)处取得最小值，则a 的取值范围是________．【解析】 作出可行域，让目标函数所表示的直线过定点，观察斜率的范围，构建不等式求参数范围．如图所示，约束条件所表示的平面区域为三角形，目标函数z ＝ax ＋2y ，即y ＝－a 2x ＋z 2仅在点(1,0)处取得最小值，故其斜率应满足－1＜－a 2＜2，即－4＜a ＜2.故填(－4,2)．【答案】 (－4,2)求非线性目标函数的最值已知x ，y 满足条件⎩⎪⎨⎪⎧7x －5y －23≤0，x ＋7y －11≤0，4x ＋y ＋10≥0.(1)求u ＝x 2＋y 2的最大值和最小值； (2)求z ＝yx ＋5的最大值和最小值． 【思路探究】【自主解答】 画出不等式组所表示的平面区域，如图所示．(1)∵u ＝x 2＋y 2，∴u 为点(x ，y )到原点(0,0)的距离，结合不等式组所表示的平面区域可知，点B 到原点的距离最大，而当(x ，y )在原点时，距离为0.由⎩⎪⎨⎪⎧7x －5y －23＝0，4x ＋y ＋10＝0得点B 的坐标为(－1，－6)，∴(x 2＋y 2)max ＝(－1)2＋(－6)2＝37，(x 2＋y 2)min ＝0. (2)z ＝yx ＋5＝y －0x －－5，所以求z 的最大值和最小值，即是求可行域内的点(x ，y )与点(－5,0)连线斜率的最大值和最小值．设点M 的坐标为(－5,0)，由⎩⎪⎨⎪⎧x ＋7y －11＝0，4x ＋y ＋10＝0得点C 的坐标为(－3,2)，由(1)知点B 的坐标为(－1，－6)，∴k max ＝k MC ＝2－0－3－－5＝1，k min ＝k MB ＝－6－0－1－－5＝－32，∴yx ＋5的最大值是1，最小值是－32. 1．本题中，(1)x 2＋y 2是平面区域内的点(x ，y )到原点的距离的平方；(2)y x ＋5＝y －0x －－5可看成平面区域内的点(x ，y )与点(－5,0)连线的斜率．2．解决此类问题，应先准确作出线性约束条件表示的平面区域，然后弄清非线性目标函数的几何意义．已知x ，y 满足⎩⎪⎨⎪⎧x －y ＋2≥0，x ＋y －4≥0，2x －y －5≤0.(1)求z ＝x 2＋y 2＋2x －2y ＋2的最小值； (2)求z ＝|x ＋2y －4|的最大值． 【解】 (1)作出可行域，如图所示， ∵z ＝(x ＋12＋y －12)2，∴z 可看作是可行域内任意一点(x ，y )到点M (－1,1)的距离的平方． 由图可知z min 等于原点到直线x ＋y －4＝0的距离的平方， ∴z min ＝(|－4|2)2＝8.(2)∵z ＝|x ＋2y －4|＝5·|x ＋2y －4|5， ∴z 可看作是可行域内任意一点(x ，y )到直线x ＋2y －4＝0的距离的5倍． 由图可知点C 到直线x ＋2y －4＝0的距离最大．由⎩⎪⎨⎪⎧x －y ＋2＝0，2x －y －5＝0得点C (7,9)，∴z max ＝|7＋2×9－4|5×5＝21.(对应学生用书第58页) 直线的倾斜程度判断不准致误已知⎩⎪⎨⎪⎧11x ＋4y ≤44，7x ＋5y ≤35，6x ＋7y ≤42，x ≥0，y ≥0，求z ＝x ＋y 的最大值．【错解】 作出可行域，如图所示．作出直线l 0：x ＋y ＝0，将它移至点B ，则点B 的坐标是可行域中的最优解，它使z 达到最大值．解方程组⎩⎪⎨⎪⎧11x ＋4y ＝44，7x ＋5y ＝35，得点B 的坐标为(8027，7727)．所以z max ＝8027＋7727＝15727.【错因分析】 将直线l 0向上移动时，最后离开可行域的点不是点B 而是点A ，这是由于直线倾斜程度不准确引起的，由于三条边界直线的斜率依次是－67，－75，－114，而目标函数z ＝x ＋y 的斜率为－1，它夹在－67与－75之间，故经过点B 时，直线x ＋y ＝z 必在点A 的下方，即点B 不是向上平移直线时最后离开可行域的点，而是点A .【防范措施】 解决线性规划问题时，可行域一定要准确，关键点的位置不能画错，若数据比较大，不易画图，也可用斜率分析法确定关键点或取得最值点．【正解】 作出二元一次不等式组所表示的平面区域如上图．作出直线l ′0：x ＋y ＝0，将它向上平移，当它经过点A 时，z 取得最大值．解方程组⎩⎪⎨⎪⎧7x ＋5y ＝35，6x ＋7y ＝42，得⎩⎪⎨⎪⎧x ＝3519，y ＝8419，故z max ＝3519＋8419＝119191．基础知识： (1)可行域； (2)线性规划． 2．基本技能： (1)解线性规划问题；(2)利用线性规划求字母参数的值(或范围)； (3)求非线性目标函数的最值． 3．思想方法： (1)数形结合思想； (2)函数思想； (3)转化思想．(对应学生用书第58页)1．已知实数x ，y 满足⎩⎪⎨⎪⎧x －y ＋5≥0，x ≤3，x ＋y ≥0，则目标函数z ＝x ＋2y 的最小值为________．【解析】 画出不等式组表示的平面区域，由图可知目标函数在点(3，－3)处取得最小值－3.【答案】 －3图3－3－72．给出平面区域(包含边界)如图3－3－7所示，若使目标函数z ＝ax ＋y (a ＞0)取得最大值的最优解有无数多个，则a 的值为________．【解析】 由题意知－a ＝k AC ＝－35，∴a ＝35.【答案】 353．已知变量x ，y 满足约束条件⎩⎪⎨⎪⎧x －y ＋2＜0，x ＞1，x ＋y －7＜0，则yx的取值范围是________．【解析】 目标函数y x 是可行域上的动点(x ，y )与原点连线的斜率，最小值是k OC ＝95，最大值是k AO ＝6，又可行域边界取不到，∴95＜yx＜6.【答案】 (95，6)4．已知x 、y 满足条件⎩⎪⎨⎪⎧7x －5y －23≤0，x ＋7y －11≤0，4x ＋y ＋10≥0，求z ＝4x －3y 的最值．【解】 原不等式组表示的平面区域如图所示： 其中A (4,1)、B (－1，－6)、C (－3,2)． 作与4x －3y ＝0平行的直线l ：4x －3y ＝t ， 即y ＝43x －t3，则当l 过C 点时，t 最小； 当l 过B 点时，t 最大．∴z max ＝4×(－1)－3×(－6)＝14，z min ＝4×(－3)－3×2＝－18.(对应学生用书第97页)一、填空题1．(2013·微山高二检测)设x ，y 满足约束条件⎩⎪⎨⎪⎧x ＋y ≤1，y ≤x ，y ≥－2，则z ＝3x ＋y 的最大值为________．【解析】 不等式组表示的平面区域如图所示：把z ＝3x ＋y 变形为y ＝－3x ＋z 得到斜率为－3，在y 轴截距为z 的一族平行直线，由图当直线l ：y ＝－3x ＋z 过可行域内一点M 时，在y 轴截距最大，z 也最大．由⎩⎪⎨⎪⎧x ＋y ＝1，y ＝－2，∴⎩⎪⎨⎪⎧x ＝3，y ＝－2，即M (3，－2)．∴当x ＝3，y ＝－2时，z max ＝3×3＋(－2)＝7. 【答案】 72．(2013·苏州高二检测)变量x ，y 满足⎩⎪⎨⎪⎧2x ＋y ≥12，2x ＋9y ≥36，2x ＋3y ≥24，x ≥0，y ≥0，则使得z ＝3x ＋2y 的值最小的(x ，y )是________．【解析】 不等式组表示的平面区域如图所示：把z ＝3x ＋2y 变形为y ＝－32x ＋z 2，作与直线l 0：y ＝－32x 平行的直线l ，显然当l 经过可行域内点M 时在y 轴上截距最小，z 也最小．由⎩⎪⎨⎪⎧2x ＋y ＝12，2x ＋3y ＝24，∴⎩⎪⎨⎪⎧x ＝3，y ＝6，即M (3,6)时，z ＝3x ＋2y 的值最小． 【答案】 (3,6)3．设z ＝2y －2x ＋4，式中的x ，y 满足条件⎩⎪⎨⎪⎧0≤x ≤1，0≤y ≤2，2y －x ≥1，则z 的取值范围是________．【解析】 作出满足不等式组⎩⎪⎨⎪⎧0≤x ≤1，0≤y ≤2，2y －x ≥1的可行域(如图所示)，作直线2y －2x ＝0，并将其平移，由图象可知当直线经过点A (0,2)时，z max ＝2×2－2×0＋4＝8； 当直线经过点B (1,1)时，z min ＝2×1－2×1＋4＝4.所以z 的取值范围是[4,8]． 【答案】 [4,8]4．(2013·连云港检测)设实数x ，y 满足⎩⎪⎨⎪⎧x －y －2≤0，x ＋2y －4≥0，2y －3≤0，则yx的最大值是________．【解析】 不等式组表示的平面区域如图所示： 又y x ＝y －0x －0表示过平面区域内一点(x ，y )与原点(0,0)的直线的斜率，由图知(x ，y )在平面区域内A 点处时直线斜率最大．由⎩⎪⎨⎪⎧x ＋2y －4＝0，2y －3＝0得⎩⎪⎨⎪⎧x ＝1，y ＝32，∴A (1，32)，∴y x 的最大值为32.【答案】 325．(2013·无锡检测)二元一次方程组⎩⎪⎨⎪⎧x ＜0，y ＜0，x ＋y ＋4＞0表示的平面区域内，使得x ＋2y 取得最小值的整点坐标为________．【解析】 不等式组表示的平面区域如图所示： ∵平面区域不包括边界，∴平面区域内的整点共有(－1，－1)，(－1，－2)，(－2，－1)三个． 代入检验知，整点为(－1，－2)时x ＋2y 取得最小值． 【答案】 (－1，－2)6．已知⎩⎪⎨⎪⎧x ＋y －1≤0，x －y ＋1≥0，y ≥－1，且u ＝x 2＋y 2－4x －4y ＋8，则u 的最小值为________．【解析】 不等式组表示的平面区域如图所示，由已知得(x －2)2＋(y －2)2＝(u )2，则(u )min ＝|2＋2－1|1＋1＝32，u min ＝92.【答案】 927．已知变量x ，y 满足约束条件1≤x ＋y ≤4，－2≤x －y ≤2.若目标函数z ＝ax ＋y (其中a ＞0)仅在点(3,1)处取得最大值，则a 的取值范围为________．【解析】 由题设知可行域为如图所示的矩形，要使目标函数z ＝ax ＋y 在点(3,1)处取得最大值，结合图形可知a ＞1.【答案】 (1，＋∞)8．如果点P 在平面区域⎩⎪⎨⎪⎧2x －y ＋2≥0，x －2y ＋1≤0，x ＋y －2≤0内，点Q 在曲线x 2＋(y ＋2)2＝1上，那么|PQ |的最小值为________．【解析】 首先作出不等式组表示的平面区域和曲线x 2＋(y ＋2)2＝1，如图所示，从而可知点P 到Q 的距离最小值是可行域上的点到(0，－2)的最小值减去圆的半径1，由图可知|PQ |min ＝12＋－22－1＝5－1。

简单的线性规划问题一、基本知识1.规划问题中的可行域，实际上是二元一次不等式（组）表示的平面区域，是解决线性规划问题的基础。

因为对在直线Ax+By+C=0同一侧的所有点(x,y)，数Ax+By+C的符号相同，所以只需在此直线的某一侧任取一点(x0,y0) （若原点不在直线上，则取原点(0,0)最简便），它的坐标代入Ax+By+c，由其值的符号即可判断二元一次不等式Ax+By+c>0(或<0)表示直线的哪一侧。

2.在求线性目标函数z=ax+by的最大值或最小值时，设ax+by=t，则此直线往右（或左）平移时，t值随之增大（或减小）。

要会在可行域中确定最优解。

3.新概念:①线性约束条件②线性目标函数③线性规划问题④可行解⑤可行域⑥最优解4.重要的思想方法：数形结合化归思想5.解线性规划问题总体步骤：设变量→ 找约束条件，找目标函数找出可行域求出最优解二、典型例题：例1．某工厂生产甲，乙两种产品，已知生产甲种产品1t，需耗A种矿石10t，B种矿石5t，煤4t, 生产乙种产品1t需耗A种矿石4t，B种矿石4t，煤9t，每1t甲种产品的利润是600元。

每1t乙种产品的利润是1000元。

工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t，B种矿石不超过200t，煤不超过360t，甲，乙这两种产品应各生产多少。

（精确到1t)。

能使利润总额达到最大？解：设生产甲，乙两种产品分别为x(t), y(t)，利润总额为Z元，则，Z=600x+1000y。

作出以上不等式组所表示的平面区域，即可行域。

作直线600x+1000y=0即3x+5y=0。

将直线向上平移到如图位置，直线经过可行域上的点M ，且与原点距离最大，即Z 取最大值。

得x=360/29≈12。

y=1000/29≈34。

例2．某家电生产企业根据市场调查分析，决定调整产品生产方案，准备每周（按120个工时计算）生产空调器、彩电、冰箱共360台，且冰箱至少生产60台，已知生产这些家电产品每台所需工时和每台产值如下表：问每周生产空调器，彩电，冰箱各多少台，才能使产值最高？最高产值是多少（以千元为单位）？解：设每周生产空调器，彩电，冰箱分别为x 台，y 台，z 台，每周产值为f 元，则f=4x+3y+2z，其中x, y, z满足由(1),(2)得y=360-3x, z=2x。

线性规划的建模技巧和求解线性规划是一种数学优化方法，用于确定一个或多个线性方程的最佳解。

它在许多领域有广泛应用，如生产、物流、金融等。

下面将介绍线性规划的建模技巧和求解方法。

一、线性规划的建模技巧：1. 确定决策变量：首先要确定需要决策的变量，这些变量决定了模型的目标函数和约束条件。

变量可以表示限制条件或可供选择的决策。

2. 确定目标函数：目标函数是需要优化的目标，可以是最大化或最小化。

一般情况下，目标函数是由决策变量的线性组合构成的。

3. 确定约束条件：约束条件是限制决策变量的条件，包括等式约束和不等式约束。

约束条件可以是资源的限制、技术要求等。

4. 确定约束集：约束集是所有约束条件的集合，它定义了可行解的范围。

在确定约束集时，需要将每个约束条件转化为决策变量的线性等式或不等式。

5. 确定可行域：可行域是约束集在决策变量空间中的几何图形。

可行域是一个多面体或多面体的集合，其中每个面都由一个或多个约束条件定义。

6. 确定边界条件：边界条件是可行域的边界，在边界上的解是目标函数的极值点。

通过分析边界条件，可以确定是否存在最优解以及在哪个边界上可以找到最优解。

二、线性规划的求解方法：1. 图形法：图形法适用于二维情况，可以将可行域和目标函数的等值线绘制在一个坐标系中，通过观察交点找到最优解。

但是，图形法只适用于简单的问题，对于复杂问题无法使用。

2. 单纯形法：单纯形法是一种常用的线性规划求解方法。

它通过迭代的方式从可行域的某个顶点开始，逐步向更优解迭代，直到找到最优解。

单纯形法的思想是寻找一个可以改进目标函数值的方向，并且每次改进保证不会违反约束条件。

3. 对偶理论：线性规划问题的对偶问题可以通过原问题的约束条件和目标函数得到。

通过对偶问题的求解，可以得到原问题的最优解、最优解的相应目标值以及松弛变量的价值。

4. 整数规划：如果决策变量是整数变量，那么线性规划问题称为整数规划问题。

整数规划问题的求解通常比线性规划问题要困难得多，因为整数变量会引入离散性。