Hedging uncertainty Approximation algorithms for stochastic optimization problems
Hedging Uncertainty:Approximation Algorithms for Stochastic
Optimization Problems
R.Ravi?Amitabh Sinha?
August20,2003
Abstract
We initiate the design of approximation algorithms for stochastic combinatorial optimization prob-lems;we formulate the problems in the framework of two-stage stochastic optimization,and provide
nearly tight approximation algorithms.Our problems range from the simple(shortest path,vertex
cover,bin packing)to complex(facility location,set cover),and contain representatives with di?erent
approximation ratios.
The approximation ratio of the stochastic variant of a typical problem is of the same order of mag-nitude as its deterministic counterpart.Furthermore,common techniques for designing approximation
algorithms such as LP rounding,the primal-dual method,and the greedy algorithm,can be carefully
adapted to obtain these results.
1Introduction
With the increasing success of optimization algorithms in process optimization,these methods are making inroads into earlier planning stages of large scale projects.The inherent di?erence between optimization at the planning stage and post-facto optimization is that in the former,data is not fully available.Yet costly decisions with wide-ranging implications need to be taken in the face of incomplete data.Nevertheless, quite often forecasts of future uncertainty are available that can be used in the planning model.Forecasts, by nature,are imprecise and provide at best a range of possible futures.The?eld of stochastic optimization is an attempt to model such situations.For a detailed introduction,please consult one of the recent texts on the topic(Birge and Louveaux,1997;Kall and Wallace,1994;Klein Haneveld and van der Vlerk,2003).
In a parallel development,the?eld of approximation algorithms evolved to counter the prohibitive resource requirements for exact solution of NP-hard combinatorial optimization https://www.wendangku.net/doc/5216649773.html,rmally,these algorithms run in polynomial time and deliver a performance ratio on the quality of the output solution over all instances.As the size of the models being solved increases in scale,this solution approach gains in importance.For a detailed exposition of this topic,the reader is referred to Vazirani(2001)and Ausiello et al(1999).
However,as approximation algorithms become more sophisticated in scope and technique,the refrain from real-world practitioners who have the need for such algorithms is that the input data is seldom well-de?ned,thus diminishing the value of the solutions and guarantees provided by the algorithm.Conversely, while the?eld of stochastic optimization models the uncertainty in data fairly well,the running times of ?GSIA,Carnegie Mellon University,Pittsburgh PA15213.ravi@https://www.wendangku.net/doc/5216649773.html,
?GSIA,Carnegie Mellon University,Pittsburgh PA15213.asinha@https://www.wendangku.net/doc/5216649773.html,
the exact algorithms developed in the stochastic optimization community often prove prohibitive.This paper combines the best of both worlds,by providing approximation algorithms for the stochastic version of several classical optimization problems.
2Background
2.1Two-stage model
Among the most popular models in stochastic optimization is the two-stage model with recourse.At the outset,some data may be known deterministically,whereas the uncertain future is characterized only by a probability distribution.The decisions made at this point are referred to as the?rst-stage decisions. Subsequently,the actual future is realized,and then there may be the opportunity to augment the?rst-stage solution in order to optimized for the realized scenario.This second stage of decision making is called the recourse stage.The goal is to optimize the?rst-stage decision variables so as to minimize the expected cost over both stages.
2.2Mathematical formulation
Formally,a two-stage stochastic optimization problem with recourse is de?ned as follows.Vector x is the set of decision variables which have to be?xed in the?rst stage,when only partial information is available. Later,full information is made available and we choose some second-stage(or recourse)variables x to augment the?rst-stage solution x0.Letξrepresent the random vector which de?nes the constraint matrix T,cost vector q and requirement vector h when the full information is made available,and let A,c,and b de?ne the same for the?rst stage.Let P denote additional constraints such as non-negativity or integrality which the components of x0and x need to satisfy.The stochastic program can be written as:
min c T x0+EξQ(x0,ξ)(IP S1)
s.t.Ax0=b
x0∈P
where Q(x0,ξ)=min q T x
s.t.T(x0,x )=h
x ∈P
Here Q(x0,ξ)represents the optimal cost of the second stage,conditioned on scenarioξ=(q,T,h) having been realized and a?rst-stage setting of the variables x0.The expectation is taken with respect to ξ.
2.3Stochastic optimization with?nite scenarios
A popular restriction of the two-stage model is where the second stage is characterized by a?nite set of m scenarios.In scenario k,the constraint matrix,cost vector and requirement vector take on values T k,q k and h k respectively,and scenario k occurs with probability p k.In this case,we can write IP S1in extensive form as follows,where x k represents our choice for the variable x if scenario k materializes:
min c T x0+
m
k=1
p k(q k)T x k(IP S2)
s.t.Ax0=b
T k(x0,x k)=h k k=1,2,...,m
(x0,x k)∈P k=1,2,...,m
The interested reader may refer to any of the texts cited above for a more complete description of models of stochastic optimization and their uses.Schultz,Stougie and van der Vlerk(1996)provide an excellent survey of two-stage stochastic integer programming,while Kong and Schaefer(2003)recently provided approximation algorithms for a class of such problems.The relevance of the?nite scenario model becomes more pronounced in light of the recent work on scenario reduction by Heitsch and R¨o misch(2003).
2.4Approximation algorithms
The raison d’etre for approximation algorithms is the prohibitively high running time of exact algorithms for integer programming and combinatorial optimization,due to their NP-completeness.Approximation algorithms are therefore required to run in time polynomial in the size of the input.At the same time, they provide guarantees in the form of approximation ratios.If C is a class of minimization problems and OP T(I)and A(I)respectively denote the value of an optimal solution and the solution output by algorithm A,then the approximation ratioρ(A)of algorithm A is de?ned as follows:
ρ(A)=max
I∈C
A(I) OP T(I)
The area of approximation algorithms has been one of the most active areas of optimization in the past decade.However,barring a few exceptions,most approximation algorithms assume complete knowledge of the input at the outset.Skutella and Uetz(2001)and Mohring,Schulz and Uetz(1999)studied approxima-tion algorithms for scheduling problems,while Karger and Minko?(2000)considered a Steiner tree problem in a slightly di?erent model of stochastic optimization.
2.5Our results
The aims of this paper are multifarious.We demonstrate the relevance and applicability of developing approximation algorithms for stochastic optimization problems.We carefully adapt existing techniques for deterministic versions of the problems we study to provide approximation guarantees for the stochastic versions within constant factors.
We provide polynomial time approximation algorithms for several classical combinatorial optimization problems,in a two-stage stochastic optimization setting with?nitely many scenarios.Our results are sum-marized in Figure1.The current best known deterministic approximations are listed,with a“1”meaning that the problem can be solved optimally in polynomial time.All the stochastic approximation ratios are derived in this paper.Some of the hardness results are carried over from the underlying deterministic problems;these are mentioned with citations.The remaining are proved in this paper.
In the table in Figure1,we use m to refer to the number of scenarios and n to refer to the number of combinatorial elements(the number of vertices in the shortest paths problems and the number of elements
Problem
Det.Stochastic Stochastic Hardness approx.elements approximation Shortest
1[9]Sink O(1)MAX-SNP paths
Sink and metric O (log 2n log m )?(log 2n )Bin packing
APTAS[7]Object sizes APTAS NP-complete[7]Facility
1.52[26]Client demands,8 1.46[12]location
facility costs Vertex cover
2[28]Vertex weights,2 1.16[15]Incidence Set cover O (log n )[17]Set weights,O (log nm )?(log n )[1],
Set inclusions
?(log m )Figure 1:Summary of results.
in the set cover problem).An APTAS (Ausiello et al,1999)is an asymptotic polynomial time approximation scheme,which is an algorithm whose performance ratio approaches 1as the number of objects increases.A problem is said to be MAX-SNP-hard (Papadimitriou and Yannakakis 1991),abbreviated MAX-SNP in the table,if there is a constant c >1such that it is impossible to approximate the problem with performance ratio smaller than c unless P =NP .
In the sequel,we consider the ?ve problems in the order listed in Figure 1.Approximation algorithms and hardness results for the underlying deterministic versions of each of these problems are surveyed,and the algorithms for the stochastic versions are presented.
3Shortest paths
Motivation
Consider a supplier who wishes to ship a single unit of a good to a single destination t from a single source s ,in a graph where the shipping cost is just the cost of the edge.The solution to this problem is to compute a shortest path from s to t ,and this can be easily done in polynomial time,for example by using the algorithm due to Dijkstra (1959).
Now consider the following stochastic extension.The supplier does not know in advance what the destination is going to be.In particular,any of m scenarios could materialize,with the destination being t k in scenario k .The supplier could enter into contracts in stage 1to ship the good along edge e at cost c e ,but this might be disadvantageous if the destination turns out to be in the opposite direction.However,if the supplier decides to wait for the scenarios to materialize,then the cost of edge e in scenario k changes to f k c e ,which could be disadvantageous if f k is large.Hence the supplier might wish to reserve some edges now at cost c e ,and augment the network in scenario k if necessary.
Problem de?nition We are given a graph G =(V,E ),with metric edge costs c e and a single source s ∈V .We also have a set of m scenarios,with scenario k speci?ed by a destination vertex t k ∈V ,a cost scale factor f k ,and a probability p k .A feasible solution is speci?ed by a set of edges E ?E .The ?rst-stage cost of this solution is e ∈E c e ,and in scenario k ,a second stage solution is a path P k from s to t k ;for
the second stage costs,we assume the edges in P k bought in the ?rst stage,namely in E ,have cost zero,while the remaining edges are increased in cost by factor f k ,giving second-stage cost f k e ∈P k \E c e .The objective is to compute E which minimizes the sum of ?rst stage edge costs and expected second stage edge costs.We abbreviate this problem as SSP (stochastic shortest paths).
While it is not obvious that E even induces a connected component,the following lemma proves that E is indeed connected;in fact,it is a tree.
Lemma 1The set of edges E bought in the ?rst stage in an optimal solution to SSP induces a tree containing the source s .
Proof:Suppose for a contradiction there is another connected component C s .Let K be the set of scenarios for which the optimal solution uses at least one edge in C ,and let E s be the connected component of ?rst-stage edges which include the source s .For optimality,it must be the case that for every edge e ∈C ,we have P k e p k f k ≥1,implying that k ∈K f k ≥1.
Now consider the paths used in the scenarios in K .Let k 0be the scenario in which the second-stage cost of the segment from C to the source is the cheapest.If we re-route the paths of all scenarios in K to using the path to using the path of k 0from the point the other scenario paths intersect C ,then since k ∈K f k ≥1,the total cost cannot increase.Therefore,we can purchase these edges (which we used for re-routing),and this does not increase the cost.
Proceeding this way for other components,we infer that E ?induces a connected graph containing s ,which need be no more than a tree since the second stage solutions only look for a single path to s .
2Interpretation as a network design problem Armed with the above lemma,SSP can be interpreted as the tree-star network design problem,de?ned as follows.In tree-star network design,demand nodes have a demand for d j units of goods to be shipped to a source.A feasible solution is speci?ed by a tree,with the cost of the solution being M times the cost of the tree (for pre-speci?ed M )plus the length of the shortest path from each demand node to the tree,weighted by the demand at the node.A constant-factor approximation algorithm for this problem was ?rst provided by Ravi and Salman (1999),and it has also been studied subsequently as the connected facility location problem (Karger and Minko?,2000;Kumar and Swamy,2002),and the asymmetric VPN design problem (Gupta et al,2001).
Theorem 1There is a polynomial-time constant-factor approximation algorithm for SSP.
Proof:SSP is equivalent to the tree-star network design problem,via the following transformation.The ?xed cost multiplier of the tree M is set to 1.The demand of each node t k is set to f k p k .Now purchasing a tree T in stage 1for SSP is equivalent to building T in the tree-star problem.The expected second stage cost is exactly m k =1p k f k dist(t k ,T ),which is the same as incurred in the tree-star problem when the demand at node t k is p k f k .2The equivalence of SSP and tree-star network design also implies the NP-hardness of SSP.Note that SSP is di?erent from the maybecast problem studied by Karger and Minko?(2000),because in their model,each node is a terminal independently with a certain probability,edge costs do not change across scenarios,and the solution is required to be a single tree spanning all potential terminals.
3.1Stochastic metric
The problem becomes even more interesting(and harder)when the metric itself is allowed to change arbitrarily across scenarios.This might happen,for example,because shipping by sea becomes much cheaper than air transport in one scenario,and vice-versa in another.The problem is de?ned exactly as in Section3,except that the cost of edge e in the?rst stage is c0e and in scenario k is c k e.We call this the stochastic metric shortest paths(SMSP)problem.
In general,the?rst-stage component of an optimal solution for SMSP need not be a tree.Consider the following example,where there is only one second-stage scenario.The graph is a path with?ve vertices s=v0,...,v4=t,where s and t are the source and the sink respectively.Let M be a large constant.The costs of the four edges(v0,v1),...,(v3,v4)in the?rst stage are respectively1,M,1,M,and in the second stage are M,1,M,1.The optimal solution is clearly to purchase edges(v0,v1)and(v2,v3)in the?rst stage, and the others in the second stage;this solution has cost4.Any solution which requires the?rst stage to be a tree has cost at least M.
Hardness Even with the restriction that the?rst stage set of edges form a tree,SMSP is as hard as the group Steiner tree problem(GST),de?ned as follows.G=(V,E)is an undirected graph with edge weights c e,and there are m vertex subsets(called groups)S k.The objective is to compute a minimum cost tree which includes at least one vertex from every group.This problem was studied by Garg,Konjevod and Ravi(2000)who also gave an approximation algorithm with performance ratio roughly O(log2n log m), and recently Halperin and Krauthgamer(2003)showed an inapproximability threshold of?(log2n)even when G is a tree.For the rest of this section,we consider the restriction of SMSP where the?rst stage solution has to be a tree,which we dub Tree-SMSP.An?(log2n)hardness for Tree-SMSP follows from the reduction of GST to Tree-SMSP,shown below.
Theorem2An instance of GST can be modeled as a special case of Tree-SMSP.
Proof:Suppose we are given an instance of group Steiner tree,speci?ed by G=(V,E),metric edge costs c,and groups S1,S2,...,S m.We create an instance of SMSP with one scenario for every group.The graph remains the same,and the?rst stage edge costs c0are the same as c,the edge costs in the GST instance. In scenario k,the metric is as follows.The distance between any two vertices in S k is zero,and all other distances are in?nity.Any vertex in S k is de?ned to be the destination t k for scenario k.All scenarios are equally likely.
An optimal solution to this instance of Tree-SMSP must select a?rst stage tree which includes at least one vertex from each S k,to avoid in?nite cost.If the tree includes any vertex in S k,it can be augmented at cost zero to a tree which includes t k if scenario k materializes.2
Approximation algorithm Our approximation algorithm relies on the following IP formulation of Tree-SMSP.Variable r k uv is1if edge(u,v)(in the direction u→v)is part of the path traversed from t k to s and edge(u,v)is chosen in the recourse solution.Variable f k uv is1if edge(u,v)is chosen in the path from t k to s and edge(u,v)is part of the?rst-stage solution.Variable x uv is1if edge(u,v)is chosen in the ?rst-stage tree.
min
e c e x e +m k =1p k e r k e c k e (IP SMSP )
s.t. v (r k t k ,v +f k t k ,v )≥1?k
v (r k uv +f k uv )= v (r k vu +f k vu )?u ∈V \{t k ,s },?k
v r k uv ≤ v
r k vu ?u ∈V \{t k },?k
f k e ≤x e
?e ∈E,?k f,r,x non-neg.integers The third set of inequalities are strengthenings valid only for the tree version of SMSP,insisting that ?ows along recourse arcs from t k to s via any node are non-increasing;they are also crucial for obtaining the result below.IP SMSP is polynomial in size,so its linear relaxation LP SMSP can be solved optimally in polynomial time.Let (f,r,x )denote an optimal solution to the linear program LP SMSP ,and OP T SMSP be its value.The following theorem describes our rounding algorithm.
Theorem 3The fractional solution (f,r,x )can be rounded in polynomial time to an integer solution (?f,?r ,?x )of cost O (log 2n log m )OP T T ree ?SMSP .
Proof:For each destination t k ,let r ?(k )= e r k e c k e be the cost incurred by the recourse component of the fractional path for t k .Let S k be the set of all nodes within distance 2r ?(k )of t k in the metric c k .The idea is that we can incur a factor of 2and pay for a path from t k to any node in S k by charging it to r ?(k ),and hence we need a ?rst stage tree which reaches at least one node in S k .We construct sets S k for every scenario k ,and create an instance of the group Steiner tree problem using the metric c .Using Markov’s inequality,it can be shown that if s /∈S k ,then we have e =(u,v ):u ∈S k ,v /∈S k x e ≥1
2.
Hence 2x is a fractional solution to the linear relaxation of the following IP formulation of the group Steiner tree problem:min e c e x e such that e =(u,v ):u ∈S,v /∈S x e ≥1?S ?k :
S k ?S .Using the result of Garg,Konjevod and Ravi (2000),we can construct an integer solution ?x at a cost which is no more than O (log 2n log m ·OP T SMSP )which is a tree and includes at least one vertex of every S k .Since for every scenario k we can augment this tree to include t k at cost no more than 2r ?(k ),our approximation ratio follows.24Bin packing
Problem de?nition and algorithm
Stochastic bin packing is motivated by applications where storage capacity has to be reserved in advance of the arrival of the objects,and if the reserved capacity is insu?cient,we have to purchase additional capacity at possibly higher costs.Formally,we are given a bin capacity B ,known in advance.There is a set of m possible scenarios,with scenario k speci?ed by a probability p k of occurrence,a set S k of objects (each with size s k i ≤B ),and a bin cost f k .A feasible solution is speci?ed by a number x of bins purchased in stage 1,at unit cost per bin.If scenario k materializes,the objects in S k need to be packed into bins of capacity B ,which may necessitate the purchase of an additional number
of bins at cost f k per bin.The objective is to compute x so as to minimize the expected total cost.Let [x ]denote the integer nearest to x .
Let ρdenote the approximation ratio of some (the best)approximation algorithm for the bin-packing problem.Any locally optimal algorithm (?rst-?t,for example)achieves ρ=2.An asymptotic PTAS was given by Fernandez de la Vega and Lueker (1981),which uses at most (1+2 )OP T +1bins.The following theorem shows how to extend any bin-packing algorithm to handle stochastic bin-packing.
Theorem 4Order the scenarios so that we have i s 1i ≥ i s 2i ≥...≥ i s m i .Let k ?be the largest integer such that k ?k =1f k p k ≥1.Then x =[ρ i s k ?i ]is an asymptotic ρ-approximate solution.
Proof:Consider the fractional relaxation of the problem,when we can pack items fractionally into bins.In that case,x ?=[ i s k ?i ]is the optimal solution,because it is the point where the expected marginal cost of buying an additional bin in recourse goes below 1.The expected total cost if we purchase x ?bins is x ?+ k>k ?p k f k ( i s k i ?x ?),which is a lower bound on the value of an optimal solution of stochastic bin packing.Since ρ i s k i bins are asymptotically su?cient to pack the objects in S k ,we will need to purchase at most ρ i s k i ?ρx ?additional bins if scenario k >k ?materializes.If scenario k ≤k ?is realized,then ρx ?bins are su?cient and no additional bins are needed.Hence the expected cost of our solution is ρx ?+ k>k ?p k f k ( ρ i s k i ?ρx ?),which is asymptotically no more than ρtimes our lower bound.25
Facility location 5.1De?nition
As in the classical uncapacitated facility location problem,we are given a set of facilities F and a set of clients D ,with a metric c ij specifying the distances between every client and every facility.However,the demand of each client is not known at the ?rst stage.In scenario k ,client j has demand d k j ,which may be zero.Facility i has a ?rst-stage opening cost of f 0i ,and recourse costs of f k i in scenario k .These may be in?nity,re?ecting the unavailability of the facilities in various scenarios.We abbreviate this problem as SFL.
min
i ∈F f i y 0i +m k =1
p k i ∈F f k i y k i + i ∈F,j ∈D d k j c ij x k ij (IP SF L )
s.t. i ∈F x k ij
≥d k j ?j ∈D,?k
x k ij ≤y 0i +y k i ?i ∈F,?j ∈D,?k x,y non-negative integers
The problem is best explained by the integer program formulation IP SF L above.While our algorithms extend to arbitrary demands at every client,for simplicity we only study the case when all d k j ’s are either
0or 1.Variable x k ij is 1if and only if client j is served by facility i in scenario k .If x k ij =1,then facility i
must either be opened at the ?rst stage (y 0i =1)or in recourse in scenario k (y k i =1)(or both).
5.2History and non-triviality of the problem
The classical(deterministic)uncapacitated facility location problem has a rich history(see Cornu′e jols, Nemhauser and Wolsey,1990for a survey).Balinski(1966)introduced an integer programming formulation for this problem which has led to several approximation algorithms.The?rst constant factor approximation using this formulation is due to Shmoys,Tardos and Aardal(1997),and the current best algorithm,due to Mahdian,Ye and Zhang(2002)uses a formulation which di?ers only slightly.Indeed,our formulation (IP SF L)extends Balinski’s formulation to the stochastic setting.In the stochastic optimization community, Louveaux and Peeters(1992)considered a slightly di?erent version of stochastic facility location,and provided a dual-ascent based exact(non-polynomial time)algorithm for it.
There are several preliminary insights which one can obtain by examining our formulation of stochastic facility location closely.First notice that if the second stage facility costs were identical to those in the?rst stage for all scenarios,then we can“de-couple”the stochastic components of the problem and solve for each scenario independently.On the other hand,if there was no second stage and all facilities had to be opened in the?rst stage,then SFL reduces to an instance of the usual UFL,where the probability multipliers in the expected service costs can be incorporated into the demand terms(thinking of the demands as being scaled based on the probability of occurrence).This also extends to allowing arbitrary demand distributions at the vertices,if they are independent.In this case,existing approximations for UFL apply directly.The added di?culty,and indeed the interesting aspect of the model,arises from varying(and typically increased) second-stage facility costs under di?erent scenarios.
In the other direction,SFL can be viewed as a special case of the multicommodity facility location problem(MCFL),where we treat each scenario as a distinct commodity and the cost of a facility depends on the commodities it serves.However,the best-known approximation ratio for MCFL is O(log m)due to Ravi and Sinha(2003),(where m is the number of scenarios),so we need di?erent techniques for better approximations of SFL.
The main di?culty stems from the fact that we cannot treat each scenario by itself,since the di?erent scenarios interact in utilizing?rst-stage facilities.A simple heuristic is to compare the solution obtained if all the demand is satis?ed in the?rst stage with the solution when no?rst stage facilities are opened. While this heuristic works well in certain instances(particularly,maximization problems such as maximum weight matchings,as in Kong and Schaefer,2003),it can easily be shown to perform badly in our case,due to the interaction across scenarios.
5.3Algorithm
Our approximation algorithm proceeds along the lines of the LP-rounding algorithm due to Shmoys,Tardos and Aardal(1997),with some crucial di?erences.We begin by solving the linear relaxation of IP SF L.Let (x,y)denote an optimal LP solution.The?rst step in rounding this fractional solution is using the?ltering technique of Lin and Vitter(1992).We?x a constant0<α<1.For every client-scenario pair(j,k),we
de?ne its optimal fractional service cost to be c?
jk =
i
c ij x k ij.Order the facilities which serve the pair
(j,k)according to non-decreasing distance from j.Theαpoint g j,k(α)for the client-scenario pair(j,k)is
the smallest distance cα
jk such that
i:c ij≤cα
jk
x k ij≥α.
Theorem 5Given a feasible fractional solution (x,y ),we can ?nd a fractional solution (x,y )which is feasible for the LP relaxation of IP SF L in polynomial time such that (i)c αjk ≤11?αc ?jk ;(ii)x k ij >0?c ij ≤c αjk for all i ∈F ,
j ∈D ,k =1,2,...,m ;(iii)y k i ≤min {1,y k i α}for all i ∈F ,k =0,1,...,m .Proof:First,if c αjk >11?αc ?jk ,then we get the following
contradiction (as an application of Markov’s
inequality):c ?jk ≥α.0+(1?α)c αjk >c ?jk ,proving (i).Next,de?ne x as follows,which satis?es (ii)by de?nition:
x k ij = min {1,1α}x k ij if c ij ≤c αjk 0otherwise
Furthermore,de?ne y k i =min j ∈D x k ij .Using (i)and the de?nition of x ,it follows that y k i ≤min {1,y k i α}
for all i ∈F ,satisfying (iii).
The de?nitions also ensure that (x,y )is a feasible solution to the LP relaxation of IP SF L .2The algorithm in Shmoys,Tardos and Aardal (1997)proceeds to iteratively round x k ij variables for which c αjk is smallest.However,this does not work in our case,because the rounding algorithm might close facilities which are needed for other scenarios k =k .Hence we need a rounding algorithm which carefully treats the distinction between stage 1facility variables y 0,and recourse facility variables y k .
We proceed as in earlier algorithms by obtaining an optimal LP solution;In the next step,we progres-sively choose clients across all scenarios with minimum fractional service cost,and neglect to serve other clients con?icting (overlapping in facility utilization)with it by assigning them to be served by this client’s serving facility.However,this will not work if the serving facility is not open in this neglected client’s scenario.Hence,the main di?erence is that if a stage 1facility is opened to serve a client,all clients that con?ict with it can be served,while if a stage 2facility variable is rounded up to serve this client,only those clients in the same scenario that con?ict with this client are neglected and assigned to this client.This strategy su?ces to pay for all opened facilities by the “disjointness”of the di?erent scenarios’contributions in the objective function,while the rule of considering clients in increasing order of fractional service cost allows us to bound the service cost.Our rounding algorithm is described in detail below.Let 0<β<1be another ?xed constant.
1.Initialize ?F
k =?to be the set of facilities opened in scenario k for k =0,1,...,m .Mark all client-scenario pairs as “unserved”.
2.Let (j,k )be an unserved client-scenario pair with smallest c αjk .Consider the following cases,in each case marking (j,k )as “served”and proceeding to the next client-scenario pair.Let S 0be the set of
facilities i such that x k ij >0∧y 0i >0,and S k be the set of facilities i such that x k ij >0∧y k i >0.
(a)If i ∈S 0
y 0i ≥β,let i be the facility such that f 0i is smallest among all facilities in S 0.Move
facility i to the set ?F 0,and set ?y 0i =1.For all other facilities i ∈S 0∪S k ,set ?y 0i =?y k i =0.For client-scenario pairs (j ,k )such that there exists a facility i ∈S 0∪S k with c i j ≤c αj k ,set ?x k ij =1and mark them as “served”.
(b)If i :i ∈S 0y 0i <β,then we must have i :c ij ≤c αjk
y k i ≥1?β.In this case,let i be the facility in S k with smallest f k i .Move facility i to the set ?F k and set ?y k i =1.For all other facilities i ∈S k ,
set ?y k i =0.For clients j such that there exists a facility i ∈S k with c i j ≤c αj k ,set ?x
k ij =1and mark them as “served”.
3.Facilities in ?F
0are the facilities to be opened in stage 1,and facilities in ?F k are the facilities to be opened in recourse if scenario k materializes.Clients are served according to the zero-one variables ?x k ij .
Lemma 2The rounding algorithm above produces an integer solution (?x ,?y )which is feasible for IP SF L such that
(i)For every client-scenario pair (j,k ),we have ?x k ij =1?c ij ≤3c αjk .(ii) i ∈F f 0i ?y 0i ≤1β i ∈F f 0i y 0i .(iii) i ∈F f k i ?y k i ≤11?β
i ∈F f k i y k i for all k =1,2,...,m .Proof:When a client is assigned to a facility (ie,?x k ij is set to 1),we either assign it to a facility within
distance c αjk ,or it is assigned when some other client j with c αj k ≤c αjk was being considered.In either case,
a simple application of triangle inequality yields c ij ≤3c αjk .
When a facility i is chosen for opening in the ?rst stage (ie,?y 0i is set to 1),case 2(a)must have occurred.
In that case,we have a su?ciently large fraction (β)of facilities which have y 0i >0which we are shutting,and we can charge the cost of opening i to the fractional solution.A similar argument holds for the case when a facility is opened in recourse in scenario k .
The solution produced is also feasible,because we start with a feasible solution (x,y ),and in each step,we maintain feasibility by ensuring that a client-scenario pair is marked “served”only when its x k ij variable is set to 1(ie,it is assigned to a facility)for some facility i .
2Theorem 6There is a polynomial time approximation algorithm with performance ratio 8for SFL.Proof:Setting α=1
4and β=1
2,along with Theorem 5and Lemma 2,yields the performance guarantee.
The running time of the algorithm is polynomial in |D |,|F |,m .
2Extensions The algorithm easily extends to allowing demands at client-scenario pairs which are non-negative real numbers instead of just 0or 1.We may also allow the costs to transport one unit of demand per unit length in di?erent scenarios to be di?erent,motivated by,e.g.,di?erent scenarios having di?erent prices of gas.In other words,each scenario has a multiplier γk such that the distance between i and j in scenario k is γk c ij .Essentially,this can be incorporated into the demand variables d k j ,and the rest of the algorithm proceeds as before to give identical results.
6Vertex cover
Problem de?nition
We are given a ?rst-stage (undirected)graph G =(V,E 0).As usual,there are m possible scenarios,each consisting of a probability of occurrence p k and a set of edges E k ,which may not necessarily be subsets of the ?rst-stage edge set E 0.The ?rst-stage cost of vertex v is c 0v ,and its cost in scenario k is c k v .The objective is to identify a set of vertices to be selected in the ?rst stage,so that the
expected cost of extending this set to a vertex cover of the edges of the realized second-stage scenario is minimized.
In the problem as de?ned above,edges in E k\E0have to be covered in the second stage,even if one of their end-points was chosen in the?rst stage.This is a generalization of the case when?rst-stage vertices cover all second-stage edges incident to them.We provide a2approximation for this generalized stochastic vertex cover problem.
The best known approximation algorithm for the deterministic version of vertex cover has performance ratio2?log log|V|
2log|V|
,due to Monien and Speckenmeyer(1985).A lower bound of1.16on the hardness of approximating the problem was shown by H?astad(1997).Our approximation ratio of2for the generalized stochastic version of vertex cover asymptotically matches the best known approximation for the deterministic version.
Integer program formulation Our algorithm is a primal-dual algorithm which rounds the natural IP formulation of stochastic vertex cover.Variable x k v indicates whether or not vertex v is purchased in scenario k(where k=0as usual denotes the?rst stage).Edges in E k∩E0may be covered in either the?rst or second stage,while edges in E k\E0must be covered in the second stage.
min c0x0+ m
k=1
p k c k x k(IP SV C)
s.t.x0u+x0v+x k u+x k v≥1?uv∈E k∩E0,?k
x k u+x k v≥1?uv∈E k\E0,?k
x non-neg.integers
Dual program The dual of the linear relaxation of IP SV C is shown below.Variable y k e packs edge e in E k if e∈E k,and it packs e∈E0if e∈E k∩E0.
max
m
k=1
u,v∈V
y k uv(DP SV C)
s.t.
e∈E k:v∈e y k e≤p k c k v?v,?k
m k=1
e∈E0∩E k:v∈e
y k e≤c0v?v
y≥0
Algorithm The algorithm is a greedy dual-ascent type of primal-dual algorithm,with two phases.In Phase I,we raise the dual variables y k e uniformly for all edges in E k\E0,separately for each k.All vertices which become tight(have the?rst dual constraint packed to p k c k v)have x k v set to1,and deleted along with adjacent edges.We proceed this way until all edges in E k\E0are covered and deleted.
In Phase II,we do a greedy dual-ascent on all uncovered edges of E k.These edges are contained in E k∩E0.This time around,we use a slightly di?erent rule for purchasing vertices.If a vertex is tight for x0v(i.e.,second dual constraint packed to c0v),then we select it in the stage1solution by setting x0v=1, and if it is not tight for x0but is tight for x k(packed in the?rst dual constraint),then we select it in the recourse solution and set x k v=1.
Theorem7The integer program IP SV C can be rounded by the primal-dual algorithm described above within a factor of2in polynomial time.
Proof:We analyze the performance of the algorithm described above.Consider an edge e =uv in scenario k .By de?nition of the algorithm,we must have selected one of its two end-points in either Phase I or Phase II (or both),so that the algorithm yields a feasible solution.We use linear programming duality to bound the cost of the solution by showing that the cost of our solution is no more than 2 k u,v ∈V y k uv ,where y is the dual solution constructed by our algorithm.
We show the performance ratio of our algorithm as follows.Each time we set an x k v variable to 1,we assign some dual variables to it such that (i)the sum of dual variables assigned to each such x k v variable equals p k c k (where p 0=1),and (ii)each dual variable is assigned at most twice.
Consider a vertex v which was selected (ie,x k v was set to 1)in scenario k in either Phase I or Phase II.
We assign all dual variables y k e such that v is an end point of e to this vertex,and since v is selected only when the constraint e ∈E k :v ∈e y k e ≤p k c k v goes tight,we maintain (i).An edge e in E k \E 0is assigned to a
vertex v only if x k v is set to 1for k =0,and since an edge has at most 2end-points,we ensure (ii)for edges in E k .
Next consider a vertex v for which we set x 0v to 1.For this to happen,the constraint l e ∈E 0∩E k :v ∈e
y k e ≤c 0v must have gone tight,and all edges in the sum are assigned to the variable x 0v .This assignment once
again ensures (i).This assignment only includes edges in E 0∩E k ,and these edges are not assigned to any variable x k v for k =0,thus also ensuring (ii)for all edges in E 0∩E k .
These two cases cover all the possibilities,thus proving the theorem.27Set cover
Problem de?nition
The input in the stochastic set cover problem consists of a universe U of |U |=n elements,and a collection S of subsets of U .Each set S ∈S has a stage 1cost c 0S and a cost of c k S in
scenario k ,some of which might be in?nity re?ecting the unavailability of the set in certain scenarios.Each element u ∈U has a demand vector d u with the k th component d k u being 1if it is required to cover u in scenario k ,and 0otherwise.A feasible solution is speci?ed by a collection S ?S ,with stage 1cost S ∈S c 0S .If scenario k is realized,then S must be extended by purchasing some more sets S k to cover all elements with d k u =1.The cost of this recourse solution is S ∈S k c k S ,and we incur this with probability p k .The objective is a solution which minimizes the sum of ?rst stage and expected second stage costs.Reduction to classical set cover
The deterministic version of set cover was among the earliest NP-hard problems to be approximated,with a O (log n )approximation was ?rst provided by Johnson (1974).The problem was also shown to be NP-hard to approximate better than a factor of ?(log n )by Arora and Sudan (1997).
Given an instance of deterministic set cover,we can de?ne an instance of stochastic set cover by creating a distinct scenario for each element,and setting all second-stage set costs to in?nity.This implies an inapproximability threshold of ?(log m )for stochastic set cover too.
We show below that any instance of stochastic set cover with n elements can be transformed to an instance of deterministic set cover with n (m +1)elements.This means that there exists an O (log nm )=O (log n +log m )approximation for stochastic set cover by using this transformation and then applying
any approximation algorithm for deterministic set cover.The approximation ratio therefore matches the inapproximability ratio upto constants.The reduction in Theorem8allows us to extend the model to the following generalization,for which the same approximation guarantee holds:In scenario k,each set S k covers only a subset of the elements that the?rst-stage set S covers.
Theorem8Any stochastic set cover problem is equivalent to a classical set cover problem with mn elements and|S|(m+1)sets.
Proof:Associate an element u k for every element-scenario pair(u,k)such that d k u=1.Create m+1 copies of every set S∈S.Set S0contains all elements u k for all k=1,2,...,m such that u∈S,while set
S k only contains u k for all u∈S.Finally,the cost of S0is c0
S and that of S k is p k c k
S
.
By construction,any solution to the stochastic set cover instance yields a solution to the transformed deterministic instance,and vice-versa.This proves the equivalence.2
8Directions for further research
Much work remains to be done on several classical combinatorial optimization problems for which algorithms in the two-stage stochastic model are not known.
Another direction of research is to develop approximation algorithms for more complex models of stochas-tic optimization:The extension of the two-stage model to multiple stages allows more detailed modeling; the variant where uncertainty is modeled by a continuous distribution is also often considered.
It is our hope that these models will provide a rich setting for the application of optimization in practice.
9Acknowledgments
We gratefully thank Andrew Schaefer and Nan Kong of the University of Pittsburgh for introducing us to the topic of this research via Schaefer and Wong(2003).
References
[1]S.Arora and M.Sudan.Improved low degree testing and its applications.In Proceedings of the29th
Annual ACM Symposium on Theory of Computing,485-495,1997.
[2]G.Ausiello,P.Crescenzi,G.Gambosi,V.Kann, A.Marchetti-Spaccamela and https://www.wendangku.net/doc/5216649773.html,-
plexity and Approximation:Combinatorial Optimization Problems and their Approximability Properties, Springer,Berlin,Germany,1999.
[3]M.L.Balinski.On?nding integer solutions to linear programs.In Proc.IBM Scienti?c Computing
Symposium on Combinatorial Problems,225-248,1966.
[4]J.Birge and F.Louveaux.Introduction to Stochastic Programming,Springer,Berlin,1997.
[5]A.Borodin and R.El-Yaniv.Online computation and competitive analysis,Cambridge,1998.
[6]H-F.Chen.Stochastic Approximation and its Application,Kluwer,Dordrecht,2002.
[7]E.Co?man Jr.,M.Garey and D.Johnson.Approximation algorithms for bin-packing:a survey.In D.S.
Hochbaum,Approximation Algorithms for NP-hard Problems,PWS,Boston,1997.
[8]G.Cornu′e jols,G.Nemhauser and L.Wolsey.The uncapacitated facility location problem.In P.Mir-
chandani and R.Francis,eds,Discrete Location Theory,119-171,Wiley,New York,1990.
[9]E.Dijkstra.A note on two problems in connexion with graphs.Numerische Mathematik1:269-271,1959.
[10]W.Fernandez de la Vega and G.S.Lueker.Bin packing can be solved within1+ in linear time.
Combinatorica1:349-355,1981.
[11]N.Garg,G.Konjevod and R.Ravi.A polylogarithmic approximation algorithm for the group Steiner
tree problem.Journal of Algorithms37(1):66-84,2000.
[12]S.Guha and S.Khuller.Greedy strikes back:Improved facility location algorithms.In Proceedings of
the9th ACM-SIAM Symposium on Discrete Algorithms,649-657,1998.
[13]A.Gupta,J.Kleinberg,A.Kumar,R.Rastogi and B.Yener.Provisioning a virtual private network:
A network design problem for multicommodity?ow.In Proceedings of the33rd Annual ACM Symposium
on Theory of Computing,389-398,2001.
[14]E.Halperin and R.Krauthgamer.Polylogarithmic inapproximability.In Proceedings of the35rd Annual
ACM Symposium on Theory of Computing,585-594,2003.
[15]J.H?astad.Some optimal inapproximability results.In Proceedings of the29th Annual ACM Symposium
on Theory of Computing,1-10,1997.
[16]H.Heitsch and W.R¨o misch.Scenario reduction algorithms in stochastic https://www.wendangku.net/doc/5216649773.html,putational
Optimization and Applications24:187-206,2003.
[17]D.Johnson.Approximation algorithms for combinatorial problems.Journal of Computer and System
Sciences9:256-278,1974.
[18]P.Kall and S.Wallace.Stochastic Programming,Wiley,Chichester,England,1994.
[19]B.Kalyanasundaram and K.Pruhs.Speed is as powerful as clairvoyance.Journal of the ACM47(4):617-
643,2000.
[20]D.Karger and M.Minko?.Building Steiner trees with incomplete global knowledge.In Proceedings of
the41st Annual IEEE Symposium on Foundations of Computer Science,613-623,2000.
[21]W.K.Klein Haneveld and M.H.van der Vlerk.Stochastic Programming,Dept.of Econometrics and
OR,University of Groningen,Netherlands,2003.
[22]N.Kong and A.Schaefer.A factor1
approximation algorithm for a class of two-stage stochastic
2
mixed-integer programs.Manuscript,submitted to INFORMS Journal of Computing,2003.
[23]A.Kumar and C.Swamy.Primal-dual algorithms for connected facility location problems.In Approx-
imation Algorithms for Combinatorial Optimization,256-270,2002.
[24]J-H.Lin and J.Vitter. -approximations with minimum packing constraint violation.In Proceedings
of the24th Annual ACM Symposium on Theory of Computing,771-782,1992.
[25]F.Louveaux and D.Peeters.A dual-based procedure for stochastic facility location.Operations Re-
search40:564-573,1992.
[26]M.Mahdian,Y.Ye and J.Zhang.A1.52approximation algorithm for the uncapacitated facility location
problem.In Approximation Algorithms for Combinatorial Optimization,229-242,2002.
[27]R.M¨o hring,A.Schulz and M.Uetz.Approximation in stochastic scheduling:The power of LP-based
priority policies.Journal of the ACM46(6):924-942,1999.
[28]B.Monien and E.Speckenmeyer.Ramsey numbers and an approximation algorithm for the vertex
cover problem.Acta Informatica22:115-123,1985.
[29]N.Nisan and A.Ronen.Algorithmic mechanism design.In Proceedings of the31st Annual ACM Sym-
posium on Theory of Computing,129-140,1999.
[30]C.H.Papadimitriou and M.Yannakakis.Optimization,approximation,and complexity classes.Journal
of Computer Systems and Sciences43:425-440,1991.
[31]R.Ravi and F.S.Salman.Approximation algorithms for the traveling purchaser problem and its variants
in network design.In European Symposium on Algorithms,29-40,1999.
[32]R.Ravi and A.Sinha.Multicommodity facility location.GSIA working paper#2003-#67,Carnegie
Mellon University,Pittsburgh,2003.
[33]R.Schultz,L.Stougie and M.H.van der Vlerk.Two-stage stochastic integer programming:A survey.
Statist.Nederlandica50(3):404-416,1996.
[34]D.Shmoys,E.Tardos and K.Aardal.Approximation algorithms for facility location problems.In
Proceedings of the29th ACM Symposium on Theory of Computing,265-274,1997.
[35]M.Skutella and M.Uetz.Scheduling precedence-constrained jobs with stochastic processing times on
parallel machines.In Proceedings of the12th Annual ACM-SIAM Symposium on Discrete Algorithms, 589-590,2001.
[36]L.Stougie.Design and analysis of algorithms for stochastic integer programming.CWI Tract Vol.37,
CWI,Amsterdam,1987.
[37]V.Vazirani.Approximation Algorithms,Springer,Berlin,Germany,2001.
非语言交际的功能与作用
非语言交际的功能与作用 非语言交际可能被认为是不直接依赖于语言使用的一种交流方式，总体来说，在哪个地方区分分开的语言和非语言交流形式是很难的。我们所需要做的是简单地认识到人类互动的许多方面取决于不能用语言所表达的交流形式，但这对我们相互理解是非常重要的。当然我们必须强调在说话和在文字表达的交流的重要性。我们应该知道许多交流不需要语言也能相互交流。一个人在会议上所穿的衣服可能对其他参与者暗示着他对这次会议是有多么认真地准备。实际上，我们可以利用别人认为是一种交流方式的行为或者是表现的任何方面。 非语言交际指除了语言之外的所有交际手段，包括肢体语言，服饰如制服，发型，化妆，等等。拿身势语举例：“身势语”同语言一样，都是文化的一部分。在不同文化中，身势语的意义并不完全相同。各民族有不同的非语言交际方式。 首先，来看看各国的文化差异。 阿拉伯人经常以亲吻脸颊的方式来进行问候。在日本，人们以弯腰来表达问候，在美国，人们会进行握手。在泰国，为了表示另外一个人靠近，人们往往会前后移动手指，手掌向下。在美国，人们为了吸引别人过来，往往举起手掌，对别人移动着手指。汤加人坐下来来表达对长辈的尊敬；而在西方，往往站着。在美国双腿交叉经常是表示轻松的方式；而在韩国，这是社会所忌讳的。在日本，礼物常常用双手交换。穆斯林认为左手不干净，不能用它来吃东西或者是交换物品。佛陀主张沉默是金。而在美国，人们通过谈话来真正表达自己的观点。 无论是有意识还是无意识，无论是有目的还是无意，我们都会关于别人的内心想法做出重要的判断和决定---那些他们不能用语言表达的想法。例如，我们可以根据这些非语言信息所表达的意思来评价人际交往的质量高低。在我们和同伴之间从语调到距离再到我们所参与的彼此接触的次数，我们就能收集和同伴间的亲密程度的信号。非语言交际是那么地细微以至于身体区域的一次小移动也能传达一种信息。你的第一次和同伴握手到触碰他（她）的脸颊，你在传达一种信息，如果你的触碰得到回应，那么这种信息就表现得极为重要。 非语言交际也很重要，因为我们会利用他们的行为来分析他们的情感或精神特征。如果我们见到一些人紧握拳头，表情严肃，不用说就知道这个人很不高兴。如果我们听到某个人的声音在颤抖，看见他(她)的手在颤抖，无论他（她）说什么，我们可以推测这个人很害怕或者充满好奇。我们的情感在我们的姿态，脸部，眼神中能反映出来，像害怕，高兴，生气，或者是伤心---所以不用一个字我们就可以全盘托出。正因为如此，我们很多人很大程度上都依赖于通过我们的眼睛所学到的东西。实际上，研究表明当语言信息和非语言信息相矛盾时，我们更愿意相信非语言信息而不是语言信息。 非语言交际在人类互动过程中表现的很重要，因为它经常要对第一印象负责。思考一下你的第一判断是多久一次的时间建立在一个人皮肤的颜色或者是穿戴方式上的。更重要的是，那些初级信息往往影响对于其他一切有关的东西的看法。甚至连我们怎么选择朋友和伙伴也是建立在第一印象上。我们经常因为别人对自己的吸引力而靠近某些人。 非言语交际对人类互动很重要因为我们许多非言语行为不能很有意识地控制住。这意味着它们有些是相对地具有歪曲性和欺骗性。当我们为难时，很难控制红色的脸。当我们生气时，我们同样很难控制紧下巴。 在交流中，我们的非言语交际有许多功能和用途。 重复的功能 一个非言语信息能重复一个言语信息。人们经常使用非语言信息来重复他们努力想表达的观点。我们会做出一只手顶住另一只手的姿势来强调一个人应该暂停，此时此刻我们实际上可以说“暂停”。或者我们在说完“新的图书馆在这幢楼南面”，我们会用手指向某个特定
电力电子技术答案第五版(全)
电子电力课后习题答案 第一章电力电子器件 1.1 使晶闸管导通的条件是什么？ 答：使晶闸管导通的条件是：晶闸管承受正相阳极电压，并在门极施加触发电流（脉冲）。 或者U AK >0且U GK >0 1.2 维持晶闸管导通的条件是什么？怎样才能使晶闸管由导通变为关断？ 答：维持晶闸管导通的条件是使晶闸管的电流大于能保持晶闸管导通的最小电流，即维持电流。 1.3 图1－43中阴影部分为晶闸管处于通态区间的电流波形，各波形的电流最大值均为 I m ，试计算各波形的电流平均值I d1 、I d2 、I d3 与电流有效值I 1 、I 2 、I 3 。 解：a) I d1= Im 2717 .0 )1 2 2 ( 2 Im ) ( sin Im 2 1 4 ≈ + = ?π ω π π π t I 1= Im 4767 .0 2 1 4 3 2 Im ) ( ) sin (Im 2 1 4 2≈ + = ?π ? π π π wt d t b) I d2= Im 5434 .0 )1 2 2 ( 2 Im ) ( sin Im 1 4 = + = ?wt d t π π ? π I 2= Im 6741 .0 2 1 4 3 2 Im 2 ) ( ) sin (Im 1 4 2≈ + = ?π ? π π π wt d t c) I d3= ?= 2 Im 4 1 ) ( Im 2 1π ω π t d I 3= Im 2 1 ) ( Im 2 1 2 2= ?t dω π π 1.4.上题中如果不考虑安全裕量,问100A的晶阐管能送出的平均电流I d1、I d2 、I d3 各为多 少?这时，相应的电流最大值I m1、I m2 、I m3 各为多少? 解：额定电流I T(AV) =100A的晶闸管，允许的电流有效值I=157A,由上题计算结果知 a) I m1 35 . 329 4767 .0 ≈ ≈ I A, I d1 ≈0.2717I m1 ≈89.48A
电力电子技术期末考试试题及答案修订稿
电力电子技术期末考试 试题及答案 Coca-cola standardization office【ZZ5AB-ZZSYT-ZZ2C-ZZ682T-ZZT18】
电力电子技术试题 第1章电力电子器件 1.电力电子器件一般工作在__开关__状态。 2.在通常情况下，电力电子器件功率损耗主要为__通态损耗__，而当器件开关频率较高时，功率损耗主要为__开关损耗__。 3.电力电子器件组成的系统，一般由__控制电路__、_驱动电路_、_主电路_三部分组成，由于电路中存在电压和电流的过冲，往往需添加_保护电路__。 4.按内部电子和空穴两种载流子参与导电的情况，电力电子器件可分为_单极型器件_、_双极型器件_、_复合型器件_三类。 5.电力二极管的工作特性可概括为_承受正向电压导通，承受反相电压截止_。 6.电力二极管的主要类型有_普通二极管_、_快恢复二极管_、_肖特基二极管_。 7.肖特基二极管的开关损耗_小于_快恢复二极管的开关损耗。 8.晶闸管的基本工作特性可概括为__正向电压门极有触发则导通、反向电压则截止__。 9.对同一晶闸管，维持电流IH与擎住电流IL在数值大小上有IL__大于__IH 。 10.晶闸管断态不重复电压UDSM与转折电压Ubo数值大小上应为，UDSM_大于__Ubo。 11.逆导晶闸管是将_二极管_与晶闸管_反并联_（如何连接）在同一管芯上的功率集成器件。 的__多元集成__结构是为了便于实现门极控制关断而设计的。 的漏极伏安特性中的三个区域与GTR共发射极接法时的输出特性中的三个区域有对应关系，其中前者的截止区对应后者的_截止区_、前者的饱和区对应后者的__放大区__、前者的非饱和区对应后者的_饱和区__。 14.电力MOSFET的通态电阻具有__正__温度系数。 的开启电压UGE（th）随温度升高而_略有下降__，开关速度__小于__电力MOSFET 。 16.按照驱动电路加在电力电子器件控制端和公共端之间的性质，可将电力电子器件分为_电压驱动型_和_电流驱动型_两类。 的通态压降在1/2或1/3额定电流以下区段具有__负___温度系数，在1/2或1/3额定电流以上区段具有__正___温度系数。 18.在如下器件：电力二极管（Power Diode）、晶闸管（SCR）、门极可关断晶闸管（GTO）、电力晶体管（GTR）、电力场效应管（电力MOSFET）、绝缘栅双极型晶体管（IGBT）中，属于不可控器件的是_电力二极管__，属于半控型器件的是__晶闸管_，属于全控型器件的是_GTO 、GTR 、电力
Chaptr15.交际功能CommunicativeFunction
Chapter15 . 交际功能Communicative Function Part One Have a try ?In the conversation below, two guests are visiting friends at their house. Read the conversation and answer the following 3 questions. ①There are four speakers, A, B, C and D. Which ones live at the house, and which ones are visitors? ②Does everyone know each other? How do you know? ③ A says: “Shall I just put these upstairs?”What do you think these are? A: Actually, I wonder if they’re in. Oh, they are in. B: They obviously are. C: Hello. A: Hello. C: Come in. B: I’m Mike. C: How are you? B: Fine. A: Shall I just put these upstairs? C: Well, yeah. Can you put them in our room, please? A: Sure. C: How were the roads? A: Oh, fine. No problem. B: No problems. No. A: Are you in there, Alison? Mmmm. Hello, there. D: Hello. A: Do you mind if I put my bag here? D: Oh, go ahead. Want a cup of tea? A: Yeah. ?Match these questions from the conversation to their functions. Shall I just put these upstairs? Can you put them in our room, please? Do you mind if I put my bag here? a request asking for permission an offer
电力电子技术试题及答案(B)
电力电子技术答案 2-1与信息电子电路中的二极管相比，电力二极管具有怎样的结构特点才使得其具有耐受高压和大电流的能力？ 答：1.电力二极管大都采用垂直导电结构，使得硅片中通过电流的有效面积增大，显著提高了二极管的通流能力。 2.电力二极管在P 区和N 区之间多了一层低掺杂N 区，也称漂移区。低掺杂N 区由于掺杂浓度低而接近于无掺杂的纯半导体材料即本征半导体，由于掺杂浓度低，低掺杂N 区就可以承受很高的电压而不被击穿。 2-2. 使晶闸管导通的条件是什么？ 答：使晶闸管导通的条件是：晶闸管承受正向阳极电压，并在门极施加触发电流（脉冲）。或：uAK>0且uGK>0。 2-3. 维持晶闸管导通的条件是什么？怎样才能使晶闸管由导通变为关断？ 答：维持晶闸管导通的条件是使晶闸管的电流大于能保持晶闸管导通的最小电流，即维持电流。 要使晶闸管由导通变为关断， 可利用外加电压和外电路的作用使流过晶闸管的电流降 到接近于零的某一数值以下，即降到维持电流以下，便可使导通的晶闸管关断。 2-4图2-27中阴影部分为晶闸管处于通态区间的电流波形，各波形的电流最大值均为I m ，试计算各波形的电流平均值I d1、I d2、I d3与电流有效值I 、I 、I 。 πππ4 π4 π2 5π4a) b)c) 图1-43 图2-27 晶闸管导电波形 解：a) I d1= π21?π πωω4 )(sin t td I m =π2m I (122+)≈0.2717 I m I 1= ?π πωωπ 4 2 )()sin (21 t d t I m =2m I π 2143+≈0.4767 I m b) I d2 = π1?π πωω4)(sin t td I m =π m I ( 12 2 +)≈0.5434 I m I 2 = ? π π ωωπ 4 2) ()sin (1 t d t I m = 2 2m I π 21 43+ ≈0.6741I m c) I d3=π21?2 )(π ωt d I m =41 I m I 3 =? 2 2 ) (21π ωπt d I m = 2 1 I m 2-5上题中如果不考虑安全裕量,问100A 的晶阐管能送出的平均电流I d1、I d2、I d3各为多少?这时，相应的电流最大值I m1、I m2、 I m3各为多少? 解：额定电流I T(AV)=100A 的晶闸管，允许的电流有效值I=157A,由上题计算结果知 a) I m1≈4767.0I ≈329.35， I d1≈0.2717 I m1≈89.48 b) I m2≈ 6741 .0I ≈232.90, I d2≈0.5434 I m2≈126.56 c) I m3=2 I = 314, I d3= 4 1 I m3=78.5 2-6 GTO 和普通晶闸管同为PNPN 结构,为什么GTO 能够自关断,而普通晶闸管不能? 答：GTO 和普通晶阐管同为PNPN 结构，由P1N1P2和N1P2N2构成两个晶体管V1、V2，分别具有共基极电流增益 1α和2α， 由普通晶阐管的分析可得， 121=+αα是器件临界导通的条件。1 21＞αα+两个等效晶体管过饱和而导通；
语言的作用是为了交际
语言的作用是为了交际，语言教学的目的是要教会学生使用语言。中学英语教学中如何培养学生的初步运用英语进行交际的能力成了刻不容缓的任务。 一、听是进行交际的前提 要学会一种语言，第一步就是听。只有身临其境, 置身于语言环境之中，才能收到良好的学习效果。所以，在英语课堂上，教师应最大限度地给学生以听的训练，使其不但听见，而且听懂。同时用神态表情的夸张表露与肢体语言的显性传递，以及借助身边事物来帮助学生理解教师的说话意图。在课堂上坚持用英语讲解、操练，并利用实物、图片、投影、录音等直观手段，给学生以启发，使他们在视觉、听觉方面得到统一，学生就会逐渐提高听的能力，不懂的句子渐渐懂了，不熟悉的句子渐渐听熟悉了，听力提高了，开口就有了保证。说与听是紧密联系在一起的，二者密不可分。影响中学生英语口语交际的主要问题是开口说，在学生有了一定的语言基础后，首先可以通过培养学生提问的能力来解决开口说的问题，帮助学生开展简单的交流。积极主动地用英语提问是展开交流、培养交际能力的一种重要的方法。提问方式多种多样，可互相提问；可借助于图样、幻灯片等提问；或对一幅图画提问；然后让学生互相来回答。这种训练学生提问的方法，既能提高学生的英语思维能力，又能提高学生的英语口语交际能力。当然，口语训练的方法很多，只有通过多种多样的语言实践，让学生在真实的语言环境中感受地道的英语和锻炼自己的语言表达能力，才能真正提高他们的口语水平和交际能力。 二、克服心理障碍，激发学生运用英语交际的兴趣 中学生中普遍存在的自卑、害怕、羞于开口、畏难等是导致他们在英语口语学习中消极、被动的主要心理原因。为此，应对其进行适时合理的心理调节，消除心理障碍，引导那些存在着心理障碍的中学生们正确进行英语口语学习。作为老师应让学生认识到，英语口语学习并不可怕，在口语交际中出错是很正常和自然的现象，谁都免不了要出错，口语学习之初最重要的不是能不能说，说得好不好的问题，而是敢不敢说的问题。而且在让学生用英语交流时，学生说错了，不要批评，鼓励他下次继续努力，说对了更应该表扬。并且口语交流重在思想的传达，只要能达到交流的目的，有一些错误是可以忽略的，并且随着训练的深入、水平的提高，错误可以逐渐减少，流利性和准确性俱佳的英语口语能力是可以获得的。 三、培养用英语思维的习惯，加强英语思维能力的训练 在教学中教师要坚持“ 尽量使用英语，适当利用母语” 的教学原则，以减少学生对母语的依赖性，母语对英语教学的负迁移。教师的教和学生的学都尽量不用母语为中介的翻译法，即使使用也应该加强分析对比。要求学生使用英汉双解词典并逐步过渡到使用英英词典，这有利于学生准确掌握词汇的内含和外延，因为用一种语言解释另一种语言不一定都能做到一一对应完全准确。教师都有这样的经历，即有些英语词句用汉语很难解释，甚至会出现越解释越难的现象。在这种情况下，我们应该经常给出一些包含该词、句的句子，让学生在具体的语境中去猜测、理解。所给出的语境应尽力和该词句所处的语境相似，而且是学生熟悉或容易接受的，这样既可以给学生的理解以铺垫，达到帮助学生理解掌握词、句的目的，又能增强语言实践的量，也能有效提高学生的英语理解能力，有助于培养学生运用英语思维的习惯。有了好的英语思维习惯，学生口语能力的提高也就有了一定的前提保障。 四、创设情景，鼓励学生大胆开口，培养说的能力 我国古代教育家孔子曰：“知之者不如好之者，好之者不如乐之者。”就已经道出了兴趣的重要性。俗话说：“兴趣是最好的老师” 。只有激发学生对口语表达产生浓厚的兴趣，才能使教师的教学与训练有所起色。因此，给学生设置一种语言学习的环境，让学生身置语境，激发学生的兴趣，通过语言气氛的感染，在自觉不自觉的状态中去说，以期达到掌
电力电子技术试卷3份答案
《电力电子技术》试卷1答案 一、填空（每空1分，36分） 1、请在正确的空格内标出下面元件的简称： 电力晶体管GTR；可关断晶闸管GTO；功率场效应晶体管MOSFET；绝缘栅双极型晶体管IGBT；IGBT是MOSFET和GTR的复合管。 2、晶闸管对触发脉冲的要求是要有足够的驱动功率、触发脉冲前沿要陡幅值要高和触发脉冲要与晶闸管阳极电压同步。 3、多个晶闸管相并联时必须考虑均流的问题，解决的方法是串专用均流电抗器。 4、在电流型逆变器中，输出电压波形为正弦波，输出电流波形为方波。 5、型号为KS100-8的元件表示双向晶闸管晶闸管、它的额定电压为800V伏、额定有效电流为100A。 6、180°导电型三相桥式逆变电路，晶闸管换相是在同一桥臂上的上、下二个元件之间进行；而120o导电型三相桥式逆变电路，晶闸管换相是在不同桥臂上的元件之间进行的。 7、当温度降低时，晶闸管的触发电流会增加、正反向漏电流会下降；当温度升高时，晶闸管的触发电流会下降、正反向漏电流会增加。 8、在有环流逆变系统中，环流指的是只流经逆变电源、逆变桥而不流经负载的电流。环流可在电路中加电抗器来限制。为了减小环流一般采控用控制角α大于β的工作方式。 9、常用的过电流保护措施有快速熔断器、串进线电抗器、接入直流快速开关、控制快速移相使输出电压下降。（写出四种即可） 10、双向晶闸管的触发方式有Ⅰ+、Ⅰ-、Ⅲ＋、Ⅲ-四种。 二、判断题,（每题1分，10分）（对√、错×） 1、在半控桥整流带大电感负载不加续流二极管电路中，电路出故障时会出现失 控现象。（√） 2、在用两组反并联晶闸管的可逆系统，使直流电动机实现四象限运行时，其中 一组逆变器工作在整流状态，那么另一组就工作在逆变状态。（×） 3、晶闸管串联使用时，必须注意均流问题。（×） 4、逆变角太大会造成逆变失败。（×） 5、并联谐振逆变器必须是略呈电容性电路。（√） 6、给晶闸管加上正向阳极电压它就会导通。（×） 7、有源逆变指的是把直流电能转变成交流电能送给负载。（×） 8、在单相全控桥整流电路中，晶闸管的额定电压应取U2。（×） 9、在三相半波可控整流电路中，电路输出电压波形的脉动频率为300Hz。（×） 10、变频调速实际上是改变电动机内旋转磁场的速度达到改变输出转速的目的。 （√） 三、选择题（每题3分，15分）
电力电子技术课后题答案
0-1.什么是电力电子技术? 电力电子技术是应用于电力技术领域中的电子技术；它是以利用大功率电子器件对能量进行变换和控制为主要内容的技术。国际电气和电子工程师协会（IEEE）的电力电子学会对电力电子技术的定义为：“有效地使用电力半导体器件、应用电路和设计理论以及分析开发工具，实现对电能的高效能变换和控制的一门技术，它包括电压、电流、频率和波形等方面的变换。” 0-2.电力电子技术的基础与核心分别是什么? 电力电子器件是基础。电能变换技术是核心. 0-3.请列举电力电子技术的 3 个主要应用领域。 电源装置;电源电网净化设备;电机调速系统;电能传输和电力控制;清洁能源开发和新蓄能系统;照明及其它。 0-4.电能变换电路有哪几种形式?其常用基本控制方式有哪三种类型? AD-DC整流电;DC-AC逆变电路;AC-AC交流变换电路;DC-DC直流变换电路。 常用基本控制方式主要有三类：相控方式、频控方式、斩控方式。 0-5.从发展过程看，电力电子器件可分为哪几个阶段? 简述各阶段的主要标志。可分为：集成电晶闸管及其应用；自关断器件及其应用；功率集成电路和智能功率器件及其应用三个发展阶段。集成电晶闸管及其应用：大功率整流器。自关断器件及其应用：各类节能的全控型器件问世。功率集成电路和智能功率器件及其应用：功率集成电路（PIC），智能功率模块（IPM）器件发展。 0-6.传统电力电子技术与现代电力电子技术各自特征是什么? 传统电力电子技术的特征：电力电子器件以半控型晶闸管为主，变流电路一般 为相控型，控制技术多采用模拟控制方式。 现代电力电子技术特征：电力电子器件以全控型器件为主，变流电路采用脉宽 调制型，控制技术采用PWM数字控制技术。 0-7.电力电子技术的发展方向是什么? 新器件：器件性能优化，新型半导体材料。高频化与高效率。集成化与模块化。数字化。绿色化。 1-1.按可控性分类，电力电子器件分哪几类? 按可控性分类，电力电子器件分为不可控器件、半控器件和全控器件。 1-2.电力二极管有哪些类型?各类型电力二极管的反向恢复时间大约为多少? 电力二极管类型以及反向恢复时间如下： 1）普通二极管，反向恢复时间在5us以上。 2）快恢复二极管，反向恢复时间在5us以下。快恢复极管从性能上可分为快速恢复和超快速恢复二极管。前者反向恢复时间为数百纳秒或更长，后者在100ns 以下，甚至达到20~30ns，多用于高频整流和逆变电路中。 3）肖特基二极管，反向恢复时间为10～40ns。 1-3.在哪些情况下，晶闸管可以从断态转变为通态? 维持晶闸管导通的条件是什么? 1、正向的阳极电压； 2、正向的门极电流。两者缺一不可。阳极电流大于维持电流。
交际语言教学法
交际语言教学法 内容提要：本文介绍了交际语言教学法这一以培养学习者的语言运用和交际能力为主要目标的语言教学方法，介绍了其发展，主要内容和特点并结合实例就此方法在外语教学中的运用进行了分析。 关键词：交际语言教学法外语教学语言交际能力随着我国的社会、经济、文化等活动进一步融入到国际化和全球化的体系之中，我国对于外语人才的语言交际能力的要求也逐渐提高。作为外语教学工作者，能够在教学工作中有效地使用交际语言教学法对于组织教学过程，使学生更好地达到学以致用的目的具有重要意义。本文就交际语言教学的起源，特点以及如何在外语教学中应用此方法进行了逐一探讨。 交际语言教学（Communicative Language Teaching）产生于七十年代初期，社会语言学家海默斯在1971年发表的《论交际能力》（On Communicative Competence）被认为是交际法的直接理论根据。其创始人之一是英国语言学家 D. A. Wilkins，1976年维尔金斯出版了《意念教学大纲》（Notional Syllabuses）一书，把交际法置于更可靠的基础之上。交际语言教学法经过近30年的发展已逐渐成为一种为世界语言教学界所普遍认同的教学思想和方向。它的理论主要来自社会语言学、心理语言学，并受到话语分析、语言哲学、人类学、社会学等多门学科的影响。交际法认为语言是交际的工具，学会一种语言不仅要掌握其语言形式和使用规则，还要学会具体运用，也就是说
要知道在什么场合运用。其核心是教语言应当教学生怎样使用语言，用语言达到交际的目的，而不是把教会学生一套语法规则和零碎的词语用法作为语言教学的最终目标。所以交际教学法强调的是要教授语言功能方面的知识，学生如果没有掌握这门语言的交际本领，没有具备这门语言交际方面的能力，就不能说学会了这一门外语。交际教学法强调要把学生真正置于尽可能真实的交际场景中，并且要由学生亲历一种活的交际活动的过程。根据交际教学法的原则，教师和学生都要注重运用所学外语进行真实的课堂以及课外交际活动，在尽量模拟现实的交际情景中来进行教学和学习，才能有利于培养学生的语言交际能力。本文以下部分就交际教学法的原则谈谈运用此方法进行教学的一些具体方式和做法。 一．尽可能在课堂教学中运用真实的交际场景 我们传统的外语教学概念中多注重语法形式是否完善，在交际教学法中更注重的是交流者是否能正确流利的表意，即是否“get the ideas across”。而这种侧重面对于培养我国所急需的实用型外语人才具有重要意义。因此，在教学中要尽可能多地运用真实场景来训练学生的实际语言应用及应变能力。而对于真实场景的选用则要有一定的取舍，我们应尽量选择符合实际需要或符合中国大学生在今后工作中实际应用的语言情景。例如作为旅游院校的学生，今后工作中在很大程度上要接触或进入旅游行业，那么选用和旅游相关的场景则比较合适。笔者在教授英语专业成人本科三年级口语课时就选用了在带外国旅游团过程中可能发生的真实场景让学生进行角色扮演，进行
电力电子技术 复习题答案
第二章： 1.晶闸管的动态参数有断态电压临界上升率du/dt和通态电流临界上升率等，若 du/dt过大，就会使晶闸管出现_ 误导通_，若di/dt过大，会导致晶闸管_损坏__。 2.目前常用的具有自关断能力的电力电子元件有电力晶体管、可关断晶闸管、 功率场效应晶体管、绝缘栅双极型晶体管几种。简述晶闸管的正向伏安特性 答: 晶闸管的伏安特性 正向特性当IG=0时，如果在器件两端施加正向电压，则晶闸管处于正向阻断状态，只有很小的正向漏电流流过。 如果正向电压超过临界极限即正向转折电压Ubo，则漏电流急剧增大，器件开通。 随着门极电流幅值的增大，正向转折电压降低，晶闸管本身的压降很小，在1V左右。 如果门极电流为零，并且阳极电流降至接近于零的某一数值IH以下，则晶闸管又回到正向阻断状态，IH称为维持电流。 3.使晶闸管导通的条件是什么 答：使晶闸管导通的条件是：晶闸管承受正向阳极电压，并在门极施加触发电流（脉冲）。或：uAK>0且uGK>0。 4.在如下器件：电力二极管（Power Diode）、晶闸管（SCR）、门极可关断晶闸管 （GTO）、电力晶体管（GTR）、电力场效应管（电力MOSFET）、绝缘栅双极型晶体管（IGBT）中，属于半控型器件的是 SCR 。 5.晶闸管的擎住电流I L 答：晶闸管刚从断态转入通态并移除触发信号后，能维持导通所需的最小电流。 6.晶闸管通态平均电流I T(AV) 答：晶闸管在环境温度为40C和规定的冷却状态下，稳定结温不超过额定结温时所允许流过的最大工频正弦半波电流的平均值。标称其额定电流的参数。 7.晶闸管的控制角α（移相角） 答：从晶闸管开始承受正向阳极电压起到施加触发脉冲止的电角度,用a表示,也称触发角或控制角。
语言交际的重要性
语言交际的重要性 每个人在很小的时候就开始学习语言，它是我们日常交流和沟通中必不可少的工具，也是是人类最基本、最重要的一种生存能力和社会行为。社会的存在和发展不能没有语言，不能没有语言的运用，也不能没有言语交际活动。而在当今社会，一个人的语言水平、言语行为和言语交际能力，完全可以体现出他的道德修养的深与浅，人格教养的好与坏，个人能力的高与低。 语言是一种灵活的东西，一句话可以表达多种意思，如“我要炒饭。”可以理解为我要做炒饭，也可以理解为，我要吃份炒饭。你可以用灵活的话语教导他人，不会热闹别人，同时也具有说服性。 我看过一则某国的交通安全广告:驾驶汽车时速不超过30 英里,你可以饱览本地美丽景色;超过60英里,请到法庭做客;超过80英里,欢迎光顾本地设备最新的急救医院;上了100英里,请君安息吧! 汽车时速“超过60英里”,即违反了该国的交通安全法规,属于违法行为,应受到法律的惩处,故委婉地表达为“请到法庭做客”。“光顾”本为“敬辞”,多用于商店表示对顾客的欢迎。车速得到80英里,很可能会发生车祸,受伤人员要到医院进行抢救,这后果多严重!故委婉地说是“光顾”。“安息”多用于对死者的悼念。车速达100英里,定会车毁人亡,它不说“你肯定会死”,而委婉地说为“请君安息吧”。这幅广告语言表现出风趣幽默的风格,对那些违章行车者有着很好的劝导和警示作用。 会用语言就不代表会交际，善于交际的人往往在职场上会很占优势，同时在大家交谈中可以活跃气氛，给大家留有好的印象，反而不善于交际的人不但在职场上处于略势，而且还容易被大家忽视和排斥。所以懂得交际，善于交际很重要。在与人交流时，要避开人们避讳的，反感的话题，评论他人时要委婉一点，否则即使你很能说，也会让人感到厌恶。 有一个故事，春秋时期发生过一件事，烛邹替齐景公饲养的爱鸟不小心飞走了，景公发怒要杀烛邹。在这千钧一发的时候，宰相晏婴站出来说：“烛邹这书呆子有三大罪状，请大王让我列举完以后，再按罪论处。”得到景公的允许后，晏婴把烛邹叫到景公的面前说：“你为大王管理着爱鸟，却让它飞走了，这是第一条罪状；你使得我们大王因为鸟的事杀人，这是第二条罪状；更严重的是各国诸侯听了这件事后，以为大王重视鸟而轻视知识分子，这是第三条罪状。”数完这些所谓罪状后，便请景公把烛邹杀掉。景公尽管残忍，但从晏婴的话里听出了利害，就对晏婴说：“不要杀了，我听从你的命令就是了。”从这个故事可以看出委婉地说话不但可与教育他人，还可以救人的性命。 要想提高语言交际能力，从这三个方面入手，首先言语交际主体因素，交际主体是指言语交际的参与者，即从事言语交际活动的个人和团体。其中的团体指各种政府或民间组织，当然也包括媒介组织。言语交际是一个涉及交际主体的双向互动过程，包括说话者的话语选择和听话者对话语的理解。交际中表达者和接受者都是交际的参与者，而且双方表达和接受的地位随时变换。所以，严格地说，言语交际的双方都应当视为交际主体。所以我们每个人都是话语的接受者又是话语的表达者，会说话对我们每个人都很重要。 然而，预设因素在言语交际话语选择和理解的动态过程中充当着一个变量，它可以在很大程度上制约交际主体的言语行为。因此，言语交际主体在言语交际活动中应在充分考虑预设因素的基础上随时调整自己的言语行为，避免给交际带
电力电子技术试题及答案(1)
《电力电子技术》试卷 一．填空（共15分，1分/空） 1.电力电子技术通常可分为（）技术和（）技术两个分支。 2.按驱动电路信号的性质可以将电力电子器件分为（）型器件和（）型器件两类，晶闸管属于其中的（）型器件。 3.晶闸管单相桥式全控整流电路带反电动势负载E时（变压器二次侧电压有效值为U ，忽略主电路 2 各部分的电感），与电阻负载时相比，晶闸管提前了电角度δ停止导电，δ称为（）角，数量关系为δ=（）。 4.三相桥式全控整流电路的触发方式有（）触发和（）触发两种，常用的是（）触发。 5.三相半波可控整流电路按联接方式可分为（）组和（）组两种。 6.在特定场合下，同一套整流电路即可工作在（）状态，又可工作在（）状态，故简称变流电路。 7.控制角α与逆变角β之间的关系为（）。 二．单选（共10分，2分/题） 1．采用（）是电力电子装置中最有效、应用最广的一种过电流保护措施。 A.直流断路器 B. 快速熔断器 C.过电流继电器 2．晶闸管属于（）。 A.不可控器件 B. 全控器件 C.半控器件 3．单相全控桥式整流电路，带阻感负载（L足够大）时的移相范围是（）。 A．180O B.90O C.120O 4．对三相全控桥中共阴极组的三个晶闸管来说，正常工作时触发脉冲相位应依次差（）度。 A.60 B. 180 C. 120 5．把交流电变成直流电的是（）。 A. 逆变电路 B.整流电路 C.斩波电路 三．多选（共10分，2分/题） 1．电力电子器件一般具有的特征有。 A.所能处理电功率的大小是其最重要的参数 B.一般工作在开关状态 C.一般需要信息电子电路来控制 D.不仅讲究散热设计，工作时一般还需接散热器 2．下列电路中，不存在变压器直流磁化问题的有。 A.单相全控桥整流电路 B.单相全波可控整流电路 C.三相全控桥整流电路 D.三相半波可控整流电路 3．使晶闸管关断的方法有。 A.给门极施加反压 B.去掉阳极的正向电压 C.增大回路阻抗 D.给阳极施加反压 4．逆变失败的原因有。 A.触发电路不可靠 B.晶闸管发生故障 C.交流电源发生故障 D.换相裕量角不足 5．变压器漏抗对整流电路的影响有。 A.输出电压平均值降低 B.整流电路的工作状态增多 C.晶闸管的di/dt减小 D.换相时晶闸管电压出现缺口 四．判断（共5分,1分/题） 1.三相全控桥式整流电路带电阻负载时的移相范围是150O。（） 2.晶闸管是一种四层三端器件。（）
HEDGING的交际功能
. HEDGING的交际功能 浙江财经学院外语系潘晓霞* 浙江大学外国语言文化与国际交流学院黄建滨** 摘要：HEDGE/HEDGING作为模糊语言学中的特殊语言现象，越来越受到国内外学者的关注。然而随着对其研究的不断深入，HEDGE/HEDGING的概念也不断地发生变化。然而对这一概念学者们至今未达成一致，不同的学者提出了不同的定义。因而，系统地回顾HEDGE/HEDGING的研究很有必要。本文首先概述HEDGE/HEDGING 的概念演变过程，接着简要回顾HEDGE/HEDGING在不同领域的研究情况，然后分析和探讨其主要交际功能，并在文章的最后提出用“模糊调和”来指称HEDGING可能会比“模糊限制语”更合适。 关键词：模糊限制语交际功能语篇功能人际功能礼貌策略 1. HEDGE和HEDGING研究综述 1.1 HEDGE和HEDGING的概念演变 语言学字典中解释HEDGE和HEDGING这两个概念的词条很少，对它们的定义多半基于LAKOFF最先提出的定义。HEDGE 作为一个语言学术语是由美国语言学家https://www.wendangku.net/doc/5216649773.html,KOFF（1972）最早提出的，虽然在这之前，ZADEH（1965）和WEINREICH（1966）已注意到了这种语言现象和概念。根据LAKOFF的定义，HEDGES指的是那些“将事物弄得模模糊糊，或将原本模糊的事物弄得不那么模糊的词语”（LAKOFF，1972，234），诸如sort of, strictly speaking。ZADEH（1972）按照LAKOFF 的定义从语义学和逻辑学的角度分析了英语中的HEDGES，诸如very，slightly，technically，practically。 HEDGE作为一个语言学术语最初指的是一种用来修饰一述语或名词短语的成员隶属关系的表达，通常为一词语或短语。由于这类词或短语有着共同的特征，即可以改变某些词的模糊程度，或者说它们在某种程度上起了限制的作用，所以在最早的译文中廖东平（1982）用“模糊限制词”对应英语中的HEDGES。继而，何自然（1985，27）改用“模糊限制语”，按照LAKOFF 的定义，“一些令听话者得不到确切信息的词语，如kinda（=kind of），sort of等是模糊限制语；而一些表达推测或不确定含义的词语，如I guess，I think等，也算是模糊限制语。”之后，中国学者便一直沿用“模糊限制语”来介绍国外有关HEDGE的研究成果，或研究英语中的这一语言现象（孙1986，陈&李1994，李1995，赵1999，何&姜1994，冯1999，杨2001）。 然而，随着国外语言学界对HEDGE研究的不断深入，HEDGE的概念发生了很大的变化，不再停留在原先的层面上。自二十世纪七十年代早期以来，尤其自HEDGE被语用学家和语篇分析学家采用以来，HEDGE 的概念就已远远偏离它最初的含义。这个术语不再仅指用于修饰一述语或一名词短语的成员隶属关系的表达。早在二十世纪七十年代，FRASER（1975）和https://www.wendangku.net/doc/5216649773.html,KOFF（1977）就曾注意到某些动词和句法结构传达各种模糊限制施事语(hedged performatives) (e.g. I suppose/guess/think that Harry is coming; Won’t you open the door?)。模糊限制施事语的提出拓宽了HEDGE的概念。此外，HEDGE还用来修饰说话者对整个命题的真值性所负的责任，而不仅仅修饰话语中某一部分的成员隶属关系。一些学者，如VANDA KOPPLE （1985），认为HEDGES (e.g. perhaps, seem, might, to a certain extent）是修饰整个命题的真值性而不是使其中个别成分变得模糊。HEDGE概念的这种扩展使一些研究者认为应该区分两类HEDGES。 *潘晓霞，女，浙江财经学院外语系教师，硕士，研究方向：语用学，词汇学。 **黄建滨，男，浙江大学外国语学院教授，教育部大学外语教学指导委员会委员，研究方向：词汇学，语言教学。通讯地址：310058 浙江杭州浙江大学紫金港校区外国语学院。E-mail：jianbin32@https://www.wendangku.net/doc/5216649773.html, 或huangjb@https://www.wendangku.net/doc/5216649773.html,
语言交际在生活中的作用与影响
。 言语交际时，要注意语言得体。语言表达“得体” ，指能够恰当使用语言，符合语境和语体的要求。“语境”有“内部语境”和“外部语境”“内部语境”主要指文。章的上下文，如文体、句式、语言间的搭配和使用习惯等。“外部语境”指言语交际时的各种情境条件，如说话的目的，说话的场合，需要表达的方式，发话者的身份、职业、处境，受话者的年龄、性别、经历、思想性格、爱好、文化水平、心理需求、职业处境等。在什么场合和什么人要说什么话？比如说，我们不能在火葬场的附近贴上如是标语“计划生育利国利民“，也不能让医院的导诊在送走病人时说“欢迎光临” ，不能在耄老人的寿宴上唱“东边的太阳就要落山了……” 言语既是交际的一种心理现象，也是展现交际心理的一种过程，所以在进行言语交际的同时就必须做到说话得体，恰如其分。这也会让对方有一个良好的印象，继而进行下一步的交际活动。然而，任何夸大其词，或是不看对象，词不达意，都会影响交际心理的展现，妨碍相互间的交流。例如怎样称呼别人，这中间就大有文章。两人见面，第一个词便是称呼，它既是见面礼，也是进入双方交际大门的通行证。在交际活动中，言语要很注意其分寸，该说则说，不该说则一句都不说。这些原则也要看自己和对方的熟悉程度而言的，总的来说，就是应视对象和交际目标而定。交际中难免会有赞美和祝贺之词，当然也会有批评等负面的说辞。所以，在言语交际的时候需要注意言语的得体，以保持与别人之间默契的联系。 “舌为利害本，口是祸福门。＂“语言切勿刺入骨髓，戏谑
切勿中人心病。”“当着矮人，别说短话。“良言一句三冬暖，恶语伤人六月寒。”希望我们所有人在交往的时候都能很好的使用语言，让语言的艺术浇出美丽的鲜花！ 们的交际是个十分复杂的过程，受各种不同的交际对象、交际目的的限制。只要我们恰当的运用交际语言，交际语言定会在为满足人们日趋复杂的社会生活需要发挥更大的作用。所以如何做好语言交际就显得尤为重要。
王兆安版电力电子技术试卷及答案
20××－20××学年第一学期期末考试 《电力电子技术》试卷(A) （时间90分钟 满分100分） （适用于 ××学院 ××级 ××专业学生） 一、 填空题（30分,每空1分）。 1．如下器件：电力二极管（Power Diode ）、晶闸管（SCR ）、门极可关断晶闸管（GTO ）、电力晶体管（GTR ）、电力场效应管（电力MOSFET ）、绝缘栅双极型晶体管（IGBT ）中，属于不可控器件的是________，属于半控型器件的是________，属于全控型器件的是________；属于单极型电力电子器件的有________，属于双极型器件的有________，属于复合型电力电子器件得有 ________；在可控的器件中，容量最大的是________，工作频率最高的是________，属于电压驱动的是________，属于电流驱动的是________。（只写简称） 2．单相桥式全控整流电路中，带纯电阻负载时，α角移相范围为 _，单个晶闸管所承受的最大正向电压和反向电压分别为 和 ；带阻感负载时，α角移相范围为 ，单个晶闸管所承受的最大正向电压和反向电压分别为 和 。 3．直流斩波电路中最基本的两种电路是 和 。 4．升降压斩波电路呈现升压状态时，占空比取值范围是__ _。 5．与CuK 斩波电路电压的输入输出关系相同的有 、 和 。 6．当采用6脉波三相桥式电路且电网频率为50Hz 时，单相交交变频电路的输出上限频率约为 。 7．三相交交变频电路主要有两种接线方式，即 _和 。 8．矩阵式变频电路是近年来出现的一种新颖的变频电路。它采用的开关器件是 ；控制方式是 。 9．逆变器按直流侧提供的电源的性质来分，可分为 型逆变器和 型逆变器。 10．把电网频率的交流电直接变换成可调频率的交流电的变流电路称为 。 二、简答题（18分,每题6分）。 1．逆变电路多重化的目的是什么？如何实现？串联多重和并联多重逆变电路各应用于什么场合？ 2．交流调压电路和交流调功电路有什么异同？ 3．功率因数校正电路的作用是什么？有哪些校正方法？其基本原理是什么？ 三、计算题（40分，1题20分，2题10分，3题10分）。 1．一单相交流调压器，电源为工频220V ，阻感串联作为负载，其中R=0.5Ω，L=2mH 。 试求：①开通角α的变化范围；②负载电流的最大有效值；③最大输出功率及此时电源侧的功率因数；④当2πα＝时，晶闸管电流有效值，晶闸管导通角和电源侧功率因数。 2．.三相桥式电压型逆变电路，工作在180°导电方式，U d =200V 。试求输出相电压的基波幅值U UN1m 和有效值U UN1、输出线电压的基波幅值U UV1m 和有效值U UV1、输出线电压中7次谐波的有效值U UV7。 3 ．如图所示降压斩波电路E=100V ，L 值极大，R=0.5Ω，E m =10V ，采用脉宽调制控制方式，T=20μs ，当t on =5μs 时，计算输出电压平均值U o ，输出电流平均值
语言交际功能课堂教学
注重语言交际功能的对话教学活动设计 语言的本质是交际。交际能力是指人们能有效地运用一种语言知识进行人际交往和文字交流的能力。英语课堂教学中怎样通过言语交际来培养学生的综合语言运用能力是我们语言教学的目标。如何围绕“语言交际功能”来设计英语课堂教学，特别是利用对话这一题材来设计活动，多年来是英语教师极为关注的问题。我认为，在对话教学设计的过程中，要注意各个环节：呈现理解时凸显语言功能，操练巩固时发挥语言的交际功能，拓展活动中运用语言的交际功能，这样的设计才能以学生为本，激发和培养学生学习英语的兴趣，提高学生英语语言运用能力。 一、呈现理解时凸显语言功能 1. 创设符合并略高于学生认知水平的情景。小学英语对话教学中，老师在对话教学一开始就应利用各种媒介（实物、图片、多媒体、动作、表情和语调等）巧妙地设置情景，通过视、听、说活动呈现新句型，让学生感受其应用的场合和意义。创设的情景要略高于学生的认知水平，让他们“跳一跳，就能摘到苹果”，学到知识。 2. 利用多媒体材料创设对话语境。多媒体课件形象生动的特点在英语教学中起着重要的作用，现在已经广泛地运用在各科的教学中。教学五年级下册unit 4what are you doing 一课时，用课件展示了一幅动物王国中各种动物和谐相处的画面，通过听声音猜动物的活动，复习已学句型“what’s this（that）？/what are these（those）？”并引出新句型，具体步骤如下：t：（让学生听老虎叫声）what’s this？
s：it’s a tiger. t：right. look！what’s the tiger doing？这时，屏幕上老虎弹钢琴的画面逐渐放大，并传出悠扬的琴声。根据这一有趣的情景，学生很快便领悟了新句型的意思，有的学生甚至能用“the tiger is playing the piano”回答问题。接着，屏幕上又出现一只笨狗熊扭动着肥胖身体跳舞的画面，笔者让男女学生用新句型轮换回答，从而加深了学生对新句型的理解。 3. 对话呈现注重交际情景的真实性和趣味性。这些源于生活并与学生生活实际为基础的活动，对学生英语语言交际能力的培养十分重要。在教学四年级下册unit5how much is it？part a let’s talk 这一部分时，将教室布置成一个服装店，拉开帘子，露出了事先准备好的衣服架子，架子上有各种衣服，衣服上有大的价格标签。教师扮演营业员，出售衣服，学生和老师进行实际交际活动，从而引出句型：can i help you？how much is it（are they）？运用直观教具配合动作、表情和手势等，呈现了一个购物的真实情景，学生在今后的学习中就能明白can i help you 这一句型真实的运用场景。 二、操练巩固时发挥交际性能 1. 创设符合学生实际的真实交际情景。句型教学中的交际性操练是指运用所学句型开展具有信息沟通的活动。这是一种在模拟的或真实的情景中进行的语言操练。教师应尽量运用学生熟练掌握的句型，提出真实性的问题或开展运用所学句型的游戏活动，以培养学生用英语做事的能力。 2. 灵活运用文本，适当进行增删。教材是教学的依据，在教学