小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Life Time
  3. 正文

算法笔记之线性规划网络流问题(1)

2019年3月7日 1043点热度 0人点赞 0条评论

线性规划问题

遇到一个线性规划问题,该如何解决呢?
1. 确定决策变量。
2. 确定目标函数。
3. 找出约束条件。
4. 求最优解。

一般线性规划问题可以表示为如下形式。

公式1

约束条件为:

公式2

  • 变量满足约束条件的一组值成为线性规划问题的一个可行解。
  • 所有可行解构成的集合成为线性规划的可行区域。
  • 使目标函数取得极值的可行解称为最优解。
  • 在最优解处目标函数的值成最优值。

线性规划解的情况:
- 有唯一最优解。
- 有无数多个最优解。
- 没有最优解。

线性规划的标准型

标准型如下:

公式3

四个要求:

  1. 目标函数为最大值(即为max);
  2. 约束条件常数项bi>=0;
  3. 约束条件全部为等式约束;
  4. 决策变量xi非负约束。

线性规划标准型转化方法:

  1. 一般线性规划行驶中目标函数如果求最小值,那么令z'=-z,得到最优解后,加负号即可。
  2. 右端常数项小于零时,则不等式两边同乘-1,将其变成大于零;同时改变不等号的方向,保证恒等变形。
  3. 约束条件为大于与等于约束条件时,则在不等式左侧减去一个新的非负变量将不等式约束改为等式约束。例如2x1-3x2≥10,修改为:2x1-3x2-x3=10,x3>0。
  4. 约束条件为小于等于约束时,则在不等式左侧加去一个新的非负变量将不等式约束改为等式约束。
  5. 无约束的决策变量x,即可正可负的变量,则引入两个新的非负变量x'和x'',令x-x'-x'',其中x'≥0,x''≥0,将x带入线性规划模型。例如:2x1-3x2+x3=10,x3无约束,则可以修改为:x3=x4-x5,x4>0,x5>0,带入方程得到2x1-3x2+x4-x5=10,x4>0,x5>0。
    注意:引入的新的非负变量称为松弛变量。

单纯形算法图解

基本概念:
- 基本变量:每个约束条件中的系数为正,且只出现在一个约束条件中的变量。
- 非基本变量:除基本变量以外的变量。
- 基本可行解:满足标准形式约束条件的可行解称为基本可行解。
- 检验数:目标函数中非基本变量的技术。

基本定理:
- 最优解判别定理:若目标函数中关于非基本变量的所有系数小于等于0,则当前基本可行解就是最优解。
- 无穷多最优解判别定理:若目标函数中关于费基本变量的所有检验数小于等于0,同时存在某个非基本变量的检验数等于0,则线性规划问题有无穷多个最优解。
- 无界解定理:如果某个检验数cj大于0,而cj所对应的列向量的各分量a1j,a2j,...,amj都小于等于0,则该线性规划问题有无界解。

约束标准型线性规划问题单纯形算法步骤如下:

  1. 建立初始单纯形表。找出基本变量和非基本变量,将目标函数由非基本变量表示,建立初始单纯形表。注意:如果目标函数含有基本变量,要通过约束条件方程转换为非基本变量。 还要注意:基本变量的系数要转化为1 ,否则不能按照下面的计算方法。基本变量做行,非基本变量做列,检验数放第一行,常数项放低1列,约束条件中非基本变量的系数作为值,构造初始单纯形表。如下所示:
    约束条件
b x2 x3 x4
c 0 -1 3 -2
x1 7 3 -1 2
x5 12 -2 4 0
x6 10 -4 3 8
  1. 判断是否得到最优解。判别并检查目标函数的所有系数。
    • 如果所有的cj<=0,则已经获得最优解,算法结束。
    • 若在检验数cj中,有些为正数,但其中某一正的检验数所对应的列向量的各分量均小于等于0,则线性规划问题无界,算法结束。
    • 若在检验数cj中,有些为正数且它们对应的列向量中有正的分量,则转到第3步。
  2. 选入基变量。选取所有正检验数中最大的一个,记为ce,其对应的非基本变量为xe,称为入基变量,xe对应的列向量[a1e,a2e,...,ame]T为入基列。在本例中,x3为入基变量,x3对应的列向量为入基列,如下所示。

