运筹学—例题求解

这篇具有很好参考价值的文章主要介绍了运筹学—例题求解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

运筹学线性规划例题及答案,最小二乘法,动态规划

作答如下:

运筹学线性规划例题及答案,最小二乘法,动态规划

 文章来源地址https://www.toymoban.com/news/detail-757112.html

运筹学线性规划例题及答案,最小二乘法,动态规划

 

运筹学线性规划例题及答案,最小二乘法,动态规划

 图解法验证:

运筹学线性规划例题及答案,最小二乘法,动态规划


 由图可得在点x1=20,x2=24取到最大值Z=4080;

运筹学线性规划例题及答案,最小二乘法,动态规划

作答如下:

解:

(1)设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表

 

B1

B2

B3

产量

A1

x11

x12

x13

200

A2

x21

x22

x23

230

销量

100

150

180

430

 模型如下:

运筹学线性规划例题及答案,最小二乘法,动态规划

  1. 采用表上作业法:

运筹学线性规划例题及答案,最小二乘法,动态规划

 

运筹学线性规划例题及答案,最小二乘法,动态规划

 

  

由表上作业法,得到最优方案:A1向B1城市运输50吨,向B2城市运输150吨;A2向B1城市运输50吨,向B3城市运输180吨;

(3)最小运输费用:

 

利用lingo求解:

运行代码:

min=90*x11+70*x12+95*x13+80*x21+65*x22+75*x23;

x11+x12+x13=200;

x21+x22+x23=230;

x11+x21=100;

x12+x22=150;

x13+x23=180;

x11>0;x12>0;x13>0;

x21>0;x22>0;x23>0;

运行结果:

  Global optimal solution found.

  Objective value:                              32500.00

  Infeasibilities:                              0.000000

  Total solver iterations:                             1

  Elapsed runtime seconds:                          0.10

 

  Model Class:                                        LP

 

  Total variables:                      6

  Nonlinear variables:                  0

  Integer variables:                    0

 

  Total constraints:                   12

  Nonlinear constraints:                0

 

  Total nonzeros:                      24

  Nonlinear nonzeros:                   0

 

 

 

                                Variable           Value        Reduced Cost

                                     X11        50.00000            0.000000

                                     X12        150.0000            0.000000

                                     X13        0.000000            10.00000

                                     X21        50.00000            0.000000

                                     X22        0.000000            5.000000

                                     X23        180.0000            0.000000

 

                                     Row    Slack or Surplus      Dual Price

                                       1        32500.00           -1.000000

                                       2        0.000000            0.000000

                                       3        0.000000            10.00000

                                       4        0.000000           -90.00000

                                       5        0.000000           -70.00000

                                       6        0.000000           -85.00000

                                       7        50.00000            0.000000

                                       8        150.0000            0.000000

                                       9        0.000000            0.000000

                                      10        50.00000            0.000000

                                      11        0.000000            0.000000

                                      12        180.0000            0.000000

答:采用以下方法,得到最小运输费用为32500元,即:

A1向B1城市运输50吨,向B2城市运输150吨;A2向B1城市运输50吨,向B3城市运输180吨;

运筹学线性规划例题及答案,最小二乘法,动态规划

运筹学线性规划例题及答案,最小二乘法,动态规划

(1)

解:运筹学线性规划例题及答案,最小二乘法,动态规划

运筹学线性规划例题及答案,最小二乘法,动态规划 

 (2)采用匈牙利解法

运筹学线性规划例题及答案,最小二乘法,动态规划

 

其次可以采用优化的匈牙利解法、具体步骤如下:
step 0:观察每行最小元素个数总和r(sum)和每列最小元素个数总和c(sum)。
step 1:当 r(sum)<=c(sum),则先从系数矩阵的每列减去该列的最小元素,再从所得系数矩阵的每行元素中减去该行的最小元素。反之如果当r(sum)c(sum),则先从系数矩阵的每行减去该行的最小元素,再从所得系数矩阵的每列元素中减去该列 的最小元素。其他步骤同匈牙利法。

  1. 具体的方案有如下两个,都可以达到最小费用32:

1.甲选择B任务,乙选择C任务,丙选择A任务,丁选择D任务,戊选择E任务;

2.甲选择B任务,乙选择D任务,丙选择A任务,丁选择C任务,戊选择E任务;用lingo进行验证答案一致。

 运筹学线性规划例题及答案,最小二乘法,动态规划

 运筹学线性规划例题及答案,最小二乘法,动态规划

运筹学线性规划例题及答案,最小二乘法,动态规划 

 运筹学线性规划例题及答案,最小二乘法,动态规划

运筹学线性规划例题及答案,最小二乘法,动态规划 

运筹学线性规划例题及答案,最小二乘法,动态规划 

梯度下降法也叫最速下降法,基本思想是往函数下降最快的方向进行搜索,函数某个方向上的变化率可以用函数导数进行表征,因此搜索方向就可以根据函数导数确定,即以 f(x) 在点 xk 方向导数最小的方向作为搜索方向:

 

