Operational Research / Investigação Operacional
Linear Programming % = Computation

* Linear Programming

01' • Example [Resnick, exa. 10-1, p 279] fertilizer problem.Pdf (1 Mb), .xlsx or .xlsb, with graph, (Lindo) .ltx, % LP ("revised"), [p 280]%.pdf, % "standard, canonical" (§% via libr.) • Software for LP (CPLEX, Gurobi, etc.) • IBM CPLEX DropSolve

02' • [Sultan].Pdf (1 Mb, pp 2–18, Soln505–507, 26–29, 225–243, 394–403, Soln552–553, 476–481) diet, cars, transportation: Solver Sultan.xlsx, .xlsb; "Mathematica" soln. diet, cars, 1, 2.nb, transport., 3.nb

03' • SAS/OR: Example 7.1 Diet Problem; diet.xlsx, .ltx .lp (source of problem ?) • WinQSB.zip (search)

04' • What is a simplex: [WolfrMW], [Dantzig].Pdf • Explaining the simplex: Zionts.pdf; H&L.pdf  "Wyndor" prb., .nb

05' • Zionts.xlsx; Wyndor & Zionts(2011).xls: feasible region, path of optimization

06' • Ferg. introduction.pdf (pp 25–26); solve.pdf by various software applications.

07' • Prepared data.pdf for (revised simplex %) several of the given LP problems.

08' • Artificial (H&L, Taha) variables.pdf; manually, ZiontsPlus.xlsx (.pdf) • Negative, free variables • Redundant.pdf  ? Impossible.pdf  ?

09' • Excel (and proper form): LP_ResnickManual.xlsx, LP_Bronson04_01to06.xlsx, LP_Bronson04_11to19.xlsx

10' • LP (Ziont's) typical "four types".Pdf : resource allocation.Pdf (28Mb, dog food), blending.pdf (candy shop, not linear?), cutting stock, flow.

11' • LP parallel resolution.pdf : algebraic, tabular, and matrix forms; or, more clearly, see (tableaux) Bronson prb4.3 (below).

12' • • • Applied exa.s:  >>> |[Bronson]| (refinery, juice, etc.)

13' • Revised simplex: % Zionts prb, inverse matrix updating (matrix Zionts.xls prb). • Excel limits: TP_big.xlsx

14' • • • Applied exa.s:  >>> |HPWilliams| (refinery, regression, etc.)

15' • [Craw] Q&A.pdf, machine shop.pdf, blending.pdf (p 4);  A. Alves.xls

16' • [Ecker&Kup.] "Some scientific applications of LP" Q&A.pdf, .xlsx (regression & Excel tricks),  1 .ltx,  2 .ltx

17' • Multiplicity: JLawr.ppsx • multi1.pdf • prb1.6.xls → with 3D graph.xlsx, .ltx (convex linear combination)

18' • Degeneracy and variants (unbounded, impossible): special.zip

19' • Cycling: Strayer.Pdf (2.6 Mb) (anti-cycling), Beale.xls, GassV.ltx (Gass&V.), Strayer.ltx • Efficiency.pdf (MCuturi: Klee-Minty)

20' • Duality [BronNaad].Pdf . Symmetric: Duality'16.zip (Excel+Lindo) • pairDual.xlsx (6 vars. & 2 constrs. vs. 2 & 6)

21' • [Bron.] prb5.2 LP_Bronson.05.02.pdf, LP_Bronson.05.02-QSB.pdf and soln. (tableaux) LP_Bronson.05.02.xlsx;  unsymmetric [Tavares].pdf (QSB)

22' • Exa.s [Desbazeille]: exa. 1.2.ltx, dual.ltx (exa. 1.8.xls, .ltx) • Jam prb. .xls, .xlsx with 0's, .ltx [Ramalhete, 2.16, prb. 14]

23' • • • Applied exa.s:  >>> [Beasley]

24' • Ramalhete sensit..xls • Arsham (search "OPRE315.101"): Game theory (→ =; ex1.ltx) • NEOS: Case Studies

* Transportation Problem

25' • Facility location... (plant location, |at (J. Buescu) Ingenium.pdf|) • Shortest path (Java)

* Integer Programming (recommended link)


* Integer Programming (older) — MILP (branch & bound) [IP_Wolsey95].Pdf, basic exa. (11 pp, 3 Mb), Solver IP_Wolsey95.xlsx, IP_Wolsey95.lp, Wols95.ltx, Wols95ltx.zip & tree, Wols95.lpp • Gurobi MIP basics • MILP: nomenclatura portuguesa.pdf