b x2 x3 x4
c 0 -1 3 -2
x1 7 3 -1 2
x5 12 -2 4 0
x6 10 -4 3 8
  1. 选离基变量、选取“常数列元素/入基列元素”正比值最小者,所对应的基本变量xk为离基变量。xk对应的行向量为离基行。在本例中,x5为离基变量,对应的行向量为离基行。
  2. 换基变换。在单纯形表上将入基变量和离基变量互换位置,即在本例中将x3和x5交换位置,换基变换后如下所示。
b x2 x5 x4
c 0 -1 3 -2
x1 7 3 -1 2
x3 12 -2 4 0
x6 10 -4 3 8
  1. 计算新的单纯形表。按照下面的方法计算新的单纯形表,然后转第2步。4个特殊位置如下:
    • 入基列:-原值/交叉位值(不包括交叉位)。
    • 离基行=原值/交叉位值(不包括交叉位)
    • 交叉位=原值取倒数。
    • c0位:原值+同行入基列元素*同列离基行元素/交叉位值。
    • 一般位置元素=原值-同行入基列元素*同列离基行元素/交叉位值。
b x2 x5 x4
c 9 0.5 -0.75 -2
x1 10 2.5 0.25 2
x3 3 -0.5 0.25 0
x6 1 -2.5 -0.75 8
  1. 判断是否得到最优解,若没有继续第3~6步,直到找到最优解或判定无界解停止。在本例中,再次选定基列变量x2和离基变量x1,将他们互换位置,重新计算单纯形表,得到下面的表。
b x1 x5 x4
c 11 -0.2 -0.8 -2.4
x2 4 0.4 0.1 0.8
x3 5 0.2 0.3 0.4
x6 11 1 -0.5 10

可以看出目标函数的检验数全部都小于0,得到最优解。c0就是我们要的最优值(11),而最优解是由基本变量对应的常数项组成的,即x2=4,x3=5,x6=11,非基本变量全部置零。以上算法获得的是max z',而本题要求是min z,所以答案是-11。

工厂最大效益——单纯形算法

题目描述

某食品加工厂有三个车间,第一车间用1个单位的原料N可以加工5个单位的产品A或者2个单位的产品B。产品A若直接出售,价格10元,如果第二车间继续加工,加工费5元,加工后售价19元,产品B直接出售16元,第三车间继续加工加工费4元,然后售价24元。原料N的单位购入价为5元,每工时工资为15元,第一车间加工一个单位N,需要0.05工时,第二个0.1工时,第三个0.08工时,每个月最多得到12000个N,工时最多为1000工时。如何生产,收益最大?

问题分析

假设变量:
x1:产品A的售出量。
x2:产品A在第二车间加工后售出量.
x3:产品B售出量。
x4:产品B在第三车间加工后售出量。
x5:第一车间所用原材料数量。

  • 第一车间所有原材料费和人工费为:5x5+0.05×15x5=5.75x5(下面计算盈利时,均已除去第一车间的材料和人工费)

  • A直接售出,盈利:10x1。

  • A加工后售出,因为有额外加工费、人工费:5+0.1×15=6.5,售价-额外成本=19-6.5=12.5,盈利12.5x2。
  • B直接售出,盈利16x3。
  • B加工后售出,额外费用4+0.08×15=5.2,售价-成本=24-5.2=18.8,盈利18.8x4。
  • 总盈利:z=10x1+12.5x2+16x3+18.8x4-5.75x5。
  • 所以目标函数和约束条件如下:

约束条件

完美图解

转化为标准型,目标函数也重新表示:

约束条件

基本变量为:x1,x3,x6,x7。
非基本变量:x2,x4,x5。

建立单纯形表如下:

b x2 x4 x5
c 0 2.5 2.8 76.25
x1 0 1 0 -5
x3 0 0 1 -2
x6 12000 0 0 1
x7 1000 0.1 0.08 0.05

具体图解过程不再重述。

代码实现

全局变量如下:

float kernel[100][100];//存储非单纯形表
char FJL[100] = {};//非基本变量
char JL[100] = {};//基本变量
int n, m, i, j;

代码内容如下:

