Gazdasági Ismeretek | Döntéselmélet » Decision Theory Overview

Source: http://www.doksinet DECISION THEORY References: (1) Michael D. Resnick, Choices (An Introduction to Decision Theory) 5th Ed. Univ Of Minnesota Press 2000 (2) Rex Brown, Rational Choice and Judgment. Wiley Interscience, 2005 (3) Robert J. Vanderbei, Linear Programing 3rd Ed , Springer 2007 (4) Yih-Long Chang, WinQSB Version 2.0, Wiley, 2003 (5) J. Lawrence, B Pasternack, Applied Management Science 2nd Ed Wiley 2010. (6) K. Leyton-Brown, Y Shoham, Essentials of Game Theory Morgan Claypool Publ 2008 (7) R. Gibbons, A Primer in Game Theory Pearson Education Ltd 1992 (8) J. Temesi, Foundations of decision theory (in Hungarian), Aula, 2002, Budapest (9) W. J Stevenson, Operation management, McGraw-Hill, Irvin, 2008 Software: WinQSB (Quantitative System for Business) http://www.econunidebhu/sites/download/WinQSBzip) 1. Introduction Decision theory: web Google search= 94.8 million hits Some areas of decision theory: • medical, • law, • economics, • technical, engineering, •

others. Some characteristic problems in decision theory Every day we have to make decisions. Sometimes we have to decide at once (e.g what to eat for breakfast, where to have lunch today, which way to go to the university from our flat) at other occasions we have time to decide, moreover we must have justified, well considered decisions (e.g decision about the productions of a factory: the quantity of various products, which are optimal in certain respect). 1. Production problem: a factory produces several products, and we have to decide how much to manufacture from each product such that e.g the profit should 1 Source: http://www.doksinet 2 be maximal, or the aim can be maximal profit with minimal use of energy (or labor) during the production process. 2. Investment problem: to choose a portfolio with maximal yield Constraint: financial, other points to consider risk factors, duration of the investment etc. 3. Work scheduling: eg a supermarket employs a certain number of workers

On each day, depending on the trade a certain number of workers have to work. We have to make a weekly schedule of the available workers such that the total weekly wage of the workers be minimal (wage for Saturday is higher than other days). 4. Buying fighter planes Points to consider: cost, max. speed, reliability etc 5. Tender evaluation An international bank wants to replace its computers with new ones. How to decide which offer to accept? Points to consider: cost, quality of hardware, service conditions, guarantees,etc. In each case the aim is one action: the best production plan, the highest return, optimal work schedule, finding the best fighter planes for the country, etc. Basic concepts Alternatives: the different actions from which we can choose, their sets is called decision space. Their characteristic properties: • • • • number of alternatives how can one characterize the alternative by numbers, independence of alternatives, probability of the alternatives

Objectives (criterions, evaluation factors, aims): the directions to which we want to take our system (sometimes these cannot be reached, or cannot be expressed by numbers). Properties of objectives: • • • • complete (all important objectives have to be present), should be suitable for scrutinizing, decomposable (the alternatives can be studied for each objective separately), omission of repetition of objectives, Source: http://www.doksinet 3 • minimal (the number of objectives be the smallest possible), Decision makers: the persons responsible for • supplying the informations needed, • determining the alternatives, choosing the best alternative(s), • realizing the best alternative(s). Behavior of decision makers: rational (wants to achieve optimum) or irrational. The decision makers see a part of the problems objectively (in particular those which can be measured, expressed by numbers, calculated values) in other parts of the problems some problems the decision

makers may have preferences (subjective standpoint). Behavior science: for the decision makers the principle of restricted rationality is valid The decision process: • • • • • • formation of a decision situation (there is a need for solving conflicts), phrasing of the decision problem, formalizing of the decision problem (in terms of mathematics), choosing the method of solution, solution (choosing the optimal action), adapting, evaluation, scrutinizing: was the decision correct or we have to begin the decision process again. 2. Buying fighter planes Viewpoints of the experts: • • • • • • S1 = S2 = S3 = S4 = S5 = S6 = max. speed km /h, useful area in the plane in m2 , loadability in kg, cost in million dollars, reliability, ability to maneouver. S5 , S6 are evaluated in the following way: vl=very low, l=low, a=average, g=good, vg=very good. Source: http://www.doksinet 4 The table of offers (alternatives: A1 A2 A3 A4 S1 1000 1250 900 1100 S2

