Linear Programming Methods
Inhaltsverzeichnis
 1 Abstract
 2 Introduction
 3 Linear Programs in Standard Form
 4 Simplex Algorithmus
 5 Naive Simplex Algorithm
 6 Duality
 7 How fast is the Simplex Method
 8 Limit of standard Simplex
 9 Integer Programming
 10 Airline Revenue and Capacity Management
 11 Limitations of Linear Programming
 12 Short Conclusions
 13 References
 14 Appendix
Abstract
In this thesis I will write about theory and application of linear programming methods. The focus will lie on practical problems. The work is related to the numerical introductory course in Winter term 2006/07 held by Prof. Dr. Wolfgang Härdle and Dr. Sigbert Klinke
Introduction
Linear Programming is a branch of mathematical optimization. Other branches of mathematical optimization are nonlinear, discrete, combinatoric und dynamic optimization. Mathematical optimization in generel, simulation techniques, data analysis and forecasting, queue theory as well as decicion and game theory form the field of Operations Research. Operations Research is a science, which deals with development of models, mathematical scheduling and building up algorithms to solve real world and theoretical problems. Fields of application are mainly economic science as well as physics, mathematics and engineering science.
Historical Background
Operations Research was developed in Great Britain and the USA during World War II. From 1940 scientists from different branches (mainly mathematics and physics) were integrated in so called Operations Research Groups. They worked on strategic military procedures like optimal use of radar, mathematical analysis of Uboot defence or optimal combination of ship convoys and bomber squadron. These academic groups had so much success that after end of the war there techniques became interesting for companies.
Applications in Economic Science
Methods from Operations Research and linear programming are principal used in producing industries. The application field is from purchasing raw material to optimal logistics, repairs and depreciation, management of production to work flow management. The main field is the planning of networks, production governing, tansportation and location problems, optimal use of plant and machinery or capacity planning and revenue management. Since last decades OR techniques has become standard in industry, finance and insurance, retail, health care and public administration. You can understand the methods without computer knowledge but to solve big problems it is not possible to solve problems by hand. A linear programm can easily have up to a million variables and constraints. Popular software for solving linear programms are AMPL, SAS, Lindo, Lingo, R.
Diet Problem  An Introductory Example
The idea of the diet problem is to find the cheapest combination of foods that will satisfy all the daily nutritional requirements like energy, proteins, minerals demand. The problem can be formulated as a linear program where the objective is to minimize cost and meet constraints which require that nutritional needs be satisfied. We include constraints which control the number of energy proteins, calciums and the number of servings. For simplicity we assume that vitamins depend on pills.
 Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
 Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
 Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
 Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
 Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
 Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Energy(kcal)  Protein(g)  Calcium(mg)  Price (cents)  max servings  

