第一章-命题逻辑04对偶定理

《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案.doc

第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么？ 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量 0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量 0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0

命题逻辑的推理理论(牛连强)

1.7 推 理 理 论 从假设前提利用推理规则得到其他命题，即形成结论的过程就是推理，这是研究逻辑的主要目标。 1.7.1 蕴含与论证 1．推理的含义与形式 [定义1-22] 当且仅当p →q 为永真式时，称为p 蕴含q （logical implication ），记作p q ?，或p q 。此时，称p 为前提，q 为p 的有效结论或逻辑结论，也称为q 可由p 逻辑推出。得出此逻辑关系的过程称为论证。 [辨析] 由于仅在p 为1而q 为0时公式p q →为0，可见，p q →永真意味着不可能存在前件p 为1而后件q 为0的情况，或者说，若p q ?，则只要前件p 为1，后件q 也一定为1。因此，p q ?也称为“永真蕴含” ，即p 永真蕴含q 。 [延伸] 通常，定理（theorem ）被解释为“经过受逻辑限制的证明为真的陈述”，就是指对“在一定条件成立的情况下必然产生某个（些）结论”的陈述。因此，定理证明也就是对蕴含关系的论证。当然，通常只有重要或有趣的陈述才被视为定理。 所有逻辑推理的实质就是证明p q ?，也就是证明p q →为永真式。例如，以下是一个简单的初等数学证明题目： 已知a 、b 、c 为实数，且22a b bc -=，0c ≠，则有2/(/1)a c b b c =+。 如果记 p ：22a b bc -=，q ：0c ≠，r ：2/(/1)a c b b c =+ 则上述论证要求可描述为： p q r ∧? 证明的目的就是说明：若前提p q ∧正确，则结论r 也正确，即证明p q r ∧→为永真式。 通常的逻辑推理问题都会由一组前提来推断一个逻辑结论，此时的多个前提可写成合取式12n H H H ∧∧∧ ，或写成用逗号分隔的命题序列H 1, H 2, ..., H n ，即论证要求可写作： 12n H H H C ∧∧∧? ，或12,...,n H H H C ?，，或 12n H H H C ∧∧∧ ，或12,...,,n H H H C 可见，论证A C 、A C ?或A C →是永真式都是同义的，且前提也可以用集合表示，如： 12{,..,},.n H H H C 在数学上，总是要求前提为真，从而推导出有效的结论，并不需要研究从假的前提能得到什么结论，且推理形式与前提的排列次序无关。尽管由前提A 到结论C 的推理一般记作A C ，如

数学建模 对偶问题和灵敏度分析

对偶问题 例题1：某养鸡场所用的混合饲料由n 种天然饲料配合而成。要求在这批配合饲料中必须含有m 种不同的营养成分，且第i 种营养成分的含量不低于bi 。已知第i 种营养成分在每单位第j 种天然饲料中的含量为a ij ，每单位第j 天然饲料的价格为 c j 。试问，应如何对这n 种饲料配方，使这批饲料的费用最小? 解 设x j 为第j 种天然饲料的用量。 显然，a ij x j 即为所用第j 种天然饲料中第i 种营养成分的含量，1n ij j j a x =∑为这批 混合饲料中第i 种营养成分的总含量；它不应低于bi 。于是，我们得下列线性规划模型(1—1)： 1 m i n n j j j f c x ==∑ 1 1,,..01,,n ij j i j j a x b i m s t x j n =?≥=???≥=? ∑ 现设想有一个饲料加工厂欲把这m 种营养成分分别制成m 种营养丸。 设第i 种营养丸的价格为ui(i ＝1，…，m)。则养鸡场采购一个单位的第j 种天然饲料，就相当于对这m 种营养丸分别采购数量a 1j ，…a mj ，所化费用为1m ij i i a u =∑养鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件： 1 1,,m i j i j i a u c j n =≤=∑ 另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i 种营养丸就需采购bi 个单位，所化费用为b i u i ，总费用为z=∑b i u i 饲料加工厂面临的问题是：应把这m 种营养丸的单价ui(f=1，…，m)定为多少，才能使养鸡场乐意全部采用该厂生产的营养丸来取代这批天然饲料，且使本厂在竞争中得到最大收益。为该问题建立数学模型，即得如下线性规划(1—2)：

第3章对偶理论

