北航最优化方法课程设计参考资料.pdf

简介：
本资料为北京航空航天大学《最优化方法》课程设计专用参考书，涵盖多种最优化理论与算法，适用于相关专业学生及研究人员。 本段落主要讲述北航最优化方法大作业参考内容，通过一个包含七个节点和十三条弧的网络流问题，并利用Matlab编写对偶单纯形法程序来解决四个不同需求量下的最优化问题。 1. 问题重述 定义有向图G = (N, E)，其中N代表节点集合，E表示边集。A是与该网络相关的点-边关联矩阵，即一个大小为N×E的矩阵；第l列对应于弧(I,j)且仅在第i行有一个1，在第j行有一个-1，其余均为0。设bm = (bm1, …, bmN)^T和fm = (fm1, …, fmE)^T，则可以将等式约束表示为：Af = bm。 2. 7节点算例求解 本部分通过四个不同需求量的例子来应用Matlab编写对偶单纯形法程序，解决对应的最优化问题。 2.1 算例一（b1 = [4; -4; 0; 0; 0; 0; 0]^T） 目标函数为：最小化cTx1 约束条件为：Ax1 = b1, x1 >= 0 利用Matlab的对偶单纯形法程序，求得最优解x1* = [4, 0, ..., 0]T（其余元素均为零），对应的最优值为20。 2.2 算例二（b2 = [4; 0; -4; 0; 0; 0; 0]^T） 目标函数为：最小化cTx2 约束条件为：Ax2 = b2, x2 >= 0 利用Matlab的对偶单纯形法程序，求得最优解x2* = [0, 4, ..., 0]T（其余元素均为零），对应的最优值为20。 2.3 算例三（b3 = [0; -4; 4; 0; 0; 0; 0]^T） 目标函数为：最小化cTx3 约束条件为：Ax3 = b3, x3 >= 0 利用Matlab的对偶单纯形法程序，求得最优解x3* = [4, ..., 4]T（仅第1和第5元素非零），对应的最优值为40。 2.4 算例四（b4 = [4; 0; 0; 0; 0; 0; -4]^T） 目标函数为：最小化cTx4 约束条件为：Ax4 = b4, x4 >= 0 利用Matlab的对偶单纯形法程序，求得最优解x4* = [4, ..., 4]T（仅第1、5和10元素非零），对应的最优值为60。 3. 计算结果及说明 对于每个算例，我们通过分析需求节点与供给节点之间的最短路径来解释计算结果的合理性。每条弧的费用均设定为5单位，根据求解出的不同情况下的最优流量分配方案，可以得到相应的最小传输成本，并验证了对偶单纯形法程序的有效性。 综上所述，本段落通过对四个不同需求量的例子进行分析和解决最优化问题的过程展示了Matlab编程技巧的应用以及对偶单纯形算法的实用性。