Oatmeal  110  4  2  3  4 
Chicken  205  32  12  24  3 
Eggs  160  13  54  13  2 
Whole milk  160  8  285  9  8 
Cherry Pie  420  4  22  20  2 
Pork with beans  260  14  80  19  2 
A verbal formulation could look like this.
Minimize the total "cost of servings" subject to the nutrition requirements: take enough but not too much Energy . . eat enough but not too much Calcium take not more than maximum number of servings. end.
We have to minimize the costs and satisfy our nutrition constraints therefore a small LP could look like this.
minimize
subject to:
Oatmeal =
Chicken =
Eggs =
Whole milk =
Cherry pie =
Pork with beans =
Lindo Code minimize 3x1+12x2+13x3+9x4+20x5+19x6 subject to 100x1+205x2+160x3+160x4+420x5+260x6>2000 4x1+32x2+13x3+8x4+4x5+14x6>55 2x1+12x2+54x3+285x4+22x5+80x6>800 x1<4 x2<3 x3<2 x4<8 x5<2 x6<2 LP OPTIMUM FOUND AT STEP 5 OBJECTIVE FUNCTION VALUE 1) 94.75000 VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X2 0.000000 0.468750 X3 0.000000 4.000000 X4 4.750000 0.000000 X5 2.000000 0.000000 X6 0.000000 4.375000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.056250 3) 7.000000 0.000000 4) 605.750000 0.000000 5) 0.000000 2.625000 6) 3.000000 0.000000 7) 2.000000 0.000000 8) 3.250000 0.000000 9) 0.000000 3.625000 10) 2.000000 0.000000 NO. ITERATIONS= 5
For cost minimal nutrition we have to consume 3 portions of oatmeal, drink 5 glasses of milk and eat two pieces of cherry cake. It will costs us about 95 cents. Lindo found the optimal solution after 5 iterations but what is behind linear programming and which kind of algorithms are use? Of course another way can be to use some trial and error aproach to find this cost minimal combination or evaluate all possible combinations or start some monte carlo simulation but this is no alternative for large scale problems.
Linear Programs in Standard Form
maximize
subject to:
()
()
Linear problems of this structure are called LP programs in standard form. What does a LP in standard form characterize? First, all constraints and the objective function are linear and the last of the contraints are the so called nonnegative constraints. To simplify calculation problems should be stated like that. It is still possible to transform any feasible LP in a LP in standard form. (e.g transform minimization problem into a maximization problem or multiply desired contraints through by 1)
Example 1.)
maximize:
subject to:
In general, it holds if coefficients take real values than is function f of variables
given by a linear function. If f is a linear function and b a real number than equation
is called a linear equation and the inequality or
linear unequality.
Simplex Algorithmus
The Simplex algorithm is the most important method solving linear programms. A linear programm can be solved in a number of finite steps, or can not be solved because it is unbounded, badly formulated or simply unfeasable. The idea is very easy. The solution space from a high dimensional LP, bounded through a number of constraints can be seen as a convex polyeder. Every corner point therefor can be a optimal solution itself. The idea is to start from a certain corner point and than evalutate the neigbour corner points for its objectiv value. This is much faster than e.g evaluation all combinations of input variables. If a corner point can be found which has an higher objective value the procedure is repeated until this converges to a maximum value. The simplex algorithm is searching on the edge of the polyeder until an optimal solution is found. The gain is obvious. For optimal case the simplex just evaluates a few cornerns. In the worst case it has to evaluate all corners and needs exponential time. For the most real world problems the simplex is faster than any know methods. For very large problem the so called interior point or barrier methods methods are faster. An additional pro is also that if an optimal solution has been found adding new constraints or changing the RHS values doesn't require solving the whole optimization problem again. The simplex takes a "warm start" from the old optimal solution which requires less iterations. This algorithm is implemented in the most solvers through simple matrix algebra. In the next section I want to show you how a naive simplex method works and leads to numerical solutions. It allows us to solve small problems.
Naive Simplex Algorithm
Before I give you some examples I want to mention some theory. If you have stated a LP in standard form and objective function as well as contraints are linear there are algorithms to solve the problem. The idea is to find an algorithm which can solve the problem efficient in less steps and in addition gives some further information we can use for economic interpretation. We consider our example . The idea of naive simplex is to introduce so called slack variables to obtain a system of equalities instead of inequalities. The task is to find positive numbers for the variables , therefore equalities must hold and the objective value has to be a maximum value and slack as small as possible. Before the first iteration we obtain the vector of basis and nonbasisvariables where first two entries are basis and the last three nonbasis.(in the beginning we haven't an idea which are the optimal values we set and to ) and a objective value .
Before the first iteration we choose a entering variable and a leaving variable from equalities
As rule of thumb we choose an entering variable which promises the biggest increase of objective value . In this example . Equation is changed to and than pluged in the objective function and the relevant constraints. The first iteration begins. The so called "Dictionary" looks as follows....
We can see that the objective values has increased to z=1500. The vector of basis and nonbasisvariables is
. For the second iteration we choose as entering variable. Equation is rearranged to and put into objective function and relevant constraints. it leads to...
We can see that the objective values has increased to z=1900. The vector of basis and nonbasisvariables is
. For the third iteration we choose as a entering variable. Equation is rearranged to and put into objective function and relevant constraints. it leads to...
We can see that the objective values has increased to z=2100. The vector of basis and nonbasisvariables is . Through there are no more variables which have a positiv increase to objective function the algortihm terminates. Maximum objectiv value is z = 2100 for and . Due there is a slack positiv slack in we haven't used all the resources of . But under given circumstances no better solution can be found.
Duality
In optimization theory, the duality principle states that optimization problems may be viewed from both of two perspectives, the primal problem or the dual problem. It was discoverd by the famous mathematician John von Neumann in 1947. It states that in the linear case there is a direct computational equivalence between the solution to the primal problem and the solution to the dual problem. An example is given over here.
Primal Problem  Dual Problem 

maximize
subject to: () ()

minimize
subject to: () ()

There is no difference whether you solve the primal or the dual problem. For large scale problems with many contraints and less variables it can be easier to solve the dual problem. See also next section.
Primal Problem  Dual Problem 

Lindo Code max 20x1+30x2 subject to x1 <60 x2 <50 x1+2x2<120 end LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 2100.000 VARIABLE VALUE REDUCED COST X1 60.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 5.000000 3) 20.000000 0.000000 4) 0.000000 15.000000 NO. ITERATIONS= 3 
Lindo Code min 60y1+50y2+120y3 subject to y1+y3>20 y2+2y3>30 end LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 2100.000 VARIABLE VALUE REDUCED COST Y1 5.000000 0.000000 Y2 0.000000 20.000000 Y3 15.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 60.000000 3) 0.000000 30.000000 NO. ITERATIONS= 2 
Figure 3: Duality
We can interprete the output of the primal as follows. We have a slack of 20 for the second constraint. Dual prices: If we would have one unit more of slack (ressources) for the first constraint we could increase the objective 5 units. Therefor we would not pay more than 5 Euro to buy this resource. If we would have one more unit of contraint three we could increase objectiv (profit) 15 units.
How fast is the Simplex Method
In this section I will shorty mention the speed of the simplex method and especially the number of iterations needed to find the optimal solution. Dantzig (1963) stated that for and the number of iterations is usually under . Danzig stated that the number of iterations increases proportionally to the numbers of constraints but only slowly increases with the number of variables . For a fix number of constraints the number of iterations increases only logarithmic with the number of variables . Theoretical results give Dantzig (1980) und Smale (1982). Kuhn und Quandt (1963) give results through Monte Carlo Simulation. The following information has been taken from Chvatal (1983).
10  20  30  40  50  