第3章 对偶理论 §3.1 线性规划的对偶理论 3.1.1 对偶问题的表述 对称形式的对偶： （L ） cx min (D) wb max s.t. b Ax ≥ s.t. c wA ≤ 0≥x 0≥w 其中c 为n 维行向量，A 为n m ?矩阵，b 为m 维列向量，x 表示n 维列向量，w 表示m 维行向量。 称(D)为线性规划(L)的对偶规划问题。 定理1 (L)与(D)互为对偶规划问题。――（对合性） 例 设原问题 对偶问题 , 12 5 s.t.min 21212121≥≥-≥+-x x x x x x x x 0 , 1 2 1 s.t.5 max 2121212 1≥-≤-≤++w w w w w w w w 非对称形式的对偶： （LP ） cx min (DP) wb max s.t. b Ax = s.t. c wA ≤ 0≥x 例 设原问题 对偶问题 ,, 523 4 s.t.345min 321321321321≥=++=++++x x x x x x x x x x x x 3 4 2 5 3 s.t.5 4 max 2121212 1≤+≤+≤++w w w w w w w w 一般线性规划问题： 可化为上述二者之一讨论其对偶问题，也可直接写出对偶问题，详细的对应法则见教材（陈宝林）124页。

直接写出对偶的弊端之一是对偶最优解不易确定，而对称形式和非对称形式对偶的最优解都可由原问题的单纯形乘子确定出来。 3.1.2 对偶定理(强对偶定理和弱对偶定理) 定理2 (弱对偶定理)：设x 和w 分别是 （L ） cx min 和 (D) wb max s.t. b Ax ≥ s.t. c wA ≤ 0≥x 0≥w 的可行解，则有下列不等式成立： b w x c ≥ 证明：由于b x A ≥和0≥w ，则有b w x A w ≥。 由于A w c ≥和0≥x ，则有x A w x c ≥。 因此有b w x c ≥ 推论 1 设x 和w 分别是(L)和(D)的可行解，且有b w x c =，则x 和w 分别是(L)和(D)的最优解。 推论2 如果(L)的目标函数在可行集上无下界，则对偶规划(D)无可行解。 推论3 如果(D)的目标函数在可行集上无上界，则原始规划(L)无可行解。 定理3 (强对偶定理)：如果互为对偶规划的两个问题之一有最优解，则另一个问题也有最优解，并且二者的目标值相等。 证明：设原问题（L ）存在最优解，引进松弛变量，写成等价形式： s.t. min ≥≥=-v x b v Ax cx （1） 由于（1）存在最优解，因此可以用单纯形方法求出它的一个最优基本可行解，不妨设该最优解是?? ????=v x y ，相应的最优基是B 。此时所有判别数均非正，即 j c p w j j ?≤- ,0 （2） 1-=B c w B 为单纯形乘子。

逻辑判断推理中常用的逻辑公式

逻辑判断推理中常用的 逻辑公式 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】

逻辑命题与推理 必然性推理（演绎推理）：对当关系推理、三段论、复合命题推理、关系推理和模态推理 可能性推理：归纳推理（枚举归纳、科学归纳）、类比推理 命题 直言命题的种类：（AEIOae） ⑴全称肯定命题：所有S是P（SAP） ⑵全称否定命题：所有S不是P（SEP） ⑶特称肯定命题：有的S是P（SIP） ⑷特称否定命题：有的S不是P（SOP） ⑸单称肯定命题：某个S是P（SaP） ⑹单称否定命题：某个S不是P（SeP） 直言命题间的真假对当关系： 矛盾关系、（上）反对关系、（下）反对关系、从属关系 矛盾关系：具有矛盾关系的两个命题之间不能同真同假。主要有三组： SAP与SOP之间。“所有同学考试都及格了”与“有些同学考试不及格” SEP与SIP之间。“所有同学考试不及格”与“有些同学考试及格” SaP与SeP之间。“张三考试及格”与“张三考试不及格” 上反对关系：具有上反对关系的两个命题不能同真（必有一假），但是可以同假。即要么一个是假的，要么都是假的。存在于SAP与SEP、SAP与SeP、SEP与SaP之间。 下反对关系：具有下反对关系的两个命题不能同假（必有一真），但是可以同真。即要么一个是真的，要么两个都是真的。存在于SIP与SOP、SeP与SIP、SaP与SOP之间。 从属关系（可推出关系）：存在于SAP与SIP、SEP与SOP、SAP与SaP、SEP与SeP、SaP与SIP、SeP与SOP

