单纯形法的旋转迭代算法及影子价格.pdfVIP

维普资讯 第 6卷 第 1期 运 筹 与 管 理 VOl6．N()l ． 1997年 3月 OPERATIONSRESEARCH AND MANAGEMENT SCIENCE M ar ．1997 单纯形法的旋转迭代算法及影子价格 邹 自德 (广东增城市 电视大学，广东 增城 511300) 摘 要 本文对线性规划 问题提 出一种寻找初始可行基和判定可行解的统一·方法。它在运 用单纯形法时，在若干情况下不必引人人工变量而可在一种表格之下直接应用旋转运算而获 得 ，之后就在 同一张表格下完全和常规单纯形法一样求最优解。此法我们称之为 “单纯形法的 旋转迭代算法”。应用此法，我们容易求 出影子价格 。 关键词 线性规划 ；单纯形法；基可行解；旋转迭代算法 ；影子价格 0 引 言 众所周知 ，用单纯形法求解线性规划 问题时，首先要找到一个初始可行基 。有时可从约 束方程组 A —B的系数矩阵A 中直接观察到一个可行基，例如 ：若约束方程组为AX≤b， 当转化为标准形式后就可得到一个明显的可行基和一个基可行解 。其它大部分情形均无 明 显的可行基。此时，通常要引入人工变量 ，采用大M 法或二阶段法来求解。采用大 法，由 于要规定常数 是一个充分大的正数，因而可能有计算错误 ；采用二阶段法 ，要把原来的线 性规划 问题转化为两个线性规划 问题来求解，计算量大大增加。另外 ，无论是大 法还是二 阶段法，由于人工变量的引入 ，变量数增加，计算量和计算机的储存量也随之增大 。事实上， 一 个基可行解就是约束方程组的一个 自由变量取 0时的非负特解。能否不引入人工变量，而 象用初等变换求解线性方程组那样找 出这个特解 ，从而找 出一个初始可行基呢?基于这一设 想，本文提出了一种旋转迭代算法 。它不但给予了以上设想一个肯定的答复，而且这种方法 操作起来 比较方便和有效。 1 线性规划标准形式的转化 线性规划标准形式为： max5一∑cix， fa z+a~2x2+…+anz，z一6 la21zl+a22z2+…+a2z一b2 (s．t．) J…………………………… Ia州z】+a砌z2+…+a z一6 lzl，z2，…，z≥o 收稿 日期：1996一o6一lO；修订 日期 ：1996一o7—1o 维普资讯 8 运筹与管理 1997年第 6卷 令 A=： ， 6一 (61，b2，… ，b)≥0， X一 (1， 2，… ， )了’， C= (c1，c2，… ， )，。 为约束条件 的 × 维 系数矩 阵，其秩为 ，且 ，C为 目标 函数系数 向量．设 尸，= (口l』’口： ”，a,nj)(一1，2，…，)，为 的第 列向量 。若 P，(j1，2，…，)中存在一个单位 初始可行基 B： (P ，P：，…， )一 ，则可得到下列线性规划标准形式 ： ● ● ● ● m ax = ● ● ● ● ∑ ， ％ ～‰ 『： 乏：：：兰：：===耋 (s．t．) … … … ………… ……………………