信息系统项目管理师-计算题专题(四)运筹学计算

ゝ一纸荒年。 2022-10-11 12:21 133阅读 0赞

# 运筹学 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70][]

注：

博客：  
[https://blog.csdn.net/badao\_liumang\_qizhi][https_blog.csdn.net_badao_liumang_qizhi]  
关注公众号  
霸道的程序猿  
获取编程相关电子书、教程推送与免费下载。

# 涉及知识点 #

可能涉及到如下知识点:

规划论:线性规划、非线性规划\}、整数规划、目标规划、动态规划  
  图论与网络  
  存储论  
  排队论  
  决策论  
  对策论  
  计算机仿真

运筹学中常考的有最短和最长路径问题、线性规划的问题、传输运输学解决资源分  
配、最小生成树、匈牙利法、最大流量、后悔值的问题

# 求最短和最长路径 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 1][]

## 解答 ##

求最长路径，就正向从前往后推，正向取最大值。

求最短路径，就正向从前往后推，正向取最小值。

比如正向从左到右，A到B1只有一条路。所以B1最短是5，C1有两条路，B1和B2，取B2+3最小为9。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 2][]

依次计算出来的最短为18

# 线性规划的问题 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 3][]

## 解答 ##

解法一：

设S为X件，K为Y件。

10X+20Y≤120

8X+8Y≤80

求12X+16Y最大

当上面两个相等时，X=8 Y等于2

解法二:

将下面的答案7、8、9、10依次代入上面的算式，符合条件求最大值。

# 投资收益最大化问题 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 4][]

## 解答 ##

首先理解第一行代表，投资1百万三个项目的收益，投资2百万三个项目的收益，投资3百万三个项目的收益，投资4百万三个项目的收益。

然后为了对比哪个项目在哪个层次(多少百万)合适，把投资其他百万情况下全部等比例改为1百万，然后同比例进行对比。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 5][]

然后对比下甲项目为1百万时最大，乙项目为百万时最大，丙项目在一百万时最大。

所以投资甲1百万，投资乙200万，投资丙1百万。

所以收益最大为4+9+5 = 18

# 对策论、博弈的问题 #

最大最大(max-max)准则

最大最大准则也称乐观准则，它找出每种行动的最好结果，再从最好结果中找一个更好的做为选择:  
u(Ai\*) = maxi maxj aij

最大最小(max-min)准则：

最大最小准则也称悲观准则,也叫小中取大， 它找出每种行动的最坏结果, 再从最坏结果中找一个最好的做为它的选择:  
u(Ai\*) = maxi minj aij

最小机会损失准则( min-max)  
也称最小最大后悔准则，它利用机会成本的概念来进行决策。决策首先要计算机会损失 (后悔值) 矩阵;  
机会损失的概念是，当一个事件发生时，由于你没有选择最优决策 而带来的收入损失。

最小最大后悔值法:  
也称萨凡奇决策准确性则，决策者不知道各种自然状态中任一种发生的概率，决策目标是确保避免较大的机会损失。  
运用最小最大后悔值法时，首先要将决策矩阵从利润矩阵转变为机会损失矩阵；  
然后确定每一可选方案的最大机会损失；  
再次，在这些方案的最大机会损失中，选出一个最小值，与该最小值对应的可选方案便是决策选择的方案.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 6][]

## 解答 ##

悲观准则先去每个的最小，再去最小中的最大。

最小依次是50、100、200

所以最大是200，应该选择保守投资。

## 最小最大后悔值 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 7][]

## 解答 ##

根据题意，较低价时为8，其他表中以后的数据为0.根据最佳决策收益的差值来看，为0时此时都为最大值。

所以销路较好时较高价比中等价多4，所以中等价的后悔值比较高价多4，就是4。

依次类推，销路一般时较高价为5，较低价为4

销路较差时较高价为4，中等价为2。

依据最小最大后悔值决策标准，先选最大的，再从最大的中选出最小的为4，即中等价。

# 流量问题 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 8][]

## 解答 ##

此种场景不是求关键路径。

流量受每条路的限制，应该每条路线中受最小的限制。

断路法一

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 9][]

断路法二

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 10][]

# 人员分配问题 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 11][]

## 解答 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 12][]

从第二个矩阵怎么判断，乙只有Ⅱ为0，所以乙只能为Ⅱ，同理丙只能为I，甲可以为Ⅰ和Ⅳ，但是因为丙只能为Ⅰ所以甲只能为Ⅳ，那么丁只能为Ⅲ

# 最小生成树的问题 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 13][]

## 解答 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 14][]

采用断路法，将最大的路断掉不走，在保证能通一条路的前提下。把7、8、9断掉，然后查看连接1的由两条，把5断掉留下3。

所以最短路径为有图所示。

# 换算方案问题 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 15][]

## 解答 ##

注意此题有坑，用21块旧电池，可以马上换取7块新电池。

等7块新电池用旧了，可以再换两块新电池，并剩余一块旧电池。

等这两块用旧了，再加上上面剩的一块旧电池，又可以再换一个电池。

所以一共能换10个。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70]: /images/20221005/1c0139c5bd2141cdb362cb09c3448cc5.png
[https_blog.csdn.net_badao_liumang_qizhi]: https://blog.csdn.net/badao_liumang_qizhi
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 1]: /images/20221005/805b75d30c9c4650913ad31e2576b824.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 2]: /images/20221005/f498712c8e184657b7b455d0cd86a49f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 3]: /images/20221005/fce466076e0648d19d4c59fbda87f763.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 4]: /images/20221005/7ef20bc7103942cfa0dcc9eee7d7639b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 5]: /images/20221005/c6fb7f03c400423c929614522a63bb78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 6]: /images/20221005/2a2637501efc4a93ba33258cae6235d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 7]: /images/20221005/f317128411364f4ea4bc1211d9548c10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 8]: /images/20221005/a404f5a8ebe944298f52145e2d498d4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 9]: /images/20221005/3248348059d3411eb8d6dc6071a042c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 10]: /images/20221005/45d8333445134d21817a592d983b8138.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 11]: /images/20221005/719f848162ce4bb7a90b112079f73b2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 12]: /images/20221005/dd3a4d91a0f448bdb7e5696f77772bc7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 13]: /images/20221005/b1b94dd4f3024dcc8097bcdc0b358a0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 14]: /images/20221005/7c740d5a547542a78162425cc2353a8c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JBREFPX0xJVU1BTkdfUUlaSEk_size_16_color_FFFFFF_t_70 15]: /images/20221005/8c08c81714044393929726c396314fc0.png