150 270 200 180 S3 20000 18000 21000 20000 S4 5.5 6.5 4.5 5.0 S5 a l g g S6 vg a g a Evaluation of quantitative points of view vl=very low l=low a=average g=good vg=very good =1 =3 =5 =7 =9 points points points points points Making data independent of units Ideal values are given by experts, or we have prior information on them. The data of our table (matrix) are denoted by: xij the number in the ith line, and the jth column (elements of a 6 × 4 type matrix) Ideal value in the ith line:max xij , (where the maximum is taken for all index j j) if the largest value is the ideal one, and min xij , if the smallest value is j the ideal one. The transformed value vij = xij , max xij j Source: http://www.doksinet 5 if the largest value is the ideal one, and min xij j vij = xij , if the smallest value is the ideal one. Therefore, if i = 1 then max x1j = 1250, v1j = j i = 2 then max x2j = 270, j v2j = i = 3 then max x3j = 21000, v3j = j i = 4 then min x4j

= 4, 5, !!! v4j = j i = 5 then max x5j = 7, v5j = i = 6 then max x6j = 9, v6j = j j x1j 1250 x2j 270 x3j 21000 4,5 x4j x5j 7 x6j 9 (j = 1, 2, 3, 4) (j = 1, 2, 3, 4) (j = 1, 2, 3, 4) (j = 1, 2, 3, 4) (j = 1, 2, 3, 4) (j = 1, 2, 3, 4) Our new table: A1 A2 S1 0.80 1 0.72 088 S2 0.56 1 0.74 067 S3 0.95 086 1 0.95 S4 0.82 064 1 0.90 S5 0.71 043 1 0.71 S6 1 A3 A4 0.56 078 056 The minimal elements in each column are written in boldface letter. Each element of the matrix is between 0 and 1 and every line contains a 1 (namely the best offer(s)) In the columns of the alternatives (offers) the best value is 1, and the smallest value is the worst. Source: http://www.doksinet 6 Decision methods: narrowing the alternatives (a) Method of satisfaction: there is a level for each alternative which is just satisfactory, below this level we cannot accept the alternative(s). For example at University mark less than 2 is failure! (b) Disjunctive method: gives priority

to excellence (e.g sport, science, art) If an alternative is better than a given level, then it is acceptable. (c) Dominated alternatives. An alternative is dominated by another one if it is worse in every point of view than the other. Rational decision maker does not choose dominated alternative. Decision based on the order of importance: lexicographic method Order the alternatives according to some point of view, and decide accordingly. For example if price is the most important (poor country cannot afford expensive planes) the we choose the cheepest offer. Decision methods: optimistic, pessimistic, Hurwicz index In each column of the table we choose the minimal (worst) and the maximal (best) value, these are printed by boldface and italic numbers respectively: A1 A2 S1 0.80 1 0.72 088 S2 0.56 1 0.74 067 S3 0.95 086 1 0 .95 S4 0.82 064 1 0.90 S5 0.71 043 1 0.71 S6 1 A3 A4 0.56 078 056 Denote thes minimal and maximal values by mj and Mj respectively: mj :=

min vij , i Mj := max vij . i Source: http://www.doksinet 7 The pessimistic decision maker first choose the worst value in each column and out of these finds the best value and takes the alternative corresponding to it (avoid the worst), this method is called the maximin method. In our case   max mj = max min vij = 0, 72 j j i the decision is A3 . The optimistic decision maker first choose the best value in each column and out of these finds again the best value and takes the alternative corresponding to it.this method is called the maximax method In our case   max Mj = max max vij = 1 j j i the decisions are A1 , A2 , A3 which are equivalent. We can introduce the Hurwicz optimistic coefficient (index) α ∈ [0, 1], then first we calculate the quantities Hj (α) = αMj + (1 − α)mj (j = 1, 2, 3, 4) where Mj := max xij , mj := min xij (j = 1, 2, 3, 4), then find the maximum of i i Hj (α): max Hj = Hj0 j if maximum is attained at j0 the the decision is the

