单纯形法求解线性规划问题(C++实现代码)

作者:弋江区易采办公设备经营部  发布时间:2017-09-03 12:39:54
单纯形法求解线性规划问题(C++实现代码)

(1) 单纯形法是解线性规划问题的一个重要方法。
其原理的基本框架为:
第一步:将LP线性规划变标准型,确定一个初始可行解(顶点)。
第二步:对初始基可行解最优性判别,若最优,停止;否则转下一步。
第三步:从初始基可行解向相邻的基可行解(顶点)转换,且使目标值有所改善—目标函数值增加,重复第二和第三步直到找到最优解。
(2) 用程序进行运算前,要将目标函数及约束方程变成标准形式。

这里写图片描述


于非标准形式须作如下变换:
a) 目标函数为极小值min z=CX时,转换为max z=-CX形式;
b) 在约束方程中有 “≤”时,在加上一个松弛变量;
c) 在约束方程中有 “≥”时,采用减去一个松弛变量,再加上一个人工变量;
d) 在约束方程中有 “=”时,加上一个人工变量;
e) 所有的人工变量,松弛变量的目标函数系数置为0。
(3) 对于标准形式的线性规划问题。用单纯形法计算步骤的框图。

2 程序测试及结果:

线性规划问题如下:
max z=2*x1-3*x2+3x3;
x1+ x2 -x3<=7;
x1- x2 +x3<=-7;
x1-2*x2 +2*x3<=4;
x1,x2,x3>=0;

这里写图片描述

3 C++实现代码 // Simplex.cpp : 定义控制台应用程序的入口点。 // // /********************************* ----------------------------------- 单纯形法求解线性规划问题(C++实现代码) ----------------------------------- Author:牧之丶 Date:2014年 Email:bzhou84@163.com **********************************/ #include stdafx.h #include #include using namespace std; #define M 10000 //全局变量大M float juzhen[11][31];//核心矩阵表 int m=0,n=0,t=0;//m:结构向量的个数 //n:约束不等式个数 //t:目标函数类型:-1代表求求最小值,1代表求最大值 void input() //输入接口函数 { int i,j; cout<<----------单纯形法的参 数 输 入-----------<>m; cout<

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:湖北SEO http://hubei.raoyu.net

  • 上一篇:Python 类型
  • 下一篇:最后一页
  •