当前位置：文档之家 › 单纯形法程序

单纯形法程序

  • 格式：doc
  • 大小：73.00 KB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

第一章 线性规划及单纯形法3-单纯形法计算步骤

第一章 线性规划及单纯形法3-单纯形法计算步骤
1.3.4 单纯形表及单纯形法
单纯形法的计算步骤如下：
第一步 找出一个基可行解 第四步 第二步 判断其是否最优 是 结束
否 第三步 转换到相邻的基可行解，并使目标函数值增大
第一步：求初始基可行解，列出初始单纯形表。 第二步：最优性检验。 第三步：从一个基可行解转换到相邻的目标函数值更大 的基可行解，列出新的单纯形表。 第四步：重复第二、三步，直到计算结束为止。
进基变量、离基变量、基变换
目标函数
约 束 条 件
基变量
=
右边常数
基矩阵
=
目标函数 约 束 条 件 进基变量
=
右边常数
=
离基变量
目标函数 约 束 条 件
=
右边常数
新的基矩阵
=
目标函数 约 束 条 件 进基变量
=
基矩阵
=
离基变量
目标函数 约 束 条 件
=
右边常数
新的基矩阵
=
例：用单纯形法求解线性规划问题
… …
cn xn
c1 c2 … cm
x1 x2 … xm cj - zj
b1 b2 … bm
1 0 … 0 0
… …
…
0 0 … 1 0
… …
…
a1j a2j … amj
… …
…
a1n a2n … amn
…
… cj - ciaij … cn-ciaij
第二步：最优性检验。 当所有的 j 0 时，且基变量中不含有人工变量，表明 表中基可行解的目标函数值比起相邻基可行解的目标函数值 都大，可以判定现有基可行解为最优解，计算结束。 当表中存在某个 j > 0，如果相应的 Pj 0 ，表明该线 性规划问题有无界解，计算结束。 否则，转下一步。 第三步：从一个基可行解转换到相邻的目标函数值更大 的基可行解，列出新的单纯形表。 1. 确定换入的基变量。 k=max {j | j > 0} 2. 确定换出的基变量。 min { bi | a 0} bl ik i aik alk

单纯形法求解过程

单纯形法求解过程

单纯形法求解过程单纯形法是一种经典的线性规划求解方法，它是由乔治·达竞士等人在1947年提出的。

该方法的基本思想是，通过在单纯形空间内不断移动顶点的位置来寻找最优解。

单纯形法是目前广泛应用的线性规划求解方法之一，它求解线性规划问题可大大地简化计算过程。

单纯形法的求解过程包括以下几个步骤：1. 将线性规划问题转化为标准形式线性规划问题的标准形式为：$ \max_{x} \ \ c^T x $$s.t. \ Ax=b$$x\geq 0$其中，$x$是要求解的向量；$b$是一个常数向量；$A$是一个$m\times n$的矩阵；$c$是一个常数向量。

2. 初始化单纯形表因为单纯形法是通过移动顶点来寻找最优解的方法，因此需要初始化单纯形表。

单纯形表是将原始的约束条件表示为不等式形式时形成的。

例如，对于一个带有3个变量的线性规划问题，其单纯形表的形式如下：CB | X1 | X2 | X3 | X4 | RHS----|-----|-----|-----|-----|----0 | a11| a12| a13| 0 | b10 | a21| a22| a23| 0 | b20 | a31| a32| a33| 0 | b31 | z1 | z2 | z3 | 0 | 0其中，CB代表成本系数，X1、X2、X3、X4分别代表变量。

a11、a12、a13等代表矩阵A中的元素，b1、b2、b3代表矩阵b中的元素。

3. 选择进入变量和离开变量在单纯形表中，规定最后一列为等式右边的常数（RHS），即b。

在单纯形法的求解过程中，首先需要选择一个“进入变量”，即在单纯形表的第一行中，寻找一个系数为正的变量，使得将其加入目标函数后，目标函数值可以上升。

这里以X1为例，X1为进入变量。

接着，需要选择一个“离开变量”，即在单纯形表中，寻找一个使得添加X1变量后，约束条件不改变且取得约束条件中系数最小的一个变量离开。

单纯形解法

单纯形解法

线性规划问题解法：（1）图解法： 优点---只管易掌握，有助于理解结构。

缺点---只能解决低维的问题，对高维无能为力。

（2）单纯形法：单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。

单纯形法的一般步骤如下：1、寻找一个初始的基本可行解。

2、检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。

3、移至目标函数值有所改善的另一个基本可行解，然后转会到步骤（2）。

步骤1： 约束方程 表示为： 用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得： 若令所有非基变量 ，则基变量 由此可得初始的基本可行解：其过程为：存在问题：1、要判断m 个系数列向量是否恰好构成一个基并不是一件容易的事。

基由系数矩阵Ａ中m 个线性无关的系数列向量构成。

