下载文档原格式
基于Matlab的动态规划问题
基于Matlab的动态规划问题
郑怡;赵海良;徐永
【期刊名称】《重庆理⼯⼤学学报（⾃然科学版）》
【年(卷),期】2008(022)005
【摘要】介绍了动态规划的基本理论,包括动态规划的基本概念和基本思路,并利⽤Matlab对动态规划中的资源分配问题进⾏了分析,然后⽤Matlab语⾔进⾏了程序设计和计算,使复杂问题简单化,避免了繁琐的计算,从⽽使问题能更⽅便地得到解决.
【总页数】4页(152-155)
【关键词】动态规划;资源分配问题;Matlab语⾔
【作者】郑怡;赵海良;徐永
【作者单位】西南交通⼤学数学系,成都,610031;西南交通⼤学数学系,成都,610031;西南交通⼤学数学系,成都,610031
【正⽂语种】中⽂
【中图分类】O153
【相关⽂献】
1.基于MATLAB的⽔资源优化分配问题动态规划解法 [J], 李旭东
2.基于MATLAB的⽔资源配置动态规划研究 [J], 王超
3.基于MATLAB的动态规划逆序算法的实现 [J], 孙晓君
4.基于MATLAB的动态规划在热连轧板形板厚协调控制中的应⽤[J], 孙宝; 张⼩平
5.基于Matlab的动态规划顺序算法的实现 [J], 黄勇; 曲长⽂; 苏峰; 周鲁苹。
基于Matlab的动态规划算法的实现及应用动态规划（Dynamic Programming）是一种用来求解多阶段最优化问题的方法，在许多领域中都得到了广泛的应用。
本文将介绍如何使用Matlab实现动态规划算法，并通过一个具体的应用案例来说明其使用方法和效果。
动态规划算法的基本思想是将一个问题分解成多个阶段，每个阶段的最优解可以通过前一阶段的最优解来计算得到。
具体实现时，需要定义一个状态转移方程来描述问题的阶段之间的关系，以及一个递推公式来计算每个阶段的最优解。
在Matlab中，可以使用矩阵来表示问题的状态和状态转移方程，使用循环结构来进行递推计算。
下面以求解最长递增子序列（Longest Increasing Subsequence）为例来说明动态规划算法在Matlab中的实现和应用。
最长递增子序列是一个经典的动态规划问题，给定一个序列，找出一个最长的子序列，使得子序列中的元素是递增的。
可以使用动态规划算法来求解该问题。
定义一个状态数组dp，其中dp(i)表示以第i个元素结尾的最长递增子序列的长度。
初始化dp数组为1，表示每个元素自身就是一个递增子序列。
然后，使用一个循环结构遍历序列的每个元素，计算以当前元素结尾的最长递增子序列的长度。
具体实现时，需要比较当前元素与之前的元素的关系，如果当前元素大于之前的元素，则可以将当前元素加入到之前的最长递增子序列中，并更新dp(i)为dp(j)+1，其中j为小于i的所有元素的位置。
遍历dp数组，找出其中的最大值，即为整个序列的最长递增子序列的长度。
下面是Matlab代码的实现：```matlabfunction LIS = LongestIncreasingSubsequence(nums)N = length(nums);dp = ones(1, N);for i = 1:Nfor j = 1:i-1if nums(i) > nums(j)dp(i) = max(dp(i), dp(j)+1);endendendLIS = max(dp);end```以上代码定义了一个函数LongestIncreasingSubsequence，输入参数为一个序列nums，输出结果为最长递增子序列的长度LIS。
基于Matlab的动态规划算法的实现及应用动态规划是一种解决多阶段决策过程的优化技术。
它的主要思想是将问题分成几个阶段，在每个阶段用一个状态来描述问题，然后找到在每个阶段中符合条件的最优状态值，以便决定在一个阶段结束的时候采取什么决策。
在Matlab中，可以非常方便地实现动态规划算法。
这里简要介绍一下基于Matlab的动态规划算法的实现及应用。
首先，我们需要定义状态转移方程。
状态转移方程是动态规划算法的核心，决定了如何从一个状态转移到另一个状态。
例如，我们要用动态规划算法求解一个背包问题，物品的重量为w1，w2，w3，w4，w5，物品的价值为v1，v2，v3，v4，v5，背包的容量为W。
那么状态转移方程可以定义如下：dp(i,j) = max(dp(i-1,j), dp(i-1,j-w(i))+v(i))其中dp(i,j)表示前i个物品放入容量为j的背包中所能得到的最大价值。
i表示物品的数量，j表示背包的容量。
w(i)表示第i个物品的重量，v(i)表示第i个物品的价值。
上式中的max表示在当前状态下，应该选择哪个状态值。
然后我们需要初始化第一个状态dp(1,j)，当只考虑第1个物品时，dp(1, j)的值与w(1)和v(1)有关。
当物品数量为0时，dp(i, j)的值为0。
接下来，我们可以使用循环以及状态转移方程来计算出dp(i,j)的值，最终得到最优的解。
在Matlab中，可以利用循环完成状态转移方程的计算，例如：dp(1,:) = (w(1) <= j).*v(1);在上述代码中，利用循环计算每个状态的最大价值。
第一行是初始化第一个状态，即当只有一个物品的时候，dp(1, j)的值为v(1)或0。
第二行是循环计算后续状态的最大价值，根据状态转移方程进行计算。
在实际应用中，动态规划算法可以用于诸如最优路径规划、时间序列分析、机器学习等领域。
例如，在机器学习中，动态规划算法可以用于序列模型的预测和分类问题。
动态规划之装配线调度问题⼀、问题描述装配线调度问题如下：Colonel汽车公司在有两条装配线的⼯⼚内⽣产汽车，⼀个汽车底盘在进⼊每⼀条装配线后，在每个装配站会在汽车底盘上安装不同的部件，最后完成的汽车从装配线的末端离开。
如下图1所⽰。
每⼀条装配线上有n个装配站，编号为j=1,2,...,n，将装配线i（i为1或2）的第j个装配站表⽰为S(i,j)。
装配线1的第j个站S(1,j)和装配线2的第j个站S(2,j)执⾏相同的功能。
然⽽这些装配站是在不同的时间建造的，并且采⽤了不同的技术，因此，每个站上完成装配所需要的时间也不相同，即使是在两条装配线上相同位置的装配站也是这样。
把每个装配站上所需要的装配时间记为a(i,j)，并且，底盘进⼊装配线i需要的时间为e(i)，离开装配线i需要的时间是x(i)。
正常情况下，底盘从⼀条装配线的上⼀个站移到下⼀个站所花费的时间可以忽略，但是偶尔也会将未完成的底盘从⼀条装配线的⼀个站移到另⼀条装配线的下⼀站，⽐如遇到紧急订单的时候。
假设将已经通过装配站S(i,j)的底盘从装配线i移⾛到另⼀条装配线所花费的时间为t(i,j)，现在的问题是要确定在装配线1内选择哪些站以及在装配线2内选择哪些站，以使汽车通过⼯⼚的总时间最⼩。
⼆：问题分析step1：通过⼯⼚最快路线的结构。
考虑底盘从起始点到装配站S1,j的最快可能路线。
如果j=1，则底盘只有⼀个路线，对于J=2，3 。
则有两种情况。
这个底盘可能从装配站S1,j-1直接到S1,j;也可能来⾃装配站S2,j-1；然后移动到装配站S1,j移动的代价为t2,j-1;通过装配站S1,j的最快路线⼀定通过了装配站S1,j-1:这是这个问题的最优⼦结构。
step2.⼀个递归的解在dp中，第⼆个步骤是利⽤⼦问题的最优解来递归定义⼀个最优解的值。
我们选择在两条装配线上通过装配站j的最快路线的问题来作为⼦问题。
j=1,2 .. .n ;令f i [j]表⽰⼀个底盘从起点到装配站Si，j的最快可能时间.最终⽬标是确定底盘通过⼯⼚所有路线的最快可能时间。
基于Matlab的动态规划算法的实现及应用动态规划是一种常用的优化算法，可以在给定的约束条件下，求解具有最优解的问题。
它通过将原问题拆分成若干子问题，并保存子问题的解，从而避免重复计算，减少运算量，提高算法的效率。
在Matlab中，可以通过使用递归或迭代的方式来实现动态规划算法。
下面将介绍一种基于Matlab的动态规划算法的实现及应用。
我们需要确定问题的状态，即在求解过程中需要保存的信息。
然后，定义状态转移方程，即问题的解与其子问题的解之间的关系。
确定边界条件，即问题的基本解。
以求解斐波那契数列为例，斐波那契数列的定义如下：F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2) (n>=2)我们可以使用动态规划算法来求解斐波那契数列。
定义一个数组dp，用来保存每个子问题的解。
然后，通过迭代的方式，计算从小到大的每个子问题的解，直到得到问题的最优解。
在Matlab中，可以使用以下代码实现动态规划算法求解斐波那契数列：```matlabfunction [result] = Fibonacci(n)% 初始化数组dpdp = zeros(1, n+1);% 定义边界条件dp(1) = 0;dp(2) = 1;% 迭代计算每个子问题的解for i = 3:n+1dp(i) = dp(i-1) + dp(i-2);end% 返回问题的最优解result = dp(n+1);end```运行以上代码，输入一个整数n，即可求解斐波那契数列的第n项。
除了求解斐波那契数列，动态规划算法还可以应用于其他许多领域，如路径规划、背包问题等。
在路径规划中，我们可以使用动态规划算法来求解最短路径或最优路径；在背包问题中，我们可以使用动态规划算法来求解能够装入背包的最大价值。
动态规划算法是一种强大的优化算法，在Matlab中的实现也相对简单。
通过定义问题的状态、状态转移方程和边界条件，我们可以使用动态规划算法来求解各种不同类型的问题。
基于Matlab的动态规划算法的实现及应用动态规划算法是解决许多计算问题的有效方法，它可以用于组合优化、资源分配和时间序列分析等方面。
Matlab是一种高级计算软件，提供了许多内置函数，使得动态规划算法的实现变得简单。
一、动态规划算法的基本思想动态规划算法是一种优化技术，可以用于解决一些复杂的计算问题。
它的基本思想是把一个大问题分解成一系列子问题，通过解决子问题得到整体的最优解。
在动态规划算法中，通常使用递推式来描述问题的最优解。
在Matlab中，动态规划算法的实现通常包括以下几个步骤：1.定义状态变量：根据问题的特性，定义一组状态变量，用于描述问题的状态。
2.制定状态转移方程：根据问题的条件和规则，制定一组状态转移方程，用于计算问题的最优解。
3.构建转移矩阵：将状态转移方程转化为矩阵形式，便于计算和优化。
4.初始化状态变量：将初始状态赋值给状态变量，用于递推计算。
5.递推计算：根据状态转移矩阵和当前状态，计算下一时刻状态的值，直到达到目标状态。
6.输出最优解：输出最终状态对应的最优解。
三、应用实例1.背包问题背包问题是一种组合优化问题，目标是在给定的一组限制条件下，尽可能地装满容量限制的背包。
动态规划算法可以有效解决背包问题。
function [optx,optf]=knapsack(w,v,c)%w：物品的重量； v：物品的价值； c：背包容量%optx：最优解； optf：最优解对应的函数值n=length(w); %物品数量f=zeros(n+1,c+1); %状态变量fx=zeros(1,n); %物品的选择变量xfor i=1:nfor j=1:cif j<w(i) %背包容量不足的情况f(i+1,j)=f(i,j);else %背包容量足够的情况f(i+1,j)=max(f(i,j),f(i,j-w(i))+v(i));endendendoptf=f(n+1,c); %最优解j=c; %从后往前寻找物品for i=n:-1:1if f(i+1,j)>f(i,j)x(i)=1;j=j-w(i);endendoptx=x; %最优解2.最长公共子序列问题最长公共子序列问题是一种字符串匹配问题，目标是在两个字符串中找到最长的公共连续子序列。
基于Matlab的动态规划算法的实现及应用动态规划算法是一种解决多阶段决策问题的优化方法，它可以在每个阶段选择最优决策，并且在各个阶段间保持最优子结构，从而达到整体最优的目的。
在实际应用中，动态规划算法被广泛用于求解优化问题、路径规划、资源分配等方面。
本文将介绍基于Matlab 的动态规划算法的实现及应用，并深入探讨其在实际问题中的应用。
一、动态规划算法的基本原理动态规划算法的基本原理是通过将问题分解为子问题，并计算每个子问题的最优解，然后存储下来以供后续使用。
最终得到整体最优解。
动态规划算法通常包括以下几个步骤：1. 确定状态和状态转移方程：首先需要确定问题的状态，然后建立状态之间的转移关系，也就是状态转移方程。
状态转移方程描述了问题的子问题之间的关系，是动态规划算法的核心。
2. 初始化：初始化动态规划数组，将初始状态下的值填入数组中。
3. 状态转移：利用状态转移方程计算出各个阶段的最优解，并将其存储在动态规划数组中。
4. 求解最优解：根据动态规划数组中存储的各个阶段的最优解，可以得到整体最优解。
Matlab是一种强大的计算软件，具有丰富的数值计算函数和可视化工具，非常适合实现动态规划算法。
下面以一个简单的背包问题为例，介绍如何在Matlab中实现动态规划算法。
假设有n件物品，每件物品的重量为w[i]，价值为v[i]。
现在有一个容量为C的背包，问如何选择物品放入背包，使得背包中物品的总价值最大。
我们需要确定问题的状态和状态转移方程。
在这个问题中，我们可以定义状态dp[i][j]表示在前i件物品中选择若干个放入容量为j的背包中所能获得的最大价值。
状态转移方程可以表示为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])然后，我们可以利用Matlab实现这个动态规划算法，代码如下：```matlabfunction max_value = knapsack(w, v, C)n = length(w);dp = zeros(n+1, C+1);for i = 1:nfor j = 1:Cif j >= w(i)dp(i+1,j+1) = max(dp(i,j+1), dp(i,j-w(i)+1)+v(i));elsedp(i+1,j+1) = dp(i,j+1);endendendmax_value = dp(n+1,C+1);end```三、动态规划算法在实际问题中的应用动态规划算法在实际问题中有着广泛的应用，下面以路径规划问题为例，介绍动态规划算法的应用。
论文题目：基于Matlab算法用Java Web 设计实现求解动态规划问题作者姓名：王永田工作单位：江苏学历网完成日期：2015年3月10日目录绪论 (1)1. Java Web网站应用Matlab流程 (1)1.1 Web应用MCR(Matlab Compiler Runtime)过程说明 (1)1.2 JA V A—H0ME路径 (2)1.3 CLASSPATH路径 (2)1.4 Path路径 (3)1.5 网站开发环境搭建及代码主要过程 (3)1.6 网站定时任务 (3)1.7 各种问题的解决方案 (4)1.8 MCR环境变量无法找到的解决方案注意事项 (4)2. 相关技术介绍 (4)2.1 Matlab (4)2.2 Logistic模型 (4)3.动态规划案例分析与Matlab求解 (5)3.1 动态规划逆序算法的MATLAB程序Dynprog.m (5)3.2 求最短的物资运输路线案例分析与Matlab求解 (7)结束语 (10)参考文献 (11)[摘要] 为了应用专业数据软件Matlab，提高供电企业网站对用户信用分析的处理能力，在应用MatLab提供的MCR，实现Web网站对数据分析处理的功能同时，通过源码分析和进程跟踪对MCR与Java的结合与应用的过程进行仔细的对比分析。
在不同的部署环境中，设置好应用MCR所需的相同环境变量后，对Web网站运行情况的结果进行对比，整理出各种由于MCR 本身与Java版本造成的冲突，导致Java网站无法正常应用MCR处理数据的解决方案。
该方案为相关业务领域开发提供了有效的技术支持，创造了很好的社会效益和经济效益。
[关键词] Web应用；MatLab；Java；MCRAbstract:In order to use the professional data software Matlab to improve the power supply enterprise website s analysis ability of the power customer credit，Matlab Compiler Runtime(MCR)provided by MatLab is adopted to realize the data analy—sis processing function of Website．A careful comparative analysis on joint application process of MCR and Java was performed through the source code analysis and process tracking．In various deployment environment，after seting up the same environment variables required fm M CR application，the results of the W ebsite running condition Were compared．The various conflicts coursed by combination of Java with MCR wele tbund，which make the Java website not to be normally applied in data processing．The scheme provided effective technical support fm the relevant business development and created good social and economic benefits．.Key words：Web application；Matlab；Java；Matlab compiler runtime绪论随利用MatLab(MATrix LABoratory)专业软件对数据处理的能力，可以充分利用各种数学理论，提高Web网站的数据挖掘、分析、处理能力。
基于Matlab的动态规划算法的实现及应用动态规划算法是一种解决多阶段决策过程的优化问题的方法，它可以用于求解最优化问题、路径规划、序列匹配等多种应用场景。
在计算机科学领域，动态规划算法被广泛应用于图像处理、机器学习、自然语言处理等诸多领域中。
本文介绍了基于Matlab的动态规划算法的实现及其应用。
一、动态规划算法概述动态规划算法是一种通过将原问题分解成子问题来求解最终问题的优化方法。
它的核心思想是利用子问题的最优解来推导出原问题的最优解。
动态规划算法通常用于解决有重叠子问题和最优子结构性质的问题，这些问题的解可以通过递归地求解子问题而得到。
动态规划算法的一般步骤如下：1. 定义子问题：将原问题分解成若干子问题，确定子问题的状态和状态转移方程。
2. 利用子问题的最优解来递推原问题的最优解，并存储中间结果。
动态规划算法具有较强的通用性和灵活性，可以适用于多种不同类型的问题，如背包问题、最短路径问题、序列匹配问题等。
尤其在处理具有多阶段决策过程的问题时，动态规划算法能够有效地求解最优解。
二、Matlab中的动态规划算法实现Matlab是一种功能强大的科学计算软件，它提供了丰富的数值计算和数据可视化功能，也支持通过编程语言实现各种算法。
在Matlab中，可以通过编写脚本或函数来实现动态规划算法。
下面以一个经典的动态规划问题——斐波那契数列为例，介绍如何在Matlab中实现动态规划算法。
斐波那契数列是一个经典的递归算法问题，其定义如下：F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2)，其中n>1我们可以用递归的方式来求解斐波那契数列：```matlabfunction result = fibonacci(n)if n == 0result = 0;elseif n == 1result = 1;elseresult = fibonacci(n-1) + fibonacci(n-2);endend```递归方法存在重复计算的问题，效率较低。
一、用MATLAB 求解线性规划问题（1）编写的M 文件为：f=[-1;-1]A=[1 -2;1 2]b=[4,8][x,feval]=linprog(f,A,b,[],[],zeros(2,1))所求解为：x 1=6,x 2=1;min f=-7（2） 编写的M 文件为：f=[-4;-3]A=[3 4;3 3;4 2]b=[12;10;8][x,feval]=linprog(f,A,b,[],[],zeros(1,2))所求得的解为：x 1=0.8,x 2=2.4;max f=10.4（3）（4） 编写的M 文件为：f=[-1;-3;3]Aeq=[1 1 2;-1 2 1]beq=[4;4][x,feval]=linprog(f,[],[],Aeq,beq,zeros(3,1))所求得的结果为：x 1=4/3,x 2=8/3,x 3=0;max f=28/3。
12121212min 24s.t.28,0f x x x x x x x x ì=--ïïïï-?镲íï+?ïïï³ïî121212121243max 3412..3310428,0f x x xx s t x x x x x x ì=+ïïïï+?ïïï+?íïïï+?ïïï³ïî12312312313min 3s.t.211423210(1,2,3)j f x x x x x xx xx x x x j =--ìïïïï-+?ïïïï-++?íïï-+=ïïïïï?ïî123123123max 3s.t.24240(1,2,3)j f x x x xx x x x x x j =+-ìïïïï++=ïïí-++=ïïïïï?ïî（5）（选做）先做如下转化：% x=u1-v1,,y=u2-v2,,z=u3-v3% min f=u1+u2+u3+v1+v2+v3% s.t. u1+u2-v1-v2<=1% 2*u1+u3-2*v1-v3=3则编写的M 文件为：f=[1;1;1;1;1;1]A=[1 1 0 -1 -1 0]b=1Aeq=[2 0 1 -2 0 -1]beq=3[x,feval]=linprog(f,A,b,Aeq,beq,zeros(6,1))所求得的结果为：u 1=1.0936,u 2=0,u 3=0.8192,v 1=0,v 2=0.9302,v 3=0Min f =2。
实验四 用MATLAB 求解线性规划问题一、实验目的：了解Matlab 的优化工具箱，能利用Matlab 求解线性规划问题。
二、实验内容：线性规划的数学模型有各种不同的形式，其一般形式可以写为：目标函数： n n x f x f x f z +++=Λ2211m in约束条件： s n sn s s n n b x a x a x a b x a x a x a ≤+++≤+++ΛΛΛΛΛ221111212111 s n tn t t n n d x c x c x c d x c x c x c =+++=+++ΛΛΛΛΛ2211112121110,,,21≥n x x x Λ 这里n n x f x f x f z +++=Λ2211称为目标函数，j f 称为价值系数，T n f f f f ),,,(21Λ=称为价值向量，j x 为求解的变量，由系数ij a 组成的矩阵⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=mn m n a a a a A ΛΛOΛΛ1111称为不等式约束矩阵，由系数ij c 组成的矩阵 ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=sn s n c c c c C ΛΛOΛΛ1111称为等式约束矩阵，列向量Tn b b b b ),,,(21Λ=和T n d d d d ),,,(21Λ=为右端向量，条件0≥j x 称为非负约束。
一个向量Tn x x x x ),,,(21Λ=，满足约束条件，称为可行解或可行点，所有可行点的集合称为可行区域，达到目标函数值最大的可行解称为该线性规划的最优解，相应的目标函数值称为最优目标函数值，简称最优值。
我们这里介绍利用Matlab 来求解线性规划问题的求解。
在Matlab 中有一个专门的函数linprog()来解决这类问题，我们知道，极值有最大和最小两种，但求z 的极大就是求z -的极小，因此在Matlab 中以求极小为标准形式，函数linprog()的具体格式如下： X=linprog(f,A,b)[X,fval,exitflag,ouyput,lamnda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options)这里X 是问题的解向量，f 是由目标函数的系数构成的向量，A 是一个矩阵，b 是一个向量，A ，b 和变量x={x1,x2,…,xn}一起，表示了线性规划中不等式约束条件，A ，b 是系数矩阵和右端向量。
Matlab中的动态规划方法与示例分析引言动态规划是一种解决多阶段决策问题的优化方法，它通过将问题分解为若干阶段，在每个阶段中做出最优决策，从而得到整体最优解。
Matlab作为一种强大的计算工具，提供了丰富的函数和工具箱来支持动态规划的求解。
本文将通过介绍动态规划的基本原理和算法，结合几个实际示例，展示在Matlab中如何应用动态规划方法解决实际问题。
一、动态规划的基本原理动态规划的基本原理是通过自底向上的递推关系，将一个大问题分解为若干个子问题，并将每个子问题的最优解存储起来，以便在解决更大的问题时进行查找和利用。
具体地，动态规划有三个关键要素：最优子结构、边界条件和状态转移方程。
最优子结构是指一个问题的最优解可以由其子问题的最优解组成。
它是动态规划的关键特点，也是将问题分解为子问题并递归求解的基础。
边界条件是指问题的边界情况和初始状态，可以是递归求解的终止条件。
状态转移方程是指描述子问题之间关系的方程，它将子问题的最优解与大问题的最优解联系起来。
在求解过程中，通过将问题划分为子问题并依次求解，最终得到整体最优解。
二、动态规划的算法实现在Matlab中，可以通过定义递归函数或使用循环结构来实现动态规划算法。
递归函数的实现方式简单直观，但由于递归调用的开销较大，可能导致算法的效率较低。
循环结构的实现方式相对复杂，但可以通过数组或矩阵来存储子问题的最优解，以减少重复计算，提高算法的效率。
在实际应用中，动态规划可以通过以下步骤来实现：1. 确定问题的最优子结构、边界条件和状态转移方程。
2. 定义数组或矩阵来存储子问题的最优解。
3. 利用循环结构或递归函数，按照自底向上的顺序计算和存储子问题的最优解。
4. 根据存储的子问题最优解，计算并返回大问题的最优解。
三、动态规划实例分析1. 背包问题背包问题是动态规划中经典的例子，它的目标是在限制总重量的情况下，选择一些物品放入背包，使得背包中物品的总价值最大化。
课程设计题目1：
某一汽车公司在有两条装配线的工厂内生产汽车，如下图所示，一个汽车底盘在进入每一条装配线后，在一些装配站中会在底盘上安装部件，然后，完成的汽车在装配线的末端离开。
每一条装配线上有n 个装配站（n=6），编号为1,2,3,,j n =⋅⋅⋅。
将装配线i （i 为1或2）的第j 个装配站表示为ij S 。
装配线1的第j 个站（1j S ）和装配线2的第j 个站（2j S ）执行相同的功能。
然而，这些装配站是在不同的时间采用不同的技术建造的，因此，每个站上所需的时间（用○中的数字表示）是不同的，即使是在两条不同装配线相同位置的装配站上也是这样。
将在装配站ij S 上所需的装配时间记为ij a 。
一个汽车底盘进入其中一条装配线，然后从每一站进行到下一站。
底盘进入装配线i 的进入时间为i e ，装配完成的汽车离开装配线
i 的离开时间为i x 。
在正常情况下，一个底盘进入一条装配线后，它只会经过该条装配线。
在相同的装配线中，从一个装配站到下一个装配站所花的时间可以忽略。
偶尔会来一个特别急的订单，客户要求尽可能快地制造这辆汽车。
对这样一个加急的订单，底盘仍然依序经过n 个装配站，
但是工厂可以将部分完成的汽车在任何装配站上从一条装配线移到另一条装配线上。
把已经通过装配站ij S 的一个底盘从装配线i 移走所花的时间为ij t ，其中1,2i =，而1,2,3,,1j n =⋅⋅⋅-。
问题是要确定在装配线1内选择哪些站以及在装配线2内选择哪些站，
以使汽车在工厂的装配总时间最小。
要求用动态规划方法设计算法求解该问题：1）写出动态规划的递归公式（包括记录最优解的记录方法，要求是逆序的，即Backward 方式的）；2）写出算法的具体步骤；3）对图中所示的实例进行求解。
解：首先写出该问题的动态规划算法的逆向递归公式：
设(,)f i j 算法表示汽车底盘在第i 条生产线的第j 个装配站完成装配工作后完成剩余装配工作所需要的最小装配时间，(,)l i j 表示汽车底盘在第i 条生产线的第j 个装配站完成装配工作后在以后的最优调度计划中的第1j +个装配工作所在的装配线，其中1,2i =，1,2,,6j =。
则有如下逆向递归公式：
12(1,)(2,)f n x f n x ==
底盘进入
装配站S 1,1
装配站S 1,2 装配站S 1,3 装配站S 1,4 装配站S 1,5 装配站S 1,6 装配站S 2,1 装配站S 2,2 装配站S 2,4 装配站S 2,5 装配站S 2,6 装配站
S 2,3
1,112,11,112,221,12,12,1,1(1,)min{(1,1),(2,1)}1(1,)(1,1)(1,)2(1,)(2,1)
(2,)min{(1,1),(2,1)}1
(2,)(1,1)
(2,)2(j j j j j j j j j j j f j a f j t a f j if
f j a f j l j if f j t a f j f j t a f j a f j if f j t a f j l j if f +++++++=+++++=++⎧=⎨
=+++⎩=+++++=+++=2,12,)(2,1)
j j a f j +⎧⎨
=++⎩ 其中1,2,
,1j n =-
*,11,2
*,11,2
min{(,1)}arg min{(,1)}i i i i i i f e a f i l e a f i ===++=++
课程设计题目2
1）在不同图形窗口画出y=sin(x), y=cos(x), y=sin(x 2), y=sin 2(x)的曲线，其中 ：-3π≤x ≤3π 2）在同一图形窗口一个坐标系画出y=sin(x), y=cos(x), y=sin(x 2), y=sin 2(x)的曲线，其中 ： -3π≤x ≤3π 2）在同一图形窗口的不同坐标系中画出y=sin(x), y=cos(x), y=sin(x 2), y=sin 2(x)的曲线，其中 ： -3π≤x ≤3π。
