Least Cost Formulations and Linear Programming

  • Thread starter Thread starter JL
  • Start date Start date
J

JL

I have a need to compute least cost formulations. This seems to be in
the domain of "linear programming" of which I know practially nothing.
Can anyone in the group give me a point in the right direction...are
there any tools/libraries, books, websites, etc.

TIA,
John
 
I have a need to compute least cost formulations. This seems to be in
the domain of "linear programming" of which I know practially nothing.
Can anyone in the group give me a point in the right direction...are
there any tools/libraries, books, websites, etc.
Click to expand...

http://mymc10.tripod.com/commonbasic.htm

http://mymc10.tripod.com/somecommon/LINPROG.TXT

(This is old standard BASIC code).
10 CLS
20 PRINT "LINEAR PROGRAMMING"
30 PRINT
40 DIM A(6,10),B(6)
50 PRINT
60 PRINT "TYPE '1' FOR MAXIMIXATION, OR '-1' FOR MINIMIZATION";
70 INPUT Z
80 Z=-Z
90 PRINT "TYPE NUMBER OF CONSTRAINTS, NUMBER OF VARIABLES";
100 INPUT M,N
110 PRINT "NUMBER OF LESS THAN, EQUAL, GREATER CONSTRAINTS";
120 INPUT L,E,G
130 IF M=L+E+G THEN 160
140 PRINT "DATA ON CONSTRAINTS INCONSISTENT. TRY AGAIN."
150 GOTO 110
160 C=N+M+G
170 C1=C+1
180 C2=N+L+G
190 M1=M+1
200 M2=M+2
210 PRINT
220 FOR I=1 TO M2
230 FOR J=1 TO C1
240 A(I,J)=0
250 NEXT J
260 NEXT I
270 FOR I=1 TO M
280 B(I)=0
290 NEXT I
300 FOR I=1 TO M
310 FOR J=1 TO N
320 READ A(I,J)
330 IF I<=L THEN 350
340 A(M1,J)=A(M1,J)-A(I,J)
350 NEXT J
360 IF I>L THEN 400
370 B(I)=N+I
380 A(I,N+1)=1
390 GOTO 460
400 B(I)=N+G+I
410 A(I,J+G+I)=1
420 IF I>L+E THEN 440
430 GOTO 460
440 A(I,N+I-E)=-1
450 A(M1,N+I-E)=1
460 NEXT I
470 FOR I=1 TO M
480 READ A(I,C1)
490 NEXT I
500 FOR J=1 TO N
510 READ A(M2,J)
520 A(M2,J)=Z*A(M2,J)
530 NEXT J
540 PRINT
550 P1=1
560 PRINT "YOUR VARIABLES ";P1;"THROUGH";N
570 IF L=0 THEN 590
580 PRINT "SLACK VARIABLES";N+1;"THROUGH";N+L
590 IF G=0 THEN 610
600 PRINT "SURPLUS VARIABLES";N+L+1;"THROUGH";C
610 IF L=M THEN 790
620 PRINT "ARTIFICIAL VARIABLES";C2+1;"THROUGH";C
630 M3=M1
640 GOSUB 1040
650 PRINT
660 FOR I1=1 TO M
670 IF B(I1)<=C2 THEN 780
680 IF A(I1,C1)<=.00001 THEN 710
690 PRINT "THE PROBLEM HAS NO FEASIBLE SOLUTION."
700 GOTO 3060
710 FOR J1=1 TO C2
720 IF ABS(A(I1,J1))<=.00001 THEN 770
730 R=I1
740 S=J1
750 GOSUB 1270
760 J1=C2
770 NEXT J1
780 NEXT I1
790 P1=2
800 PRINT
810 M3=M2
820 GOSUB 1040
830 PRINT
840 PRINT "ANWWERS:"
850 PRINT "PRIMAL VARIABLES:"
860 PRINT "VARIABLES","VALUE"
870 FOR J=1 TO C2
880 FOR I=1 TO M
890 IF B(I)<>J THEN 920
900 PRINT J,A(I,C1)
910 I=M
920 NEXT I
930 NEXT J
940 PRINT "DUAL VARIABLES:"
950 PRINT "VARIABLE","VALUE"
960 IF L=0 THEN 1000
970 FOR I=1 TO L
980 PRINT I,-Z*A(M2,N+I)
990 NEXT I
1000 PRINT "VALUE OF OBJECTIVE FUNCTION";-Z*A(M2,C1)
1010 PRINT
1020 PRINT
1030 GOTO 3060
1040 P=-.00001
1050 FOR J=1 TO C2
1060 IF A(M3,J)>=P THEN 1090
1070 S=J
1080 P=A(M3,J)
1090 NEXT J
1100 IF P=-.00001 THEN 1450
1110 GOSUB 1140
1120 GOSUB 1220
1130 GOTO 1040
1140 Q=1.E+38
1150 FOR I=1 TO M
1160 IF A(I,S)<=.00001 THEN 1200
1170 IF A(I,C1)/A(I,S)>=Q THEN 1200
1180 R=I
1190 Q=A(I,C1)/A(I,S)
1200 NEXT I
1210 RETURN
1220 IF Q=1.E+38 THEN 1250
1230 GOSUB 1270
1240 RETURN
1250 PRINT "THEN SOLUTION IS UNBOUNDED."
1260 GOTO 3060
1270 P=A(R,S)
1280 FOR I=1 TO M2
1290 IF I=R THEN 1360
1300 FOR J=1 TO C1
1310 IF J=S THEN 1350
1320 A(I,J)=A(I,J)-A(I,S)*A(R,J)/P
1330 IF ABS(A(I,J))>=.00001 THEN 1350
1340 A(I,J)=0
1350 NEXT J
1360 NEXT I
1370 FOR J=1 TO C1
1380 A(R,J)=A(R,J)/P
1390 NEXT J
1400 FOR I=1 TO M2
1410 A(I,S)=0
1420 NEXT I
1430 A(R,S)=1
1440 B(R)=S
1450 RETURN
3000 DATA 1,1,1,1,1
3010 DATA .9,.8,.95,.7,.3
3020 DATA .05,.05,.02,.3,.7
3030 DATA .05,.15,.03,0,0
3040 DATA 100,83,14,3
3050 DATA 6.13,7.12,5.85,4.57,3.96
3060 END
 