26' [EiseltSandblom] B&B.Pdf p 211 (4 pp, 3 Mb), strategies: depth-first, breadth-first, best-bound-first+most fractional (6.2.2, p 217). Soln p 211 .xlsx, .ltx, tree.Pdf (p 211, not 122).

27' [Bron.] prb6.2.Pdf (1 Mb) and prb6.4 (←prb1.6), Bron62.ltx, Bron62ltx.zip (relax.).

28' Wiesemann IP_Wiesemann.pdf (380 kb), IP_Wiese.lp, IP_Wiese_ltx.zip (tree).

29' [Sultan] p395ff.Pdf, p400.xls (count iterations !), p400soln.zip • [EckerKup]prb..Pdf (node 7 wrong ? .xlsx), EckerKup.ltx, tree.Pdf

30' • • • Applied exa.s:  >>>|[Eiselt & Sandblom]| (logical, Boolean, binary variables)

31' • Binary variables Knapsack problem: [Bron.] KnapsackPr4e5.pdf: KnapsPr4.ltx; KnapsPr5.ltx, 5.lpp, 5.pdf

32' • Chen et al.'s "Transformation using 0-1 var.s".pdf.

33' • Beasley 7 prbs.: (IP_Beasley_pdf.zip, solved or illustrative) prb1, blending IP_Beasley.pdf, limiting var.s and constr.s (with areas for IP or BIP use)

34' • Wikipedia: Travelling salesman problem (TSP) • 1992EJOR_Laporte.pdf, an overview • (CD) TSP_prototype.pdf

35' • %, as AP: [Bron.] prb9.6.Pdf (1 Mb) (prb9.6&18.xls, tree18.pdf ?)

36' • TSP as AP relaxation: (Parviainen, LUT.fi) #tsp5_2.pdf (=), LUTtspltx.zip, LUTtspap.xlsx (AP relaxation: 2 or more subproblems !) • TSP_Raffensperger.ppsx (sl. 1–7) • Covering (visiting) TSP_data.xlsx tray points (Carpaneto....)

* Revisions • Transportation problem.xlsx, with tolls, models.pdf • Simulation of distance.xlsx in a circle (COUNTIF) • "Julia".pdf.

37' • Beasley IP (Tutorials): "4 variants of product" manufacture, question, solution, answer.xlsx, =.ltx;  Project selection question, solution, answer.xlsx, =.ltx • Vandenberghe ilp.pdf (facility location, B&B), =.xlsx =.ltx (& see log)

38' • How to snatch into Excel • How to pilfer a 'ppsx' ? (save 'ppsx', start PP, open 'ppsx', etc.). See DePaul (above) and M/M/1, M/M/s (Kendall, Erlang). Mark Hillier.xlsx.

39' • LP w/ bin. var., fix cost.mp4 • IntegerProg.pptx (pptx or ppsx; 103 sl.: exa.s 45 bin 49 57 59 62 71 fixCh 87)

40' • Exam problems: cinetica.jpg, .xlsx; Plymax.jpg; exam1.pdf

• Boston Univ. • #Craw • IMSL lib.s • mc, Monte Carlo • MILP search (Mixed Integer Linear Programming) • NAG, Fortran library • NEOS (Network-Enabled Optimization Sys.) — ANL (Argonne Nat'l Lab.), MCS (Maths. & Computer Sci.), #OTC (Opt. Technology Center) • #QSB • TSP, travelling salesman problem • WolfrMW, Wolfram MathWorld (Mathematica)

• Dictionaries, etc....: optimum (n./adj.), greatest degree / best, most advantageous ← L., neut. s. of optimus (used as superl. of bonus, "good") ← ops, "power" (related to opt ← Fr. opter) • solution (soln.), an action or process of solving a problem; answer to a problem; specifically, a set of values of the variables that satisfies an equation • {un|a}symmetric(al) (sci.: -symmetric ?), symmetrical • to prune, to cut off parts (eg., tree branches) for better shape, more fruits (podar .pt .es, élaguer .fr, potare .it, stutzen .de) • to fathom, to measure by a sounding line (to evaluate)

• Bibliography  H&L [Hillier & Lieberman, 2005]; BronNaad [Bronson & Naadimuthu, 1997]; [Chen et al., 2010 (book !)]
EckerKup [Ecker & Kupferschmid, 1988]; Sultan [Sultan, 1993] • Mathematica, MathWorld, Integrator, Functions Site • NIST/SEMATECH e-Handbook of Statistical Methods • ASQ

(This colour: if in Portuguese) • Math. symbols %, to compute; §, inoper'l; #, unlinked
Link checker
 
 
Valid HTML 4.01! IST http://web.ist.utl.pt/~mcasquilho/acad/or/OperRes_LinearProg.php
Created: ~1999 — Last modified: 2020-10-20