求解线性规划的单纯形法的基本原理
求解线性规划的单纯形法的基本原理
09-07-12 &匿名提问
画出可行域 根据目标函数直线求范围 原理是根据不等式找范围 再用已知函数直线确定最值线性规划是到两个直线区域的最高点目标函数值最大是错的 如果目标函数为z=-x+y或z=x-y就不是最高点你初学时所解决的都是实际问题x,y的系数都为正,也就是类似z=x+y这类目标函数,所以你会错误的以为最高点就是最大值
请登录后再发表评论!线性规划单纯形法的matlab程序
例：max& 2*x1+3*x2
s.t.& x1+2*x2&=8
&& x1,x2&=0
加入松驰变量，化为标准型，得到
A=[1 2 1 0 0 8;4 0 0 1 0 16;0 4 0 0 1 12;2 3 0 0 0 0];
N=[3 4 5];
然后执行& [sol,val,kk]=ssimplex(A,N)就可以了。
注：基变量对应的基矩阵一定是单位阵。（这一局限将在后面的升级是改善）
%& 求解标准型线性规划:max c*x;s.t. A*x=b;x&=0
本函数中的A是单纯初始表，包括:第一行为c，最后一行是初始的检验数，最后一列是资源向量b
%& N是初始的基变量的下标
%输出变量sol是最优解
%输出变量val是最优值，kk是迭代次数
function [sol,val,kk]=ssimplex(A,N)
[mA,nA]=size(A);
%& 迭代次数
while flag
A(mA,:)&=0&&&&&
%& 已找到最优解
sol=zeros(1,nA-1);
for i=1:mA-1
&&&&&&&&&&&
sol(N(i))=A(i,nA);
val=-A(mA,nA);
for i=1:nA-1
&&&&&&&&&&&
A(mA,i)&0&A(1:mA-1,i)&=0&&&
%& 问题有无界解
&&&&&&&&&&&&&&&
disp('have infinite solution!');
&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&
&&&&&&&&&&&
flag&&&&&&&
还不是最优表，进行转轴运算
&&&&&&&&&&&
&&&&&&&&&&&
for i=1:nA-1
&&&&&&&&&&&&&&&
if A(mA,i)&temp
&&&&&&&&&&&&&&&&&&&
temp=A(mA,i);
&&&&&&&&&&&&&&&&&&&
%&& 进基变量的下标
&&&&&&&&&&&&&&&
&&&&&&&&&&&
&&&&&&&&&&&
sita=zeros(1,mA-1);
&&&&&&&&&&&
for i=1:mA-1
&&&&&&&&&&&&&&&
if A(i,inb)&0
&&&&&&&&&&&&&&&&&&&
sita(i)=A(i,nA)/A(i,inb);
&&&&&&&&&&&&&&&
&&&&&&&&&&&
&&&&&&&&&&&
&&&&&&&&&&&
for i=1:mA-1
&&&&&&&&&&&&&&&
sita(i)&0&sita(i)&&&&&&&&&&&&&&&&&&&
temp=sita(i);
&&&&&&&&&&&&&&&&&&&
outb=i;&& %&
出基变量下标
&&&&&&&&&&&&&&&
&&&&&&&&&&&
&&&&&&&&&&&
%& 以下更新N
&&&&&&&&&&&
for i=1:mA-1
&&&&&&&&&&&&&&&
if i==outb
&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&
&&&&&&&&&&&
&&&&&&&&&&&
%& 以下进行转轴运算
&&&&&&&&&&&
A(outb,:)=A(outb,:)/A(outb,inb);
&&&&&&&&&&&
for i=1:mA
&&&&&&&&&&&&&&&
if i~=outb
&&&&&&&&&&&&&&&&&&&
A(i,:)=A(i,:)-A(outb,:)*A(i,inb);
&&&&&&&&&&&&&&&
&&&&&&&&&&&
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。第一章线性规划及单纯形法习题；1.用图解法求解下列线性规划问题,并指出问题具有；minz?2x1?3x2；（1）?；max?3x1?2x2；(2)?；?4x1?6x2?6?2x1?2x2?4?x,x；3x?4x?12?12?x,x?0?12；maxz?5x1?6x2；maxz?x1?x2；(3)?；?6x1?10x2?120?2x1?x2?2；(4)?；??
第一章 线性规划及单纯形法习题
1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。
minz?2x1?3x2
max?3x1?2x2
?4x1?6x2?6?2x1?2x2?4?x,x?0?12?2x1?x2?2
3x?4x?12?12?x,x?0?12
maxz?5x1?6x2
maxz?x1?x2
?6x1?10x2?120?2x1?x2?2
??2x1?3x2?2?5?x1?10
?x,x?0?3?x?8
2.将下列线性规划问题化成标准形式。
minz??3x1?4x2?2x3?5x4?4x1?x2?2x3?x4??2
(1)?x1?x2?x3?2x4?14?
??2x1?3x2?x3?x4?2??x1,x2,x3?0,x4无约束
minz?2x1?2x2?3x3
??x1?x2?x3?4
(2) ??2x1?x2?x3?6
??2x1?3x2?x3?x4?2??x1?0,x2?0,x3无约束
3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优
minz?3x1?x2?2x3
?12x1?3x2?6x3?3x4?9
?x1?2x2?3x3?4x4?7?8x?x?4x?2x?10
?2x1?2x2?x3?2x4?10?
?x?0(j?1,?,4)?3x1?x6?2
?j?xj?0(j?1,?,6)?
minz?5x1?2x2?3x3?2x4
4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可
行解对应图解法中可行域的哪一顶点。
maxz?10x1?5x2
?3x1?4x2?9
?5x1?2x2?8?x,x?0?21
maxz?2x1?x2
?3x1?5x2?15
6x?2x?24?12?x,x?0?21
5.上题（1）中，若目标函数变为maxz?cx1?dx2，讨论c,d的值如何变化，使该问题可行域的每一顶点依次使目标函数达到最优。
6.考虑下述线性规划问题：
maxz?cx1?dx2
?a11x1?a12x2?b
?a21x1?a22x2?b?
式中1?c1?3,4?c2?6 , ?1?a11?3,2?a12?5,8?b1?12,
2?a21?5,4?a22?6,10?b2?14，试确定目标函数最优值的下界和上
7.分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解。
maxz?2x1?x2?2x3
?x1?x2?x3?6?
(1) ??2x1?x3?2
?2x2?x3?0?xj?0(j?1,2,3)?
minz?4x1?x2
minz?2x1?3x2?x3
?x1?4x2?2x3?8?3x1?2x2?6?x,x,x?0?123
maxz?10x1?15x2?12x3
?5x1?3x2?x3?9?3x1?x2?3
(3) ?4x1?3x2?x3?6
(4) ??5x1?6x2?15x3?15
??x?2x?x?424?1?2x1?x2?x3?5?xj?0(j?1,?,4)?xj?0(j?1,?,3)??
8.已知某线性规划问题的初始单纯形表和单纯形法迭代后得到的表
1-1，试求括号中未知数a～l的值。
9.若X(1),X(2)
均为某线性规划问题的最优解，证明在两点连线上的所有点也是该问题的最优解。
10. 线性规划问题max z=CX，AX=b，X≥0，设X为问题的最优解。若目标函数中用C*代替C后，问题的最优解变为X，求证:
(C-C)( X- X)≥0
11. 考虑线性规划问题
maxz??x1?2x2?x3?x4?x1?x2?x4?4?2??
?2x1?x2?x3?2x4?5?7??x?0(j?1,?,4)?j
模型中?,?,为参数，要求：
(1)组成两个新的约束(i)'?(i)?(
ii),根据(i)',(ii)',以x1，x2为基变量，列出初始单纯形表；
(2)在表中，假定??0,则?为何值时，x1，x2为问题的最优基；
(3)在表中，假定??3,则?为何值时，x1，x2为问题的最优基。
线性规划问题max z=CX，AX=b，X≥0，如X?是该问题的最优解，又且&0为某一常数，分别讨论下列情况时最优解的变化。
(1)目标函数变为maxz＝?CX； (2)目标函数变为max2＝(C+?)X；
(3)目标函数变为maxz?
x，约束条件变为AX=?b
某饲养场饲养动物出售，设每头动物每天至少需700克蛋白质、30克矿物质、100毫克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如表1―2所示：
个问题的线性规划模型，不求解) 14. 某医院护士值班班次、每班工作时间及各班所需护士数如表1-3所示。每班护士值班开始时向病房报到，试决定：
（1）若护士上班后连续工作8小时。该医院最少需多少名护士，以满足轮班需要？
（2）若除22点上班的护士连续工作8小时外，其他护士由医院排定上1～4班中的两个，则该医院又需多少名护士，以满足轮班需要？
一艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量如表1-4所示。现有三种货物待运，已知有关数据列于表1-5。
又为了航运安全，前、中、后舱的实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例上偏差不超过15％，前、后舱之间不超过10％。问该货轮应装载A、B、C各多少件运费收入才最大?试建立这个问题的线性规划模型。 16. 时代服装公司生产一款新的时装，据测今后6个月的需求量如表1－6所示。每件时装用工2小时和10元的原材料非，售价40元。该公司1月初又4个工人，
每人每月可工作200小时，月薪2000元。该公司可于任何一个月初新雇工人，但每雇一人需要一次额外支出1500元，也可辞退工人，但每辞退1人需要补偿1000元。如当月生产数超过需求，可留到后面月份销售，但需付库存每件每月5元。当供不应求时，短缺数不需要补上。试帮助该公司决策，如何使6个月的总利润最大。
17． 童心玩具厂下一年度的现金流（万元）如表1－7所示，表中负号所示该月现金流出大于流入，为此该厂需借款。借款有两种方式：一是于上一年末借一年期贷款，一次得全部贷款额，从1月份起每月还息1％，于12月归还本金及最后一次利息；二是得到短期贷款。每月初获得，于月底还，月息1.5％，当该厂有多余现金时，可短期存款，月初存入，月末取出，月息0.4％。问该厂应如何进行贷款操作，即能弥补可能出现得负现金流，又可使年末现金总量最大？
款：2003年――100万元，2004年――150万元，2005年――120万元，2006年――110万元。以上贷款均于2002年底筹集齐。但为了充分发挥这笔资金得作用，在满足每年贷款额得前提下，可将多于资金分别用于下列投资项目：
（1） 于2003年初购买A种债券，期限3年，到期后本息合计为投资额得
140％，但限购60万元；
（2） 于2003年初购买B种债券，期限2，到期后本息合计为投资额得125％
限购90万元；
（3） 于2004初购买C种债券，期限2，到期后本息合计为投资额得130％，
但限购50万元；
（4） 于每年年初将任意数额的资金存放于银行，年息4％，于每年底取出。
求宏银公司应如何用这笔筹集到的资金存放于银行，使得2002年底需要筹集到的资金数额为最少。
包含各类专业文献、中学教育、应用写作文书、专业论文、行业资料、文学作品欣赏、幼儿教育、小学教育、各类资格考试、17第一章线性规划及单纯形法习题等内容。
　运筹学习题选解 1 第一章 线性规划及单纯形法 1、 (生产计划问题) 某工厂明年根据合同,每个季度末向销售公司提供产品,有关信息如 、表 1-12.. 若当季生产... 　第一章L.P及单纯形法练习题_理学_高等教育_教育专区。第一章一、判断下列说法是否正确 L.P 及单纯形法练习题 1. 线性规划模型中增加一个约束条件,可行域的范... 　第一章一、判断下列说法是否正确 L.P 及单纯形法练习题 1. 线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束 条件,可行域的范围一般将扩大... 　《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 【8页1.(1 4 ...求解线性规划的单纯形法... 36页 免费
第一章 线性规划和单纯形... 37页... 　第一章L.P及单纯形法练习题答案_经济学_高等教育_教育专区。第一章 L.P 及单纯形法练习题答案一、判断下列说法是否正确 1. 线性规划模型中增加一个约束条件,... 　第二章 线性规划习题(附答案)_管理学_高等教育_教育专区。管理运筹学 线性规划...(6) 应用对偶单纯形法计算时, 若单纯形表中某一基变量 xi&0, 又 xi 所在... 　线性规划及单纯形法 一.选择 1. 运筹学应用分析、试验、 )的方法,对经济管理系统中人、财、物等有限资源进行统 ( 筹安排,为决策者提供有依据的最优方案,以实... 　第​一​章​ ​线​性​规​划​与​单​纯​形​法第一章 习题 1. 思考题 (1)微分学求极值的方法为什么不适用于线性规划的求解? (... 　运筹学教程(胡运权主编,清华第三版 部分习题答案(第一章) 运筹学教程(胡运权主编,清华第三版)部分习题答案(第一章) 第三 1.1 (1) (2) (3) (4) 无穷...