alternative Aj0 . α = 0 means pessimistic decision maker, α = 1 is the optimistic one. 3. Decision in case of uncertainty: extension of a business In the previous example the offers do not depend on random events, we had a deterministic model. In a stochastic model our decision is influenced by random events. Our business can be extended in 3 ways: A1 = new branch, A2 = new service, A3 = new product. Our decision depends on the demand of next year, which should be estimated. Source: http://www.doksinet 8 demand of next year estimated subjective probabilities S1 very good P (S1 ) = 0.4 S2 good P (S2 ) = 0.3 S3 medium P (S3 ) = 0.2 S4 weak P (S4 ) = 0.1 4 P P (Si ) = 1 i=1 The payoff table of the alternatives depends on the demands in the following way (given in million Ft) together with the probabilities is given in the next table: A 1 A2 A 3 P S1 20 26 10 0.4 S2 12 10 8 0.3 S3 8 4 7 0.2 S4 4 −4 5 0.1 The elements of the matrix are denoted by vij =

v(Si , Aj ). Decision possibilities. 1. We neglect the probabilities and decide on the basis of the payoffs(giving equal chance to S1 , S2 , S3 , S4 ). (a) Pessimistic, optimistic and Hurwicz index, see before. (b) Minimax regret decision. Regret is the payoff which is not realized Source: http://www.doksinet 9 If e.gS1 happens but we did not choose (the best payoff) A2 but A1 or A3 then payoff not realized is A1 A 2 A3 6 0 16 Each elements of the line are deducted from the maximal element, in this way we get the regret table: A1 A 2 A3 S1 6 0 16 S2 0 2 4 S3 0 4 1 S4 1 9 0 column maximum 6 9 16 The minimum of these column maximums is =6, the decision is A1 . 2. We take the probabilities into consideration (a) Decision based on (maximal) expected payoff The expected values of the payoffs for each alternative are: E(A1 ) = 20 · 0.4 + 12 · 03 + 8 · 02 + 4 · 01 = 136 E(A2 ) = = 13.8 E(A3 ) = = 8.3 Decision: A2 . (b) Equal likelihood method. Decision based

on maximal expected value taking equal probabilities: Source: http://www.doksinet 10 E(A1 ) = 20 · 0.25 + 12 · 025 + 8 · 025 + 4 · 025 = 11 E(A2 ) = =9 E(A3 ) = = 7.5 Decision: A1 . (c) Decision based on (minimal) expected regret. The expected values of the regrets: Ẽ(A1 ) = 6 · 0.4 + 0 · 03 + 0 · 02 + 1 · 01 = 25 Ẽ(A2 ) = = 2.3 Ẽ(A3 ) = = 7.8 Decision A2 . Expected value of perfect information. Suppose that in some way we can influence the state of events Si (e.g we postpone the decision until the economy is booming and the demand is very good) and in each year we do know which state will be realized. The probabilities of the events will remain the same, but repeating the expansion of our business through 100 years (of course in theory only) we make in each year the best decision.Out of 100 years as P (S1 ) = 0.4 the event S1 is realized 40 times, we choose A2 with payoff 26, as P (S2 ) = 0.3 the event S2 is realized 30 times, we choose A2 with payoff 12, as

P (S3 ) = 0.2 the event S3 is realized 20 times, we choose A1 with payoff 8, as P (S4 ) = 0.1 the event S4 is realized 10 times, we choose A3 with payoff 5, the average payoff for one year is 26 · 0.4 + 12 · 03 + 8 · 02 + 5 · 01 = 161 subtracting the expected value of the payoff we get the expected value (payoff ) of perfect information: 16.1 − 138 = 23 We can solve this problem by the Decision Analysis module of the software WinQSB. Source: http://www.doksinet 11 Data entry to the Payoff table analysis problem: The table of solution: 4. Decision trees This is a graphical decision method. A company considers developing two new products. The first alternative A1 is a smoke and fire detector, the estimated development costs is 100000Ft, in case of success the expected increase of the profit is 1000000Ft and the probability of success is 0.5 The second alternative A2 is a motion detector, whose estimated development cost is 10000Ft, in case of success the expected increase of

