Linear Programming Methods

From Teachwiki
Jump to: navigation, search

Abstract[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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.

Figure 1: Diet Problem


The following food is available.


Food 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
Table 1: Indegrients of food

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 3x_{1}+12x_{2}+13x_{3}+9x_{4}+20x_{5}+19x_{6}\,

subject to:

100x_{1}+205x_{2}+160x_{3}+160x_{4}+420x_{5}+260x_{6}\geq 2000\,

4x_{1} \ \ \ + \   32x_{2}  +   13x_{3}+ \ \ \ \ \ 8x_{4}+ \ \ 4x_{5} \ + \ 14x_{6}\geq 55\,

2x_{1} \ \ \ + \ 12x_{2} \ +  54x_{3} \ +  285x_{4}+ \ 22x_{5} \ + 80x_{6}\geq 800 \,


0 \leq x_{1}\leq  4 Oatmeal =  x_{1} \,

0 \leq x_{2}\leq  3 Chicken = x_{2} \,

0 \leq x_{3}\leq  2 Eggs = x_{3} \,

0 \leq x_{4}\leq  8 Whole milk = x_{4} \,

0 \leq x_{5}\leq  2 Cherry pie = x_{5} \,

0 \leq x_{6}\leq  2 Pork with beans = x_{6} \,

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[edit]

maximize \sum_{j=1}^{n}c_{j}x_{j}\,

subject to:

\sum_{j=1}^{n}a_{ij}x_{j}<b_{i} (i= 1,2,....m\,)

x_{j}>0\, (j=1,2,...n\,)

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 n\, of the n + m\, 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: 5x_{1}+4x_{2}+3x_{3}\,

subject to:

2x_{1}+3x_{2}+x_{3}\leq  5

4x_{1}+x_{2}+2x_{3}\leq 11

3x_{1}+4x_{2}+2x_{3}\leq  8

x_{1},x_{2},x_{3}\geq 0


In general, it holds if coefficients c_{1},c_{2},......,c_{n}\, take real values than is function f of variables x_{1},x_{2},.....,x_{n}\, given by f(x_{1},x_{2},....,x_{n}
)=c_{1}x_{1}+c_{2}x_{2}+....+c_{n}x_{n}=\sum_{j=1}^{n}c_{j}x_{j} a linear function. If f is a linear function and b a real number than equation f(x_{1},x_{2},....,x_{n})=b\, is called a linear equation and the inequality f(x_{1},x_{2}
,....,x_{n})\leq b or f(x_{1},x_{2},....,x_{n}) \geq  b\, linear unequality.

Simplex Algorithmus[edit]

Figure 2: Solution Space in a Convex Polyeder

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 b_{i} 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[edit]

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 max\, 20x_{1}+30x_{2}\mid x_{1}\leq 60,x_{2}\leq 50,x_{1}+2x_{2}\leq 120. The idea of naive simplex is to introduce so called slack variables s_{i}\, to obtain a system of equalities instead of inequalities. The task is to find positive numbers for the variables x_{1},x_{2},s_{1},s_{2},s_{3}\, , therefore equalities (1)-(3)\, must hold and the objective value z\, 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 x_{1}\, and x_{1}\, to 0\,) w^{(0)}=( x_{1},x_{2},s_{1},s_{2},s_{3})=(0,0,60,50,120)\, and a objective value z=0\,.


(1)\, s_{1}=60-x_{1}\,

(2)\, s_{2}=50-x_{2}\,

(3)\, s_{3}=120-x_{1}-2x_{2}\,

z = 0+ 20x_{1}+30x_{2}\,


x_{1},x_{2},s_{1},s_{2},s_{3}>0\,


Before the first iteration we choose a entering variable x_{1},x_{2}\, and a leaving variable s_{1},s_{2},s_{3}\, from equalities (1)-(3)\, As rule of thumb we choose an entering variable which promises the biggest increase of objective value z\,. In this example x_{2}\,. Equation (2)\, is changed to x_{2}\, and than pluged in the objective function and the relevant constraints. The first iteration begins. The so called "Dictionary" looks as follows....


(1)\, s_{1}=60-x_{1}\,

(2)\, x_{2}=50-s_{2}\,

(3)\, s_{3}=20-x_{1}+2s_{2}\,

z = 1500+ 20x_{1}-30s_{2}\,


x_{1},x_{2},s_{1},s_{2},s_{3}>0\,


