当前位置: 首页 > news >正文

对偶问题的基本性质

写于:2024年1月3日晚

修改于:


原规划与对偶规划

原规划对偶规划
max ⁡ z = C T X s.t.  { A X ≤ b , 其中  X ( m ∗ 1 ) X ≥ 0 \begin{aligned} & \max \mathrm{z}=\mathbf{C}^T \mathbf{X} \\ & \text { s.t. }\left\{\begin{array}{l}\mathbf{A X} \leq \mathbf{b}, \quad \text { 其中 } \mathrm{X}_{\left(\mathrm{m}^* 1\right)} \\ \mathbf{X} \geq \mathbf{0}\end{array}\right.\end{aligned} maxz=CTX s.t. {AXb, 其中 X(m1)X0 min ⁡ w = Y b s.t.  { Y A ≥ C T , 其中  Y ( 1 ∗ n ) Y ≥ 0 \begin{aligned} & \min w=\mathbf{Y b} \\ & \text { s.t. }\left\{\begin{array}{l}\mathbf{Y A} \geq \mathbf{C}^T, \text { 其中 } \mathrm{Y}_{\left(1^* \mathrm{n}\right)} \\ \mathbf{Y} \geq 0\end{array}\right.\end{aligned} minw=Yb s.t. {YACT, 其中 Y(1n)Y0
max ⁡ z = ∑ j = 1 n c j x j s.t.  { ∑ j = 1 n a i j x j ≤ b i ( i = 1 , 2 , … , m ) x j ≥ 0 ( j = 1 , 2 , … , n ) \begin{aligned} & \max \mathrm{z}=\sum_{j=1}^n c_j x_j \\ & \text { s.t. }\left\{\begin{array}{l}\sum_{j=1}^n a_{i j} x_j \leq b_i(i=1,2, \ldots, m) \\ x_j \geq 0(j=1,2, \ldots, n)\end{array}\right.\end{aligned} maxz=j=1ncjxj s.t. {j=1naijxjbi(i=1,2,,m)xj0(j=1,2,,n) min ⁡ w = ∑ i = 1 m b i y i s.t.  { ∑ i = 1 m a i j y i ≥ c j ( j = 1 , 2 , … , n ) y i ≥ 0 ( i = 1 , 2 , … , m ) \begin{aligned} & \min w=\sum_{i=1}^m b_i y_i \\ & \text { s.t. }\left\{\begin{array}{l}\sum_{i=1}^m a_{i j} y_i \geq c_j(j=1,2, \ldots, n) \\ y_i \geq 0(i=1,2, \ldots, m)\end{array}\right.\end{aligned} minw=i=1mbiyi s.t. {i=1maijyicj(j=1,2,,n)yi0(i=1,2,,m)

对称性:对偶问题的对偶问题是原问题。任何一个线性规划问题存在且有唯一的对偶问题。


弱对偶性:若 X ‾ \overline{\mathbf{X}} X 是原问题的可行解, Y ‾ \overline{\mathbf{Y}} Y 是对偶问题的可行解,则存在 C X ‾ ⩽ Y ‾ b \mathbf{C} \overline{\mathbf{X}} \leqslant \overline{\mathbf{Y}} \mathbf{b} CXYb

原问题最优目标函数值是对偶目标函数值的下界,对偶问题最优目标函数值是原问题目标函数值的上界。
在这里插入图片描述

坐标轴理解: 坐标轴自左向右逐渐增大。如果原问题和对偶问题都有可行解 X ‾ 、 Y ‾ \overline{\mathbf{X}} 、 \overline{\mathbf{Y}} XY,那么说明原问题和对偶问题都存在某个可行解对应的函数值,而因为原问题为 max ⁡ \max max 类型,则更优解会在 Z ∗ \mathrm{Z}^* Z 右侧,而对偶问题为 m i n \mathrm{min} min 类型,更优解会在 W ∗ \mathrm{W}^* W 左侧,两者一定会在某一处取得相同的最优目标函数值,因此存在 C X ‾ ⩽ Y ‾ b \mathbf{C} \overline{\mathbf{X}} \leqslant \overline{\mathbf{Y}} \mathbf{b} CXYb

将原问题和对偶问题看做是两个人在角力,目标函数值视为擂台。原问题自左向右冲,对偶问题自右向左冲,如果问题有可行解,那么就在擂台上,如果有无界解,那么就将对方挤出擂台。


无界性

  1. 若原问题/对偶问题有无界解,那么对偶问题/原问题无可行解
    在这里插入图片描述
    如果原问题有无界解,说明原问题最优值随着坐标轴一直向右延伸,对偶问题被挤出擂台,所以对偶问题无可行解。

  2. 若原问题/对偶问题无可行解,那么对偶问题/原问题无可行解或有无界解

  3. 若原问题有可行解,而对偶问题无可行解,那么原问题有无界解

  4. 若对偶问题有可行解,而原问题无可行解,那么对偶问题有无界解

补充:原问题和对偶问题中有一个为无穷多/唯一最优解,无法退出另一个最优解的情况。


最优性:设 X ^ \widehat{\mathbf{X}} X 是原问题的可行解, Y ^ \widehat{\mathbf{Y}} Y 是对偶问题的可行解,当 C X ^ = Y ^ b \mathbf{C} \hat{\mathbf{X}}=\hat{\mathbf{Y}} \mathbf{b} CX^=Y^b 时, X ^ \hat{\mathbf{X}} X^ Y ^ \hat{\mathbf{Y}} Y^ 是最优解。
对偶定理:
表述1:若原问题和对偶问题都有可行解,则都有最优解,而且最优解的目标函数值相等。
表述2:若原问题有最优解,则对偶问题也有最优解,而且目标函数值相等。


互补松驰定理:线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,那么该约束条件取严格等式;反之如果约束条件取严格不等式,那么对应的对偶变量一定为零。也即:
{ y i ∗ ( ∑ j = 1 n a i j x j − b i ) = 0 ( i = 1 , 2 , … , m ) x j ∗ ( ∑ i = 1 m a i j y i − c j ) = 0 ( j = 1 , 2 , … , n ) \left\{\begin{array}{l} y_i *\left(\sum_{j=1}^n a_{i j} x_j-b_i\right)=0(i=1,2, \ldots, m) \\ x_j *\left(\sum_{i=1}^m a_{i j} y_i-c_j\right)=0(j=1,2, \ldots, n) \end{array}\right. {yi(j=1naijxjbi)=0(i=1,2,,m)xj(i=1maijyicj)=0(j=1,2,,n)

应用:由原/对偶问题最优解求对偶/原问题最优解

相关文章:

对偶问题的基本性质

写于:2024年1月3日晚 修改于: 原规划与对偶规划 原规划对偶规划 max ⁡ z C T X s.t. { A X ≤ b , 其中 X ( m ∗ 1 ) X ≥ 0 \begin{aligned} & \max \mathrm{z}\mathbf{C}^T \mathbf{X} \\ & \text { s.t. }\left\{\begin{array}{l}\mat…...

Google Chrome 现在会在后台扫描泄露的密码

谷歌表示,Chrome 安全检查功能将在后台运行,检查网络浏览器中保存的密码是否已被泄露。 如果桌面用户正在使用标记为危险的扩展程序(从 Chrome Web Store 中删除)、最新的 Chrome 版本,或者如果启用安全浏览来阻止 Go…...

【Matlab】PSO-BP 基于粒子群算法优化BP神经网络的数据时序预测(附代码)

资源下载: https://download.csdn.net/download/vvoennvv/88689096 目录 【Matlab】BP 神经网络时序预测算法 【Matlab】CNN卷积神经网络时序预测算法 【Matlab】ELM极限学习机时序预测算法 【Matlab】基于遗传算法优化BP神经网络 (GA-BP)的数据时序预测 【Mat…...

Linux 485驱动通信异常

背景 前段时间接到一个项目,要求用主控用485和MCU通信。将代码调试好之后,验证没问题就发给测试了。测试测的也没问题。 但是,到设备量产时,发现有几台设备功能异常。将设备拿回来排查,发现是485通信有问题&#xff…...

mybatis配置与标签大全

文章目录 mybatis配置与标签大全mybatis的配置属性(properties)设置(settings)类型别名(typeAliases)类型处理器(typeHandlers)对象工厂(objectFactory)插件&…...

Mysql的基本用法(上)非常详细、快速上手

上篇结束了java基础,本篇主要对Mysql中的一些常用的方法进行了总结,主要对查询方法进行了讲解,包括重要的多表查询用到的内连接和外连接等,以下代码可以直接复制到可视化软件中,方便阅读以及练习; SELECT *…...

使用Vite创建React + TypeScript(node版本为16.17.0,含资源下载)

PC端 安装指令: npm create vitelatest react-ts-pro -- --template react-tsVite是一个框架无关的前端工具链,可以快速的生成一个React TS的开发环境,并且可以提供快速的开发体验说明: 1. npm create vitelatest固定写法&#…...

Springboot集成RabbitMq二

接上一篇:Springboot集成RabbitMq一-CSDN博客 1、搭建项目-消费者 与之前一样 2、创建配置类 package com.wym.rabbitmqconsumer.utils;import org.springframework.amqp.core.Binding; import org.springframework.amqp.core.BindingBuilder; import org.spring…...

机器学习笔记 - 基于Python的不平衡数据的欠采样技术

一、简述 随着从不同的来源生成和捕获大量数据。尽管信息量巨大,但它往往反映了现实世界现象的不平衡分布。数据不平衡的问题不仅仅是统计上的挑战,它对数据驱动模型的准确性和可靠性具有深远的影响。 以金融行业欺诈检测为例。尽管我们希望避免欺诈,因为其具有高度破坏性,…...

facebook广告的基础知识

Facebook广告是在Facebook、Instagram、Audience Network等与Facebook相关的SNS和服务上投放的广告。以下是关于Facebook广告的基础知识: 广告类型: 静态图片广告:主要通过Facebook的新闻提要投放的图片广告,可以张贴产品和服务…...

java常见面试题:什么是异常?Java中的异常有哪些分类?

异常是一个汉语词语,读音为y chng,指非正常的;不同于平常的;非常。在Java中,异常(Exception)是程序在运行过程中出现的不正常情况,例如除以零、数组越界等。异常分为两大类&#xff…...

类的加载顺序问题-demo展示

面试的的时候经常会被问到包含静态代码块、实例代码块和构造器等代码结构的加载顺序问题,下面借用一个面试题,回顾一下类的代码加载顺序。 public class AooTest {public static void main(String[] args) {AooTest.f1();}static AooTest test1 new Ao…...

[蓝桥杯2020国赛]答疑

答疑 题目描述 有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。 老师可以安排答疑的顺序,同学们要依次进入老师办公室答疑。 一位同学答疑的过程如下: 首先进入办公室,编号为 i 的同学需要 si​ 毫秒的时间。然后同学问…...

【AIGC表情prompt】提示词练习技巧

表情类提示词练习技巧 医疗机器人,男人笑脸景深,数据,座标,12k,c4d渲染,高分辨率,,暖色调,高清对比 医疗机器人,男人微笑,景深,数据,座标&#xf…...

SpringBoot项目的三种创建方式

手动创建方式&#xff1a; ①&#xff1a;新建maven项目 ②&#xff1a;引入依赖 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.3.10.RELEASE</version>&l…...

【docker实战】01 Linux上docker的安装

Docker CE是免费的Docker产品的新名称&#xff0c;Docker CE包含了完整的Docker平台&#xff0c;非常适合开发人员和运维团队构建容器APP。 Ubuntu 14.04/16.04&#xff08;使用 apt-get 进行安装&#xff09; # step 1: 安装必要的一些系统工具 sudo apt-get update sudo ap…...

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK设置相机的图像剪切(ROI)功能(C#)

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK设置相机的图像剪切&#xff08;ROI&#xff09;功能&#xff08;C#&#xff09; Baumer工业相机Baumer工业相机的图像剪切&#xff08;ROI&#xff09;功能的技术背景CameraExplorer如何使用图像剪切&#xff08;ROI&#xff09;…...

软件测试之安全测试

一、测试范围 管理系统&#xff1a;url、登录框、搜索框、输入框、文件上传、文件下载 客户端&#xff1a;搜索框、输入框、文件上传、系统功能 二、测试点 密码安全 XSS注入 SQL注入 操作越权 上传安全 下载安全 三、工具 fiddler sqlmap 同时&#xff0c;在这我为…...

【华为OD机试真题2023CD卷 JAVAJS】会议室占用时间

华为OD2023(C&D卷)机试题库全覆盖,刷题指南点这里 会议室占用时间 时间限制:1s 空间限制:256MB 限定语言:不限 题目描述: 现有若干个会议,所有会议共享一个会议室,用数组表示每个会议的开始时间和结束时间,格式:[[会议1开始时间,会议1结束时间], [会议2开始时间…...

UR5机器人的旋转向量转换到四元数,再从四元数转换到旋转向量python代码

能够通过接口获得UR5机器人末端在基坐标系下的位姿&#xff0c;姿态表示方法是用旋转向量表示的&#xff0c;一般会涉及到四元数和旋转向量之间的转换。 1、方法一 import numpy as np from pytransform3d import rotations as pr import copy # 输入旋转向量 quaternion2 n…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...