当前位置： 首页 > article >正文

线性规划的标准形式

article 2025/3/21 15:08:22

标准形式的定义

  • 目标函数：最大化线性目标函数 \max \; z = c^T x, 其中，x 是决策变量向量，c  是目标系数向量。

  • 约束条件：等式形式约束 A x = b, 其中，A 是约束系数矩阵，b 是常数项向量。

  • 变量非负约束： x \geq 0。

因此，标准形式可以写成：

\max \; z = c^T x, \quad \text{subject to} \quad A x = b, \; x \geq 0.

如何将线性规划问题化为标准形式？

在实际问题中，线性规划模型的形式可能不符合标准形式，需要进行如下转换：

1. 目标函数方向转换

  • 如果目标函数是最小化（min⁡z ），将其转换为最大化形式： \min z = -\max (-z)。 因此，将目标函数的系数乘以 -1。

2. 不等式约束转为等式约束

  • “≤”约束： 如果某约束为 a_i^T x \leq b_i,则引入松弛变量 s_i \geq 0，a_i^T x + s_i = b_i.

  • “≥”约束： 如果某约束为 a_i^T x \geq b_i, 则引入剩余变量（也叫过剩变量）s_i \geq 0： a_i^T x - s_i = b_i.

3. 消除自由变量

  • 如果某变量x_j无非负约束（即 x_j 可以取正数或负数），用两个非负变量替换： x_j = x_j^+ - x_j^-, 其中 x_j^+, x_j^- \geq 0。

4. 确保变量非负

  • 标准形式要求所有变量均满足非负约束，因此需要处理自由变量或带负号的变量。

示例

原始问题

\min z = 3x_1 + 2x_2, \quad \text{subject to:}

x_1 + x_2 \geq 4,\quad 3x_1 + 2x_2 \leq 6,\quad x_1 \; \text{free}.

标准化过程

  1. 目标函数方向转换： 将 min⁡z 转换为 max⁡z ： z' = -z = -3x_1 - 2x_2

  2. 处理约束：

    • 第一约束 x_1 + x_2 \geq 4： 引入剩余变量 s_1 \geq 0： x_1 + x_2 - s_1 = 4.

    • 第二约束 3x_1 + 2x_2 \leq 6： 引入松弛变量 s_2 \geq 0： 3x_1 + 2x_2 + s_2 = 6.

  3. 处理自由变量： x_1为自由变量，替换为x_1 = x_1^+ - x_1^-，其中 x_1^+, x_1^- \geq 0。

  4. 整理结果： 标准形式为：

\max z' = -3(x_1^+ - x_1^-) - 2x_2,

subject to:

(x_1^+ - x_1^-) + x_2 - s_1 = 4,

3(x_1^+ - x_1^-) + 2x_2 + s_2 = 6,

x_1^+, x_1^-, x_2, s_1, s_2 \geq 0.


http://www.kler.cn/a/592637.html

相关文章：

  • Golang开发
  • 【Dive Into Stable Diffusion v3.5】1：开源项目正式发布——深入探索SDv3.5模型全参/LoRA/RLHF训练
  • 使用 Wireshark 在 Ubuntu 22.04 上抓包分析网络流量
  • 危化品经营单位考试：从基础夯实到能力提升的进阶之路​
  • Docker 存储
  • 麒麟服务器操作系统Node.js环境部署手册
  • 当今前沿技术：改变生活的创新趋势
  • 微信小程序检测滚动到某元素位置的计算方法
  • 黑马跟学.苍穹外卖.Day08
  • Android Launcher3 首屏图标锁定技术方案解析
  • docker登陆问题
  • Linux 安装apache服务
  • Spring Boot Bean 的生命周期管理：从创建到销毁
  • Eclipse 创建 Java 类
  • 【前端 vue 或者麦克风，智能语音识别和播放功能】
  • 利用flex布局写的一个样式
  • Python的内置函数 - min()
  • 英伟达“AI 超级碗”开幕
  • 事件、页面跳转、wxml语法——微信小程序学习笔记
  • 机器学习 Day08，案例实现，代码学习，数据分析基本完成