This webapplication solves Linear Programming problems using the Simplex method and offers handy input formats for a Transportation problem*, a Network problem*, and a generic LP problem. Soft limit: solving a transportation problem with 2500 decision variables takes approx. 30 seconds, with 5000 decision variables approx. 4 minutes.

* Input is automatically transformed into Simplex tableau format.

Add specific information to transportation and network problem solution

1. Solve transportation problem

2. Solve network problem

3. Solve LP problem

Output: optimal solution

OUTPUT: OPTIMAL SOLUTION

Your input: 1. Transportation problem

Show explanation and demo case

In this case, demand should be met by supply against minimal transportation costs. The table below shows demand, supply and the transportation cost per quantity for each supply-demand connection. Note that total demand equals total supply (no requirement as such). With r referring to row, and c to column, and X_{rc} to the transport quantity from Supply_{r} to Demand_{c}, the LP problem can be formulated as:

Minimize Σ quantity_{rc} × cost_{rc} , subject to
Σ 1 × X_{rc} ≥ Demand_{c} ∀ c

c

Σ 1 × X_{rc} ≤ Supply_{r} ∀ r

r

Demo data

COST PER QUANTITY

SUPPLY

14

15

16

18

9

4

7

15

20

232

DEMAND

40

334

356

336

18

45

795

59

291

89

585

14

285

234

805

283

440

325

957

330

796

600

26

431

965

600

241

190

417

117

916

631

436

18

763

719

550

396

200

619

689

514

108

874

10

484

933

792

607

322

548

851

715

802

272

30

816

611

225

79

851

425

841

481

500

903

18

899

391

165

155

657

231

757

730

48

282

8

922

320

661

38

726

760

150

891

483

407

4

316

504

123

587

938

706

382

729

547

310

6

751

37

825

754

140

323

229

592

571

914

6

117

706

414

674

275

703

395

315

115

891

12

498

898

858

498

187

411

717

353

560

368

18

169

470

643

433

132

652

898

719

555

444

2

840

336

860

577

112

292

422

294

411

474

20

935

569

443

639

523

549

60

415

409

791

32

753

614

610

426

136

578

118

335

751

494

20

83

572

108

570

241

946

651

762

790

40

36

167

838

963

299

362

90

843

39

50

45

28

517

657

914

79

678

811

173

364

930

593

2

746

440

747

392

946

456

560

462

798

462

Optimal quantities: total costs are 102587

OPTIMAL QUANTITIES

SUPPLY

14

15

16

18

9

4

7

15

20

232

DEMAND

40

4

9

2

2

23

14

1

9

4

26

26

18

18

10

10

30

16

14

18

18

8

8

4

4

6

6

6

6

12

12

18

7

11

2

2

20

7

13

32

32

20

20

36

36

28

28

2

2

TRANSPORTATION PROBLEM (semicolon or tab separated)
1^{st} row = supply 1^{st} column = demand All other cells = transport cost per quantity

Your input: 2. Network problem

Show explanation and demo case

You can define a netwok consisting of nodes and arcs. The decision variables in this type of problem are the arc quantities. Each arc has costs per quantity, a lowerbound (minimum flow quantity) and upperbound (maximum flow quantity). Nodes also have costs. They can be related to incoming quantities - those are effectively added to the arc costs of all incoming arcs of this node. They can also be related to outgoing quantities, added to outgoing arcs costs. Nodes can also have upperbound and lowerbounds that relate to troughput (incoming quantities). By adding dummy nodes and arcs (with zero costs) you can create completely balanced systems and/or make a model better 'readible'. This type of model can also be used to model transitions in time, with an arc representing a transition from time to time+1.

Demo case
The graph below shows a min cost flow problem (source: Google). The arcs are labeled with pairs of numbers: the first number is the capacity and the second number is the cost. The numbers in parentheses next to the nodes represent supplies or demands. Node 0 is a supply node with supply 20, while nodes 3 and 4 are demand nodes, with demands -5 and -15, respectively. (Note: labeling nodes and arcs like 1,2,3...n seems handier, but case has been copied in as is.)

Maximize ΣC_{i} × X_{i} , subject to Σ (A_{ij} × X_{j}) ≤ Bi ∀ i , and X_{j} ≥ 0 ∀ j

j

j

You can also minimize and/or use ≥ and = as restriction type as shown by the demo cases. See also: wikipedia: Linear Programming

Simplex tableau legend

Top row

1^{st} cell = MIN (minimize) or MAX (maximize)

2^{nd} cell = initial goal value = 0

next cells = costs factors C_{j}

All other rows

1^{st} cell = constraint type <= or >= or =

2^{nd} cell = constraint value B_{i}

next cells = values of A_{ij} (optional: can be left empty if zero)

Do not enter slack variables: those are created automatically!

The tableau is prefilled with the transportation problem demo case
Putting the demo case table next to this Simplex tableau you will recognize figures. Note that instead of X_{rc} (20 rows × 10 columns) all has been translated into X_{j} (200 variables sitting on a single row), so X_{r=6,c=3} has become X_{53} that has a value of 16 in the optimal solution.