首页 > 编程语言 >对偶理论和对偶单纯形法——Python实现

对偶理论和对偶单纯形法——Python实现

时间：2024-06-01 14:45:12浏览次数：15  
标签：matrix 单纯形法 Python 0.00 min print row 对偶

对偶单纯形法是从对偶可行性逐步搜索出原始问题最优解的方法。由线性规划问题的对偶理论，原始问题的检验数对应于对偶问题的一组基本可行解或最优解；原始问题的一组基本可行解或最优解对应于对偶问题的检验数；原始问题约束方程的系数矩阵的转置是对偶问题约束条件方程的系数矩阵。所以，在求解常数项小于零的线性规划问题时，可以把原始问题的常数项视为对偶问题的检验数，原始问题的检验数视为对偶问题的常数项。

一、对偶理论

若原问题为 \(LP_1\)

\[\max z=C X\\ s.t. \left\{\begin{array}{l}A X \leq b \\ X \geq b \end{array}\right. \]

则其对偶问题定义为 \(LP_2\)

\[\begin{aligned} & \qquad \min w=Y^T b \\ & \text { s.t. }\left\{\begin{array}{l} A^T Y \geq C^T \\ Y \geq 0 \end{array}\right. \end{aligned} \]

  • 弱对偶性: 如果 \(X\) 是原问题的可行解， \(Y\) 是对偶问题的可行解，则 \(C X \leq Y^T b\)证明: \(Y^T \geq Y^T A X=\left(Y^T A X\right)^T=X^T A^T Y \geq X^T C^T=C X\)推论:
  • 最优性: 如果 \(X\) 是原问题的可行解， \(Y\) 是对偶问题的可行解, 且 \(C X=Y^T b\), 则 \(X\) 和 \(Y\) 分别为原问题和对偶问题的最优解
  • 无界性: 如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解
  • 强对偶性: 如果原问题有最优解，则其对偶问题也一定具有最优解，且max \(z=\min w\)

证明：设 \(\mathrm{B}\) 为原问题标准形式的可行解基，且其基解为最优解，则由最优性条件应有检验数全部小于等于零：

\[-C_B B^{-1} \leq 0, \theta=C-C_B B^{-1} A \leq 0 \]

从而可得:

\[A^T B^{-T} C_B^T \geq C^T, B^{-T} C_B^T \geq 0 \]

所以 \(B^{-T} C_B^T\) 是对偶问题的一个可行解，且

\[\left(B^{-T} C_B^T\right)^T b=C_B B^{-1} b=\max z \]

由最优性可知， \(B^{-T} C_B^T\) 为对偶问题的最优解，且 \(\max z=\min w\)

  • 互补昖驰性: 在线性规划问题的最优解中，如果某一约束条件的对偶变量值非零，则该约束条件严格取等，反之，如果约束条件取不等式，则对应的对偶变量一定为o，可以表示为 \(Y^T(b-A X)=0\)
    证明: 由强弱偶性可知 \(C X=Y^T b\) ，

\[\begin{aligned} & \text { 又 } \because C X=X^T C^T \leq X^T A^T Y=Y^T A X \leq Y^T b \\ & \therefore Y^T A X=Y^T b \Longrightarrow Y^T(b-A X)=0 \end{aligned} \]

  • 基解互补性: 原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变量对应对偶问题的变量对偶问题的剩余变量对应原问题的变量.这些互相对应的变量如果在一个问题的解中是基变量则在另一个问题的解中是非基变量; 将这对互补的集解分别带入原问题和对偶问题的目标函数中有 \(z=w\)。

二、对偶单纯形法迭代-python实现

流程图 原理 关系

\[\begin{align*} \text{min } Z &= 15x_1 + 24x_2 + 5x_3 \\ & \text{subject to: } \ & \\ & 6x_2 + x_3 \geq 2 \\ & 5x_1 + 2x_2 + x_3 \geq 1 \\ & x_i \geq 0, \quad (i = 1,2,3) \end{align*} \]

"""
对偶单纯形法
min z=15*x1+24*x2+5*x3
      6*x2+x3>=2
      5*x1+2*x2+x3>=1
      x1,x2>=0
标准化后格式
max z=-15*x1-24*x2-5*x3
      -6*x2-x3+x4=-2
      -5*x1-2*x2-x3+x5=-1
      x1,x2,x3,x4,x5>=0     
"""
import numpy as np

#根据线性规划要改变的数据
Cj = [-15, -24, -5, 0, 0]  # Coefficients of the objective function
constraints_matrix = [[-2, 0, -6, -1, 1, 0], [-1, -5, -2, -1, 0, 1]]  # Constraints matrix (with RHS)
z = [0, -15, -24, -5, 0, 0]  # Z-row
Xb = [4, 5]  # Basis variables (indices of slack variables)
Cb = [0, 0]  # Coefficients of basis variables

#为便于表示而生成
C = [0] + Cj
print(C)

# Output simplex table
def show():
    print("--" * 50)
    print("|               Cj               ", end='|')
    for i in Cj:
        print(f"{i:.2f}".center(10), end='|')
    
    print("--" * 50)
    print("|    Cb    |    Xb    |    b     ", end='|')
    for i in range(len(Cj)):
        print(("X" + str(i + 1)).center(10), end='|')
    
    print("--" * 50)
    for i in range(len(constraints_matrix)):
        print("|", end="")
        print(f"{Cb[i]:.2f}".center(10), end='|')
        print(("X" + str(Xb[i])).center(10), end='|')
        for j in range(len(constraints_matrix[0])):
            print(f"{constraints_matrix[i][j]:.2f}".center(10), end="|")
        
        print("--" * 50)
    print("|          Z          ", end='|')
    for i in range(len(z)):
        print(f"{z[i]:.2f}".center(10), end='|')
    
    print("--" * 50)
    print("**" * 50)
    
show()


def fu():
    global constraints_matrix, z, Xb, Cb  # Declare global variables

    # Extracting the first column
    first_column = [row[0] for row in constraints_matrix]
    print(first_column)

    # Finding the index of the minimum value in the first column
    min_index = first_column.index(min(first_column))
    print("Index of the minimum value in the first column:", min_index)

    # Extract the row corresponding to min_index
    min_row = constraints_matrix[min_index]

    # Calculate the ratios z / min_row
    ratios = [z[i] / min_row[i] if min_row[i] != 0 else float('inf') for i in range(len(z))]

    # Filter out the non-positive values from z and corresponding min_row
    filtered_ratios = [ratios[i] for i in range(len(ratios)) if z[i] < 0 and min_row[i] < 0]

    # Find the minimum ratio and its index in z
    if filtered_ratios:
        min_ratio = min(filtered_ratios)
        min_ratio_index = ratios.index(min_ratio)
        print("Minimum ratio:", min_ratio)
        print("Index of the minimum ratio in z:", min_ratio_index)
    else:
        print("No valid ratio found")
        return

    # Updating Xb
    Xb[min_index] = min_ratio_index 
    print("Updated basis variables Xb:")
    print(Xb)

    # Updating Cb based on Xb
    Cb = [C[Xb[i]] for i in range(len(Xb))]
    print("Updated coefficients of basis variables Cb:")
    print(Cb)

    # Extract columns according to Xb to form matrix B
    B = [[row[Xb[0]], row[Xb[1]]] for row in constraints_matrix]
    print("Matrix B:")
    for row in B:
        print([f"{val:.2f}" for val in row])

    try:
        # Calculate the inverse of matrix B
        B_matrix = np.array(B)
        B_inv = np.linalg.inv(B_matrix)
    except np.linalg.LinAlgError:
        print("Matrix B is singular, skipping this iteration.")
        return

    print("Inverse of matrix B (B_inv):")
    print(B_inv)

    # Update z
    z_update = (np.array(C[1:]) - np.dot(np.array(Cb), np.dot(B_inv, np.array(constraints_matrix)[:, 1:]))).tolist()
    z = [z[0]] + z_update  # Add the first element back to z

    # Update constraints_matrix with the inverse of B
    constraints_matrix = np.dot(B_inv, np.array(constraints_matrix)).tolist()

# Iterate until all elements in the first column of constraints_matrix are non-negative
while any(row[0] < 0 for row in constraints_matrix):
    fu()
    show()

三、对偶单纯形法迭代示例

\[\begin{align*} \text{min } Z &= 9x_1 + 12x_2 + 15x_3 \\ & \text{subject to: } \ & \\ & 2x_1 + 2x_2 + x_3 \geq 10 \\ & 2x_1 + 2x_2 + 4x_4 \geq 12 \\ & x_1 + x_2 + 5x_4 \geq 14 \\ & x_i \geq 0, \quad (i = 1,2,3) \end{align*} \]

import numpy as np

Cj = [-9, -12, -15, 0, 0, 0]  # 要求的函数
constraints_matrix = [
    [-10, -2, -2, -1, 1, 0, 0],
    [-12, -2, -3, -1, 0, 1, 0],
    [-14, -1, -1, -5, 0, 0, 1]
]  # 每个子列表第一位为b
z = [0, -9, -12, -15, 0, 0, 0]
Xb = [4, 5, 6]
Cb = [0, 0, 0]

# 为便于表示而生成
C = [0] + Cj

# Output simplex table
def show():
    print("--" * 50)
    print("|               Cj               ", end='|')
    for i in Cj:
        print(f"{i:.2f}".center(10), end='|')
    print()
    
    print("--" * 50)
    print("|    Cb    |    Xb    |    b     ", end='|')
    for i in range(len(Cj)):
        print(("X" + str(i + 1)).center(10), end='|')
    print()
    
    print("--" * 50)
    for i in range(len(constraints_matrix)):
        print("|", end="")
        print(f"{Cb[i]:.2f}".center(10), end='|')
        print(("X" + str(Xb[i])).center(10), end='|')
        for j in range(len(constraints_matrix[0])):
            print(f"{constraints_matrix[i][j]:.2f}".center(10), end='|')
        print()
        
    print("--" * 50)
    print("|          Z          ", end='|')
    for i in range(len(z)):
        print(f"{z[i]:.2f}".center(10), end='|')
    print()
    
    print("--" * 50)
    print("**" * 50)

show()

def fu():
    global constraints_matrix, z, Xb, Cb  # Declare global variables

    # Extracting the first column
    first_column = [row[0] for row in constraints_matrix]
    print("First column:", first_column)

    # Finding the index of the minimum value in the first column
    min_index = first_column.index(min(first_column))
    print("Index of the minimum value in the first column:", min_index)

    # Extract the row corresponding to min_index
    min_row = constraints_matrix[min_index]

    # Calculate the ratios z / min_row
    ratios = [z[i] / min_row[i] if min_row[i] != 0 else float('inf') for i in range(len(z))]
    print("Ratios:", ratios)

    # Filter out the non-positive values from z and corresponding min_row
    filtered_ratios = [ratios[i] for i in range(len(ratios)) if z[i] < 0 and min_row[i] < 0]

    # Find the minimum ratio and its index in z
    if filtered_ratios:
        min_ratio = min(filtered_ratios)
        min_ratio_index = ratios.index(min_ratio)
        print("Minimum ratio:", min_ratio)
        print("Index of the minimum ratio in z:", min_ratio_index)
    else:
        print("No valid ratio found")
        return

    # Updating Xb
    Xb[min_index] = min_ratio_index 
    print("Updated basis variables Xb:")
    print(Xb)

    # Updating Cb based on Xb
    Cb = [C[Xb[i]] for i in range(len(Xb))]
    print("Updated coefficients of basis variables Cb:")
    print(Cb)

    # Extract columns according to Xb to form matrix B
    B = [[row[Xb[0]], row[Xb[1]], row[Xb[2]]] for row in constraints_matrix]
    print("Matrix B:")
    for row in B:
        print([f"{val:.2f}" for val in row])

    try:
        # Calculate the inverse of matrix B
        B_matrix = np.array(B)
        B_inv = np.linalg.inv(B_matrix)
    except np.linalg.LinAlgError:
        print("Matrix B is singular, skipping this iteration.")
        return

    print("Inverse of matrix B (B_inv):")
    print(B_inv)

    # Update z
    z_update = (np.array(C[1:]) - np.dot(np.array(Cb), np.dot(B_inv, np.array(constraints_matrix)[:, 1:]))).tolist()
    z = [z[0]] + z_update  # Add the first element back to z

    # Update constraints_matrix with the inverse of B
    constraints_matrix = np.dot(B_inv, np.array(constraints_matrix)).tolist()

# Iterate until all elements in the first column of constraints_matrix are non-negative
while any(row[0] < 0 for row in constraints_matrix):
    fu()
    show()
    input("按回车键继续...")

----------------------------------------------------------------------------------------------------
|               Cj               |  -9.00   |  -12.00  |  -15.00  |   0.00   |   0.00   |   0.00   |
----------------------------------------------------------------------------------------------------
|    Cb    |    Xb    |    b     |    X1    |    X2    |    X3    |    X4    |    X5    |    X6    |
----------------------------------------------------------------------------------------------------
|   0.00   |    X4    |  -10.00  |  -2.00   |  -2.00   |  -1.00   |   1.00   |   0.00   |   0.00   |
|   0.00   |    X5    |  -12.00  |  -2.00   |  -3.00   |  -1.00   |   0.00   |   1.00   |   0.00   |
|   0.00   |    X6    |  -14.00  |  -1.00   |  -1.00   |  -5.00   |   0.00   |   0.00   |   1.00   |
----------------------------------------------------------------------------------------------------
|          Z          |   0.00   |  -9.00   |  -12.00  |  -15.00  |   0.00   |   0.00   |   0.00   |
----------------------------------------------------------------------------------------------------
****************************************************************************************************
----------------------------------------------------------------------------------------------------
|               Cj               |  -9.00   |  -12.00  |  -15.00  |   0.00   |   0.00   |   0.00   |
----------------------------------------------------------------------------------------------------
|    Cb    |    Xb    |    b     |    X1    |    X2    |    X3    |    X4    |    X5    |    X6    |
----------------------------------------------------------------------------------------------------
|   0.00   |    X4    |  -7.20   |  -1.80   |  -1.80   |   0.00   |   1.00   |   0.00   |  -0.20   |
|   0.00   |    X5    |  -9.20   |  -1.80   |  -2.80   |   0.00   |   0.00   |   1.00   |  -0.20   |
|  -15.00  |    X3    |   2.80   |   0.20   |   0.20   |   1.00   |   0.00   |   0.00   |  -0.20   |
----------------------------------------------------------------------------------------------------
|          Z          |   0.00   |  -6.00   |  -9.00   |   0.00   |   0.00   |   0.00   |  -3.00   |
----------------------------------------------------------------------------------------------------
****************************************************************************************************
----------------------------------------------------------------------------------------------------
|               Cj               |  -9.00   |  -12.00  |  -15.00  |   0.00   |   0.00   |   0.00   |
----------------------------------------------------------------------------------------------------
|    Cb    |    Xb    |    b     |    X1    |    X2    |    X3    |    X4    |    X5    |    X6    |
----------------------------------------------------------------------------------------------------
|   0.00   |    X4    |  -1.29   |  -0.64   |  -0.00   |   0.00   |   1.00   |  -0.64   |  -0.07   |
|  -12.00  |    X2    |   3.29   |   0.64   |   1.00   |   0.00   |   0.00   |  -0.36   |   0.07   |
|  -15.00  |    X3    |   2.14   |   0.07   |   0.00   |   1.00   |   0.00   |   0.07   |  -0.21   |
----------------------------------------------------------------------------------------------------
|          Z          |   0.00   |  -0.21   |   0.00   |   0.00   |   0.00   |  -3.21   |  -2.36   |
----------------------------------------------------------------------------------------------------
****************************************************************************************************
----------------------------------------------------------------------------------------------------
|               Cj               |  -9.00   |  -12.00  |  -15.00  |   0.00   |   0.00   |   0.00   |
----------------------------------------------------------------------------------------------------
|    Cb    |    Xb    |    b     |    X1    |    X2    |    X3    |    X4    |    X5    |    X6    |
----------------------------------------------------------------------------------------------------
|  -9.00   |    X1    |   2.00   |   1.00   |   0.00   |   0.00   |  -1.56   |   1.00   |   0.11   |
|  -12.00  |    X2    |   2.00   |   0.00   |   1.00   |   0.00   |   1.00   |  -1.00   |   0.00   |
|  -15.00  |    X3    |   2.00   |   0.00   |   0.00   |   1.00   |   0.11   |   0.00   |  -0.22   |
----------------------------------------------------------------------------------------------------
|          Z          |   0.00   |   0.00   |   0.00   |   0.00   |  -0.33   |  -3.00   |  -2.33   |
----------------------------------------------------------------------------------------------------
****************************************************************************************************

总结

对偶理论在线性规划中主要涉及原问题（称为"主问题"）和其对应的对偶问题。每个线性规划问题都有一个对应的对偶问题，通过解决对偶问题，可以获得关于原问题的重要信息。对偶问题的解提供了对原问题最优解的界限和性质的洞察。对偶定理表明，如果原问题有最优解，那么对偶问题也有最优解，并且两者的目标函数值相等。这种关系在经济解释、灵敏度分析和复杂问题分解等方面有广泛应用。
对偶单纯形法是一种用于解决线性规划问题的迭代算法，尤其适用于初始解不满足原问题的可行性条件但满足对偶问题的可行性条件的情况。该方法从对偶问题的可行解出发，通过逐步调整，使得原问题的约束条件逐渐满足，最终找到原问题的最优解。具体步骤包括选择入基变量和出基变量，以保持对偶问题的可行性，并通过对偶单纯形表调整基解。

参考文献

  1. python 实现对偶单纯形法
  2. python 实现对偶单纯形法
  3. 对偶理论

标签：matrix,单纯形法,Python,0.00,min,print,row,对偶
From： https://www.cnblogs.com/haohai9309/p/18225391

相关文章

  • 超详细Python教程——第一个python程序
    一、Python简介Python是著名的“龟叔”GuidovanRossum在1989年圣诞节期间，为了打发无聊的圣诞节而编写的一个编程语言。牛人就是牛人，为了打发无聊时间竟然写了一个这么牛皮的编程语言。现在，全世界差不多有600多种编程语言，但流行的编程语言也就那么20来种。不知道......
  • 【MISC】一道假的二维码题目学习zxing库[python解读二维码]
    引言这道题目的考点是文件格式、双图差值、Ook!编码、PRC等，我做这题的重点是复习巩固python读取二维码zxing库的使用。例题┌───────────────────────────────────────────────────┐│马老师的秘籍......
  • python 卡尔曼滤波算法
    卡尔曼滤波（KalmanFilter）是一种有效的递归滤波器，用于线性动态系统的状态估计。它通过考虑先前的估计和当前的观测来提供下一个状态的最佳估计。卡尔曼滤波器广泛应用于导航系统、机器人定位、信号处理等领域。下面是一个简单的Python实现卡尔曼滤波算法的例子，用于估计一个一维......
  • Python依据遥感影像的分幅筛选出对应的栅格文件
      本文介绍基于Python语言，结合已知研究区域中所覆盖的全部遥感影像的分幅条带号，从大量的遥感影像文件中筛选落在这一研究区域中的遥感影像文件的方法。  首先，先来明确一下本文所需实现的需求。现已知一个研究区域（四川省），且已知覆盖这一研究区域所需的全部遥感影像的分幅条带号......
  • 基于Python+OpenCV高速公路行驶车辆的速度检测系统
    欢迎大家点赞、收藏、关注、评论啦，由于篇幅有限，只展示了部分核心代码。文章目录一项目简介二、功能三、系统四.总结一项目简介  一、项目背景与意义随着交通流量的增加和高速公路的快速发展，高速公路上的车辆速度管理成为了保障道路安全和提升通行效率的重......
  • SockJS Python 客户端
    SockJS是一个用于浏览器和服务器之间建立全双工连接的库，它允许在不支持原生WebSocket的浏览器中提供类似WebSocket的API。Python中也有很多SockJS客户端库，例如`python-socketio`和`sockjs-client-py`。以下是如何使用Python客户端（在这个例子中，我们将使用`pytho......
  • 【多进程并发笔记】Python-Multiprocess
    目录调用函数后,函数内的变量如何释放?python2.7怎么使用多线程加速forloop多进程进程池,函数序列化错误的处理Time模块计算程序运行时间使用多进程,Start()后,如何获得返回值?使用多进程并行,每个进程都将结果写入sqlite3数据库,可以么python创建进程池进程池的最大进程数怎么确......
  • 【计算机毕业设计】谷物识别系统Python+人工智能深度学习+TensorFlow+卷积算法网络模
    谷物识别系统，本系统使用Python作为主要编程语言，通过TensorFlow搭建ResNet50卷积神经算法网络模型，通过对11种谷物图片数据集（'大米','小米','燕麦','玉米渣','红豆','绿豆','花生仁','荞麦','黄豆','黑米','黑豆'）进行训练......
  • 为什么 python 会出现这种行为？
    我试图在Python中将数字动态追加到2D数组中。temp=[]arr=[tempforiinrange(2)]Arr[0].append("erg;erg)arr[0].append("ergse")print(arr)我得到的输出结果是......
  • 基于python美食网站的设计与实现论文
    目录摘要IAbstractII第1章绪论11.1项目研究的背景11.2开发目的和意义11.3国内外研究现状1第2章系统开发工具32.1Python编程语言32.2B/S模式32.3MySQL数据库42.4Django框架介绍42.5Vue开发技术52.6JavaScript简介5第3章系统分析73.......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99