运筹学单纯形法求解线性规划问题_运筹学单纯形法计算步骤

运筹学单纯形法求解线性规划问题_运筹学单纯形法计算步骤线性规划是研究在一组线性不等式或等式约束下使得某一线性目标函数取最大(或最小)的极值问题。

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

运筹学——线性规划及单纯形法求解

 

1. 线性规划的概念

线性规划是研究在一组线性不等式或等式约束下使得某一线性目标函数取最大(或最小)的极值问题。

 

2. 线性规划的标准形

 

clip_image002

 

特点目标函数极大等式约束变量非负

clip_image004clip_image006

则线性规划标准形的矩阵表达式为:

 

clip_image008

约定:clip_image010

 

如何化标准形:

(I) 目标函数实现极大化,即clip_image012,令clip_image014,则clip_image016

(II)约束条件为不等式

约束条件为“clip_image018” 不等式,则在约束条件的左端加上一个非负的松弛变量;

约束条件为“clip_image020” 不等式,则在约束条件的左端减去一个非负的松弛变量。

(III)若存在无约束的变量clip_image022,可令clip_image024,其中clip_image026

 

3. 单纯形法求解

(I) 化为标准形(要求clip_image028),确定初始基clip_image030,建立初始单纯形表(假设A矩阵中存在单位矩阵);

 

clip_image032

(II)若clip_image034,则已得到最优解,停止。否则转入下一步;

(III)若在clip_image036中,存在clip_image038,而clip_image040,则无最优解,停止。否则转入下一步;

(IV)由clip_image042,确定clip_image022[1]为换入变量,按clip_image045规则

clip_image047

可确定clip_image049为换出变量;

(V)以clip_image051为主元进行迭代

即将clip_image053 迭代成clip_image055

并将单纯形表clip_image057列中的clip_image049[1]换成clip_image022[2],得到新的单纯形表;

重复(ⅱ)~(ⅴ)。

4. 单纯形法求解例示

 
 
 
  clip_image002[1]

 

 

clip_image063

 

clip_image065

 

clip_image067

 

clip_image069

 

clip_image071

 

clip_image073

 

clip_image075

 

clip_image077

 

两阶段法

第一阶段求初始基可行解:在原线性规划问题中加入人工变量,使约束矩阵出现单位子矩阵,然后以这些人工变量之和W求最小为目标函数,构造如下模型:

 
  clip_image079

 

对上述模型求解(单纯形法),若W=0,说明问题存在基本可行解,可以进行第二个阶段;否则,原问题无可行解,停止运算。

 

第二阶段:在第一阶段的最终表中,去掉人工变量,将目标函数的系数换成原问题的目标函数系数,作为第二阶段计算的初始表(用单纯形法计算)。

 

clip_image081

 

例:

第一阶段

 

clip_image083

第二阶段

 

clip_image085

∴最优解为(4 1 9 0 0),目标函数 Z = –2

 

退化: 即计算出的θ(用于确定换出变量)存在有两个以上相同的最小比值,会造成下一次迭代中由一个或几个基变量等于零,这就是退化(会产生退化解)。

虽任意换出变量,目标函数值不变,但此时不同的基却表示为同一顶点,其特例是永远达不到最优解。需作如下处理:

⑴. .当clip_image087中出现两个以上最大值时,选下标最小非基变量换入变量;

⑵.当θ中出现两个以上最小值时,选下标最小的基变量为换出变量。

参考文献:

[1] 《运筹学》教材编写组. 运筹学. 北京: 清华大学出版社.

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166557.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Java8 Stream 之groupingBy 分组讲解

    Java8 Stream 之groupingBy 分组讲解本文主要讲解:Java8Stream之Collectors.groupingBy()分组示例Collectors.groupingBy()分组之常见用法功能代码:/** *使用java8streamgroupingBy操作,按城市分组list */ publicvoidgroupingByCity(){ Map<String,List<Employee>>map=employees.stream().collect(Collect

  • UML图:类图 –详细介绍

    UML图:类图 –详细介绍类图的概念描述类、接口及它们之间关系的图,显示系统中各个类的静态结构类图的元素类面向对象系统组织结构的核心对一组具有相同属性、操作、关系和语义的对象的抽象包括名称部分(Name)、属性部分(Attribute)和操作部分(Operation)类的组成名称属性操作名称:应该是一个名词,分为简单名称和路径名称,每个单词首字母大写属性:描述了类在软件系统中代表的事物(即对象)所具备的特性,类可以有任意数目的属性,也可以没有属性在UML中,类属性的语法为属性的可见性

  • k3 梅林固件设置_OpenWrt中,旁路由的设置与使用

    k3 梅林固件设置_OpenWrt中,旁路由的设置与使用旁路由,这神奇的名称,听着是不是有点不知所云?本文的目的,是让您知晓旁路由的概念,并掌握最基础的旁路由设置方法。一、什么是旁路由?旁路由又叫独臂路由,这一概念由杨过大侠首创(手动狗头)。旁路由一般是由CPU性能比较强的路由器来担当。旁路由的主要责任是帮助网络中的其他设备获取国外网站的数据。二、旁路由的接线方式及工作原理最基础最常规的旁路由接线方式是这样的基础的旁路由接线方式是不是有点挑战常识?主路…

  • 最长回文子串 python_最长回文子序列

    最长回文子串 python_最长回文子序列647.回文子串题目给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。示例1:输入:”abc”输出:3解释:三个回文子串:”a”,”b”,”c”示例2:输入:”aaa”输出:6解释:6个回文子串:”a”,”a”,”a”,”aa”,”aa”,”aaa”提示:输入的字符串长度不会超过10…

    2022年10月16日
  • Python入门:Anaconda和Pycharm的安装和配置「建议收藏」

    Python入门:Anaconda和Pycharm的安装和配置「建议收藏」子曰:“工欲善其事,必先利其器。”学习Python就需要有编译Python程序的软件,一般情况下,我们选择在Python官网下载对应版本的Python然后用记事本编写,再在终端进行编译运行即可,但是对于我这样懒的小白,我喜欢装一些方便的软件来辅助我编写程序。在学习Java时,正常情况选择安装JDK然后配置环境变量后,用记事本编写程序再在终端编译运行即可,而我一般选择安装JDK+MyEclipse。…

  • navicat for mysql 15 激活码【2021.10最新】

    (navicat for mysql 15 激活码)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号