线性规划问题的规范型算法.pdf

文档介绍：第 卷 第 期 运 筹 与 管 理 ，
!" " 行基，但大部分情形均无明显的可行基。此时，通常要引入人工变量，采用大
>
法或二阶段法来求解。采用大 法，由于要规定常数 是一个充分大的正数，因而可能有计算错误；
A A A
采用二阶段法，要把线性规划问题转化为两个线性规划问题来求解，计算量和计算机的储存量也随之增
大。能否不引入人工变量而直接求解呢？基于这一设想，本文提出线性规划的两种规范标准型，证明了任
一线性规划问题都可化为这两种规范标准型之一。给出了这两种规范标准型的求解算法。
线性规划标准型的两种规范形式
!
定理 任意一个线性规划问题都可化为以下两种规范形式之一：
!
) ⋯
! RLX-Y/!?!Z/(?(Z Z/)?)Z-)
⋯
#%!!?!Z%!(?(Z Z%!)?)Z?)Z!Y@!
⋯ （ ）
%(!?!Z%((?(Z Z%()?)Z?)Z(Y@( CD !
⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯
O&N&"
⋯
%(!?!Z%((?(Z Z%()?)Z?)Z(Y@(
， ，，⋯ ，
$?B!)BY!( )Z(
收稿日期：
())"<)+<)=
基金项目：山东科技大学济南校区科研基金资助项目
万方数据
作者简介：高国成（ ），男，河南人，硕士，教授，主要从事微分方程和最优化问题研究。
!>+!<运 筹 与 管 理 年第 卷
,