但是要判断m 个系数列向量是否线性无关并非易事。

2、即使系数矩阵Ａ中找到了一个基B ，也不能保证该基恰好是可行基。

因为不能保证基变量ＸB =Ｂ-1b ≥0。

3、为了求得基本可行解，必须求基Ｂ的逆阵Ｂ-1。

但是求逆阵Ｂ-1也是一件麻烦的事。

结论：在线性规划标准化过程中设法得到一个m 阶单位矩阵I 作为初始可行基Ｂ为了设法得到一个m 阶单位矩阵I 作为初始可行基Ｂ，可在规划标准化过程中作如下处理：1、若在化标准形式前，m 个约束方程都是“≤”的形式，那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量x n+i (i=12…m)。

2、若在化标准形式前，约束方程中有“≥”不等式，那么在化标准形时除了在方程式左端减去剩余变量使不等式变成等式以外，还必须在左端再加上一个非负新变量，称为人工变量．3、若在化标准形式前，约束方程中有等式方程，那么可以直接在等式左端添加人工变量。

【步骤一完成：寻找一个初始的基本可行解】 AX=bB B N N X AX=(BN)=BX +NX =bX ⎛⎫ ⎪⎝⎭-1-1B N X =B b-B NX N X =0-1B X =B b1B b X=0-⎛⎫ ⎪⎝⎭-1-1-1B N B N N B AX=b BX +NX =b X =B b-B NX X =0,X =B b→→→步骤2： 假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值其中 分别表示基变量和非基变量所对应的价值系数子向量。

程序求解 单纯形法

程序求解 单纯形法

程序求解单纯形法
单纯形法是一种求解线性规划问题的常用方法。

它通过一系列的迭代步骤，从一个初始的基本可行解开始，逐步改进解，直到找到最优解或证明问题无最优解。

以下是使用单纯形法求解线性规划问题的一般步骤：
1. 构建初始基本可行解：选择一个初始的基本可行解，通常可以通过引入松弛变量或人工变量来构建。

2. 计算目标函数值：计算当前基本可行解下的目标函数值。

3. 检查最优性：如果当前基本可行解满足最优性条件（目标函数值最小或最大），则停止迭代，当前解即为最优解。

4. 寻找改进方向：如果当前基本可行解不满足最优性条件，则需要找到一个改进的方向。

这可以通过计算每个非基变量（即未被选入基本可行解的变量）的检验数来完成。

5. 选择进入变量：根据检验数，选择一个具有正检验数的非基变量作为进入变量。

6. 确定离开变量：为了保持基本可行解的可行性，需要选择一个离开变量。

通常选择一个具有最小比值的基变量作为离开变量。

7. 更新基本可行解：通过替换离开变量和进入变量，构建一个新的基本可行解。

8. 重复步骤 2 至步骤 7，直到找到最优解或证明问题无最优解。

需要注意的是，单纯形法的具体实现可能因问题的规模和结构而有所不同。

在实际应用中，可以使用编程语言或优化软件来实现单纯形法。

希望以上内容对你有所帮助。

如果你有具体的线性规划问题需要求解，我可以根据具体问题提供更详细的帮助。

单纯形法步骤

单纯形法步骤