the profit is 400000Ft and the probability of success is 0.8 Of course there is a third alternative A3 doing nothing (no new product). In a decision tree we have three kind of nodes: (1) decision node (denoted by a square) (2) chance node, from which branches start with probabilities (denoted by a circle) (3) endpoint (denoted by a black dot or triangle) Source: http://www.doksinet 12 The starting node is called root. Starting from the root we draw branches to the right which run into a circle or square. If a branch starts at a circle then we write on it the corresponding probability, and continue until we reach the endpoint. The we calculate the expected values which we write under the chance nodes (circles). Going to the left we write under the decision nodes the smaller expected value. The decision tree of the above problem is shown below. We put the following data in the decision analysis program: Method of solution: first we draw the decision tree by hand, number the nodes,

decide which is decision node which is chance node and also write in the tree the Source: http://www.doksinet 13 probabilities and the payoffs(profits). Next we open the Decision Analysis module of WinQSB then after clicking to File/ New Problem /Decision Tree Analysis a window opens to where we write the name of the problem and give the number of nodes OK. Again a window opens to which we write (using the hand drawn decision tree) the names of the nodes, the branchings, the types of the nodes, the payoffs and probabilities (if any). Next click Solve and Analyse, Draw Decision Tree which opens again a window where we can modify the size of the tree, the nodes the data the program has to calculate. Click OK then the tree will be drawn which we can make nicer modifying the display data. Modification of the previous problem. It turned out that the smoke and fire detector can be sold only after a quality control. The cost of this is 5000Ft After the control the product can obtain three

different quality grade: commercial quality, public quality and not qualified. The probability of obtaining commercial grade is 0.3 and in that case the net income from this product is 1000000Ft, while public grade has probability 0.6 and in this case the net income from this product is only 800000Ft. Probability of no qualification is 1-03-06=01 The data of the modified problem and its decision tree: Source: http://www.doksinet 14 The decision: develop the motion detector. The data window and the decision tree of the business extension problem (dealt with in 3.1) is seen below: Source: http://www.doksinet 15 Source: http://www.doksinet 16 5. Constrained extremum, linear programing Extremum= maximum or minimum Decision variables: x = (x1 , . , xn ) ∈ Rn united into an n-dimensional vector, description of conditions/constrains: by help of given functions gi : Rn R i = 1, . , k + l gi (x) = 0 (i = 1, . , k); k < n constraints of equality type gj (x) ≤ 0 (j = k

+ 1, . , k + l); constraints of inequality type Decision set: set of alternatives gi (x) = 0, i = 1, . , k, ( X= ) x ∈ Rn : gj (x) ≤ 0 j = k + 1, . , k + l Single decision function: f (x) = max ha, x ∈ X Since f (x) = min ⇔ −f (x) = max, if, x ∈ X, it is enough to seek max. Solution: linear or integer programing, finding constrained extremum. Example for linear programing (two variables, graphical solution):(ELOAD1.LPP) x1 , x2 ≥ 0, x1 + 2x2 ≥ 6 x2 − x1 ≤ 3 x1 + x2 ≤ 10 2x1 − 3x2 = z max or min Source: http://www.doksinet 17 Solution: The set of points satisfying the system of inequalities is polygon which is colored in our figure. The straight lines 2x1 − 3x2 = z where z = a constant are parallel lines for different values of z, in our figure the lines for z = 20, 6, −12.5 are drawn. z is maximal if the line passes through the point (100) and minimal if it goes through the point (3.5, 65), zmax = 20, zmin = −125 Source:

http://www.doksinet 18 6. The simplex method In case of several (more than two) variables we can use the simplex methodto solve LP (linear programing) problems. Consider the following LP problem: z = 5x1 + 4x2 + 3x3 = maximum, subject to 2x1 + 3x2 + x3 ≤ 5 4x1 + x2 + 2x3 ≤ 11 3x1 + 4x2 + 2x3 ≤ 8 x1 , x2 , x3 ≥ 0 Introduce the slack variables s1 , s2 , s3 (as the difference between the right and left hand sides of the inequalities. In this way we get the following problem which is equivalent with the original problem: z s1 s2 s3 = 5x1 + 4x2 + 3x3 = maximum, subject to = 5 − 2x1 − 3x2 − x3 = 11 − 4x1 − x2 − 2x3 = 8 − 3x1 − 4x2 − 2x3 x1 , x2 , x3 , s1 , s2 , s3 ≥ 0 s1 , s2 , s3 are called basic variables, while x1 , x2 , x3 are called nonbasic variables. Let us start with the solution x1 = x2 = x3 = 0, then s1 = 5, s2 = 11, s3 = 8 and the value of the decision function is z = 0.Try to find a better solution Since in the decision function the coefficient of