六种直言命题之间存在的对当关系可以用一个六角图形来表示，“逻辑方阵图” SAP SEP SaP SeP SIP SOP 直言命题的真假包含关系 全同关系、真包含于关系、真包含关系、交叉关系、全异关系 复合命题：负命题、联言命题、选言命题、假言命题 负命题的一般公式：并非P 联言命题公式：p并且q “并且、…和…、既…又…、不但…而且、虽然…但是…” 选言命题：相容的选言命题、不相容的选言命题 相容的选言命题公式：p或者q“或、或者…或者…、也许…也许…、可能…可能…” 【一个相容的选言命题是真的，只有一个选言支是真的即可。只有当全部选言支都假时，相容的选言命题才是假的】 不相容选言命题公式：要么p要么q

对偶与灵敏度分析

§2 对偶与灵敏度分析 §2.1 LP 的对偶问题 无论从理论和实践角度，对偶理论是LP 中的一个最重要和有趣的概念，支持对偶理论的基本思想是：每一个LP 问题都存在一个与其对偶的问题，在求解一个问题解的时候，也同时给出了另一问题的解。 一、问题的提出 例2.1：设某工厂生产两种产品甲乙，生产过程需要4种设备ABCD 进行加工，每件产品加工所需机时数，每件产品的利润值及每种设备的可利用机时如下表： 1.问：充分利用设备时，应怎样安排甲乙产品的生产数量，利润才能最大？ 2.问：如有另外一家公司想租用该厂设备加工生产，那么，这家公司应至少对每台设备的机时价格为多少时，才能使该厂愿意出租设备？ 解：1.设甲乙产品各生产1x 2x 件

LP1：?????? ?≥≤≤+≤++=0 ,1648 212 2232211 21212 1x x x x x x x x x MaxZ 2.设每台设备的机时最低价分别为：1y ，2y ，3y ，4y LP2：??? ??=≥≥++≥+++++=4,3,2,1,03422242121681242 13 214 321i y y y y y y y y y y y MinZ i 二、原问题和对偶问题之间的关系： 1.对称形式下的原问题与对偶问题 对称形式下原问题的一般式： 矩阵形式： ????? ?? ??=≥≤+++≤+++≤++++++=n j x b x a x a x a b x a x a x a b x a x a x a x c x c x c MaxZ j m n mn m m n n n n n n ....... 21,0 (221) 1222221211 12121112211 ???≥≤=0X b AX CX Max 若用i y 代表第i 种资源的估价，则其对偶问题的一般式为： ????? ?? ??=≥≥+++≥+++≥++++++=m j y c y a y a y a c y a y a y a c y a y a y a y b y b y b MinZ j n m mn n n m mn m m m m ....... 21,0 (221) 1222221121 12211112211 ???≥≥=0Y C Y A Yb Min T T ω 2.非对称形式下原问题与对偶问题： 方法一：将非对称形式转化为对称形式，求出对偶问题，然后再还原。

离散数学结构 第3章 命题逻辑的推理理论

第3章命题逻辑的推理理论 3.1 推理的形式结构 一、有效推理 数理逻辑的主要任务是用数学的方法来研究数学中的推理。所谓推理是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式。要研究推理就应该给出推理的形式结构，为此，首先应该明确什么样的推理是有效的或正确的。 定义3.1设A1,A2,…,A k和B都是命题公式，若对于A1,A2,…,A k和B中出现的命题变项的任意一组赋值，或者A1∧A2∧…∧A k为假，或者当A1∧A2∧…∧A k为真时，B 也为真，则称由前提A1,A2,…,A k推出B的推理是有效的或正确的，并称B是有效结论。 关于定义3.1还需要做以下几点说明： 1．由前提A1,A2,…,A k推结论B的推理是否正确与诸前提的排列次序无关。因而前提的公式不一定是序列，而是一个有限的公式集合，若将这个集合记为Г，可将由Г推B 的推理记为Г├B。若推理是正确的，则记为ГB，否则记为ГB。这里，可以称Г├B和{ A1,A2,…,A k}├B 为推理的形式结构。 2．设A1,A2,…,A k，B中共出现n个命题变项，对于任何一组赋值α1,α2,…,αn(αi =0或者1，i=1,2,…,n)，前提和结论的取值情况有以下四种： (1) A1∧A2∧…∧A k为0，B为0. (2) A1∧A2∧…∧A k为0，B为1. (3) A1∧A2∧…∧A k为1，B为0. (4) A1∧A2∧…∧A k为1，B为1. 由定义3.1可知，只要不出现(3)中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现(3)中的情况。 3．由以上的讨论可知，推理正确，并不能保证结论B一定为真，这与数学中的推理是不同的。