利用python程序求解、程序具体见附加:

运筹学线性规划例题及答案,最小二乘法,动态规划

运筹学线性规划例题及答案,最小二乘法,动态规划 

得出:x1= 3.99996710374836,

x2=1.99997966899839 ,

f(x)极小值分别为 -7.99999999942876

在通过编写MATLAB进行计算,结果如下:x1=4,x2=2时,f(x)=−8,迭代次数为12,与python程序求解一致。

 

# -*- coding: utf-8 -*-
import sympy as sy


def cal_dffi(f, a, b):
    # 声明变量
    x1 = sy.symbols("x1")
    x2 = sy.symbols("x2")
    # 求偏导
    f1 = sy.diff(f, x1)
    y1 = f1.evalf(subs={x1: a, x2: b})
    f2 = sy.diff(f, x2)
    y2 = f2.evalf(subs={x1: a, x2: b})

    return y1, y2


def gd(a, b, f, alpha, detal):
    x1 = sy.symbols("x1")  # 声明变量
    x2 = sy.symbols("x2")
    y0 = f.evalf(subs={x1: a, x2: b})  # 计算函数值

    while True:

        detalx, detaly = cal_dffi(f, a, b)
        a = a - alpha * detalx
        b = b - alpha * detaly
        y1 = f.evalf(subs={x1: a, x2: b})  # 偏导
        if abs(y1 - y0) < detal:  # 函数值
            break
        else:
            y0 = y1
    return a, b, y1


if __name__ == '__main__':
    # 定义函数
    x1 = sy.symbols("x1")  # 声明变量
    x2 = sy.symbols("x2")
    f = x1 ** 2 + 2 * x2 ** 2- 2 * x1 * x2  - 4 * x1  # 函数

    a = 1  # 初始点
    b = 1
    alpha = 0.1
    detal = 1e-10  # 精度

    a, b, y = gd(a, b, f, alpha, detal)
    print("x1,x2,f极小值分别为", a, b, y)

6.现有15米长的钢管若干,生产某产品需4米、5米、7米长的钢管各为100、150、120根,问如何截取才能使余料最省?(建立数学模型即可)

作答如下:

这是一个线性规划问题,首先要找出一共有多少中截法;

规格/根   序号

1

2

3

4

5

6

7

 

7米

2

1

1

0

0

0

0

120

5米

0

1

0

3

2

1

0

150

4米

0

0

2

0

1

2

3

100

余料/米

1

3

0

0

1

2

3

 

建立数学模型:      解:设按第i种方法截xi根(i=1,2,…7);

运筹学线性规划例题及答案,最小二乘法,动态规划

 

 

利用lingo求解:

运行代码:

min=x1+x2+x3+x4+x5+x6+x7;

2*x1+x2+x3>=120;

x2+3*x4+2*x5+x6>=150;

2*x3+x5+2*x6+3*x7>=100;

@gin(x1);@gin(x2);@gin(x3);@gin(x4);

@gin(x5);@gin(x6);@gin(x7);

结果:

  Global optimal solution found.

  Objective value:                              135.0000

  Objective bound:                              135.0000

  Infeasibilities:                              0.000000

  Extended solver steps:                               0

  Total solver iterations:                             3

  Elapsed runtime seconds:                          0.11

 

  Model Class:                                      PILP

 

  Total variables:                      7

  Nonlinear variables:                  0

  Integer variables:                    7

 

  Total constraints:                    4

  Nonlinear constraints:                0

 

  Total nonzeros:                      18

  Nonlinear nonzeros:                   0

 

 

 

                                Variable           Value        Reduced Cost

                                      X1        35.00000            1.000000

                                      X2        0.000000            1.000000

                                      X3        50.00000            1.000000

                                      X4        50.00000            1.000000

                                      X5        0.000000            1.000000

                                      X6        0.000000            1.000000

                                      X7        0.000000            1.000000

 

                                     Row    Slack or Surplus      Dual Price

                                       1        135.0000           -1.000000

                                       2        0.000000            0.000000

                                       3        0.000000            0.000000

                                       4        0.000000            0.000000

运筹学线性规划例题及答案,最小二乘法,动态规划

答:使用135根15米长的钢管,采用以下方案,余料最省:

取35根使用第一种法得到70根7米长的钢管,剩余余料35米;

取50根使用第四种法得到150根5米长的钢管,剩余余料0米;

取50根使用第三种法得到50根7米长、100根4米长的钢管,剩余余料0米;

 

  1. 请结合实例解释线性规划问题的基本(不可行)解,基本可行解,可行解(不是基本解),并说明三者之间关系。

结合生产计划用一张图,来举例分析线性规划问题的三种解:

 

 

生产计划问题:结合下列表格,如何安排生产使利润最大?

 

资源

设备

5

2

170

原材料A

2

3

100

原材料B

1

5

150

利润

10

18

 

采用图解法:

运筹学线性规划例题及答案,最小二乘法,动态规划

基本解:各个等式约束直线的交点,外加与坐标轴的交点

基本可行解:基本解里面在可行域范围的那些基本解,可行域的顶点