x1 is positive, thus increasing x1 the value of z will increase too. Unfortunately we cannot increase x1 to much, as the slack variables must remain nonnegative. If x1 ≥ 0, x2 = x3 = 0 then all inequalities s1 = 5 − 2x1 ≥ 0 s2 = 11 − 4x1 ≥ 0 s3 = 8 − 3x1 ≥ 0 x1 ≤ 52 = 2.5 x1 ≤ 11 4 = 2.75 8 x1 ≤ 3 = 2.66 have to be satisfied, therefore 0 ≤ x1 ≤ 2.5 or x1 can increase to at most 25 Let therefore 5 1 x1 = , x2 = x3 = 0 then s1 = 0, s2 = 1, s3 = 2 2 5 the value of z increased to 5 · 2 = 12.5 Source: http://www.doksinet 19 How should we continue? Since now s1 = x2 = x3 = 0 the role of x1 is taken over by s1 , the decision function and the inequality conditions should be rewritten corresponding to these. From the definition of s1 we get that x1 = 2.5 − 05s1 − 15x2 − 05x3 , substituting this into the decision function and into s2 , s3 we get that z = 5 (2.5 − 05s1 − 15x2 − 05x3 ) + 4x2 + 3x3 = 12.5 − 25s1 − 35x2 + 05x3 s2 = 11 − 4 (2.5 −

05s1 − 15x2 − 05x3 ) − x2 − 2x3 = 1 + 2s1 + 5x2 s3 = 8 − 3 (2.5 − 05s1 − 15x2 − 05x3 ) − 4x2 − 2x3 = 0.5 + 15s1 + 05x2 − 05x3 Our problem with the new variables is: z x1 s2 s3 = 12.5 − 25s1 − 35x2 + 05x3 = maximum, subject to = 2.5 − 05s1 − 15x2 − 05x3 = 1 + 2s1 + 5x2 = 0.5 + 15s1 + 05x2 − 05x3 s1 , x2 , x3 , x1 , s2 , s3 ≥ 0 We can read from this that for s1 = x2 = x3 = 0 we get x1 = 2.5, s2 = 1, s3 = 05 and z = 12.5 In the decision function only the coefficient of x3 is positive, increasing x3 will increase the value of z. How much can we increase x3 ? Since x3 ≥ 0, s1 = x2 = 0 from the inequalities x1 , s2 , s3 ≥ 0 we get that x1 = 2.5 − 05x3 ≥ 0 x3 ≤ 5 s2 = 1 ≥ 0 this is satisfied for all x3 s3 = 0.5 − 05x3 ≥ 0 x3 ≤ 1 therefore x3 = 1 s3 = 0 and s1 = x2 = 0, the decision function increases by 0.5 · 1 = 05 to 13 The new nonbasic variables are s1 , x2 , s3 , the role of x3 is taken over by s3 . From the equation s3 = 05 + 15s1

+ 05x2 − 05x3 we get that x3 = 1 + 3s1 + x2 − 2s3 , Source: http://www.doksinet 20 substituting this into z, x1 , s2 (please check yourself) we get our problem with the new variables: z x1 s2 s3 = 13 − s1 − 3x2 − s3 = maximum, subject to = 2 − 2s1 − 2x2 + s3 = 1 + 2s1 + 5x2 = 1 + 3s1 + x2 − 2s3 s1 , x2 , s3 , x1 , s2 , x3 ≥ 0 Now there is no positive coefficient in z, we cannot increase z anymore. We have s1 , x2 , s3 ≥ 0 therefore z = 13 − s1 − 3x2 − s3 ≤ 13, but with s1 = x2 = s3 = 0 (while x1 , s2 , x3 can be calculated from the previous formulae) we get z = 13 thus the maximal value of is z = 13. The simplex tableau of the preceding problem (after the introduction of the slack variables s1 , s2 , s2 ) 2x1 + 3x2 + x3 + s1 4x1 + x2 + 2x3 + s2 3x1 + 4x2 + 2x3 + s3 −5x1 − 4x2 − 3x3 + z =5 = 11 =8 =0 (where x1 , x2 , x3 , s1 , s2 , s3 ≥ 0 and we look for the maximum of z) consist of the coefficient matrix: x1 x2 x3 s1 2 3 1 s2 4 1 2 s3 3 4 2 z

