欢迎访问 生活随笔!

生活随笔

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

最优化——线性规划总结1(线性规划标准型,规范型,顶点)

发布时间:2025/1/21 编程问答 13 豆豆
生活随笔 收集整理的这篇文章主要介绍了 最优化——线性规划总结1(线性规划标准型,规范型,顶点) 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

文章目录

  • 线性规划的形式
    • 标准型
    • 规范型
  • 线性规划的求解思路
    • 前提条件
    • 主要思路
    • 怎么搞
    • 一些概念
    • 线性规划标准形式的基本定理

线性规划的形式

标准型


规范型


线性规划的求解思路

前提条件

线性规划:凸优化(凸集上的凸函数的优化)

线性规划的可行集是凸集,优化函数是凸函数(仿射函数嘛)

总有顶点是最优解,所有顶点组成的集合总是有限集,所以可以在顶点集中找到最优解。

主要思路

根据前提条件来看,我们求解线性规划的思路:找到所有的顶点,在顶点中找到最优的那个,就是最优解。相当于缩小了搜索范围。

怎么搞

首先计算顶点:顶点是改点所有起作用约束构成的线性方程组的唯一解。
因为所有的线性规划形式都能转换成标准型,所以这里只考虑标准型的顶点,这也是单纯形法的思路。
标准型顶点的等价描述(一):

标准型顶点的等价描述(二):

一些概念

线性规划标准形式的基本定理

定理1:标准线性规划型问题若有可行解,则至少存在一个基本可行解
定理2:标准线性规划型问题若有有限的最优解,则其中一定有一个是基本可行解。
定理3:若标准线性规划型问题的某个基可行解比周围的基可行解都要好,那么这个基可行解就是最优解。

总结

以上是生活随笔为你收集整理的最优化——线性规划总结1(线性规划标准型,规范型,顶点)的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错,欢迎将生活随笔推荐给好友。