内容发布更新时间 : 2024/5/22 8:33:59星期一 下面是文章的全部内容请认真阅读。
第一章作业
1．对于下列线性规划模型，找出顶点和约束之间的对应关系（图解法）
max z?2x1?x2?5x2?15?6x?2x?24
?12s..t??x1?x2?5??x1?0,x2?0 （答案略: 任何一个顶点对应两个约束的交点）
2．用单纯形法求解线性规划模型
max z?2x1?x2
?3x1?x2?24?s..t?x1?x2?5?x?0,x?02?1
（答案略：最好两阶段法和大M法均练习一遍）
3．通过观察，判断下列线性规划模型有无最优解、在有解的情况下是否为无界解(说明理由)
max z?2x1?x2 （1）
?x1?x2?5?s..t?2x1?2x2?8?x?0,x?02?1
因为 x1?x2?5和2x1?2x2?8是两个矛盾的条件，所以问题无解
max z?2x1?x2?x3?x1?x2?2x3?5 （2） ?s..t?3x1?2x2?5x3?8?x?0,x?02?1 因为(M，0，0)是模型的一个可行解，所以可认为问题为无界解。
4．判断题(说明理由)
1．最优解不唯一，那么一定有两个最优基可行解。
错误。最优解不唯一，可能存在一个基可行解，也可能存在r(r≥2)个基可行解。举一例子
进行反驳即可。（注意区分基可行解和可行解）
2．在最优单纯形表中，如果某个非基变量的检验数值为0，且相应的技术系数均小于等于0，
则相应的线性规划有无界解。
错误。判定无界解的原则有二：（1）某一单纯表中某一非基变量的检验数为正(目标函数
求最大值时，求最小值时正好相反)，而该变量的技术向量P≤0；（2）某一单纯表中某一非基变量的技术向量P≤0，而该变量的价值系数又大于0(目标函数求最大值时，求最小值时正好相反)。（注意：区分无界解和无穷多最优解） 5 线性规划问题max z?CX,AX?b,X?0，如果X是该问题的最优解，又??0为一常数，
分别讨论下述情况时最优解的变化：
*（a） 目标函数变为 max z??CX 方法1: 使用检验数进行讨论
最优单纯表中, 变量X的检验数为??C?CBBA, 显然 C?CBBA?0
设这时的最优解为X*. 当价值系数变为?C时, X*仍然是新问题的可行解,但变量X的检验数变为?1??C??CBBA??(C?CBBA)
仍有?1?0, 因而两个问题具有同样的最优基, 进而有同样的最优解,仅仅最优目标函数值变化了?倍.
方法2: 设X*为原问题的一个最优解, X是原问题的任意一个可行解
因而必有CX?CX
由于X*和X均也为新问题的可行解,由于??0, 因而 ?CX??CX 因而X也是新问题的最优解.
（b） 目标函数变为 max z?(C??)X
提示: 通过选择具体的例子, 分析目标函数的变化, 最优解可能发生改变, 也可能不变. 6．已知线性规划问题
**?1?1?1?1*?????max???z?c1x1?c2x2?c3x3?a11x1?a12x2?a13x3?x4?b1 ?s..t?a21x1?a22x2?a23x3?x5?b2?x?0??????j?1,2,3,4?j 已知最优单纯形表如下 CB c3 c1 XB x3 x1 cj-zj 试确定模型中各参数的值 解法1: 直接使用矩阵变换.
解法2: 使用B和B解题(关键知识点), 具体略.
?1b 5/2 5/2 c1 x1 0 1 0 c2 x2 1/2 -1/2 -4 c3 x3 1 0 0 c4 x4 1/2 -1/6 -4 c5 x5 0 1/3 -2 0??1/2 B???
?1/61/3???1 7． (证明题)线性规划问题max z?CX,AX?b,X?0，设X是问题的最优解，若目标函数中
*用C替换C后，问题的最优解为X，则必有(C?C)(X?X)?0
***00 证明：对于原问题，由于X和X均为可行解，X为最优解，因而有
0*0CX0?CX* （7.1）
对于替换后的问题，由于X0和X*均为可行解，X*为最优解，因而有 CX?CX （7.2） 结合（7.1）和（7.2）命题成立.
8．(选做题)对于大M法和两阶段法下面线性规划需要引入m个人工变量, 你是否可以设计一种方法只引入一个人工变量就可
***0 mzi?nc 1 x1?cx?cn...xn2?2?a1x2?2...?anxn1?b1?a11x1?ax?ax?...?ax?b211222nn22? ?s..t?...?ax?ax?...?ax?bmnnm?m11m22??xi?0,i?1,2,...,n9．（选做题）证明标准的线性规划模型，要么不存在可行解，要么至少存在一个基可行解。
证明: 首先以具体例子说明标准的线性规划模型可能不存在可行解.
其次, 证明如果标准的线性规划模型存在可行解则一定存在基可行解.