−5 −4 −3 s1 1 0 0 0 s2 0 1 0 0 s3 0 0 1 0 5 11 8 0 The notation of rows and columns and the decision function and the numbers on the right hand sides are separated by one-one line segments. 1st step. First we find the pivot element, the entering and leaving(dropping) variables We choose the ”most negative” element (that is the negative element of largest absolute value) in the last line this is −5 in our example. If there are more such element then we can choose any of them. The column of the chosen element will be the pivot column. Then we divide each element of the last column by the corresponding element of the pivot column (we divide only by Source: http://www.doksinet 21 positive elements), the rations will be written after the last column: x1 x2 x3 s1 s2 s3 h. s1 2 3 1 1 0 0 5 5 2 s2 4 1 2 0 1 0 11 11 4 s3 3 4 2 0 0 1 8 8 3 z −5 −4 −3 0 0 0 0 = 2.5 pivot row = 2.75 = 2.66 We find the smallest ration (it there are more

smallest ratio the we choose any of them) the row of this element will be the pivot row. In our example the smallest ration is 2.5 in the first row, thus the pivot row is the first one The pivot element is the element in the pivot row and the pivot column, in our example the element 2. The entering variable is the variable corresponding to the pivot column (in our case x1 ), the leaving variable is the one corresponding to the pivot row (in our case s1 ). 2nd step. Next comes the pivoting First we divide the elements of the pivot row by the pivot element: x1 x2 x3 s1 s2 s3 h. s1 1 1.5 05 05 0 0 2.5 5 2 s2 4 1 2 0 1 0 11 11 4 s3 3 4 2 0 0 1 8 8 3 z −5 −4 −3 0 0 0 0 = 2.5 pivot row = 2.75 = 2.66 then subtracting suitable multiples of this row from the other rows we make all elements of the pivot column (except the pivot element) zero. In our example four times the first row is deducted from the second row, three times the first row is deducted