行解:可行解只有一个要求:满足所有约束条件

最优解:基本可行解里面使目标函数最大(最小)的基本可行解

解之间的关系如下图:

运筹学线性规划例题及答案,最小二乘法,动态规划

 

 

 

 

 

到了这里,关于运筹学—例题求解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【管理运筹学】第 8 章 | 动态规划(4,生产与储存问题)

    【管理运筹学】第 8 章 | 动态规划(1,多阶段决策过程与动态规划基本概念) 【管理运筹学】第 8 章 | 动态规划(2,动态规划的基本思想与模型求解) 【管理运筹学】第 8 章 | 动态规划(3,资源分配问题) 【管理运筹学】第 8 章 | 动态规划(4,生产与储存问题) 【管理

    2024年02月03日
    浏览(77)
  • 【管理运筹学】第 8 章 | 动态规划(3,资源分配问题)

    【管理运筹学】第 8 章 | 动态规划(1,多阶段决策过程与动态规划基本概念) 【管理运筹学】第 8 章 | 动态规划(2,动态规划的基本思想与模型求解) 【管理运筹学】第 8 章 | 动态规划(3,资源分配问题) 【管理运筹学】第 8 章 | 动态规划(4,生产与储存问题) 【管理

    2024年02月04日
    浏览(46)
  • 【管理运筹学】第 8 章 | 动态规划(1,多阶段决策过程与动态规划基本概念)

    【管理运筹学】第 8 章 | 动态规划(1,多阶段决策过程与动态规划基本概念) 【管理运筹学】第 8 章 | 动态规划(2,动态规划的基本思想与模型求解) 【管理运筹学】第 8 章 | 动态规划(3,资源分配问题) 【管理运筹学】第 8 章 | 动态规划(4,生产与储存问题) 【管理

    2024年04月23日
    浏览(43)
  • 运筹学—运输问题与表上作业法

    不考虑运价,从西北角的格子开始分配运量,按尽可能满足一方取小的原则,第一行和第一列的格子分配完后,依次向东南角方向的格子进行运量分配。 例如: 第一步:列出产售平衡表 第二步:利用西北角法进行运量分配: 首先在产售平衡表的x 11 处尽可能取最小值:min

    2024年02月12日
    浏览(45)
  • 运筹学经典问题(五):多商品流运输问题

    前面介绍了多商品网络流(MCNF)问题,今天要介绍的多商品流运输问题(Mulit-commodity Transportation Problem, MCTP)与MCNF的唯一差异别:MCTP要求商品直接从供应商运送到客户,没有中间流转的路径。 集合: S S S :供应商的集合; C C C :客户的集合; A A A :网络中弧段的集合,

    2024年02月04日
    浏览(52)
  • 【课堂笔记】运筹学第二章:对偶问题

    听说运筹学这门课挺好的,有值得一听的必要;此篇用作课堂总结、期末复习及记录。 或许与教材内容会有很大程度重复。 本章开始会适当结合一些B站网课【运筹学】应试向基础教程 对偶问题的对偶问题就是原问题 矩阵表达 要弄清楚矩阵 A A A 和 C C C 分别是什么 最好记住

    2024年02月07日
    浏览(97)
  • 运筹学的松弛变量和影子价格或者对偶价格

    1、影子价格就是对偶价格,反应的是对偶问题的决策变量的值;对偶问题中,决策变量对应的是原问题的资源,而松弛变量反应的是资源的利用问题,如果某种资源的松弛变量为0,说明这个资源在此模型下面全部用完,入股松弛变量不为0,说明,此资源还有剩余。 2、如果

    2024年02月11日
    浏览(44)
  • 一些关于运筹学和机器学习之间协同作用的思考

    几十年来,运筹学(OR)和机器学习(ML)一直作为两个相对独立的研究领域不断发展。数据科学和人工智能领域的专家可能更熟悉机器学习而不是运筹学,尽管每个机器学习实践者都应该至少了解一些优化技术,因为每个机器学习问题本质上都是一个优化问题。在本文中,我

    2024年02月05日
    浏览(50)
  • 【管理运筹学】第 7 章 | 图与网络分析(3,最短路问题)

    【管理运筹学】第 7 章 | 图与网络分析(1,图论背景以及基本概念、术语、矩阵表示) 【管理运筹学】第 7 章 | 图与网络分析(2,最小支撑树问题) 【管理运筹学】第 7 章 | 图与网络分析(4,最大流问题) 【管理运筹学】第 7 章 | 图与网络分析(5,最小费用流问题及最小

    2024年02月09日
    浏览(54)
  • 服务运营 | INFORMS论文精选:公平高效!运筹学下的器官移植

    Fairness, Efficiency, and Flexibility in Organ Allocation for Kidney Transplantation | Operations Research (informs.org) Problem 器官移植被部分患者视为拯救生命的礼物。器官的供体主要有两种渠道,包括活体供体(器官来自亲朋好友)或尸体供体。而大多数接受器官移植的患者,其器官渠道都来自尸体

    2024年02月21日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包