469,607 Members | 1,922 Online

# Least Cost Formulations and Linear Programming

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
Feb 10 '06 #1
20 2786

"JL" <jo**@marymonte.com> wrote in message
news:a6********************************@4ax.com...
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.

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
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
490 NEXT I
500 FOR J=1 TO N
520 A(M2,J)=Z*A(M2,J)
530 NEXT J
540 PRINT
550 P1=1
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
Feb 12 '06 #2
JL wrote:
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.

http://mathworld.wolfram.com/LinearProgramming.html

This may help, too:-
http://www.aspirin.com/index_en.html

Andrew
Feb 14 '06 #3
Thanks Homer and Andrew...I especially needed the Asprin link LOL.

John

On Tue, 14 Feb 2006 14:40:38 -0000, "Andrew Morton"
<ak*@in-press.co.uk.invalid> wrote:
JL wrote:
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.

http://mathworld.wolfram.com/LinearProgramming.html

This may help, too:-
http://www.aspirin.com/index_en.html

Andrew

Feb 17 '06 #4

"JL" <jo**@marymonte.com> wrote in message
news:nv********************************@4ax.com...
Thanks Homer and Andrew...I especially needed the Asprin link LOL.

John

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.

Feb 17 '06 #5
>
This may help, too:-
http://www.aspirin.com/index_en.html

LOL
Feb 17 '06 #6
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
Feb 17 '06 #7
Hi Homer,
Thanks for the link and the fantastic humor :>)

John

On Fri, 17 Feb 2006 07:48:50 GMT, "Homer J Simpson"
<no****@nowhere.com> wrote:

"JL" <jo**@marymonte.com> wrote in message
news:nv********************************@4ax.com.. .
Thanks Homer and Andrew...I especially needed the Asprin link LOL.

John

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.

Feb 18 '06 #8
Hi Cor,
Thanks for the input. What language do you recommend?

John

On Fri, 17 Feb 2006 09:48:11 +0100, "Cor Ligthert [MVP]"
<no************@planet.nl> wrote:
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

Feb 18 '06 #9

"JL" <jo**@marymonte.com> wrote in message
news:uh********************************@4ax.com...
Hi Cor,
Thanks for the input. What language do you recommend?

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.

Feb 18 '06 #10
Why should VB.NET never be consider for this problem?

Cor Ligthert [MVP] wrote:
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

Feb 18 '06 #11
> 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
Feb 19 '06 #12
"Cor Ligthert [MVP]" <no************@planet.nl> schrieb:
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.

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.

--
M S Herfried K. Wagner
M V P <URL:http://dotnet.mvps.org/>
V B <URL:http://classicvb.org/petition/>

Feb 19 '06 #13

"Brian Gideon" <br*********@yahoo.com> wrote in message
Why should VB.NET never be consider for this problem?

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.

Feb 19 '06 #14
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 Ligthert [MVP] wrote:
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

Feb 19 '06 #15

"Brian Gideon" <br*********@yahoo.com> wrote in message
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.

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.

Feb 19 '06 #16
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.

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
Feb 20 '06 #17
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.

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
Feb 20 '06 #18
"Cor Ligthert [MVP]" <no************@planet.nl> schrieb:
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.

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

Implementing algorithms (in general) is something different from
implementing low-level (real-time) hardware-related functionality.

--
M S Herfried K. Wagner
M V P <URL:http://dotnet.mvps.org/>
V B <URL:http://classicvb.org/petition/>

Feb 20 '06 #19

"Cor Ligthert [MVP]" <no************@planet.nl> wrote in message
news:uR**************@TK2MSFTNGP15.phx.gbl...
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.

The OP didn't suggest a web application.
Feb 21 '06 #20
As follow up to my own question and for reference to those who may
have a similar need, check out the following Yahoo group and the
lp_solve DLL which is easily integrated to VB.Net and is both free and
supported by a fairly active discussion group.

http://groups.yahoo.com/group/lp_solve/

Thanks to all who replied!

John
On Fri, 10 Feb 2006 11:45:03 -0800, JL <jo**@marymonte.com> wrote:
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

Feb 24 '06 #21

### This discussion thread is closed

Replies have been disabled for this discussion.