from the third row, finally fifth times the first row should be added to the last row. Source: http://www.doksinet 22 The name of the leaving variable is replaced by the name of the entering variable. The table obtained in this way is x1 x2 x3 s1 s2 x1 1 1.5 0.5 0.5 0 0 2.5 s2 0 −5 0 −2 1 0 s3 0 −0.5 0.5 −15 0 1 0.5 0 0 12.5 z 3.5 −05 0 2.5 s3 1 Next we repeat steps 1 and 2 until all elements of the last row become nonnegative or zero. Then the optimal solution can be read from the column on the right hand side. In our table the column of -0.5 will be the pivot column, the pivot row will be given again the row of smallest ratio of the corresponding elements of the last column and the pivot column (we divide only by positive elements). In our case the pivot raw is the third one. The entering variable in the one corresponding to the pivot column (in our case x3 ), the leaving variable is he one corresponding to the pivot row (in our case s3

) x1 x2 x3 s1 s2 x1 1 15 0.5 0.5 0 0 2.5 2.5 0.5 s2 0 −5 0 −2 1 0 − s3 0 −0.5 0.5 −15 0 1 0.5 0 0 12.5 z 0 3.5 −05 2.5 s3 h. 1 0.5 0.5 =5 = 1 pivot row We divide the third row by 0.5 and deduct from the last row, and also deduct its multiple by 0.5 from the first row The table obtained (omitting the ratios of the Source: http://www.doksinet 23 last column) is x1 x2 x3 2 s3 0 −1 2 1 s2 0 −5 0 −2 1 0 1 x3 0 −1 1 −3 0 2 1 0 0 0 1 13 3 0 s2 x1 z 2 s1 1 Since in the last column there are no negative elements, the solution process ended. The maximal value of z is 13, and the optimal values of the variables in the left side column can be read from the z column, thus in our case x1 = 2, s2 = 1, x3 = 1 the optimal values of the other variables is zero, i.e x2 = s1 = s3 = 0 Remarks. The method above is the so called primal simplex method which can be applied to the solution of standard normal maximum

problems. Such problems have the form c1 x1 + c2 x2 + · · · + cn xn = z max subject to the conditions a11 x1 + a12 x2 + · · · + a1n xn ≤ b1 , a21 x1 + a22 x2 + · · · + a2n xn ≤ b2 , . . ak1 x1 + ak2 x2 + · · · + akn xn ≤ bk , x1 ≥ 0, x2 ≥ 0, . , xn ≥ 0, where, x = (x1 , . , xn )> ∈ Rn×1 is the unknown n dimensional (column) vector/matrix 0 = (0, , 0)> ∈ Rn×1 , is the n dimensional zero vector, A = (aij ) ∈ Rk×n is a given k × n type matrix, b = (b1 , . , bk )> ∈ Rk×1 is a given k dimensional (column) vector/matrix with nonnegative entries c = (c1 , . , cn )> ∈ Rn×1 is a given n dimensional row vector with nonnegative entries (we may assume that there is at least one positive cj ). Source: http://www.doksinet 24 Next we show the solution of the previous LP problem z = 5x1 + 4x2 + 3x3 2x1 + 3x2 + x3 4x1 + x2 + 2x3 3x1 + 4x2 + 2x3 x1 , x2 , x3 = maximum, subject to ≤5 ≤ 11 ≤8 ≥0 by help of the WinQSB software.

The problem data (in matrix form) and the table of solution are: (five variables, solution with WinQSB ):(ELOAD1B.LPP) Source: http://www.doksinet 25 x1 , x2 , x3 , x4 , x5 ≥ 0, x1 + 2x3 − 2x4 + 3x5 x1 + 3x2 + x3 + x5 x2 + x3 + x4 2x1 + 2x3 ≤ 60 ≤ 12 ≤ 10 ≤ 20 3x1 + 4x2 + 5x3 + 3x4 − 2x5 = z max vagy min Data entry in matrix form into WinQSB: The table of solution: Source: http://www.doksinet 26 In this table the reduced cost enters with decision variables with zero optimal value. It shows how the value of the decision function changes if we require positive value for the variable. For example at x3 = 0 the reduces cost is −1, which means that requiring x3 ≥ a3 (> 0) (instead of x3 ≥ 0) results in increasing the optimal value of the decision function (approximately) by (−1) · a3 . The shadow price appearing at a constraint shows how the change of the constant on the right hand side of the constraint influences the optimal value of the decision

function. For example at the constraint C3 the shadow price is 3, which means that increasing the right hand side of C3 by b3 (in our case to 10 + b3 ) the optimal value of the decision function will (approximately) increase by 3 · b3 . The upper 1-5 rows of the last two column show that between which bounds may the coefficient of the variable in the decision function change in order that the LP problem still has optimal solution. The last 4 rows of last two column show that between which bound may the right hand sides of the constraints change in order that the LP problem still has optimal solution. Further remarks: LP problems may have several solution. As an example consider the problem (ELOAD2.LPP) x1 , x2 , x3 , x4 ≥ 0 x1 − x2 + x3 ≤ 8 x2 + x3 − x4 ≤ 11 x1 + 2x2 − x3 + x4 ≤ 10 z = 6x1 + 2x2 + 5x3 + 7x4 max . This has two basis solutions (0, 0, 8, 18) and (0, 7, 15, 11) and obviously their convex combinations, i.e λ(0, 0, 8, 18) + (1 − λ)(0, 7, 15, 11) with

arbitrary λ ∈ [0, 1] are solutions as well. Source: http://www.doksinet 27 It may happen that the LP problem has no solution, an example for this is the LP problem (ELOAD3.LPP) x1 , x2 ≥ 0 x1 + x2 ≤ 120 x1 ≤ 90 12x1 + 12x2 ≥ 1680 z = 14x1 + 6x2 max