10  9.4  14.2  17.4  19.4  20.2 
20  25.2  30.7  38.0  41.5  
30  44.4  52.7  62.9  
40  67.6  78.7  
50  95.2 
Limit of standard Simplex
The optimal solution of an LP are often no integers. An rounding to the nearest feasible interger solution is not neccessary an optimum. It generell the optimal integer solution can be found close the noninteger but you need to check this to avoid a nonoptimal solution.
Proof by example:
The first contraint can be seen as a resource contraint. For the second contraint you can imagine e.g a machine which can not produce a lot more from the first than from the second product. Think for example production of gas from oil. You get the following "optimal" solution =(6.069, 3.194) with objectiv value z=489.336. The next feasible integer solution would be =(5,3). The optimal integer solution therefor is =(2,5). This shows that simplex is not reliabel finding optinmal integer solutions. This means we need an advanced algorithm. Integer solutions are needed e.g in Network programming, optimal combination of freight or solving contingent problems.
Integer Programming
In economic science integer solutions are very important. You can't produce half cars or sell a 1/6 seat in a plane. An algorithm is need which gives direcly integer solutions. I want you to give you the idea by the following example.
The optimal solution found by the simplex is and . We want to find the optimal integer solution.
A possibility to overcome this is the so called branchandbound method. The main idea is to solve a sequence of linear programms while looking for integer solutions. The branchandbound procedure requires two tools. The first one is to partion the feasible region in several smaller feasible subregions. This is called branching, since the procedure may be repeated to each of the subregions and all produced subregions naturally form a tree structure, called search tree. The other tool is bounding, which is a fast way of finding upper and lower bounds for the optimal solution within a feasible subregion. In this example we branch the search tree down while bounding for the other variable and vice versa. If the integer solution is close to the nonintersolution this will take not very long. But if the difference is big this will needs some time. For more than 2 variables its already computational intensive.
Lindo Code max 5x1+8x2 subject to x1+x2<6 5x1+9x2<45 end gin x1 gin x2 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE VALUE = 41.2500000 SET X2 TO >= 4 AT 1, BND= 41.00 TWIN= 39.00 7 SET X1 TO <= 1 AT 2, BND= 40.56 TWIN=0.1000E+31 9 SET X2 TO >= 5 AT 3, BND= 40.00 TWIN= 37.00 12 NEW INTEGER SOLUTION OF 40.0000000 AT BRANCH 3 PIVOT 12 BOUND ON OPTIMUM: 40.00000 DELETE X2 AT LEVEL 3 DELETE X1 AT LEVEL 2 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 3 PIVOTS= 12 LAST INTEGER SOLUTION IS THE BEST FOUND REINSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) 40.00000 VARIABLE VALUE REDUCED COST X1 0.000000 5.000000 X2 5.000000 8.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 1.000000 0.000000 3) 0.000000 0.000000 NO. ITERATIONS= 12 BRANCHES= 3 DETERM.= 1.000E 0
Airline Revenue and Capacity Management
An important application for linear programming is the capacity management. It is used in hotels, mobile phone companies, power market, car rentals, or railway companies. The idea is to sell a product which has fixed capacities, cannot be stored, has low marginal costs, a fluctuating demand, and low marginal cost. The trade off is between selling it in advance for a low price or keeping capacities and sell it later for a higher price. This is a typical problem for linear programming. In the airline sector this is used nearly in every company. The airlines have high fixed cost and the tickets expire with the flight issued. The methods of capacity planning are capacity control and overbooking control. The idea of overbooking control is simply to sell more tickets than seats are available because empirical can be shown that up to 20% of the passengers do not show up. There is also a tradeoff from having not sold out the plane or having unsatisfied customers which are denied boarding. Within capacity control the hole capacity of a plane is divided into subcapacities, so called contingents for the booking classes. A service class (economy, business, first) is devided in up to 12 booking classes. E.g for early bookings, last minute contingents, contingents for travel agencies. This has to be done in a revenue maximizing way. This is the first problem. Having 3 Service classes and 12 booking classes you have up to 36 different price classes in a plane. The customer next to you could only payed half the price form you. The problem becomes more complex if we allow booking more for than one leg.
A leg is a simply a connection from one city to another. The low cost carrier just allow for booking a single leg. If you fly with a quality airline you want to fly e.g. from London to Syney via. Singapure and pay just one price while use 2 units of capacity (LondonSingapure and SingapureSydney). Based on these information linear programming can be used to make the best decisions selling capacities in different time, for different prices and in different quantities.
The network is usually in a form called hub and spoke network which has usually a hub city which is the home of the airline e.g Lufthansa in Frankfurt. The spoke cities are the cities the airline is in service with. So a plane operating from Frankfurt to Hamburg is not occupied usually only by passengers from Frankfurt but also passengers coming from all the other spoke cities interchanging in Frankfurt. For the Airlines operation in Alliances with Code Sharing this optimization problem is more complex. There are so called ODF Combinations which means OriginDestinationFare. You can combine your spoke cities to certain Combinations which have up to 3 different Fares. E.g LondonBukarestFirst_Class. I used fictiv demand and prices and created a linear programm from figure 3. The idea is to find optimal contingents for the different booking classes. For simplicy I used just 3 booking classes not to be mixed with the service classes. We have 7 planes operation on this network which are 14 return flights. In this small model we have already 56 OD Combinations (8x7) with 3 diffent booking classes = 168 ODF Combinations we have to assign capacity. The planes operating have capacity from 100 to 200. The Optimization model looks as follow.
Find the optimal contingents for every possible OriginDestinationFare Combination subject to the contraint capacity it uses over all legs. The solution should be integer. If for an certain combination the contingent is zero it is not offered in the booking system. The model and the data can be found in the appendix. I want to present shorty some results.
Maximum Revenue von 567.400 Presolve eliminates 168 constraints. Adjusted problem: 168 variables, all linear 14 constraints, all linear; 294 nonzeros 1 linear objective; 168 nonzeros. MINOS 5.5: MINOS 5.5: optimal solution found. 68 iterations, objective 567400 display Sitz ; Sitz [*,*]: Class1 Class2 Class3 BUK_LON 50 5 0 BUK_MAD 40 0 0 BUK_PAR 30 0 0 BUK_ROM 25 0 0 LON_BUK 50 10 0 LON_MAD 30 0 0 LON_MOS 40 0 0 LON_PAR 60 10 0 MAD_BUK 30 20 0 MAD_LON 80 0 0 MAD_MOS 5 0 0 MAD_STO 25 0 0 MOS_MAD 20 0 0 MOS_PAR 45 0 0 MOS_ROM 35 0 0 MUC_BUK 15 0 0 MUC_MOS 25 0 0 MUC_ROM 20 0 0 PAR_LON 65 0 0 PAR_MOS 30 0 0 PAR_STO 50 35 0 ROM_MUC 30 30 0 ROM_STO 60 0 0 STO_BUK 25 0 0 Dual Prices for the capacities: display kapazität ; kapazit?t [*] := BUKMUC 330 LONMUC 170 MADMUC 300 MOSMUC 340 MUCBUK 150 MUCLON 240 MUCMAD 280 MUCMOS 160 MUCPAR 220 MUCROM 160 MUCSTO 330 PARMUC 250 ROMMUC 180 STOMUC 320;
The expected prices for class 1 was maybe chosen a bit to optimistic but since there is no uncertainty in this little model capacity is assigned to expensive classes and just 24 OD Combinations. The dual prices also called opportunity costs which I have mentioned in the beginning of the thesis has a now a nice interpration. It has to be at least paid this price no matter what booking class to get a ticket. When you want to go from London to Moscow you have to pay the opportunity costs for LONMUC + MUCMOS =330 Euro to get a ticket. So if you send a price request to the airline via internet the airline won't sell this for less than 330 Eur. Based on the estimated demand the airline could sell it anyway for this price (Opportunity Price). In practice tickets are sold up to one year before the flight appears. The airline starts with an estimated model (more stochastic) and than update this consequently with new requests. If one booking has taken place a new model is estimated and the new dual price for an ODF is estimated. Prices are therefor very dynamic. If a customer sends an request he has to pay at least this dual price. Usually if departure approaches prices rises.
Limitations of Linear Programming
Traveling Salesman Problem
This is one optimization problem which linear programming methods did not perform well yet. The traveling salesman problem is a problem of discrete or combinatorial optimization. It is a prominent illustration of a class of problems with highest computational complexity. The idea is to find the shortest path starting from a certain city while visiting all cities. It is just allowed to visit a city ones and than coming back to the starting point.
This problem sounds very easy but there are exact algorithms which can solve this problem for up to 40120 cities. (various branch and bound algorithms). Havin 500 cities we have 500! permutations and it would take at least a month on a personal computer to find the optimal solution.
Short Conclusions
Linear Programming can be used for a various number of real world problems. The solution give some nice economic interpretation which can help to make better decisions. But there are also some pitfalls and limitations we have to deal with to avoid losses. In general linear programming is a usefull tool which every economist should be familar.
References
 Vasek Chvatal: Linear Programming. W. H. Freeman and Company, New York, 1983
 Dantzig G. B., Thapa M. N.: Linear Programming, Springer, Berlin, Heidelberg, u.a., 1997
 Dürr W., Kleibohm K.: Operations Research, Lineare Modelle und ihre Anwendungen, 3. Aufl., Hanser, München Wien, 1992