数学建模 对偶问题和灵敏度分析资料讲解

数学建模对偶问题和灵敏度分析

对偶问题 例题1：某养鸡场所用的混合饲料由n 种天然饲料配合而成。要求在这批配合饲料中必须含有m 种不同的营养成分，且第i 种营养成分的含量不低于bi 。已知第i 种营养成分在每单位第j 种天然饲料中的含量为a ij ，每单位第j 天然饲料的价格为c j 。试问，应如何对这n 种饲料配方，使这批饲料的费用最小? 解 设x j 为第j 种天然饲料的用量。 显然，a ij x j 即为所用第j 种天然饲料中第i 种营养成分的含量，1n ij j j a x =∑为这批混 合饲料中第i 种营养成分的总含量；它不应低于bi 。于是，我们得下列线性规划模型(1—1)： 1 min n j j j f c x ==∑ 1 1,,..01,,n ij j i j j a x b i m s t x j n =?≥=???≥=? ∑ 现设想有一个饲料加工厂欲把这m 种营养成分分别制成m 种营养丸。 设第i 种营养丸的价格为ui(i ＝1，…，m)。则养鸡场采购一个单位的第j 种天然饲料，就相当于对这m 种营养丸分别采购数量a 1j ，…a mj ，所化费用为1m ij i i a u =∑养 鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件： 1 1, ,m ij i j i a u c j n =≤=∑ 另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i 种营养丸就需采购bi 个单位，所化费用为b i u i ，总费用为z=∑b i u i

对偶理论与灵敏度分析练习题答案