We can see that the objective values has increased to z=1500. The vector of basis and nonbasisvariables is w^{(1)}=(0,50,60,0,20)\,. For the second iteration we choose x_{1}\, as entering variable. Equation (3)\, is rearranged to x_{1}\, and put into objective function and relevant constraints. it leads to...


(1)\, s_{1}=40-2s_{2}+s_{3}\,

(2)\, x_{2}=50-s_{2}\,

(3)\, x_{1}=20+2s_{2}-s_{3}\,

z = 1900+ 10s_{2}-20s_{3}\,


We can see that the objective values has increased to z=1900. The vector of basis and nonbasisvariables is w^{(2)}=(20,50,40,0,0)\,. For the third iteration we choose s_{2}\, as a entering variable. Equation (1)\, is rearranged to s_{2}\, and put into objective function and relevant constraints. it leads to...


(1)\, s_{2}=20-0.5s_{1}+0.5s_{3}\,

(2)\, x_{2}=30+0.5s_{1}-0.5s_{3}\,

(3)\, x_{1}=60-s_{1}\,

z = 2100 -5s_{1}-15s_{3}\,


We can see that the objective values has increased to z=2100. The vector of basis and nonbasisvariables is w^{(3)}=(60,30,0,20,0)\,. Through there are no more variables which have a positiv increase to objective function the algortihm terminates. Maximum objectiv value is z = 2100 for x_{1}=60 and x_{2}=30. Due there is a slack positiv slack in s_{2} we haven't used all the resources of x_{2}. But under given circumstances no better solution can be found.

Duality[edit]

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 \sum_{j=1}^{n}c_{j}x_{j}\,

subject to:

\sum_{j=1}^{n}a_{ij}x_{j}<b_{i} (i= 1,2,....m\,)

x_{j}>0\, (j=1,2,...n\,)


minimize \sum_{i=1}^{m}b_{i}y_{i}\,

subject to:

\sum_{i=1}^{m}a_{ij}y_{i}<c_{j} (i= 1,2,....n\,)

y_{i}>0\, (j=1,2,...m\,)


Table 2: Equivalence of Primal and Dual Problem

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[edit]

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 m<50 and m+n<200 the number of iterations is usually under  3m/2. Danzig stated that the number of iterations increases proportionally to the numbers of constraints m but only slowly increases with the number of variables n. For a fix number of constraints the number of iterations increases only logarithmic with the number of variables n. 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).

m  /  n 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
Tabelle 3: Numbers of iterations

Limit of standard Simplex[edit]

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:

 max \ 28x_{1}+81x_{3}\mid 18x_{1}+40x_{2}\leq 237,8x_{1}-8x_{2}\leq 23,x_{1}\geq 0,x_{2}\geq0 

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 (x_{1},x_{2})=(6.069, 3.194) with objectiv value z=489.336. The next feasible integer solution would be (x_{1},x_{2})=(5,3). The optimal integer solution therefor is (x_{1},x_{2})=(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[edit]

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.

max \ 5x_{1}+8x_{3}\mid  \ x_{1}+x_{2}\leq 6 , \ 5x_{1}+9x_{2}\leq 45 

The optimal solution found by the simplex is x_{1}=2.25 and x_{1}=3.75. We want to find the optimal integer solution.

Branchandbound.JPG
Figure 4: Branch and Bound


A possibility to overcome this is the so called branch-and-bound method. The main idea is to solve a sequence of linear programms while looking for integer solutions. The branch-and-bound 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
 RE-INSTALLING 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[edit]

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.

Vortrag numerical.jpg
Figure 5: Fictive Hub and Spoke Network


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 (London-Singapure and Singapure-Sydney). 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.

Emirates Hub and 81 Spoke.JPG


Figure 6: Hub and Spoke Network in Real World


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 Origin-Destination-Fare. You can combine your spoke cities to certain Combinations which have up to 3 different Fares. E.g London-Bukarest-First_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.

Vortrag numerica2l.jpg

Find the optimal contingents for every possible Origin-Destination-Fare 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[edit]

Traveling Salesman Problem[edit]

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.

Vortrag numerical3.jpg
Figure 7: Traveling Salesman Problem


This problem sounds very easy but there are exact algorithms which can solve this problem for up to 40-120 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.

Vortrag numerical4.jpg
Figure 8: Paths Traveling Salesman

Short Conclusions[edit]

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[edit]

  • 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[edit]

#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;