Thanks Homer and Andrew...I especially needed the Asprin link LOL.

John
Click to expand...

See also http://www2.isye.gatech.edu/~spyros/LP/LP.html - An Introduction to
Linear Programming and the Simplex Algorithm

As I like to say, for a given set of ingredients and costs, I can compute
the lowest cost pet food formulation which will kill no more than the
allowable percentage of kittens or puppies as you prefer.
 
JL,

In my opinion is VBNet (as is any managed code so as well C# and C++
managed) never the tool if this comes in question.

Just my thought,

Cor
 
Hi Cor,
Thanks for the input. What language do you recommend?
Click to expand...

The algorithms are already available in Basic and there is no perceived
benefit to translating them to another language.

VB is the best at self documenting as anyone who has tried to read APL, Perl
or Python must surely agree.
 
Why should VB.NET never be consider for this problem?Because in my opinion the first goal (as any OOP language) is not
performance however maintainability. There are very few applications todays
that real needs that low lever performance and than we have in my opinion to
go back to languages as real C or direct assembler.

However, just my thought,

Cor
 
Cor Ligthert said:
Because in my opinion the first goal (as any OOP language) is not
performance however maintainability.
Click to expand...

Writing procedures is still possible in VB.NET and non-OO. I don't see why
a programming language like VB.NET which /supports/ OO as it supports
procedural programming should be less suitable for writing algorithms than
other languages like C or assembler. Moreover I believe that VB.NET's
high-level syntax ('Select Case', ...) is more suitable for writing
algorithms than C because its syntax is closer to pseudo-code.
 
Why should VB.NET never be consider for this problem?
Click to expand...

There is no reason. These algorithms run perfectly fine in interpreted MS
Basic on a 1 MHz processor. Running them in a compiled language (CLR) on a 3
GHz machine is hardly likely to result in a lower performance. Most of the
processor time will be used to provide graphics support.

Write in a language you are comfortable with and which is maintainable. I've
seen horrible software written in VC++ "for speed", ignoring the obvious
fact that it is mainly dealing with people typing and mousing - not the
fastest input system known to man.
 
Cor,

Sure, you'll gain some speed by using a low level language, but it may
not be worth the added complexity. I have worked on several applied
optimization problems and in each case we decided the marginal
difference in performance just wasn't worth it. That doesn't mean I'd
recommend VB.NET for everything. I just think it might be a mistake to
not consider it in this case.

Brian
 
Cor,

Sure, you'll gain some speed by using a low level language, but it may
not be worth the added complexity. I have worked on several applied
optimization problems and in each case we decided the marginal
difference in performance just wasn't worth it. That doesn't mean I'd
recommend VB.NET for everything. I just think it might be a mistake to
not consider it in this case.
Click to expand...

I was once asked to look at a module to compute the projection of a flat map
onto the surface of the earth, allowing for the oblate spheroid shape. I was
prepared to hand code this complex algorithm in coprocessor assembly
language, however a test in Visual C++ showed that we could run 10,000 loops
in a few seconds so there was no point since we only needed to run a handful
in response to manual input from a user.
 
Brian,
Sure, you'll gain some speed by using a low level language, but it may
not be worth the added complexity. I have worked on several applied
optimization problems and in each case we decided the marginal
difference in performance just wasn't worth it. That doesn't mean I'd
recommend VB.NET for everything. I just think it might be a mistake to
not consider it in this case.
Click to expand...
As I always say, however than I get answers as. "How can you say that,
withouth knowing for what it is". It is for a real time depending
environment. And to make that complete after a while once was written that
it was in a webapplication.

:-)

Cor
 
Herfried,
Writing procedures is still possible in VB.NET and non-OO. I don't see
why a programming language like VB.NET which /supports/ OO as it supports
procedural programming should be less suitable for writing algorithms than
other languages like C or assembler. Moreover I believe that VB.NET's
high-level syntax ('Select Case', ...) is more suitable for writing
algorithms than C because its syntax is closer to pseudo-code.
Click to expand...

Will I show you the messages from a guy named Herfried K. Wagner about
writing drivers?

You know very well that mostly my answer is more in the "Why" trend what I
did not wanted to do because of some of the obvious reactions I get than on
that question. And last week I was not so good able to answer those.

:-)

Cor
 
Cor Ligthert said:
Will I show you the messages from a guy named Herfried K. Wagner about
writing drivers?
Click to expand...

Implementing algorithms (in general) is something different from
implementing low-level (real-time) hardware-related functionality.
 
As I always say, however than I get answers as. "How can you say that,
withouth knowing for what it is". It is for a real time depending
environment. And to make that complete after a while once was written that
it was in a webapplication.
Click to expand...

The OP didn't suggest a web application.
 
Back
Top