单纯形法步骤：1. 给定初始点 )0(x 初始单纯形边长 a ，α ， 收缩系数 β ， 延伸系数 γ 以及精度要求 ε。

2. 作出初始单纯形图3. 找出坏点 )(h x 、好点 )(e x 计算中心点 )1(+n x 及 反射点 )2(+n x 和各点上的目标函数值4. 比较反射点和除了坏点上的函数值，5.⑴. 如果反射点上的函数值比好点差，但比坏点外的其他顶点函数值好，认为反射成功，将反射点代替坏点构成新的单纯形，转7 ⑵. 如果反射点上的函数比好点还要好，说明反射点很好，可以沿此方向作延伸尝试，如果延伸点上的函数值比好点还好，则将延伸点取代坏点，形成新单纯形，转7。

反之，延伸点上函数值不如好点，说明延伸失败，但反射还是成功的，所以仍可用反射点代替坏点，然后转75. 如果反射点连坏点都不如，说明反射失败，那么作收缩，找出收缩点的函数值，并转6.；如果反射点仅比坏点好，则将反射点取代坏点，然后收缩，转下一步6。

6. 如果收缩点上函数比坏点还差，说明收缩也失败，作缩小运算，形成缩小后的单纯形转7；反之（即收缩点上的函数值比坏点好），说明收缩成功，用收缩点代替坏点，形成新的单纯形转。

转下一步7。

7. 检查是否满足精度要求 ()(1)max(()i n f x f x ε+-≤如满足，停止迭代，否则转3，继续迭代。

%三个考察点，最优，次差，最差best = vx(: , 1) ; fbest = vf(1) ;soso = vx(: , n) ; fsoso = vf(n) ;worst = vx(: , n+1) ; fworst = vf(n+1) ;center = sum(vx(: , 1:n) , 2) ./ n ;r = 2 * center - worst ;%反射点fr = feval(fun , r) ;if fr < fbest %比最好的结果还好，说明方向正确，考察扩展点，以期望更多的下降e = 2 * r - center ; %扩展点fe = feval(fun , e) ;if fe < fr %在扩展点和反射点中选择较优者去替换最差点vx(: , n+1) = e ; f(: , n+1) = fe ;elsevx(: , n+1) = r ; vf(: , n+1) = fr ;endelseif fr < fsoso %比次差结果好，能够改进vx(: , n+1) = r ; vf(: , n+1) = fr ;else %比次差结果坏，当压缩点无法得到更优值的时候，考虑收缩shrink = 0 ;if fr < fworst %由于r点更优所以向r点的方向找压缩点c = ( r + center ) ./ 2 ; fc = feval(fun , c) ;if fc < fr %确定从r压缩向c可以改进vx(: , n+1) = c ; vf(: , n+1) = fc ;else %否则的话，准备进行收缩shrink = true ;endelsec = (worst + center) ./ 2 ; fc = feval(fun , c) ;if fc < fr %确定从r压缩向c可以改进vx(: , n+1) = c ; vf(: , n+1) = fc ;else %否则的话，准备进行收缩shrink = 1 ;endend%fr < fworstif shrink %压缩点并非更优，考虑所有点向best收缩for i = 2:n+1vx(: , i) = ( vx(i) + best ) ./ 2 ; vf(: , i) = feval(fun , vx(: , i)) ;endend %shrinkend%fr < fsosoend %fr < fbest[vf index] = sort(vf) ;vx = vx(:,index) ;。

单纯形法计算步骤

单纯形法计算步骤

单纯形法计算步骤引言单纯形法是一种常用的数学优化方法，主要用于求解线性规划问题。

它的基本思想是通过不断地在可行解集合内移动，逐步靠近最优解，直到找到最优解。

本文将介绍单纯形法的基本步骤，以帮助读者了解如何使用该方法解决线性规划问题。

步骤一：建立线性规划模型在使用单纯形法之前，首先需要建立线性规划模型。

线性规划模型由决策变量、目标函数和约束条件组成。

决策变量是需要在问题中决策的变量，目标函数是需要最大化或最小化的目标，约束条件是限制决策变量取值范围的条件。

步骤二：将线性规划模型转化为标准形式单纯形法只适用于标准形式的线性规划模型。

标准形式要求目标函数为最大化，并且所有的约束条件都是等式形式。

如果初始线性规划模型不符合标准形式，我们可以通过适当的代数操作将其转化为标准形式。

步骤三：构造初始单纯形表初始单纯形表是单纯形法求解线性规划问题的起点。

它由决策变量、松弛变量、人工变量、目标函数系数和约束条件组成。

初始单纯形表的构造方法如下： 1. 将决策变量的系数及其对应的松弛变量、人工变量放在单纯形表的第一行。

2. 将目标函数的系数放在单纯形表的第一列。

3. 将约束条件的系数及其对应的松弛变量、人工变量放在单纯形表的其他行。

步骤四：确定基变量和非基变量基变量是单纯形表中拥有非零系数的变量，非基变量是单纯形表中拥有零系数的变量。

基变量和非基变量的确定方法如下： 1. 将目标函数的系数列中不为零的变量作为基变量。

2. 将约束条件中非零系数列中对应的变量作为基变量。

3. 剩余的变量作为非基变量。

步骤五：计算单纯形表中的系数根据基变量和非基变量的定义，我们可以计算单纯形表中的系数。

计算方法如下： 1. 将基变量的系数列除以对应的基变量系数。

2. 将非基变量的系数列减去对应的基变量系数列乘以非基变量所在行和基变量所在行之间的系数。

步骤六：检查是否达到最优解在每次迭代过程中，都需要检查是否达到最优解。

如果单纯形表中目标函数系数列的所有值都是非负的，表示已经达到最优解；否则，需要进行下一次迭代。

单纯形法的计算步骤


运筹学基础及应用
解：化标准型
max
z 2 x1 x2 0 x3 0 x4 0 x5 5 x2 x3 15 6 x 2 x x4 24 1 2 x5 5 x1 x2 x1 , , x5 0
运筹学基础及应用
表1：列初始单纯形表 （单位矩阵对应的变量为基变量）
运筹学基础及应用
单纯形表
- Z x1基变量 x 2 ... xm XB 0 1 1E 0 单位阵 ....... 0 1 1 c c 0... c 1 2 m xm xNn 非基变量 1 .... X a1m 1 ...a1n a 2 m 1N...a 2 n
非基阵 ......
在上一节单纯形法迭代原理中可 知，每一次迭代计算只要表示出当前的约 束方程组及目标函数即可。
a1m 1 xm 1 ..... a1n xn b1 x1 x a2 m 1 xm 1 ..... a2 n xn b2 2 .......... .......... .......... ..... xm amm 1 xm 1 ..... amn xn bm Z c1 x1 ... cm xm cm 1 xm 1 ... cn xn 0
3
0 1 5/4 -15/2 1*3/2 0 0 1/4 -1/2 +0*15/2 检验数<=0 1 0 -1/4 3/2
cj z j
8.5
0
0
-1/4
-1/2
最优解为X=(7/2,3/2,15/2,0,0) 目标函数值Z=8.5
cj
CB
0 0 0
2
1
0最小的值对应 0 0

单纯形法

单纯形法(SM ，simplex method)首先在n 维欧氏空间n E 中构造一个包含1n +顶点的凸多面体，求出各顶点的函数值并确定其中的最大值，次大值和最小值。

然后通过反射、扩张、内缩、缩边等求出一个较好解，用之取代最差点，从而构成新的多面体。

如此迭代可求得一个极小点。

具体步骤如下：①、 确定初始点。

②、 反射操作：求出1n +个顶点的函数值，确定其中最大值G f ，次大值H f 和最小值L f 。

除去最大值点G X ，计算剩余n 个点的形心X ，然后求出G X 关于X的对称点(2)n X +，计算(2)()n f X +。

若(2)()n L f X f +<，则令(3)(2)()n n X X X X γ++=+-，其中1γ>，取2γ=，并计算(3)()n f X +，若(3)(2)()()n n f X f X++<则用(3)n X +取代G X 转步骤⑤，否则用(2)n X +取代G X 转步骤⑤。

③、 若(2)()n L H f f X f +≤≤，则用(2)n X +取代G X 步骤⑤。

④、 若(2)()n H f X f +≥，则需要内缩，(2)(')min{(),()}n H f X f X f X +=，令(4)(')n X X X X β+=+-，其中0.5β=，计算(4)()n f X +，若(4)()(')n f X f X +≤，则用(4)n X +取代G X ，并转步骤⑤。

若(4)()(')n f X f X +>则缩边，即()/2i i L X X X =+，(1,2,,1)i n =+ ，转步骤⑤。

⑤、 若120.511{[()()]}1n i i f X f X n ε+=-<+∑，则停止，否则转②。

SM 简单，计算量小，优化快速，不需要函数可导。

但对初始值依赖性强，容易陷入局部极小，而且优化效果随函数维数增加明显下降。

单纯形法解题步骤

三、单纯形法的解题步骤第一步：作单纯形表.）（1）把原线性规划问题化为标准形式；）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；）（3）目标函数非基化；）（4）作初始单纯形表.第二步：最优解的判定.(1) 若所有检验数都是非正数，即，则此时线性规划问题已取得最优解.(2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划问题无最优解.如果以上两条都不满足，则进行下一步.第三步：换基迭代.，并确定所在列的非基变量为进基变量.（1）找到最大正检验数，设为（2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号.主元是最大正检验数所在列，用常数项与进基变量所对应的列向量中正分量的比值最小者；替换出基变量，从而得到新的基变量.也就是主元所在（3）换基：用进基变量（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.例3 求.解（1）化标准型：令，引进松弛变量，其标准型为求（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为标函数取得最优值.目性规划问题的最优解为：.原线目标函数的最优值为14，即.例4 用单纯形方法解线性规划问题.求.解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数, 经整理后，目标函数非基化了.作单纯形表，并进行换基迭代（见表6.9）.最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变换，基变量出基，非基变量进基.表 6.9目前最大检验数，其所在列没有正分量，所以该线性规划问题没有最优解.例5用单纯形方法解线性规划问题.求解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数，经整理得,目标函数已非基化.作单纯形表，并进行换基迭代(见表6.10).最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变换，基变量出基，非基变量x2进基，先将主元化为1，然后再将主元所在列的其他元素化为零.表 6.10至此，检验数均为非正数，故得基础可行解.原问题的最优解为：.最优值为6，即.如果我们再迭代一次，将基变量出基，非基变量进基（见表6.11）.表 6.11可得到另一个基础可行解,原问题的最优解为：，最优值仍为6，说明该线性规划问题有无穷多最优解，其最优解均为6.如何知道线性规划问题有无穷多最优解呢？这主要反映在单纯形表中.如果非基变量所对应的检验数为0，我们可对此列继续进行换基迭代，就可以得到另一个基础可行解.以此作下去，可得到许多基础可行解，即相对应的最优解有无穷多个.（4） 011 0。

单纯形法的计算步骤

4 从一个基可行解转换到另一个目标值更大的基可行解,列出新的单纯形表
确定换入基的变量。选择 ,对应的变量xj作为换入变量,当有一个以上检验数大于0时,一般选择最大的一个检验数,即： ,其对应的xk作为换入变量。 确定换出变量。根据下式计算并选择θ ,选最小的θ对应基变量作为换出变量。
商务 图标元素
商务 图标元素
商务 图标元素
商务 图标元素
商务 图标元素
商务 图标元素
商务 图标元素
商务 图标元素
商务 图标元素
单纯形法的计算步骤
用换入变量xk替换基变量中的换出变量,得到一个新的基。对应新的基可以找出一个新的基可行解,并相应地可以画出一个新的单纯形表。 5 重复3 、4 步直到计算结束为止。
单纯形法的计算步骤
换入列
bi /ai2,ai2>0
40
10
换出行
将3化为1
5/3
1
18
0
1/3
0
1/3
10
1
－1/3
其中：M是一个很大的抽象的数,不需要给出具体的数值,可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型,计算结果见下表。
单纯形法的进一步讨论－人工变量法
→
→
→
单纯形法的进一步讨论－人工变量法
单纯性法小结:
PPT常用编辑图使用方法
1.取消组合
2.填充颜色
3.调整大小ຫໍສະໝຸດ 商务 图标元素30
30
0
5/3
0
－4/3
乘以1/3后得到
1
0
3/5
－1/5
18
0
1
－1/5
－2/5
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

/*单纯形法程序*//*p46--5(2)*/#include "stdio.h"main(){int i,j,r,k,l,jj[4],m=4,n=7,maxjj,mini,count=0;floata[4][7]={{0,2,-1,1,0,0,0},{60,3,1,1,1,0,0,},{10,1,-1,2,0,1,0},{20,1, 1,-1,0,0,1}};floatb[4][4],e[4][4],t[4][4],y[4],maxcj,tb[4],tp[4],cb[4],cj[7],theta,lk,z; jj[1]=4;jj[2]=5;jj[3]=6;for(i=0;i<m;i++)for(j=0;j<m;j++)b[i][j]=0.0;for(i=1;i<m;i++) b[i][i]=1.0;printf("*********************************\n");for(i=0;i<m;i++){ for(j=0;j<n;j++)printf("%6.1f",a[i][j]);printf("\n");}for(i=1;i<m;i++) cb[i]=a[0][jj[i]];for(j=1;j<m;j++){ y[j]=0.0;for(i=1;i<m;i++) y[j]+=cb[i]*b[i][j]; }for(j=1;j<n;j++){for(r=1;r<m;r++)if(jj[r]==j){cj[j]=0.0;break; }cj[j]=a[0][j];for(i=1;i<m;i++) cj[j]=cj[j]-y[i]*a[i][j];}maxcj=cj[1]; maxjj=1;for(j=2;j<n;j++)if(maxcj<cj[j]){ maxcj=cj[j]; maxjj=j;}k=maxjj;for(j=1;j<n;j++)printf("%6.1f",cj[j]);printf(" k=%d\n",k); while(maxcj>0){ count++;for(i=1;i<m;i++){ tb[i]=0.0;for(r=1;r<m;r++)tb[i]+=b[i][r]*a[r][0]; }for(i=1;i<m;i++){ tp[i]=0.0;for(r=1;r<m;r++)tp[i]+=b[i][r]*a[r][k]; }/*for(i=1;i<m;i++)printf("%6.1f",tb[i]);for(i=1;i<m;i++)printf("%6.1f",tp[i]);printf("tb--tp\n"); */theta=1000.0;for(j=1;j<m;j++){ if(tp[j]>0)if (theta>tb[j]/tp[j]){ theta=tb[j]/tp[j]; mini=j;}}/* printf("LLL=%d Theta=%f\n",mini,theta); */l=mini;lk=tp[l];jj[l]=k;printf("*********************************\n");for(i=0;i<m;i++)for(j=0;j<m;j++)e[i][j]=0.0;for(i=1;i<m;i++) e[i][i]=1.0;for(i=1;i<m;i++)e[i][l]=(-1)*tp[i]/lk;e[l][l]=1.0/lk;for(i=1;i<m;i++){ for(j=1;j<m;j++)printf("%6.1f",e[i][j]);printf("\n"); } /* for(j=1;j<m;j++)printf("%6.1f",tp[j]); printf("\n");*/ for(i=1;i<m;i++)for(j=1;j<m;j++){ t[i][j]=0.0;for(r=1;r<m;r++)t[i][j]+=e[i][r]*b[r][j];}for(i=1;i<m;i++){ for(j=1;j<m;j++){ b[i][j]=t[i][j];printf("%6.1f",b[i][j]);}printf(" x%d\n",jj[i]);}for(i=1;i<m;i++) cb[i]=a[0][jj[i]];for(j=1;j<m;j++){ y[j]=0.0;for(i=1;i<m;i++) y[j]+=cb[i]*b[i][j]; }for(j=1;j<n;j++){for(r=1;r<m;r++)if(jj[r]==j){cj[j]=0.0;break; }cj[j]=a[0][j];for(i=1;i<m;i++) cj[j]=cj[j]-y[i]*a[i][j];}maxcj=cj[1]; maxjj=1;if(maxcj<cj[j]){ maxcj=cj[j]; maxjj=j;}k=maxjj;for(j=1;j<n;j++)printf("%6.1f",cj[j]);printf(" k=%d\n",k);}for(i=1;i<m;i++){ tb[i]=0.0;for(r=1;r<m;r++)tb[i]+=b[i][r]*a[r][0]; }z=0.0;for(i=1;i<m;i++){ cb[i]=a[0][jj[i]];printf(" x%d=%6.1f\n",jj[i],tb[i]);z+=tb[i]*cb[i];}printf(" Max_z=%5.1f THE_count=%d\n",z,count);}/*p37--li1-13*/#include "math.h"#include "stdio.h"main(){int i,j,r,k,l,jj[4],m,n,maxjj,mini,count=0;floatb[4][4],e[4][4],t[4][4],y[4],maxcj,tb[4],tp[4],cb[4],cj[7],theta,lk,z; floata[4][6]={{0,700,1200,0,0,0},{360,9,4,1,0,0,},{200,4,5,0,1,0},{300, 3,10,0,0,1}};m=4;n=6;jj[1]=3;jj[2]=4;jj[3]=5;for(j=0;j<m;j++)b[i][j]=0.0;for(i=1;i<m;i++) b[i][i]=1.0;printf("*********************************\n");for(i=0;i<m;i++){ for(j=0;j<n;j++)printf("%6.1f",a[i][j]);printf("\n");}for(i=1;i<m;i++) cb[i]=a[0][jj[i]];for(j=1;j<m;j++){ y[j]=0.0;for(i=1;i<m;i++) y[j]+=cb[i]*b[i][j]; }for(j=1;j<n;j++){for(r=1;r<m;r++)if(jj[r]==j){cj[j]=0.0;break; }cj[j]=a[0][j];for(i=1;i<m;i++) cj[j]=cj[j]-y[i]*a[i][j];}maxcj=cj[1]; maxjj=1;for(j=2;j<n;j++)if(maxcj<cj[j]){ maxcj=cj[j]; maxjj=j;}k=maxjj;for(j=1;j<n;j++)printf("%6.1f",cj[j]);printf(" k=%d\n",k);while(maxcj>0.0001){ count++;for(i=1;i<m;i++){ tb[i]=0.0;for(i=1;i<m;i++){ tp[i]=0.0;for(r=1;r<m;r++)tp[i]+=b[i][r]*a[r][k]; }/*for(i=1;i<m;i++)printf("%6.1f",tb[i]);for(i=1;i<m;i++)printf("%6.1f",tp[i]);printf("tb--tp\n"); */theta=1000.0;for(j=1;j<m;j++){ if(tp[j]>0)if (theta>tb[j]/tp[j]){ theta=tb[j]/tp[j]; mini=j;}}/* printf("LLL=%d Theta=%f\n",mini,theta); */l=mini;lk=tp[l];jj[l]=k;printf("*********************************\n");for(i=0;i<m;i++)for(j=0;j<m;j++)e[i][j]=0.0;for(i=1;i<m;i++) e[i][i]=1.0;for(i=1;i<m;i++)e[i][l]=(-1)*tp[i]/lk;e[l][l]=1.0/lk;for(i=1;i<m;i++){ for(j=1;j<m;j++)printf("%6.1f",e[i][j]);printf("\n"); } /* for(j=1;j<m;j++)printf("%6.1f",tp[j]); printf("\n");*/ for(i=1;i<m;i++)for(j=1;j<m;j++){ t[i][j]=0.0;for(i=1;i<m;i++){ for(j=1;j<m;j++){ b[i][j]=t[i][j];printf("%6.1f",b[i][j]);}printf(" x%d\n",jj[i]);}for(i=1;i<m;i++) cb[i]=a[0][jj[i]];for(j=1;j<m;j++){ y[j]=0.0;for(i=1;i<m;i++) y[j]+=cb[i]*b[i][j]; }for(j=1;j<n;j++){for(r=1;r<m;r++)if(jj[r]==j){cj[j]=0.0;break; }cj[j]=a[0][j];for(i=1;i<m;i++) cj[j]=cj[j]-y[i]*a[i][j];}maxcj=cj[1]; maxjj=1;for(j=2;j<n;j++)if(maxcj<cj[j]){ maxcj=cj[j]; maxjj=j;}k=maxjj;for(j=1;j<n;j++)printf("%6.1f",cj[j]);printf(" k=%d MAXcj=%f\n",k,maxcj);} /*while--end*/for(i=1;i<m;i++){ tb[i]=0.0;for(r=1;r<m;r++)tb[i]+=b[i][r]*a[r][0]; }z=0.0;for(i=1;i<m;i++){ cb[i]=a[0][jj[i]];printf(" x%d=%6.1f\n",jj[i],tb[i]);z+=tb[i]*cb[i];}printf(" Max_z=%5.1f THE_count=%d\n",z,count);}/*p47--6(5)*/#include "math.h"#include "stdio.h"main(){int i,j,r,k,l,jj[4],m,n,maxjj,mini,count=0,ok=0;floatb[4][4],e[4][4],t[4][4],y[4],maxcj,tb[4],tp[4],cb[4],cj[8],theta,lk,z; floata[4][8]={{0,-1,-1,3,0,0,-1000,-1000},{11,1,-2,1,1,0,0,0},{3,2,1,-4,0 ,-1,1,0},{1,1,0,-2,0,0,0,1}};m=4;n=8;jj[1]=4;jj[2]=6;jj[3]=7;for(i=0;i<m;i++)for(j=0;j<m;j++)b[i][j]=0.0;for(i=1;i<m;i++) b[i][i]=1.0;printf("*********************************\n");for(i=0;i<m;i++){ for(j=0;j<n;j++)printf("%6.1f",a[i][j]);printf("\n");}for(i=1;i<m;i++) cb[i]=a[0][jj[i]];for(j=1;j<m;j++){ y[j]=0.0;for(i=1;i<m;i++) y[j]+=cb[i]*b[i][j]; }for(j=1;j<n;j++){for(r=1;r<m;r++)if(jj[r]==j){cj[j]=0.0;break; }cj[j]=a[0][j];for(i=1;i<m;i++) cj[j]=cj[j]-y[i]*a[i][j];}maxcj=cj[1]; maxjj=1;for(j=2;j<n;j++)if(maxcj<cj[j]){ maxcj=cj[j]; maxjj=j;}k=maxjj;for(j=1;j<n;j++)printf("%6.1f",cj[j]);printf(" k=%d\n",k);while(maxcj>0.001&&count<5){ count++;for(i=1;i<m;i++){ tb[i]=0.0;for(r=1;r<m;r++)tb[i]+=b[i][r]*a[r][0]; }for(i=1;i<m;i++){ tp[i]=0.0;for(r=1;r<m;r++)tp[i]+=b[i][r]*a[r][k]; }/*for(i=1;i<m;i++)printf("%6.1f",tb[i]);for(i=1;i<m;i++)printf("%6.1f",tp[i]);for(i=1;i<m;i++)if(tp[i]<=0)ok=-1;if (ok==-1){ printf("*** z\030 \354 ***\n");return;} */theta=1000.0;for(j=1;j<m;j++){ if(tp[j]>0.01)if (theta>tb[j]/tp[j]){ theta=tb[j]/tp[j]; mini=j;}}/* printf("LLL=%d Theta=%f\n",mini,theta); */l=mini;lk=tp[l];jj[l]=k;printf("*********************************\n"); /* getchar();*/for(i=0;i<m;i++)for(j=0;j<m;j++)e[i][j]=0.0;for(i=1;i<m;i++) e[i][i]=1.0;for(i=1;i<m;i++)e[i][l]=(-1)*tp[i]/lk;e[l][l]=1.0/lk;for(i=1;i<m;i++){ for(j=1;j<m;j++)printf("%6.1f",e[i][j]);printf("\n"); }/* for(j=1;j<m;j++)printf("%6.1f",tp[j]); printf("\n");*/for(i=1;i<m;i++)for(j=1;j<m;j++){ t[i][j]=0.0;for(r=1;r<m;r++)t[i][j]+=e[i][r]*b[r][j];}for(i=1;i<m;i++){ for(j=1;j<m;j++){ b[i][j]=t[i][j];printf("%6.1f",b[i][j]);}printf(" x%d\n",jj[i]);}for(i=1;i<m;i++) cb[i]=a[0][jj[i]];for(j=1;j<m;j++){ y[j]=0.0;for(i=1;i<m;i++) y[j]+=cb[i]*b[i][j]; }for(j=1;j<n;j++){for(r=1;r<m;r++)if(jj[r]==j){cj[j]=0.0;break; }cj[j]=a[0][j];for(i=1;i<m;i++) cj[j]=cj[j]-y[i]*a[i][j];}maxcj=cj[1]; maxjj=1;for(j=2;j<n;j++)if(maxcj<cj[j]){ maxcj=cj[j]; maxjj=j;}k=maxjj;for(j=1;j<n;j++)printf("%6.1f",cj[j]);printf(" k=%d MAXcj=%f\n",k,maxcj);} /*while--end*/for(i=1;i<m;i++){ tb[i]=0.0;for(r=1;r<m;r++)tb[i]+=b[i][r]*a[r][0]; }z=0.0;for(i=1;i<m;i++){ cb[i]=a[0][jj[i]];printf(" x%d=%6.1f\n",jj[i],tb[i]);z+=tb[i]*cb[i];}printf(" Max_z=%5.1f THE_count=%d\n",z,count);}/*p47---6(3)*/#include "math.h"#include "stdio.h"main(){int i,j,r,k,l,jj[4],m,n,maxjj,mini,count=0;floatb[4][4],e[4][4],t[4][4],y[4],maxcj,tb[4],tp[4],cb[4],cj[8],theta,lk,z; floata[4][7]={{0,-4,-1,0,0,-1000,-1000},{3,3,1,0,0,1,0},{6,4,3,-1,0,0,1}, {4,1,2,0,1,0,0}};m=4;n=7;jj[1]=5;jj[2]=6;jj[3]=4;for(i=0;i<m;i++)for(j=0;j<m;j++)b[i][j]=0.0;for(i=1;i<m;i++) b[i][i]=1.0;printf("*********************************\n");for(i=0;i<m;i++){ for(j=0;j<n;j++)printf("%6.1f",a[i][j]);printf("\n");}for(i=1;i<m;i++) cb[i]=a[0][jj[i]];for(j=1;j<m;j++){ y[j]=0.0;for(i=1;i<m;i++) y[j]+=cb[i]*b[i][j]; }for(j=1;j<n;j++){for(r=1;r<m;r++)if(jj[r]==j){cj[j]=0.0;break; }cj[j]=a[0][j];for(i=1;i<m;i++) cj[j]=cj[j]-y[i]*a[i][j];}maxcj=cj[1]; maxjj=1;for(j=2;j<n;j++)if(maxcj<cj[j]){ maxcj=cj[j]; maxjj=j;}k=maxjj;for(j=1;j<n;j++)printf("%6.1f",cj[j]);printf(" k=%d\n",k);while(maxcj>0.001){ count++;for(i=1;i<m;i++){ tb[i]=0.0;for(r=1;r<m;r++)tb[i]+=b[i][r]*a[r][0]; }for(i=1;i<m;i++){ tp[i]=0.0;for(r=1;r<m;r++)tp[i]+=b[i][r]*a[r][k]; }/*for(i=1;i<m;i++)printf("%6.1f",tb[i]);for(i=1;i<m;i++)printf("%6.1f",tp[i]);printf("tb--tp\n"); */theta=1000.0;for(j=1;j<m;j++){ if(tp[j]>0.01)if (theta>tb[j]/tp[j]){ theta=tb[j]/tp[j]; mini=j;}}/* printf("LLL=%d Theta=%f\n",mini,theta); */l=mini;lk=tp[l];jj[l]=k;printf("*********************************\n"); /* getchar();*/for(i=0;i<m;i++)for(j=0;j<m;j++)e[i][j]=0.0;for(i=1;i<m;i++) e[i][i]=1.0;for(i=1;i<m;i++)e[i][l]=(-1)*tp[i]/lk;e[l][l]=1.0/lk;for(i=1;i<m;i++){ for(j=1;j<m;j++)printf("%6.1f",e[i][j]);printf("\n"); }/* for(j=1;j<m;j++)printf("%6.1f",tp[j]); printf("\n");*/for(i=1;i<m;i++)for(j=1;j<m;j++){ t[i][j]=0.0;for(r=1;r<m;r++)t[i][j]+=e[i][r]*b[r][j];}for(i=1;i<m;i++){ for(j=1;j<m;j++){ b[i][j]=t[i][j];printf("%6.1f",b[i][j]);}printf(" x%d\n",jj[i]);}for(i=1;i<m;i++) cb[i]=a[0][jj[i]];for(j=1;j<m;j++){ y[j]=0.0;for(i=1;i<m;i++) y[j]+=cb[i]*b[i][j]; }for(j=1;j<n;j++){for(r=1;r<m;r++)if(jj[r]==j){cj[j]=0.0;break; }cj[j]=a[0][j];for(i=1;i<m;i++) cj[j]=cj[j]-y[i]*a[i][j];}maxcj=cj[1]; maxjj=1;for(j=2;j<n;j++)if(maxcj<cj[j]){ maxcj=cj[j]; maxjj=j;}k=maxjj;for(j=1;j<n;j++)printf("%6.1f",cj[j]);printf(" k=%d MAXcj=%f\n",k,maxcj);} /*while--end*/for(i=1;i<m;i++){ tb[i]=0.0;for(r=1;r<m;r++)tb[i]+=b[i][r]*a[r][0]; }z=0.0;for(i=1;i<m;i++){ cb[i]=a[0][jj[i]];printf(" x%d=%6.1f\n",jj[i],tb[i]);z+=tb[i]*cb[i];}printf(" Max_z=%5.1f THE_count=%d\n",z,count);}。