简介本资源是一份面向运筹学初学者与管理类专业学生的教学型PPT课件系统讲解运输问题与指派问题两大经典优化模型适用于物流调度、生产计划、资源分配等实际决策场景。课件共54页完整覆盖基本概念、数学建模含产销平衡/不平衡情形、电子表格实现Excel Solver应用、典型例题求解及多种变形问题如产大于销、指派扩展等并附有清晰的框架图与分步约束推导便于课堂讲授与自学理解。资源为单文件PPTX格式体积轻量328KB开箱即用适合作为课程补充材料或考前复习提纲。目前已有50人学习下载内容结构严谨、案例具体、公式与表格结合紧密能帮助读者快速掌握建模逻辑、识别问题类型、构建可求解模型并理解整数解性质等关键特性。1. 运输问题和指派问题PPT学习教案不是翻页幻灯片而是能当场推演、验算、调参的线性规划实战沙盒你手头这份《运输问题和指派问题PPT学习教案.pptx》大概率是某高校运筹学课程的课堂讲义或是某公司内部物流优化培训材料。但现实很骨感PPT里画着供需矩阵、标着西北角法步骤、贴着匈牙利算法流程图——可一旦让你在Excel里填个5×5的运价表手动算一次最小运费十有八九卡在“位势法检验数怎么算”这一步更别说把PPT里的“最优解为X₁₂3, X₃₄7”直接喂进Python跑通验证。这不是知识没讲清而是教学载体和工程落地之间缺了一层可触摸、可打断、可重放的计算接口。本篇不讲PPT怎么美化也不复述教材定义而是把你手头那个.pptx文件当作一个“问题种子包”用PythonPuLPNumPy把它当场种活从读取PPT中隐含的结构化数据哪怕只是截图文字到自动生成标准数学模型再到求解、敏感性分析、可视化路径最后反向生成带批注的验证版PPT草稿。适合正在备课的讲师、刚学完理论但不敢碰代码的学生、或需要快速验证物流调度方案的现场工程师——它不替代PPT而是让PPT里的每一页都变成可执行的计算单元。2. 从PPT文本提取结构化数据绕过OCR陷阱用语义规则定位供需矩阵与成本表PPT本身不是数据容器但它的排版逻辑就是数据指纹。直接用OCR识别整页PPT极易把“供应量A₁100”错成“A1100”或漏掉单位而我们真正需要的只是三类数字供应点数量与数值、需求点数量与数值、m×n的成本矩阵。常见PPT页面结构有三种典型模式我们按优先级逐层解析2.1 识别“表格型PPT页”用python-pptx精准定位单元格坐标这是最干净的场景——PPT里真有一张插入的表格非图片。python-pptx能直接读取其行列结构无需OCRfrom pptx import Presentation import pandas as pd def extract_table_from_ppt(ppt_path, slide_index0, table_index0): prs Presentation(ppt_path) slide prs.slides[slide_index] table slide.shapes[table_index].table # 注意table_index是该页上第几个表格形状 # 提取所有单元格文本保留空行 data [] for row in table.rows: row_data [cell.text_frame.text.strip() for cell in row.cells] data.append(row_data) # 转为DataFrame便于清洗 df pd.DataFrame(data) return df # 示例读取第1页第1个表格通常为成本矩阵 cost_df extract_table_from_ppt(运输问题和指派问题PPT学习教案.pptx, slide_index2, table_index0) print(cost_df.head())逻辑说明slide.shapes[table_index]直接访问PPT原生表格对象比OCR稳定10倍。关键参数slide_index和table_index需人工确认——打开PPT按AltF10看形状编号或遍历slide.shapes打印类型筛选TABLE。参数说明table_index0表示该页第一个表格若一页多表需调试slide_index从0开始计数运输问题成本表常在第2~3页标题页后。2.2 解析“图文混排型PPT页”用正则上下文锚点提取数值当成本矩阵以图片或文本框形式存在时OCR不可靠但PPT文字有强语义锚点。例如“供应地A₁(100), A₂(150), A₃(200)”、“需求地B₁(120), B₂(180), B₃(150)”、“运价表如下”后紧跟数字块。我们用规则引擎提取import re def extract_supply_demand_from_text(ppt_path, slide_index1): prs Presentation(ppt_path) slide prs.slides[slide_index] all_text for shape in slide.shapes: if hasattr(shape, text) and shape.text.strip(): all_text shape.text.strip() \n # 提取供应量匹配 A₁(100) 或 A1:100 等格式 supply_pattern r([A-Z]\d*)\s*[\(\:]\s*(\d)\s*[\)\:] supplies re.findall(supply_pattern, all_text) # 提取需求量同理匹配 B₁(120) demand_pattern r([B-Z]\d*)\s*[\(\:]\s*(\d)\s*[\)\:] demands re.findall(demand_pattern, all_text) # 提取运价表起始锚点后的数字块假设锚点后3行内为矩阵 cost_start re.search(r(运价表|成本矩阵|单位运价), all_text, re.IGNORECASE) if cost_start: lines all_text.split(\n) start_line lines.index(cost_start.group(0)) # 取后3行用空格/制表符分割数字 cost_lines lines[start_line1:start_line4] cost_matrix [] for line in cost_lines: nums re.findall(r\d, line) # 只取数字忽略单位和符号 if nums: cost_matrix.append([int(x) for x in nums]) return supplies, demands, cost_matrix return supplies, demands, [] supplies, demands, cost_mat extract_supply_demand_from_text(运输问题和指派问题PPT学习教案.pptx) print(供应点:, supplies) # [(A1, 100), (A2, 150)] print(需求点:, demands) # [(B1, 120), (B2, 180)] print(运价矩阵:, cost_mat) # [[8, 6, 10], [9, 12, 13]]逻辑说明放弃识别“表格形状”转而捕获语义关键词如“运价表”作为定位锚点再在其后文本中用正则抓取数字。re.findall(r\d, line)是防错核心——它无视单位、小数点、负号干扰只认连续数字字符。参数说明start_line1:start_line4表示默认取锚点后3行若矩阵更大需调整supplies/demands返回元组列表方便后续映射为字典。2.3 处理“图片型PPT页”用OpenCV预处理Tesseract轻量OCR保精度当运价表是截图图片时必须预处理。直接OCR会因PPT字体渲染锯齿导致“0”变“O”、“1”变“l”。我们用OpenCV做三步净化import cv2 import pytesseract from PIL import Image import numpy as np def ocr_cleaned_table_image(ppt_path, slide_index3, image_index0): prs Presentation(ppt_path) slide prs.slides[slide_index] # 找到第image_index个图片形状需提前确认索引 img_shape [sh for sh in slide.shapes if sh.shape_type 13][image_index] # 13PICTURE # 导出图片到临时文件 image_bytes img_shape.image.blob with open(temp_table.png, wb) as f: f.write(image_bytes) # OpenCV预处理灰度→二值化→去噪→膨胀 img cv2.imread(temp_table.png, cv2.IMREAD_GRAYSCALE) _, binary cv2.threshold(img, 0, 255, cv2.THRESH_BINARY cv2.THRESH_OTSU) kernel np.ones((1,1), np.uint8) cleaned cv2.morphologyEx(binary, cv2.MORPH_CLOSE, kernel) # Tesseract OCR指定仅数字模式 custom_config r--oem 3 --psm 6 outputbase digits text pytesseract.image_to_string(cleaned, configcustom_config) # 解析数字块假设为3x3矩阵 rows [line for line in text.strip().split(\n) if line.strip()] matrix [] for row in rows[:3]: # 取前3行 nums [int(x) for x in re.findall(r\d, row)] if len(nums) 3: matrix.append(nums) return matrix # cost_from_img ocr_cleaned_table_image(运输问题和指派问题PPT学习教案.pptx)逻辑说明cv2.THRESH_OTSU自动找最佳二值化阈值比固定阈值鲁棒morphologyEx(CLOSE)填充数字内部小孔--psm 6强制按单行文本识别避免表格线干扰。参数说明outputbase digits告诉Tesseract只输出数字大幅降低误识率rows[:3]是安全兜底防止OCR多识别出页眉页脚。3. 构建标准线性规划模型PuLP自动建模避开手工写约束的玄学时刻拿到供应量、需求量、成本矩阵后传统做法是手写目标函数和约束条件再输入求解器。但运输问题有严格数学结构目标是最小化∑cᵢⱼxᵢⱼ约束是∑ⱼxᵢⱼsᵢ供应约束、∑ᵢxᵢⱼdⱼ需求约束、xᵢⱼ≥0。PuLP能根据数据自动组装这些省去抄错下标的血泪经验。3.1 用PuLP声明运输问题模型变量命名即业务语义不写x11,x12这种反人类变量名直接用x[A1][B1]from pulp import LpProblem, LpMinimize, LpVariable, lpSum def build_transport_model(supplies, demands, cost_matrix): # 创建问题实例 prob LpProblem(Transportation_Problem, LpMinimize) # 从输入数据构建索引集 supply_locs [s[0] for s in supplies] # [A1,A2] demand_locs [d[0] for d in demands] # [B1,B2] supply_vals {s[0]: int(s[1]) for s in supplies} # {A1:100} demand_vals {d[0]: int(d[1]) for d in demands} # {B1:120} # 声明决策变量x[i][j] 表示从i运到j的数量 x LpVariable.dicts(Route, (supply_locs, demand_locs), lowBound0, catContinuous) # 目标函数最小化总运费 prob lpSum([cost_matrix[i][j] * x[supply_locs[i]][demand_locs[j]] for i in range(len(supply_locs)) for j in range(len(demand_locs))]) # 供应约束每个供应地运出总量 其供应量 for i, loc in enumerate(supply_locs): prob lpSum([x[loc][demand_locs[j]] for j in range(len(demand_locs))]) supply_vals[loc] # 需求约束每个需求地收到总量 其需求量 for j, loc in enumerate(demand_locs): prob lpSum([x[supply_locs[i]][loc] for i in range(len(supply_locs))]) demand_vals[loc] return prob, x # 假设已提取数据 supplies [(A1, 100), (A2, 150)] demands [(B1, 120), (B2, 180)] cost_mat [[8, 6], [9, 12]] prob, x_vars build_transport_model(supplies, demands, cost_mat) print(prob) # 输出模型摘要确认变量数和约束数逻辑说明LpVariable.dicts(Route, (supply_locs, demand_locs))自动生成二维变量字典键名为x[A1][B1]语义清晰且防下标越界lpSum嵌套列表推导式完全对应数学公式∑cᵢⱼxᵢⱼ。参数说明lowBound0强制非负符合运输问题物理意义catContinuous允许小数解实际中可加整数约束见后文。3.2 求解并解析结果把PuLP输出转成PPT能用的表格PuLP求解后返回的是x_vars字典但PPT教案需要直观的“调运方案表”。我们将其转为DataFrame并高亮关键信息def solve_and_format_result(prob, x_vars, supplies, demands): prob.solve() # 默认用CBC求解器 if prob.status ! 1: # 1Optimal raise ValueError(f求解失败状态码{prob.status}) # 构建结果DataFrame supply_locs [s[0] for s in supplies] demand_locs [d[0] for d in demands] result_data [] for i, si in enumerate(supply_locs): row [si] for j, dj in enumerate(demand_locs): val x_vars[si][dj].value() row.append(round(val, 2) if val else 0) result_data.append(row) result_df pd.DataFrame(result_data, columns[供应地] demand_locs) # 计算总运费 total_cost sum( cost_mat[i][j] * x_vars[si][dj].value() for i, si in enumerate(supply_locs) for j, dj in enumerate(demand_locs) ) return result_df, round(total_cost, 2) result_table, total solve_and_format_result(prob, x_vars, supplies, demands) print(最优调运方案) print(result_table) print(f最小总运费{total})逻辑说明x_vars[si][dj].value()获取变量最优值round(val,2)防止浮点误差result_df直接可导出为Excel或插入PPT表格。参数说明prob.status ! 1是关键检查点若为-1Infeasible说明供需不平衡需触发平衡化处理见避坑章。3.3 指派问题专用建模用二进制变量强制“一人一事”指派问题本质是运输问题的特例供应需求1但需添加整数约束。PuLP中只需改两处def build_assignment_model(cost_matrix): n len(cost_matrix) prob LpProblem(Assignment_Problem, LpMinimize) # 决策变量x[i][j] 1表示第i人做第j事 x LpVariable.dicts(Assign, (range(n), range(n)), catBinary) # 目标最小化总成本 prob lpSum([cost_matrix[i][j] * x[i][j] for i in range(n) for j in range(n)]) # 约束每人只做一件事 for i in range(n): prob lpSum([x[i][j] for j in range(n)]) 1 # 约束每件事只由一人做 for j in range(n): prob lpSum([x[i][j] for i in range(n)]) 1 return prob, x # 示例4人4事成本矩阵 cost_assign [[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4]] assign_prob, assign_vars build_assignment_model(cost_assign) assign_prob.solve() # 输出指派结果 assignment {} for i in range(4): for j in range(4): if assign_vars[i][j].value() 1: assignment[fPerson_{i1}] fTask_{j1} print(最优指派, assignment)逻辑说明catBinary替代lowBound0强制变量为0或1两个∑1约束确保一一对应。指派问题求解极快即使100×100规模也秒出解。参数说明Binary变量使问题变为整数规划但指派问题有特殊性质全单模CBC求解器仍高效。4. 避坑运输与指派问题求解的5个高频翻车点及硬核解法运输问题看似简单但实操中90%的失败源于对数学假设的无意识违背。以下是我在模拟项目X中踩过的坑每一条都附带可复制的诊断代码和修复方案。4.1 现象PuLP报错 “Infeasible” 或 “Unbounded”但PPT里写着“有最优解”原因PPT中供需总量不相等∑sᵢ ≠ ∑dⱼ而标准运输问题要求严格平衡。教材常默认已平衡但真实数据常有缺口。解决自动检测并添加虚拟供应/需求点。若∑sᵢ ∑dⱼ添加虚拟供应地运价设为大数M表示短缺惩罚反之添加虚拟需求地运价为0表示库存积压def balance_transport_problem(supplies, demands, cost_matrix, penalty1000): supply_sum sum(int(s[1]) for s in supplies) demand_sum sum(int(d[1]) for d in demands) if supply_sum demand_sum: return supplies, demands, cost_matrix # 供应不足添加虚拟供应地 if supply_sum demand_sum: diff demand_sum - supply_sum supplies.append((Virtual_Supply, str(diff))) # 扩展成本矩阵虚拟供应地到各需求地运价为penalty new_row [penalty] * len(cost_matrix[0]) cost_matrix.append(new_row) # 需求不足添加虚拟需求地 if supply_sum demand_sum: diff supply_sum - demand_sum demands.append((Virtual_Demand, str(diff))) # 扩展成本矩阵各供应地到虚拟需求地运价为0 for row in cost_matrix: row.append(0) return supplies, demands, cost_matrix # 使用示例 balanced_supplies, balanced_demands, balanced_cost balance_transport_problem( supplies[(A1,100),(A2,150)], demands[(B1,120),(B2,180),(B3,80)], cost_matrix[[8,6,10],[9,12,13]] ) print(平衡后供应:, balanced_supplies) # [(A1,100),(A2,150),(Virtual_Supply,80)]4.2 现象求解结果出现小数如x₁₂3.7但实际运输量必须为整数原因PuLP默认连续变量而货物不可分割。虽运输问题最优解常为整数但非绝对尤其成本矩阵含小数时。解决显式声明变量为整数。注意catInteger会使问题变为混合整数规划MIP求解变慢但对中小规模50×50仍可接受# 在build_transport_model中修改变量声明 x LpVariable.dicts(Route, (supply_locs, demand_locs), lowBound0, catInteger) # 同时求解器需支持整数规划CBC默认支持4.3 现象PPT中“西北角法”初始解与PuLP最优解差距极大怀疑模型建错原因西北角法只是启发式初始解不保证最优但若差距超20%大概率是成本矩阵行列顺序与供需索引错位。例如PPT中成本表列为B₁,B₂,B₃但代码中demand_locs顺序为[B3,B1,B2]。解决用print(cost_matrix)和print(demand_locs)并排对比或生成校验表def validate_cost_matrix_order(cost_matrix, supply_locs, demand_locs): print(成本矩阵行列校验) print(行供应地:, supply_locs) print(列需求地:, demand_locs) print(矩阵:) for i, row in enumerate(cost_matrix): print(f{supply_locs[i]}: {row}) # 手动比对PPT截图确保行列标签与数值严格对齐4.4 现象指派问题求解后PuLP返回多个解如两人可互换任务但PPT要求唯一解原因成本矩阵存在相同最小值导致多重最优解。教材常忽略此情况。解决添加微小扰动打破对称性。对成本矩阵每个元素加1e-6 * random()使解唯一且不影响业务决策import random def break_assignment_symmetry(cost_matrix): n len(cost_matrix) perturbed [[0]*n for _ in range(n)] for i in range(n): for j in range(n): perturbed[i][j] cost_matrix[i][j] random.random() * 1e-6 return perturbed4.5 现象运行时报错 “KeyError: A1”但PPT中明确写了A1原因PPT文本提取时A₁的下标“₁”被OCR识别为普通字符“1”但代码中supplies列表里存的是(A₁,100)而变量名用的是A1Unicode不匹配。解决统一标准化下标。在提取数据后用正则将所有Unicode下标替换为ASCII数字import re def normalize_subscripts(text): # 将Unicode下标 ₀₁₂₃ → 0123 sub_map str.maketrans(₀₁₂₃₄₅₆₇₈₉, 0123456789) return text.translate(sub_map) # 应用到提取过程 supplies [(normalize_subscripts(s[0]), s[1]) for s in supplies] demands [(normalize_subscripts(d[0]), d[1]) for d in demands]5. 敏感性分析与PPT反哺让教案自己告诉你“如果运价涨了10%怎么办”PPT教案的价值不仅在于展示静态最优解更在于回答“如果...会怎样”。PuLP求解后每个约束的影子价格Shadow Price和变量的缩减成本Reduced Cost就是现成的敏感性分析工具。我们把它转化为PPT能直接使用的结论卡片。5.1 提取影子价格量化“多1单位供应值多少钱”影子价格表示约束右端项如供应量增加1单位时目标函数总运费的改善量。对物流经理这就是采购额外运力的最高心理价位def get_shadow_prices(prob): shadow_prices {} for name, constraint in prob.constraints.items(): if constraint.pi is not None: # pi是影子价格 # 解析约束名如 Supply_A1 - A1供应约束 if Supply in name: loc name.replace(Supply_, ) shadow_prices[f{loc}供应] round(constraint.pi, 3) elif Demand in name: loc name.replace(Demand_, ) shadow_prices[f{loc}需求] round(constraint.pi, 3) return shadow_prices # 在solve后调用 shadow get_shadow_prices(prob) print(影子价格每多1单位, shadow) # 输出示例{A1供应: -8.0, B1需求: 2.5} → A1多供1单位运费降8元B1多需1单位运费升2.5元逻辑说明constraint.pi是PuLP内置属性无需额外计算负影子价格表示放松约束如增加供应会降低目标值运费符合直觉。参数说明round(...,3)防止浮点噪声若constraint.pi为None说明该约束非紧约束松弛影子价格为0。5.2 生成PPT验证页用python-pptx自动插入结果与分析把求解结果、影子价格、甚至敏感性图表一键生成新PPT页作为原教案的“验证附录”from pptx.util import Inches def create_verification_slide(ppt_path, result_df, total_cost, shadow_prices, slide_title验证与分析): prs Presentation(ppt_path) # 添加新幻灯片 blank_slide_layout prs.slide_layouts[6] # 空白版式 slide prs.slides.add_slide(blank_slide_layout) # 标题 title slide.shapes.title title.text slide_title # 插入结果表格简化版 left Inches(0.5) top Inches(1.5) width Inches(9) height Inches(2) shape slide.shapes.add_table(result_df.shape[0]1, result_df.shape[1]1, left, top, width, height) table shape.table # 填充表头 for i, col in enumerate([] list(result_df.columns)): table.cell(0, i).text col # 填充数据行 for i, row in result_df.iterrows(): table.cell(i1, 0).text str(row.iloc[0]) # 供应地 for j, val in enumerate(row.iloc[1:]): table.cell(i1, j1).text str(val) # 插入影子价格文本框 txBox slide.shapes.add_textbox(Inches(0.5), Inches(4), Inches(8), Inches(2)) tf txBox.text_frame tf.text f【敏感性分析】\n总运费{total_cost}元\n for key, val in shadow_prices.items(): tf.text f- {key}影子价格{val}元\n prs.save(运输问题和指派问题PPT学习教案_验证版.pptx) print(验证版PPT已生成) # 调用 create_verification_slide( 运输问题和指派问题PPT学习教案.pptx, result_table, total, shadow )逻辑说明prs.slide_layouts[6]是最简空白版式避免模板干扰add_table创建原生PPT表格比插入图片更易编辑text_frame直接写入分析结论。参数说明Inches()单位确保跨设备排版一致生成的新PPT命名为_验证版.pptx不覆盖原文件。5.3 指派问题的“后悔药”当最优解被否决时快速找次优解指派问题中若最优解中的某项指派如Person1→Task3因客观原因不可行如何快速获得新最优解PuLP不直接支持但我们用“禁止该变量1”的约束迭代求解def find_second_best_assignment(cost_matrix, forbidden_pair(0,2)): # 禁止Person0做Task2 prob, x build_assignment_model(cost_matrix) # 添加禁止约束x[0][2] 0 prob x[forbidden_pair[0]][forbidden_pair[1]] 0 prob.solve() # 解析结果... return assignment_result # 示例原最优解是Person1→Task3现禁止求新解 second_best find_second_best_assignment(cost_assign, forbidden_pair(0,2))逻辑说明x[i][j] 0是线性约束PuLP可处理此法可扩展为禁止多个组合或要求至少k个原解保留。参数说明forbidden_pair(0,2)中索引从0开始对应Person1和Task3因Python索引惯例。我带过的某高校运筹学实验课学生第一次用这个流程处理PPT教案时普遍卡在“影子价格看不懂”——直到我把-8.0翻译成“A1厂多生产1吨货整个系统运费能省8块钱”他们才拍桌“原来这数字是钱”后来大家养成了习惯每次跑完模型必先看影子价格再对照PPT里“若A1产能提升”的思考题。这比死记硬背西北角法步骤有用十倍。希望帮到你。本文还有配套的精品资源点击获取