目标规划整数规划第三、四、五章

1第三章运输问题第四章目标规划第五章整数规划销地产地B1B2B3B4产量A116A210A322销量8141214484125210391146811求运费最小的运输方案。一、引例某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：A1B1B216cijA21012148求最小运费的运输方案？？运输问题图示：产地销地B3B4A32214共产48共销48minZ=4x11+12x12+4x13+11x14+2x21+10x22+3x23+9x24+8x31+5x32+11x33+6x34x11+x12+x13+x14=16x21+x22+x23+x24=10x31+x32+x33+x34=22x11+x21+x31=8x12+x22+x32=14x13+x23+x33=12x14+x24+x34=14xij041ijijxai=1,2,331ijjixbj=1,2,3,4xij0(16,10,22)'a(8,14,12,14)'b其中，x11x12x13x14x21x22x23x24x31x32x33x341111111111111111111111113个4个t1t2t3t4t5t6t71(1,1,1,1,0,0,0,0,0,0,0,0)t2(0,0,0,0,1,1,1,1,0,0,0,0)t3(0,0,0,0,0,0,0,0,1,1,1,1)t4(1,0,0,0,1,0,0,0,1,0,0,0)t5(0,1,0,0,0,1,0,0,0,1,0,0)t6(0,0,1,0,0,0,1,0,0,0,1,0)t7(0,0,0,1,0,0,0,1,0,0,0,1)t12345670ttttttt7个条件线性相关任6个线性无关基变量6个系数矩阵的特点：(1)约束条件的系数矩阵的元素只有两个：0、1。(2)元素xij对应于每一个变量在前3个约束方程中(第i个方程中)出现1次，在后四个约束方程中（第3+j个方程中）也出现1次。(3)产销平衡问题为等式约束。(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等。(5)运输问题基变量的个数：6个A1AmB1B2Bna1……cijA2a2ambnb2b1……求最小运费的运输方案？？二.典型的运输问题：1miia共产j1njb共销产地销地销地产地B1B2…Bn产量A1x11x12…x1na1A2x21x22…x2na2………………Amxm1xm2…xmnam销量b1b2…bnc11c12cm1c21c22c2nc1ncmncm211minmnijijijZcx1nijijxai=1,2,…,m1mijjixbj=1,2,…,nxij0典型运输问题的数学模型:x11x12…x1nx21x22…x2n…xm1xm2…xmn11…111…1………………………………11…1•1…111…1………………………………11…1mnm*n三、运输问题数学模型的特点：1.运输问题一定有最优解；2.运输问题约束条件的系数矩阵的特点：(1)约束条件的系数矩阵的元素只有两个：0、1。(2)元素xij对应于每一个变量在前m个约束方程中(第i个方程中)出现一次，在后n个约束方程中（第m+j个方程中）也出现一次。(3)产销平衡问题为等式约束。(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等。3.运输问题基变量的个数：m+n-1个设对偶变量向量为Y=(u1,u2,…,um,v1,v2,…,vn)对偶规划为11maxmniijjijWaubvui+vj≤cijui、vj无约束i=1,2,3…m，j=1,2,3…n11mnijiiabnijmiiba11nijmiiba11•产销平衡问题——总产量=总销量即•产销不平衡问题——总产量≠总销量总产量总销量:总产量总销量:13第一节运输问题及其数学模型第二节用表上作业法求解运输问题解运输问题基本思想和步骤：1.基本思想：单纯形法的基本思想初始基本可行解是否为最优解换基结束YN此过程可以在运费表上直接运算，故称之为表上作业法4125210391146811销地产地B1B2B3B4产量A116A210A322销量814121448初始方案的求法：三种（一）西北角法(优先考虑表中西北角的运输问题。)88866448814144125210391146811销地产地B1B2B3B4产量A18816A26410A381422销量814121448西北角法初始方案：优点：简单易行缺点：没有考虑运费08481261043811146372z41228543961111104814121482210163214321AAABBBB销量产量822010100614868000060初始方案的求法（二）：最小元素法(优先考虑表中运费最低运输。)最小元素法初始方案41228543961111104814121482210163214321AAABBBB销量产量821014680821451042361186246z优点：就近供应，即优先供应运价小的业务。缺点：会出现顾此失彼（三）沃格尔法1.罚数=次小费用-最小费用2.找出最大的罚数行或列所对应的最小费用优先安排。3.重复计算步骤1和2。4125210391146811销地产地B1B2B3B4产量行罚数A1124160A282101A3148223销量814121448列罚数21258（三）沃格尔法1.罚数=次小费用-最小费用2.找出最大的罚数行或列所对应的最小费用优先安排。3.重复计算步骤1和2。4125210391146811销地产地B1B2B3B4产量行罚数A1124160A282101A3148223销量814121448列罚数21258解运输问题基本步骤：初始基本可行解是否为最优解换基结束YN最优解的判别（计算空格检验数）两种方法：闭回路法、对偶变量法（位势法）(一)闭回路法闭回路：从空格出发，遇到数字格可以旋转90度，最后回到空格所构成的回路。思想：初始基可行解的目标值与相邻基可行解目标值比较；由检验数体现。4125210391146811销地产地B1B2B3B4产量A110616A28210A314822销量814121448σ11=4-4+3-2=1σ22=10-3+4-11+6-5=1σ12=12-11+6-5=2σ24=9-11+4-3=-1σ31=8-2+3-4+11-6=10σ33=11-6+11-4=12设对偶变量向量为Y=(u1,u2,…,um,v1,v2,…,vn)对偶规划为11maxmniijjijWaubvui+vj≤cijui+vj无约束i=1,2,3…m，j=1,2,3…n对应的变量xij检验数的计算：一般问题：σj=Cj-CBB-1Pj=Cj-YPj运输问题：σij=Cij-CBB-1Pij=Cij-YPij=Cij-(u1,u2,…,um,v1,v2,…,vn)Pij=Cij-(ui+vj)当xij为基变量时，σij=Cij-(ui+vj)=0由此，任选一个对偶变量为0，可求出其余所有的ui，vj。再根据σij=Cij-(ui+vj)求出所有非基变量的检验数。(二)对偶变量法（位势法）1.基本原理第三节运输问题的应用一、产销不平衡的运输问题例1：31271125943561销地产地B1B2B3B4产量A18A25A39销量4356销地产地B1B2B3B4B5产量A18A25A39销量4356431271125943561000销地产地B1B2B3B4B5产量A14228A2325A3549销量4356431271125943561000当产大于销时，即njjmiiba11加入假想销地（假想仓库），销量为运费为0njjmiiba11ijminjijxcZ11minnjiijax1i=1,2,…,mmijijbx1j=1,2,…,nxij0ijminjijxcZ11min11njiijaxi=1,2,…,mmijijbx1j=1,2,…,n，n+1xij0ijminjijxcZ11minnjiijax1i=1,2,…,mmijijbx1j=1,2,…,nxij0ijminjijxcZ11minnjijijax1i=1,2,…,m，m+111miijijbxj=1,2,…,nxij0第四章目标规划目标规划问题及其数学模型一、目标规划问题的提出例4.1.某工厂计划制造I、II两种产品，受原材料和工时的限制。已知分别制造两种产品一件时所需的设备台时和原材料及产品利润如下表。问题：制定一个获利最大的计划.86利润(元)4044设备工时(h/件)60105原材料(Kg/件)限量III产品5x1+10x2604x1+4x240x1，x20Z=6x1+8x2解:设两种产品产量分别为x1、x2maxs.t解：x1=8，x2=2，z=64元实际情况：1.物资部门2.销售部门3.计划部门4.财务部门12利润(元)4044设备工时(h/件)60105原材料(Kg/件)限量III产品具体要求：1.由于产品II销售疲软，故希望产品II的产量不超过产品I的一半2.原材料严重短缺，生产中应避免过量消耗3.最好能节约4h设备工时4.计划利润不少于48元。•原材料使用不得超过限额•产品II产量要求必须考虑•设备工时问题其次考虑•最后考虑计划利润的要求。描述多个目标的解决方法：引进偏差变量正偏差d+变量：决策值超过目标值的部分负偏差d-变量：决策值不足目标值的部分对每一目标引入d+、d-，d+≥0,d-≥0,d+·d-=05x1+10x260x1-2x2+d1--d1+=04x1+4x2+d2--d2+=366x1+8x2+d3--d3+=48x1，x2,di+,di-0Min{P1d1-,P2d2+,P3d3-}maxZ=6x1+8x2绝对约束和目标约束：•绝对约束：必须严格满足的约束条件，决定了解的可行性•目标约束：软约束用符号来表示可控制的因素优先因子和权系数：•体现不同目标的主次轻重•绝对优先次序：只有在满足高级优先目标的基础上才可以考虑较低级的目标，可用优先因子Pl表示，P1P2P3……Pn•相对优先：目标具有相同的优先因子，但他们的重要程度用权数表示目标函数：通过各目标约束的正、偏差变量和赋于相应的优先等级来构造的。决策者的要求是尽可能从某个方向缩小偏离目标的数值。于是，目标规划的目标函数应该是求极小：(,)minffdd()mindd()mind()mind1）要求恰好达到目标值，即相应目标约束的正、负偏差变量都要尽可能地小。这时取2)要求不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。这时取3)要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。这时取其基本形式有以下三种：建模步骤1.列出全部的约束条件2.把要达到指标的约束不等式加上正、负偏差变量后，化为目标约束等式3.对目标赋予相应的优先因子4.对同一级优先因子中的各偏差变量，若重要程度不一样，可根据题意赋予不同的加权系数5.构造一个按优先因子及加权系数对应的目标偏差量所要实现最小化的目标函数。例5.2：已知某实际问题的线性规划模型为1212121020032501611xxxxx，在此基础上考虑：1.Z的值不低于19002.资源1必须全部利用资源1资源2121016200xx12max10050Zxx12100501900xx优先因子P1：约束转换1211100501900xxddP2：12221016200xxdd1211325xx无级别：12311325xxx目标minf=11,Pd22Pd