第二章 对偶理论与灵敏度分析练习题答案 1．判断下列说法是否正确： (1) 任何线性规划问题存在并具有惟一的对偶问题；() (2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；() (3) 设j ? x ，i ?y 分别为标准形式的原问题与对偶问题的可行解，* j x ，*i y 分别为其最优解，则恒有n n m m **j j j j i i i i j 1j 1i 1i 1??c x c x b y b y ====≤=≤∑∑∑∑；() (4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；() (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；() (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；() (7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；() (8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；() (9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；() (10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。() 2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。 要求：(1) (3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。(4)若以单价购入第一种资源是否值得，为什么若有人愿意购买第二种资源应要价多少，为什么

第二章对偶理论与灵敏度分析练习题答案

第二章 对偶理论与灵敏度分析练习题答案 1．判断下列说法是否正确： (1) 任何线性规划问题存在并具有惟一的对偶问题；() (2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；() (3) 设j ? x ，i ?y 分别为标准形式的原问题与对偶问题的可行解，*j x ，*i y 分别为其最优解，则恒有n n m m **j j j j i i i i j 1 j 1 i 1 i 1 ??c x c x b y b y ====≤=≤∑∑∑∑；() (4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；() (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；() (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；() (7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；() (8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；() $ (9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；() (10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。() 2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。 X B ｂ x 1 x 2 x 3 x 4 x 5 — x 3 5/2 0 1/2 1 1/2 0 x 1 5/2 1 — -1/2 0 -1/6 1/3 σj 0 -4 0 -4 -2 ; 要求：(1)写出原线性规划问题及其对偶问题的数学模型；(2)直接由表写出对偶问题的最优解； (3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。(4)若以单价购入

命题逻辑中几种常见的推理证明方法

ljlj 逻 辑 学 论 文 数学科学学院 09级3班 吴洁琼 学号2009040288

命题逻辑中几种常见的推理证明方法 吴洁琼 哈尔滨师范大学 （黑龙江·哈尔滨 150025） 【摘 要】：命题逻辑的推理证明是《离散数学》课程的重点难点内容，其主要原因有两个： 一是内容比较抽象且方法较独特，其灵活性很大, 故很难掌握；二是题型以证明题居多, 大多数题的知识面涉及较广, 故习题较难。而命题逻辑又是数理逻辑的基础, 熟练而灵活地掌握好命题逻辑中推理证明的方法既是学习命题逻辑的重点, 又会为进一步学习谓词逻辑打下良好的基础。本文结合适当的例题讲解，总结了命题逻辑中几种常见的推理证明方法，并进行了分析和探讨,以加深学生的理解，以及知识的灵活使用。 以期在帮助学生掌握命题逻辑的推理证明方法的同时, 又能对学生进行逻辑思维能力的训练,培养学生分析问题和解决问题的能力。 【关键词】：命题逻辑；推理；证明方法 数理逻辑是《离散数学》课程的主要内容之一，它主要包括命题逻辑和谓词逻辑两大部分, 而命题逻辑又是谓词逻辑的基础,其中的内容也比较抽象，所以学好命题逻辑又是学好数理逻辑的关键。学好数理逻辑既能加强学生的逻辑思维能力，又同时能够帮助同学学习数字电路和人工智能等其它课程。数理逻辑中关于命题逻辑证明题比较多，学好数理逻辑的关键是能不能很好的掌握这些证明题。 一、命题逻辑中推理的相关概念 定义1：一个命题公式序列1α，2α， ，n α；β，即βααα→ΛΛΛ)(21n 称为推理形式，其中序列最后一项β称为推理的结论，1α，2α， ，n α称为推理的条件。 定义2：对于命题公式序列1α，2α， ，n α；β的命题变元组);,,,(21p p p p n 的任意指派);,,,(21t t t t n 存在使n αααΛΛΛ 21为真，而β为假，则称此推理为无效推理，否则是有效推理。 证明命题公式β为有效结论的过程就是命题逻辑推理证明的过程。而证明推理形式1α， 2α， ，n α；β是有效的充要条件是βααα→ΛΛΛ)(21n 为重言式。 二、常见证明方法 命题逻辑的推理证明有六种常用证明方法，分别是直接证明法，真值表法,范式法，间接证明法。其中间接证明法里面常见的是CP 规则证明法和反证法，本文就这几种方法进行论述。

运筹学对偶理论与灵敏度分析作业

作业： 问题1：书本P71第7题 1、设x1 、x2 、x3分别为A产量，B产量，C产量 目标函数：Z=4 x1 +x2 +5x3 约束条件： +3x2 + 5x3<=45 6x 3x1 +4x2 +5x3<=30 x1 、x2 、x3>0 2、A的利润在3~6之间，最优计划不变。 3、设x1 、x2 、x3、x4 分别为A产量，B产量，C产量，D产量 目标函数：Z=4 x1 +x2 +5x3+2.5x4 约束条件： +3x2 + 5x3+3x4<=45 6x 3x1 +4x2 +5x3+2x4<=30 x1 、x2 、x3、x4>0 利润从35增加到37.5，值得生产。 4、见Excel 问题2：某厂拟生产甲、乙、丙三种产品，都需要在A，B两种设备上加工，有关数据如下表所示： （1）如何充分发挥设备能力，使产品总产值最大？ 设x1 、x2 、x3分别为甲产量，乙产量，丙产量 目标函数：Z=3 x1 +2x2 +x3 约束条件： +2x2 + 1x3<=400 x 2x1 +1x2 +2x3<=500 x1 、x2 、x3>0 最优解 甲产量乙产量丙产量 200 100 0 总产值最大800 （2） 200个甲产品在A设备上加工1小时，B设备上加工2小时。

100个乙产品在A设备上加工2小时，B设备上加工1小时。 丙产品不生产。 使得总产值最大为80万。 （3）试分别确定甲产品单位产值、B设备供量各自的影响范围。 甲产品的范围是198~201。 B设备供量的范围是200~800。 （4）若每月能以39万元租金租用外厂B设备300台时，则应否租用？为什么？ 原来的产值为80万，租用外厂之后的产值为120万，则产值增加了40万，而租金要39万，则增加的产值足够支付租金，最后剩余1万，说明能租用。 （5）若每月A设备提供量减少200台时，B设备供量增加100台时，试问最优解与影子价格有何变化？ 最优解是600 影子价格：A设备从0.333~3 ；B设备从1.333~0

线性规划的对偶理论与灵敏度分析习题

线性规划的对偶理论与灵敏度分析习题

1 第二章 线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1) ?????? ?≥=++≤++≥++++=无约束 3213213213213 21,0,5343322 43422min x x x x x x x x x x x x x x x z (2) ?????? ?≤≥≤++≥-+-=++++=0 ,0,8374355 22365max 321321321321321x x x x x x x x x x x x x x x z 无约束 (3) ????? ??????==≥=====∑∑∑∑====),,1;,,1(0),,1(),,1(min 1 111 n j m i x n j b x m i a x x c z ij m i j ij n j i ij m i ij n j ij

2 (4) ????? ??????=≥++==<=<=∑∑∑===) ,,,,1(0),,2,1(),,1(min 1 211 111 n n j x m m m i b x a m m i b x a x c z j n j i j ij n j i j ij n j j j 无约束 2. 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行 解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行 解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶 问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值； (4)任何线性规划问题具有唯一的对 偶问题。 3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。 3 2 2 0 0 0

判断推理——逻辑判断

、必然性推理 概念间关系 直言命题的对当关系 直言命题的变形推理 三段论推理 联言命题与选言命题 假言命题 模态命题 智力推理 ? 概念间关系（概念，是构成命题与推理的基础，只有表达了一类事物的词语才是概念） 直言命题（简单命题），是断定对象是否具有某种性质的单句 ? 直言命题的对当关系（不同直言命题之间在真假方面所存在的制约关系） 所有 A 是 B 反对 ........... 所有 A 不是 B 推出 推出 有的 A 是 B. “所有A 是B ” 与“有的A 不是B ”、“.所有A 不是B ”与“有的A 是 B ”必有一真一假 “所有A 是B ”与“.所有A 不是 B ” 必有一假（可以同假） “有的 A 不是B ”与“有的 A 是 B ” 必有一真（可以同真） 一个命题前面+“并非”=这个命题的矛盾命题 所有与有的互换，有“不”的去掉，没“不”的加上 ? 直言命题的变形推理（通过改变前提中直言命题的联项或主项与谓项的关系 结论） ①换质推理 双重否定表示肯定 将“不是”改为“是”或将“是”改为“不是” ②换位推理（倒过来说） 所有A 是B 有些B 是 A 所有 A 不是 B 所有 B 不是 A 有些 A 是 B 有些 B 是 A 有些 A 不是 B 特殊词量（少数，大部分，一半）作为量项引导命题，不能换位 ? 三段论推理（两个直言命题作为前提/ 一个直言命题作为结论） （两个前提包含三个概念/ 前提和结论中，每个概念都出现两次） 两条常用规则 一特得特：两个前提不能都是特称命题（含有“有的”命题） 只有一个前提是特称，结论也是特称 一否得否：两个前反对 矛盾 . 有的A 不是 B 下反对

《运筹学》第3章习题

第三章线性规划对偶理论与灵敏度分析习题 一、 思考题 1． 对偶问题和对偶变量的经济意义是什么 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么 3．什么是资源的影子价格它和相应的市场价格之间有什么区别 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化有多少种不同情况如何去处理 二、 判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0

运筹学_第2章_对偶理论习题

第二章线性规划的对偶理论 2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x2－4x3 x1 + 3x2 + 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2，x3≥0 解：其对偶问题为 min w=30y1+ 80y2 y1+ 4y2≥2 3y1 + 2y2 ≥2 3y1 + 4y2≥－4 y1、y2≥0 2.2 写出下列线性规划问题的对偶问题 min z=2x1+8x2－4x3 x1 + 3x2－3x3 ≥30 －x1 + 5x2 + 4x3 = 80 4x1 + 2x2－4x3≤50 x1≤0、x2≥0，x3无限制 解：其对偶问题为 max w=30y1+80 y2+50 y3 y1－y2 + 4 y3≥2 3y1+5y2 + 2y3≤8 －3y1 + 4y2－4y3 =－4 y1≥0，y2无限制，y3≤0 2.3已知线性规划问题 max z=x1+2x2+3x3+4x4 x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0 其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。 解：其对偶问题为

min w=20y1+ 20y2 y1 + 2y2≥1 （1） 2y1 + y2 ≥2 （2） 2y1 +3y2≥3 （3） 3y1 +2y2≥4 （4） y1、y2≥0 将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以 2x3*+3x4* = 20 3x3* +2x4* = 20 解得x3* = x4* = 4。故原问题的最优解为 X*=（0，0，4，4）T 2.4用对偶单纯形法求解下列线性规划 min z=4x1+2x2+6x3 2x1 +4x2 +8x3 ≥24 4x1 + x2 + 4x3≥8 x1、x2，x3≥0 解将问题改写成如下形式 max（－z）=－4x1－2x2－6x3 －2x1－4x2 －8x3 + x4=－24 －4x1－x2－4x3+x5 =－8 x1、x2，x3，x4，x5≥0 显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。

《运筹学》第3章习题

第三章线性规划对偶理论与灵敬度分析习题 一、思考题 1.对偶问题和对偶变量的经济意义是什么 2.简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么 3.什么是资源的影子价格它和相应的市场价格之间有什么区别 4.如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数 之间的关系 5.利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解 6.在线性规划的最优单纯形表中，松弛变量（或剩余变量）>0,其经济意 义是什么 7.在线性规划的最优单纯形表中，松弛变量心+代的检验数（T n+k > 0 （标准形为求 最小值），其经济意义是什么 8.将（幻，Cj的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化有多少种不同情况如何去处理 二、判断下列说法是否正确 1.任何线性规划问题都存在且有唯一的对偶问题。 2.对偶问题的对偶问题一定是原问题。 3.若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4.对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优 解。 5.若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6.已知在线性规划的对偶问题的最优解中，对偶变量y；>0,说明在最优生产计划 中，第i种资源已经完全用尽。 7.已知在线性规划的对偶问题的最优解中，对偶变量y；=0,说明在最优生产计划 中，第i种资源一定还有剩余。 8.对于（们，勺，勺来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9.若某种资源的影子价格为Z7,则在其它资源数量不变的情况下，该资源增加￡ 个单 位，相应的目标函数值增加ku o 10.应用对偶单纯形法计算时，若单纯形表中某一基变量X,. < 0,且母所在行的 所有元素都大于或等于零，则其对偶问题具有无界解。

逻辑判断推理中常用的逻辑公式

逻辑命题与推理 必然性推理（演绎推理）：对当关系推理、三段论、复合命题推理、关系推理和模态推理 可能性推理：归纳推理（枚举归纳、科学归纳）、类比推理 命题 直言命题的种类：（AEIOae） ⑴全称肯定命题：所有S是P（SAP） ⑵全称否定命题：所有S不是P（SEP） ⑶特称肯定命题：有的S是P（SIP） ⑷特称否定命题：有的S不是P（SOP） ⑸单称肯定命题：某个S是P（SaP） ⑹单称否定命题：某个S不是P（SeP） 直言命题间的真假对当关系： 矛盾关系、（上）反对关系、（下）反对关系、从属关系 矛盾关系：具有矛盾关系的两个命题之间不能同真同假。主要有三组： SAP与SOP之间。“所有同学考试都及格了”与“有些同学考试不及格” SEP与SIP之间。“所有同学考试不及格”与“有些同学考试及格” SaP与SeP之间。“张三考试及格”与“张三考试不及格” 上反对关系：具有上反对关系的两个命题不能同真（必有一假），但是可以同假。即要么一个是假的，要么都是假的。存在于SAP与SEP、SAP与SeP、SEP与SaP之间。 下反对关系：具有下反对关系的两个命题不能同假（必有一真），但是可以同真。即要么一个是真的，要么两个都是真的。存在于SIP与SOP、SeP与SIP、SaP与SOP之间。 从属关系（可推出关系）：存在于SAP与SIP、SEP与SOP、SAP与SaP、SEP与SeP、SaP与SIP、SeP与SOP 六种直言命题之间存在的对当关系可以用一个六角图形来表示，“逻辑方阵图” SAP SEP SaP SeP

SIP SOP 直言命题的真假包含关系 全同关系、真包含于关系、真包含关系、交叉关系、全异关系 复合命题：负命题、联言命题、选言命题、假言命题 负命题的一般公式：并非P 联言命题公式：p并且q “并且、…和…、既…又…、不但…而且、虽然…但是…” 选言命题：相容的选言命题、不相容的选言命题 相容的选言命题公式：p或者q“或、或者…或者…、也许…也许…、可能…可能…” 【一个相容的选言命题是真的，只有一个选言支是真的即可。只有当全部选言支都假时，相容的选言命题才是假的】不相容选言命题公式：要么p要么q “要么…要么…、不是…就是…、或者…或者…二者必居其一、或者…或者…二者不可兼得” 【一个不相容的选言命题是真的，有且只有一个选言支是真的。当选言支全真或全假时，此命题为假】 假言命题：充分条件假言命题、必要条件假言命题、充要条件假言命题 充分条件假言命题公式：如果p，那么q“如果…就…、有…就有…、倘若…就…、哪里有…哪里有…、一旦…就…、假若…、只要…就…” 【有前件必然有后件。如果有前件却没有后件，这个充分条件假言命题就是假的。因此，对于一个充分条件的假言命题来说，只有当其前件真而后件假时，命题才假。】 必要条件假言命题公式：只有p，才q “没有…就没有…、不…不…、除非…不…、除非…才…” 【没有前件必然没有后件。如果没有前件也有后件，这个必要假言命题为假。对于一个必要条件的假言命题来说，只有当其前件假而后件真时，命题才假。】 充要条件假言命题公式：当且仅当p，才q 【有前件必然有后件，没有前件必然没有后件。充要条件假言命题在前件与后件等值即前件真并且后件真，或者前件假并且后件假时，命题为真，在前件与后件不等值即前真后假，或前假后真时，命题为假】

天津大学《最优化方法》复习题(含答案)

天津大学《最优化方法》复习题（含答案） 第一章 概述(包括凸规划) 一、 判断与填空题 1 )].([arg )(arg min max x f x f n n R x R x -=∈∈ √ 2 {}{} .:)(m in :)(m ax n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题 )(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切 )(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f D x ∈的严格局部最 优解. ? 5 给定一个最优化问题，那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈?，有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为下降算法， 则对{}Λ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ .

逻辑学版答案复合命题及其推理

第五章复合命题及其推理 一、分析下列语句各表达什么复合命题？请写出其逻辑式。 1.书山有路巧为径，学海无涯乐作舟。 答：这是一个二支联言命题，可表示为：p∧q 2．只有发展外向型经济，才能打入国际市场。 答：这是一个必要条件假言命题，可表示为：p←q 3．但凡家庭之事，不是东风压倒西风，就是西风压倒东风。 答：这是一个二支不相容选言命题，可表示为：p q 4．并不是每一个科学家都是上过大学的。 答：这是个负A 命题，它等值一个O 命题：?(SAP) ←→ SOP 5．足球的进攻方式，主要是中路突破，此外或边线进攻，或长传短切，或单刀直入。 答：这是一个四支不相容选言命题：p q r s 6．法律如果并且只有推开特权的大门，才能跨进人民的心。 答：这是一个充分必要条件假言命题：p←→ q 二、下列语句是否表达选言命题？如表达，各表达什么选言命题？请 写出逻辑式。 1．身体不好，或者是由于有病，或者是由于锻炼差，或者是由于营养 不良。 答：表达一个三支相容选言命题：p∨q∨r 2．这堂课是你上，还是我上？ 答：表达一个二支不相容选言命题：p q 3．这次围棋名人赛，要么小林光一取得胜利，要么马晓春取得胜利。答：表达一个二支不相容选言命题：p q 4．雇用的女工大抵非馋即懒，或者馋而且懒。 答：表达一个二支相容选言命题，用p 表示“女工馋”，用q 表示“女 工懒”，其逻辑式为：p∨q，也可理解为三支不相容选言命题：（?p∧q）(p∧?q) (p∧q),二者等值。 三、下列语句是否表达假言命题？如表达，各表达哪种假言命题？请 写出它们的逻辑式。 1．一人抽烟，大家受害。 答：表达一个充分条件假言命题：如果一人抽烟，那么大家受害，p →q 2．人们首先必须吃、喝、住、穿，然后才能从事政治、科学、艺术、 宗教等等。 答：表达一个必要条件假言命题：p←q 3．如果说幼年时期的无知是天真的表现的话，那么，成年以后还满足 于自己的无知就是愚蠢的表现了。 答：这个假设句不表达假言命题，而表达转折联言命题。 4．人不犯我，我不犯人；人若犯我，我必犯人。 答：表达一个充分必要条件假言命题，用p 表示"人犯我"，用q 表示 “我犯人”：p←→q 5．没有共产党，就没有新中国。 答：可有两种理解：一是充分条件假言命题，一是必要条件假言命题。