当前位置: 首页 > 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…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

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…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...