Appendix
#AMPL Code set ROUTEN; set KLASSE; set LEG; set STRECKE{ROUTEN} within LEG; param Preis {ROUTEN,KLASSE} >= 0; param Nachfrage {ROUTEN,KLASSE} >= 0; param Kapa {LEG} >= 0; var Sitz {ROUTEN,KLASSE} >= 0; maximize Gewinn: sum {r in ROUTEN,k in KLASSE} Preis[r,k] * Sitz[r,k]; subject to sitz {r in ROUTEN,k in KLASSE}: Sitz[r,k] <= Nachfrage[r,k]; subject to kapazität {l in LEG}: sum {k in KLASSE} (sum{r in ROUTEN : l in STRECKE[r]} Sitz[r,k]) <= Kapa[l]; set ROUTEN := MUC_ROM MUC_LON MUC_MOS MUC_STO MUC_MAD MUC_PAR MUC_BUK ROM_MUC ROM_LON ROM_MOS ROM_STO ROM_MAD ROM_PAR ROM_BUK LON_MUC LON_ROM LON_MOS LON_STO LON_MAD LON_PAR LON_BUK MOS_MUC MOS_ROM MOS_LON MOS_STO MOS_MAD MOS_PAR MOS_BUK STO_MUC STO_ROM STO_LON STO_MOS STO_MAD STO_PAR STO_BUK MAD_MUC MAD_ROM MAD_LON MAD_MOS MAD_STO MAD_PAR MAD_BUK PAR_MUC PAR_ROM PAR_LON PAR_MOS PAR_STO PAR_MAD PAR_BUK BUK_MUC BUK_ROM BUK_LON BUK_MOS BUK_STO BUK_MAD BUK_PAR; set KLASSE := Class1 Class2 Class3; set LEG := MUCROM MUCLON MUCMOS MUCSTO MUCMAD MUCPAR MUCBUK ROMMUC LONMUC MOSMUC STOMUC MADMUC PARMUC BUKMUC; param Kapa := MUCROM 120 MUCLON 200 MUCMOS 100 MUCSTO 170 MUCMAD 160 MUCPAR 180 MUCBUK 150 ROMMUC 120 LONMUC 200 MOSMUC 100 STOMUC 170 MADMUC 160 PARMUC 180 BUKMUC 150; set STRECKE[MUC_ROM] := MUCROM; set STRECKE[MUC_MOS] := MUCMOS; set STRECKE[MUC_LON] := MUCLON; set STRECKE[MUC_STO] := MUCSTO; set STRECKE[MUC_MAD] := MUCMAD; set STRECKE[MUC_PAR] := MUCPAR; set STRECKE[MUC_BUK] := MUCBUK; set STRECKE[ROM_MUC] := ROMMUC; set STRECKE[ROM_LON] := ROMMUC MUCLON; set STRECKE[ROM_MOS] := ROMMUC MUCMOS; set STRECKE[ROM_STO] := ROMMUC MUCSTO; set STRECKE[ROM_MAD] := ROMMUC MUCMAD; set STRECKE[ROM_PAR] := ROMMUC MUCPAR; set STRECKE[ROM_BUK] := ROMMUC MUCBUK; set STRECKE[LON_MUC] := LONMUC; set STRECKE[LON_ROM] := LONMUC MUCROM; set STRECKE[LON_MOS] := LONMUC MUCMOS; set STRECKE[LON_STO] := LONMUC MUCSTO; set STRECKE[LON_MAD] := LONMUC MUCMAD; set STRECKE[LON_PAR] := LONMUC MUCPAR; set STRECKE[LON_BUK] := LONMUC MUCBUK; set STRECKE[MOS_MUC] := MOSMUC; set STRECKE[MOS_ROM] := MOSMUC MUCROM; set STRECKE[MOS_LON] := MOSMUC MUCLON; set STRECKE[MOS_STO] := MOSMUC MUCSTO; set STRECKE[MOS_MAD] := MOSMUC MUCMAD; set STRECKE[MOS_PAR] := MOSMUC MUCPAR; set STRECKE[MOS_BUK] := MOSMUC MUCBUK; set STRECKE[STO_MUC] := STOMUC; set STRECKE[STO_ROM] := STOMUC MUCROM; set STRECKE[STO_LON] := STOMUC MUCLON; set STRECKE[STO_MOS] := STOMUC MUCMOS; set STRECKE[STO_MAD] := STOMUC MUCMAD; set STRECKE[STO_PAR] := STOMUC MUCPAR; set STRECKE[STO_BUK] := STOMUC MUCBUK; set STRECKE[MAD_MUC] := MADMUC; set STRECKE[MAD_ROM] := MADMUC MUCROM; set STRECKE[MAD_LON] := MADMUC MUCLON; set STRECKE[MAD_MOS] := MADMUC MUCMOS; set STRECKE[MAD_STO] := MADMUC MUCSTO; set STRECKE[MAD_PAR] := MADMUC MUCPAR; set STRECKE[MAD_BUK] := MADMUC MUCBUK; set STRECKE[PAR_MUC] := PARMUC; set STRECKE[PAR_ROM] := PARMUC MUCROM; set STRECKE[PAR_LON] := PARMUC MUCLON; set STRECKE[PAR_MOS] := PARMUC MUCMOS; set STRECKE[PAR_STO] := PARMUC MUCSTO; set STRECKE[PAR_MAD] := PARMUC MUCMAD; set STRECKE[PAR_BUK] := PARMUC MUCBUK; set STRECKE[BUK_MUC] := BUKMUC; set STRECKE[BUK_ROM] := BUKMUC MUCROM; set STRECKE[BUK_LON] := BUKMUC MUCLON; set STRECKE[BUK_MOS] := BUKMUC MUCMOS; set STRECKE[BUK_STO] := BUKMUC MUCSTO; set STRECKE[BUK_MAD] := BUKMUC MUCMAD; set STRECKE[BUK_PAR] := BUKMUC MUCPAR; param Preis: Class1 Class2 Class3 := MUC_ROM 160 100 80 MUC_LON 230 160 110 MUC_MOS 200 150 120 MUC_STO 300 270 230 MUC_MAD 280 200 150 MUC_PAR 190 180 170 MUC_BUK 170 140 80 ROM_MUC 250 180 150 ROM_LON 400 360 340 ROM_MOS 300 250 220 ROM_STO 540 360 310 ROM_MAD 230 200 190 ROM_PAR 260 230 200 ROM_BUK 300 240 210 LON_MUC 120 90 70 LON_ROM 300 280 220 LON_MOS 350 290 190 LON_STO 230 200 180 LON_MAD 480 400 370 LON_PAR 410 390 360 LON_BUK 370 320 300 MOS_MUC 140 100 80 MOS_ROM 500 460 410 MOS_LON 400 350 270 MOS_STO 290 200 190 MOS_MAD 620 540 510 MOS_PAR 580 500 450 MOS_BUK 300 280 220 STO_MUC 170 130 120 STO_ROM 520 360 310 STO_LON 470 390 320 STO_MOS 360 290 260 STO_MAD 600 520 490 STO_PAR 540 400 360 STO_BUK 500 380 320 MAD_MUC 270 230 180 MAD_ROM 420 320 300 MAD_LON 570 490 460 MAD_MOS 460 390 360 MAD_STO 660 590 540 MAD_PAR 340 300 270 MAD_BUK 480 450 410 PAR_MUC 240 200 170 PAR_ROM 410 310 280 PAR_LON 590 470 390 PAR_MOS 410 340 310 PAR_STO 610 580 540 PAR_MAD 350 310 280 PAR_BUK 380 360 300 BUK_MUC 300 270 260 BUK_ROM 490 380 360 BUK_LON 690 570 520 BUK_MOS 310 300 280 BUK_STO 650 560 470 BUK_PAR 550 510 490 BUK_MAD 680 560 490; param Nachfrage: Class1 Class2 Class3:= MUC_ROM 30 60 130 MUC_LON 60 80 120 MUC_MOS 25 60 80 MUC_STO 25 80 100 MUC_MAD 60 80 140 MUC_PAR 35 55 75 MUC_BUK 15 45 60 ROM_MUC 30 70 110 ROM_LON 50 80 160 ROM_MOS 40 80 140 ROM_STO 60 90 160 ROM_MAD 40 100 170 ROM_PAR 45 60 80 ROM_BUK 30 50 90 LON_MUC 50 60 160 LON_ROM 30 70 160 LON_MOS 40 80 120 LON_STO 25 60 90 LON_MAD 30 80 180 LON_PAR 60 90 120 LON_BUK 50 80 100 MOS_MUC 30 60 110 MOS_ROM 60 90 130 MOS_LON 40 70 120 MOS_STO 25 70 130 MOS_MAD 60 100 110 MOS_PAR 45 70 90 MOS_BUK 50 90 130 STO_MUC 60 110 130 STO_ROM 40 80 100 STO_LON 60 110 140 STO_MOS 60 80 110 STO_MAD 70 160 170 STO_PAR 35 50 85 STO_BUK 25 45 75 MAD_MUC 50 100 120 MAD_ROM 40 80 140 MAD_LON 80 110 150 MAD_MOS 60 100 120 MAD_STO 25 90 110 MAD_PAR 40 60 70 MAD_BUK 30 50 80 PAR_MUC 50 70 100 PAR_ROM 60 80 120 PAR_LON 65 85 125 PAR_MOS 30 40 70 PAR_STO 50 55 90 PAR_MAD 70 80 100 PAR_BUK 40 55 65 BUK_MUC 30 50 60 BUK_ROM 25 45 65 BUK_LON 50 70 90 BUK_MOS 60 80 100 BUK_STO 40 55 75 BUK_PAR 35 50 65 BUK_MAD 40 70 90;