void print()//输出单纯型表
{
    cout<<endl;
    cout<<"----------单纯形表如下:----------"<<endl;
    cout<<"  ";
    cout<<setw(7)<<"b ";
    for(i=1;i<=m;i++)
       cout<<setw(7)<<"x"<<FJL[i];
    cout<<endl;
    cout<<"c ";
    for(i=0;i<=n;i++)
    {
        if(i>=1)
            cout<<"x"<<JL[i];
        for(j=0;j<=m;j++)
           cout<<setw(7)<<kernel[i][j]<<" ";
        cout<<endl;
    }
}

void DCXA()
{
    float max1;  //max1用于存放最大的检验数
    float max2;  //max2用于存放最大正检验数对应的基本变量的最大系数
    int e=-1;    //记录入基列
    int k=-1;    //记录离基行
    float min;
    //循环迭代,直到找到问题的解或无解为止
    while(true)
    {
        max1=0;
        min=100000000;
        for(j=1;j<=m;j++)  //找入基列(最大正检验数对应的列)
        {
            if(max1<kernel[0][j])
            {
                max1=kernel[0][j];
                e=j;
            }
        }
        if(max1<=0) //最大值小于等于0,即所有检验数小于等于0,满足获得最优解的条件
        {
           cout<<endl;
           cout<<"获得最优解:"<<kernel[0][0]<< endl;
           print();
           break;
         }
        for(j=1;j<=m;j++)  //判断正检验数对应的列是否都小于等于0,如果是则无界解
        {
            max2=0;
            if(kernel[0][j]>0)
            {
                for(i=1;i<=n;i++) //搜索正检验数对应的列
                  if(max2<kernel[i][j])
                     max2=kernel[i][j];
                if(max2==0)
                {
                   cout<<"解无界"<<endl;
                   return;//退出函数,不能用break,因为它只是退出当前循环
                }
            }
        }
        for(i=1;i<=n;i++) //找离基行(常数列/入基列正比值最小对应的行)
        {
            float temp=kernel[i][0]/kernel[i][e]; //常数项在前,temp=fabs(temp);
            if(temp>0&&temp<min) //找离基变量
            {
               min=temp;
               k=i;
            }
        }
        cout<<"入基变量:"<<"x"<<FJL[e]<<" ";
        cout<<"离基变量:"<<"x"<<JL[k]<<endl;
       //换基变换(转轴变换)
        char temp=FJL[e];
        FJL[e]=JL[k];
        JL[k]=temp;
        for(i=0;i<=n;i++) //计算除入基列和出基行的所有位置的元素
        {
            if(i!=k)
            {
                for(j=0;j<=m;j++)
                {
                    if(j!=e)
                    {
                        if(i==0&&j==0) //计算特殊位c0,即目标函数的值
                           kernel[i][j]=kernel[i][j]+kernel[i][e]*kernel[k][j]/kernel[k][e];
                        else   //一般位置
                           kernel[i][j]=kernel[i][j]-kernel[i][e]*kernel[k][j]/kernel[k][e];
                    }
                }
            }
        }
        for(i=0;i<=n;i++) //计算特殊位,入基列的元素
        {
            if(i!=k)
                kernel[i][e]=-kernel[i][e]/kernel[k][e];
        }
        for(j=0;j<=m;j++) //计算特殊位,离基行的元素
        {
            if(j!=e)
              kernel[k][j]=kernel[k][j]/kernel[k][e];
        }
        //计算特殊位,交叉位置
        kernel[k][e]=1/kernel[k][e];
        print();
    }
}

复杂度分析

  1. 时间复杂度:在输入基本变量和非基本变量中用了n+m循环次数,在输入单纯形表时有nm此循环,打印最优解时有n+nm次的时间打印结果,在寻找入基列和离基行中,最坏情况下有O(n*m)次循环,在循环迭代中最坏情况需要2n迭代,则时间复杂度为O(2n)。
  2. 空间复杂度:O(1)。
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 算法 线性规划
最后更新:2019年3月7日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
志愿高校团体掠影 2010 S.V Beijing Travel 17:一个月后·一中! 2013北京暑假之行日程安排 暑假回顾奥特曼的安排 高考考生写给李华(Li Hua)的信(转自人人网) Welcome to Jinan!华夏大地聚焦济南,全运会即将开幕!
标签聚合
高中 python学习 Python 鸟哥的linux私房菜 算法 Java 学习 生活 linux leetcode
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号